Hi there! I have a large database and a file with ID-Name pairs in each line, where ID corresponds to the primary key of the table in the database. I need to write all the names from the file into the database using corresponding IDs. Of course, if there is such ID in the table (do not insert a new record if there is no such user with this ID, just UPDATE existing one).

I've written a simple python script for this purpose. I realized that it worked extremely slow. Much slower than it has to be for UPDATE (not even INSERT). ID is a primary key, so it must be indexed automatically and it should not slow down UPDATEs, right?

Then I started experimenting with the script and found that UPDATEs are much faster when IDs are a constant or incrementing for example. The script for experiments are:

    import sqlite3
    import traceback
    import time
    import random
    
    conn = sqlite3.connect('database.sqlite')
    
    c = conn.cursor()
    c.execute('BEGIN')
    
    PERIOD_SEC = 3
    
    prev_tp = 0
    counter = 0
    
    try:
        while True:
            tp = time.time()
            elapsed_sec = tp - prev_tp
            if elapsed_sec > PERIOD_SEC:
                prev_tp = tp
    
                speed = counter / elapsed_sec
    
                print('Speed: %.02f/sec' % (speed))
                counter = 0
    
            c.execute('UPDATE users SET username = ? WHERE id = ?', ('random', 555))
            counter += 1
    
    
        c.execute('COMMIT')
    except Exception:
        c.execute('ROLLBACK')
        traceback.print_exc()

The value of username doesn't affect on performance, so let it be always random. In the example above the ID is constant and equals to 555 (the value doesn't matter, the speed is the same also for big values of ID). For this example the speed is (UPDATEs per second):

Speed: 376665.88/sec
Speed: 404738.08/sec
Speed: 404942.04/sec
Speed: 403681.24/sec

If I replace

c.execute('UPDATE users SET username = ? WHERE id = ?', ('random', 555))

with

c.execute('UPDATE users SET username = ? WHERE id = ?', ('random', inc))

where inc is increased by 1 after every UPDATE, then the results would be:

Speed: 233977.17/sec
Speed: 229630.93/sec
Speed: 223424.88/sec
Speed: 218353.56/sec

It's worse, but it's still not so bad.

But.. If I use a random ID

c.execute('UPDATE users SET username = ? WHERE id = ?', ('random', random.randint(0, 1000000000)))

then the results become disappointing:

Speed: 514.18/sec
Speed: 732.49/sec
Speed: 886.28/sec
Speed: 999.34/sec

More than 100 times slower! I also noticed the bigger range of IDs I choose the slower it becomes, but IDs from that range are always exist in the table.

I also tried using prepared statements (executemany in python). It improves performance a little, maybe 4 times faster, but for random IDs it's still very slow.

So my questions are:

1. Why this happens? I think it may be somehow related to caching, but I don't know if it's normal. I mean in real sutiations IDs are near to random and as I know the performance is not as bad as mine.

2. How to improve performance? Especially, if I have a non-sorted list of ID-Name pairs. Are there other ways besides sorting it and only then writing to the database?

Thanks in advance!

You don't say what the schema is of the table that you're running the UPDATE against, or approximately how many rows are in that table.

I posted the database schema and other details under Gunter Hick's comment.

I created a sample database with a simple schema to demonstrate you the problem. The database is generated using this script: here it is There are no indexes. Total number of records equals to 1.5 billion records and the size of the database is 16.6 GB.

The schema:

0|id|INTEGER|0||1
1|username|TEXT|0||0
2|score|INTEGER|0||0

I've written a simple script for testing UPDATEs performance. Link Uncomment lines starting with "batch = [(123456" to choose which ID to use: constant, incremental or random.

The results:

Constant ID:

Speed: 988930.78/sec (UPDATEs/sec)
Speed: 1114647.55/sec (UPDATEs/sec)
Speed: 972525.72/sec (UPDATEs/sec)
Speed: 980894.68/sec (UPDATEs/sec)
Speed: 1015316.88/sec (UPDATEs/sec)

Incremental ID:

Speed: 1045197.19/sec (UPDATEs/sec)
Speed: 956844.17/sec (UPDATEs/sec)
Speed: 972709.29/sec (UPDATEs/sec)

Random ID:

Speed: 23985.74/sec (UPDATEs/sec)
Speed: 25132.00/sec (UPDATEs/sec)
Speed: 25622.54/sec (UPDATEs/sec)
Speed: 26498.24/sec (UPDATEs/sec)
Speed: 27205.41/sec (UPDATEs/sec)

Random ID is more than 50 times slower than others. It seems like it's related to cache, but anyway are there any ways to optimize it? The database creation takes less than 30 minutes, but updating values at random IDs will take at least 24 hours or even more.

Any ideas? Hope for your help!

I would also note that every update to the database requires deleting and re-allocating the entire row since you have created the database with nothing other than the rowid, and "insert" the data when you "update" it (as you call it).

This is absolutely the most pernicious example and you should expect the absolute worst performance possible (not representative of a functional system or database) performance.

You don't ever commit in your infinite loop, so sqlite.exe only needs to go to disk to

• Get something it doesn't already have in memory.
• To free up memory (toss something it doesn't want to remember, or to make room for something new).

For the first case, not counting the first time through the loop, it likely doesn't need to go to disk at all, and it goes through your loop in about 2.5e-6 seconds.

For the second case, it will want to read/write logically consecutive records in a tree. On most systems, sequential i/o is fast, but it still cuts your speed in half, to about 5e-6 seconds per iteration. Each write to disk averages dozens to hundreds of your points.

For the third case, you are accessing and modifying items more or less at random. On average, each disk i/o gives you slightly less than one point (one point from the leaf record, plus additional records related to the interior of the tree).

Change your tests to do raw i/o. Make a big file.

• Repeatedly read and write 4k at the same offset.
• Repeatedly read and write 4k sequentially.
• Repeatedly read and write 4k at random locations.

You'll see a similar progression in timings.

So you think the only way to improve performance is to sort the IDs?

If your set of random ids spans the whole key space then it will surely slow down as it will need to fetch a lot of data from desk.

That said, it might be beneficial to try and have a large amount of cache. While there will be evictions probably, still you could get value from having many requests hitting the cache. For that I would use mmap and set it to the highest reasonable value for my system. e.g. Pragma mmap = 4 * 1024 * 1024 * 1024 to create a 4GB mmap

Hope that helps