Traitement et optimisation des requêtes
Le traitement et l'optimisation des requêtes constituent la partie d'un système de gestion de base de données qui transforme une requête déclarative en un plan d'exécution efficace, en choisissant des opérateurs physiques et des chemins d'accès afin de minimiser les coûts sur de grands ensembles de données.
Definition
Le traitement des requêtes est l'ensemble des activités par lesquelles un système de gestion de base de données analyse, optimise et exécute une requête ; l'optimisation des requêtes est la recherche d'un plan d'exécution à faible coût estimé parmi les nombreux plans logiquement équivalents à la requête.
Scope
Ce domaine couvre le processus allant d'une requête analysée aux résultats : la traduction du SQL en expressions d'algèbre relationnelle, les opérateurs physiques qui implémentent chaque opération algébrique (balayages, jointures, tri, agrégation), les index et méthodes d'accès qui fournissent des chemins rapides vers les données, et l'optimiseur basé sur les coûts qui utilise des statistiques pour choisir parmi des plans équivalents. Il exclut le contrôle des transactions et de la concurrence ainsi que la conception des schémas ; il se concentre sur la manière dont une seule requête est évaluée efficacement.
Sub-topics
Core questions
- Comment une requête déclarative est-elle traduite en un arbre d'opérateurs physiques ?
- Quels algorithmes physiques implémentent la sélection, la jointure, le tri et l'agrégation ?
- Comment les index et les méthodes d'accès accélèrent-ils la récupération des données ?
- Comment un optimiseur basé sur les coûts estime-t-il le coût d'un plan et choisit-il parmi les plans ?
- Pourquoi des requêtes logiquement équivalentes peuvent-elles différer énormément en coût d'exécution ?
Key concepts
- plan de requête physique
- équivalences d'algèbre relationnelle
- algorithmes de jointure
- tri et tri fusion externe
- index et méthodes d'accès
- estimation de la sélectivité et de la cardinalité
- modèle de coût
- énumération de l'ordre des jointures
- pipeline et matérialisation
Key theories
- Génération de plan logique-à-physique
- Une requête est d'abord réécrite en utilisant des équivalences d'algèbre relationnelle pour former des plans logiques candidats, puis chaque opérateur algébrique est mappé à un algorithme physique, produisant des plans exécutables dont les coûts peuvent être comparés.
- Optimisation basée sur les coûts
- L'optimiseur utilise des statistiques sur les tailles de tables et les distributions de valeurs pour estimer le coût des plans alternatifs — en particulier les ordres de jointure et les chemins d'accès — et sélectionne le moins coûteux, une approche initiée par l'optimiseur de System R.
- Sélection du chemin d'accès
- Choisir de balayer une table, d'utiliser un index ou d'exploiter le regroupement (clustering) pour chaque opération est essentiel à la performance ; l'optimiseur évalue les estimations de sélectivité et le coût d'E/S pour choisir le meilleur chemin d'accès.
Clinical relevance
L'optimisation des requêtes est ce qui rend les bases de données relationnelles utilisables à grande échelle : la même requête SQL peut s'exécuter en millisecondes ou en heures selon le plan choisi, de sorte que la qualité de l'optimiseur détermine directement les performances de l'analyse commerciale, du traitement des transactions et des applications gourmandes en données.
History
L'optimiseur basé sur les coûts du System R d'IBM (Selinger et al., 1979) a établi l'approche dominante : énumérer les plans, estimer les coûts à partir de statistiques et utiliser la programmation dynamique pour l'ordonnancement des jointures. Des décennies de perfectionnement ont ajouté une meilleure estimation de la cardinalité, de nouveaux opérateurs et des techniques adaptatives, mais le cadre fondamental demeure la base des optimiseurs de requêtes modernes.
Debates
- Fiabilité de l'estimation de la cardinalité
- Les optimiseurs basés sur les coûts dépendent des estimations des tailles de résultats intermédiaires, qui peuvent être très erronées pour des données corrélées ou asymétriques ; les chercheurs débattent de l'investissement à consacrer à de meilleures statistiques et à des estimateurs appris par rapport à une ré-optimisation adaptative en temps réel.
Key figures
- Patricia Selinger
- Jeffrey D. Ullman
- Michael Stonebraker
Related topics
Seminal works
- selinger1979
- garciamolina2008
- silberschatz2019
Frequently asked questions
- Pourquoi la même requête s'exécute-t-elle rapidement sur un système et lentement sur un autre ?
- La performance dépend du plan d'exécution choisi par l'optimiseur, qui à son tour dépend des index disponibles, des statistiques sur les données et du modèle de coût. Différents systèmes, ou le même système avec des statistiques obsolètes, peuvent choisir des plans très différents — par exemple un ordre de jointure différent ou une analyse d'index par rapport à une analyse complète de table.
- Quelle est la partie la plus difficile de l'optimisation des requêtes ?
- Estimer avec précision les tailles des résultats intermédiaires (estimation de la cardinalité). Les erreurs s'accumulent à travers les jointures, de sorte qu'une petite erreur d'estimation au début d'un plan peut amener l'optimiseur à choisir un ordre de jointure ou un chemin d'accès considérablement moins bon. C'est pourquoi l'estimation de la cardinalité reste un problème de recherche actif.