Sur une table d’un million de lignes, la même SELECT peut prendre cinquante millisecondes, ou nettement moins d’une seule milliseconde. Toute la différence tient à un choix : la base de données lit chaque ligne pour trouver celles que vous avez demandées, ou elle saute directement dessus. Un index est ce qui lui permet de sauter, et vous le payez à chaque écriture.

Concrètement, un index est une seconde copie triée d’une ou plusieurs colonnes, stockée à côté de la table et mise à jour automatiquement à chaque modification de la table. La base de données l’utilise pour atteindre les lignes correspondantes sans toucher au reste.

Pourquoi une requête sans index lit toute la table

Sans index, WHERE customer_id = 42 oblige Postgres à lire chaque ligne et à tester la condition sur chacune. C’est un balayage séquentiel (Seq Scan). Sur mille lignes, vous ne le remarquez pas. Sur un million de lignes où presque rien ne correspond, vous lisez et jetez 999 989 lignes pour en obtenir 11.

Vous pouvez le constater vous-même. Démarrez un conteneur Postgres, configuré comme dans Qu’est-ce que Docker Compose et Comment l’Utiliser :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

services:
  db:
    image: postgres:16
    environment:
      POSTGRES_PASSWORD: postgres
    ports:
      - "5432:5432"
    volumes:
      - db-data:/var/lib/postgresql/data

volumes:
  db-data:

1
2

docker compose up -d db
docker compose exec db psql -U postgres

Créez ensuite une table assez grande pour que la différence se voie :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

CREATE TABLE orders (
  id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  customer_id integer NOT NULL,
  status text NOT NULL,
  created_at timestamptz NOT NULL DEFAULT now(),
  total_cents integer NOT NULL
);

INSERT INTO orders (customer_id, status, created_at, total_cents)
SELECT
  (random() * 50000)::int,
  (ARRAY['pending', 'paid', 'shipped', 'refunded'])[(floor(random() * 4) + 1)::int],
  now() - (random() * interval '365 days'),
  (random() * 20000)::int
FROM generate_series(1, 1000000);

ANALYZE orders;

Un million de lignes, aucun index sur customer_id. Demandez les commandes d’un client. Les exemples ci-dessous désactivent d’abord les workers parallèles (SET max_parallel_workers_per_gather = 0), pour que le plan reste sur un seul nœud — sur une machine multicœur, Postgres pourrait sinon répartir le même balayage entre un Gather et plusieurs workers Parallel Seq Scan, ce qui revient au même avec plus de processus en même temps :

1
2

SET max_parallel_workers_per_gather = 0;
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;

1
2
3
4
5

 Seq Scan on orders  (cost=0.00..20834.00 rows=21 width=31) (actual time=1.066..53.238 rows=11 loops=1)
   Filter: (customer_id = 42)
   Rows Removed by Filter: 999989
 Planning Time: 0.301 ms
 Execution Time: 53.284 ms

Rows Removed by Filter: 999989 est la facture. Postgres a lu toute la table pour renvoyer 11 lignes.

Ce qu’un index B-tree stocke vraiment

Une table sans index est une boîte à chaussures pleine de reçus, jetés les uns sur les autres dans l’ordre d’arrivée. Retrouver tous les reçus d’un client oblige à vider la boîte.

Un index B-tree, ce sont ces mêmes reçus classés dans un tiroir, triés par client. Le niveau le plus bas, les leaf pages, contient chaque valeur indexée avec un pointeur vers sa ligne sur le disque. Au-dessus des feuilles se trouvent quelques pages internes, chacune portant la valeur la plus basse d’un intervalle et un pointeur vers celui-ci. Les pages de Postgres font 8 Ko par défaut et une page interne peut pointer vers des centaines d’enfants, donc trois ou quatre niveaux couvrent des dizaines de millions de lignes. Une recherche lit une page par niveau et atterrit sur la bonne feuille. Quelques lectures de page au lieu d’un passage sur toute la table.

Ajoutez l’index et relancez la même requête :

1

CREATE INDEX idx_orders_customer_id ON orders (customer_id);

1
2

SET max_parallel_workers_per_gather = 0;
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;

1
2
3
4
5
6
7

 Bitmap Heap Scan on orders  (cost=4.59..85.69 rows=21 width=31) (actual time=0.217..0.295 rows=11 loops=1)
   Recheck Cond: (customer_id = 42)
   Heap Blocks: exact=11
   ->  Bitmap Index Scan on idx_orders_customer_id  (cost=0.00..4.58 rows=21 width=0) (actual time=0.090..0.090 rows=11 loops=1)
         Index Cond: (customer_id = 42)
 Planning Time: 0.979 ms
 Execution Time: 0.449 ms

De 53 ms à 0,45 ms, soit environ 120 fois plus rapide, et le coût estimé passe de 20834 à 86. Le Seq Scan a disparu, et il n’y a plus de ligne Rows Removed by Filter : il n’y avait rien à jeter.

Postgres a choisi une Bitmap Heap Scan plutôt qu’un simple Index Scan. Avec une vingtaine de lignes correspondantes dispersées dans la table, il est moins coûteux d’extraire d’abord toutes les entrées voulues de l’index (la ligne Bitmap Index Scan), de les trier par page physique, puis de visiter chaque page du heap une seule fois (Heap Blocks: exact=11), plutôt que de sauter dans le heap séparément pour chaque ligne. Filtrez sur une seule ligne (une égalité sur une colonne unique, par exemple id = 42) et vous verrez à la place un simple Index Scan. Dans les deux cas, l’index fait le même travail : atteindre les lignes correspondantes sans lire celles qui ne correspondent pas.

Comment fonctionne l’ordre des colonnes dans un index composite

Un index peut couvrir plusieurs colonnes, et l’ordre dans lequel vous les listez décide des requêtes qu’il peut servir. CREATE INDEX ON orders (customer_id, status) trie d’abord par customer_id, puis par status à l’intérieur de chaque customer_id. Il peut donc répondre à :

  • WHERE customer_id = 42, en utilisant la première colonne.
  • WHERE customer_id = 42 AND status = 'paid', en utilisant les deux.

Il ne peut pas répondre efficacement à WHERE status = 'paid' seul. status n’est trié qu’à l’intérieur du groupe de chaque client, donc il n’existe pas de suite triée unique de lignes 'paid' sur laquelle l’arbre puisse sauter. C’est la règle du préfixe le plus à gauche (leftmost prefix rule) : un index composite n’aide une requête que si celle-ci contraint ses colonnes à partir de la gauche, dans l’ordre, sans trou.

Deux règles pour choisir l’ordre. D’abord, placez devant la colonne sur laquelle vos requêtes filtrent seule, car c’est la seule que l’index peut servir seul. Ensuite, placez les colonnes que vous comparez avec = avant une colonne que vous comparez avec une plage (>, <, BETWEEN), car tout ce qui suit la colonne de plage cesse de restreindre la recherche. Pour cette table, customer_id (environ 50 000 valeurs distinctes) passe avant status (quatre valeurs) : vous cherchez des clients en permanence, et vous ne voulez jamais balayer toutes les commandes 'paid' sans distinguer le client.

Si vous avez aussi besoin de recherches rapides uniquement par status, créez un second index. Ne réordonnez pas le premier.

Quand un index-only scan saute la table

Le Bitmap Heap Scan ci-dessus touche quand même la table : c’est ce qu’indique Heap Blocks: exact=11. L’index contient customer_id et un pointeur vers chaque ligne ; SELECT * veut aussi status, total_cents et created_at, qui n’existent que dans la table. Une clause INCLUDE place des colonnes supplémentaires directement dans l’index :

1
2
3

CREATE INDEX idx_orders_customer_covering
  ON orders (customer_id)
  INCLUDE (status, total_cents);

status et total_cents voyagent en tant que payload. Elles ne font pas partie de la clé de tri, donc un WHERE status = ... ne peut pas les utiliser pour chercher. Mais demandez seulement les colonnes que l’index porte désormais :

1

EXPLAIN ANALYZE SELECT customer_id, status, total_cents FROM orders WHERE customer_id = 42;

1
2
3
4
5

 Index Only Scan using idx_orders_customer_covering on orders  (cost=0.42..4.79 rows=21 width=15) (actual time=0.071..0.073 rows=11 loops=1)
   Index Cond: (customer_id = 42)
   Heap Fetches: 0
 Planning Time: 0.442 ms
 Execution Time: 0.108 ms

Index Only Scan et Heap Fetches: 0 : chaque ligne vient directement de l’index, sans aucun passage par la table. C’est un index-only scan.

Heap Fetches: 0 dépend de la visibility map de la table, qui marque les pages dont les lignes sont visibles pour toutes les transactions — un balayage ne saute le heap que pour les pages marquées. VACUUM pose ces marques (généralement autovacuum, qui tourne selon son propre calendrier, pas quelque chose que vous lancez à la main) et toute écriture sur une page les efface à nouveau. Sur une table avec beaucoup d’écritures récentes, de nombreuses pages ne sont pas marquées, Heap Fetches grimpe au-dessus de zéro, et Postgres visite quand même le heap pour ces lignes. Les index couvrants rapportent le plus sur des tables bien plus lues qu’écrites.

Ce que coûte un index et pourquoi Postgres l’ignore

Chaque INSERT écrit une entrée dans chaque index de la table, et un UPDATE qui modifie une colonne indexée écrit lui aussi de nouvelles entrées. Cinq index, c’est cinq structures supplémentaires à maintenir à chacune de ces écritures. Les index prennent aussi de la place disque. Comparez directement les deux tailles :

1
2

SELECT pg_size_pretty(pg_relation_size('orders')) AS table_size,
       pg_size_pretty(pg_relation_size('idx_orders_customer_id')) AS index_size;

Et parfois vous créez l’index et le planner ne l’utilise pas. Ce n’est rarement un bug de Postgres. C’est en général l’un de ces cas :

  • Une fonction enrobe la colonne. WHERE lower(email) = '[email protected]' ne peut pas utiliser un index simple sur email, car l’index stocke les valeurs brutes, pas lower(email). Indexez l’expression (CREATE INDEX ON users (lower(email))) ou filtrez sur la colonne brute.
  • Un joker en tête. WHERE name LIKE '%smith' ne donne à l’arbre aucun préfixe où chercher. LIKE 'smith%' si.
  • Faible sélectivité. Un index sur un booléen réparti 50/50 ne fait rien gagner. Postgres lirait quand même la moitié de l’index et la plupart des pages de la table, donc le planner choisit à juste titre un balayage séquentiel.
  • Statistiques obsolètes. Le planner choisit entre les types de balayage à partir des statistiques que ANALYZE collecte dans pg_statistic. Après un chargement massif sans ANALYZE, ses estimations de lignes peuvent être très éloignées de la réalité. Lancez-le après chaque gros chargement, comme dans la configuration ci-dessus.

Quand vous voyez un Seq Scan là où vous attendiez un Index Scan, vérifiez la requête par rapport à cette liste avant de toucher à l’index.

Quand ajouter un index et quand s’en passer

Ajoutez-en un quand une colonne apparaît dans une WHERE, une JOIN ou un ORDER BY sur une table assez grande pour qu’un balayage coûte un temps réel, et que le filtre est sélectif : il réduit le résultat à une petite partie de la table, pas à la moitié. Passez-vous-en quand la table est assez petite pour qu’un balayage soit déjà rapide, quand la table reçoit beaucoup d’écritures et peu de lectures, ou quand la colonne ne peut rien restreindre.

N’en ajoutez pas sur une intuition. Lancez d’abord EXPLAIN ANALYZE sur la requête lente. Si elle montre déjà un Index Scan et reste lente, l’index n’est pas votre problème : réécrivez la requête, ou mettez le résultat en cache avec Redis. Si elle montre un Seq Scan sur une grande table avec un filtre sélectif, créez l’index exactement sur les colonnes utilisées par la WHERE, dans l’ordre requis par la règle du préfixe le plus à gauche, puis relancez EXPLAIN ANALYZE pour confirmer que le plan a changé.

Articles associés