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


He estado trabajando en 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 los resultados después de ejecutar una consulta sqlite?, ¿Es normal que sqlite.fetchall () sea 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 toma de consultas sqlite 100.95 segundos y tomando fetchall: 1485.43. Esto aún no era suficiente, así que después de probar algunos índices diferentes logré bajar el tiempo de consulta a 0.08 segundos para una muestra y el tiempo de búsqueda hasta 54.97 segundos. Así que pensé que finalmente había logrado acelerar las cosas lo suficiente.

Luego, la consulta se ejecuta para la siguiente muestra, tomando 0.58 segundos, y el fetchall teniendo 3952.80 segundos. Para la tercera muestra, la consulta tomó 1.01 segundos y tomó 1970.67 segundos para buscar.

La primera muestra obtuvo 12951 filas, la segunda muestra 24972 filas y la tercera 6470 filas. Tengo mucha curiosidad de por qué la primera muestra fue mucho más rápida para buscar las filas, cuando solo tenía la mitad de la cantidad que recuperar como 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<?) (~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 crea 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 pueden ver, he hecho índices del mz y rt valores tanto en el espectro como en la característica, porque pensé que pasaría la mayor parte del tiempo comparando esos números.

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 collegaue es probable porque la comparación de un punto con una dimensión 2d (el rtMin, rtMax, mzMin, mzMax) llevará n ^ 2 veces. Esta aproximadamente corresponde al segundo fetchall que toma un poco más de 60 ^ 2 segundos (tiempo aproximado que tomó el primer fetchall) y recuperó un poco menos del doble de la cantidad de filas. Sin embargo, esto no responde ninguna de mis preguntas.


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

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


Actualización 3

Utilizando 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<?) (~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

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 estaba yendo increíblemente lenta, vi que estaba entrando en un sueño ininterrumpido (ver esta pregunta) Así que marqué la parte superior mientras ejecutaba esta consulta y está cambiando entre el estado R y D, lo que reduce el uso de la CPU del 100 al 50%. Esta podría ser la razón por la que funciona tan lento con todas las soluciones proporcionadas.


Actualización 5

Migré a MySQL pero obtengo los mismos resultados.


32
2018-05-10 10:15


origen


Respuestas:


El tiempo de ejecución es geométricamente proporcional al número de filas en cada tabla en lugar de aritméticamente, p. Ej.

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 combinaciones / 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 y luego los espectros no relacionados antes de buscar precursores adecuados.

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

ACTUALIZADO: error solucionado en SQL

Notas:

No tiene que preocuparse por los AND, solo obtendrá:

  • características donde feature.msrun_msrun_id = 'value'
  • espectros para esas características y donde spectrum.scan_start_time BETWEEN subquery.rtMin AND subquery.rtMax
  • precursores para esas espectros y donde MSMS_precursor.ion_mz BETWEEN 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 uniones: los índices de claves externas 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); 

8
2018-05-16 10:49



Te sugiero que intentes usar una Índice de árboles R *, Están diseñados para consultas de rango eficientes.


No he usado mucho R * Tree, solo lea la documentación, pero creo que podría estar utilizándolo incorrectamente. Es posible que desee intentar cambiar su consulta para usar

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 Árbol R *, en lugar de comparar el punto con el rango)


3
2018-05-18 21:00



Considere usar Índices de cobertura en las tablas involucradas en su consulta.

De hecho, está buscando una cantidad limitada de columnas en su select declaración y el correspondiente inner join y where cláusulas. Al usar un índice de cobertura con las columnas ordenadas en él, debe obtener una consulta muy rápida, es decir, eliminará el scan table a favor de un search table usando 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 busque velocidad, también debe insinuarle al planificador de consultas que entienda que msrun_msrun_id es una constante para verificar ambos feature y spectrum mesas. Agregue la prueba constante en su consulta al colocar esta prueba adicional al final de la consulta (y pase spectrumFeature_InputValues dos veces):

"AND spectrum.msrun_msrun_id = ?"

1
2018-05-19 08:45