Le cost based optimizer transforme chaque requête SQL en plan d’exécution optimal

Le cost based optimizer est le mécanisme central qui détermine comment un moteur de base de données exécute vos requêtes. Sans lui, les systèmes OLAP traiteraient des milliards de lignes de façon séquentielle et désastreuse.

Apparu dans les années 1980 avec les premiers systèmes relationnels commerciaux, le cost based optimizer (CBO) a remplacé progressivement les optimiseurs basés sur des règles fixes. Il évalue des centaines de plans d’exécution possibles avant d’en retenir un seul. Ce choix repose sur des statistiques collectées sur les tables, index et distributions de données. La précision de ces statistiques conditionne directement la qualité des décisions prises.

Synthèse de l’article en trois points

• Le cost based optimizer sélectionne le plan d’exécution SQL le moins coûteux en ressources (CPU, I/O, mémoire) en se basant sur des statistiques internes actualisées.
• Son efficacité dépend directement de la fraîcheur des statistiques : des statistiques obsolètes génèrent des estimations erronées et des plans sous-optimaux pouvant multiplier les temps d’exécution par 10 à 100.
• Les solutions d’entreprise (Oracle Database, PostgreSQL, SQL Server) proposent des niveaux d’optimisation distincts selon la licence, avec des écarts de performance et de coût significatifs entre éditions.

Comment le cost based optimizer calcule-t-il le meilleur plan d’exécution ?

En 1979, IBM publie le papier fondateur Access Path Selection in a Relational Database Management System signé par Patricia Selinger et son équipe au IBM Research Center. Ce document pose les bases mathématiques du cost based optimizer moderne. Chaque plan d’exécution se voit attribuer un coût estimé exprimé en unités d’accès disque et de cycles CPU. Le CBO génère un arbre de plans alternatifs, avec des jointures en nested loop, hash join ou merge join. Il calcule ensuite le coût estimé de chacun en interrogeant les statistiques stockées dans le catalogue système.

Ces statistiques tiennent en trois points. Il y a d’abord la cardinalité avec le nombre de lignes et la sélectivité sur la proportion de lignes retournées par un prédicat. Vient ensuite les histogrammes de distribution des valeurs. Sur Oracle Database, le paramètre OPTIMIZER_MODE contrôle si le CBO vise le premier résultat (FIRST_ROWS) ou le coût global minimal (ALL_ROWS).

PostgreSQL utilise le paramètre default_statistics_target (valeur par défaut : 100) pour ajuster la granularité des histogrammes. Une requête impliquant trois tables peut générer jusqu’à six plans de jointure distincts. Au-delà de huit tables, le nombre de combinaisons croît de façon factorielle. Le CBO doit ensuite recourir à des heuristiques pour limiter l’espace de recherche.

Les statistiques au cœur du cost based optimizer et leur collecte

Un arrêt de la Cour fédérale américaine dans l’affaire Oracle America Inc. v. Google LLC (2021) a rappelé combien le code d’optimisation interne des bases de données constitue une propriété intellectuelle stratégique. Sur le plan technique, la collecte de statistiques précises est le prérequis absolu à l’efficacité d’un cost based optimizer.

Sous Oracle, la procédure DBMS_STATS.GATHER_TABLE_STATS collecte automatiquement les histogrammes et les Number of Distinct Values ou NDV. Son exécution est planifiée par défaut chaque nuit par le job scheduler interne. PostgreSQL délègue cette tâche au démon autovacuum, qui déclenche un ANALYZE automatique lorsque 20 % des lignes d’une table ont été modifiées. SQL Server dispose d’un mécanisme similaire avec la propriété AUTO_UPDATE_STATISTICS activée par défaut.

Une statistique périmée conduit le CBO à sous-estimer la cardinalité d’un résultat intermédiaire. Si le moteur pense traiter 1 000 lignes alors qu’il en traite 10 millions, il choisira un nested loop join là où un hash join serait 50 fois plus rapide. Des outils tiers comme pgStatsTuner ou SolarWinds Database Performance Analyzer permettent de surveiller la fraîcheur des statistiques en continu. Ces outils transmettent également des alertes avant que la dégradation ne devienne critique.

Les limites du CBO face aux requêtes complexes

En 2014, le groupe TPC (Transaction Processing Performance Council) a documenté dans ses benchmarks TPC-DS que même les CBO les plus avancés produisent des plans sous-optimaux sur 15 à 25 % des requêtes analytiques complexes. Le problème principal est la propagation d’erreurs d’estimation. Lorsqu’une première jointure sous-estime sa cardinalité de sortie, chaque opération suivante hérite de cette erreur et l’amplifie.

Ce phénomène, appelé estimation error amplification, devient critique dans les schémas en étoile ou en flocon typiques des entrepôts de données. Pour y répondre, Oracle 12c a introduit l’Adaptive Query Optimization, qui permet au CBO de corriger son plan en cours d’exécution si les statistiques d’exécution réelles divergent trop des estimations.

PostgreSQL 14 a ajusté le calcul des row estimates pour les partitioned tables, réduisant les erreurs d’un facteur 3 dans les benchmarks publiés par la communauté pgPerfFarm. SQL Server 2022 introduit le Cardinality Estimator v160, avec un modèle de corrélation inter-colonnes plus précis. Malgré ces avancées, les requêtes impliquant des prédicats sur colonnes corrélées non déclarées restent un angle mort de la plupart des CBO commerciaux actuels.

Le cost based optimizer dans les environnements cloud et distribués

En 2012, le papier Dremel publié par Google a ouvert la voie aux CBO distribués capables d’optimiser des requêtes sur des systèmes de fichiers columnar comme Parquet ou ORC à l’échelle du pétaoctet. Dans un environnement distribué (Apache Spark, Presto, Google BigQuery), le cost based optimizer doit intégrer un paramètre supplémentaire absent des bases classiques. Il s’agit du coût réseau lié aux transferts de données entre nœuds.

Apache Spark 2.2 a introduit son CBO natif en 2017, activé via spark.sql.cbo.enabled=true. Il permet des gains de performance de 2x à 8x sur les jointures multi-tables selon les benchmarks publiés par Databricks. Presto (devenu Trino) utilise des cost annotations propagées nœud par nœud dans l’arbre de plan.

BigQuery s’appuie sur un CBO propriétaire invisible à l’utilisateur, dont Google ne publie pas les paramètres internes. La vraie contrainte de ces CBO distribués est la collecte de statistiques sur des sources hétérogènes (data lakes, lakehouses, connecteurs JDBC). L’absence de statistiques force le moteur à utiliser des heuristiques par défaut, dégradant la qualité des plans générés.

Coûts et licences des solutions intégrant un cost based optimizer avancé

Les écarts tarifaires entre éditions sont significatifs pour les fonctionnalités avancées du cost based optimizer. Les fonctions adaptatives et l’optimisation automatique des statistiques sont souvent réservées aux versions entreprise. Le tableau ci-dessous compare les principales solutions du marché selon leurs capacités CBO et leurs niveaux de tarification publics.

Foire aux Questions

Quelle est la différence entre un cost based optimizer et un rule based optimizer ?

Le rule based optimizer (RBO) applique un ordre de priorité fixe entre les opérations (index avant scan complet, par exemple) sans tenir compte du volume réel des données. Le cost based optimizer évalue le coût estimé de chaque plan en s’appuyant sur les statistiques réelles, ce qui le rend adaptatif au contenu de la base.

Comment forcer un plan d’exécution spécifique quand le cost based optimizer fait un mauvais choix ?

La plupart des SGBD proposent des hints d’optimisation. Cette approche doit rester exceptionnelle, car elle court-circuite le CBO et risque de devenir contre-productive après une montée en charge.

Le cost based optimizer prend-il en compte les ressources disponibles au moment de l’exécution ?

Pas dans la grande majorité des implémentations classiques. Le CBO calcule un plan avant l’exécution sur la base de statistiques statiques. Seules les architectures adaptatives permettent une réévaluation partielle pendant l’exécution.

Quel impact a la fragmentation des index sur les décisions du cost based optimizer ?

Une fragmentation élevée (supérieure à 30 %) fausse les statistiques d’I/O estimées par le CBO car les pages de données ne sont plus contiguës sur disque. Le moteur sous-estime alors le coût d’un index range scan, choisissant ce plan là où un full table scan serait plus rapide sur un disque fragmenté.

Existe-t-il des alternatives au cost based optimizer pour les très grandes volumétries ?

Les moteurs Hybrid Transactional/Analytical Processing ou HTAP comme SingleStore ou TiDB combinent CBO classique et compilation JIT des plans pour réduire le temps d’optimisation lui-même. Des approches de machine learning utilisent l’apprentissage par renforcement pour améliorer les estimations du CBO sur la base de l’historique d’exécution réel.

Partager l'article :
• Facebook
• Twitter
• LinkedIn