Optimisation de requêtes basée sur les coûts

L'optimisation de requêtes basée sur les coûts explore l'espace des plans d'exécution équivalents pour une requête et sélectionne celui dont le coût estimé est le plus bas, en utilisant des statistiques sur les données et un modèle de coût d'exécution.

Definition

L'optimisation de requêtes basée sur les coûts est le processus d'estimation, à partir de statistiques de données et d'un modèle de coût, du coût d'exécution de plans équivalents alternatifs pour une requête et de sélection du plan ayant le coût estimé le plus bas, généralement avec un ordre de jointure choisi par programmation dynamique.

Scope

Ce sujet aborde la manière dont un optimiseur choisit un plan : l'espace de recherche des plans généré par les équivalences d'algèbre relationnelle et les opérateurs physiques alternatifs, le modèle de coût qui évalue les plans (principalement en termes d'E/S et de CPU), l'estimation de la cardinalité et de la sélectivité à partir de statistiques et d'histogrammes, et l'approche de programmation dynamique pour l'énumération de l'ordre des jointures introduite par System R. Il exclut l'implémentation des opérateurs eux-mêmes et la réécriture logique basée sur des règles au-delà de ce qui alimente la génération de plans.

Core questions

• Comment l'espace des plans d'exécution équivalents est-il généré et élagué ?
• Comment l'optimiseur estime-t-il la cardinalité et la sélectivité des opérations ?
• Comment la programmation dynamique énumère-t-elle efficacement les ordres de jointure ?
• De quoi le modèle de coût tient-il compte, et comment les coûts d'E/S et de CPU sont-ils combinés ?
• Pourquoi les erreurs d'estimation de la cardinalité entraînent-elles de mauvais choix de plan ?

Key concepts

• espace de recherche des plans
• modèle de coût (E/S et CPU)
• estimation de la sélectivité et de la cardinalité
• histogrammes et statistiques
• énumération de l'ordre des jointures
• programmation dynamique
• ordres intéressants
• optimisation basée sur les transformations

Key theories

Optimisation par programmation dynamique de System R

L'optimiseur de Selinger énumère les ordres de jointure de bas en haut (bottom-up) avec la programmation dynamique, en conservant le plan le moins coûteux pour chaque sous-ensemble de relations (et chaque ordre de tri intéressant), ce qui rend la recherche dans le vaste espace des ordres de jointure traitable.

Estimation de la cardinalité et de la sélectivité

L'optimiseur estime le nombre de tuples produits par chaque opération en utilisant des statistiques de table, des histogrammes et des formules de sélectivité ; ces estimations alimentent le modèle de coût et sont la principale source d'erreur d'optimisation.

Modèles de coût et stratégies de recherche

Les plans sont évalués par un modèle de coût combinant les effets d'E/S, de CPU et de mémoire ; au-delà de la programmation dynamique de System R, les optimiseurs basés sur des transformations explorent les plans via des règles de réécriture pour étendre l'optimisation à des opérateurs plus riches et à des environnements distribués.

Clinical relevance

L'optimiseur est le composant qui permet aux utilisateurs d'écrire du SQL déclaratif sans spécifier comment l'exécuter ; la qualité de ses estimations de coûts et de sa recherche détermine directement la rapidité des requêtes sur de grandes bases de données, de sorte que l'optimisation basée sur les coûts est l'une des parties les plus étudiées et commercialement importantes des systèmes de gestion de bases de données.

History

L'optimiseur System R de 1979, développé par Selinger et ses collègues, a introduit l'optimisation basée sur les coûts avec l'ordonnancement des jointures par programmation dynamique et l'estimation des coûts basée sur la sélectivité, définissant ainsi le domaine. Des optimiseurs ultérieurs basés sur des transformations, tels que Volcano et Cascades, ont généralisé la recherche, et les travaux en cours sur l'estimation de la cardinalité, y compris les modèles appris, abordent la faiblesse centrale de ce cadre.

Debates

Estimation de la cardinalité versus exécution adaptative

Étant donné que l'optimisation basée sur les coûts n'est aussi bonne que ses estimations de taille, qui sont souvent erronées pour les données corrélées, les chercheurs débattent de l'opportunité d'investir dans de meilleures statistiques et des estimateurs appris par machine ou de s'appuyer davantage sur une ré-optimisation adaptative en temps réel qui corrige les mauvais plans pendant l'exécution.

Key figures

• Patricia Selinger
• Goetz Graefe
• Surajit Chaudhuri

Seminal works

• selinger1979
• graefe1993

Frequently asked questions

Pourquoi un optimiseur choisit-il parfois un mauvais plan ?

Les optimiseurs basés sur les coûts s'appuient sur des estimations du nombre de lignes que chaque opération produira. Lorsque les données sont asymétriques ou que les colonnes sont corrélées, ces estimations peuvent être très éloignées de la réalité, et l'erreur se cumule à travers les jointures. Une estimation erronée peut amener l'optimiseur à choisir un ordre de jointure ou un chemin d'accès médiocre, même si le plan semblait peu coûteux sur le papier.

Pourquoi utiliser la programmation dynamique pour l'ordonnancement des jointures ?

Le nombre d'ordres de jointure possibles croît de manière combinatoire avec le nombre de tables, de sorte qu'une recherche exhaustive est irréalisable. La programmation dynamique construit des plans optimaux pour des ensembles de relations plus grands à partir de plans optimaux pour des sous-ensembles plus petits, réduisant considérablement le travail tout en trouvant un bon (souvent optimal) ordre de jointure pour les tailles de requêtes typiques.