当前位置：首页 > news >正文

DeepSeek总结的使用 PEG 实现运行时可扩展的 SQL 解析器

news 2026/6/3 0:52:51

来源：https://duckdb.org/2024/11/22/runtime-extensible-parsers.html

使用 PEG 实现运行时可扩展的 SQL 解析器

作者:Hannes Mühleisen, Mark Raasveldt
日期:2024-11-22
阅读时间:18 分钟

摘要:尽管解析器在查询处理中扮演着核心角色，但在数据系统领域并未受到任何显著的关注。最先进的系统满足于古老的解析器生成器。这些生成器创建了单体、不灵活且不容错的解析器，阻碍了查询语言的创新，并让用户感到沮丧。相反，解析器应该使用像解析表达文法这样的现代抽象来重写，它允许动态更改可接受的查询语法并提供更好的错误恢复。在这篇文章中，我们将讨论如何使用 PEG 重新设计解析器，并通过实验验证我们建议的有效性和效率。

更新

2026 年 3 月，DuckDB v1.5 发布了一个实验性解析器。你可以通过以下方式选择使用它：

CALLenable_peg_parser();

本文是我们经过同行评审的研究论文“运行时可扩展解析器”的缩短版本，该论文已被接受在将于 2025 年 1 月 19 日至 22 日在阿姆斯特丹举行的 2025 年创新数据系统研究会议 (CIDR) 上发表和演示。如果你愿意，可以阅读完整的论文。

解析器是数据库管理系统中负责将字符串格式的查询转换为内部表示（通常是树形结构）的组件。解析器定义了哪些查询将被接受。每一个 SQL 查询都从解析器开始其旅程。尽管解析器在技术栈中地位突出，但关于为数据管理系统解析查询的研究发表得很少。过去几十年，这个主题似乎没有什么进展，其实现很大程度上停留在六十年前的抽象和技术上。

SQL 规范的不断增长，包含了各种小众特性（例如，SQL/PGQ 中对图查询的支持或 XML 支持），以及支持 dplyr、piped SQL、PRQL 或 SaneQL 等替代查询符号的需求，使得单体解析器越来越不实用：在它们传统设计中，解析器构建是一项编译时活动，其中庞大的文法文件被转换为状态机转换查找表，然后被固化在系统二进制文件中。让这些总是存在于解析器中可能很浪费，特别是对于注重大小的二进制分发（如 WebAssembly）而言。

许多（如果不是大多数的话）SQL 系统使用由 YACC 风格的解析器工具包创建的静态解析器：我们可以很容易地为开源系统如 PostgreSQL 和 MySQL/MariaDB 确认这一点。通过分析它们二进制文件的符号名称，我们还发现 Oracle、SQL Server 和 IBM Db2 也使用 YACC。YACC 及其稍新的变体 GNU Bison 以及 SQLite 使用的“Lemon”解析器生成器，内部都使用了“单向前看从左到右最右推导” LALR(1) 解析器生成器。这个生成器将扩展巴科斯-瑙尔范式形式的一组形式上下文无关文法规则转换为解析器状态机。LALR 解析器是 Knuth 首次描述的 LR(k) 解析器的一种更节省空间的特殊化。但实际上，2024 年最先进的 SQL 系统使用的是 1960 年代的解析器技术。鉴于数据管理系统的其余部分自那时起已大为改观，这应该引发一个问题：为什么解析器没有得到任何认真的工程关注。

数据库系统正在朝着成为生态系统而非预构建的庞然大物的方向发展。PostgreSQL、SQLite 和 DuckDB 社区中的许多创新现在都来自扩展，这些扩展是加载到数据库系统中的共享库，用于扩展数据库系统的功能，如向量相似性搜索、地理空间支持、文件系统或图形处理。由于额外的二进制大小、外部依赖关系，预先捆绑所有这些功能将是困难的。此外，它们通常由各自的社区独立维护。到目前为止，至少部分由于 YACC 风格解析器的普遍存在，这些社区扩展一直受到限制，无法扩展语法。虽然在其他生态系统（如 Python）中也是如此，但 SQL 的设计高度关注语法而非函数调用，这使得扩展成为二等公民，它们不得不以某种方式绕过原始解析器的限制，例如，通过将自定义表达式嵌入字符串中。

我们提议重新思考数据管理系统解析器设计，以创建现代的、可扩展的解析器，允许在运行时动态配置可接受的语法，例如，允许语法扩展、新的语句，或添加全新的查询语言。这将允许打破目前使用的单体文法，并为数据管理系统可以接受的语法带来更多的创造性和灵活性，无论是工业还是研究用途。可扩展的解析器允许新的文法特性被轻松集成和测试，并且还可以通过将一个系统的方言支持添加到另一个系统的解析器中，帮助弥合不同 SQL 方言之间的差距。反过来，在某些用例中，限制可接受的文法也可能是可取的，例如，限制查询的复杂性，或强制严格遵守 SQL 标准。

现代化解析器基础设施还有额外的好处：数据管理系统中报告最多的支持问题之一是无用的语法错误。一些系统不遗余力地试图提供有意义的错误消息，例如，“此列不存在，您是不是指…”，但这通常仅限于在实际解析之后解析标识符。YACC 风格的解析器表现出“全有或全无”的行为，整个查询或查询集要么被完全接受，要么根本不接受。这就是为什么具有实际语法错误的查询（例如，SELEXT 而不是 SELECT）通常会被数据库管理系统严厉拒绝。例如，MySQL 以其无用的错误消息而臭名昭著：

您的 SQL 语法有错误；请查看与您的 MySQL 服务器版本对应的手册，以了解在第 1 行 ‘SELEXT’ 附近使用的正确语法。

解析表达文法

解析表达文法代表了一种更现代的解析方法。PEG 解析器是自上而下的解析器，可以有效地从文法生成递归下降风格的解析器。通过“Packrat”记忆化技术，PEG 解析器在解析时表现出线性时间复杂度，但代价是消耗与文法相关的额外内存。从文法编写者的角度来看，最大的区别在于选择操作符，其中可以匹配多个语法选项。在 LALR 解析器中，具有相似语法的选项可能会产生歧义并增加冲突。在 PEG 解析器中，始终选择第一个匹配的选项。因此，PEG 解析器在设计上不会产生歧义。

顾名思义，解析表达文法由一组解析表达式组成。表达式可以包含对其他规则的引用，或字面量标记引用，可以是实际字符串，也可以是类似于正则表达式的字符类。表达式可以通过序列、量词、可选、分组以及正/反向预查来组合。每个表达式要么匹配，要么不匹配，但如果匹配，则需要消耗输入的一部分。表达式能够向前查看并考虑剩余的输入，但不要求必须消耗它。词法分析通常是 PEG 解析器本身的一部分，这消除了单独步骤的需要。

一个很大的优点是 PEG 解析器不需要一个将文法转换为例如基于查找表的有限状态自动机的编译步骤。PEG 可以直接在输入上执行，只需最少的文法转换，这使得在运行时重新创建解析器变得可行。PEG 解析器越来越受欢迎，例如，Python 编程语言最近已切换到 PEG 解析器。

PEG 解析器的另一个大优点是错误处理：论文“解析表达文法中的语法错误恢复”描述了一种实用的技术，其中解析器规则被注解了“恢复”动作，它可以（1）显示多个错误，以及（2）用更有意义的错误消息注解错误。

记忆化 Packrat 解析的一个可能缺点是记忆化所需的内存：所需的内存量与输入大小成正比，而不是堆栈大小。当然，自 60 年前 LALR 解析器发明以来，内存限制已经大大放宽，并且查询本身通常不是“大数据”。

概念验证实验

为了对解析器可扩展性进行实验，我们实现了一个——诚然是简单化的——实验性 PEG 解析器原型，足以解析所有 TPC-H 和 TPC-DS 查询的 SQL 子集。该文法与 cpp-peglib 单头文件 C++17 PEG 执行引擎兼容。

cpp-peglib 使用稍微不同的文法语法，其中/用于表示选择。符号?表示可选元素，*定义任意重复。特殊规则Parens()和List()是简化常用元素文法的文法宏。特殊的%whitespace规则用于描述分词。

以下是我们实验性 SQL 文法的删节版，为简洁起见，省略了 Expression 和 Identifier 语法解析规则：

Statements <- SingleStmt (';' SingleStmt )* ';'* SingleStmt <- SelectStmt SelectStmt <- SimpleSelect (SetopClause SimpleSelect)* SetopClause <- ('UNION' / 'EXCEPT' / 'INTERSECT') 'ALL'? SimpleSelect <- WithClause? SelectClause FromClause? WhereClause? GroupByClause? HavingClause? OrderByClause? LimitClause? WithStatement <- Identifier 'AS' SubqueryReference WithClause <- 'WITH' List(WithStatement) SelectClause <- 'SELECT' ('*' / List(AliasExpression)) ColumnsAlias <- Parens(List(Identifier)) TableReference <- (SubqueryReference 'AS'? Identifier ColumnsAlias?) / (Identifier ('AS'? Identifier)?) ExplicitJoin <- ('LEFT' / 'FULL')? 'OUTER'? 'JOIN' TableReference 'ON' Expression FromClause <- 'FROM' TableReference ((',' TableReference) / ExplicitJoin)* WhereClause <- 'WHERE' Expression GroupByClause <- 'GROUP' 'BY' List(Expression) HavingClause <- 'HAVING' Expression SubqueryReference <- Parens(SelectStmt) OrderByExpression <- Expression ('DESC' / 'ASC')? ('NULLS' 'FIRST' / 'LAST')? OrderByClause <- 'ORDER' 'BY' List(OrderByExpression) LimitClause <- 'LIMIT' NumberLiteral AliasExpression <- Expression ('AS'? Identifier)? %whitespace <- [ \t\n\r]* List(D) <- D (',' D)* Parens(D) <- '(' D ')'

所有实验均在 2021 年的 MacBook Pro（配备 M1 Max CPU 和 64 GB 内存）上运行。实验性文法和实验代码可在 GitHub 上获取。

将基础文法从其文本表示加载到带有符号规则表示的 cpp-peglib 文法字典中需要 3 毫秒。如果该延迟成为问题，该库也允许以编程方式定义规则，而不是作为字符串。将文法文件预编译为源代码进行编译（YACC 风格）将很简单。虽然有些反直觉，但这将减少初始化原始的、未修改的解析器所需的时间。这种差异对于 DuckDB 的某些应用（例如，数据库实例仅存在几毫秒）很重要。

对于实际的解析，YACC 解析 TPC-H 查询 1 大约需要 0.03 毫秒，而 cpp-peglib 大约需要 0.3 毫秒，增加了大约 10 倍。为了进一步测试解析性能，我们将所有 TPC-H 和 TPC-DS 查询重复了六次，创建了一个 36,840 行的 SQL 脚本，大小约为 1 MB。请注意，最近的一项研究发现，Amazon Redshift 云数据仓库中 99% 的读取查询小于 16.5 kB。

Postgres 使用 YACC 解析此文件平均需要 24 毫秒。请注意，此时间包括执行创建 Postgres 解析树的文法操作的时间。cpp-peglib 解析测试文件平均需要 266 毫秒。但是，我们的实验性解析器尚未定义文法操作。当通过为每条规则生成默认 AST 操作来模拟操作时，解析时间增加到 339 毫秒。请注意，AST 生成比所需更昂贵，因为即使当前文法中没有语义含义，也会为每条匹配的规则创建一个节点。

总体而言，我们观察到使用 cpp-peglib 解析器时，解析性能下降了约 10 倍。但是，应该注意的是，这两个过程的绝对持续时间仍然很小；至少对于分析查询而言，亚毫秒级的解析时间是完全可接受的，因为解析仍然只占整个查询处理时间的一小部分。此外，我们使用现成的 PEG 库创建的实验性解析器仍然有很多优化机会。例如，该库大量使用递归函数调用，可以通过使用循环抽象等方式进行优化。

接下来，我们将介绍一些扩展原型解析器的实验，包括支持新语句、全新的语法以及改进错误消息。

替换 DuckDB 的解析器

通过提供替代解析器，已经可以替换 DuckDB 的解析器。一些社区扩展，如 duckpgq、prql 和 psql，都使用了这种方法。当尝试解析查询字符串时，DuckDB 首先尝试使用默认解析器。如果失败，它会切换到扩展解析器作为故障转移。因此，这些扩展不能简单地用几条额外规则来扩展解析器——相反，它们实现了其目标语言的完整文法。

添加 UNPIVOT 语句

假设我们想向 SQL 方言添加一个新的顶级 UNPIVOT 语句，用于将列转换为行。UNPIVOT 应该与 SELECT 等在同一级别上工作，例如，为了解构表 t1 上的特定列列表或所有列（*），我们希望能够编写：

UNPIVOTt1ON(c1,c2,c3);UNPIVOTt1ON(*);

很明显，我们必须以某种方式修改解析器以允许这种新语法。然而，当使用 YACC 解析器时，这将需要修改文法、重新运行解析器生成器、希望没有移位-归约冲突，然后重新编译实际的数据库系统。然而，这在运行时是不切实际的，而扩展正是在运行时加载的，理想情况下在几毫秒内完成。

为了添加 UNPIVOT，我们必须定义一个文法规则，然后修改SingleStmt以允许该语句出现在 SQL 语句的全局序列中。如下所示。我们通过将新的UnpivotStatement文法规则添加到字典中来定义它，然后修改字典中的SingleStmt规则条目以也允许新语句。

UnpivotStatement <- 'UNPIVOT' Identifier 'ON' Parens(List(Identifier) / '*') SingleStmt <- SelectStatement / UnpivotStatement

请注意，我们重用了文法中的其他机制，如Identifier规则以及Parens()和List()宏来定义 ON 子句。文法字典的其余部分保持不变。修改后，解析器可以在另外 3 毫秒内重新初始化。解析器执行时间不受影响。

使用 GRAPH_TABLE 扩展 SELECT

现在假设我们想修改 SELECT 语法以添加对 SQL/PGQ 图匹配模式的支持。下面是一个 SQL/PGQ 中的示例查询，用于查找所有名为 Bob 的学生的大学名称和年份：

SELECTstudy.classYear,study.nameFROMGRAPH_TABLE(pg,MATCH(a:PersonWHEREa.firstName='Bob')-[s:studyAt]->(u:University)COLUMNS(s.classYear,u.name))study;

我们可以看到，这个新语法添加了GRAPH_TABLE子句以及其中的模式匹配领域特定语言（DSL）。为了在运行时向 SQL 解析器添加对此语法的支持，我们需要修改 SELECT 语句本身的文法。使用 PEG 时，这相当简单。我们替换描述 FROM 子句的规则，使其也接受以GRAPH_TABLE关键字开头后跟括号的子文法。因为解析器不需要生成状态机，我们能够立即接受新语法。

下面我们展示了一小组文法规则，足以扩展我们的实验性解析器以支持 SQL/PGQGRAPH_TABLE子句和包含的属性图模式。通过此添加，解析器可以解析上述查询。解析器构建和解析器执行时间不受影响。

Name <- (Identifier? ':' Identifier) / Identifier Edge <- ('-' / '<-') '[' Name ']' ('->' / '-') Pattern <- Parens(Name WhereClause?) Edge Parens(Name WhereClause?) PropertyGraphReference <- 'GRAPH_TABLE'i '(' Identifier ',' 'MATCH'i List(Pattern) 'COLUMNS'i Parens(List(ColumnReference)) ')' Identifier? TableReference <- PropertyGraphReference / ...

支持 dplyr

dplyr，“数据操作文法”，是 R 统计计算环境中事实上的标准数据转换语言。该语言使用函数调用和一个特殊的管道操作符（%>%）来组合操作符。下面是一个 dplyr 查询示例：

df%>%group_by(species)%>%summarise(n=n(),mass=mean(mass,na.rm=TRUE))%>%filter(n>1,mass>50)

对于那些不熟悉 dplyr 的人来说，这个查询等价于以下 SQL 查询：

SELECT*FROM(SELECTcount(*)ASn,AVG(mass)ASmassFROMdfGROUPBYspecies)WHEREn>1ANDmass>50;

使用可扩展解析器，向 SQL 解析器添加对 dplyr 等全新查询语言的支持是可行的。下面是一个简化的文法片段，使我们的 SQL 解析器能够接受上面的 dplyr 示例。

DplyrStatement <- Identifier Pipe Verb (Pipe Verb)* Verb <- VerbName Parens(List(Argument)) VerbName <- 'group_by' / 'summarise' / 'filter' Argument <- Expression / (Identifier '=' Expression) Pipe <- '%>%' SingleStmt <- SelectStatement / UnpivotStatement / DplyrStatement

重要的是要注意，实验性 SQL 解析器的其余部分仍然有效，即 dplyr 语法现在也能工作。解析器构建和解析器执行时间再次不受影响。

更好的错误消息

如前所述，PEG 解析器能够优雅地生成更好的错误消息。一个常见的 SQL 新手用户错误是搞混查询中关键字的顺序，例如，ORDER BY必须在GROUP BY之后。假设一个缺乏经验的用户键入了以下查询：

SELECTcustomer,SUM(sales)FROMrevenueORDERBYcustomerGROUPBYcustomer;

默认情况下，YACC 和 PEG 解析器都会报告一个关于意外关键字 ‘GROUP’ 的类似错误消息，并附带字节位置。然而，使用 PEG 解析器，我们可以定义一个“恢复”语法规则，该规则将创建一条有用的错误消息。我们像这样修改实验性文法中的OrderByClause：

OrderByClause <- 'ORDER'i 'BY'i List(OrderByExpression) %recover(WrongGroupBy)? WrongGroupBy <- GroupByClause { error_message "GROUP BY must precede ORDER BY" }

在这里，我们使用%recover结构来匹配放错位置的GROUP BY子句，重用了原始定义，然后触发一条自定义错误消息，建议用户如何修复他们的查询。果然，当我们解析错误的 SQL 示例时，解析器将输出自定义消息。

结论与未来工作

在这篇文章中，我们提议使用更现代的解析器生成器（如 PEG）来现代化古老的 SQL 解析艺术。我们展示了如何使用 PEG，可以在运行时以最小的代价扩展解析器，而无需重新编译。在我们的实验中，我们展示了微小的文法调整如何从根本上扩展和改变可接受的语法。

一个显而易见的下一步是解决在我们原型中观察到的性能缺陷。使用更高效的实现技术，应该有可能缩小基于 YACC 的 LALR 解析器和动态 PEG 解析器之间的解析性能差距。另一个下一步是解决实现中的一些细节问题：例如，解析器扩展加载顺序理想情况下不应影响最终文法。此外，虽然解析器操作原则上可以执行任意代码，但可能必须对返回类型和输入处理施加限制。

我们计划在不久的将来将 DuckDB 的解析器（最初是作为 Postgres YACC 解析器的一个分支开始的）切换到 PEG 解析器。作为第一步，我们进行了一个实验，发现可以用 PEG 解释当前的 Postgres YACC 文法。这应该会大大简化过渡过程，因为它确保了两种解析框架将接受相同的文法。