How the Merger Tree Sped Up SQLite Database UPDATEs
@ Stephen Skory | Thursday, Sep 9, 2010 | 5 minute read | Update at Thursday, Sep 9, 2010

The Parallel Merger Tree in yt, like most of the code in yt, has a rich history of changes and upgrades. One of the most significant upgrades was a change in the way the SQLite database file is updated during the course of building the merger tree. Briefly, the database contains all the information about the merger tree of the halos, as well as the specifics of each halo, such as the mass, position or bulk velocity. Originally, the database was built by first filling in all the initially available information about each halo: the data that comes from the halo finder. Then, as the merger tree ran and identified relationships between halos, the entries for each halo would be modified to reflect the new information using the SQL “UPDATE” command. Below is a simplified example of how this worked, using random numbers instead of halo data:

import sqlite3 as sql
import numpy as np
import time, random
# How many random numbers we'll be working with.
number = int(5e5)

# Create and connect to the database.
conn = sql.connect("test.db")
cursor = conn.cursor()
# Make the table we'll be using. The first column will automatically
# generate the integer index for each row starting at 0.
line = "CREATE TABLE randoms
(count INTEGER PRIMARY KEY, value FLOAT);"
cursor.execute(line)

# Make the random numbers.
rnum = np.random.random(number)

t1 = time.time()
# Insert the values the first time.
for r in rnum:
    line = "INSERT INTO randoms VALUES (null, %1.10e);" % r
    cursor.execute(line)
t2 = time.time()

print "First insertion took %1.2e seconds" % (t2-t1)
print "Now let's update the information."
# Make some more random numbers.
rnum2 = np.random.random(number)
# This make an array of integers [0:number-1], with the positions randomly
# placed.
order = np.array(random.sample(xrange(number), number))

t3 = time.time()
# Update the entries.
for pair in zip(order, rnum2):

    line = "UPDATE randoms SET value = %1.10e WHERE count = %d;" % \
            (pair[1], pair[0])
    cursor.execute(line)
t4 = time.time()

print "Update took %1.2e seconds" % (t4-t3)

# Close up properly.
cursor.close()
conn.close()

Running this on my two year old Macbook Pro gives me:

First insertion took
1.79e+01 seconds
Now let's update the information.
Update took 4.58e+01 seconds

Remember that the second operation is putting no more information in the database, it is just changing the data. However, it’s much slower because it must search the database for each entry with the current “count” value. In effect, with each “UPDATE”, the whole database is being read and every entry is being compared to “count” to see if it needs to be changed. There is a “LIMIT” keyword that can be part of an “UPDATE” statement that tells SQLite to only affect a certain number of rows. However, this is not a good solution for two reasons. First, this capability needs to be enabled when the SQLite library is compiled, and it often isn’t. Second, this only reduces the average number of rows searched from N to N/2, which is not a very good improvement.

In the Merger Tree, this “UPDATE” step became the largest single factor in the runtime. This is very bad because in the Parallel Merger Tree, all SQLite writes are done with the root processor, which means all the other tasks sat idle waiting on the root task. A better way was needed!

As it turns out, there is a much faster way. Instead of using “UPDATE”, a second, temporary database is created. As we can even see from the example above, “INSERT” statements are relatively fast, so we would like to use that! As the first database is read in, its values are modified, and then the data is added to the second. After all is said and done, the second database will then replace the first, and the overall effect will be the same.

import sqlite3 as sql

import numpy as np
import time, random
# How many random numbers we'll be working with.
number = int(5e5)

# Create and connect to the database.
conn = sql.connect("test.db")
cursor =
conn.cursor()

# Make the table we'll be using.
line = "CREATE TABLE randoms (count INTEGER PRIMARY KEY, value FLOAT);"
cursor.execute(line)

# Make the random numbers.
rnum = np.random.random(number)

t1 = time.time()
# Insert the values the first time.
for r in rnum:
    line = "INSERT INTO randoms VALUES (null, %1.10e);" % r
    cursor.execute(line)
t2 = time.time()

print "First insertion took %1.2e seconds" % (t2-t1)
print "Now let's update the information in a faster way."
# Make some more random numbers.
rnum2 = np.random.random(number)

t3 = time.time()
# Make a second database.
conn2 = sql.connect("test2.db")
cursor2 = conn2.cursor()
# We need to make the table, again.
line = "CREATE TABLE randoms (count INTEGER PRIMARY KEY, value FLOAT);"
cursor2.execute(line)
# Update the entries by reading in from the first, writing to the second.
line = "SELECT * FROM randoms ORDER BY count;"
cursor.execute(line)
results = cursor.fetchone()
mark = 0
while results:
    line = "INSERT INTO randoms VALUES (%d, %1.10e);" % \
         (results[0], rnum[mark])
    cursor2.execute(line)
    mark += 1
    results = cursor.fetchone()
t4 = time.time()

print "Update took %1.2e seconds" % (t4-t3)

# Close up properly.
cursor.close()
conn.close()
cursor2.close()
conn2.close()

And the timings:

First insertion took
1.55e+01 seconds
Now let's update the information in a faster way.
Update took
1.82e+01 seconds

Of course there will always be some variability in the timings, but the relative differences between the two methods is very clear. In this second method, the update time is just a bit longer than the initial timing. However, the first method was several times longer, for the same overall result. Note that in the second example, the “count” data column is being specified, and even if a new entry is made with a “null” value, SQLite will correctly fill in with the next larger integer with no problem.

The only caveat is that this method will temporarily require roughly double the amount of disk space. This is a minor concern because modern computers have far more disk space than a SQLite database (or two) could ever fill up in a reasonable application.

yt extension modules

yt has many extension packages to help you in your scientific workflow! Check these out, or create your own.

ytini

ytini is set of tools and tutorials for using yt as a tool inside the 3D visual effects software Houdini or a data pre-processor externally to Houdini.

Trident

Trident is a full-featured tool that projects arbitrary sightlines through astrophysical hydrodynamics simulations for generating mock spectral observations of the IGM and CGM.

pyXSIM

pyXSIM is a Python package for simulating X-ray observations from astrophysical sources.

ytree

Analyze merger tree data from multiple sources. It’s yt for merger trees!

yt_idv

yt_idv is a package for interactive volume rendering with yt! It provides interactive visualization using OpenGL for datasets loaded in yt. It is written to provide both scripting and interactive access.

widgyts

widgyts is a jupyter widgets extension for yt, backed by rust/webassembly to allow for browser-based, interactive exploration of data from yt.

yt_astro_analysis

yt_astro_analysis is the yt extension package for astrophysical analysis.

Make your own!!

Finally, check out our development docs on writing your own yt extensions!

Contributing to the Blog

Are you interested in contributing to the yt blog?

Check out our post on contributing to the blog for a guide!

We welcome contributions from all members of the yt community. Feel free to reach out if you need any help.

the yt data hub

The yt hub at https://girder.hub.yt/ has a ton of resources to check out, whether you have yt installed or not.

The collections host all sorts of data that can be loaded with yt. Some have been used in publications, and others are used as sample frontend data for yt. Maybe there’s data from your simulation software?

The rafts host the yt quickstart notebooks, where you can interact with yt in the browser, without needing to install it locally. Check out some of the other rafts too, like the widgyts release notebooks – a demo of the widgyts yt extension pacakge; or the notebooks from the CCA workshop – a user’s workshop on using yt.

Social Links