运行时可扩展的 SQL 解析器（使用 PEG）

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

解析器是 DBMS 的一个组件，负责将字符串格式的查询转换为通常为树状的内部表示。解析器定义了哪些查询将被接受。每条 SQL 查询的旅程都始于解析器。尽管它在技术栈中占据着重要位置，但关于数据管理系统查询解析的研究却很少。在过去的几十年里，这个主题似乎进展甚微，它们的实现很大程度上停留在六十年前的抽象和技术中。

随着 SQL 规范不断增长的利基功能（例如，SQL/PGQ 中的图查询支持或 XML 支持），以及支持替代查询表示法（如 dplyr、管道 SQL、PRQL 或 SaneQL）的愿望，使得单一的解析器越来越不实用：在其传统设计中，解析器构建是一个编译时活动，巨大的文法文件被转换为状态机转换查找表，然后固化到系统二进制文件中。让这些内容始终存在于解析器中可能会造成浪费，特别是对于对大小敏感的二进制分发，如 WebAssembly (Wasm)。

许多（如果不是大多数）SQL 系统都使用通过 YACC 风格的解析器工具包创建的静态解析器：我们可以轻松地在 PostgreSQL 和 MySQL/MariaDB 等开源系统中证实这一点。通过分析其二进制文件的符号名，我们还发现 Oracle、SQL Server 和 IBM Db2 使用 YACC。在内部，YACC 及其稍新的变体 GNU Bison，以及 SQLite 使用的“Lemon”解析器生成器，都使用“单向前瞻从左到右最右推导”（single look-ahead left-to-right rightmost derivation）LALR(1) 解析器生成器。这个生成器将扩展巴科斯-瑙尔范式（EBNF）中的形式上下文无关文法规则集转换为解析器状态机。LALR 解析器是 Knuth 最早描述的 LR(k) 解析器的一种更节省空间的特化。但实际上，2024年最先进的 SQL 系统仍在采用上世纪60年代的解析器技术。考虑到自那时以来数据管理系统的其他部分已经进行了重大改造，这应该引发一个问题：为什么解析器没有受到任何认真的工程关注。

数据库系统正朝着成为生态系统而非预构建的整体式系统发展。PostgreSQL、SQLite 和 DuckDB 社区的许多创新现在都来自于扩展，这些扩展是运行时加载到数据库系统中的共享库，用于扩展数据库系统，提供诸如向量相似度搜索、地理空间支持、文件系统或图处理等功能。预先捆绑所有这些功能会因为额外的二进制大小和外部依赖而变得困难。此外，它们通常由各自的社区独立维护。迄今为止，至少部分由于 YACC 风格解析器的普遍性，这些社区扩展在语法扩展方面受到了限制。尽管这在 Python 等其他生态系统中也是如此，但 SQL 的设计侧重于语法而非函数调用，使得扩展成为“二等公民”，必须通过某种方式规避原始解析器的限制，例如通过在字符串中嵌入自定义表达式。

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

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

You have an error in your SQL syntax; check the manual that corresponds
to your MySQL server version for the right syntax to use near 'SELEXT'
at line 1.

解析表达式文法

解析表达式文法 (PEG) 解析器代表了一种更现代的解析方法。PEG 解析器是自顶向下的解析器，能有效地从文法生成递归下降风格的解析器。通过“packrat”备忘录技术，PEG 解析器在解析时表现出线性时间复杂度，但代价是需要额外取决于文法大小的内存。从文法作者的角度来看，最大的区别在于选择运算符，它可以匹配多个语法选项。在 LALR 解析器中，具有相似语法的选项可能会产生歧义并减少冲突。在 PEG 解析器中，总是选择第一个匹配的选项。因此，PEG 解析器在设计上不会产生歧义。

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

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

PEG 解析器的另一个巨大优势是错误处理：论文《解析表达式文法中的语法错误恢复》描述了一种实用的技术，其中解析器规则可以标注“恢复”动作，这些动作可以（1）显示多个错误，并且（2）用更有意义的错误消息来标注错误。

备忘录化 packrat 解析的一个可能缺点是备忘录化所需的内存：所需内存量与输入大小成正比，而非堆栈大小。当然，自六十年前 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 ')'

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

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

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

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

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

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

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

添加 UNPIVOT 语句

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

UNPIVOT t1 ON (c1, c2, c3);
UNPIVOT t1 ON (*);

显然，我们必须以某种方式修改解析器以允许这种新语法。然而，当使用 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 的学生的大学名称和年份：

SELECT study.classYear, study.name
FROM GRAPH_TABLE (pg,
    MATCH
        (a:Person WHERE a.firstName = 'Bob')-[s:studyAt]->(u:University)
        COLUMNS (s.classYear, u.name)
) study;

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

下面我们展示了一小组文法规则，它们足以扩展我们的实验性解析器，使其支持 SQL/PGQ GRAPH_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，即“数据操作文法”（Grammar of Data Manipulation），是 R 统计计算环境中事实上的数据转换标准语言。该语言使用函数调用和一个特殊的链式操作符 (%>%) 来组合操作符。下面是一个 dplyr 查询示例：

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

对于不熟悉 dplyr 的人来说，该查询等同于以下 SQL 查询：

SELECT * FROM (
    SELECT count(*) AS n, AVG(mass) AS mass
        FROM df
        GROUP BY species)
    WHERE n > 1 AND mass > 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 之后。假设一个经验不足的用户输入了以下查询：

SELECT customer, SUM(sales)
FROM revenue
ORDER BY customer
GROUP BY customer;

默认情况下，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 文法。这应该会大大简化转换过程，因为它确保了相同的文法将在两种解析框架中都被接受。

致谢

我们衷心感谢 Torsten Grust、Gábor Szárnyas 和 Daniël ten Wolde 提供的宝贵建议。我们还要感谢 Carlo Piovesan 将 Postgres YACC 文法翻译成 PEG。