Comment les idées centrales de Jeffrey Ullman alimentent les bases modernes : algèbre relationnelle, règles d'optimisation, jointures et planification façon compilateur qui aident les systèmes à monter en charge.
La plupart des gens qui écrivent du SQL, construisent des tableaux de bord ou optimisent une requête lente ont profité du travail de Jeffrey Ullman — même s'ils n'ont jamais entendu son nom. Ullman est un informaticien et pédagogue dont les recherches et les manuels ont aidé à définir comment les bases de données décrivent les données, raisonnent sur les requêtes et les exécutent efficacement.
Quand un moteur de base de données transforme votre SQL en quelque chose qu'il peut exécuter rapidement, il s'appuie sur des idées à la fois précises et adaptables. Ullman a aidé à formaliser le sens des requêtes (pour que le système puisse les réécrire en toute sécurité) et à relier la pensée base de données à la pensée compilateur (pour qu'une requête soit analysée, optimisée et traduite en étapes exécutables).
Cette influence est discrète parce qu'elle n'apparaît pas comme un bouton dans votre outil BI ni comme une fonctionnalité visible dans votre console cloud. Elle se manifeste par :
JOINCet article utilise les idées centrales d'Ullman comme visite guidée des internals de base de données qui comptent le plus en pratique : comment l'algèbre relationnelle se cache sous le SQL, comment les réécritures de requêtes préservent le sens, pourquoi les optimiseurs fondés sur les coûts font les choix qu'ils font, et comment les algorithmes de jointure décident souvent si un travail se termine en secondes ou en heures.
Nous intégrerons aussi quelques concepts proches du compilateur — parsing, réécriture et planification — parce que les moteurs de base de données ressemblent davantage à des compilateurs sophistiqués que beaucoup ne le réalisent.
Une promesse rapide : nous garderons la discussion précise, mais éviterons les preuves mathématiques lourdes. L'objectif est de vous donner des modèles mentaux utilisables au travail la prochaine fois que la performance, la mise à l'échelle ou un comportement de requête déroutant apparaîtra.
Si vous avez déjà écrit une requête SQL en supposant qu'elle « ne peut signifier qu'une chose », vous vous appuyez sur des idées qu'Ullman a contribué à populariser et formaliser : un modèle propre pour les données, plus des façons précises de décrire ce qu'une requête demande.
Au cœur, le modèle relationnel traite les données comme des tables (relations). Chaque table a des lignes (tuples) et des colonnes (attributs). Cela semble maintenant évident, mais l'aspect important est la discipline que cela crée :
Ce cadrage permet de raisonner sur la correction et la performance sans approximations. Quand vous savez ce qu'une table représente et comment les lignes sont identifiées, vous pouvez prédire ce que les jointures doivent faire, ce que signifient les doublons et pourquoi certains filtres modifient les résultats.
L'enseignement d'Ullman utilise souvent l'algèbre relationnelle comme une sorte de calculatrice de requêtes : un petit ensemble d'opérateurs (select, project, join, union, difference) que l'on combine pour exprimer ce que l'on veut.
Pourquoi c'est utile avec le SQL : les bases de données traduisent le SQL en une forme algébrique puis le réécrivent dans une forme équivalente. Deux requêtes qui semblent différentes peuvent être algébriquement identiques — c'est ainsi que les optimiseurs peuvent réordonner des jointures, pousser des filtres ou supprimer du travail redondant tout en conservant le sens.
Le SQL est en grande partie du « quoi », mais les moteurs optimisent souvent en utilisant l'algèbre comme « comment ».
Les dialectes SQL varient (Postgres vs Snowflake vs MySQL), mais les fondamentaux tiennent. Comprendre les clés, les relations et l'équivalence algébrique vous aide à repérer quand une requête est logiquement incorrecte, quand elle est simplement lente, et quelles modifications préservent le sens entre plateformes.
L'algèbre relationnelle est la « mathématique sous-jacente » du SQL : un petit ensemble d'opérateurs qui décrivent le résultat souhaité. Le travail d'Ullman a contribué à rendre cette vision opératoire claire et enseignable — et c'est toujours le modèle mental que la plupart des optimiseurs utilisent.
Une requête peut s'exprimer comme un pipeline de quelques blocs de construction :
WHERE en SQL)SELECT col1, col2 en SQL)JOIN ... ON ...)UNION)EXCEPT dans plusieurs dialectes SQL)Parce que l'ensemble est petit, il devient plus facile de raisonner sur la correction : si deux expressions algébriques sont équivalentes, elles retournent la même table pour tout état de base de données valide.
Prenons une requête familière :
SELECT c.name
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE o.total > 100;
Conceptuellement, c'est :
commencer par une jointure de customers et orders : customers ⋈ orders
sélectionner uniquement les orders supérieurs à 100 : σ(o.total > 100)(...)
projeter la colonne voulue : π(c.name)(...)
Ce n'est pas la notation interne exacte utilisée par chaque moteur, mais c'est l'idée : le SQL devient un arbre d'opérateurs.
Beaucoup d'arbres différents peuvent signifier le même résultat. Par exemple, les filtres peuvent souvent être poussés plus tôt (appliquer σ avant une grosse jointure), et les projections peuvent souvent éliminer des colonnes inutilisées plus tôt (appliquer π plus tôt).
Ces règles d'équivalence permettent à une base de données de réécrire votre requête en un plan moins coûteux sans changer la signification. Une fois que vous voyez les requêtes comme de l'algèbre, « l'optimisation » cesse d'être de la magie et devient une reformulation sûre guidée par des règles.
Quand vous écrivez du SQL, la base de données ne l'exécute pas « tel que tapé ». Elle traduit votre instruction en un plan de requête : une représentation structurée du travail à effectuer.
Un bon modèle mental est un arbre d'opérateurs. Les feuilles lisent des tables ou des index ; les nœuds internes transforment et combinent des lignes. Les opérateurs courants incluent scan, filter (sélection), project (choix de colonnes), join, group/aggregate et sort.
Les bases séparent typiquement la planification en deux couches :
L'influence d'Ullman apparait dans l'accent mis sur les transformations préservant le sens : réarranger le plan logique de nombreuses façons sans changer la réponse, puis choisir une stratégie physique efficace.
Avant de choisir l'approche finale d'exécution, les optimiseurs appliquent des règles algébriques de « nettoyage ». Ces réécritures ne changent pas les résultats ; elles réduisent le travail inutile.
Exemples fréquents :
Supposons que vous vouliez les commandes d'utilisateurs dans un pays :
SELECT o.order_id, o.total
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE u.country = 'CA';
Une interprétation naïve pourrait joindre tous les users à toutes les orders puis filtrer pour le Canada. Une réécriture qui préserve le sens pousse le filtre plus tôt pour réduire le nombre de lignes impliquées :
country = 'CA'order_id et totalEn termes de plan, l'optimiseur tente de transformer :
Join(Users, Orders) → Filter(country='CA') → Project(order_id,total)
en quelque chose qui ressemble plutôt à :
Filter(country='CA') on Users → Join(with Orders) → Project(order_id,total)
Même réponse. Moins de travail.
Ces réécritures sont faciles à négliger parce que vous ne les tapez jamais — et pourtant elles expliquent en grande partie pourquoi le même SQL peut être rapide sur une base et lent sur une autre.
Quand vous exécutez une requête SQL, la base de données considère plusieurs manières valides d'obtenir le même résultat, puis choisit celle qu'elle s'attend à être la moins coûteuse. Ce processus s'appelle optimisation fondée sur les coûts — et c'est un lieu pratique où la théorie à la Ullman apparaît dans la performance quotidienne.
Un modèle de coûts est un système de notation que l'optimiseur utilise pour comparer des plans alternatifs. La plupart des moteurs estiment le coût en se basant sur quelques ressources clés :
Le modèle n'a pas besoin d'être parfait ; il doit être juste dans la bonne direction assez souvent pour choisir de bons plans.
Avant de pouvoir évaluer des plans, l'optimiseur se pose la question à chaque étape : combien de lignes cela produira-t-il ? C'est l'estimation de cardinalité.
Si vous filtrez WHERE country = 'CA', le moteur estime quelle fraction de la table correspond. Si vous joignez customers et orders, il estime combien de paires correspondront sur la clé de jointure. Ces prédictions déterminent s'il préfère un index scan plutôt qu'un scan complet, un hash join plutôt qu'un nested loop, ou si un tri sera petit ou énorme.
Les estimations de l'optimiseur sont guidées par des statistiques : comptes, distributions de valeurs, taux de null, et parfois corrélations entre colonnes.
Quand les stats sont obsolètes ou manquantes, le moteur peut se tromper de plusieurs ordres de grandeur sur le nombre de lignes. Un plan qui semble bon sur le papier peut devenir coûteux en réalité — symptômes classiques : ralentissements soudains après croissance des données, changements « aléatoires » de plan, ou jointures qui déversent des données sur disque.
De meilleures estimations demandent souvent plus de travail : statistiques plus détaillées, échantillonnage ou exploration d'un plus grand nombre de plans candidats. Mais la planification coûte elle-même du temps, surtout pour des requêtes complexes.
Ainsi, les optimiseurs équilibrent deux objectifs :
Comprendre ce compromis vous aide à interpréter la sortie d'un EXPLAIN : l'optimiseur n'essaie pas d'être brillant — il essaie d'être prévisiblement correct avec des informations limitées.
Ullman a aidé à populariser une idée simple mais puissante : le SQL n'est pas tant « exécuté » que traduit en un plan d'exécution. Nulle part cela n'est plus visible que dans les jointures. Deux requêtes qui retournent les mêmes lignes peuvent avoir des temps d'exécution très différents selon l'algorithme de jointure choisi et l'ordre des jointures.
Nested loop join : pour chaque ligne du côté gauche, trouver les lignes correspondantes à droite. Il peut être rapide quand le côté gauche est petit et que le côté droit dispose d'un index utile.
Hash join : construire une table de hachage à partir d'une des entrées (souvent la plus petite) et la sonder avec l'autre. Il excelle pour de grandes entrées non triées avec des conditions d'égalité (par ex. A.id = B.id), mais nécessite de la mémoire ; un déversement sur disque peut effacer l'avantage.
Merge join : parcourir deux entrées en ordre trié. C'est idéal quand les deux côtés sont déjà ordonnés (ou triables à moindre coût), par exemple quand des index fournissent les lignes dans l'ordre de la clé de jointure.
Avec trois tables ou plus, le nombre d'ordres de jointure possibles explose. Joindre deux grandes tables en premier peut créer un intermédiaire gigantesque qui ralentit tout le reste. Un meilleur ordre commence souvent par le filtre le plus sélectif (le moins de lignes) et étend depuis là, en maintenant les intermédiaires petits.
Les index ne se contentent pas d'accélérer des recherches — ils rendent certaines stratégies de jointure viables. Un index sur la clé de jointure peut transformer un nested loop coûteux en une série de « seeks » rapides. À l'inverse, l'absence ou l'inutilisabilité d'index peut pousser le moteur vers des hash joins ou de grands tris pour des merge joins.
Les bases de données ne se contentent pas d'« exécuter » du SQL. Elles le compilent. L'influence d'Ullman couvre la théorie des bases de données et la pensée compilateur, et cette connexion explique pourquoi les moteurs de requête ressemblent à des chaînes d'outils de langages : ils traduisent, réécrivent et optimisent avant de faire le moindre travail.
Quand vous envoyez une requête, la première étape ressemble à l'avant‑propos d'un compilateur. Le moteur tokenise mots-clés et identifiants, vérifie la grammaire et construit un parse tree (souvent simplifié en AST). C'est là que les erreurs de base sont détectées : virgules manquantes, noms de colonne ambigus, règles de groupement invalides.
Un modèle mental utile : le SQL est un langage de programmation dont le « programme » décrit des relations de données plutôt que des boucles.
Les compilateurs convertissent la syntaxe en une représentation intermédiaire (IR). Les bases font de même : elles traduisent le SQL en opérateurs logiques tels que :
GROUP BY)Cette forme logique se rapproche davantage de l'algèbre relationnelle que du texte SQL, ce qui facilite le raisonnement sur le sens et l'équivalence.
Les optimisations de compilateur conservent le résultat identique tout en rendant l'exécution moins coûteuse. Les optimiseurs de bases de données font de même, en utilisant des systèmes de règles tels que :
C'est la version base de données de « dead code elimination » : pas exactement les mêmes techniques, mais la même philosophie — préserver la sémantique, réduire le coût.
Si votre requête est lente, ne vous contentez pas d'inspecter le SQL. Regardez le plan de requête comme vous liriez la sortie d'un compilateur. Un plan vous dit ce que le moteur a effectivement choisi : ordre des jointures, utilisation d'index et où le temps est passé.
Conclusion pratique : apprenez à lire la sortie d'un EXPLAIN comme une « liste d'assemblage » de performance. Cela transforme l'optimisation en débogage fondé sur des preuves. Pour développer cette habitude, voir /blog/practical-query-optimization-habits.
Une bonne performance de requête commence souvent avant d'écrire le SQL. La théorie de conception de schéma d'Ullman (en particulier la normalisation) vise à structurer les données pour que la base puisse les maintenir correctes, prévisibles et efficaces à mesure qu'elles grandissent.
La normalisation vise à :
Ces gains de correction se traduisent souvent par des gains de performance : moins de champs dupliqués, des index plus petits et moins de mises à jour coûteuses.
Pas besoin d'apprendre des preuves pour utiliser les idées :
La dénormalisation peut être un choix judicieux quand :
L'important est de dénormaliser délibérément, avec un processus pour garder les duplications synchronisées.
La conception du schéma façonne ce que l'optimiseur peut faire. Des clés et des clés étrangères claires permettent de meilleures stratégies de jointure, des réécritures plus sûres et des estimations de cardinalité plus précises. À l'inverse, une duplication excessive peut gonfler les index et ralentir les écritures, et les colonnes multi‑valeurs bloquent des prédicats efficaces. À mesure que le volume de données croît, ces décisions de modélisation initiales valent souvent plus que l'optimisation micro d'une seule requête.
Quand un système « scale », il ne s'agit rarement d'ajouter simplement des machines plus puissantes. Le défi tient souvent à préserver le même sens de requête alors que le moteur choisit une stratégie physique très différente pour garder les temps d'exécution prévisibles. L'accent d'Ullman sur les équivalences formelles est précisément ce qui permet de changer ces stratégies sans modifier les résultats.
À petite échelle, beaucoup de plans « fonctionnent ». À grande échelle, la différence entre scanner une table, utiliser un index ou utiliser un résultat précalculé peut faire passer d'une seconde à des heures. La partie théorique compte parce que l'optimiseur a besoin d'un ensemble sûr de règles de réécriture (pousser les filtres, réordonner les jointures) qui n'altèrent pas la réponse — même si elles modifient radicalement le travail effectué.
Le partitionnement (par date, client, région, etc.) transforme une table logique en plusieurs morceaux physiques. Cela affecte la planification :
Le texte SQL peut rester inchangé, mais le meilleur plan dépendra désormais de l'endroit où vivent les lignes.
Les vues matérialisées sont essentiellement des « sous‑expressions sauvegardées ». Si le moteur peut prouver que votre requête correspond (ou peut être réécrite pour correspondre) à un résultat stocké, il peut remplacer un travail coûteux — comme des jointures et agrégations répétées — par une simple lecture. C'est de la pensée algébrique relationnelle en pratique : reconnaître l'équivalence, puis réutiliser.
Le cache accélère les lectures répétées, mais il ne sauvera pas une requête qui doit scanner trop de données, échanger d'énormes intermédiaires ou calculer une jointure géante. Quand des problèmes d'échelle apparaissent, la solution est souvent : réduire la quantité de données touchées (agencement/partitionnement), réduire le calcul répété (vues matérialisées) ou changer le plan — pas seulement « ajouter du cache ».
L'influence d'Ullman se manifeste dans un état d'esprit simple : traiter une requête lente comme une intention que la base est libre de réécrire, puis vérifier ce qu'elle a réellement décidé de faire. Pas besoin d'être théoricien pour en tirer parti — il suffit d'une routine reproductible.
Commencez par les éléments qui dominent généralement le temps d'exécution :
Si vous ne faites qu'une chose, identifiez le premier opérateur où le nombre de lignes explose. C'est généralement la cause racine.
Faciles à écrire et étonnamment coûteux :
WHERE LOWER(email) = ... peut empêcher l'utilisation d'un index (préférez une colonne normalisée ou un index fonctionnel si pris en charge).L'algèbre relationnelle encourage deux mouvements pratiques :
WHERE avant les jointures quand c'est possible pour réduire les entrées.Une bonne hypothèse ressemble à : « Cette jointure est coûteuse parce qu'on joint trop de lignes ; si on filtre orders aux 30 derniers jours d'abord, l'entrée de la jointure diminue. »
Règle de décision simple :
EXPLAIN montre du travail évitable (jointures inutiles, filtrage tardif, prédicats non sargables).Le but n'est pas d'écrire du SQL « malin », mais d'obtenir des résultats intermédiaires prévisibles et plus petits — exactement le type d'amélioration qui devient plus visible grâce aux idées d'Ullman.
Ces concepts ne sont pas réservés aux administrateurs de bases. Si vous expédiez une application, vous prenez des décisions de planification et de base de données, que vous en ayez conscience ou non : forme du schéma, choix de clés, motifs de requêtes et couche d'accès aux données influencent tout ce que peut faire l'optimiseur.
Si vous utilisez un workflow « vibe‑coding » (par exemple générer une app React + Go + PostgreSQL depuis une interface conversationnelle avec Koder.ai), les modèles mentaux à la Ullman sont un filet de sécurité pratique : vous pouvez examiner le schéma généré pour vérifier des clés et relations propres, inspecter les requêtes de votre application et valider les performances avec EXPLAIN avant que les problèmes n'atteignent la production. Plus vite vous itérez sur « intention de requête → plan → correction », plus vous tirez de valeur d'un développement accéléré.
Vous n'avez pas besoin d'« étudier la théorie » comme loisir séparé. Le moyen le plus rapide de profiter des fondamentaux à la Ullman est d'apprendre juste assez pour lire des plans de requête en confiance — puis de pratiquer sur votre propre base.
Recherchez ces livres et thèmes de cours (aucune affiliation — simplement des points de départ largement cités) :
Commencez petit et ancrez chaque étape à quelque chose d'observable :
Choisissez 2–3 requêtes réelles et itérez :
IN en EXISTS, pousser des prédicats, enlever des colonnes inutiles, comparer les résultats.Utilisez un langage clair, centré sur le plan :
Voilà le gain pratique des fondations d'Ullman : un vocabulaire partagé pour expliquer la performance — sans supposition.
Jeffrey Ullman a contribué à formaliser la façon dont les bases de données « représentent le sens des requêtes » et comment elles peuvent transformer des requêtes pour les exécuter plus rapidement tout en garantissant l'équivalence des résultats. Cette base théorique se manifeste chaque fois qu'un moteur réécrit une requête, réordonne des jointures ou choisit un plan d'exécution différent sans modifier le jeu de résultats.
L'algèbre relationnelle est un petit ensemble d'opérateurs (select, project, join, union, difference) qui décrivent précisément le résultat d'une requête. Les moteurs traduisent couramment le SQL en un arbre d'opérateurs proche de l'algèbre pour appliquer des règles d'équivalence (comme pousser des filtres plus tôt) avant de choisir une stratégie d'exécution.
Parce que l'optimisation repose sur la preuve qu'une requête réécrite renvoie les mêmes résultats. Les règles d'équivalence permettent à l'optimiseur de :
WHERE avant une jointureCes modifications peuvent réduire considérablement le travail sans changer le sens.
Un plan logique décrit quoi calculer (filtre, jointure, agrégation) indépendamment des détails de stockage. Un plan physique choisit comment l'exécuter (scan d'index vs scan complet, hash join vs nested loop, parallélisme, stratégies de tri). La plupart des différences de performance viennent des choix physiques, rendus possibles par des réécritures logiques.
L'optimisation fondée sur les coûts évalue plusieurs plans valides et choisit celui qui a le coût estimé le plus bas. Les coûts sont généralement déterminés par des facteurs pratiques tels que le nombre de lignes traitées, les E/S, le CPU et la mémoire (y compris le risque de déversement disque pour hash ou tri).
L'estimation de cardinalité est la prédiction du nombre de lignes qu'une étape produira. Ces estimations déterminent l'ordre des jointures, le type de jointure et si un scan d'index est rentable. Quand elles sont erronées (souvent à cause de statistiques absentes ou obsolètes), on observe des ralentissements soudains, des déversements massifs ou des changements de plan surprenants.
Concentrez‑vous sur quelques indices forts :
Considérez le plan comme du code compilé : il montre ce que le moteur a réellement choisi de faire.
La normalisation réduit la duplication des faits et les anomalies de mise à jour, ce qui conduit souvent à des tables et index plus petits et à des jointures plus fiables. La dénormalisation peut être appropriée pour l'analytics ou des motifs de lecture intense, mais elle doit être délibérée (règles de rafraîchissement claires, redondance maîtrisée) pour ne pas dégrader la cohérence.
Garder des performances à l'échelle implique souvent de changer la stratégie physique tout en conservant le sens logique. Outils courants :
Le cache accélère les lectures répétées, mais ne corrigera pas une requête qui doit toucher trop de données ou produire d'énormes jointures intermédiaires.