Opérateurs d'exécution de requêtes

Les opérateurs d'exécution de requêtes sont les algorithmes physiques — balayages (scans), sélections, projections, tris, agrégations et jointures — qu'un moteur de base de données compose en un plan et exécute pour produire le résultat d'une requête.

Definition

Un opérateur d'exécution de requête est une implémentation d'une opération d'algèbre relationnelle sous forme d'algorithme sur des flux de tuples ; les opérateurs sont composés en un arbre ou un pipeline qui, une fois exécuté, calcule le résultat d'une requête.

Scope

Ce sujet couvre les opérateurs physiques d'un moteur de requêtes et leur organisation pour l'exécution : le modèle d'itérateur (ouvrir-suivant-fermer), le pipelining versus la matérialisation, les balayages de tables et d'index, la sélection et la projection, le tri-fusion externe, le regroupement et l'agrégation, et l'élimination des doublons. Il aborde la manière dont les opérateurs consomment et produisent des flux de tuples et comment la mémoire et les E/S affectent leur coût. Il exclut les spécificités des algorithmes de jointure et de l'optimiseur qui choisit parmi les opérateurs, qui sont des sujets connexes.

Core questions

• Comment le modèle d'itérateur (ouvrir-suivant-fermer) permet-il de composer des opérateurs en un pipeline ?
• Quand un résultat est-il traité en pipeline plutôt que matérialisé sur disque ?
• Comment la sélection, la projection et l'élimination des doublons sont-elles implémentées physiquement ?
• Comment le tri-fusion externe gère-t-il les données plus grandes que la mémoire ?
• Comment le budget mémoire et le coût des E/S influencent-ils la performance des opérateurs ?

Key concepts

• modèle d'itérateur / ouvrir-suivant-fermer
• balayages de tables et d'index
• opérateurs de sélection et de projection
• tri-fusion externe
• regroupement basé sur le hachage
• opérateurs d'agrégation
• élimination des doublons
• pipelining versus matérialisation

Key theories

Le modèle d'itérateur (Volcano)

Chaque opérateur expose des méthodes open, next et close et extrait des tuples de ses enfants à la demande ; cette interface uniforme permet de composer des opérateurs arbitraires en pipelines et constitue la base de la plupart des moteurs de requêtes.

Pipelining versus matérialisation

Les opérateurs pipelinés transmettent les tuples directement à leur parent sans écrire de résultats intermédiaires, ce qui économise des E/S, tandis que les opérateurs bloquants tels que le tri doivent matérialiser leur entrée avant de produire une sortie ; l'optimiseur équilibre les deux approches.

Tri et agrégation externes

Lorsque les données dépassent la mémoire, le tri-fusion externe et le regroupement basé sur le hachage les traitent en plusieurs passes sur disque ; ces algorithmes sous-tendent les clauses ORDER BY, GROUP BY, l'élimination des doublons et les jointures par tri-fusion.

Clinical relevance

Les opérateurs d'exécution sont le point où le coût estimé d'un plan de requête devient le temps d'exécution réel : le choix et l'implémentation des opérateurs, ainsi que leur capacité à utiliser efficacement la mémoire et à éviter les E/S disque inutiles, déterminent le débit et la latence de chaque requête traitée par une base de données.

History

Le modèle d'itérateur a été cristallisé dans le cadre d'évaluation de requêtes Volcano de Graefe et son étude de 1993 sur les techniques d'évaluation de requêtes, qui a catalogué les opérateurs physiques utilisés par les moteurs relationnels. L'interface uniforme du modèle a rendu les moteurs de requêtes extensibles et composables pratiques et reste la norme, des travaux ultérieurs ayant ajouté l'exécution vectorisée et compilée pour une plus grande efficacité.

Key figures

• Goetz Graefe
• Jeffrey D. Ullman

Seminal works

• graefe1993
• garciamolina2008

Frequently asked questions

Qu'est-ce que le modèle d'itérateur ?

C'est une conception dans laquelle chaque opérateur physique implémente la même interface — typiquement open, next et close — et produit des tuples un par un lorsque son parent appelle next. Étant donné que tous les opérateurs partagent cette interface, ils peuvent être assemblés en des arbres de plan arbitraires, et les tuples remontent l'arbre à la demande.

Pourquoi certains opérateurs sont-ils dits bloquants ?

Un opérateur bloquant ne peut produire aucune sortie tant qu'il n'a pas consommé toutes ses entrées — le tri et certaines agrégations en sont des exemples, car le résultat final dépend de chaque tuple d'entrée. Les opérateurs bloquants doivent matérialiser leur entrée, tandis que les opérateurs pipelinés, tels que la sélection, peuvent émettre des résultats au fur et à mesure.