Comment fonctionne une base de données SQL

Quand tu envoies SELECT nom FROM etudiant WHERE num = 42;, le SGBD (système de gestion de base de données, le logiciel qui tient la base) reçoit une demande, pas une marche à suivre. Il l'analyse, choisit lui-même un plan d'exécution, puis lit des pages de données sur le disque ou en mémoire : ici, toute la table, ou quelques pages d'un index si c'est moins coûteux. Toute modification passe d'abord par un journal, qui permet de repartir après une panne. On suit ce trajet dans PostgreSQL, syntaxe et modélisation supposées connues.

Le trajet d'une requête

SQL est déclaratif : ta requête dit quelles lignes tu veux, jamais comment les chercher. Le « comment », c'est le SGBD qui le décide, en quatre étapes.

Étape 1 : l'analyse. Le texte est contrôlé selon la grammaire de SQL, puis chaque nom est cherché dans le catalogue, la description interne des tables et des colonnes. Une faute de syntaxe ou une colonne inconnue s'arrête ici, avant toute lecture de données.

Étape 2 : la réécriture. Des règles stockées dans le catalogue transforment la requête ; une vue, par exemple, y est remplacée par la requête qui la définit.

Étape 3 : la planification. L'optimiseur choisit l'ordre de lecture des tables, l'usage ou non d'un index, la méthode de jointure : c'est le plan d'exécution.

Étape 4 : l'exécution. L'exécuteur suit le plan, lit les lignes, filtre, trie, joint et te renvoie le résultat.

Deux plans différents donnent le même résultat, pas dans le même temps.

Pages et index B-tree

PostgreSQL range chaque table et chaque index en pages de taille fixe, en général 8 ko. L'adresse physique d'une ligne, c'est le numéro de sa page et son rang dans cette page. Pour lire une ligne, le SGBD charge toute sa page ; les pages lues récemment restent en mémoire vive, dans un cache, et les relire n'impose aucun accès au disque.

Sans index, chercher num = 42 oblige à lire toutes les pages de la table : c'est le parcours séquentiel. Un index B-tree est un arbre de pages. Ses feuilles contiennent les valeurs de la colonne, triées, chacune avec l'adresse de sa ligne. Ses pages internes aiguillent vers le niveau inférieur, à partir d'une racine unique.

Pour trouver 42, le SGBD lit la racine, suit l'aiguillage jusqu'à la bonne feuille, puis lit la page de la table : une page par niveau, plus une. Les feuilles sont chaînées dans l'ordre, donc pour num BETWEEN 40 AND 60 il descend jusqu'à 40 puis avance de feuille en feuille. Le B-tree sert ainsi à =, <, >, BETWEEN, IN et IS NULL.

Son prix : chaque ligne insérée s'ajoute aussi aux index, qui occupent leurs propres pages ; trop d'index ralentissent les écritures.

Piège classique : un index sur nom ne sert pas à WHERE lower(nom) = 'dupont', car il range les valeurs de nom, pas celles de lower(nom). Il faut un index sur l'expression : CREATE INDEX ON etudiant (lower(nom));. De même, LIKE '%dupont' ne peut pas utiliser un B-tree : un motif qui commence par % ne dit pas où entrer dans l'index.

L'optimiseur compare des coûts

Qu'un index existe n'oblige pas le SGBD à s'en servir : l'optimiseur estime le coût de chaque plan possible et garde le moins cher. Écris EXPLAIN devant ta requête pour voir son choix. Voici l'exemple de la documentation de PostgreSQL :

EXPLAIN SELECT * FROM tenk1;
 Seq Scan on tenk1  (cost=0.00..445.00 rows=10000 width=244)

Seq Scan est le parcours séquentiel. Dans cost, le premier nombre est le coût de démarrage, payé avant la première ligne renvoyée, le second le coût total ; rows est le nombre de lignes estimé.

Formule : pour un parcours séquentiel,

$$\text{coût} = \text{pages lues} \times \texttt{seq\_page\_cost} + \text{lignes lues} \times \texttt{cpu\_tuple\_cost}$$

avec par défaut $\texttt{seq\_page\_cost} = 1$ et $\texttt{cpu\_tuple\_cost} = 0{,}01$. La table tenk1 occupe 345 pages pour 10 000 lignes : $345 \times 1 + 10\,000 \times 0{,}01 = 445$.

L'unité est arbitraire, calée sur une page lue en séquence : ce ne sont pas des millisecondes. Une page lue au hasard, quand on saute de l'index vers la table, vaut par défaut $\texttt{random\_page\_cost} = 4$. L'index gagne donc quand la condition garde peu de lignes, le parcours séquentiel quand elle en garde beaucoup.

Piège classique : « J'ai créé un index et EXPLAIN affiche encore Seq Scan, donc l'index ne marche pas. » Faux si ta condition garde une grosse part de la table : tout lire dans l'ordre coûte alors moins cher que sauter de page en page. L'exercice 2 le chiffre.

Le journal passe avant les données

Une transaction regroupe des ordres entre BEGIN et COMMIT, appliqués tous ou aucun. Parmi les garanties ACID, la durabilité promet qu'une transaction validée survit à une panne. Écrire à chaque COMMIT toutes les pages modifiées serait lent : elles sont éparpillées sur le disque.

PostgreSQL passe donc par un journal, le WAL (write-ahead log). Chaque modification y est d'abord décrite, et une page de données n'est écrite sur le disque qu'après les entrées du journal qui la concernent. Au COMMIT, seul le journal est forcé sur le disque ; écrit à la suite, il coûte bien moins cher que des pages dispersées. Après une panne, le SGBD relit le journal et refait ce qui n'avait pas atteint les pages : c'est la reprise par rejeu, ou REDO.

Règle : une transaction est validée quand le journal qui la décrit est sur le disque, pas quand ses pages de données y sont.

Plusieurs transactions en même temps

PostgreSQL fait cohabiter les connexions par MVCC (contrôle de concurrence multiversion) : chaque ordre SQL voit un instantané, une version figée des données. Lire ne bloque donc jamais écrire, et écrire ne bloque jamais lire.

Deux écritures sur la même ligne, elles, passent l'une après l'autre. Au niveau d'isolation par défaut, Read Committed, la seconde attend que la première valide ou annule. Si la première valide, la seconde revérifie sa condition WHERE sur la nouvelle version de la ligne, puis y applique son calcul. Cela protège SET solde = solde - 30, calculé dans la base, mais pas une valeur calculée par ton programme puis recopiée : c'est l'exercice 3.

Exercices corrigés

Les tables sont fictives. Cherche avant d'ouvrir la correction.

Exercice 1 : La table inscription occupe 1 200 pages et contient 50 000 lignes ; les paramètres de coût sont ceux par défaut. EXPLAIN SELECT * FROM inscription; affiche Seq Scan on inscription (cost=0.00..X rows=50000 width=40). Calcule X, puis dis ce que signifie 0.00.

Correction :

Le parcours séquentiel lit les 1 200 pages et traite les 50 000 lignes : $X = 1\,200 \times 1 + 50\,000 \times 0{,}01 = 1\,200 + 500 = 1\,700$, en unités de coût, pas en millisecondes.

Le 0.00 est le coût de démarrage : ce parcours renvoie sa première ligne sans rien préparer avant.

Exercice 2 : Même table, avec un index B-tree à trois niveaux sur num_etudiant. On ne compte que les pages, sans cache : 4 par page lue au hasard, 1 par page lue en séquence.

a) WHERE num_etudiant = 42 renvoie une ligne. Combien de pages lit le plan par l'index, et pour quel coût ? Compare au parcours séquentiel.

b) Une autre condition garde 30 % des lignes, et chaque ligne trouvée par l'index coûte une page lue au hasard. Compare les deux plans, sans compter la descente dans l'index.

Correction :

a) Trois pages d'index (racine, page interne, feuille), puis la page de la table : 4 pages au hasard, soit $4 \times 4 = 16$. En séquence : 1 200 pages, coût 1 200. L'index gagne largement.

b) $50\,000 \times 0{,}30 = 15\,000$ lignes, donc $15\,000 \times 4 = 60\,000$ par l'index, contre 1 200 en séquence : l'index coûte 50 fois plus. L'optimiseur choisit le parcours séquentiel, et il a raison.

Exercice 3 : Le compte 7 d'une association affiche 100 euros. Anne retire 30 euros et Bilal 20 euros, avec une application qui lit le solde par SELECT, calcule le nouveau solde, puis l'écrit par UPDATE compte SET solde = ... WHERE id = 7. Dans l'ordre : Anne lit, Bilal lit, Anne écrit et valide, Bilal écrit et valide. Quel est le solde final, et que devrait-il être ? Corrige la requête.

Correction :

Anne écrit SET solde = 70 et valide. Bilal, qui a lu 100, écrit SET solde = 80 : son ordre porte bien sur la version validée par Anne, mais il ne contient qu'une valeur, 80, qui écrase 70.

Solde final : 80 euros, au lieu de $100 - 30 - 20 = 50$ euros. Le retrait d'Anne a disparu : c'est une mise à jour perdue.

La correction calcule dans la base : UPDATE compte SET solde = solde - 30 WHERE id = 7; pour Anne, solde - 20 pour Bilal. L'ordre de Bilal part alors des 70 euros validés, et le solde final vaut 50 euros.

À retenir

À retenir :

SQL dit quoi, le SGBD décide comment : analyse, réécriture, planification, exécution.
Tables et index sont rangés en pages, de 8 ko en général ; un B-tree se descend de la racine à une feuille.
Une page lue au hasard vaut par défaut quatre pages lues en séquence : si la condition garde beaucoup de lignes, Seq Scan gagne.
Au COMMIT, seul le journal est forcé sur le disque ; après une panne, on le rejoue.
Deux écritures sur une même ligne passent l'une après l'autre : calcule dans l'UPDATE, pas dans ton programme.

Sources

Documentation officielle de PostgreSQL 18 (en anglais), sur postgresql.org : parcours d'une requête, pages, index B-tree, EXPLAIN, coûts du planificateur, journal WAL et contrôle de concurrence.