- Die SQL-Engine ist die logische Schicht einer Datenbank und arbeitet zwischen Client und Speicher
- Detaillierte Erläuterung der Kernprozesse einer SQL-Engine: Parsing, Binding, Planvereinfachung, Join-Exploration und Kostenbewertung, Ausführung und Ergebnis-Spooling
- Parsing wandelt SQL-Abfragen in einen strukturierten abstrakten Syntaxbaum (AST) um
- Binding ordnet die Felder des AST den Symbolen im aktuellen Datenbankkatalog zu
- Planvereinfachung normalisiert komplexe SQL-Syntax in ein vereinfachtes Format, um die Ausführung zu beschleunigen
- Plan-Exploration untersucht verschiedene Varianten von Joins, Aggregationen und Window-Funktionen, um den optimalen Ausführungsplan zu finden
- Ausführung und Ergebnis-Spooling wandeln den finalen Plan in ein ausführbares Format um und geben die Ergebnisse an den Client zurück
Überblick über die SQL-Engine
- Die SQL-Engine ist die logische Vermittlungsschicht zwischen Client-Anfragen und dem Datenspeicher
- Wichtige Phasen
- Parsing: Wandelt die Abfrage in einen AST (abstrakten Syntaxbaum) um
- Binding: Verknüpft Identifikatoren im AST mit Symbolen im Datenbankkatalog
- Plan Simplification: Vereinfacht verschiedene SQL-Syntaxformen zu einer standardisierten Planform
- Join Exploration & Costing: Untersucht verschiedene Join-Reihenfolgen und bewertet deren Kosten
- Execution: Führt die Abfrage mit dem optimalen Ausführungsplan aus
- Spooling Results: Gibt die Ergebnisse an den Client zurück
Parsing
- Parsing ist der Prozess, die eingegebene Abfrage zu tokenisieren und in einen AST umzuwandeln
- Ein rechtsrekursiver Parser ist leicht verständlich und einfach zu debuggen, benötigt aber viel Stack-Speicher
- Ein linksrekursiver Parser (auf Yacc-Basis) ist speichereffizienter, erfordert jedoch komplexere Logik
- Dolt verwendet einen linksrekursiven Parser, um schnelles Parsing zu unterstützen
- Wenn das Parsing erfolgreich ist, entspricht die AST-Struktur den Yacc-Regeln
Binding
- Binding ist der Prozess, Felder im AST mit den tatsächlichen Tabellen- und Spaltensymbolen der Datenbank zu verknüpfen
- Zentrale Konzepte
- Tabellendefinition: Dient als Datenquelle
- Spaltendefinition: Referenziert eine bestimmte Spalte aus einer Tabellenquelle
- Alias: Verwendet Skalarwerte sowohl als Quelle als auch als Senke
- Skalare Subquery: Teilt den übergeordneten Scope und führt Name Binding aus
- Als Ergebnis des Bindings werden Ausführungsplan-Knoten im Format sql.Node erzeugt
Planvereinfachung
- Dies ist der Prozess, verschiedene SQL-Darstellungen in eine normalisierte Form zu überführen, um die Ausführungsoptimierung zu unterstützen
- Typische Optimierungen
- Filter Pushdown: Entfernt unnötige Zeilen
- Column Pruning: Entfernt nicht benötigte Spalten
- Auch Join-Plan-Optimierungen werden durch Transformationen wie Subquery-Dekorrelation (
subquery decorrelation) durchgeführt
Type Coercion
- Type Coercion ist der Prozess, Ausdruckstypen abhängig vom Kontext automatisch umzuwandeln
- Je nach Kontext wie
WHERE oder INSERT können unterschiedliche Typen erforderlich sein
- Dolt verarbeitet Typumwandlungen schrittweise in der Binding-Phase
Join-Exploration
- Join-Exploration ist der Prozess, verschiedene Join-Reihenfolgen zu erzeugen und zu prüfen
- Zwei Explorationsstrategien
- Top-down-Backtracking: Untersucht nur gültige Join-Reihenfolgen
- Bottom-up Dynamic Programming (DP): Probiert alle Kombinationen aus, um die optimale Join-Reihenfolge zu finden
- Zur effizienten Verwaltung von Zwischenzuständen wird eine Memo-Struktur verwendet
Funktionale Abhängigkeiten
- Bei Joins mit fünf oder mehr Tabellen können die Kosten stark ansteigen
- Wenn man 1:1-Beziehungen wie PK-basierte Joins nutzt, lassen sich die Explorationskosten senken
- Dabei wird LOOKUP_JOIN zur Optimierung bevorzugt berücksichtigt
Zusammenfassung der Zwischenrepräsentationen (IR Intermission)
- Zusammenfassung der bisher verwendeten drei IR-Stufen
- AST: Ordnung der Tokens
- Scope Binding: Validierung von Spaltenreferenzen
- Memo: Darstellung für Join-Exploration und Kostenbewertung
Join-Kostenbewertung
- Join-Kostenbewertung ist der Prozess, die Ausführungskosten aller möglichen Pläne abzuschätzen
- Kostenfaktoren
- Größe der Eingabetabellen
- Größe der Ergebnistabelle
- Art des Join-Operators (
LOOKUP_JOIN, HASH_JOIN usw.)
- Dolt bewertet die Kosten auf Basis präziser Tabellenstatistiken (Histogramme)
Join-Hints
- Je nach vom Nutzer vorgegebenen Hints wird versucht, bestimmte Join-Strategien bevorzugt anzuwenden
- Widersprüchliche oder ungeeignete Hints werden ignoriert
Ausführung
- Der optimale Plan wird in eine tatsächlich ausführbare Iterator-Struktur (Volcano Iterator) umgewandelt
- Merkmale
- Nicht materialisierende Iteratoren (
non-materializing): Geben Zeilen sofort zurück
- Materialisierende Iteratoren (
materializing): Sammeln erst alle Zeilen und geben sie dann zurück
- Spaltenreferenzen werden vor der Ausführung anhand von Index-Offsets zugeordnet
I/O und Ergebnis-Spooling
- Die Ausführungsergebnisse werden in das MySQL-Protokollformat umgewandelt und an den Client übermittelt
- In manchen Fällen wird zur Optimierung direkt aus der Key-Value-(KV-)Speicherschicht gelesen
- Durch Batch-Verarbeitung und Wiederverwendung von Puffern werden Durchsatz und Speichereffizienz verbessert
Zukunftspläne
- Dolt verwendet grundsätzlich row-based execution auf einem lokalen Server
- Mit AST, scope-basiertem Binding und Join-Exploration über eine Memo-Struktur nutzt Dolt drei Stufen von Intermediate Representation (IR), um optimale Ausführungspläne zu unterstützen
- Über Join Search und Join Costing wird die optimale Join-Strategie bestimmt
- Künftig sind IR-Integration und Optimierungen zur Speicherwiederverwendung geplant, um die Performance zu verbessern
Noch keine Kommentare.