Comment fonctionnent réellement les index de base de données

« Ajoutez simplement un index » est le conseil de base de données le plus courant, et aussi le plus souvent mal appliqué : lancé sur des requêtes lentes sans comprendre ce que fait réellement l'index, ce qui explique pourquoi il ne change souvent rien du tout. Un index est une seconde copie, triée séparément, d'une tranche de vos données, tenue synchronisée avec la table, qui échange du coût d'écriture et de l'espace de stockage contre de la vitesse de lecture pour des schémas d'accès précis.

Sans index : le balayage complet

Une table sans index sur une colonne est, pour une requête qui filtre sur cette colonne, un tas de lignes non ordonné. Pour trouver les lignes où email = 'user@example.com', la base n'a d'autre choix que de vérifier chaque ligne.

SELECT * FROM users WHERE email = 'user@example.com';
-- Seq Scan on users (cost=0.00..18334.00 rows=1 width=120)
--   Filter: (email = 'user@example.com'::text)

Sur une table de quelques centaines de lignes, c'est instantané. Sur une table de dix millions de lignes, cela fait dix millions de comparaisons à chaque recherche, et cela empire linéairement avec la croissance de la table.

Ce qu'est réellement un index

La plupart des index (par défaut dans Postgres, dans InnoDB de MySQL, dans SQL Server) sont des arbres B : une structure d'arbre équilibré où chaque nœud contient des valeurs de clé triées et des pointeurs, soit vers des nœuds enfants, soit, au niveau des feuilles, vers la ligne réelle.

CREATE INDEX idx_users_email ON users (email);

Cela construit un arbre trié, indexé sur email. Trouver 'user@example.com' revient désormais à descendre dans l'arbre (comparer aux valeurs d'un nœud, suivre le pointeur vers la branche susceptible de contenir la clé, recommencer) au lieu de balayer toute la table. Un arbre B sur un million de lignes nécessite typiquement de l'ordre de 20 comparaisons pour trouver une correspondance, et non un million.

EXPLAIN SELECT * FROM users WHERE email = 'user@example.com';
-- Index Scan using idx_users_email on users (cost=0.42..8.44 rows=1 width=120)
--   Index Cond: (email = 'user@example.com'::text)

L'estimation de cost qui passe de 18334 à 8.44 dans la sortie d'EXPLAIN résume en une ligne tout l'intérêt de l'indexation.

L'index n'aide que les colonnes qu'il couvre

Un index sur email ne fait rien pour une requête qui filtre sur created_at. Il cesse aussi, point crucial, d'aider dès que la colonne la plus à gauche d'un index multicolonne ne fait pas partie de votre filtre.

CREATE INDEX idx_orders_user_status ON orders (user_id, status);

-- uses the index: user_id is the leftmost column
SELECT * FROM orders WHERE user_id = 42;
SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';

-- does NOT use this index: status alone isn't the leftmost column
SELECT * FROM orders WHERE status = 'shipped';

Pensez à un index multicolonne comme à un annuaire trié par nom de famille, puis par prénom. Vous pouvez aller directement à « Smith », puis à « Smith, John », mais vous ne pouvez pas l'utiliser pour trouver tous les « John » sans parcourir chaque nom de famille. L'ordre des colonnes dans un index composite n'est pas cosmétique : il détermine quelles requêtes l'index peut réellement servir.

Les index ne sont pas gratuits

Chaque index doit être mis à jour à chaque INSERT, UPDATE ou DELETE qui touche une colonne indexée : c'est plus de travail par écriture, et plus de stockage. Une table avec huit index paie ce coût huit fois à chaque insertion. C'est pourquoi indexer aveuglément chaque colonne est une erreur en soi : cela ralentit les écritures et gonfle la base pour des index que les requêtes n'utilisent jamais.

Recherchez les index que rien n'utilise :

-- Postgres: indexes with zero scans since the last stats reset
SELECT relname AS table, indexrelname AS index, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0;

Un index inutilisé n'est que du coût : aucun bénéfice, mais toujours la taxe d'écriture et de stockage.

LIKE et pourquoi il ignore parfois votre index

SELECT * FROM users WHERE email LIKE '%example.com';  -- can't use a standard B-tree index
SELECT * FROM users WHERE email LIKE 'user@%';         -- can

Un index B-tree est trié, donc il peut trouver efficacement tout ce qui commence par un préfixe donné ('user@%' : sauter à cet endroit de l'ordre trié et lire vers l'avant), mais pas tout ce qui se termine par un suffixe donné ('%example.com' : cela peut se trouver n'importe où dans l'ordre de tri, donc on retombe sur un balayage complet). Si la recherche par suffixe ou sous-chaîne est un vrai besoin, c'est le rôle des index trigrammes (pg_trgm de Postgres) ou d'un moteur de recherche dédié : un arbre B n'est pas le bon outil pour cela.

EXPLAIN avant d'indexer, pas après

L'instinct du « ajoutons simplement un index » saute l'étape qui vous dit réellement si cela aidera : regarder d'abord le plan de requête.

EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';

EXPLAIN ANALYZE exécute la requête et rapporte ce qui s'est réellement passé : Seq Scan ou Index Scan, combien de lignes ont été examinées par rapport à celles renvoyées, et les temps réels. Si une requête utilise déjà un index et reste lente, la solution peut être un autre index (couvrant davantage de colonnes de la requête), une requête plus astucieuse (éviter un appel de fonction sur la colonne indexée, qui neutralise aussi l'index), ou l'acceptation du fait que certaines requêtes (un rapport sur une année complète de données) vont par nature balayer beaucoup de lignes.

À retenir

Un index transforme « vérifier chaque ligne » en « parcourir un arbre trié », mais seulement pour les colonnes qu'il couvre et les schémas d'accès qu'il prend en charge : ce n'est pas un interrupteur de performance universel. Ajoutez des index pour les requêtes que vous exécutez réellement, dans l'ordre de colonnes selon lequel ces requêtes filtrent réellement, et vérifiez avec EXPLAIN que la base utilise ce que vous avez construit au lieu de le supposer.