HN 日本語サマリー

← 一覧へ戻る
プログラミング

DuckDB V2 PEGベースSQLパーサー

DuckDB V2 PEG-based SQL parser (duckdb.org)

44 pointsby karma_daemon4 コメント

要約

DuckDB v2.0では、PostgreSQL由来のSQLパーサーをPEG(Parsing Expression Grammar)ベースのパーサーに置き換えました。これにより、パーサーの進化が容易になり、実行時の拡張性も向上しました。この変更はユーザーには気づかれないものの、DuckDBのSQL方言(DuckSQL)をより柔軟に進化させるための重要なステップです。

全文翻訳

DuckDB v2.0: より良いパーサーを手に入れたあなたのデータベース

ブログ リリース

要約: DuckDB v2.0は、PostgreSQL由来のSQLパーサーをPEGベースのパーサーに置き換えました。これにより、進化が容易になり、実行時に拡張できるようになります。

DuckDBでは、データベースシステムとの連携を可能な限り容易にすることが目標の一つです。ユーザーは広く理解されている構造化照会言語(SQL)を通じてシステムと対話します。以前のブログ記事では、GROUP BY ALLやSELECT * EXCLUDE (...)を使用した列選択など、DuckDBのフレンドリーなSQL SQLについて解説しました。しかし、DuckDBがこれらの機能を使用してクエリを実行するには、まずその構文が有効かどうかを判断する必要があります。それがパーサーの仕事であり、DuckDB v2.0では、ユーザーが気づかないうちにこれを完全に置き換えます。

パーサーの役割とは?

大まかに言うと、DuckDBはSQLクエリを以下のステージで処理します。

[画像: Parser workflow] [画像: Parser workflow]

このブログでは、トークナイザー、パーサー、トランスフォーマーに焦点を当てます。

  • トークナイザー: これは最初のステップで、生の入力文字列をトークンに分割する役割を担います。これらは、例えば KEYWORD、NUMBER、IDENTIFIER など、さまざまなカテゴリに分類されます。また、SQLで -- または /* */ で示されるコメントを認識してスキップする場所でもあります。
  • パーサー: パーサーは、これらのトークンがDuckDBの文法に従っているかどうかを判断し、ParseResultツリーを生成します。
  • トランスフォーマー: ジェネリックな解析結果をDuckDBの内部抽象構文木(AST)に変換し、SQLStatement、TableRef、ParsedExpressionなどの構造を形成します。生成されたASTはバインダーに渡されます。

パーサーはクエリが構文的に有効かどうかを判断し、バインダーはそれが参照するテーブル、列、関数が実際に存在するかどうかを判断します。

以下のクエリを考えてみましょう。

SELECT *
WHERE true
FROM range(1);
Parser Error:
syntax error at or near "FROM"

LINE 3: FROM range(1);
        ^^^^

このクエリの個々のトークンはすべて有効ですが、句の順序がDuckDBの文法で許可されていない順序になっています。フレンドリーSQLはSELECT先行構文とFROM先行構文の両方を許可しますが、句を任意の順序で配置することは許可しません。

これに対し、以下のクエリは構文的に有効であるため、パーサーとトランスフォーマーを通過します。しかし、テーブル missing_table が存在しないため、後でバインダーで失敗します。

FROM missing_table;
Catalog Error:
Table with name missing_table does not exist!

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を解析するために使用される実装は、別個のものです。DuckDB v2.0では、パーサーの実装を置き換え、その文法を書き直しています。私たちが置き換えていないのは、DuckSQLそのものです。

PostgreSQL由来のパーサーの限界

DuckDBが開発された当初は、PostgreSQL由来のパーサーと文法を使用するのは理にかなっていました。このパーサーは、2018年のDuckDBへの最初のコミットから存在していました。これにより、多くのユーザーが既に慣れ親しんでいる構文に基づいた、成熟した、実証済みのSQL文法をDuckDBは得ることができました。私たちはパーサーをニーズに合わせて調整し、生成されたPostgreSQLスタイルの構文解析ツリーをDuckDBの内部ASTに変換するTransformerを追加しました。

しかし、長年にわたり、このパーサーにはいくつかの欠点も伴いました。DuckSQLを拡張するには、基盤となるYACC/Bisonの文法を変更する必要がありました。BisonはLALR(1)パーサーを生成するため、文法への些細な追加が既存のルールと相互作用し、shift/reduceまたはreduce/reduceの競合を引き起こす可能性がありました。DuckSQLが成長するにつれて、文法の変更はますます困難になりました。

これが、実行時に拡張可能なSQLパーサーに関する以前のブログ記事の動機の一つでした。その記事と付随するCIDR論文では、Parsing Expression Grammars(PEG)が拡張可能なデータベースパーサーのより良い基盤を提供できるかどうかを検討しました。当時、PEGパーサーはまだSQLのサブセットしか解析できない実験的なプロトタイプでした。

PEGパーサー入門

プロトタイプを本番用パーサーに転換する前に、PEGがどのように言語を記述するかを簡単に復習しましょう。

PEGは、入力がどのように一致するかを記述する名前付きルールで構成されます。DuckDBの新しい文法の以下のルールを考えてみましょう。

SelectFrom <- SelectFromClause / FromSelectClause
SelectFromClause <- SelectClause FromClause?
FromSelectClause <- FromClause SelectClause?

<-演算子はルールを定義し、/は代替案間の選択を指定し、?は要素をオプションにします。これらを組み合わせると、これらのルールはDuckSQLが従来のSELECT先行クエリと、

SELECT *
FROM range(1);

DuckDBのフレンドリーSQLのFROM先行相当の両方を許容することを示しています。

FROM range(1)
SELECT *;

PEGは代替案を順番に評価します。SelectFromを一致させる際、パーサーはまずSelectFromClauseを試みます。それが一致しない場合、FromSelectClauseを試みます。最初に成功した代替案が選択されます。その結果、PEG文法はLALR文法と同じshift/reduceおよびreduce/reduceの競合を持ちません。代わりに、代替案は明示的に順序付けられ、その順序が文法の動作の一部を形成します。

PEGベースのパーサーに変更しているのは私たちだけではありません。PythonはPython 3.9でLL(1)パーサーからPEGベースのパーサーに切り替えましたが、これもPEGが言語を進化させるための追加の柔軟性を提供することに動機づけられました。

DuckDBでは、これらのルールはトークナイザーによって生成されたトークン上で動作します。マッチャーは文法ルールをそれらのトークンに適用し、ジェネリックなParseResultツリーを構築します。これはその後、DuckDBの内部ASTに変換されます。

プロトタイプから本番へ

研究プロトタイプは、PEGベースのSQLパーサーが実現可能であることを示しました。しかし、DuckDBの既存のパーサーを置き換えるには、SQLのサブセットを解析する以上のことが必要でした。新しいパーサーは、すべてのDuckSQLを受け入れ、DuckDBのバインダーが期待するのと同じASTを生成する必要がありました。

PEG文法は、CLIでのオートコンプリートを処理したDuckDB v1.2で最初に導入されました。その後、DuckDB v1.5では、実験的なオプトイン機能として完全なPEGパーサーを導入しました。また、DuckDBがオランダ語を話すようにしたエイプリルフールのジョークにも使用しました。それ以来、文法、マッチャー、トランスフォーマーは着実に改善され、PEGパーサーはDuckDB v2.0のデフォルトとなりました。

とりわけ、パーサーは以下をサポートする必要がありました。

  • すべてのステートメントと式タイプ: 完全なDuckSQL方言をサポートするには、一般的な構文と、あまり使用されないステートメントや式の両方が含まれます。
  • 演算子の優先順位と結合規則: 例えば、SELECT true OR true AND false; は (true OR (true AND false)) と解釈される必要があります。なぜなら、AND は OR よりも強く結合するためです。
  • 正しいキーワード分類: SELECT のような一部のキーワードは RESERVED であり、引用符で囲まれていないテーブル名や列名として使用できません。他のキーワードは、コンテキストに応じて識別子として使用できる場合があります。
  • DuckDBの内部ASTとの互換性: PEGトランスフォーマーは、言語の動作が変更されないことが意図されている箇所では、PostgreSQL由来の構文解析ノードのトランスフォーマーと同じDuckDB AST構造を生成する必要があります。
  • 正しいエラーレポート: 無効なクエリの場合、パーサーは解析が失敗した場所を報告し、可能であればコンテキストと何が間違っていたのかについての有用な兆候を提供する必要があります。理想的には、マニュアルを指し示すことなく、これを行うべきです。
  • 異常な入力に対するパフォーマンス: 通常の解析を高速に保つことに加えて、不正なクエリが突然解析に長い時間がかかることがないようにする必要もありました。
Packratパーシングによる繰り返し作業の回避

遭遇した問題の一つは、バックトラッキング中の繰り返し作業でした。単純なPEGマッチャーは、さまざまな代替案を試す間に、同じトークン位置で同じ文法ルールを何度も評価する可能性があります。特定の不正な入力では、繰り返し作業の量が指数関数的に増加する可能性があります。

多数の閉じられていない開き括弧を含むクエリでこれに遭遇しました。

SELECT ((((((((((((((((((;

v1.5で出荷された実験的なPEGパーサーでは、開き括弧を1つ追加すると、解析時間が約2倍になりました。

18個の開き括弧:  5.303秒
19個の開き括弧: 10.640秒

これをPackratパーシング、PEGパーサーで一般的に使用されるメモ化技術を使用して解決しました。メモ化された各マッチャーについて、特定のトークン位置での適用結果を保存します。パーサーが後で同じ位置で同じマッチャーを試した場合、再度評価するのではなく、キャッシュされた結果を再利用します。

Packratパーシングを有効にすると、同じ不正なクエリがほぼ瞬時に拒否されました。

19個の開き括弧: 0.001秒

その結果、メモ化されたマッチャーは特定のトークン位置で最大1回評価され、この例で指数関数的な動作を引き起こした繰り返し作業が排除されます。これにより、解析中に余分なメモリが必要になりますが、このようなケースを回避するためには価値のあるトレードオフです。

プロトタイプを本番用パーサーに転換するには、文法を翻訳する以上のことが必要でした。新しいパーサーは、完全なDuckSQL方言をカバーし、DuckDBの既存のASTを維持し、既存のクエリとの互換性を保ち、有効な入力と不正な入力の両方を効率的に処理する必要がありました。

結果として得られたアーキテクチャは、PostgreSQL由来のパーサーフロントエンドを置き換えますが、バインダーとDuckDBのクエリ処理パイプラインの残りの部分は、同じ内部AST上で引き続き動作します。

[画像: Parser architecture] [画像: Parser architecture] DuckDBパーサーアーキテクチャ。重要なアイデア:PostgreSQL由来の構文解析フロントエンドを置き換え、DuckDBの残りの実行パイプラインはそのまま維持する。

DuckSQLの進化

DuckDB v2.0でPEGパーサーが導入されたことで、DuckSQLに新しい構文を追加し続けることもできました。

その一例が、新しい式ステートメント構文です。これまで、式のみで構成されるクエリを実行するには、常にSELECTを記述する必要がありました。

SELECT date: current_date(), time: current_localtime();

式ステートメントを使用すると、SELECTを省略できます。

date: current_date(), time: current_localtime();

ボーナスとして、これはプレフィックスエイリアスでも機能します。

もう一つの例は、Quackのために導入された新しいCONNECTステートメントです。これにより、リモートデータベースに接続し、DISCONNECTを実行するまで、後続のクエリをそこにルーティングできます。

CONNECT 'postgres://localhost/mydb';
SELECT count(*) FROM orders; -- PostgreSQLサーバーで実行される
DISCONNECT;

外部リソースを操作するための新しい構文も追加されます。これにより、拡張機能を通じてDuckDBの外部にあるリソースを管理できるようになります。DuckDB内からリソースの作成、登録、検査、接続、破棄をすべて行うことができます。

CREATE EXTERNAL RESOURCE 'resource-type' AS name (...);
REGISTER EXTERNAL RESOURCE 'resource-type' AS name FROM <handle>;

SHOW EXTERNAL RESOURCES;

CONNECT TO EXTERNAL RESOURCE name;

DESTROY EXTERNAL RESOURCE name;

また、COPY TOにPARTITION BYとORDER BY構文を追加しました。

COPY orders TO 'orders'
(
    FORMAT parquet,
    PARTITION BY (year, month),
    ORDER BY (order_date)
);

これらの追加は、古いPostgreSQL由来のパーサーでも可能でしたが、追加するにはかなりの手間がかかりました。PEG文法により、DuckSQLを進化させることが容易になりました。

これまでのところ、これらのルールはすべてDuckSQL自体の一部です。次のステップは、拡張機能が独自のルールを追加できるようにすることです。

パーサーの拡張

拡張機能はDuckDBの中心的な部分です。既にスカラー関数やテーブル関数、オプティマイザールール、クエリプランのリライト、さらにはカスタム物理演算子を追加できます。

新しい構文を追加する拡張機能は既に存在しますが(例:psqlやduckpgq)、内部的にはフォールバックパーサーとして機能します。DuckDBはまずクエリ自体を解析しようとし、失敗した場合にのみ拡張機能を呼び出します。これは自己完結型の構文にはうまく機能しますが、SQL内に構文を追加したい拡張機能は、周囲のSQL自体も解析する必要があります。これらのフォールバックパーサーは、複数の拡張機能の構文を組み合わせることも不可能にします。

PEGパーサーを使用すると、拡張機能は代わりにDuckDBパーサーの個々の部分を拡張できます。トークナイザーを拡張したり、文法ルールを追加したり、カスタムマッチャーを登録したりしながら、DuckSQLの残りの部分を再利用し続けることができます。

警告: ここに示すAPIはまだプレビュー段階であり、DuckDB v2.0のリリース前に変更される可能性があります。GitHubで進行中の開発をフォローできます:GitHub。

これを具体的にするために、Googleのパイプクエリ構文を使用します。これは、パイプデータフロー構文を追加するSQLの拡張機能です。パイプ構文は、各演算子が前の演算子の結果を消費する一連の演算子としてクエリを表現します。

FROM produce
  |> WHERE
        item != 'bananas'
        AND category IN ('fruit', 'nut')
  |> AGGREGATE count(*) AS num_items, sum(sales) AS total_sales
     GROUP BY item
  |> ORDER BY item DESC;

このための簡略化されたPEG文法には、いくつかのルールが必要です。

PipeSelectAtom <- PipeSource PipeStage+
PipeSource <- FromClause / SelectStatementType / SelectParens
PipeStage <- '|>' PipeOperator
PipeOperator <- PipeAggregate / PipeAggregateGroupOnly / PipeWhere / PipeSelect / PipeExtend / PipeDistinct / PipeOrderBy / PipeLimit
PipeWhere <- WhereClause
PipeSelect <- 'SELECT' TargetList
PipeExtend <- 'EXTEND' TargetList
PipeDistinct <- 'DISTINCT'
PipeOrderBy <- OrderByClause
PipeLimit <- LimitClause OffsetClause?
PipeAggregate <- 'AGGREGATE' TargetList GroupByClause?
PipeAggregateGroupOnly <- 'AGGREGATE' GroupByClause

ここで、+はPipeStageが1回以上発生する必要があることを意味するため、パイプクエリには少なくとも1つのパイプ演算子が含まれている必要があります。

この文法は、GroupByClauseなどの既存のルールを再利用して、拡張機能が定義する必要のある文法の量を減らすことができます。拡張機能は、DuckDBの既存の構文が適合しない場所に独自のルールを定義することもできます。

文法の登録

PEGルールを定義するだけでは、それらがDuckDBの文法の一部になるわけではありません。拡張機能は、(1)拡張したい既存の文法ルールと、(2)新しい構文をDuckDBのASTに変換するトランスフォーマールールを指定する必要があります。

現在のプロトタイプでは、特定の文法ルールが拡張ポイントを公開しています。Pipe SQLは、新しいキーワードAGGREGATEとEXTENDとともに、PipeSelectAtomをSelectAtomの追加の代替案として登録します。

static void LoadInternal(ExtensionLoader &loader) {
    ParserExtension extension;
    extension.grammar_extension.grammar = PIPE_SQL_GRAMMAR;
    extension.grammar_extension.select_atom_rule = "PipeSelectAtom";

    extension.grammar_extension.RegisterSelectAtomTransformer(
        "PipeSelectAtom",
        TransformPipeSelectAtom
    );

    loader.RegisterKeyword(
        "aggregate",
        ExtensionKeywordCategory::RESERVED
    );
    loader.RegisterKeyword(
        "extend",
        ExtensionKeywordCategory::RESERVED
    );

    loader.RegisterParserExtension(std::move(extension));
}

この代替案を登録することにより、結果として得られる文法は実質的に次のようになります。

SelectAtom <-
    PipeSelectAtom /
    SelectParens /
    SelectStatementType

拡張機能の代替案が最初に試されます。パイプ構文が存在しない場合、トークンを消費せずに失敗し、クエリは組み込みの代替案で解析されます。

結果の変換

文法ルールを追加しても、ParseResultが得られるだけです。拡張機能は、バインダーが期待するDuckDB ASTにその結果を変換する必要があります。PipeSelectAtomはSelectAtomを拡張するため、そのトランスフォーマーはSelectStatementを返します。

static unique_ptr<SelectStatement>
TransformPipeSelectAtom(PEGTransformer &transformer, ParseResult &parse_result) {
    auto &pipe = parse_result.Cast<ListParseResult>();

    // PipeSelectAtom <- PipeSource PipeStage+
    auto statement = TransformPipeSource(transformer, pipe.GetChild(0));

    auto &stages = pipe.Child<RepeatParseResult>(1);
    for (auto &stage : stages.GetChildren()) {
        ApplyPipeStage(transformer, stage.get(), *statement);
    }

    return statement;
}

ParseResultの形状は、前述の文法ルールに従います。PipeSelectAtomにはPipeSourceと1つ以上のPipeStageが含まれます。まずPipeSourceをDuckDBのSelectStatementに変換します。次に、各PipeStageが順番にそのステートメントに適用されます。結果のSelectStatementが返され、パーサーのパイプラインの残りの部分に進み、最終的にバインダーに渡されます。

ここでDuckDBの既存の文法を再利用することが特に役立ちます。拡張機能は、導入した新しい構文のみを変換する必要があります。既存のDuckDB文法ルール(例:GroupByClause)を再利用する場合、GROUP BY自体を実装する必要なく、対応する変換関数も再利用できます。

これは、現在利用可能なフォールバックパーサーとの重要な違いです。拡張機能は、式、テーブル参照、GROUP BY句、およびSQLの残りの部分自体を実装する必要がなくなりました。代わりに、必要な構文のみを追加し、それ以外のすべてについてDuckDBの文法と変換を再利用できます。

パイプSQLの実行

拡張機能が登録されたので、新しいパイプ構文を使用したクエリを実行できるようになりました。例えば、拡張機能によって追加されたパイプ演算子と、range()やプレフィックスエイリアスなどの既存のDuckSQL機能を組み合わせることができます。

FROM range(6) t(i)
  |> WHERE i % 2 = 0
  |> SELECT i, doubled: i * 2
  |> ORDER BY i DESC;
┌───────┬─────────┐
│   i   │ doubled │
│ int64 │  int64  │
├───────┼─────────┤
│     4 │       8 │
│     2 │       4 │
│     0 │       0 │
└───────┴─────────┘

拡張機能はパイプ固有の構文のみを定義します。式、テーブル参照、WHERE、SELECT、ORDER BY、およびその他の再利用されたルールは、引き続きDuckDB自体によって解析および変換されます。これは、新しい構文をDuckSQLと組み合わせることができることを意味します。拡張機能がSQLの残りの部分を再度実装する必要はありません。

結論

DuckDB v2.0では、PostgreSQL由来のパーサーを新しいPEGパーサーに置き換えます。既存のDuckSQLクエリは、これまでどおり動作するはずです。しかし、内部的には、新しいパーサーは進化が容易で、実行時拡張のために設計されたものを提供します。

この記事で示された実行時文法拡張APIはまだプレビュー段階であり、v2.0がリリースされる前に変更される可能性があります。しかし、基盤となるアイデアは既に機能しています。拡張機能は、既存のルールと変換を再利用しながら、独自の構文をDuckDBの文法に直接追加できます。これは、SQLの残りの部分を自分で解析する必要がなくなることを意味します。

コミュニティがどのような新しい構文を作成するかを見るのが楽しみです。それまでの間、DuckSQLを進化させ、パーサーを改善し続けます。

PEGパーサーで既存のクエリの動作が異なることに気づいた場合は、問題を報告して私たちに知らせてください。

最近の投稿

[画像: Benchmarking DuckDB v2.0-dev on NVIDIA Vera]

NVIDIA VeraでのDuckDB v2.0-devのベンチマーク

[画像]

Gábor Szárnyas

[画像: From JSON Strings to Typed Columns]

JSON文字列から型付き列へ

DuckDBチーム

[画像: What Is Inside an Iceberg Table?]

Icebergテーブルの中身は?

DuckDBチーム