¿Por qué la misma consulta SQLite es 30 veces más lenta cuando obtiene solo el doble de resultados?

He estado trabajando para acelerar una consulta que estoy usando durante aproximadamente una semana y he hecho varias preguntas al respecto aquí ( ¿Cómo puedo acelerar la obtención de resultados después de ejecutar una consulta de sqlite? ¿Es normal que sqlite.fetchall ()? es tan lento?, ¿Cómo usar min () y max () de una manera eficiente?

Con la ayuda muy útil de las respuestas dadas allí logré bajar el tiempo a la consulta de sqlite tomando 100.95 segundos y tomando 1485.43 : 1485.43 . Esto aún no era suficiente, así que, después de probar algunos índices diferentes, logré reducir el tiempo de consulta a 0.08 segundos para una muestra y el tiempo de recuperación a 54.97 segundos. Así que pensé que finalmente logré acelerar las cosas lo suficiente.

Luego, la consulta se ejecuta para la siguiente muestra, tomando 0.58 segundos, y la búsqueda toma 3952.80 segundos. Para la tercera muestra, la consulta tomó 1.01 segundos y tomó 1970.67 segundos para fetchall.

La primera muestra obtuvo 12951 filas, la segunda muestra 24972 filas y la tercera 6470 filas. Tengo mucha curiosidad por la razón por la cual la primera muestra fue mucho más rápida para buscar las filas, cuando solo tenía aproximadamente la mitad de la cantidad a recuperar como el segundo ejemplo.


Código ( spectrumFeature_inputValues es (1,), (2,) y (3,), de las 3 muestras utilizadas.):

 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() 

y los resultados:

 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? AND 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 crear declaraciones:

 -- ----------------------------------------------------- -- 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); 

Como puede ver, he hecho índices a partir de los valores de mz y rt tanto en el espectro como en la característica, porque pensé que la mayor parte del tiempo se invierte en comparar esos números juntos.

Entonces, ¿por qué la primera muestra es mucho más rápida que la segunda y la tercera? ¿Y cómo se relaciona el tiempo de consulta con el tiempo de búsqueda? Lo más importante, ¿hay alguna manera de acelerar esto?


Actualización 1:

Después de hablar con un colega es probablemente porque la comparación de un punto con una dimensión 2d (rtMin, rtMax, mzMin, mzMax) tomará n ^ 2 tiempo. Esto corresponde aproximadamente al segundo fetchall que toma un poco más de 60 ^ 2 segundos (el tiempo aproximado que tomó el primer fetchall) y recuperó un poco menos del doble de la cantidad de filas. Esto no responde ninguna de mis preguntas sin embargo.


Actualización 2:

Intenté usar R * tree como se aconseja en los comentarios. Hice una nueva mesa:

 CREATE VIRTUAL TABLE convexhull_edges USING rtree( feature_feature_table_id, rtMin, rtMax, mzMin, mzMax, ); 

y cambiar mi consulta a:

 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) 

Esto dio los siguientes resultados:

 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? AND 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 

Así que un poco más rápido que mi forma anterior, pero todavía no lo suficientemente rápido. A continuación voy a probar la solución de web_bod.


Actualización 3

Usando la solución de web_bod obtuve los siguientes tiempos:

 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? 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 

El tercero lamentablemente no terminó debido a un reinicio. Así que esto es un poco más rápido que mi primera solución, pero más lento que usar R * Tree


Actualización 4

Trabajando en una consulta diferente que iba increíblemente lenta, vi que iba a tener un sueño ininterrumpido (consulte esta pregunta ). Así que revisé la parte superior mientras ejecutaba esta consulta y está cambiando entre los estados R y D, reduciendo el uso de la CPU de 100 a 50%. Esta podría ser la razón por la que funciona tan lento con todas las soluciones provistas.


Actualización 5

Migré a MySQL pero estoy obteniendo los mismos resultados.

El tiempo de ejecución geométricamente proporcional al número de filas en cada tabla en lugar de aritméticamente, por ejemplo

 3 tables with 10 rows each => 1,000 comparision 3 tables with 10, 10 and 40 rows => 4,000 comparisons 3 tables with 20 rows each => 8,000 comparisons 

Probablemente podría volver a factorizar la consulta para evitar algunas de las uniones / cursores. ¿Cuándo necesita una respuesta?

¿Podrías hacer algo como esto?

 SELECT precursor_id, feature_table_id FROM MSMS_precursor INNER JOIN ( SELECT mzMin, mzMax, rtMin, rtMax, spectrum_id, feature_table_id, msrun_msrun_id FROM spectrum INNER JOIN (select feature_table_id, mzMin, mzMax, rtMin, rtMax, msrun_msrun_id from feature where feature.msrun_msrun_id = 'value' ) subquery ON subquery.msrun_msrun_id = spectrum.msrun_msrun_id WHERE spectrum.scan_start_time BETWEEN subquery.rtMin AND subquery.rtMax ) subquery ON subquery.spectrum_id = MSMS_precursor.spectrum_spectrum_id WHERE MSMS_precursor.ion_mz BETWEEN subquery.mzMin AND subquery.mzMax 

El uso de una subconsulta le permite reducir el número de comparaciones entre las tablas; puede filtrar rápidamente las características no deseadas, luego los espectros no relacionados antes de buscar los precursores adecuados.

No uso SQLLite, pero el principio aún debería aplicarse.

ACTUALIZADO: error corregido en SQL

Notas:

No tienes que preocuparte por los AND, solo obtendrás:

  • características donde feature.msrun_msrun_id = ‘valor’
  • espectros para esas características y donde spectrum.scan_start_time ENTRE subquery.rtMin AND subquery.rtMax
  • precursores para esos espectros y donde MSMS_precursor.ion_mz ENTRE subquery.mzMin AND subquery.mzMax

ACTUALIZACIÓN 18 / mayo:

Es la indexación !!! tiene índices en los campos de búsqueda, pero no en los campos que participan en las combinaciones: los índices de clave externa realmente mejoran el rendimiento:

 CREATE INDEX `fk_msrun_msrun_id_feature` ON `feature` (`msrun_msrun_id` ASC); CREATE INDEX `fk_spectrum_spectrum_id_feature` ON `feature` (`msrun_msrun_id` ASC); CREATE INDEX `fk_spectrum_spectrum_id_MSMS_precursor` ON `MSMS_precursor` (`spectrum_spectrum_id` ASC); 

Le sugiero que intente usar un índice R * Tree , están diseñados para consultas de rango eficiente.


En realidad no he usado mucho R * Tree, solo leí la documentación, pero creo que podría estar usándolo incorrectamente. Es posible que desee intentar cambiar su consulta para utilizar

 WHERE convexhull_edges.rtMin <= spectrum.scan_start_time AND convexhull_edges.rtMax >= spectrum.scan_start_time AND convexhull_edges.mzMin <= MSMS_precursor.ion_mz AND convexhull_edges.mzMax >= MSMS_precursor.ion_mz 

que debería ser equivalente a su consulta actual, pero creo que debería ser más rápido (debería elegir un rango del R * Tree, en lugar de comparar el punto con el rango)

Considere utilizar índices de cobertura en las tablas involucradas en su consulta.

De hecho, está obteniendo una cantidad limitada de columnas en su statement de select y en la inner join correspondiente y where cláusulas where . Al usar un índice de cobertura con las columnas bien ordenadas en él, debería obtener una consulta muy rápida, es decir, eliminará la scan table en favor de una search table utilizando un covering index .

Intenta usar esos índices en tus tablas:

 CREATE INDEX `fk_covering_feature` ON `feature` (`msrun_msrun_id`,`mzMin`,`mzMax`,`rtMin`,`rtMax`,`feature_table_id`); CREATE INDEX `fk_covering_spectrum` ON `spectrum` (`msrun_msrun_id`,`scan_start_time`,`spectrum_id`); CREATE INDEX `fk_covering_MSMS_precursor` ON `MSMS_precursor` (`spectrum_spectrum_id`,`ion_mz`,`precursor_id`); 

Cuando vaya a la velocidad, también debe sugerir al planificador de consultas que comprenda que msrun_msrun_id es una constante para verificar las tablas de feature y de spectrum . Agregue la prueba constante en su consulta colocando esta prueba adicional al final de la consulta (y pase dos veces el valor del spectrumFeature_InputValues ):

 "AND spectrum.msrun_msrun_id = ?"