来源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 单头文件 C17 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.firstNameBob)-[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_TABLEi ( Identifier , MATCHi List(Pattern) COLUMNSi Parens(List(ColumnReference)) ) Identifier? TableReference - PropertyGraphReference / ...支持 dplyrdplyr“数据操作文法”是 R 统计计算环境中事实上的标准数据转换语言。该语言使用函数调用和一个特殊的管道操作符%%来组合操作符。下面是一个 dplyr 查询示例df%%group_by(species)%%summarise(nn(),massmean(mass,na.rmTRUE))%%filter(n1,mass50)对于那些不熟悉 dplyr 的人来说这个查询等价于以下 SQL 查询SELECT*FROM(SELECTcount(*)ASn,AVG(mass)ASmassFROMdfGROUPBYspecies)WHEREn1ANDmass50;使用可扩展解析器向 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 解析器我们可以定义一个“恢复”语法规则该规则将创建一条有用的错误消息。我们像这样修改实验性文法中的OrderByClauseOrderByClause - ORDERi BYi 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。
DeepSeek总结的使用 PEG 实现运行时可扩展的 SQL 解析器
发布时间：2026/6/3 0:45:14
来源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 单头文件 C17 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.firstNameBob)-[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_TABLEi ( Identifier , MATCHi List(Pattern) COLUMNSi Parens(List(ColumnReference)) ) Identifier? TableReference - PropertyGraphReference / ...支持 dplyrdplyr“数据操作文法”是 R 统计计算环境中事实上的标准数据转换语言。该语言使用函数调用和一个特殊的管道操作符%%来组合操作符。下面是一个 dplyr 查询示例df%%group_by(species)%%summarise(nn(),massmean(mass,na.rmTRUE))%%filter(n1,mass50)对于那些不熟悉 dplyr 的人来说这个查询等价于以下 SQL 查询SELECT*FROM(SELECTcount(*)ASn,AVG(mass)ASmassFROMdfGROUPBYspecies)WHEREn1ANDmass50;使用可扩展解析器向 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 解析器我们可以定义一个“恢复”语法规则该规则将创建一条有用的错误消息。我们像这样修改实验性文法中的OrderByClauseOrderByClause - ORDERi BYi 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。
