Überblick über die DuckDB-Interna
Tipp Eine ausführliche Erklärung der DuckDB-Interna finden Sie im Library-Eintrag Design and Implementation of DuckDB Internals („DiDi“).
Auf dieser Seite finden Sie eine kurze Beschreibung der Interna der DuckDB-Engine.
Parser
Der Parser wandelt eine Abfragezeichenkette in die folgenden Tokens um:
Der Parser kennt weder den Katalog noch andere Aspekte der Datenbank. Er wirft keine Fehler, wenn Tabellen nicht existieren, und löst noch keine Spaltentypen auf. Er wandelt lediglich eine Abfragezeichenkette in eine Menge der angegebenen Tokens um.
ParsedExpression
Die ParsedExpression repräsentiert einen Ausdruck innerhalb einer SQL-Anweisung. Das kann z. B. eine Referenz auf eine Spalte, ein Additionsoperator oder ein konstanter Wert sein. Der Typ der ParsedExpression gibt an, was sie darstellt; ein Vergleich wird beispielsweise als ComparisonExpression dargestellt.
ParsedExpressions haben keine Typen, außer bei Knoten mit expliziten Typen wie CAST-Anweisungen. Die Typen der Ausdrücke werden im Binder aufgelöst, nicht im Parser.
TableRef
Der TableRef repräsentiert eine beliebige Tabellenquelle. Das kann eine Referenz auf eine Basistabelle sein, aber auch ein Join, eine tabellenerzeugende Funktion oder eine Unterabfrage.
QueryNode
Der QueryNode repräsentiert entweder (1) eine SELECT-Anweisung oder (2) eine Mengenoperation (also UNION, INTERSECT oder DIFFERENCE).
SQL Statement
Das SQLStatement repräsentiert eine vollständige SQL-Anweisung. Der Typ des SQL Statement gibt an, um welche Art von Anweisung es sich handelt (z. B. steht StatementType::SELECT für eine SELECT-Anweisung). Eine einzelne SQL-Zeichenkette kann in mehrere SQL-Anweisungen umgewandelt werden, wenn die ursprüngliche Abfragezeichenkette mehrere Abfragen enthält.
Binder
Der Binder wandelt alle Knoten in ihre gebundenen (bound) Äquivalente um. In der Binder-Phase:
- Tabellen und Spalten werden über den Katalog aufgelöst
- Typen werden aufgelöst
- Aggregat-/Fensterfunktionen werden extrahiert
Die folgenden Umwandlungen finden statt:
- SQLStatement →
BoundStatement - QueryNode →
BoundQueryNode - TableRef →
BoundTableRef - ParsedExpression →
Expression
Logischer Planner
Der logische Planner erzeugt LogicalOperator-Knoten aus den gebundenen Statements. In dieser Phase wird der eigentliche logische Abfragebaum erstellt.
Optimizer
Nachdem der logische Planner den logischen Abfragebaum erstellt hat, werden die Optimizer über diesen Abfragebaum ausgeführt, um einen optimierten Abfrageplan zu erzeugen. Folgende Query-Optimizer werden ausgeführt:
- Expression Rewriter: Vereinfacht Ausdrücke, führt Constant Folding durch
- Filter Pushdown: Schiebt Filter im Abfrageplan nach unten und dupliziert Filter über Äquivalenzmengen. Beschneidet außerdem Teilbäume, die garantiert leer sind (weil Filter statisch zu false ausgewertet werden).
- Join Order Optimizer: Ordnet Joins mittels dynamischer Programmierung neu. Konkret wird der Algorithmus
DPhypaus dem Paper Dynamic Programming Strikes Back verwendet. - Common Sub Expressions: Extrahiert gemeinsame Teilausdrücke aus Projektions- und Filterknoten, um unnötige doppelte Ausführung zu vermeiden.
- In Clause Rewriter: Schreibt große statische IN-Klauseln in einen MARK-Join oder INNER-Join um.
Column Binding Resolver
Der Column Binding Resolver wandelt logische BoundColumnRefExpression-Knoten, die auf eine Spalte einer bestimmten Tabelle verweisen, in BoundReferenceExpression-Knoten um, die auf einen bestimmten Index in den DataChunks verweisen, die in der Execution Engine weitergereicht werden.
Generator für physische Pläne
Der Generator für physische Pläne wandelt den resultierenden logischen Operatorbaum in einen PhysicalOperator-Baum um.
Ausführung
In der Ausführungsphase werden die physischen Operatoren ausgeführt, um das Abfrageergebnis zu erzeugen.
DuckDB verwendet ein push-basiertes vektorisiertes Modell, bei dem DataChunks durch den Operatorbaum geschoben werden.
Weitere Informationen finden Sie im Vortrag Push-Based Execution in DuckDB.