Pourquoi cette requête sqlite est-elle beaucoup plus lente lorsque j'indexe les colonnes?

14

J'ai une base de données sqlite avec deux tables, chacune avec 50 000 lignes, contenant les noms de (fausses) personnes. J'ai construit une requête simple pour savoir combien de noms (prénom, initiale, prénom) sont communs aux deux tables:

select count(*) from fakenames_uk inner join fakenames_usa on fakenames_uk.givenname=fakenames_usa.givenname and fakenames_uk.surname=fakenames_usa.surname and fakenames_uk.middleinitial=fakenames_usa.middleinitial;

Lorsqu'il n'y a pas d'index sauf sur les clés primaires (sans rapport avec cette requête), il s'exécute rapidement:

[james@marlon Downloads] $ time sqlite3 generic_data_no_indexes.sqlite "select count(*) from fakenames_uk inner join fakenames_usa on fakenames_uk.givenname=fakenames_usa.givenname and fakenames_uk.surname=fakenames_usa.surname and fakenames_uk.middleinitial=fakenames_usa.middleinitial;"
131

real    0m0.115s
user    0m0.111s
sys     0m0.004s

Mais si j'ajoute des index aux trois colonnes de chaque table (six index en tout):

CREATE INDEX `idx_uk_givenname` ON `fakenames_uk` (`givenname` )
//etc.

puis il s'exécute douloureusement lentement:

[james@marlon Downloads] $ time sqlite3 generic_data.sqlite "select count(*) from fakenames_uk inner join fakenames_usa on fakenames_uk.givenname=fakenames_usa.givenname and fakenames_uk.surname=fakenames_usa.surname and fakenames_uk.middleinitial=fakenames_usa.middleinitial;"
131

real    1m43.102s
user    0m52.397s
sys     0m50.696s

Y a-t-il une rime ou une raison à cela?

Voici le résultat de EXPLAIN QUERY PLANla version sans index:

0|0|0|SCAN TABLE fakenames_uk
0|1|1|SEARCH TABLE fakenames_usa USING AUTOMATIC COVERING INDEX (middleinitial=? AND surname=? AND givenname=?)

C'est avec des index:

0|0|0|SCAN TABLE fakenames_uk
0|1|1|SEARCH TABLE fakenames_usa USING INDEX idx_us_middleinitial (middleinitial=?)
performance index optimization sqlite count sécurité-chiastique
la source
1
Vos index ne couvrent pas. Il semble que vous indexiez chaque colonne individuellement. Que se passe-t-il lorsque vous créez un index de couverture contenant les trois colonnes d'un index ( middleinitial, surnameet givenname)?
Randolph West
@Randoph West Je comprends ce que vous vouliez dire, mais vous n'utilisez pas la bonne terminologie: un "indice de couverture" est celui qui inclut également les colonnes sélectionnées. Par exemple, pour la requête SELECT c FROM t WHERE a=1 AND b=2, l'index t(a,b,c)couvre mais t(a,b)ne l'est pas. L'avantage de couvrir les indices est que le résultat de la requête entière peut être extrait directement de l'index, tandis que les indices non couvrant trouvent rapidement les lignes pertinentes, mais il doit toujours se référer aux données du tableau principal pour sélectionner les valeurs.
Arthur Tacca

Réponses:

15

Dans SQLite, les jointures sont exécutées en tant que jointures en boucle imbriquées, c'est-à-dire que la base de données passe par une table et, pour chaque ligne, recherche les lignes correspondantes de l'autre table.

S'il existe un index, la base de données peut rechercher rapidement toutes les correspondances dans l'index, puis accéder à la ligne de table correspondante pour obtenir les valeurs de toutes les autres colonnes nécessaires.

Dans ce cas, il existe trois index possibles. Sans aucune information statistique (qui serait créée en exécutant ANALYZE ), la base de données choisit la plus petite, pour réduire les E / S. Cependant, l' middleinitialindex est inutile car il ne réduit pas considérablement le nombre de lignes de table qui doivent être récupérées; et l'étape supplémentaire à travers l'index augmente réellement les E / S nécessaires parce que les lignes de table ne sont plus lues dans l'ordre, mais au hasard.

S'il n'y a pas d'index, la recherche de lignes correspondantes nécessiterait une analyse complète de la table de la deuxième table pour chaque ligne de la première table. Ce serait si mauvais que la base de données estime qu'il vaut la peine de créer puis de supprimer un index temporaire juste pour cette requête. Cet index temporaire ("AUTOMATIQUE") est créé sur toutes les colonnes utilisées pour la recherche. L'opération COUNT (*) n'a pas besoin de valeurs provenant d'autres colonnes, donc cet index se trouve être un index de couverture , ce qui signifie qu'il n'est pas nécessaire de rechercher réellement la ligne du tableau correspondant à une entrée d'index, ce qui économise encore plus I / O.

Pour accélérer cette requête, créez cet index en permanence, afin qu'il ne soit plus nécessaire d'en construire un temporaire:

CREATE INDEX uk_all_names ON fakenames_uk(surname, givenname, middleinitial);

EXPLAIN QUERY PLAN
SELECT count(*)
FROM fakenames_uk
JOIN fakenames_usa USING (givenname, middleinitial, surname);

0|0|1|SCAN TABLE fakenames_usa
0|1|0|SEARCH TABLE fakenames_uk USING COVERING INDEX uk_all_names (surname=? AND givenname=? AND middleinitial=?)

L'index activé surnamen'est plus nécessaire car l'index à trois colonnes peut être utilisé pour toutes les recherches sur cette colonne.
L'index sur givennamepeut être utile si vous effectuez des recherches sur cette colonne uniquement.
L'index on middleinitialest toujours sans valeur: une requête qui recherche l'une des 26 valeurs possibles est plus rapide si elle analyse uniquement la table entière.

CL.
la source