En séparant le "quoi" et le "comment", le langage SQL masque le traitement qui s'effectue au niveau du système d'une base de données. En plus, les ORM peuvent ajouter une couche d'obscurcissement supplémentaire.
Cette abstraction atteint ses limites quand des performances importantes sont attendues… mais qu'elles ne sont pas au rendez-vous !
L'indexation est la clé du succès.
Ce billet est inspiré par Use The Index Luke: Un tutoriel sur l'optimisation SQL pour les développeurs qui couvre la base Oracle et l'index B-tree.
De mon côté, je mets le focus sur PostgreSQL qui est ma base de prédilection.
Anatomie d'un index B-tree
Un index est une structure séparée dans la base de données qui stocke des informations rangées dans un ordre bien défini.
Il nécessite son propre espace sur le disque et détient une copie des données de la table : il est redondant.
Un index B-tree combine deux structures qui conditionnent les performances :
- un arbre de recherche équilibré (balanced tree search ou B-tree)
- une liste doublement chaînée (doubly linked list)
Avec un B-tree, la racine et les nœuds branches permettent une recherche en temps toujours logarithmique jusqu'aux nœuds feuilles (ceux qui n'ont pas d'enfants) qui contiennent les données d'indexation.
Les nœuds feuilles (ou leaf nodes) sont connectés entre eux par une liste doublement chaînée. Chacun d'eux pointe explicitement vers le nœud qui la suit et vers celui qui la précède. Du coup ces nœuds individuels peuvent être stockés à des endroits distincts dans la mémoire physique. Puisqu'un index est constamment modifié, cette structure permet d'économiser beaucoup d'I/O pendant un INSERT par rapport à une structure qui stockerait les données de façon séquentielle.
Chaque nœud feuille est stocké dans un block (ou page) de taille fixe qui est la plus petite unité de stockage de la base de données (quelques kilo-octets).
Un nœud feuille peut stocker plusieurs entrées de l'index. S'il faut indexer des données de taille variable, chaque nœud de l'index aura potentiellement un nombre différent d'entrées.
Une entrée de l'index stocke la valeur à indexer et un ROWID qui fait référence à la ligne de la table dont les données sont stockées dans une structure de type heap non triée.
L'ordre de l'index est maintenu à deux niveaux différents : les enregistrements de l'index à l'intérieur de chaque nœud feuille, et les nœuds feuilles entre eux.
Une recherche dans un index suit trois étapes :
- le parcours de l'arbre
- la suite de la chaîne de nœuds feuilles (quand il n'y a pas d'unicité)
- la récupération des données de la table
Les deux ingrédients qui peuvent rendre une recherche par index lente sont les deux dernières étapes : le parcours d'un grand nombre de nœuds feuilles et les accès à la table.
Le plan d'exécution permet de décrire la façon dont une recherche est exécutée avec EXPLAIN.
La clause WHERE
Une clause WHERE mal écrite est la première cause d'une requête lente. Les clauses WHERE qui combinent plusieurs conditions sont particulièrement vulnérables.
Pour définir un index optimal il faut connaître les combinaisons de colonnes qui apparaissent dans les clauses WHERE : le développeur est le mieux placé.
Moins une table a d'index, meilleures sont les performances des commandes INSERT, DELETE et UPDATE.
En effet, plus il y a d'index, plus l'exécution est lente : il faut conserver la propriété balancée de l'arbre. Pour un INSERT ou un UPDATE il faut vérifier qu'il reste de la place dans le nœud feuille de destination ou en créer un nouveau. Dans le pire des cas, la profondeur de l'arbre grossit.
Pour accélérer une opération INSERT sur un grand volume de données, il peut être intéressant de supprimer temporairement les index.
Clés primaires
Pour les clés primaires, un index est créé automatiquement.
Une requête qui récupère des informations en utilisant une clé primaire se traduit par une traversée d'index suivie d'un accès à la table pour chercher les informations.
Les ingrédients d'une requête lente ne sont pas présents dans un tel cas.
Dans PostgreSQL, le plan d'exécution d'une recherche par clé primaire indique Index Scan.
Un Index Scan signifie :
- traversée d'un index B-tree
- recherche dans les nœuds feuilles pour trouver un résultat
- accès à la table pour récupérer les informations
PostgreSQL indique Index Only Scan quand il n'y a pas d'accès à la table car l'index dispose de toutes les informations.
Seq Scan veut dire que l'opération doit parcourir toute la table : le temps d'exécution augmente alors en fonction de la taille de la table.
PostgreSQL dispose aussi de Bitmap Heap Scan et de Recheck condition.
Planificateur/optimiseur
Comment une base de données choisit-elle un index quand il y en a plusieurs ?
C'est le planificateur/optimiseur qui choisit la meilleure solution.
Il transforme une déclaration SQL en un plan d'exécution.
Un optimiseur basé sur le coût (cost-based optimizer ou CBO) génère plusieurs plans d'exécution possibles et calcule un coût pour chacun.
Le calcul du coût est basé sur les opérations utilisées et des statistiques (volumétrie d'une table, nombre de nœuds feuilles et profondeur de l'arbre d'un index, etc.).
À la fin, la valeur du coût permet de choisir le meilleur plan.
Dans le cas où il n'y a pas de statistiques disponibles (si elles ont été supprimées par exemple), l'optimiseur utilise des valeurs par défaut, ce qui peut conduire à de grosses sous-estimations du nombre de résultats possible.
Function-based index
Un index dont la définition contient des fonctions est appelé un index fonctionnel (Function-based index ou FBI).
Un index fonctionnel applique la fonction, puis stocke le résultat.
On utilise ce genre d'index pour des recherches insensibles à la casse par exemple.
Un exemple de la documentation de PostgreSQL suggère d'utiliser un index fonctionnel avec lower pour une recherche insensible à la casse. Mais si vous utilisez Django et iexact il vaut mieux utiliser upper et créer un index fonctionnel à la main :
CREATE INDEX upper_username_idx ON users_user (upper(username));
Et vous pourrez vérifier que la requête sollicite bien cet index :
qs = User.objects.filter(username__iexact="KeMaR")
print(qs.query)
SELECT * FROM "users_user" WHERE UPPER(username) = UPPER('KeMaR');
qs.explain()
Il faut être vigilant avec les index fonctionnels car ils permettent de créer très facilement des index redondants.
Attention à la sur-indexation car chaque index doit être mis à jour lors de chaque INSERT, UPDATE, et DELETE.
Filtres LIKE et index
La position des caractères jokers affecte l'utilisation des index.
Un filtre LIKE peut solliciter un index seulement si des caractères existent avant le premier caractère joker.
Une expression LIKE qui commence par un caractère joker (par exemple, '%TERM') ne peut pas solliciter un index. La base de données doit parcourir la table entière. C'est ce qui se passe toujours dans l'admin de Django par exemple.
Si possible, il faut éviter les expressions LIKE ayant des caractères joker en début et leur préférer du Full Text Search.
Joint