DuckDB V2 基于PEG的SQL解析器

# DuckDB v2.0：您的数据库值得更好的解析器 来源：https://duckdb.org/2026/08/20/duckdb-20-peg-parser *概要：DuckDB v2.0 用基于 PEG 的解析器替代了从 PostgreSQL 衍生的 SQL 解析器，新解析器更易于演进且支持运行时扩展。* 在 DuckDB，我们的目标之一是尽可能简化数据库系统的使用。用户通过广泛使用的结构化查询语言（SQL）与系统交互。之前的博文已介绍过 DuckDB 的友好 SQL（https://duckdb.org/2022/05/04/friendlier-sql）和更友好的 SQL（https://duckdb.org/2023/08/23/even-friendlier-sql），包括 `GROUP BY ALL` 和使用 `SELECT * EXCLUDE (...)` 进行列选择。然而，在 DuckDB 执行使用这些特性的查询之前，它首先需要确定语法是否有效。这是*解析器*的工作，在 DuckDB v2.0 中，我们正在完全替换它，而您不会察觉。 ## 解析器的作用是什么？ (https://duckdb.org/2026/08/20/duckdb-20-peg-parser#what-is-the-role-of-a-parser) 从高层次看，DuckDB 通过以下阶段处理 SQL 查询：  在本文中，我们将重点关注分词器、解析器和转换器： - **分词器**：这是第一步，负责将原始输入字符串分割成*词元*。这些词元可以属于不同类别，例如：`KEYWORD`、`NUMBER` 或 `IDENTIFIER`。它还会识别并跳过 SQL 中用 `--` 或 `/* */` 表示的注释。 - **解析器**：解析器确定这些词元是否遵循 DuckDB 的语法，并生成一个 `ParseResult` 树。 - **转换器**：将通用的解析结果转换为 DuckDB 的内部抽象语法树（AST），构建诸如 `SQLStatement`、`TableRef` 和 `ParsedExpression` 等结构。 生成的 AST 会传递给绑定器。 解析器决定查询在语法上是否有效，而绑定器决定其引用的表、列和函数是否实际存在。 考虑以下查询： ```sql SELECT * WHERE true FROM range(1); ``` ``` 解析器错误：语法错误，在 "FROM" 附近或之前 第 3 行: FROM range(1); ^^^^ ``` 此查询中的每个单独*词元*都是有效的，但子句的顺序是 DuckDB 语法所不接受的。友好 SQL 允许 `SELECT` 优先和 `FROM` 优先的语法，但不允许子句以任意顺序出现。 相比之下，以下查询在语法上是有效的，因此通过了解析器和转换器。但是，它稍后在绑定器中失败，因为表 `missing_table` 不存在。 ```sql FROM missing_table; ``` ``` 目录错误：名为 missing_table 的表不存在！ 第 1 行: FROM missing_table; ^^^^^^^^^ ``` ## DuckDB SQL 方言 (https://duckdb.org/2026/08/20/duckdb-20-peg-parser#the-duckdb-sql-dialect) 尽管存在 SQL 标准，但每个数据库系统支持该标准的不同部分，并添加自己的语法和行为。由此产生的变体通常被称为 SQL 方言。示例包括 PostgreSQL (https://www.postgresql.org/docs/current/sql.html)、Oracle (https://docs.oracle.com/en/database/oracle/oracle-database/26/sqlrf/)、BigQuery 的 GoogleSQL (https://docs.cloud.google.com/bigquery/docs/introduction-sql)、MySQL (https://dev.mysql.com/doc/refman/8.4/en/sql-statements.html)、MariaDB (https://mariadb.com/docs/server/reference/sql-statements)、SQLite (https://sqlite.org/lang.html)、Spark SQL (https://spark.apache.org/docs/latest/sql-ref.html) 以及当然，DuckDB (https://duckdb.org/docs/current/sql/dialect/overview) 支持的方言。 DuckDB 的 SQL 严格遵循 PostgreSQL 的约定，但多年来已有了显著的发展。我们添加了自己的特性，如 `GROUP BY ALL`，以及受其他数据库系统启发的特性。同时，DuckDB 并未实现 PostgreSQL 行为的方方面面。因此，DuckDB 有自己的 SQL 方言，我们在本文中称之为 **DuckSQL**，尽管它仍深受 PostgreSQL 的影响。 这个区分在讨论解析器时很重要。DuckDB 接受的 SQL 方言与用于解析该 SQL 的实现是两回事。对于 DuckDB v2.0，我们正在替换解析器实现并重写其语法。我们**没有**替换的是 DuckSQL 本身。 ## 超越从 PostgreSQL 衍生的解析器 (https://duckdb.org/2026/08/20/duckdb-20-peg-parser#outgrowing-the-postgresql-derived-parser) 当 DuckDB 刚起步时，使用从 PostgreSQL 衍生的解析器和语法是非常合理的。这个解析器早已包含在 DuckDB 2018 年的第一次提交 (https://github.com/duckdb/duckdb/commit/ba75d81601913782d28a3878707d135319f38bdd) 中。它为 DuckDB 提供了一个成熟、经过实战检验的 SQL 语法，基于许多用户已经熟悉的语法。我们调整了解析器以适应我们的需求，并添加了一个 `Transformer`，将生成的 PostgreSQL 风格的解析树转换为 DuckDB 的内部 AST。 然而，这些年来，这个解析器也带来了一些缺点。扩展 DuckSQL 意味着要修改底层的 YACC/Bison 语法。因为 Bison 生成 LALR(1) 解析器，所以语法上看似小的改动也可能与现有规则交互，引入 `shift/reduce` 或 `reduce/reduce` 冲突。随着 DuckSQL 的发展，修改语法变得越来越困难。这是我们之前关于运行时可扩展 SQL 解析器的博文 (https://duckdb.org/2024/11/22/runtime-extensible-parsers) 的动机之一。在那篇文章以及相关的 CIDR 论文 (https://vldb.org/cidrdb/papers/2025/p18-muhleisen.pdf) 中，我们探讨了解析表达式语法（PEG）是否可以为可扩展的数据库解析器提供更好的基础。当时，PEG 解析器还是一个实验性原型，只能解析 SQL 的一个子集。 ## PEG 解析器入门 (https://duckdb.org/2026/08/20/duckdb-20-peg-parser#a-primer-on-peg-parsers) 在了解我们如何将原型转化为生产解析器之前，让我们简要回顾一下 PEG 如何描述语言。PEG 由命名规则组成，描述如何匹配输入。考虑 DuckDB 新语法中的以下规则： ``` SelectFrom <- SelectFromClause / FromSelectClause SelectFromClause <- SelectClause FromClause? FromSelectClause <- FromClause SelectClause? ``` `<-` 运算符定义了一个规则，`/` 指定选项之间的选择，`?` 使元素可选。这些规则共同指出 DuckSQL 接受传统的 `SELECT` 优先查询： ```sql SELECT ... FROM ...; ``` 以及 DuckDB 的友好 SQL 的 `FROM` 优先等效形式： ```sql FROM ... SELECT ...; ``` PEG 按顺序评估选项。在匹配 `SelectFrom` 时，解析器首先尝试 `SelectFromClause`。如果不匹配，则尝试 `FromSelectClause`。第一个成功的替代方案被选中。因此，PEG 语法没有像 LALR 语法那样的 `shift/reduce` 和 `reduce/reduce` 冲突。相反，替代方案是显式排序的，该顺序构成了语法行为的一部分。 我们并非唯一转向基于 PEG 解析器的团队。Python 从其 LL(1) 解析器切换 (https://peps.python.org/pep-0617/) 到 Python 3.9 中基于 PEG 的解析器，动机也是 PEG 为语言演进提供的额外灵活性。在 DuckDB 中，这些规则作用于分词器产生的词元。匹配器将语法规则应用于这些词元，并构造一个通用的 `ParseResult` 树，随后将其转换为 DuckDB 的内部 AST。 ## 从原型到生产 (https://duckdb.org/2026/08/20/duckdb-20-peg-parser#going-from-prototype-to-production) 研究原型证明了基于 PEG 的 SQL 解析器是可行的。然而，替换 DuckDB 现有的解析器远不止解析 SQL 子集。新解析器必须接受所有 DuckSQL 并生成 DuckDB 绑定器所期望的相同 AST。 PEG 语法首先在 DuckDB `v1.2` 中引入，用于处理 CLI 中的自动补全。后来，在 DuckDB `v1.5` 中，我们将完整的 PEG 解析器作为实验性、可选的功能引入。我们还用它开了一个愚人节玩笑，让 DuckDB 说荷兰语 (https://duckdb.org/2026/04/01/duckdb-now-speaks-dutch)。从那时起，语法、匹配器和转换器得到了持续改进，使 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 结构。 - **正确的错误报告：** 对于无效查询，解析器应报告解析失败的位置，并尽可能提供上下文和有用的错误提示。理想情况下，它应该在不指向手册 (https://duckdb.org/2024/11/22/runtime-extensible-parsers#:~:text=You%20have%20an%20error%20in%20your%20SQL%20syntax%3B%20check%20the%20manual%20that%20corresponds%20to%20your%20MySQL%20server%20version%20for%20the%20right%20syntax%20to%20use%20near%20%27SELEXT%27%20at%20line%201%2E) 的情况下做到这一点。 - **对异常输入的性能：** 除了保持正常解析快速之外，我们还必须确保格式错误的查询不会突然花费很长时间来解析。 ### 通过打包鼠解析避免重复工作 (https://duckdb.org/2026/08/20/duckdb-20-peg-parser#avoiding-repeated-work-with-packrat-parsing) 我们遇到的一个问题是回溯期间的重复工作。一个朴素的 PEG 匹配器在尝试不同替代方案时，可能会在相同词元位置多次评估同一语法规则。对于某些格式错误的输入，重复工作的量可能呈指数级增长。我们在包含大量未匹配左括号的查询中遇到了这种情况： ```sql SELECT ((((((((((((((((((; ``` 使用 `v1.5` 中附带的实验性 PEG 解析器，每增加一个左括号，解析时间大约翻倍： ``` 18 个左括号：5.303 秒 19 个左括号：10.640 秒 ``` 我们通过使用 **打包鼠解析**（一种常用于 PEG 解析器的记忆化技术）来解决这个问题。对于每个记忆化的匹配器，我们存储在特定词元位置应用它的结果。如果解析器稍后尝试在同一位置的相同匹配器，它会重用缓存的结果，而不是再次评估它。启用打包鼠解析后，相同的格式错误查询几乎立即被拒绝： ``` 19 个左括号：0.001 秒 ``` 因此，一个记忆化的匹配器在特定词元位置最多被评估一次，消除了在此示例中导致指数行为的重复工作。这需要在解析过程中占用额外内存，但为了避免此类情况，这是值得的权衡。 将原型转化为生产解析器涉及的远不止翻译语法。新解析器必须覆盖完整的 DuckSQL 方言，保留 DuckDB 现有的 AST，与现有查询保持兼容，并高效处理有效和格式错误的输入。最终的架构替换了从 PostgreSQL 衍生的解析器前端，而绑定器和 DuckDB 查询处理管道的其余部分继续在相同的内部 AST 上操作。  *DuckDB 解析器架构。核心思想：替换从 PostgreSQL 衍生的解析前端，同时保持 DuckDB 的其余执行管道不变。* ## 演进 DuckSQL (https://duckdb.org/2026/08/20/duckdb-20-peg-parser#evolving-ducksql) 随着 PEG 解析器现在已应用于 DuckDB v2.0，我们也持续用新语法扩展 DuckSQL。一个例子是新的表达式-语句语法。到目前为止，执行仅由表达式组成的查询总是需要编写一个 `SELECT`： ```sql SELECT date: current_date(), time: current_localtime(); ``` 使用表达式语句，可以省略 `SELECT`： ```sql date: current_date(), time: current_localtime(); ``` 作为额外好处，这也适用于前缀别名。 另一个例子是为 Quack (https://duckdb.org/quack/) 引入的新 `CONNECT` (https://github.com/duckdb/duckdb/pull/22732) 语句。它允许您连接到远程数据库，并将后续查询路由到该数据库，直到您运行 `DISCONNECT`： ```sql CONNECT 'postgres://localhost/mydb'; SELECT count(*) FROM orders; -- 在 PostgreSQL 服务器上运行 DISCONNECT; ``` 还将有用于处理外部资源 (https://github.com/duckdb/duckdb/pull/23731) 的新语法。这将允许您通过扩展管理存在于 DuckDB 外部的资源。您将能够在 DuckDB 内部创建、注册、检查、连接或销毁资源： ```sql CREATE EXTERNAL RESOURCE '' AS (...); REGISTER EXTERNAL RESOURCE '' AS FROM ; SHOW EXTERNAL RESOURCES; CONNECT TO EXTERNAL RESOURCE ; DESTROY EXTERNAL RESOURCE ; ``` 我们还扩展了 `COPY TO`，增加了 `PARTITION BY` 和 `ORDER BY` 语法： ```sql COPY orders TO 'orders' ( FORMAT parquet, PARTITION BY (year, month), ORDER BY (order_date) ); ``` 这些添加用旧的 PostgreSQL 衍生解析器也是可能的，但添加它们会相当麻烦。PEG 语法使我们更容易继续演进 DuckSQL。 到目前为止，这些规则都是 DuckSQL 本身的一部分。下一步是允许扩展添加它们自己的规则。 ## 扩展解析器 (https://duckdb.org/2026/08/20/duckdb-20-peg-parser#extending-the-parser) 扩展是 DuckDB 的核心部分。它们已经可以添加标量和表函数、优化器规则、查询计划重写，甚至自定义物理算子。添加新语法的扩展已经存在，例如 `psql` (https://duckdb.org/community_extensions/extensions/psql) 和 `duckpgq` (https://duckdb.org/community_extensions/extensions/duckpgq)，但底层它们是作为回退解析器工作的。DuckDB 首先尝试自己解析查询，只有在失败时才调用扩展。这对于独立的语法很有效，但希望在 SQL 内部添加语法的扩展也必须自己解析周围的 SQL。这些回退解析器还使得无法组合多个扩展的语法。 使用 PEG 解析器，扩展可以改为扩展 DuckDB 解析器的各个部分。它们可以扩展分词器，添加语法规则，并注册自定义匹配器，同时继续重用 DuckDB 的其余部分。 > **警告**：下面显示的 API 仍然是预览版，在 DuckDB v2.0 (https://duckdb.org/2026/08/17/duckdb-20-highlights.html) 之前可能会更改。您可以在 GitHub (https://github.com/duckdb/duckdb/pull/24919) 上关注正在进行的开发。 为了具体说明，我们使用 Google 的管道查询语法 (https://docs.cloud.google.com/bigquery/docs/reference/standard-sql/pipe-syntax)。这是对 SQL 的扩展，添加了管道数据流语法。管道语法将查询表示为一系列算子，每个算子使用前一个算子的结果。 ```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 / SelectStatement ```