DuckDB V2 PEGベースSQLパーサー

DuckDB v2.0: データベースにはより良いパーサーが必要です Daniël ten Wolde 2026-08-20 | 16 分 TL;DR: DuckDB v2.0 は、PostgreSQL 由来の SQL パーサーを PEG ベースのパーサーに置き換えました。これにより、進化が容易になり、実行時に拡張できるようになります。 DuckDB では、データベースシステムでの作業を可能な限り容易にすることが目標の 1 つです。ユーザーは広く理解されている構造化照会言語（SQL）を通じてシステムと対話します。以前のブログ投稿では、GROUP BY ALL や SELECT * EXCLUDE (...) を使用した列選択など、DuckDB のフレンドリーな SQL について取り上げました。しかし、DuckDB がこれらの機能を使用してクエリを実行できるようになる前に、まずその構文が有効かどうかを判断する必要があります。それがパーサーの仕事であり、DuckDB v2.0 では、ユーザーが気づかないうちにそれを完全に置き換えます。 パーサーの役割とは？ 大まかに言うと、DuckDB は SQL クエリを次のステージで処理します。 このブログでは、トークナイザー、パーサー、トランスフォーマーに焦点を当てます。 トークナイザー: これは最初のステップであり、生の入力文字列をトークンに分割する責任があります。これらは、たとえば KEYWORD、NUMBER、IDENTIFIER など、さまざまなカテゴリに分類できます。また、SQL で -- または /* */ として示されるコメントを認識してスキップする場所でもあります。 パーサー: パーサーは、これらのトークンが DuckDB の文法に従っているかどうかを判断し、ParseResult ツリーを生成します。トランスフォーマー: 一般的な解析結果を DuckDB の内部抽象構文ツリー（AST）に変換し、SQLStatement、TableRef、ParsedExpression などの構造を形成します。結果の AST はバインダーに渡されます。 パーサーはクエリが構文的に有効かどうかを判断し、バインダーはそれが参照するテーブル、列、関数が実際に存在するかどうかを判断します。 次のクエリを検討してください。 SELECT * WHERE true FROM range(1); パーサーエラー: "FROM" の近くで構文エラー LINE 3: FROM range(1); ^^^^^^ このクエリの個々のトークンはすべて有効ですが、句の順序が DuckDB の文法で許可されていない順序になっています。フレンドリー SQL は、SELECT ファーストと FROM ファーストの両方の構文を許可しますが、句を任意の順序で表示することは許可しません。比較すると、次のクエリは構文的に有効であるため、パーサーとトランスフォーマーを通過します。ただし、テーブル missing_table が存在しないため、バインダーで later に失敗します。 FROM missing_table; カタログエラー: 名前 missing_table のテーブルが存在しません！ LINE 1: FROM missing_table; ^^^^^^^^^^^^^ DuckDB の SQL 方言 SQL 標準は存在しますが、各データベースシステムは標準のさまざまな部分をサポートし、独自の構文と動作を追加します。結果のバリアントは、一般に SQL 方言と呼ばれます。例としては、PostgreSQL、Oracle、GoogleSQL for BigQuery、MySQL、MariaDB、SQLite、Spark SQL、そしてもちろん DuckDB がサポートする方言があります。DuckDB の SQL は PostgreSQL の規則に強く従いますが、長年にわたって大きく進化してきました。GROUP BY ALL のような独自の機能を追加したり、他のデータベースシステムに触発された機能を追加したりしました。同時に、DuckDB は PostgreSQL のすべての動作を実装しているわけではありません。したがって、DuckDB は独自の SQL 方言を使用します。この投稿では、それを DuckSQL と呼びますが、PostgreSQL の影響を強く受けています。この区別は、パーサーについて話す際に重要です。DuckDB が受け入れる SQL 方言と、その SQL を解析するために使用される実装は、2 つの別個のものです。DuckDB v2.0 では、パーサーの実装を置き換え、その文法を書き直しています。置き換えていないのは DuckSQL 自体です。 PostgreSQL 由来のパーサーの限界 DuckDB が始まったとき、PostgreSQL 由来のパーサーと文法を使用するのは理にかなっていました。このパーサーは、2018 年の DuckDB への最初のコミットに既に含まれていました。多くのユーザーが既に慣れ親しんでいる構文に基づいた、成熟した、実証済みの SQL 文法を DuckDB に提供しました。私たちはパーサーをニーズに合わせて適応させ、結果の PostgreSQL スタイルの構文ツリーを DuckDB の内部 AST に変換するトランスフォーマーを追加しました。しかし、長年にわたり、このパーサーにはいくつかの欠点もありました。DuckSQL を拡張することは、基盤となる YACC/Bison 文法を変更することを意味しました。Bison は LALR(1) パーサーを生成するため、文法への小さな追加でも既存のルールと相互作用し、シフト/リデュースまたはリデュース/リデュースの競合を引き起こす可能性があります。DuckSQL が成長するにつれて、文法への変更はますます困難になりました。これは、実行時に拡張可能な SQL パーサーに関する以前のブログ投稿の動機の 1 つでした。その投稿と付随する CIDR ペーパーで、Parsing Expression Grammars（PEG）が拡張可能なデータベースパーサーのより良い基盤を提供できるかどうかを検討しました。当時、PEG パーサーは SQL のサブセットしか解析できない実験的なプロトタイプでした。 PEG パーサーの概要 プロトタイプを本番用パーサーに変える方法を見る前に、PEG が言語をどのように記述するかを簡単に復習しましょう。PEG は、入力がどのように一致する必要があるかを記述する名前付きルールで構成されます。DuckDB の新しい文法からの次のルールを検討してください。 SelectFrom <- SelectFromClause / FromSelectClause SelectFromClause <- SelectClause FromClause? FromSelectClause <- FromClause SelectClause? <- 演算子はルールを定義し、/ は代替案間の選択を指定し、? は要素をオプションにします。これらのルールは together、DuckSQL が従来の SELECT ファーストクエリと、DuckDB のフレンドリー SQL である FROM ファーストの同等物の両方を受け入れることを示しています。 SELECT * FROM range(1); FROM range(1) SELECT *; PEG は代替案を順序どおりに評価します。SelectFrom を一致させるとき、パーサーは最初に SelectFromClause を試します。それが一致しない場合、FromSelectClause を試します。最初に成功した代替案が選択されます。その結果、PEG 文法には LALR 文法のようなシフト/リデュースおよびリデュース/リデュースの競合はありません。代わりに、代替案は明示的に順序付けられ、その順序は文法の動作の一部を形成します。PEG ベースのパーサーに変更しているのは私たちだけではありません。Python は Python 3.9 で LL(1) パーサーから PEG ベースのパーサーに切り替えましたが、これも PEG が言語を進化させるための追加の柔軟性を提供することによって動機付けられました。 DuckDB では、これらのルールはトークナイザーによって生成されたトークン上で動作します。マッチャーは文法ルールをそれらのトークンに適用し、一般的な ParseResult ツリーを構築します。これは subsequently DuckDB の内部 AST に変換されます。 プロトタイプから本番へ 研究プロトタイプは、PEG ベースの SQL パーサーが実現可能であることを示しました。しかし、DuckDB の既存のパーサーを置き換えるには、SQL のサブセットを解析する以上のことが必要でした。新しいパーサーは、すべての DuckSQL を受け入れ、DuckDB のバインダーが期待するのと同じ AST を生成する必要がありました。PEG 文法は最初に DuckDB v1.2 で導入され、CLI でのオートコンプリートを処理しました。その後、DuckDB v1.5 では、実験的なオプトイン機能として完全な PEG パーサーを導入しました。また、DuckDB にオランダ語を話させるエイプリルフールのジョークにも使用しました。それ以来、文法、マッチャー、トランスフォーマーは着実に改善され、PEG パーサーは DuckDB v2.0 のデフォルトになりました。とりわけ、パーサーは次のことをサポートする必要がありました。 すべてのステートメントと式のタイプ: 完全な DuckSQL 方言をサポートするには、一般的な構文と、あまり使用されないステートメントや式が含まれます。 演算子の優先順位と結合性: たとえば、SELECT true OR true AND false; は (true OR (true AND false)) と解釈される必要があります。AND は OR よりも優先順位が高いためです。 正しいキーワード分類: SELECT のような一部のキーワードは予約済みであり、引用符で囲まれていないテーブル名または列名として使用できません。他のキーワードは、コンテキストに応じて識別子として使用できます。 DuckDB の内部 AST との互換性: PEG トランスフォーマーは、言語の動作が変更されないことが意図されている場所では、PostgreSQL 由来の構文ノードのトランスフォーマーと同じ DuckDB AST 構造を生成する必要があります。 正しいエラーレポート: 無効なクエリの場合、パーサーは解析が失敗した場所を報告し、可能な場合はコンテキストと有用な指示を提供する必要があります。