» FRANÇAIS | ENGLISH

• Une table ordinaire
• Une requête ordinaire
  • Vérifions ce que je vous raconte
  • Performances de la requête
• Mais que se passe-t-il ?
• Le mystère résolu
• Conclusion

J’ai découvert tout récemment une optimisation un peu étonnante que l’on peut faire avec SQLite. Mais tout d’abord, qu’est-ce qu’un index couvrant (ou covering index) ? C’est un index qui contient toutes les colonnes nécessaires pour répondre à la requête sans que le moteur SQL ait besoin d’accéder à la table. Cela permet évidemment d’économiser du temps. Mais comme pour tout index, on va en perdre à l’insertion, pour autant qu’on considère que c’est significatif pour notre application, ce qui n’est pas un problème dans mon cas.

Une table ordinaire

Il n’y a rien de particulier à avoir des index couvrants. Mais avant d’aller plus loin, je vais vous présenter une table très simple comme vous pourriez en voir dans de nombreux logiciels.

CREATE TABLE data (
  rowid     INTEGER PRIMARY KEY AUTOINCREMENT,
  timestamp TEXT,
  payload   JSON,
  commitId  TEXT DEFAULT NULL
);

CREATE INDEX commitId ON data (commitId);

Cette table a un index qui est la clef primaire rowid et auto-incrémentée. La colonne rowid est spéciale dans SQLite car elle existe toujours même si on ne la déclare pas explicitement dans le schéma et qu’on ne demande pas explicitement une table sans rowid (WITHOUT ROWID).

Le but avec cette table est que le rowid ne soit jamais recyclé en cas de suppression de lignes. En ne déclarant pas explicitement une colonne INTEGER PRIMARY KEY dans le schéma, il est tout à fait possible qu’un rowid soit réutilisé. Pour notre usage ici, on va garantir que le rowid ne fait que s’incrémenter. Le rowid étant un identifiant 64 bits utilisé au niveau du stockage, ce n’est pas un index comme les autres. Les accès aux données en se basant sur le rowid sont bien plus rapides et optimisés qu’avec un index ordinaire.

Une requête ordinaire

Voici une requête nécessaire dans cette application. Celle-ci va compter combien il y a de lignes avec un rowid plus grand que le plus grand rowid qui existe pour un commitId donné. Il faut comprendre qu’un même commitId peut apparaître plusieurs fois dans la table ; d’ailleurs, ce n’est pas un index unique.

SELECT count(*)
FROM data
WHERE rowid > (
  SELECT max(rowid)
  FROM data
  WHERE commitId = 'abcd'
);

Exemple avec quelques données :

Pour le commitId abcd, la requête va retourner la valeur 2 (les rowid 13 et 14 sont plus grands que le plus grand rowid utilisé par le commitId abcd qui vaut 11).

Je pense que comme moi, vous trouvez tout ceci assez simple et ordinaire. La seule particularité de cette requête c’est l’utilisation d’une sous-requête pour récupérer le plus grand rowid associé à un commitId. Vous êtes certainement d’accord avec moi que ça devrait être assez efficace car la sous-requête peut exploiter l’index commitId pour réduire la quantité de données dans laquelle retrouver le max. D’ailleurs, dans l’application, il n’y a que très rarement beaucoup de lignes pour un même commitId (moins d’une dizaine).

Vérifions ce que je vous raconte

En utilisant EXPLAIN QUERY PLAN avec notre SELECT ... on va pouvoir vérifier que je ne vous raconte pas de bêtises.

Ceci paraît très bien et même merveilleux. La sous-requête utilise bien l’index commitId et en plus en mode couvrant car on n’accède à rien d’autre qu’à l’index pour résoudre la condition commitId = 'abcd'. Concernant la condition avec rowid > (...) on accède à l’index de la clef primaire. On peut imaginer que c’est très performant car on utilise directement le rowid de la table de SQLite.

Performances de la requête

Jetons alors un œil aux performances avec une table qui contient environ 200'000 lignes et un commitId qui se situe presque au milieu de celle-ci. Il n’y a que 3 lignes (avec la sous-requête) pour ce commitId.

$ sqlite3 data.db
SQLite version 3.46.1 2024-08-13 09:16:08
Enter ".help" for usage hints.
sqlite> .timer on
sqlite> SELECT count(*)
FROM data
WHERE rowid > (
  SELECT max(rowid)
  FROM data
  WHERE commitId = '81b5f0ae-7f4a-4db2-ae3f-dea5bd35e0ad'
);
93356
Run Time: real 0.031 user 0.007897 sys 0.023278
sqlite> SELECT count(*) ...
93356
Run Time: real 0.038 user 0.007570 sys 0.030460
sqlite> SELECT count(*) ...
93356
Run Time: real 0.038 user 0.003727 sys 0.033857
sqlite> SELECT count(*) ...
93356
Run Time: real 0.033 user 0.011919 sys 0.020516

L’instruction .timer on permet d’activer un minuteur pour chaque requête exécutée. Voici ce qui en ressort :

Je ne sais pas ce que vous en pensez, mais moi je ne suis pas satisfait du résultat. Je peux exécuter cette requête des dizaines de fois, elle ne descend jamais en dessous des 30 ms. Ne trouvez-vous pas que c’est un peu lent ? Il n’y a pas tant de lignes que ça, le schéma est simple, les requêtes sont simples, le planificateur de requêtes est satisfait.

Mais que se passe-t-il ?

C’est une excellente question et c’est tout le sujet de cet article. Il y a un moyen d’améliorer drastiquement les performances de cette requête. Voici une mesure avec le changement que je vais vous présenter plus bas (ne sautez pas directement à la fin de l’article, essayez d’imaginer comment améliorer les performances de ce SELECT en allant revoir le schéma et ce que le planificateur de requêtes a dit).

$ sqlite3 data.db
SQLite version 3.46.1 2024-08-13 09:16:08
Enter ".help" for usage hints.
sqlite> .timer on
sqlite> SELECT count(*)
FROM data
WHERE rowid > (
  SELECT max(rowid)
  FROM data
  WHERE commitId = '81b5f0ae-7f4a-4db2-ae3f-dea5bd35e0ad'
);
93356
Run Time: real 0.002 user 0.000577 sys 0.001397
sqlite> SELECT count(*) ...
93356
Run Time: real 0.002 user 0.000456 sys 0.001106
sqlite> SELECT count(*) ...
93356
Run Time: real 0.005 user 0.004119 sys 0.000222
sqlite> SELECT count(*) ...
93356
Run Time: real 0.004 user 0.004134 sys 0.000268

On passe de plus de 30 ms à quelques millisecondes. Pour comprendre ce qui se passe ici, il faut réétudier ce que le planificateur de requêtes nous a dit tout à l’heure et surtout la première ligne SEARCH data USING INTEGER PRIMARY KEY (rowid>?). Ici il n’est pas dit que SQLite va utiliser un index couvrant, mais uniquement que SQLite va utiliser l’index sur la clef primaire. Mais finalement, qu’est-ce que ça signifie dans ce cas ?

Cette clef primaire n’est pas un index ordinaire car c’est l’identifiant qui permet de retrouver un enregistrement dans la table. Ce qui veut dire qu’il faut accéder à la table pour accéder à cette clef. C’est très performant si vous voulez extraire un enregistrement de la table comme par exemple avec un simple SELECT * FROM data WHERE rowid = 101256;. Un SELECT de ce type doit forcément aller chercher les données et il vaut mieux connaître directement l’identifiant et ne pas perdre de temps avec un index intermédiaire.

Mais que faire pour le SELECT count(*) ... ? Il nous faut un index couvrant. Ainsi SQLite ne va pas accéder aux pages du stockage pour retrouver les rowid. Ne pas accéder au stockage permet d’éviter le chargement des autres colonnes de la table. Si vous regardez bien le schéma, il y a une colonne payload. Cette colonne peut contenir de gros documents JSON. C’est une colonne assez lourde et ici, elle est suffisante pour rendre la requête moins efficace bien qu’on ne s’intéresse pas du tout au payload.

Le mystère résolu

CREATE INDEX rowId ON data (rowId);

OMG ?! 😱

Nous sommes en train de créer un index par-dessus une clef primaire. Sommes-nous devenus fous ? Même le Grand Richard Hipp (auteur de SQLite) nous dit :

(2) By Richard Hipp (drh) on 2020-09-26 18:18:07 in reply to 1

An INTEGER PRIMARY KEY becomes the actual key used in the B-tree that stores your table. So no index is required for efficient operation.

You should always omit indexes on PRIMARY KEY columns, regardless of the type. The best case for an index on a PRIMARY KEY is that it will be a no-op. The worst case is that it will make things run slower. So avoid the worst-case and just leave it off.

– https://sqlite.org/forum/info/8876e4e648bf8f93

Voyons voir ce que nous dit le planificateur de requêtes…

Désormais c’est bien l’index couvrant qui est utilisé. Nous sommes face alors à un cas de figure où ajouter un index par-dessus une clef primaire va améliorer drastiquement les performances de ce SELECT.

À noter que si je supprime la colonne payload et que je reteste la requête sans l’index couvrant sur rowid, j’obtiens environ 9 ms au lieu de plus de 30 ms.

Conclusion

Ce qu’il faut retenir c’est qu’avec un INTEGER PRIMARY KEY, SQLite doit charger les pages complètes (avec payload). Mais avec l’index couvrant (covering index), SQLite ne lit plus que l’index léger.

Ces différentes expérimentations montrent une particularité peu connue du moteur SQLite. On peut probablement considérer ce comportement comme un cas limite avec des subtilités entre l’optimiseur de requêtes, les index couvrants et les opérations d’agrégation avec de gros volumes. Je ne vais pas vous conseiller de le faire, mais je vous encourage à inspecter et mesurer vos requêtes avec et sans cet index qui semble pourtant mal venu.