Dieser Beitrag ist eine gekürzte Fassung unseres begutachteten Forschungspapers „Runtime-Extensible Parsers“, das zur Veröffentlichung und Präsentation auf der 2025 Conference on Innovative Data Systems Research (CIDR) angenommen wurde, die vom 19. bis 22. Januar 2025 in Amsterdam stattfindet. Sie können das vollständige Paper lesen, wenn Sie das bevorzugen.
Der Parser ist die DBMS-Komponente, die eine Query im String-Format in eine interne, meist baumförmige Darstellung überführt. Der Parser definiert, welche Queries überhaupt akzeptiert werden. Jede einzelne SQL-Query beginnt ihre Reise in einem Parser. Trotz dieser prominenten Position im Stack wurde sehr wenig Forschung zum Parsen von Queries für Datenmanagementsysteme veröffentlicht. In den letzten Jahrzehnten scheint sich auf dem Thema kaum etwas bewegt zu haben; die Implementierungen stecken weitgehend in sechzig Jahre alten Abstraktionen und Technologien fest.
Das ständige Wachstum der SQL-Spezifikation mit Nischenfeatures (z. B. Unterstützung für Graph-Queries in SQL/PGQ oder XML) sowie der Wunsch, alternative Query-Notationen wie dplyr, Piped SQL, PRQL oder SaneQL zu unterstützen, macht monolithische Parser immer unpraktischer: Im klassischen Design ist die Parser-Konstruktion eine Compile-Time-Aktivität, bei der riesige Grammatikdateien in State-Machine-Übergangstabellen übersetzt und in ein Systembinary gebacken werden. Diese immer im Parser zu haben, kann verschwenderisch sein, besonders bei größenbewussten Binary-Distributionen wie WebAssembly (Wasm).
Viele, wenn nicht die meisten SQL-Systeme nutzen einen statischen Parser, der mit einem YACC-artigen Parser-Toolkit erzeugt wird: Für Open-Source-Systeme wie PostgreSQL und MySQL/MariaDB können wir das leicht bestätigen. Aus den Symbolnamen ihrer Binaries haben wir auch Hinweise gefunden, dass Oracle, SQL Server und IBM Db2 YACC nutzen. Intern nutzen YACC und seine etwas jüngere Variante GNU Bison sowie der von SQLite verwendete Parser-Generator „Lemon“ alle einen LALR(1)-Parser-Generator („single look-ahead left-to-right rightmost derivation“). Dieser Generator übersetzt ein formales kontextfreies Regelwerk in Extended Backus-Naur Form (EBNF) in eine Parser-State-Machine. LALR-Parser sind eine speichereffizientere Spezialisierung von LR(k)-Parsern, zuerst von Knuth beschrieben. Im Effekt nutzen die fortschrittlichsten SQL-Systeme von 2024 Parser-Technologie aus den 1960ern. Angesichts der großen Überholung des Rests der Datenmanagementsysteme sollte man fragen, warum der Parser keine ernsthafte Engineering-Aufmerksamkeit bekommen hat.
Datenbanksysteme werden zu Ökosystemen statt vorgefertigter Monolithen. Viel Innovation in den Communities von PostgreSQL, SQLite und DuckDB kommt jetzt von Erweiterungen – Shared Libraries, die zur Laufzeit ins Datenbanksystem geladen werden, um Features wie Vektorsuche, Geospatial-Unterstützung, Dateisysteme oder Graphverarbeitung zu ergänzen. All das von vornherein zu bündeln wäre schwierig wegen zusätzlicher Binary-Größe und externer Abhängigkeiten. Außerdem werden sie oft unabhängig von ihren Communities gepflegt. Bisher waren Community Extensions – zumindest teilweise wegen der Allgegenwart von YACC-Parsern – daran gehindert, die Syntax zu erweitern. Das gilt auch in anderen Ökosystemen wie Python; das Design von SQL mit seinem starken Fokus auf Syntax statt Funktionsaufrufen macht Erweiterungen aber zu Bürgern zweiter Klasse, die irgendwie um die Beschränkungen des Originalparsers herumarbeiten müssen, z. B. indem sie eigene Ausdrücke in Strings einbetten.
Wir schlagen vor, das Parser-Design von Datenmanagementsystemen neu zu denken, um moderne, erweiterbare Parser zu schaffen, die eine dynamische Konfiguration der akzeptierten Syntax zur Laufzeit erlauben – zum Beispiel Syntaxerweiterungen, neue Statements oder ganz neue Abfragesprachen. Das würde die derzeitigen monolithischen Grammatiken aufbrechen und mehr Kreativität und Flexibilität darin ermöglichen, welche Syntax ein Datenmanagementsystem akzeptiert, sowohl industriell als auch in der Forschung. Erweiterbare Parser erlauben, neue Grammatikfeatures leicht zu integrieren und zu testen, und können die Lücke zwischen SQL-Dialekten schließen, indem die Unterstützung für den Dialekt eines Systems in den Parser eines anderen kommt. Umgekehrt kann es in manchen Fällen wünschenswert sein, die akzeptierte Grammatik zu beschränken, z. B. um die Komplexität von Queries einzuschränken oder strikte Einhaltung des SQL-Standards zu erzwingen.
Die Modernisierung der Parser-Infrastruktur hat weitere Vorteile: Eines der am häufigsten gemeldeten Support-Probleme bei Datenmanagementsystemen sind wenig hilfreiche Syntaxfehler. Manche Systeme geben sich große Mühe, eine sinnvolle Fehlermeldung zu liefern, z. B. this column does not exist, did you mean ..., das ist aber typischerweise auf das Auflösen von Identifikatoren nach dem eigentlichen Parsen beschränkt. YACC-Parser zeigen „Alles-oder-nichts“-Verhalten: Die gesamte Query oder Query-Menge wird entweder vollständig akzeptiert oder gar nicht. Deshalb werden Queries mit tatsächlichen Syntaxfehlern (z. B. SELEXT statt SELECT) von einem DBMS meist hart abgelehnt. MySQL ist zum Beispiel berüchtigt für wenig hilfreiche Fehlermeldungen:
Terminal window
You have an error in your SQL syntax; check the manual that corresponds
to your MySQL server version for the right syntax to use near 'SELEXT'
at line 1.
Parsing Expression Grammar
Parsing Expression Grammar-(PEG-)Parser sind ein modernerer Ansatz zum Parsen. PEG-Parser sind Top-Down-Parser, die aus einer Grammatik effektiv einen Recursive-Descent-Parser erzeugen. Durch die „Packrat“-Memoizationstechnik haben PEG-Parser lineare Zeitkomplexität beim Parsen, auf Kosten eines grammatikabhängigen Extra-Speichers. Der größte Unterschied aus Sicht des Grammatikautors ist der Choice-Operator, bei dem mehrere Syntaxoptionen gematcht werden können. In LALR-Parsern können Optionen mit ähnlicher Syntax Mehrdeutigkeit und Reduce-Konflikte erzeugen. In PEG-Parsern wird immer die erste passende Option gewählt. Deshalb können PEG-Parser per Design nicht mehrdeutig sein.
Wie der Name sagt, besteht eine Parsing Expression Grammar aus einer Menge von Parsing Expressions. Ausdrücke können Referenzen auf andere Regeln oder literale Token-Referenzen enthalten, sowohl als echte Strings als auch als Zeichenklassen ähnlich regulären Ausdrücken. Ausdrücke lassen sich durch Sequenzen, Quantoren, Optionals, Gruppierungen und positiven sowie negativen Look-ahead kombinieren. Jeder Ausdruck kann matchen oder nicht, muss aber bei einem Match einen Teil der Eingabe konsumieren. Ausdrücke können vorausblicken und die restliche Eingabe betrachten, müssen sie aber nicht konsumieren. Die lexikalische Analyse ist typischerweise Teil des PEG-Parsers selbst, was einen separaten Schritt überflüssig macht.
Ein großer Vorteil: PEG-Parser brauchen keinen Kompilierungsschritt, in dem die Grammatik z. B. in einen endlichen Automaten auf Lookup-Tabellen umgewandelt wird. PEG lässt sich mit minimaler Grammatiktransformation direkt auf der Eingabe ausführen, sodass ein Parser zur Laufzeit neu erzeugt werden kann. PEG-Parser gewinnen an Popularität; die Programmiersprache Python ist kürzlich auf einen PEG-Parser umgestiegen.
Ein weiterer großer Vorteil von PEG-Parsern ist Fehlerbehandlung: Das Paper „Syntax Error Recovery in Parsing Expression Grammars“ beschreibt eine praktische Technik, bei der Parser-Regeln mit „Recovery“-Aktionen annotiert werden, die (1) mehr als einen Fehler zeigen und (2) Fehler mit einer sinnvolleren Fehlermeldung annotieren können.
Ein möglicher Nachteil von memoisiertem Packrat-Parsing ist der Speicherbedarf für die Memoization: Die Menge ist proportional zur Eingabegröße, nicht zur Stackgröße. Speicherbeschränkungen haben sich seit der Erfindung von LALR-Parsern vor sechzig Jahren natürlich stark gelockert, und Queries sind typischerweise selbst kein „Big Data“.
Proof-of-Concept-Experimente
Für Experimente zur Parser-Erweiterbarkeit haben wir einen – zugegeben einfachen – experimentellen Prototyp-PEG-Parser für genug SQL implementiert, um alle TPC-H- und TPC-DS-Queries zu parsen. Diese Grammatik ist kompatibel mit der cpp-peglib-Single-Header-C++17-PEG-Ausführungsengine.
cpp-peglib nutzt eine leicht andere Grammatiksyntax, in der / Alternativen bezeichnet. Das Symbol ? zeigt ein optionales Element, * beliebige Wiederholung. Die Sonderregeln Parens() und List() sind Grammatikmakros, die die Grammatik für häufige Elemente vereinfachen. Die Sonderregel %whitespace beschreibt die Tokenisierung.
Unten eine gekürzte Version unserer experimentellen SQL-Grammatik; die Syntaxregeln Expression und Identifier sind der Kürze halber weggelassen:
Alle Experimente liefen auf einem MacBook Pro 2021 mit M1-Max-CPU und 64 GB RAM. Die experimentelle Grammatik und der Code für die Experimente sind auf GitHub verfügbar.
Das Laden der Basisgrammatik aus ihrer Textdarstellung in das cpp-peglib-Grammatikwörterbuch mit symbolischen Regelrepräsentationen dauert 3 ms. Sollte diese Verzögerung zum Problem werden, erlaubt die Bibliothek auch, Regeln programmatisch statt als Strings zu definieren. Es wäre geradlinig, die Grammatikdatei im YACC-Stil vorab in Quellcode für die Kompilierung zu übersetzen. Das ist etwas kontraintuitiv, würde aber die Zeit verkürzen, den initialen, unveränderten Parser zu initialisieren. Der Unterschied zählt für manche Anwendungen von z. B. DuckDB, in denen die Datenbankinstanz nur wenige Millisekunden lebt.
Beim eigentlichen Parsen parst YACC TPC-H Query 1 in ca. 0,03 ms, cpp-peglib braucht ca. 0,3 ms – etwa das Zehnfache. Um die Parsing-Performance weiter zu belasten, haben wir alle TPC-H- und TPC-DS-Queries sechsmal wiederholt und so ein 36.840-zeiliges SQL-Skript von ca. 1 MB erzeugt. Eine aktuelle Studie hat ergeben, dass das 99-Perzentil der Lesequeries im Amazon-Redshift-Cloud-Data-Warehouse kleiner als 16,5 kB ist.
Postgres braucht im Schnitt 24 ms, um diese Datei mit YACC zu parsen. Diese Zeit umfasst die Ausführung von Grammatikaktionen, die den Parse-Baum von Postgres erzeugen. cpp-peglib braucht im Schnitt 266 ms, um die Testdatei zu parsen. Unser experimenteller Parser hat aber noch keine Grammatikaktionen definiert. Simuliert man Aktionen durch Standard-AST-Aktionen für jede Regel, steigt die Parse-Zeit auf 339 ms. Die AST-Erzeugung ist teurer als nötig, weil für jede passende Regel ein Knoten entsteht, auch wenn die Grammatik keine semantische Bedeutung hat.
Insgesamt beobachten wir etwa eine 10-fache Verlangsamung der Parsing-Performance mit dem cpp-peglib-Parser. Die absolute Dauer beider Prozesse ist aber immer noch winzig; zumindest für analytische Queries ist eine Parse-Zeit unter einer Millisekunde mehr als akzeptabel, weil das Parsen nur einen winzigen Bruchteil der gesamten Query-Verarbeitungszeit ausmacht. Außerdem gibt es in den experimentellen Parsern, die wir mit einer Off-the-Shelf-PEG-Bibliothek erzeugt haben, noch reichlich Optimierungsmöglichkeiten. Die Bibliothek nutzt zum Beispiel stark rekursive Funktionsaufrufe, die sich z. B. durch eine Schleifenabstraktion optimieren lassen.
Im Folgenden zeigen wir Experimente zur Erweiterung des Prototyp-Parsers um neue Statements, ganz neue Syntax und bessere Fehlermeldungen.
Es ist bereits möglich, DuckDBs Parser zu ersetzen, indem man einen alternativen Parser bereitstellt.
Mehrere Community Extensions wie duckpgq, prql und psql nutzen diesen Ansatz.
Beim Parsen eines Query-Strings versucht DuckDB zuerst den Standardparser.
Schlägt das fehl, wechselt es als Failover zu den Extension-Parsern.
Diese Erweiterungen können den Parser also nicht einfach um ein paar Extra-Regeln erweitern – sie implementieren die vollständige Grammatik ihrer Zielsprache.
Das Statement UNPIVOT hinzufügen
Angenommen, wir wollen ein neues Top-Level-Statement UNPIVOT hinzufügen, das Spalten in Zeilen verwandelt. UNPIVOT soll auf derselben Ebene wie z. B. SELECT funktionieren, etwa um eine Tabelle t1 auf einer bestimmten Spaltenliste oder allen Spalten (*) zu unpivotieren:
UNPIVOT t1 ON (c1, c2, c3);
UNPIVOT t1 ON (*);
Klar ist, dass wir den Parser irgendwie ändern müssten, um diese neue Syntax zu erlauben. Mit einem YACC-Parser hieße das: Grammatik ändern, Parser-Generator neu ausführen, auf das Ausbleiben von Shift-Reduce-Konflikten hoffen und dann das eigentliche Datenbanksystem neu kompilieren. Das ist zur Laufzeit nicht praktikabel – genau dann, wenn Erweiterungen geladen werden, idealerweise innerhalb von Millisekunden.
Um UNPIVOT hinzuzufügen, müssen wir eine Grammatikregel definieren und dann SingleStmt ändern, damit das Statement in einer globalen Folge von SQL-Statements erlaubt ist. Das zeigt das Folgende. Wir definieren die neue Grammatikregel UnpivotStatement, indem wir sie ins Wörterbuch aufnehmen, und ändern dann den Eintrag SingleStmt, damit auch das neue Statement erlaubt ist.
UnpivotStatement <- 'UNPIVOT' Identifier
'ON' Parens(List(Identifier) / '*')
SingleStmt <- SelectStatement / UnpivotStatement
Beachten Sie, dass wir andere Maschinerie der Grammatik wiederverwenden, etwa die Regel Identifier sowie die Makros Parens() und List() für die ON-Klausel. Der Rest des Grammatikwörterbuchs bleibt unverändert. Nach der Änderung kann der Parser in weiteren 3 ms neu initialisiert werden. Die Parser-Ausführungszeit blieb unbeeinflusst.
SELECT um GRAPH_TABLE erweitern
Angenommen, wir wollen die SELECT-Syntax um Unterstützung für SQL/PGQ-Graph-Matching-Muster erweitern. Unten eine Beispielquery in SQL/PGQ, die Universitätsname und Jahr für alle Studierenden namens Bob findet:
Diese neue Syntax fügt die Klausel GRAPH_TABLE und die Pattern-Matching-Domain-Specific Language (DSL) darin hinzu. Um diese Syntax zur Laufzeit in einen SQL-Parser zu bringen, müssen wir die Grammatik des SELECT-Statements selbst ändern. Mit PEG ist das recht geradlinig. Wir ersetzen die Regel, die die FROM-Klausel beschreibt, sodass sie auch eine Subgrammatik akzeptiert, die beim Schlüsselwort GRAPH_TABLE beginnt, gefolgt von Klammern. Weil der Parser keine State Machine erzeugen muss, können wir die neue Syntax sofort akzeptieren.
Unten eine kleine Menge Grammatikregeln, die ausreichen, um unseren experimentellen Parser um die SQL/PGQ-Klausel GRAPH_TABLE und die enthaltenen Property-Graph-Muster zu erweitern. Mit dieser Ergänzung kann der Parser die Query oben parsen. Parser-Konstruktion und -Ausführungszeit blieben unbeeinflusst.
Name <- (Identifier? ':' Identifier) / Identifier
Edge <- ('-' / '<-') '[' Name ']' ('->' / '-')
Pattern <- Parens(Name WhereClause?) Edge
Parens(Name WhereClause?)
PropertyGraphReference <- 'GRAPH_TABLE'i '('
Identifier ','
'MATCH'i List(Pattern)
'COLUMNS'i Parens(List(ColumnReference))
')' Identifier?
TableReference <-
PropertyGraphReference / ...
dplyr, die „Grammar of Data Manipulation“, ist die De-facto-Standard-Datentransformationssprache in der R-Umgebung für statistisches Rechnen. Die Sprache nutzt Funktionsaufrufe und einen speziellen Verkettungsoperator (%>%), um Operatoren zu kombinieren. Unten eine Beispiel-dplyr-Query:
df%>%
group_by(species) %>%
summarise(
n=n(),
mass=mean(mass,na.rm=TRUE)
) %>%
filter(n>1,mass>50)
Für Unvertraute mit dplyr: Die Query entspricht dieser SQL-Query:
SELECT*FROM (
SELECTcount(*) AS n, AVG(mass) AS mass
FROM df
GROUP BY species)
WHERE n >1AND mass >50;
Mit einem erweiterbaren Parser ist es machbar, Unterstützung für ganz neue Abfragesprachen wie dplyr in einen SQL-Parser zu bringen. Unten ein vereinfachtes Grammatik-Snippet, das unseren SQL-Parser in die Lage versetzt, das dplyr-Beispiel oben zu akzeptieren.
Wichtig: Der Rest des experimentellen SQL-Parsers funktioniert weiter, d. h. die dplyr-Syntax funktioniert zusätzlich. Parser-Konstruktion und -Ausführungszeit blieben wieder unbeeinflusst.
Bessere Fehlermeldungen
Wie oben erwähnt, können PEG-Parser eleganter bessere Fehlermeldungen erzeugen. Ein häufiger Anfängerfehler in SQL ist, die Reihenfolge der Schlüsselwörter zu vertauschen: ORDER BY muss nach GROUP BY kommen. Angenommen, ein unerfahrener Nutzer tippt folgende Query:
SELECT customer, SUM(sales)
FROM revenue
ORDER BY customer
GROUP BY customer;
Standardmäßig melden sowohl der YACC- als auch der PEG-Parser eine ähnliche Fehlermeldung über ein unexpected 'GROUP' keyword mit Byte-Position. Mit einem PEG-Parser können wir aber eine „Recovery“-Syntaxregel definieren, die eine nützliche Fehlermeldung erzeugt. Wir ändern die OrderByClause unserer experimentellen Grammatik so:
{ error_message "GROUP BY must precede ORDER BY" }
Hier nutzen wir das Konstrukt %recover, um eine falsch platzierte GROUP BY-Klausel zu matchen – unter Wiederverwendung der Originaldefinition – und dann eine eigene Fehlermeldung auszulösen, die dem Nutzer rät, wie die Query zu korrigieren ist. Und tatsächlich: Parsen wir das falsche SQL-Beispiel, gibt der Parser die eigene Meldung aus.
Fazit und Ausblick
In diesem Beitrag haben wir vorgeschlagen, die uralte Kunst des SQL-Parsens mit moderneren Parser-Generatoren wie PEG zu modernisieren. Wir haben gezeigt, wie sich ein Parser zur Laufzeit mit minimalen Kosten ohne Rekompilierung erweitern lässt. In unseren Experimenten haben wir gezeigt, wie kleine Grammatikanpassungen die akzeptierte Syntax grundlegend erweitern und ändern können.
Ein offensichtlicher nächster Schritt ist, den beobachteten Performance-Nachteil unseres Prototyps anzugehen. Mit effizienteren Implementierungstechniken sollte sich die Lücke in der Parsing-Performance zwischen YACC-basierten LALR-Parsern und einem dynamischen PEG-Parser verkleinern lassen. Ein weiterer Schritt sind Detailfragen der Implementierung: Die Ladeordnung von Parser-Erweiterungen sollte idealerweise die finale Grammatik nicht beeinflussen. Außerdem können Parser-Aktionen im Prinzip beliebigen Code ausführen, es können aber Beschränkungen für Rückgabetypen und Eingabebehandlung nötig sein.
Wir planen, DuckDBs Parser, der als Fork des Postgres-YACC-Parsers begann, in naher Zukunft auf einen PEG-Parser umzustellen. Als ersten Schritt haben wir ein Experiment durchgeführt und festgestellt, dass sich die aktuelle Postgres-YACC-Grammatik mit PEG interpretieren lässt. Das sollte den Übergang stark vereinfachen, weil dieselbe Grammatik in beiden Parsing-Frameworks akzeptiert wird.
