コードをほとんど見ずに作った、70倍高速なSQLパーサー

• PostHogはANTLRベースのC++ SQLパーサーを複数のClaude Codeセッションで書き直し、16K行のRustパーサー、5K行のツール群、数千行のテストを作成し、ノートPC環境で約70倍の高速化を達成
• 新しい実装は予測型再帰下降パーサーとPratt式コアを中心に据え、必要な箇所にのみ限定的な先読みと推測的バックトラッキングを適用することで、ANTLRの汎用グラフ走査コストを排除
• 既存のC++パーサーを基準実装として置き、プロパティベーステスト、匿名化した実運用クエリ、回帰テスト、コードカバレッジ誘導生成、ShrinkRayによる縮小を組み合わせて、2つのパーサーの不一致を繰り返し解消
• 本番シャドーモードで数百万回のパース結果が既存パーサーと一度も異ならず、数時間でトラフィックを切り替え、本番平均454倍の高速化を記録
• パーサージェネレーターが文法と基準実装を提供し、LLMがファジングで同等性を検証するやり方は、専門知識が必要だった数か月規模の高性能パーサー開発を数日に短縮できる可能性を示す

---

PostHogにSQLパーサーが必要な理由

• PostHogはユーザーがSQLでデータに直接アクセスできるよう、入力SQLを生のClickHouse SQLに変換する
  • データベースの物理配置に依存しない論理データビューを提供
  • データベース層を変更しても既存クエリが壊れないよう保護
  • 変換過程に性能最適化とアクセス制御を追加
• プロダクト分析、セッションリプレイ、エラートラッキングなど、PostHogの大半のツールもSQLで書かれたクエリを同じ変換過程に通す
• SQLを変換するには、まず抽象構文木(AST) に変換する必要があり、この木が再びClickHouse SQLへ変換される
• パーサーは信頼できないクエリ入力を最初に処理するコンポーネント
  • その後のアクセス制御や最適化もすべて、パーサーが作った木に依存する

既存ANTLRパーサーの構造とコスト

• AIコーディング以前はパーサーを直接書いて保守するのが非常に難しかったため、PostHogはオープンソースのパーサージェネレーターANTLRを使用していた
• 文法を宣言的な.g4ファイルで与えると、ANTLRがパーサーコードの大半を生成する
• 既存パーサーもすでにC++で生成されていたため、今回の性能向上は単に実装言語をRustに変えた結果ではない
• ANTLRは強力で柔軟だが、各トークンを処理するたびにより多くの作業が必要
  • 文法を拡張遷移ネットワーク(ATN)、つまりスタックを含む非決定性有限オートマトン(NFA)に近い形へコンパイルする
  • 実行時には汎用インタープリターがこのグラフを走査する
  • parseExpression() のような手書き関数の代わりに、追加の抽象化と間接呼び出しの層を経由する
• 任意の動的先読みもサポートするため、候補が複数あると、1つだけが有効に残るまであらゆる解釈を同時にシミュレートする
• 十分に最適化されたANTLRでも、グラフ走査インタープリターという構造上、直接実装した再帰下降パーサーより速くなるのは難しい

2種類のパーサー実装を並行実験

• AIを使えば手書きパーサーの作成と保守は容易になるが、Claudeに誤りのないRustパーサーを頼むだけでは不十分だった
  • Claudeは多くのミスをした
  • 書き直し自体の実現可能性を何度も疑った
  • 各コーディングラウンドの終わりに作業を完了させようとする傾向があった
• 複数の長時間実行Claude Codeセッションで、2つのアプローチを並行して試した
  • 性能重視アプローチでは、再帰下降パーサーとPratt式ループを使い、必要な箇所にだけ先読みとバックトラッキングを追加
  • 成功確率重視アプローチでは、ANTLRの動作をできる限り踏襲しつつ、汎用グラフ走査の代わりに遷移を明示的なコードで実装
• 2つのアプローチは最終的に似たレベルで動作したが、それを確認するまでに数日かかった
• 目標は、現実的なすべてのクエリで既存のC++パーサーと完全一致し、人工的なクエリでもできるだけ近い結果を出すことだった
  • SELECT SELECT FROM FROM WHERE WHERE AND AND のように異常に見えても有効なSQLもテスト対象に含めた
• 既存のC++パーサーを基準実装(オラクル) とし、異なる扱いになるSQLを見つけ、新しいパーサーを修正して再比較するテスト駆動方式で開発した

プロパティベーステストで不一致を生成

• 既存パーサー開発の過程で蓄積された回帰テストをまず通したうえで、新たな不一致を体系的に生成した
• Hypothesisを使ったプロパティベーステスト(PBT) では、検証プロパティを「新しいパーサーが基準実装と一致すること」と定義
  • 入力値はSQLクエリ
  • Hypothesisが2つのパーサーの結果が一致しないクエリを探索する
• 興味深いSQLを生成するため、ANTLR文法ファイルからSQLジェネレーターをコード生成するツールをClaudeと一緒に作成
  • .g4 ファイル自体を読む別のパーサーも書いた
  • その後、トークン入れ替えや括弧追加のような変形も生成段階に組み込んだ

脆い修正を防ぐプロンプト構成

• PBTは新しいテストを安定して作れたが、Claudeは1トークン先読みで特定ケースを直した後、あとで2トークン先読みが必要だと判明するような脆い修正を繰り返した
• コンテキストウィンドウが頻繁に埋まって圧縮され、実際の文法や基準パーサーの動作を忘れた状態で修正していた可能性があった
• 各不一致を修正するコードを書く直前に、関連する文法ファイルとC++ソースコードを両方コンテキストへ読み込むよう指示し、この問題を緩和した

CPUとClaudeを同時に回し続ける

• PBTがバックグラウンドで動き続けて失敗事例をファイルに記録し、Claudeはほかの作業がないときにその事例を取得するようツールを構成
• 失敗事例は複数の経路から収集した
  • 既存の回帰テスト
  • PBTで生成したSQL
  • 本番クエリログから取得した匿名化クエリ
  • バックグラウンドエージェントに「境界ケースを本当に深く考えろ」と依頼して作った事例
• 並行開発した2つのパーサーは回帰テスト群を共有し、あるセッションで見つかった失敗が別セッションにも即座に反映されるようにした
• Hypothesisは自前で生成した事例を最小再現へ縮小できるが、外部SQLには適用できないため、それらの事例にはShrinkRayを使用
• その後、コードカバレッジ誘導テスト生成も追加
  • まだ実行されていないSQL構成要素を検出し、その構造がより頻繁に生成されるよう偏らせた
  • 本番クエリ集合で100%正確性に到達するために必須ではなかったが、非常に微妙なケースを見つけるのに役立った

失敗を見つけて直す自動反復プロセス

• 最終的な開発ループは、次の手順を自律的に繰り返した
  1. PBT、実クエリ集合、回帰テスト、境界ケース探索で新しい失敗を生成
  2. 失敗を縮小し、拡張し続ける回帰テスト一覧に追加
  3. 一般的な解決策を優先しつつ、文法とC++基準実装の扱い方を確認
  4. 修正後、人が読める1段落の要約を出力
  5. 全回帰テストを実行してすべての事例が通るか確認
  6. 同じ過程を再び自律実行
• 新しいパーサーははるかに高速だったため、本番環境では既存のC++パーサーと並べてシャドーモードで実行し、結果差分を報告できた

本番検証と切り替え

• 本番クエリログを使った事前比較では約5万件のクエリをテスト
• シャドーモードでは数百万回のパースを高速に実行し、既存パーサーとの不一致は1件も発生しなかった
• 当初は数日間シャドーモードを維持する予定だったが、結果が十分に強力だったため、数時間で本番トラフィックを新しいパーサーへ切り替えた
• 切り替え後は、既存パーサーでも再比較する0.1%逆方向シャドーを維持
• 新しいパーサーはASTだけでなく、ソース位置情報までC++ ANTLRパーサーと同一に出力する

ノートPCで70倍、本番で454倍

• ノートPCベンチマークでは既存パーサーより約70倍高速を記録
• 本番クエリでは平均454倍高速化
  • 本番ではパーサーキャッシュにヒットしない、より長いSQLを主に処理するため、ノートPCより性能差が大きくなった
• 最終成果物は、パーサーコード約16K行、ツール約5K行、テスト数千行で構成
• 現実的なクエリでは既存パーサーと同等で、差異は人工的に構成したごく少数のクエリに限られる

最終パーサー構造と変わった開発スタイル

• 最終パーサーは次の構造で構成される
  • 大部分を予測型再帰下降パーサーとして実装
  • 式処理にはPrattパーサーコアを使用
  • 基本カーソルはLL(2)で、特定箇所でのみ入力を消費しない限定的先読み探索によって範囲を広げる
  • 本当に必要な少数の判断にのみ、順序付き選択ベースの局所的な推測バックトラッキングを適用
• パーサー全体は2026年5月のClaude Opus 4.7がRustで記述し、コードを直接手書きすることはなかった
• 文法から入力を生成し、コードカバレッジで生成を誘導するPBT構成は、単なる「バイブコーディング」とは異なり、パーサーファジングの最新手法に近い
• 特定のパーサー知識を持つ開発者でも数か月かかりうる作業を、数日で実施した
• 今後はANTLRのようなパーサージェネレーターが基準実装を提供し、LLMがPBTとファジングで同等性を合わせ込みながら、より高速な手書きパーサーを作る方式が一般化する可能性がある