MTI·Training

Jour 20 Day 20 · jeudi 27 août 2026 Thursday 27 August 2026 Data Intermédiaire

Index, modélisation & optimisation SQL Indexes, modeling & SQL optimization

B-tree, EXPLAIN, index composites et formes normales : savoir répondre posément à « cette requête est lente, tu fais quoi ? » — la question data qui départage les candidats. B-trees, EXPLAIN, composite indexes and normal forms: how to calmly answer "this query is slow, what do you do?" — the data question that separates candidates.

L’essentiel

Une base sans index lit ses tables comme on lirait un annuaire page par page : c’est le sequential scan, O(n). Un index est une structure de données auxiliaire — presque toujours un B-tree — que la base maintient à côté de la table pour localiser les lignes en O(log n). C’est la différence entre une requête à 400 ms et la même à 0,1 ms.

Mais rien n’est gratuit : chaque INSERT, UPDATE ou DELETE doit mettre à jour tous les index de la table, et chacun consomme du disque et du cache. Optimiser, c’est arbitrer lecture contre écriture — et la modélisation (normalisation, dénormalisation) fixe en amont la forme des tables sur lesquelles cet arbitrage se joue.

💡 La règle qui cadre tout — on indexe ce que les requêtes réelles filtrent (WHERE), joignent (JOIN … ON) ou trient (ORDER BY). Jamais « toutes les colonnes au cas où » : un index inutilisé est une taxe pure sur les écritures.

Comment ça marche

Le B-tree (« balanced tree ») est l’index par défaut de PostgreSQL comme de MySQL/InnoDB. Ses nœuds sont larges : une page de 8 Ko contient des centaines de clés, donc l’arbre est très plat — hauteur 3 ou 4 même pour des millions de lignes. Chercher une valeur, c’est descendre 3-4 nœuds : voilà le log n. Les feuilles sont triées et chaînées entre elles, ce qui sert aussi les ranges (BETWEEN, >) et les ORDER BY.

              [ racine ]              hauteur 3-4,
             /    |     \             même pour des
      [int.]   [int.]   [int.]        millions de
      /  |  \    ...      ...         lignes
[feuille][feuille][feuille]
    │        │        │
    └── pointeurs vers les lignes (heap)
feuilles triées et chaînées → ranges efficaces

Pour voir ce que fait vraiment la base : EXPLAIN affiche le plan estimé, EXPLAIN ANALYZE exécute la requête et donne les temps réels.

-- Table orders : 5 M de lignes, pas d'index sur customer_id
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 4242;

-- AVANT : la table est lue en entier
-- Seq Scan on orders  (cost=0.00..93241.00 rows=48 ...)
--   Filter: (customer_id = 4242)
--   Rows Removed by Filter: 4999952   ← 5 M lues pour 48 gardées
-- Execution Time: 412.33 ms

CREATE INDEX idx_orders_customer ON orders (customer_id);

-- APRÈS : le B-tree cible directement les bonnes pages
-- Index Scan using idx_orders_customer on orders
--   (cost=0.43..12.15 rows=48 ...)
--   Index Cond: (customer_id = 4242)
-- Execution Time: 0.09 ms             ← ~4500× plus rapide

À repérer dans un plan : le type de scan (Seq Scan vs Index Scan vs Index Only Scan), l’écart entre rows estimées et réelles (statistiques périmées → lancer ANALYZE), et le nœud qui concentre le temps d’exécution.

Concepts clés à maîtriser

  • Index composite & leftmost prefix : un index sur (last_name, first_name) est trié comme un annuaire — par nom, puis prénom. Il sert pour WHERE last_name = … et pour last_name = … AND first_name = …, mais pas pour first_name seul (chercher tous les « Kevin » dans un annuaire oblige à tout lire). D’où le choix de l’ordre : les colonnes filtrées en égalité d’abord, les plus sélectives en tête.
  • Index couvrant : si l’index contient toutes les colonnes demandées par la requête (clause INCLUDE en PostgreSQL), la base répond sans toucher la table — c’est l’Index Only Scan, le plus rapide des scans.
  • Quand un index ne sert à rien : fonction appliquée à la colonne (WHERE lower(email) = … → il faut un index fonctionnel sur lower(email)), LIKE '%terme' (préfixe inconnu, l’arbre trié est inutilisable), faible sélectivité (un booléen à 50/50 : autant lire la table), types incompatibles (comparer une colonne text à un entier).
  • Le coût à l’écriture : chaque écriture met à jour tous les B-trees de la table ; les pages se scindent, l’index se fragmente, les écritures ralentissent.
  • Normalisation 1NF → 3NF — éliminer la redondance et les anomalies de mise à jour :
FormeRègleViolation typique
1NFValeurs atomiques, pas de listes dans une colonnetags = "a,b,c"
2NFPas de dépendance à une partie de la clé composite(order_id, product_id) mais product_name ne dépend que de product_id
3NFPas de dépendance transitive entre colonnes non-clésorders stocke customer_id et customer_city
  • Dénormalisation assumée : dupliquer une donnée (compteur likes_count, total_amount précalculé) pour éviter un JOIN ou un COUNT coûteux. Légitime si c’est un choix documenté avec sa stratégie de synchronisation (trigger, job, événement) — pas un accident.
  • N+1 (aperçu) : 1 requête pour charger 100 commandes, puis 100 requêtes pour leurs clients — le grand classique des ORM. Ça se voit dans les logs SQL et se corrige avec un JOIN ou l’eager loading (select_related, includes, JOIN FETCH).

🎤 En entretien — « cette requête est lente, tu fais quoi ? » Réponse structurée : 1) reproduire et mesurer, 2) EXPLAIN ANALYZE, 3) repérer le nœud coûteux (seq scan sur une grosse table ? estimations fausses ?), 4) vérifier qu’un index existe et est utilisable (fonction sur la colonne ? ordre du composite ?), 5) regarder côté applicatif (N+1, SELECT *), 6) en dernier recours : dénormaliser ou mettre en cache. La méthode vaut plus que la solution.

En entretien

« Pourquoi un index accélère-t-il la recherche ? » — Parce que c’est un B-tree : un arbre équilibré à nœuds très larges (des centaines de clés par page), donc de hauteur 3-4 même pour des millions de lignes. Une recherche descend l’arbre en O(log n) au lieu de lire toute la table en O(n). Bonus : les feuilles triées et chaînées servent aussi les ranges et les ORDER BY.

« Pourquoi ne pas indexer toutes les colonnes ? » — Chaque index est mis à jour à chaque écriture et occupe disque et cache ; le planner n’en utilisera de toute façon qu’un ou deux par requête. Un index que personne n’interroge est un pur coût. On indexe en fonction des requêtes observées, pas du schéma.

« Index sur (a, b) : quelles requêtes en profitent ? » — Celles qui filtrent sur a, ou sur a et b (leftmost prefix). WHERE b = … seul ne peut pas l’utiliser : l’index est trié par a d’abord. Analogie annuaire : trouver un nom connaissant le prénom seul oblige à tout lire.

« EXPLAIN vs EXPLAIN ANALYZE ? » — EXPLAIN montre le plan et les coûts estimés par le planner ; EXPLAIN ANALYZE exécute réellement la requête et ajoute temps et lignes réels. L’écart entre les deux révèle des statistiques périmées. Piège : ANALYZE exécute vraiment — sur un UPDATE, l’encadrer de BEGIN; … ROLLBACK;.

« Normaliser ou dénormaliser ? » — Normaliser en 3NF par défaut : une seule source de vérité, pas d’anomalies de mise à jour. Dénormaliser ensuite, ponctuellement et en connaissance de cause, quand une lecture critique le justifie — en documentant comment la copie reste synchrone.

Pièges & idées reçues

⚠️ Piège vécu — EXPLAIN ANALYZE exécute la requête. Sans conséquence sur un SELECT, mais sur un UPDATE ou un DELETE les lignes sont réellement modifiées. Réflexe : BEGIN; EXPLAIN ANALYZE …; ROLLBACK;.

  • « L’index existe, donc il est utilisé » — non : fonction sur la colonne, mauvais ordre du composite, statistiques périmées ou faible sélectivité peuvent le rendre invisible pour le planner. Toujours vérifier au plan.
  • LIKE '%terme%' n’utilise pas un B-tree — seul un préfixe fixe ('terme%') le peut. Pour la recherche « contient », PostgreSQL propose pg_trgm avec un index GIN.
  • Les clés étrangères ne sont pas auto-indexées en PostgreSQL (elles le sont côté InnoDB). Les colonnes FK utilisées dans les JOIN méritent presque toujours leur index.
  • La clé primaire, elle, est toujours indexée — inutile d’en rajouter un.
  • Les ORM cachent le SQL, pas son coût : activer les logs de requêtes en dev pour attraper les N+1 avant la prod.

Pour aller plus loin

The essentials

A database without indexes reads its tables the way you’d read a phone book page by page: that’s the sequential scan, O(n). An index is an auxiliary data structure — almost always a B-tree — that the database maintains alongside the table to locate rows in O(log n). It’s the difference between a 400 ms query and the same one at 0.1 ms.

But nothing is free: every INSERT, UPDATE or DELETE must update all the table’s indexes, and each one consumes disk and cache. Optimizing means trading reads against writes — and modeling (normalization, denormalization) shapes upfront the tables on which that trade-off plays out.

💡 The rule that frames everything — you index what real queries filter (WHERE), join (JOIN … ON) or sort (ORDER BY). Never “every column just in case”: an unused index is a pure tax on writes.

How it works

The B-tree (“balanced tree”) is the default index in PostgreSQL as well as MySQL/InnoDB. Its nodes are wide: an 8 KB page holds hundreds of keys, so the tree is very flat — height 3 or 4 even for millions of rows. Looking up a value means walking down 3-4 nodes: that’s your log n. The leaves are sorted and chained together, which also serves ranges (BETWEEN, >) and ORDER BY.

              [ root ]                height 3-4,
             /    |    \              even for
      [int.]   [int.]  [int.]         millions of
      /  |  \    ...     ...          rows
  [leaf]  [leaf]  [leaf]
    │        │       │
    └── pointers to the rows (heap)
sorted, chained leaves → efficient ranges

To see what the database actually does: EXPLAIN shows the estimated plan, EXPLAIN ANALYZE executes the query and reports real timings.

-- orders table: 5M rows, no index on customer_id
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 4242;

-- BEFORE: the whole table is read
-- Seq Scan on orders  (cost=0.00..93241.00 rows=48 ...)
--   Filter: (customer_id = 4242)
--   Rows Removed by Filter: 4999952   ← 5M read to keep 48
-- Execution Time: 412.33 ms

CREATE INDEX idx_orders_customer ON orders (customer_id);

-- AFTER: the B-tree targets the right pages directly
-- Index Scan using idx_orders_customer on orders
--   (cost=0.43..12.15 rows=48 ...)
--   Index Cond: (customer_id = 4242)
-- Execution Time: 0.09 ms             ← ~4500× faster

What to spot in a plan: the scan type (Seq Scan vs Index Scan vs Index Only Scan), the gap between estimated and actual rows (stale statistics → run ANALYZE), and the node that concentrates the execution time.

Key concepts to master

  • Composite indexes & the leftmost prefix: an index on (last_name, first_name) is sorted like a phone book — by last name, then first name. It works for WHERE last_name = … and for last_name = … AND first_name = …, but not for first_name alone (finding every “Kevin” in a phone book means reading the whole book). Hence how you pick the column order: equality-filtered columns first, most selective ones leading.
  • Covering index: if the index contains every column the query asks for (INCLUDE clause in PostgreSQL), the database answers without touching the table — that’s the Index Only Scan, the fastest scan there is.
  • When an index is useless: a function applied to the column (WHERE lower(email) = … → you need a functional index on lower(email)), LIKE '%term' (unknown prefix, the sorted tree can’t help), low selectivity (a 50/50 boolean: might as well read the table), incompatible types (comparing a text column to an integer).
  • The write cost: every write updates all the table’s B-trees; pages split, the index fragments, writes slow down.
  • Normalization 1NF → 3NF — eliminating redundancy and update anomalies:
FormRuleTypical violation
1NFAtomic values, no lists inside a columntags = "a,b,c"
2NFNo dependency on part of a composite key(order_id, product_id) but product_name depends only on product_id
3NFNo transitive dependency between non-key columnsorders stores customer_id and customer_city
  • Deliberate denormalization: duplicating a value (a likes_count counter, a precomputed total_amount) to avoid a costly JOIN or COUNT. Legitimate if it’s a documented choice with its sync strategy (trigger, job, event) — not an accident.
  • N+1 (preview): 1 query to load 100 orders, then 100 queries for their customers — the great ORM classic. It shows up in SQL logs and is fixed with a JOIN or eager loading (select_related, includes, JOIN FETCH).

🎤 In an interview — “this query is slow, what do you do?” Structured answer: 1) reproduce and measure, 2) EXPLAIN ANALYZE, 3) spot the costly node (seq scan on a big table? wrong estimates?), 4) check that an index exists and is usable (function on the column? composite order?), 5) look at the application side (N+1, SELECT *), 6) as a last resort: denormalize or cache. The method is worth more than the fix.

In an interview

“Why does an index speed up lookups?” — Because it’s a B-tree: a balanced tree with very wide nodes (hundreds of keys per page), so height 3-4 even for millions of rows. A lookup walks the tree in O(log n) instead of reading the whole table in O(n). Bonus: the sorted, chained leaves also serve ranges and ORDER BY.

“Why not index every column?” — Every index is updated on every write and occupies disk and cache; the planner will only use one or two per query anyway. An index nobody queries is pure cost. You index based on observed queries, not on the schema.

“Index on (a, b): which queries benefit?” — Those filtering on a, or on a and b (leftmost prefix). WHERE b = … alone can’t use it: the index is sorted by a first. Phone book analogy: finding a name when you only know the first name means reading everything.

“EXPLAIN vs EXPLAIN ANALYZE?” — EXPLAIN shows the plan and the planner’s estimated costs; EXPLAIN ANALYZE actually runs the query and adds real times and row counts. The gap between the two reveals stale statistics. Trap: ANALYZE really executes — on an UPDATE, wrap it in BEGIN; … ROLLBACK;.

“Normalize or denormalize?” — Normalize to 3NF by default: a single source of truth, no update anomalies. Then denormalize selectively and knowingly, when a critical read justifies it — documenting how the copy stays in sync.

Pitfalls & misconceptions

⚠️ Real-world trap — EXPLAIN ANALYZE executes the query. Harmless on a SELECT, but on an UPDATE or DELETE the rows really are modified. Reflex: BEGIN; EXPLAIN ANALYZE …; ROLLBACK;.

  • “The index exists, so it’s used” — no: a function on the column, wrong composite order, stale statistics or low selectivity can make it invisible to the planner. Always check the plan.
  • LIKE '%term%' cannot use a B-tree — only a fixed prefix ('term%') can. For “contains” search, PostgreSQL offers pg_trgm with a GIN index.
  • Foreign keys are not auto-indexed in PostgreSQL (they are in InnoDB). FK columns used in JOINs almost always deserve their own index.
  • The primary key, however, is always indexed — no need to add another.
  • ORMs hide the SQL, not its cost: enable query logs in dev to catch N+1 before production.

Going further

S'entraîner sur ce sujet → Practice this topic →