ほとんどコードを見ずに、PostHogのSQLパーサーを70倍高速に書き直した
I rewrote PostHog's SQL parser, 70x faster, while barely looking at the code (posthog.com)
要約
PostHogのSQLパーサーをAI(Claude)の助けを借りて書き直し、70倍の高速化を達成したプロセスを解説しています。AIが生成したコードの正確性を確保するため、プロパティベースドテストとプロンプトエンジニアリングを駆使し、複雑なパーサー開発におけるAIの可能性と課題が示されています。最終的に、ほとんどコードを直接見ることなく、大規模なパフォーマンス改善を実現しました。
全文翻訳
コードをほとんど見ずに70倍高速なSQLパーサーを書いた
エージェントを使用してクエリパフォーマンスを自動リサーチで改善した成功を受けて、さらに野心的な試みに挑戦したくなりました。
複数の長期間稼働するClaude Codeセッションを並列で使用して、PostHogのSQLパーサーを書き直しました。その結果、約16,000行の「手書き」パーサーコード、5,000行のツールコード、さらに数千行のテストコードが作成され、パフォーマンスは約70倍向上しました。
新しいパーサーは、現実的なクエリのほとんどで以前のものと同等であり、悪意のあるトリックスター神によって書かれたごく一部のクエリでのみ異なります(SELECT SELECT FROM FROM WHERE WHERE AND ANDのような、完全に有効なSQLに対するテストも存在します)。
どのようにしてこれを実現し、その過程で何を学んだのかを説明します。
PostHogがそもそもSQLパーサーを持つ理由
PostHogでは、SQLでデータに直接アクセスできます。これは、SQLを生のClickHouse SQLにトランスパイルするためです。その理由は以下の通りです。
- データベース内の物理的なレイアウトに依存しない、データの論理ビューを提供したいからです。
- これにより、既存のクエリを壊すことなく、データベース層で変更を加えることができます。
- パフォーマンス最適化やアクセス制御なども追加できます。
PostHogのツールの大部分(例: プロダクトアナリティクス、セッションリプレイ、エラー追跡)ではSQLでクエリが書かれており、それらはすべて同じトランスパイルプロセスを経由します。しかし、このトランスパイルを行う前に、パーサーを使用してSQLをAST(Abstract Syntax Tree)に変換する必要があります。このASTが、ClickHouse SQLにトランスパイルされます。
パーサーはクエリに最初に触れるものであり、信頼できない入力を処理します。アクセス制御や最適化など、後続のすべてはパーサーが生成したツリー上で動作します。
ANTLRによるパーサーの生成
このパーサーを手書きで作成しなかったのは、少なくともAIコーディング以前は、パーサーの保守が非常に困難だったからです。AIなしで書くには数ヶ月かかり、パフォーマンスが劇的に向上したとしても、それに見合う価値はなかったでしょう。
代わりに、最先端のオープンソースパーサー生成ツールであるANTLRを使用しています。.g4ファイルに文法を宣言的に記述すると、ANTLRがパーサーコードの大部分を生成してくれます。私たちはC++版を使用しているため、すでに「高速」な言語です。私たちのflags rewriteとは異なり、速度向上はRustへの移行だけによるものではありません。
ANTLRは非常に強力で柔軟ですが、トレードオフとして、トークンを訪問するたびに多くの処理を行います。文法をATN(本質的にはスタック付きのNFA)にコンパイルし、実行時には汎用的なインタープリターがグラフをウォークします。手書きのparseExpression()のようなものはありません。すべては、追加の抽象化と間接参照のレイヤーを通じて行われます。
さらに、ANTLRは任意の動的ルックアヘッドをサポートしているため、複数の可能な代替がある場合、1つの解釈が有効になるまで、すべての解釈をロックステップでシミュレートする必要があります。これは非常に最適化されていますが、グラフウォークインタープリターが手書きの再帰下降パーサーほど高速になることはありません。
新しいパーサーを書き、間違いをなくす
AIを使えば、手書きのパーサーを書き、保守することがはるかに容易になります。残念ながら、「新しいパーサーをRustで、間違いなく書いて」とClaudeに指示するほど簡単ではありませんでした。実際、多くの間違いを犯し、そのような書き直しが可能かどうかさえ疑い、コーディングの各ラウンドの後に一日を終えたがっていました。正直なところ、私自身もそれが可能かどうかはわかりませんでした。
並列で2つのアプローチをテストしました。
- パフォーマンスに焦点を当てたもの。もし機能すれば、最も高速なパーサーは再帰下降法とPratt式ループであり、必要に応じてルックアヘッドとバックトラッキングを追加するというものでした。
- 成功するパーサーを生成する可能性が最も高いアプローチに焦点を当てたもの。ANTLRの動作にできるだけ近く従いましたが、遷移は汎用的なグラフトラバーサルではなく、明示的なコードで実装しました。
最終的に、どちらのアプローチもほぼ同じように機能しましたが、これを数日間取り組むまでわかりませんでした。
私の目標は、現実的なクエリすべてにおいて、オラクル(つまり、既存のC++パーサー)と完全に一致させ、人工的なクエリについては可能な限り一致させることでした。オラクルを持つことは、新しいパーサーの開発において極めて重要でした。なぜなら、パーサー間で意見が分かれるSQLを見つけ、新しいパーサーを修正して一致させ、繰り返すという、テスト駆動開発を実質的に行うことができたからです。
不一致の生成(多くの方法で)
不一致、つまりテストケースの生成は、当初は簡単でした。なぜなら、元のパーサー開発中に多くの回帰テストがすでに書かれていたからです。それらがすべてパスするようになると、興味深いことが始まりました。
プロパティベーステスト
以前、HypothesisというPBT(プロパティベーステスト)ライブラリを使用して、SQLトランスパイラでバグを見つけたことがあります。コードのプロパティと入力値を定義すると、そのプロパティが成り立たないような入力値を生成しようとします。
具体的な例を挙げると、私の新しいパーサーのプロパティは、オラクルと一致することです。入力はSQLクエリです。これは、Hypothesisが私の新しいパーサーがオラクルと一致しないようなSQLクエリを見つけようとすることを意味します。
興味深いSQLを生成するためにHypothesisに指示する必要があったため、(Claudeと共に)ANTLRの文法ファイルに基づいたSQLジェネレーターをコード生成するツールを作成しました。新しいSQLパーサーを書くことが、.g4ファイルの新しいパーサーを書くことにつながったとき、少し笑ってしまったことを認めなければなりません。その後、生成されたSQLにトークンを入れ替えたり、括弧を追加したりする追加の順列ステップも追加しました。
脆弱な修正に対するプロンプトエンジニアリング
PBTは新しいテストケースを確実に生成でき、私の開発ループはうまく機能していましたが、Claudeは脆弱な修正を繰り返し行っていました。例えば、1つのケースを1トークンのルックアヘッドを追加して修正し、後で2トークンのルックアヘッドが必要だと気づく、といった具合です。私は定期的にコンテキストウィンドウの最大値に達し、コンパクションを行っていたため、実際の文法や参照パーサーの見た目を「忘れて」しまっていたのだと思われます。
これは、基本的なプロンプトエンジニアリングで解決できました。特定の分岐を修正するコードを書く直前に、文法ファイルと関連するC++ソースコードの両方をコンテキストにロードするように指示しただけです。これを理解するのに、認めがたいほど時間がかかりました。
最大化と熟考
この時点で、PBTでCPUを最大化し、Claudeの推論をパーサー作成で最大化したいと考えたため、PBTがバックグラウンドで常に実行され、失敗する新しいテストケースをファイルに書き出す(表示するのではなく)ツールを作成しました。Claudeは、他に作業がないときにそれらを取得できました。
本番のクエリログから匿名化されたクエリをプルするなど、失敗するテストケースを生成する他の方法もいくつかありました。おかしいことに、最も効果的な方法の1つは、バックグラウンドエージェントに「エッジケースについて深く考えて」と指示することでした。
2つの並列パーサーアプローチは回帰スイートを共有していたため、一方のセッションで見つかった失敗したテストケースはもう一方と共有されました。
Hypothesisはテストケースを「削減」して最小限の再現コードにすることもできますが、他のソースからのSQLではそれを使用できませんでした。それらには代わりにShrinkRayを使用しました。
その後、コードカバレッジ誘導のテストケース生成を追加しました。これにより、生成されるSQLの分布が改善されました。カバレッジフィードバックにより、ジェネレーターはまだ実行されていないコンストラクトを特定し、それらに偏らせることができます。これは、本番コーパスで100%の精度を達成するために必須ではありませんでしたが、非常に微妙なテストケースを見つけるのに役立ちました。
最終的なイテレーションループ
私のループの最終的なイテレーションは、次のようになりました。
- PBT、実際のコーパス、回帰テスト、および「エッジケースについて深く考える」から新しいテストの失敗を生成する。
- 失敗の削減されたバージョンを、拡大し続ける回帰テストリストに追加する。
- これを修正する最善の方法について深く考え、可能な場合は一般的な解決策を優先し、文法とC++ソースを読んで参照パーサーがどのように処理するかを確認する。
- 修正を行い、人間が読むための1段落の要約を出力する。
- 回帰スイートを実行して、すべてがパスすることを確認する。
- ループを自律的に再実行する。
新しいパーサーは非常に高速になったため、本番環境の既存のC++パーサーと「シャドウモード」でこのループを実行し、逸脱があれば報告できました。
本番のクエリログと比較した際、約50,000クエリしかテストしませんでした。シャドウモードでは、数百万のパースを迅速にテストでき、逸脱はゼロでした。数日間実行し続ける予定でしたが、結果が非常に強かったため、数時間後に本番トラフィックを切り替えました(0.1%の「リバースシャドウ」付き)。
454倍高速なパーサーと未来への展望
これにより、C++ ANTLRベースのパーサーと全く同じ出力(AST + ソース位置)が得られ、パフォーマンスの結果(黄色で表示)はほとんど信じられないほどです。
[画像: 新しいパーサーを示すベンチマーク結果]
本番クエリでは、以前のパーサーよりも平均で454倍高速でした。タイトルにある70倍は、私のラップトップでのベンチマークによるものですが、本番環境ではパーサーキャッシュにヒットしない長いSQLを主にパースしています。
これは私にとって大きな進歩でした。専門知識を持つ人が数ヶ月かかるようなものを、数日で構築できたことは非常に力強く感じました。
そして、コードを一切手書きで書いていないにもかかわらず、これを「バイブコーディング」とは全く呼びません。文法ファイルに基づいたコード生成入力と、カバレッジ誘導生成を備えた私のPBTセットアップは、パーサーファジングの最先端に非常に近いです。
これがANTLRのようなツールにとって何を意味するのかを考えるのは興味深いです。私のもののようなAIベースのアプローチが新常態になると予想しています。パーサージェネレーターがオラクルを提供し、その後LLMがPBT/ファジングを使用してパフォーマンスの高いパーサーを「手書き」で作成して一致させるのです。
具体的に何を得たのか?形式的には、私の新しいパーサーは「手書き」で、主に予測的再帰下降パーサーであり、Pratt式コアを持ち、LL(2)カーソルは特定の箇所で境界付きの非消費ルックアヘッドプローブによって拡張され、さらに、それが必要な数少ない決定のために予約された局所的な順序選択的投機的バックトラッキングを備えています。これは、2026年5月にClaude Opus 4.7によってRustで完全に書かれました。