L'indexation : ce qui se passe vraiment sous une requête

Le cadastre et l'annuaire des rues

La Ville a grossi. Vingt mille habitants, huit cents rues, et un huissier qui doit remettre un pli à monsieur Roche. La seule chose que sache faire la mairie, c'est ouvrir le registre à la première page et lire les fiches une par une jusqu'à tomber sur la bonne.

Le cadastre existe pour éviter ça. Une entrée par parcelle, classée par numéro, avec le renvoi vers le dossier complet rangé aux archives. L'annuaire des rues fait le même travail pour les adresses. Aucun des deux ne contient l'information : ils contiennent le chemin vers l'information, et ce chemin est trié.

Un index de base de données est exactement cet objet. Une structure séparée, plus petite que la table, maintenue triée, qui dit où aller chercher la ligne. Le moteur ne lit plus cent millions de lignes, il descend quatre étages et tombe sur la bonne.

Un index ne stocke presque rien d'utile en soi. Il stocke un ordre, et cet ordre transforme une lecture exhaustive en quelques accès ciblés.

C'est aussi le seul levier de ce palier qui accélère un système sans qu'une ligne de code applicatif change. Et le seul dont le prix se paie ailleurs, dans les écritures, longtemps après la décision.

Vue d'ensemble : balayer ou parcourir

Face à WHERE client_id = 4217, un moteur a deux stratégies. Tout lire et filtrer au passage, c'est le balayage séquentiel. Ou descendre dans l'index, récupérer les positions et n'aller chercher que ces lignes-là, c'est le parcours d'index.

Chiffrons l'écart sur une table de commandes, à la louche.

Table : 100 000 000 lignes x 200 octets = 20 000 000 000 octets = 20 Go
Lecture séquentielle à 2 Go/s                                   = 10 secondes

Parcours d'index, arbre de 4 niveaux :
4 pages d'index de 8 Ko + 1 page de table de 8 Ko = 40 960 octets ≈ 40 Ko

Vingt gigaoctets contre quarante kilooctets, soit un facteur 500 000. Voilà pourquoi un index manquant ne ralentit pas un service : il le fait tomber.

Sauf que le calcul s'inverse dès que la requête ramène beaucoup de lignes. Si client_id = 4217 correspondait à trente millions de lignes, le parcours d'index coûterait, au pire, un accès aléatoire par ligne :

30 000 000 lignes x 8 192 octets de page = 245 760 000 000 octets ≈ 245 Go

Deux cent quarante-cinq gigaoctets d'accès dispersés, contre vingt gigaoctets lus d'un trait. Le balayage complet gagne largement.

Le planificateur tranche avec des statistiques et des constantes de coût. PostgreSQL compare seq_page_cost, à 1.0 par défaut, et random_page_cost, à 4.0 : lire une page au hasard est réputé quatre fois plus cher que lire la suivante. En pratique, passé quelques pour cent de la table, le balayage l'emporte.

Un index n'est jamais rapide dans l'absolu. Il est rapide quand il élimine une large majorité des lignes. Sur une colonne peu discriminante, il ajoute du travail au lieu d'en retirer.

Le reste du billet déplie l'objet : sa structure, la différence entre index groupant et index secondaire, l'index composite et sa règle du préfixe, l'index couvrant, le prix à l'écriture, les index qui ne servent jamais, et la lecture d'un plan d'exécution.

La structure : arbre B+ et table de hachage

Le cadastre est trié par numéro de parcelle. Cela répond aussi bien à « la parcelle 4217 » qu'à « toutes les parcelles de 4200 à 4300 ». Le vestiaire du théâtre, lui, attribue un casier par un calcul sur le nom : on retrouve le sien instantanément, mais personne ne peut demander tous les casiers entre Dupont et Durand.

Ces deux comportements sont ceux des deux grandes familles d'index.

L'arbre B+ est la structure par défaut partout. Une racine, quelques niveaux internes qui ne portent que des bornes de clés, et des feuilles qui portent les clés triées et les pointeurs vers les lignes. Les feuilles sont chaînées entre elles, ce qui rend le parcours d'un intervalle aussi naturel qu'une recherche par égalité.

Sa profondeur reste faible parce que l'éventail est large. Avec une page de 8 Ko, la taille de bloc par défaut de PostgreSQL, et une entrée interne d'une vingtaine d'octets :

Éventail : 8 192 / 20 ≈ 400 pointeurs par page

Niveau 1, la racine :            400 clés
Niveau 2            :        160 000 clés
Niveau 3            :     64 000 000 clés
Niveau 4            : 25 600 000 000 clés

Cent millions de lignes tiennent donc dans un arbre de quatre niveaux. Mieux : la racine pèse 8 Ko et le deuxième niveau 400 pages, soit 3,2 Mo. Ces deux étages restent en mémoire en permanence, et une recherche coûte en pratique une ou deux lectures réelles.

L'index de hachage, lui, calcule une empreinte de la clé et va droit au seau correspondant. Très bon sur l'égalité, incapable de tout le reste. Dans PostgreSQL, un index hash ne sert que l'opérateur d'égalité, ne peut pas être déclaré unique et ne peut pas porter sur plusieurs colonnes. Dans InnoDB, on ne crée pas d'index de hachage soi-même : le moteur en construit un en mémoire, automatiquement, sur les clés les plus sollicitées.

Choisir autre chose qu'un arbre B+ suppose de savoir précisément quelle opération on veut servir. Dans le doute, c'est un B+, et la question suivante porte sur les colonnes, pas sur la structure.

Index groupant et index secondaire

À la mairie, deux organisations coexistent. Les dossiers de parcelle sont physiquement rangés dans l'ordre des numéros de parcelle : le classement et le contenu ne font qu'un. Le fichier des propriétaires, lui, est une liste alphabétique qui renvoie vers un numéro de parcelle, donc vers une seconde recherche.

Cette différence, transposée dans un moteur, décide de son comportement en écriture.

Dans InnoDB, toute table possède un index groupant, et les lignes vivent dans ses feuilles. La clé primaire en tient le rôle ; à défaut, le premier index unique et non nul ; à défaut encore, le moteur fabrique un identifiant caché de 6 octets. Une feuille d'index secondaire ne contient donc pas une position physique mais la valeur de la clé primaire, et toute lecture par index secondaire enchaîne deux descentes.

Dans PostgreSQL, la table est un tas non ordonné, rempli dans l'ordre des écritures. Les entrées d'index pointent vers un ctid, la position physique d'une version de ligne : numéro de page et rang dans la page. Il n'existe pas d'index groupant maintenu ; la commande CLUSTER réordonne la table une fois, et l'ordre se dégrade dès les écritures suivantes.

Le point sur la clé primaire longue mérite un chiffre. Une clé bigint occupe 8 octets, un identifiant universel stocké sous forme de chaîne de 36 caractères en occupe 36. Sur cent millions de lignes et cinq index secondaires :

Écart par entrée      : 36 - 8 = 28 octets
Par index             : 100 000 000 x 28 = 2 800 000 000 octets = 2,8 Go
Sur 5 index           : 5 x 2,8 = 14 Go

Quatorze gigaoctets de plus, en mémoire comme sur disque, pour un choix de type fait le premier jour dans un fichier de migration.

Ce que contient la feuille d'un index secondaire décide du reste. De là dépend qu'une mise à jour touche un seul index, ou la totalité de ceux que la table porte.

L'index composite et le préfixe le plus à gauche

L'annuaire des rues est trié par rue, puis par numéro. Il répond à « tout ce qui est rue des Lilas » et à « le 12 rue des Lilas ». Il ne répond pas à « tous les numéros 12 de la ville » sans relire l'annuaire entier.

Un index composite obéit à la même règle. Sur (client_id, statut, date_creation) :

-- 1. sert : la colonne de tête est contrainte
SELECT * FROM commandes WHERE client_id = 4217;

-- 2. sert : préfixe (client_id, statut)
SELECT * FROM commandes WHERE client_id = 4217 AND statut = 'PAYEE';

-- 3. ne sert pas efficacement : la colonne de tête manque
SELECT * FROM commandes WHERE statut = 'PAYEE';

Une nuance honnête sur la troisième. MySQL applique la règle du préfixe le plus à gauche strictement, avec une exception introduite dans la série 8.0, le balayage à saut, qui contourne partiellement le problème quand la colonne de tête a peu de valeurs distinctes. PostgreSQL, lui, accepte d'utiliser un index multicolonne avec n'importe quel sous-ensemble de colonnes, mais en balayant l'index entier ; la documentation précise que l'index est efficace quand les colonnes de tête sont contraintes. Utilisable ne veut pas dire rentable.

L'ordre des colonnes suit une règle simple : les colonnes d'égalité d'abord, la colonne d'intervalle ou de tri ensuite. Dès qu'une inégalité apparaît, les colonnes suivantes ne servent plus à cibler, seulement à filtrer ce qu'on a déjà lu.

Sur WHERE client_id = 4217 AND date_creation > '2026-01-01', l'index (client_id, date_creation) descend directement sur le bon segment. L'index (date_creation, client_id) lit toutes les commandes de tous les clients depuis janvier, puis jette celles qui ne concernent pas le client 4217.

Le tri profite du même arbre. Un index (client_id, date_creation) sert ORDER BY client_id, date_creation et son exact inverse, par parcours arrière. Il ne sert pas un tri mixte, une colonne croissante et l'autre décroissante, sauf à déclarer le sens souhaité dans la définition de l'index.

Un index composite se conçoit à partir d'une requête écrite, pas à partir d'une liste de colonnes qui semblent importantes. La première colonne est la décision, le reste est du réglage.

L'index couvrant

Le meilleur guichet est celui qui répond depuis le comptoir sans descendre aux archives. Si l'agent a sous les yeux tout ce que demande l'usager, le dossier reste dans son carton.

Un index est dit couvrant quand il contient toutes les colonnes dont la requête a besoin. Le moteur lit l'index et ne touche jamais la table. PostgreSQL appelle ça un Index Only Scan, MySQL l'affiche par la mention Using index dans son plan.

CREATE INDEX idx_cmd_client_date
    ON commandes (client_id, date_creation)
    INCLUDE (montant);

La clause INCLUDE, disponible sur les index btree depuis PostgreSQL 11, range montant dans les feuilles sans en faire une colonne de recherche. Elle ne participe ni au tri, ni à une éventuelle contrainte d'unicité : elle est là uniquement pour éviter l'aller-retour vers la table.

Une réserve propre à PostgreSQL : le parcours par index seul suppose que le moteur sache que toutes les versions de ligne de la page sont visibles, information portée par la carte de visibilité. Sur une table fraîchement écrite et pas encore traitée par VACUUM, le plan annonce un Index Only Scan mais repasse quand même par le tas, ligne par ligne. Le gain disparaît sans que la requête change.

Et le prix reste : chaque colonne ajoutée élargit chaque feuille, donc chaque écriture. Un index couvrant est une lecture achetée avec de l'écriture.

L'index couvrant est le seul cas où l'index remplace la table au lieu de la compléter. C'est aussi le plus tentant à élargir jusqu'à recopier la moitié des colonnes.

Le prix de chaque index

À la mairie, une vente ne coûte pas une écriture mais trois : le cadastre, le fichier des propriétaires, le rôle d'imposition. Personne ne s'en aperçoit tant qu'il y a deux ventes par semaine.

Dans une base, la règle est identique. Chaque insertion et chaque suppression touchent la table plus la totalité des index. Chaque mise à jour touche au minimum les index portant sur les colonnes modifiées, et parfois tous, selon le moteur.

L'espace se calcule aussi, et il surprend. Sur la même table de cent millions de lignes :

Table                          : 100 000 000 x 200 octets =  20 Go
Index sur un bigint            : 100 000 000 x  20 octets =   2 Go
Index sur un courriel (40 car.): 100 000 000 x  52 octets = 5,2 Go

3 index bigint + 2 index courriel = 3 x 2 + 2 x 5,2 = 16,4 Go
soit 82 % de la taille de la table

Ces seize gigaoctets se sauvegardent, se restaurent, se répliquent et se disputent la mémoire cache avec les données réelles.

Un dernier facteur pèse plus lourd qu'on ne le croit : la forme de la clé. Une clé monotone, séquence entière ou identifiant horodaté, écrit toujours à l'extrémité droite de l'arbre, sur les mêmes pages, déjà chaudes. Une clé aléatoire écrit à chaque insertion sur une feuille différente, et l'ensemble des pages salies devient énorme.

Le journal d'écriture amplifie le phénomène. Dans PostgreSQL, avec full_page_writes actif par défaut, la première modification d'une page après un point de reprise recopie la page entière dans le journal. Beaucoup de pages différentes salies, c'est beaucoup de journal produit, donc beaucoup de trafic de réplication.

Un index se justifie par une requête qu'on peut nommer. Sans cette requête, ce n'est pas une optimisation, c'est un impôt prélevé sur chaque écriture jusqu'à la fin du système.

Les index qui ne servent jamais

Le pire fichier n'est pas celui qui manque. C'est celui qu'un clerc met à jour consciencieusement depuis quatre ans, et que plus personne n'ouvre.

Cinq situations produisent des index inertes, tous coûteux et aucun utile.

Une fonction appliquée à la colonne. WHERE lower(email) = 'x' ou WHERE YEAR(date_creation) = 2026 ne peuvent pas exploiter un index sur email ou date_creation : l'index range les valeurs brutes, pas le résultat de la fonction. La parade est un index d'expression sous PostgreSQL, une clé fonctionnelle ou une colonne générée indexée sous MySQL 8.0.

Une conversion de type implicite. Comparer une colonne texte à une valeur numérique force le moteur à convertir la colonne, donc à la lire entièrement. L'index existe, le plan l'ignore, et rien dans la requête ne le laisse deviner.

Un joker en tête de motif. LIKE 'dupont%' descend dans l'arbre, LIKE '%dupont' ne le peut pas : sans début connu, aucune branche n'est éliminable. Il faut alors un index trigramme ou un index plein texte.

Une sélectivité trop faible. Sur une colonne booléenne où 97 % des lignes valent false, l'index ne sert que la valeur rare. Un index partiel, restreint à cette valeur, coûte cent fois moins cher et rend le même service.

Une redondance avec le préfixe d'un autre. Un index sur (client_id) n'apporte rien de plus qu'un index sur (client_id, date_creation). Il double simplement le travail de chaque écriture.

Le dernier cas se mesure au lieu de se deviner :

SELECT relname, indexrelname, idx_scan,
       pg_size_pretty(pg_relation_size(indexrelid)) AS taille
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;

Avant d'ajouter un index, il faut regarder ceux que la table porte déjà. La moitié des bases lentes que j'ai vues portaient trop d'index, pas trop peu.

Lire un plan d'exécution

On ne laisse pas partir un employé sans lui demander par où il compte passer. Le plan d'exécution est cette question, posée au moteur.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, montant, date_creation
FROM commandes
WHERE client_id = 4217
ORDER BY date_creation DESC
LIMIT 20;

Sans index adapté, le plan ressemble à ceci, réduit aux lignes qui comptent :

Limit  (cost=2874318.42..2874320.75 rows=20 width=24)
       (actual time=9412.331..9418.204 rows=20 loops=1)
  Buffers: shared hit=812 read=2440594
  ->  Sort  (cost=2874318.42..2874320.75 rows=934 width=24)
        Sort Key: date_creation DESC
        Sort Method: top-N heapsort  Memory: 27kB
        ->  Seq Scan on commandes  (cost=0.00..2874293.00 rows=934 width=24)
              Filter: (client_id = 4217)
              Rows Removed by Filter: 99999066
Execution Time: 9418.331 ms

Avec un index sur (client_id, date_creation) :

Limit  (cost=0.57..46.12 rows=20 width=24)
       (actual time=0.043..0.092 rows=20 loops=1)
  Buffers: shared hit=24
  ->  Index Scan Backward using idx_cmd_client_date on commandes
        (cost=0.57..2127.44 rows=934 width=24)
        (actual time=0.041..0.086 rows=20 loops=1)
        Index Cond: (client_id = 4217)
Execution Time: 0.118 ms

Quatre choses se lisent dans cet ordre.

Le type de nœud. Seq Scan lit tout, Index Scan descend puis va chercher les lignes, Index Only Scan ne touche pas la table, Bitmap Heap Scan combine plusieurs index avant de trier les pages à lire.

La distinction entre Index Cond et Filter. La première condition s'applique dans l'index et élimine avant de lire ; la seconde s'applique après avoir lu la ligne. Une condition qu'on croyait indexée et qui apparaît en Filter est le symptôme le plus courant d'un index mal ordonné.

Rows Removed by Filter. Quatre-vingt-dix-neuf millions de lignes lues puis jetées pour en garder vingt : c'est là que se voit le travail inutile, plus clairement que dans n'importe quel coût estimé.

L'écart entre rows estimé et rows réel. Un facteur mille entre les deux signifie que les statistiques sont périmées, et que toutes les décisions du planificateur reposent sur une carte fausse. Un ANALYZE règle souvent ce qu'on croyait être un problème d'index.

La ligne Buffers complète le tableau : shared hit compte les pages trouvées en cache, read celles qu'il a fallu aller chercher plus bas. Du côté de MySQL, le EXPLAIN classique donne l'index retenu, le nombre estimé de lignes et une colonne Extra où Using index et Using filesort en disent long ; la série 8.0 propose en plus un EXPLAIN ANALYZE qui exécute réellement la requête.

Le premier chiffre à regarder est l'écart entre les lignes prévues et les lignes réellement produites, avant même le coût estimé. Tout le reste du plan en découle.

Scénario B : Uber, l'index vu de l'intérieur

En juillet 2016, l'équipe d'ingénierie d'Uber publie « Why Uber Engineering Switched from Postgres to MySQL ». Le billet SQL ou NoSQL exploite déjà ce texte, sous l'angle du choix de magasin de données. Ici, on le relit uniquement pour ce qu'il dit des index, et il en dit beaucoup.

Le cœur de l'argument tient à un choix de conception. Dans PostgreSQL, une entrée d'index désigne l'emplacement physique d'une version de ligne. Or le contrôle de concurrence multiversion ne modifie pas une ligne : il en écrit une nouvelle version, potentiellement sur une autre page. Il faut donc que chaque index de la table reçoive une nouvelle entrée pointant vers cette version, y compris les index portant sur des colonnes que la requête n'a pas touchées.

Dans InnoDB, une feuille d'index secondaire porte la valeur de la clé primaire. Une ligne peut se déplacer physiquement sans qu'aucun index secondaire ne bouge, et seuls les index portant sur les colonnes modifiées sont mis à jour.

La conséquence que décrit le billet est une amplification d'écriture proportionnelle au nombre d'index de la table, et non au nombre de colonnes modifiées. Sur des tables fortement indexées, changer un seul champ déclenche un volume de travail sans rapport avec ce que la requête laisse imaginer.

Le billet enchaîne sur la réplication. La réplication en flux de PostgreSQL transporte le journal d'écriture physique : l'amplification est donc payée une deuxième fois sur le réseau, ce qui pèse entre centres de données. La réplication de MySQL travaille au niveau logique, sur l'instruction ou sur la ligne modifiée.

Deux précautions de lecture, parce que ce billet a été discuté publiquement à sa sortie. La communauté PostgreSQL a rappelé le mécanisme des mises à jour dites HOT : si aucune colonne indexée n'est modifiée et que la page dispose de place libre, la nouvelle version reste sur la même page, chaînée à l'ancienne, et aucun index n'est touché. D'où l'intérêt du réglage du taux de remplissage des pages sur les tables très mises à jour. Et il s'agit du profil d'accès d'Uber en 2016 : PostgreSQL a évolué depuis, avec les index couvrants de la version 11 et la déduplication des entrées btree de la version 13.

L'enseignement transposable est indépendant des deux produits. Un index n'est pas une structure neutre posée à côté de la table : la façon dont sa feuille désigne la ligne fixe le coût de chaque écriture, et ce coût voyage jusqu'aux répliques.

Points clés

• Un index remplace une lecture exhaustive par quelques accès ciblés, mais seulement s'il élimine une large majorité des lignes ; au-delà de quelques pour cent de la table, le balayage complet reprend l'avantage.
• L'arbre B+ sert l'égalité, l'intervalle, le préfixe et le tri avec une profondeur de quatre niveaux sur cent millions de lignes ; les autres structures répondent à des besoins précis qu'il faut savoir nommer.
• La feuille d'un index secondaire pointe vers la clé primaire dans InnoDB, vers une position physique dans PostgreSQL. Ce détail décide du coût des mises à jour, du poids d'une clé primaire longue et du volume répliqué.
• Un index composite s'utilise par son préfixe le plus à gauche : colonnes d'égalité d'abord, colonne d'intervalle ou de tri ensuite.
• Chaque index se paie sur toutes les écritures et sur l'espace, souvent 50 à 100 % de la taille de la table pour un jeu d'index courant. Un index sans requête nommée est un coût permanent sans contrepartie.

Dans la série

Palier 3 : Tenir les registres. Domaine : Données.

• Précédent : Sharding et hachage cohérent : découper sans tout déménager
• Suivant : Transactions distribuées : 2PC, 3PC, SAGA et verrous
• Vue d'ensemble : System design : par où commencer

Pour aller plus loin

• Sharding et hachage cohérent : découper sans tout déménager, parce que la clé de partition et la clé d'index se choisissent sur les mêmes requêtes.
• Concevoir un raccourcisseur d'URL, où l'index sur la clé courte porte l'intégralité du chemin de lecture.
• SQL ou NoSQL : choisir son magasin de données, qui lit le billet d'Uber sous l'angle du choix de moteur.
• Why Uber Engineering Switched from Postgres to MySQL, le texte d'origine.
• Documentation PostgreSQL sur les index et sur l'utilisation d'EXPLAIN.
• Documentation MySQL sur les types d'index InnoDB.
• Use The Index, Luke, de Markus Winand, pour le traitement long de l'indexation côté développeur.