Very slow select query, how can I speed this up?

Question

I asked two related questions ( How can I speed up fetching the results after running an sqlite query? and Is it normal that sqlite.fetchall() is so slow?). I've changed some things around and got some speed-up, but it still takes over an hour for the select statement to finish. I've got a table `feature` which contains an `rtMin`, `rtMax`, `mzMin` and `mzMax` value. These values together are the corners of a rectangle (if you read my old questions, I save these values separatly instead of getting the min() and max() from the `convexhull` table, works faster). And I got a table `spectrum` with an `rt` and an `mz` value. I have a table which links features to spectra when the `rt`and `mz`value of the spectrum is in the rectangle of the feature. To do this I use the following sql and python code to retrieve the ids of the spectrum and feature: ``` self.cursor.execute("SELECT spectrum_id, feature_table_id "+ "FROM `spectrum` "+ "INNER JOIN `feature` "+ "ON feature.msrun_msrun_id = spectr…

Accepted Answer

You are correlating two big tables. Some quick math: 300k x 20k = 6 billion rows. If it was just a matter of returning all these rows, then you would surely be I/O bound (but really only on the (O)utput side). However, your where clause filters out almost everything, as you only have 10k rows returned so you are for sure CPU bound here. SQLite can't use more than one index at a time, with the exception of what is called the "OR optimizations". Furthermore, you don't get any performance gain from inner joins as they "are converted into additional terms of the WHERE clause". Bottom line is that SQLite will not be able to execute your query as efficiently as say `postgresql` et al. I played around with your scenario as I was curious to see by how much your query can be optimized. Ultimately, it seems that the best optimization is to remove all explicit indices (!). It seems that SQLite figures some on-the-fly index/indices that results in better performance than the different approaches I tried. As a demonstration, consider this schema derived from yours: ``` CREATE TABLE feature ( -- 300k feature_id INTEGER PRIMARY KEY, mzMin DOUBLE, mzMax DOUBLE, rtMin DOUBLE, rtMax DOUBLE, lnk_feature INT); CREATE TABLE spectrum ( -- 20k spectrum_id INTEGER PRIMARY KEY, mz DOUBLE, rt DOUBLE, lnk_spectrum INT); ``` `feature` has 300k rows, and `spectrum` 20k (the python code that does this is somewhere below). There is no explicit index specified, only implicit ones due to the definition `INTEGER PRIMARY KEY`: INTEGER PRIMARY KEY columns aside, both UNIQUE and PRIMARY KEY constraints are implemented by creating an index in the database (in the same way as a "CREATE UNIQUE INDEX" statement would). Such an index is used like any other index in the database to optimize queries. As a result, there often no advantage (but significant overhead) in creating an index on a set of columns that are already collectively subject to a UNIQUE or PRIMARY KEY constraint. Using the schema above, SQLite mentions it would create an index during the life of the query on `lnk_feature`: ``` sqlite> EXPLAIN QUERY PLAN SELECT feature_id, spectrum_id FROM spectrum, feature ...> WHERE lnk_feature = lnk_spectrum ...> AND rt >= rtMin AND rt <= rtMax ...> AND mz >= mzMin AND mz <= mzMax; 0|0|0|SCAN TABLE spectrum (~20000 rows) 0|1|1|SEARCH TABLE feature USING AUTOMATIC COVERING INDEX (lnk_feature=?) (~7 rows) ``` And even though I tested with an index on that column, or other columns, it seems that the fastest way to run that query is without any of those indices. The fastest I ran the query above using python is 20 minutes. This includes the completion of `.fetchall()`. You mention that you will have 150 times more rows at some point. I'd start looking into `postgresql` if I were you ;-)... Note that you could split the work in threads and potentially divide the time to complete the query by the number of threads that will be able to run concurrently (i.e. by the number of CPUs available). In any case, here is the code I used. Can you run it yourself and report back how fast the query ran in your environment. Note that I am using `apsw`, so if you can't use it you'll need to tweak to use your own sqlite3 module. ``` #!/usr/bin/python import apsw, random as rand, time def populate(cu): cu.execute(""" CREATE TABLE feature ( -- 300k feature_id INTEGER PRIMARY KEY, mzMin DOUBLE, mzMax DOUBLE, rtMin DOUBLE, rtMax DOUBLE, lnk_feature INT); CREATE TABLE spectrum ( -- 20k spectrum_id INTEGER PRIMARY KEY, mz DOUBLE, rt DOUBLE, lnk_spectrum INT);""") cu.execute("BEGIN") for i in range(300000): ((mzMin, mzMax), (rtMin, rtMax)) = (get_min_max(), get_min_max()) cu.execute("INSERT INTO feature VALUES (NULL,%s,%s,%s,%s,%s)" % (mzMin, mzMax, rtMin, rtMax, get_lnk())) for i in range(20000): cu.execute("INSERT INTO spectrum VALUES (NULL,%s,%s,%s)" % (get_in_between(), get_in_between(), get_lnk())) cu.execute("COMMIT") cu.execute("ANALYZE") def get_lnk(): return rand.randint(1, 2) def get_min_max(): return sorted((rand.normalvariate(0.5, 0.004), rand.normalvariate(0.5, 0.004))) def get_in_between(): return rand.normalvariate(0.5, 0.49) def select(cu): sql = """ SELECT feature_id, spectrum_id FROM spectrum, feature WHERE lnk_feature = lnk_spectrum AND rt >= rtMin AND rt <= rtMax AND mz >= mzMin AND mz <= mzMax""" start = time.time() cu.execute(sql) print ("%s rows; %.2f seconds" % (len(cu.fetchall()), time.time() - start)) cu = apsw.Connection('foo.db').cursor() populate(cu) select(cu) ``` Output I get: ``` 54626 rows; 1210.96 seconds ```

Very slow select query, how can I speed this up?

Solution

Problem