I have been working on speeding up a query I'm using for about a week now and asked several questions about it here ( How can I speed up fetching the results after running an sqlite query?, Is it normal that sqlite.fetchall() is so slow?, How to use min() and max() in an efficient way?).
With the very useful help from the answers given there I managed to get the time down to the sqlite query taking 100.95 seconds and fetchall taking: 1485.43. This was still not enough, so after trying out some different indexes I managed to get the query time down to 0.08 seconds for one sample and the fetchall time down to 54.97 seconds. So I thought I finally managed to speed things up enough.
Then the query runs for the next sample, taking 0.58 seconds, and the fetchall taking 3952.80 seconds. For the third sample the query took 1.01 seconds and took 1970.67 seconds to fetchall.
The first sample fetched 12951 rows, the second sample 24972 rows and the third 6470 rows. I'm very curious why the first sample was so much faster to fetch the rows, when it had only about half the amount to fetch as the second example.
Code (spectrumFeature_inputValues is (1,), (2,) and (3,), from the 3 samples used.):
self.cursor.execute('begin')
self.cursor.execute("EXPLAIN QUERY PLAN "+
"SELECT precursor_id, feature_table_id "+
"FROM `MSMS_precursor` "+
"INNER JOIN `spectrum` ON spectrum.spectrum_id = MSMS_precursor.spectrum_spectrum_id "+
"INNER JOIN `feature` ON feature.msrun_msrun_id = spectrum.msrun_msrun_id "+
"WHERE spectrum.scan_start_time BETWEEN feature.rtMin AND feature.rtMax "+
"AND MSMS_precursor.ion_mz BETWEEN feature.mzMin AND feature.mzMax "+
"AND feature.msrun_msrun_id = ?", spectrumFeature_InputValues)
print 'EXPLAIN QUERY PLAN: '
print self.cursor.fetchall()
import time
time0 = time.time()
self.cursor.execute("SELECT precursor_id, feature_table_id "+
"FROM `MSMS_precursor` "+
"INNER JOIN `spectrum` ON spectrum.spectrum_id = MSMS_precursor.spectrum_spectrum_id "+
"INNER JOIN `feature` ON feature.msrun_msrun_id = spectrum.msrun_msrun_id "+
"WHERE spectrum.scan_start_time BETWEEN feature.rtMin AND feature.rtMax "+
"AND MSMS_precursor.ion_mz BETWEEN feature.mzMin AND feature.mzMax "+
"AND feature.msrun_msrun_id = ?", spectrumFeature_InputValues)
print 'query took:',time.time()-time0,'seconds'
time0 = time.time()
precursorFeatureIds = self.cursor.fetchall()
print 'it fetched:',len(precursorFeatureIds),'rows'
print 'fetchall took',time.time()-time0,'seconds'
time0 = time.time()
for precursorAndFeatureID in precursorFeatureIds:
feature_has_MSMS_precursor_inputValues = (precursorAndFeatureID[0], precursorAndFeatureID[1])
self.cursor.execute("INSERT INTO `feature_has_MSMS_precursor` VALUES(?,?)", feature_has_MSMS_precursor_inputValues)
print 'inserting took',time.time()-time0,'seconds'
self.connection.commit()
and the results:
EXPLAIN QUERY PLAN:
[(0, 0, 2, u'SCAN TABLE feature (~100000 rows)'), (0, 1, 1, u'SEARCH TABLE spectrum USING INDEX fk_spectrum_scahn_start_time_1 (scan_start_time>? AND scan_start_time<?) (~3125 rows)'), (0, 2, 0, u'SEARCH TABLE MSMS_precursor USING INDEX fk_MSMS_precursor_spectrum_spectrum_id_1 (spectrum_spectrum_id=?) (~5 rows)')]
query took: 0.0754859447479 seconds
it fetched: 12951 rows
fetchall took 54.2855291367 seconds
inserting took 0.602859973907 seconds
It took 54.9704811573 seconds
EXPLAIN QUERY PLAN:
[(0, 0, 2, u'SCAN TABLE feature (~100000 rows)'), (0, 1, 1, u'SEARCH TABLE spectrum USING INDEX fk_spectrum_scahn_start_time_1 (scan_start_time>? AND scan_start_time<?) (~3125 rows)'), (0, 2, 0, u'SEARCH TABLE MSMS_precursor USING INDEX fk_MSMS_precursor_spectrum_spectrum_id_1 (spectrum_spectrum_id=?) (~5 rows)')]
query took: 0.579694032669 seconds
it fetched: 24972 rows
fetchall took 3950.08093309 seconds
inserting took 2.11575508118 seconds
It took 3952.80745602 seconds
EXPLAIN QUERY PLAN:
[(0, 0, 2, u'SCAN TABLE feature (~100000 rows)'), (0, 1, 1, u'SEARCH TABLE spectrum USING INDEX fk_spectrum_scahn_start_time_1 (scan_start_time>? AND scan_start_time<?) (~3125 rows)'), (0, 2, 0, u'SEARCH TABLE MSMS_precursor USING INDEX fk_MSMS_precursor_spectrum_spectrum_id_1 (spectrum_spectrum_id=?) (~5 rows)')]
query took: 1.01185703278 seconds
it fetched: 6470 rows
fetchall took 1970.622962 seconds
inserting took 0.673867940903 seconds
It took 1972.31343699 seconds
SQLite create statements:
-- -----------------------------------------------------
-- Table `feature`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `feature` (
`feature_table_id` INT PRIMARY KEY NOT NULL ,
`feature_id` VARCHAR(40) NOT NULL ,
`intensity` DOUBLE NOT NULL ,
`overallquality` DOUBLE NOT NULL ,
`charge` INT NOT NULL ,
`content` VARCHAR(45) NOT NULL ,
`intensity_cutoff` DOUBLE NOT NULL,
`mzMin` DOUBLE NULL ,
`mzMax` DOUBLE NULL ,
`rtMin` DOUBLE NULL ,
`rtMax` DOUBLE NULL ,
`msrun_msrun_id` INT NOT NULL ,
CONSTRAINT `fk_feature_msrun1`
FOREIGN KEY (`msrun_msrun_id` )
REFERENCES `msrun` (`msrun_id` )
ON DELETE NO ACTION
ON UPDATE NO ACTION);
CREATE INDEX `fk_mzMin_feature` ON `feature` (`mzMin` ASC);
CREATE INDEX `fk_mzMax_feature` ON `feature` (`mzMax` ASC);
CREATE INDEX `fk_rtMin_feature` ON `feature` (`rtMin` ASC);
CREATE INDEX `fk_rtMax_feature` ON `feature` (`rtMax` ASC);
DROP TABLE IF EXISTS `spectrum`;
-- -----------------------------------------------------
-- Table `spectrum`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `spectrum` (
`spectrum_id` INT PRIMARY KEY NOT NULL ,
`spectrum_index` INT NOT NULL ,
`ms_level` INT NOT NULL ,
`base_peak_mz` DOUBLE NOT NULL ,
`base_peak_intensity` DOUBLE NOT NULL ,
`total_ion_current` DOUBLE NOT NULL ,
`lowest_observes_mz` DOUBLE NOT NULL ,
`highest_observed_mz` DOUBLE NOT NULL ,
`scan_start_time` DOUBLE NOT NULL ,
`ion_injection_time` DOUBLE,
`binary_data_mz` BLOB NOT NULL,
`binary_data_rt` BLOB NOT NULL,
`msrun_msrun_id` INT NOT NULL ,
CONSTRAINT `fk_spectrum_msrun1`
FOREIGN KEY (`msrun_msrun_id` )
REFERENCES `msrun` (`msrun_id` )
ON DELETE NO ACTION
ON UPDATE NO ACTION);
CREATE INDEX `fk_spectrum_spectrum_id_1` ON `spectrum` (`spectrum_id` ASC);
CREATE INDEX `fk_spectrum_scahn_start_time_1` ON `spectrum` (`scan_start_time` ASC);
DROP TABLE IF EXISTS `feature_has_MSMS_precursor`;
-- -----------------------------------------------------
-- Table `spectrum_has_feature`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `feature_has_MSMS_precursor` (
`MSMS_precursor_precursor_id` INT NOT NULL ,
`feature_feature_table_id` INT NOT NULL ,
CONSTRAINT `fk_spectrum_has_feature_spectrum1`
FOREIGN KEY (`MSMS_precursor_precursor_id` )
REFERENCES `MSMS_precursor` (`precursor_id` )
ON DELETE NO ACTION
ON UPDATE NO ACTION,
CONSTRAINT `fk_spectrum_has_feature_feature1`
FOREIGN KEY (`feature_feature_table_id` )
REFERENCES `feature` (`feature_table_id` )
ON DELETE NO ACTION
ON UPDATE NO ACTION);
CREATE INDEX `fk_feature_has_MSMS_precursor_feature1` ON `feature_has_MSMS_precursor` (`feature_feature_table_id` ASC);
CREATE INDEX `fk_feature_has_MSMS_precursor_precursor1` ON `feature_has_MSMS_precursor` (`MSMS_precursor_precursor_id` ASC);
As you can see I have made indexes out of the mz and rt values in both spectrum and feature, because I figured that most time is spent comparing those numbers together.
So why is the first sample so much faster than the second and third? And how does the query time relate to the fetchall time? Most importantly, is there a way I can speed this up?
Update 1:
After talking to a collegaue it's probably because comparing a point to a 2d dimension (the rtMin, rtMax, mzMin, mzMax) will take n^2 time. This roughly corresponds to the second fetchall taking a bit more than 60^2 seconds (aproximate time the first fetchall took) and it retrieved a little less than twice the amount of rows. This doesn't answer any of my questions though.
Update 2:
I tried using R*tree as advised in the comments. I made a new table:
CREATE VIRTUAL TABLE convexhull_edges USING rtree(
feature_feature_table_id,
rtMin, rtMax,
mzMin, mzMax,
);
and change my query to:
self.cursor.execute("SELECT precursor_id, feature_table_id "+
"FROM `MSMS_precursor` "+
"INNER JOIN `spectrum` ON spectrum.spectrum_id = MSMS_precursor.spectrum_spectrum_id "+
"INNER JOIN `feature` ON feature.msrun_msrun_id = spectrum.msrun_msrun_id "+
"INNER JOIN `convexhull_edges` ON convexhull_edges.feature_feature_table_id = feature.feature_table_id "
"WHERE spectrum.scan_start_time BETWEEN convexhull_edges.rtMin AND convexhull_edges.rtMax "+
"AND MSMS_precursor.ion_mz BETWEEN convexhull_edges.mzMin AND convexhull_edges.mzMax "+
"AND feature.msrun_msrun_id = ?", spectrumFeature_InputValues)
This gave the following results:
EXPLAIN QUERY PLAN:
[(0, 0, 3, u'SCAN TABLE convexhull_edges VIRTUAL TABLE INDEX 2: (~0 rows)'), (0, 1, 2, u'SEARCH TABLE feature USING INDEX sqlite_autoindex_feature_1 (feature_table_id=?) (~1 rows)'), (0, 2, 1, u'SEARCH TABLE spectrum USING INDEX fk_spectrum_scahn_start_time_1 (scan_start_time>? AND scan_start_time<?) (~3125 rows)'), (0, 3, 0, u'SEARCH TABLE MSMS_precursor USING INDEX fk_MSMS_precursor_spectrum_spectrum_id_1 (spectrum_spectrum_id=?) (~5 rows)')]
query took: 0.0572800636292 seconds
it fetched: 13140 rows
fetchall took 34.4445540905 seconds
EXPLAIN QUERY PLAN:
[(0, 0, 3, u'SCAN TABLE convexhull_edges VIRTUAL TABLE INDEX 2: (~0 rows)'), (0, 1, 2, u'SEARCH TABLE feature USING INDEX sqlite_autoindex_feature_1 (feature_table_id=?) (~1 rows)'), (0, 2, 1, u'SEARCH TABLE spectrum USING INDEX fk_spectrum_scahn_start_time_1 (scan_start_time>? AND scan_start_time<?) (~3125 rows)'), (0, 3, 0, u'SEARCH TABLE MSMS_precursor USING INDEX fk_MSMS_precursor_spectrum_spectrum_id_1 (spectrum_spectrum_id=?) (~5 rows)')]
query took: 0.819370031357 seconds
it fetched: 25402 rows
fetchall took 3625.72873998 seconds
EXPLAIN QUERY PLAN:
[(0, 0, 3, u'SCAN TABLE convexhull_edges VIRTUAL TABLE INDEX 2: (~0 rows)'), (0, 1, 2, u'SEARCH TABLE feature USING INDEX sqlite_autoindex_feature_1 (feature_table_id=?) (~1 rows)'), (0, 2, 1, u'SEARCH TABLE spectrum USING INDEX fk_spectrum_scahn_start_time_1 (scan_start_time>? AND scan_start_time<?) (~3125 rows)'), (0, 3, 0, u'SEARCH TABLE MSMS_precursor USING INDEX fk_MSMS_precursor_spectrum_spectrum_id_1 (spectrum_spectrum_id=?) (~5 rows)')]
query took: 0.878498077393 seconds
it fetched: 6761 rows
fetchall took 1419.34246588 seconds
inserting took 0.340960025787 seconds
It took 1420.56637716 seconds
So a bit faster than my previous way, but still not fast enough. Next I'm going to try web_bod's solution.
Update 3
Using web_bod's solution I got the following times:
EXPLAIN QUERY PLAN:
[(0, 0, 2, u'SCAN TABLE feature (~100000 rows)'), (0, 1, 1, u'SEARCH TABLE spectrum USING INDEX fk_spectrum_scahn_start_time_1 (scan_start_time>? AND scan_start_time<?) (~3125 rows)'), (0, 2, 0, u'SEARCH TABLE MSMS_precursor USING INDEX fk_MSMS_precursor_spectrum_spectrum_id_1 (spectrum_spectrum_id=?) (~5 rows)')]
query took: 0.0521960258484 seconds
it fetched: 13052 rows
fetchall took 90.5810132027 seconds
EXPLAIN QUERY PLAN:
[(0, 0, 2, u'SCAN TABLE feature (~100000 rows)'), (0, 1, 1, u'SEARCH TABLE spectrum USING INDEX fk_spectrum_scahn_start_time_1 (scan_start_time>? AND scan_start_time<?) (~3125 rows)'), (0, 2, 0, u'SEARCH TABLE MSMS_precursor USING INDEX fk_MSMS_precursor_spectrum_spectrum_id_1 (spectrum_spectrum_id=?) (~5 rows)')]
query took: 0.278959989548 seconds
it fetched: 25195 rows
fetchall took 4310.6012361 seconds
The third one sadly didn't finish because of a reboot. So this is a bit faster than my first solution, but slower than using R*Tree
Update 4
Working on a different query which was going incredibly slow I saw that it was going into an uninterrupted sleep (see this question). So I checked top while running this query and it's switching between R and D state, lowering the CPU usage from 100 to 50%. This could be why it's running so slow with all the solutions provided.
Update 5
I migrated to MySQL but I'm getting the same results.
INNER JOIN'sONclause might help. I had a similar problem with PostgreSQL, and after a lot of time mucking around with it, it wasn't resolvable without a complete schema redesign. The multiple inequalities in yourWHEREclause, running against a non-uniform set of data essentially make this a non-deterministic problem. For us the only solution was implementing a statistics-driven "guessing" logic to reduce the size of data hitting the inequality heap scan (inequalities will usually go through a full heap scan, by the way, index or not). – Dantefetchallruns the query? you give separate times for query and fetching. in all cases query is fast enough. so why are people answering with improved queries? if fetchall is just data retrieval (for data already selected) then surely it is a question of disk ordering, memory caches, etc etc? (but i do not know how sqlite works, so perhaps there is some reason for people focusing on queries - can someone clarify?) – PlainspokenSELECT * FROM random_tablethe fetchall would be a lot faster than selecting the 12000 rows now. Sadly I didn't keep complete track of everythin I tried, but there's been instances where the fetchall was a lot faster than the query. Anyway, the fact that the query only takes about a second while it has to compare a lot of rows indicates that the speed of the fetchall is definetly dependent on the query. – Cohort