70-mal schnellerer SQL-Parser, fast ohne Blick in den Code gebaut

• PostHog schrieb seinen ANTLR-basierten C++-SQL-Parser in mehreren Claude-Code-Sitzungen neu und erzeugte dabei einen 16K-Zeilen-Rust-Parser, 5K Zeilen Werkzeuge und tausende Zeilen Tests; auf einem Laptop wurde dadurch eine etwa 70-fache Beschleunigung erreicht
• Die neue Implementierung basiert auf einem prädiktiven Recursive-Descent-Parser mit einem Pratt-Ausdruckskern und setzt begrenztes Lookahead sowie spekulatives Backtracking nur dort ein, wo es nötig ist, wodurch die Kosten von ANTLRs allgemeiner Graph-Traversierung entfallen
• Mit dem bestehenden C++-Parser als Referenzimplementierung wurden Property-based Tests, anonymisierte echte Queries, Regressionstests, Code-Coverage-gesteuerte Generierung und ShrinkRay-Minimierung kombiniert, um Abweichungen zwischen beiden Parsern iterativ zu beseitigen
• Im Shadow Mode in Produktion unterschieden sich die Parsergebnisse über Millionen von Ausführungen hinweg kein einziges Mal vom bisherigen Parser; der Traffic wurde innerhalb weniger Stunden umgestellt, mit einer durchschnittlichen 454-fachen Beschleunigung in Produktion
• Der Ansatz, Parsergeneratoren für Grammatik und Referenzimplementierung zu nutzen und die Äquivalenz per Fuzzing mit einem LLM zu verifizieren, zeigt das Potenzial, monatelange Entwicklung hochperformanter Parser mit Spezialwissen auf wenige Tage zu verkürzen

---

Warum PostHog einen SQL-Parser braucht

• PostHog wandelt eingegebenes SQL in rohes ClickHouse-SQL um, damit Nutzer direkt per SQL auf Daten zugreifen können
  • Es stellt eine logische Datensicht bereit, die unabhängig vom physischen Layout der Datenbank ist
  • Es schützt bestehende Queries davor, bei Änderungen an der Datenbankebene zu brechen
  • Es fügt dem Transformationsprozess Performance-Optimierungen und Zugriffskontrolle hinzu
• Die meisten PostHog-Werkzeuge wie Produktanalyse, Session Replay und Error Tracking schicken ebenfalls in SQL geschriebene Queries durch denselben Transformationsprozess
• Um SQL zu transformieren, muss es zuerst in einen abstrakten Syntaxbaum (AST) umgewandelt werden, der anschließend wieder in ClickHouse-SQL transformiert wird
• Der Parser ist die erste Komponente, die nicht vertrauenswürdige Query-Eingaben verarbeitet
  • Auch die nachgelagerte Zugriffskontrolle und Optimierung hängen vollständig von dem vom Parser erzeugten Baum ab

Struktur und Kosten des bisherigen ANTLR-Parsers

• Vor AI Coding war es sehr schwierig, Parser direkt zu schreiben und zu pflegen, daher nutzte PostHog den Open-Source-Parsergenerator ANTLR
• Wenn die Grammatik in einer deklarativen .g4-Datei bereitgestellt wird, erzeugt ANTLR den Großteil des Parsercodes
• Der bisherige Parser wurde ebenfalls bereits in C++ erzeugt, daher ist der Performance-Gewinn diesmal nicht einfach das Ergebnis eines Sprachwechsels zu Rust
• ANTLR ist leistungsfähig und flexibel, benötigt aber bei der Verarbeitung jedes Tokens mehr Arbeit
  • Es kompiliert die Grammatik in eine Augmented Transition Network (ATN), also in eine Form nahe einem nichtdeterministischen endlichen Automaten (NFA) mit Stack
  • Zur Laufzeit traversiert ein allgemeiner Interpreter diesen Graphen
  • Statt direkt geschriebener Funktionen wie parseExpression() gibt es zusätzliche Abstraktions- und Indirektionsschichten
• Da auch beliebiges dynamisches Lookahead unterstützt wird, simuliert es bei mehreren Alternativen alle Interpretationen gleichzeitig, bis nur noch eine gültig bleibt
• Selbst ein gut optimiertes ANTLR kann mit seiner Struktur als Graph-Traversierungs-Interpreter nur schwer schneller sein als ein direkt implementierter Recursive-Descent-Parser

Zwei Parser-Implementierungen parallel erprobt

• Mit AI ist es einfacher geworden, direkt implementierte Parser zu schreiben und zu pflegen, doch es reichte nicht aus, Claude einfach um einen fehlerfreien Rust-Parser zu bitten
  • Claude machte viele Fehler
  • Es stellte die Machbarkeit der Neuschreibung wiederholt infrage
  • Nach jeder Coding-Runde neigte es dazu, die Arbeit als abgeschlossen zu betrachten
• In mehreren lang laufenden Claude-Code-Sitzungen wurden zwei Ansätze parallel getestet
  • Der performanceorientierte Ansatz nutzte einen Recursive-Descent-Parser mit Pratt-Ausdrucksschleife und ergänzte Lookahead sowie Backtracking nur dort, wo es nötig war
  • Der erfolgsorientierte Ansatz folgte dem Verhalten von ANTLR so eng wie möglich, setzte Übergänge aber als expliziten Code statt als allgemeine Graph-Traversierung um
• Beide Ansätze funktionierten am Ende auf ähnlichem Niveau, aber es dauerte mehrere Tage, das festzustellen
• Das Ziel war vollständige Übereinstimmung mit dem bestehenden C++-Parser bei allen realistischen Queries und ein möglichst ähnliches Verhalten auch bei künstlichen Queries
  • Auch ungewöhnlich wirkendes, aber gültiges SQL wie SELECT SELECT FROM FROM WHERE WHERE AND AND gehörte zum Testumfang
• Der bestehende C++-Parser diente als Referenzimplementierung (Orakel); SQLs mit abweichendem Verhalten wurden gesucht, der neue Parser angepasst und anschließend erneut verglichen

Abweichungen mit Property-based Tests erzeugen

• Zunächst wurden die im Verlauf der Entwicklung des bisherigen Parsers angesammelten Regressionstests bestanden, danach wurden neue Abweichungen systematisch erzeugt
• In Property-based Tests (PBT) mit Hypothesis wurde die zu prüfende Eigenschaft als „der neue Parser stimmt mit der Referenzimplementierung überein“ definiert
  • Die Eingaben sind SQL-Queries
  • Hypothesis sucht nach Queries, bei denen die Ergebnisse der beiden Parser nicht übereinstimmen
• Um interessante SQLs zu erzeugen, wurde zusammen mit Claude ein Werkzeug gebaut, das aus der ANTLR-Grammatikdatei einen SQL-Generator erzeugt
  • Dafür wurde auch ein separater Parser geschrieben, der die .g4-Datei selbst einliest
  • Anschließend wurden Varianten wie Token-Tausch oder zusätzliche Klammern in die Generierung aufgenommen

Prompt-Gestaltung gegen fragile Fixes

• PBT erzeugte zuverlässig neue Testfälle, doch Claude wiederholte immer wieder fragile Fixes: Es reparierte einen Einzelfall mit einem Token Lookahead und stellte später fest, dass zwei Tokens nötig gewesen wären
• Da das Kontextfenster oft voll lief und komprimiert wurde, war es möglich, dass Fixes vorgenommen wurden, ohne sich an die tatsächliche Grammatik oder das Verhalten des Referenzparsers zu erinnern
• Dieses Problem wurde entschärft, indem vor jedem Fix einer Abweichung explizit angewiesen wurde, sowohl die relevante Grammatikdatei als auch den C++-Quellcode in den Kontext zu laden

CPU und Claude dauerhaft gemeinsam auslasten

• PBT lief im Hintergrund weiter, schrieb Fehlfälle in Dateien, und die Werkzeuge wurden so aufgebaut, dass Claude diese Fälle abholte, wenn gerade nichts anderes anstand
• Fehlfälle wurden aus mehreren Quellen gesammelt
  • bestehende Regressionstests
  • durch PBT erzeugtes SQL
  • anonymisierte Queries aus Produktions-Logs
  • Fälle, die durch die Bitte an Hintergrund-Agenten entstanden, „wirklich tief über Randfälle nachzudenken“
• Die beiden parallel entwickelten Parser teilten sich eine Regressionstest-Sammlung, sodass in einer Sitzung entdeckte Fehler sofort auch in der anderen reflektiert wurden
• Hypothesis kann selbst erzeugte Fälle auf eine minimale Reproduktion schrumpfen, lässt sich aber nicht auf externes SQL anwenden; dafür wurde ShrinkRay verwendet
• Später kam zusätzlich Code-Coverage-gesteuerte Testgenerierung hinzu
  • Nicht ausgeführte SQL-Konstrukte wurden erkannt und die Generierung so verzerrt, dass diese Strukturen häufiger entstanden
  • Für 100 % Genauigkeit auf dem Produktions-Query-Set war das nicht zwingend nötig, half aber beim Finden sehr subtiler Fälle

Automatischer Kreislauf zum Finden und Beheben von Fehlern

• Die finale Entwicklungsschleife wiederholte autonom die folgenden Schritte
  1. Neue Fehler durch PBT, reale Query-Sammlungen, Regressionstests und die Suche nach Randfällen erzeugen
  2. Fehler minimieren und zu einer ständig wachsenden Liste von Regressionstests hinzufügen
  3. Allgemeine Lösungen bevorzugen und dabei prüfen, wie Grammatik und C++-Referenzimplementierung den Fall behandeln
  4. Nach dem Fix eine für Menschen lesbare Zusammenfassung in einem Absatz ausgeben
  5. Die vollständige Regressionstest-Suite ausführen und prüfen, ob alle Fälle bestehen
  6. Den gleichen Prozess erneut autonom ausführen
• Da der neue Parser deutlich schneller war, konnte er in Produktion zusammen mit dem bisherigen C++-Parser im Shadow Mode laufen und Ergebnisabweichungen melden

Produktionsvalidierung und Umstellung

• Beim Vorabvergleich anhand von Produktions-Query-Logs wurden etwa 50.000 Queries getestet
• Im Shadow Mode wurden Millionen von Parsing-Vorgängen schnell ausgeführt, ohne auch nur eine einzige Abweichung zum bisherigen Parser
• Ursprünglich war geplant, den Shadow Mode mehrere Tage laufen zu lassen, doch die Ergebnisse waren stark genug, um den Produktions-Traffic bereits nach wenigen Stunden auf den neuen Parser umzustellen
• Nach der Umstellung blieb ein 0,1-%-Reverse-Shadowing erhalten, bei dem weiterhin gegen den bisherigen Parser gegengeprüft wird
• Der neue Parser gibt nicht nur denselben AST aus, sondern auch dieselben Source-Location-Informationen wie der C++-ANTLR-Parser

70-fach auf dem Laptop, 454-fach in Produktion

• In Benchmarks auf dem Laptop war der neue Parser etwa 70-mal schneller als der bisherige Parser
• Bei Produktions-Queries lag der Durchschnitt bei einer 454-fachen Beschleunigung
  • In Produktion werden meist längere SQLs verarbeitet, die den Parser-Cache nicht treffen, weshalb der Abstand größer ist als auf dem Laptop
• Das Endergebnis besteht aus rund 16K Zeilen Parsercode, etwa 5K Zeilen Werkzeugen und tausenden Zeilen Tests
• Bei realistischen Queries ist das Verhalten äquivalent zum bisherigen Parser; Unterschiede beschränken sich auf eine winzige Zahl künstlich konstruierter Queries

Endgültige Parser-Struktur und veränderte Entwicklungsweise

• Der finale Parser ist wie folgt aufgebaut
  • Der Großteil ist als prädiktiver Recursive-Descent-Parser implementiert
  • Für die Ausdrucksverarbeitung kommt ein Pratt-Parser-Kern zum Einsatz
  • Der Basiscursor ist LL(2); nur an bestimmten Stellen wird der Bereich durch begrenzte, nicht konsumierende Lookahead-Suche erweitert
  • Nur bei wenigen zwingend nötigen Entscheidungen wird lokales spekulatives Backtracking mit geordneten Alternativen eingesetzt
• Der gesamte Parser wurde im Mai 2026 von Claude Opus 4.7 in Rust geschrieben, ohne dass der Code manuell von Hand verfasst wurde
• Die PBT-Konfiguration, die Eingaben aus der Grammatik erzeugt und die Generierung über Code Coverage steuert, entspricht eher dem modernen Stand des Parser-Fuzzings und unterscheidet sich von einfachem „Vibe Coding“
• Eine Aufgabe, die selbst für Entwickler mit speziellem Parserwissen Monate dauern könnte, wurde in wenigen Tagen erledigt
• Künftig könnte es üblich werden, dass Parsergeneratoren wie ANTLR eine Referenzimplementierung liefern und LLMs mit PBT und Fuzzing auf Äquivalenz hinarbeiten, während sie schnellere direkt implementierte Parser schreiben