Résumé

  • System R choisissait le coût estimé le plus faible parmi les plans effectivement examinés. Sa formule combinait lectures de pages et appels à l’interface de stockage ; elle ne mesurait pas à l’avance la durée réelle.
  • La sélectivité produit une estimation de cardinalité, laquelle modifie le prix apparent des chemins d’accès, des ordres de jointure et des opérateurs. Les « ordres intéressants » empêchent d’éliminer un plan localement plus cher mais utile plus tard.
  • Selinger a organisé un travail collectif signé avec Morton Astrahan, Donald Chamberlin, Raymond Lorie et Thomas Price. Sa force durable tient à la séparation entre hypothèse, décision physique et observation d’exécution.

Ce que le chiffre ne dit pas

Deux plans peuvent répondre exactement à la même question SQL. Le premier parcourt un index sélectif, produit peu de lignes et conserve un ordre exploitable par l’agrégation. Le second balaie une grande table, fabrique un résultat intermédiaire massif puis trie. Le sens relationnel est identique ; l’expérience physique ne l’est pas.

Au moment du choix, aucun des deux parcours n’a encore eu lieu. L’optimiseur ignore quelles pages seront en mémoire, quelle concurrence pèsera sur le stockage, combien de lignes un paramètre précis rencontrera et si un opérateur dépassera son budget mémoire. Il doit s’engager à partir d’une représentation du monde.

Le mot « coût » désigne donc une comparaison interne au modèle. Après l’exécution seulement apparaissent les lignes réelles, les lectures, le travail du processeur, les débordements et le temps écoulé. Confondre ces deux registres transforme un pari informé en certitude fictive.

Le mérite de System R n’est pas d’avoir supprimé cet écart. Il est d’avoir rendu le pari explicite, calculable et révisable.

SQL a déplacé l’autorité physique

Une requête déclarative décrit le résultat voulu sans imposer la suite des opérations de stockage. Cette abstraction permet au moteur de changer de voie lorsque la taille des tables, les index ou le matériel évoluent. En échange, l’auteur de l’application abandonne une part de contrôle au planificateur.

L’article publié en 1979 portait le titre anglais Access Path Selection in a Relational Database Management System. Il décrit quatre moments. L’analyse construit une représentation de la requête. L’optimisation produit une spécification d’accès. La génération de code la transforme en programme. L’exécution vient ensuite. La chronologie fixe la nature de la décision : le plan est choisi avant que cette exécution puisse fournir ses propres preuves.

La correction sémantique et l’économie physique restent séparées. Réordonner des jointures ou remplacer un balayage par un index ne doit pas changer le résultat, sous réserve des règles du langage sur les valeurs nulles, les doublons ou l’agrégation. Mais un résultat correct peut arriver trop tard. Une mauvaise réponse relève de la sémantique ; une bonne réponse obtenue à un coût démesuré relève de l’estimation, de la planification ou de l’exécution.

Cette séparation explique aussi pourquoi une victoire ponctuelle ne suffit pas. Un plan rapide avec un cache chaud ou une valeur de paramètre rare ne devient pas, par ce seul fait, le meilleur plan général.

Le catalogue résumait le monde au lieu de le copier

System R utilisait des statistiques de catalogue : NCARD pour le nombre de tuples d’une relation, TCARD pour ses pages, P pour l’occupation, ICARD pour les clés distinctes d’un index et NINDX pour les pages de cet index. Ces grandeurs rendaient la planification possible sans lire toutes les données.

Elles étaient initialisées puis renouvelées périodiquement par UPDATE STATISTICS. Les auteurs expliquaient qu’une mise à jour après chaque modification imposerait trop d’écritures de catalogue et de verrouillage. Dès l’origine, l’observation parfaite était donc rejetée pour une raison économique.

Une statistique est une compression. Elle conserve certaines propriétés, en perd d’autres et vieillit. Plus on veut la rendre fine et actuelle, plus sa production coûte cher. Moins on l’entretient, plus le choix du plan dépend d’une image décalée.

Cette tension ne se résume pas à une négligence d’exploitation. Toute base choisit quoi échantillonner, à quelle fréquence et avec quelle granularité. L’optimiseur ne voit jamais le futur complet ; il voit un dossier constitué à un prix acceptable.

De la sélectivité à la cardinalité

System R associait aux prédicats un facteur de sélectivité : la fraction attendue des tuples satisfaisant la condition. Une égalité appuyée par un index pouvait exploiter le nombre de clés distinctes. En l’absence de meilleure information, le système appliquait des valeurs par défaut : un dixième pour une égalité sans index, un tiers pour une borne ouverte, un quart pour un intervalle fermé.

Le texte précise que ces valeurs n’ont pas d’autre signification qu’un classement grossier. Il ne s’agit pas de lois statistiques. Ce sont des conventions permettant de décider malgré une information incomplète.

Pour plusieurs conditions reliées par AND, les facteurs pouvaient être multipliés. Le calcul suppose implicitement l’indépendance. Or une ville et son code postal, une gamme de produits et son prix, un type de compte et son solde sont souvent corrélés. Multiplier des probabilités marginales peut alors produire une estimation minuscule ou énorme sans rapport avec les données.

La cardinalité transforme cette fraction en nombre de lignes. Le raisonnement QCARD associe tailles de relations et sélectivités. Ce nombre alimente ensuite les coûts des opérateurs. Sous-estimer l’entrée externe d’une boucle imbriquée rend la répétition artificiellement bon marché ; à l’exécution, chaque ligne supplémentaire déclenche du travail. Surestimer un filtre peut au contraire faire écarter un index réellement efficace.

Sélectivité et cardinalité ne sont donc pas synonymes. La première est une estimation proportionnelle ; la seconde est un volume. Une petite erreur en amont traverse les jointures, modifie les tailles intermédiaires, l’ordre choisi, la mémoire et les tris.

L’étude de Leis et de ses coauteurs en 2015 a montré que les erreurs de cardinalité dégradaient généralement davantage les plans que les petites imperfections des fonctions de coût. Leur rétrospective de 2025 insiste encore sur ces erreurs, la robustesse et l’adaptation. La chaîne conceptualisée par System R reste bien celle où se concentre le risque.

Une monnaie de classement

La formule publiée était :

COST = PAGE FETCHES + W × (RSI CALLS)

Les lectures de pages représentaient les entrées-sorties. Les appels à la Research Storage Interface approchaient le calcul. Le coefficient W établissait un taux de conversion. Intégrer le processeur était une avancée importante, mais additionner ces grandeurs ne produisait pas des secondes.

Le score pouvait ordonner des candidats. Il ne connaissait pas exactement le cache, la séquentialité des lectures, la contention, les débordements, le matériel futur ou la consommation finale du client. Le candidat le moins coûteux selon ce taux était un candidat à la rapidité, pas une mesure anticipée.

Dire qu’un plan est optimal exige deux compléments : optimal pour quel objectif, et dans quel ensemble de plans ? Le modèle peut privilégier les ressources totales, la latence ou un compromis. L’énumérateur peut n’autoriser que certains arbres de jointure et opérateurs. Le minimum est relatif à ces choix.

La documentation actuelle de PostgreSQL permet de revoir cette frontière. Les unités de coût sont conventionnelles et propres à la plateforme. EXPLAIN présente les estimations sans exécuter. EXPLAIN ANALYZE exécute et ajoute lignes et temps observés. La première sortie est la décision ex ante ; la seconde est l’épreuve du réel.

Trois décisions cachées dans le mot « plan »

Un chemin d’accès dit comment atteindre une relation de base : balayage ou index, par exemple. Un opérateur physique dit comment joindre, trier ou agréger. L’ordre des jointures détermine quelles relations sont combinées en premier et quelle taille auront les résultats intermédiaires.

Ces choix se répondent. Un index peut filtrer mais aussi livrer un ordre. Une jointure très sélective placée tôt réduit tout l’aval. Un opérateur adapté à une petite entrée devient mauvais si cette entrée a été sous-estimée. Un tri payé maintenant peut supprimer un tri futur.

La relation entre logique et physique ne doit donc pas être écrasée par un mot unique. L’équivalence sémantique autorise plusieurs réalisations. Le planificateur doit comparer leurs propriétés sans confondre la validité du résultat et le prix de sa production.

Pourquoi conserver un « ordre intéressant »

Un chemin par index peut être plus coûteux qu’un balayage pour la relation immédiatement traitée. S’il fournit déjà l’ordre d’une jointure, d’un GROUP BY ou de l’ORDER BY final, il peut éviter un tri et réduire le coût global. L’éliminer sur le seul critère local serait une erreur.

System R conservait le plan non ordonné le moins cher et le meilleur plan pour chaque ordre jugé intéressant. Deux résultats intermédiaires contenant les mêmes lignes ne sont physiquement substituables au même prix que s’ils transportent aussi les propriétés pertinentes.

Cette règle donne une valeur d’option à l’ordre. Dépenser davantage à une étape peut préserver une possibilité utile. L’optimisation n’est donc pas une succession de choix gloutons ; elle doit conserver des candidats dont la valeur apparaîtra plus loin.

Les ordres intéressants constituent également une discipline de mémoire. Il n’est pas nécessaire de garder tous les plans, mais il serait dangereux de ne garder qu’un score. Le système retient les différences physiques qui peuvent modifier la suite.

Le prix de la recherche

Avec plusieurs relations, les ordres de jointure se multiplient de façon combinatoire. Énumérer chaque permutation tend vers une croissance factorielle. Une optimisation exhaustive pourrait dépenser plus de temps qu’elle n’en économise.

System R utilisait la programmation dynamique. Pour chaque sous-ensemble de relations, l’optimiseur sauvegardait les meilleurs représentants par ordre intéressant, puis réutilisait ces résultats pour construire des ensembles plus grands. Une heuristique repoussait les produits cartésiens, généralement producteurs d’intermédiaires volumineux.

L’article décrit ainsi une recherche organisée autour des sous-ensembles et des propriétés utiles, et rapporte des jointures de huit tables optimisées en quelques secondes sur un IBM 370/158. Le résultat est majeur, mais il ne signifie pas que toute forme physique imaginable a été visitée.

L’élagage définit le problème calculable. La programmation dynamique trouve le meilleur candidat dans l’espace qu’on lui donne ; elle ne démontre pas que cet espace est l’univers de tous les plans. Parler d’optimum global sans nommer l’énumérateur, les opérateurs et les règles d’élagage retire précisément les conditions de la preuve.

Le temps d’optimisation et celui d’exécution sont enfin deux postes distincts. Rechercher davantage peut économiser des heures plus tard ; pour une requête brève et fréquente, le même effort devient un gaspillage. Les plans génériques des requêtes préparées économisent la planification, mais peuvent mal représenter des paramètres atypiques.

La validation faisait partie du contrat

Les auteurs de 1979 reconnaissaient que leurs coûts prédits étaient souvent inexacts en valeur absolue. Ils observaient aussi que le meilleur chemin testé était choisi dans la majorité des cas et demandaient davantage de validation. Un score peut donc être mal calibré tout en classant utilement.

En 1986, Mackert et Lohman ont confronté les estimations de R* aux ressources mesurées. Une grande partie du modèle d’entrées-sorties fonctionnait, mais le calcul demandait plus de détail ; les hypothèses de tampon importaient ; les boucles imbriquées dépendaient ensemble de la cardinalité de jointure, de l’entrée externe et des pages disponibles.

Cette comparaison retire au modèle toute immunité. Une formule n’est pas vraie parce qu’elle est formelle. Ses écarts avec l’exécution indiquent où améliorer statistiques, coefficients, hypothèses d’opérateurs ou rétroaction.

Les travaux d’IBM sur les statistiques juste à temps ont prolongé ce principe. Si une statistique indépendante est absente ou périmée, le planificateur peut demander une observation ciblée au moment où elle devient utile. L’incertitude ne disparaît pas ; on paie une meilleure information là où sa valeur attendue justifie son coût.

Une direction intellectuelle, cinq signatures

Patricia G. Selinger a rejoint IBM Research en 1975. IBM lui attribue la direction des travaux d’optimisation de System R, puis des responsabilités dans R* et dans les technologies de bases de données. Elle est devenue IBM Fellow en 1994, a été élue à la National Academy of Engineering des États-Unis en 1999 et a pris sa retraite d’IBM en 2018.

Le papier fondateur porte cinq noms : P. Griffiths Selinger, puis Morton M. Astrahan, avec Donald D. Chamberlin, ainsi que Raymond A. Lorie et enfin Thomas G. Price. Dans son histoire orale, Chamberlin explique que Selinger a organisé le travail et l’article décisif, tout en citant Lorie, Price et Astrahan comme contributeurs importants. L’histoire plus large d’IBM relie ce travail au modèle relationnel d’Edgar Codd, au SQL de Chamberlin et Raymond Boyce, au compilateur de Lorie et à l’ensemble de l’équipe System R.

Le leadership de Selinger réside dans l’architecture d’une décision collective : statistiques en entrée, sélectivité et cardinalité, coût pondéré, propriétés physiques utiles, recherche bornée. Il ne requiert ni mythe de l’inventrice solitaire ni étiquette d’« intelligence artificielle ». Les mécanismes décrits sont explicites : règles, estimations et programmation dynamique.

Une frontière conçue pour être corrigée

La réussite durable n’est pas la découverte d’un chemin vrai pour toujours. C’est la création d’un niveau où le sens de la requête reste stable tandis que ses moyens physiques peuvent changer. On peut enrichir les statistiques, modéliser des corrélations, modifier les poids, ajouter des opérateurs ou réagir aux mesures sans réécrire toutes les requêtes en procédures.

Cette souplesse exige une phrase exacte : le plan choisi est une prévision autorisée. Il a gagné la comparaison effectivement mise en œuvre. Il n’a pas encore reçu la confirmation de l’exécution. Conserver l’estimation et l’observation permet ensuite d’apprendre de leur distance.

Un bon optimiseur n’est pas celui qui prétend ne jamais se tromper. C’est celui dont les hypothèses sont identifiables, les erreurs mesurables et les décisions révisables sans altérer le sens déclaré par l’utilisateur.

Sources