- Le moteur SQL est la couche logique de la base de données, qui fonctionne entre le client et le stockage
- Explication détaillée des principaux processus du moteur SQL : parsing, binding, simplification du plan, exploration des jointures et évaluation des coûts, exécution, spooling des résultats
- Le parsing convertit la requête SQL en arbre de syntaxe abstraite structuré (AST)
- Le binding fait correspondre les champs de l’AST avec les symboles du catalogue actuel de la base de données
- La simplification du plan normalise la syntaxe SQL complexe en une forme simplifiée afin d’accélérer l’exécution
- L’exploration du plan examine différentes variantes de jointures, d’agrégations et de fonctions de fenêtre pour trouver le meilleur plan d’exécution
- L’exécution et le spooling des résultats convertissent le plan final dans un format exécutable puis renvoient les résultats au client
Vue d’ensemble du moteur SQL
- Le moteur SQL est une couche d’intermédiation logique entre les requêtes du client et le stockage des données
- Étapes principales
- Parsing : convertit la requête en AST (arbre de syntaxe abstraite)
- Binding : relie les identifiants de l’AST aux symboles du catalogue de la base de données
- Plan Simplification : simplifie diverses syntaxes SQL en une forme de plan standardisée
- Join Exploration & Costing : explore différents ordres de jointure et en évalue le coût
- Execution : exécute la requête à l’aide du meilleur plan d’exécution
- Spooling Results : renvoie les résultats au client
Parsing
- Le parsing est le processus qui tokenise la requête d’entrée et la convertit en AST
- Un parseur récursif à droite est plus facile à comprendre et à déboguer, mais consomme davantage de mémoire de pile
- Un parseur récursif à gauche (basé sur Yacc) est plus efficace en mémoire, mais nécessite une logique plus complexe
- Dolt utilise un parseur récursif à gauche pour offrir un parsing rapide
- Lorsque le parsing réussit, la structure de l’AST correspond aux règles Yacc
Binding
- Le binding consiste à relier les champs de l’AST aux symboles réels des tables et colonnes de la base de données
- Concepts principaux
- Définition de table : joue le rôle de source des données
- Définition de colonne : référence une colonne spécifique dans une source de table
- Alias : utilise une valeur scalaire à la fois comme source et comme destination
- Sous-requête scalaire : partage le scope parent et effectue la résolution des noms
- Le résultat du binding génère des nœuds de plan d’exécution au format sql.Node
Simplification du plan
- Processus qui convertit différentes expressions SQL en une forme normalisée afin d’aider à l’optimisation de l’exécution
- Optimisations représentatives
- Filter Pushdown : suppression des lignes inutiles
- Column Pruning : suppression des colonnes inutiles
- Des transformations comme la decorrelation de sous-requêtes (subquery decorrelation) sont aussi appliquées pour optimiser les plans de jointure
Coercition de types
- La coercition de types est le processus qui convertit automatiquement le type d’une expression selon le contexte
- Le type peut varier selon le contexte, comme dans WHERE ou INSERT
- Dolt traite progressivement la conversion de types à l’étape du binding
Exploration du plan
- L’exploration des jointures consiste à générer et examiner différents ordres de jointure
- Deux stratégies d’exploration
- Backtracking top-down : explore uniquement les ordres de jointure valides
- Programmation dynamique bottom-up (DP) : essaie toutes les combinaisons pour trouver l’ordre de jointure optimal
- Une structure Memo est utilisée pour gérer efficacement les états intermédiaires
Dépendances fonctionnelles
- Le coût peut augmenter fortement lors de jointures impliquant 5 tables ou plus
- Exploiter des relations 1:1, comme les jointures basées sur une clé primaire (PK), permet de réduire le coût d’exploration
- L’optimisation donne la priorité à LOOKUP_JOIN
Résumé des représentations intermédiaires (IR Intermission)
- Résumé des 3 étapes d’IR parcourues jusqu’ici
- AST : organisation des tokens
- Binding de scope : validation des références de colonnes
- Memo : représentation pour l’exploration des jointures et l’évaluation des coûts
Évaluation du coût des jointures
- L’évaluation du coût des jointures consiste à estimer le coût d’exécution de tous les plans possibles
- Facteurs de coût
- Taille des tables d’entrée
- Taille de la table résultante
- Type d’opérateur de jointure (
LOOKUP_JOIN, HASH_JOIN, etc.)
- Dolt évalue les coûts à partir de statistiques de table précises (histogrammes)
Indications de jointure
- Le moteur tente d’appliquer en priorité la stratégie de jointure en fonction des hints fournis par l’utilisateur
- Les hints contradictoires ou inadaptés sont ignorés
Exécution
- Le meilleur plan est converti en une structure itérateur (Volcano Iterator) réellement exécutable
- Caractéristiques
- Itérateur non matérialisant (non-materializing) : renvoie immédiatement les lignes
- Itérateur matérialisant (materializing) : collecte toutes les lignes avant de les renvoyer
- Les références de colonnes sont mappées sur des offsets d’index avant l’exécution
E/S et spooling des résultats
- Les résultats d’exécution sont convertis au format du protocole MySQL puis transmis au client
- Dans certains cas, l’optimisation lit directement les résultats depuis la couche de stockage clé-valeur (KV)
- Le traitement par lots (batch) et la réutilisation des buffers améliorent la vitesse de traitement et l’efficacité mémoire
Perspectives
- Dolt utilise principalement une exécution orientée ligne (row-based execution) sur un serveur local
- Il s’appuie sur 3 étapes de représentation intermédiaire (IR) — AST, binding basé sur les scopes et exploration des jointures via une structure Memo — pour construire le meilleur plan d’exécution
- Il détermine la meilleure stratégie de jointure grâce à la recherche d’ordre de jointure (Join Search) et à l’évaluation du coût des jointures (Join Costing)
- À l’avenir, des améliorations de performances sont prévues via l’intégration des IR et l’optimisation de la réutilisation mémoire
Aucun commentaire pour le moment.