SQL 引擎的解剖

Anatomy of a SQL Engine

Source | HN Comments

文章剖析了 SQL 引擎的内部运作，从查询的接收到结果的输出，详细阐述了其关键步骤。首先，SQL 引擎对查询进行解析，生成抽象语法树 (AST)。接着，进行绑定，将 AST 中的标识符与数据库目录中的符号匹配。然后，通过计划简化规范化语法，并进行类型强制转换。计划探索阶段包括连接搜索和成本估算，以优化查询执行。最后，执行阶段将计划转换为可执行格式，并进行 IO/假脱机操作，将结果返回给客户端。文章还提到了未来的改进方向，包括统一中间表示和优化内存管理。

Blog

SQL 引擎的解剖

Max Hoffman 2025年4月25日 REFERENCESQL 阅读时长 13 分钟

五月标志着 Dolt 采用 go-mysql-server 五周年。今天，我们将通过一个查询从解析到结果假脱机的整个过程，来总结 GMS 的当前状态。

概述

SQL 引擎是数据库的逻辑层，位于客户端和存储之间。为了代表客户端改变数据库状态，SQL 引擎执行以下步骤：

解析 (Parsing)
绑定 (Binding)
计划简化 (Plan Simplification)
连接探索 (Join Exploration)
计划成本估算 (Plan Costing)
执行 (Execution)
结果假脱机 (Spooling Results)

大多数系统还有各种执行策略（基于行 vs 基于向量）和基础设施层（本地运行 vs 分布式运行）。目前，Dolt 的引擎默认在本地服务器中使用基于行的执行。

解析

SQL 引擎接收到查询后，首先尝试形成结构化的抽象语法树 (AST)。AST 是对查询是否格式良好的一个初步判断。解析器的入口点是这里。

客户端驱动程序通过网络将字节流传递给服务器监听器，然后进入 ComHandler 命令来初始化查询。处理程序积累数据，直到到达分隔符 token（通常是 ;）。然后，该字符串被分割成以空格分隔的 token，并输入到解析器中。下图显示了从字节到 token，最终到 AST 节点的移动过程：

右递归解析易于理解和调试，因为程序是一个决策树，它根据前瞻 token 选择下一个路径。因此，右递归解析器最初可能期望一个 SELECT，然后累积选择表达式，直到遇到 FROM token，等等。之所以称之为“右递归”，是因为当我们遇到类似 join 的情况时，我们会贪婪地累积 table token，并不断将解析状态推向更深层。但是，右递归解析器是自上而下的，不幸的是，它使用的堆栈内存与 token 的数量成正比。

相反，左递归解析器是自下而上的，当它们找到一个满足条件的模式时，会积极地折叠累积的堆栈。因此，当我们看到 join 时，我们会在检查更多 table 之前折叠到目前为止的 join。这降低了内存使用量，但代价是决策标准变得更加复杂。

Dolt 的 Yacc 语法是左递归的，即使 shift（添加 token）reduce（折叠 token 堆栈）逻辑难以调试，执行速度也很快。Yacc 允许我们在堆栈折叠 (reduce) 钩子中进行一些小的格式化。下面的规则显示了从工程师/语义角度来看，“左递归折叠”的简化细节：

table_reference:
 table_factor
| join_table
table_factor:
 aliased_table_name
 {
  $$ = $1.(*AliasedTableExpr)
 }
| openb table_references closeb
 {
  $$ = &ParenTableExpr{Exprs: $2.(TableExprs)}
 }
| table_function
| json_table
join_table:
 table_reference inner_join table_factor join_condition_opt
 {
  $$ = &JoinTableExpr{LeftExpr: $1.(TableExpr), Join: $2.(string), RightExpr: $3.(TableExpr), Condition: $4.(JoinCondition)}
 }
join_condition_opt:
%prec JOIN
 { $$ = JoinCondition{} }
| join_condition
 { $$ = $1.(JoinCondition) }
join_condition:
 ON expression
 { $$ = JoinCondition{On: tryCastExpr($2)} }
| USING '(' column_list ')'
 { $$ = JoinCondition{Using: $3.(Columns)} }

table_reference 是行源（table scan 或 join）的 umbrella 表达式。join_table 是两个或多个用 JOIN 子句连接的 table，递归的 table_reference 部分位于左侧而不是右侧。当堆栈的头部匹配 join_table 的定义时，我们会弹出这些堆栈组件，执行回调钩子，并将这些组件替换为堆栈上的单个 *JoinTableExpression。join 树本身是右深的，因为旧状态将是左节点，新状态将是递归调用中的右节点。未删节的版本在这里。

如果解析成功，则保证输出的 AST 与我们的 Yacc 规则的结构匹配。如果解析失败，客户端会收到一个错误，指示查询字符串中哪个前瞻 token 无效。

绑定

查询解析仅部分检查查询是否格式良好。AST 中的字段仍然需要与当前数据库 catalog 中的符号匹配，此外还需要进行大量的类型检查和特定于子句的检查。我们将这个阶段称为“绑定”，因为它的核心中间表示是为了命名空间作用域而设计的（代码入口点在这里）。

将 AST 标识符绑定到 catalog 符号类似于在任何编程语言中定义和引用变量。Table 和别名创建 column 变量，column 字段引用这些变量。从行源/行接收的角度来看，我们可以考虑大约四个核心对象。

Table 定义是提供许多行/列的源。Table 名称不能在同一作用域内冲突（例如：select * from mydb.mytable.xy join xy on x），但在其他情况下是全局可访问的。子查询是一种特殊的表达式，它添加了一个额外的命名空间层，但在其他方面就像 table 源一样：select sq.a from (select x as a from xy) sq。

Column 定义是引用行源中特定列的接收器。具有两个原本不明确的列名的作用域中的引用必须限定 table 才能消除其标识的歧义。例如，select * from xy a join xy b where x = 2 会出错，因为 x = 2 过滤器中的列引用缺少 table 限定符。

别名是标量接收器和源，这有点不寻常。对于源中的每一行，它们输出一个值。这意味着我们添加了可供引用的 column 定义，但仅在原始作用域的边界处。例如，select x+y as a from xy where a > 2 会出错，因为 a 定义是在过滤器/投影之后定义的和创建的。具有 having a > 2 的相同查询是有效的，因为 HAVING 可以访问具有 a 别名的第二个作用域。

标量子查询是源和接收器。它们类似于别名，但增加了一个复杂性，即子查询作用域都共享父作用域。多个作用域为名称绑定添加了一个层次结构，但在其他方面是直观的：在当前作用域中搜索名称匹配项，然后向上迭代，直到找到具有适当定义的作用域。公共名称不能在作用域之间冲突，只能在作用域内冲突。select (select a.x from xy b) from xy a 是有效的，因为即使在 b 作用域中找不到 a.x 变量，a 父作用域也提供了绑定。

公共表表达式 (CTEs) 和子查询别名是相同命名空间规则的简单扩展。关于 GROUP BY 和选择列的哪些组合有效，聚合具有相当具体的规则，我们这里不讨论。

binding 阶段将 AST 节点转换为自定义的 go-mysql-server sql.Node 计划节点作为输出。

计划简化

简化将 SQL 丰富的语法规范化为狭窄的格式。理想情况下，所有逻辑上等效的计划都将汇集到一个通用形状中。 “规范”形式应该是最不令人惊讶且执行速度最快的。实际上，完美的简化是一个理想的目标，随着工作负载复杂性的增加，它会随着时间的推移而得到改进。代码入口点是这里。当前规则列表位于此文件中。

计划节点以一种适合查询转换的格式保存了在绑定期间计算出的正确性信息。从技术上讲，这是我们的第三个中间表示 (IR)，在 AST 和作用域层次结构之后。简化规则始终会触发，因为它们以编译器优化（例如死代码消除和表达式折叠）的方式提高了查询运行时。一些有据可查的 SQL 简化是过滤器下推和列修剪，它们在执行期间尽早丢弃未使用的行和列（分别）。

我们有数十个简化规则，其中大多数都符合狭窄的模式匹配 => 重新排列流程。该结构非常标准化，以至于 CockroachDB 专门为转换编写了 DSL。这些规则很简单并且很少更改，因此我们手动完成，但对于那些想要了解更多信息的人来说，形式化很有趣。

一个值得注意的打破常规的转换是子查询去关联/应用连接。类似 select * from xy where x = (select a from ab) 的查询等效于 select * from xy join ab on x = a。将 table 关系、过滤器和投影折叠到通用作用域中总是会导致更好的连接计划，并且通常会导致额外的作用域内简化。更多正式规范可以在这里和这里找到。

类型强制转换

同一表达式的类型根据调用上下文而变化。例如，插入中的表达式可以强制转换为目标列类型，而 WHERE 过滤器表达式可以强制转换为布尔值。Dolt 的 SQL 引擎越来越多地使用自上而下的强制转换提示将类型转换从执行转移到绑定。类型转换通常是一个单独的编译器阶段，因为它共享绑定和简化的属性。我们在语义上验证查询的类型一致性和正确性，同时以一种将工作从执行引擎卸载的方式简化表达式。

计划探索

查询计划的最简单形式通常是执行速度最快的。但是，连接、聚合和窗口通常有几种等效的变体，其性能取决于数据库。

计划探索有两个可分离的组件：搜索和成本估算。搜索枚举所有产生逻辑上等效结果的有效连接配置。逻辑变体包括顺序重新排列（A x (B x C) = > (C x A) x B）和运算符选择（LOOKUP_JOIN vs HASH_JOIN vs ...）。成本估算估计特定（物理）计划配置的运行时成本。

连接搜索

在连接顺序探索中，有两种策略。第一种策略在种子计划上迭代执行有效的排列，记忆路径以避免重复工作。当我们用完排列或者确定我们已经找到最佳计划时，搜索终止。搜索入口点是这里。

自上而下的回溯策略与自下而上的动态编程 (DP) 形成对比，在动态编程中，我们迭代每个可能的连接顺序。首先，我们尝试每个两表连接配置，然后尝试每个三表组合，依此类推，一直到所有 n 表。

回溯仅访问有效状态，但 DP 需要检测所有组合的冲突。例如，对于 A LEFT JOIN B，我们将使任何违反 A < B 的顺序无效。这意味着如果我们的搜索不够远，回溯可能会错过好的计划。DP 无效标准可能太宽泛而拒绝有效计划，或者存在漏洞并意外接受无效计划。GMS 当前使用第二种策略，其中包含一个 DP-Sube 冲突检测器，该检测器比回溯达到更多的重新排列，而不会牺牲正确性。

除了默认的 INNER_JOIN 计划之外，每个有效的顺序都会扩展以考虑 LOOKUP_JOIN、HASH_JOIN 和 MERGE_JOIN 等等。

一个未被充分重视的值得注意的点是用于累积探索状态（连接顺序）的中间表示。提醒一下，DP 子问题的最优性条件是：

可以根据连接状态产生的结果，将连接状态逻辑地聚类成组。
连接组始终由两个较小的逻辑连接组组成。

有各种词语用于描述这个问题（超图 = 图的图，森林 = 树的树），但 memo 是我们看到的最常见的术语，因此我们坚持使用它。memo 组包含所有产生相同结果的搜索状态（连接顺序），因此由组中节点 ID 的位图 AND 标识。特定的搜索状态是两个表达式组和一个物理运算符，它终止 table 源组。

select * from join ab, uv, xy where a = u and u = x; 的初始 memo 如下所示：

memo:
├── G1: (tableScan: ab)
├── G2: (tableScan: uv)
├── G3: (innerJoin 2 1) (innerJoin 1 2)
├── G4: (tableScan: xy)
├── G5: (innerJoin 3 4) (innerJoin 6 1)
└── G6: (innerJoin 4 2)

每个 table 获得一个逻辑表达式组。每个 2 路连接获得一个表达式组（我们使用传递属性链接 a=x）。它们都汇集到 G5 中的顶级连接中。

这种组织使我们能够在组级别缓存逻辑属性，其中最值得注意的是最低成本的物理计划。激励 memo 的子问题最优性愉快地适用于连接重新排序和成本估算。

函数依赖

对于 5+ 表连接，探索可能很昂贵。幸运的是，大型连接通常具有星型模式的主键 (t1 join t2 on pk1 = pk2) 连接。如果所有连接运算符都通过“严格键”（唯一且非空的 1 对 1 关系）连接，则按 table 大小对树进行排序并使用 LOOKUP_JOIN 运算符连接计划通常是有效的。输出行数（基数）限制为第一个/最小的行源的大小。 Nick 在这里更多地讨论了用于连接计划的函数依赖分析。函数依赖代码位于这里。

IR 中场休息

这是自解析 AST 以来我们取得的进展：

第一个 IR 将列定义分组到作用域中，这有助于验证和绑定字段引用。第二个 IR 允许我们对简化的计划执行结构优化。第三个 IR 适应了探索连接重新排序的方式，这有助于我们的下一个主题，即连接成本估算。

连接成本估算

连接成本估算识别在探索期间枚举的每个逻辑表达式组中最快的物理计划。成本估算器的入口点是这里。

我们有很多博客详细介绍了连接成本估算（链接集合在这里）。总结是，模式和 table 键分布会影响连接成本。A JOIN B 可能在一个数据库中返回 10 行，而在另一个数据库中返回 1000 万行。10 行连接可能会使用 LOOKUP_JOIN 来优化延迟，而 1000 万行连接可能会使用 HASH JOIN 来优化吞吐量。我们将索引键分布表示为直方图。相交的直方图大致近似结果关系的计数和新的键分布。 (1) 输入大小、(2) 结果大小、(3) 运算符选择的组合为我们提供了 (1) 从磁盘拉取行所需的 IO 工作、(2) 运算符特定数据结构（例如：哈希映射）的内存开销和 (3) 用于读取 table 源以生成结果计数的近似 CPU 周期。

以下是我们的查询的扩展成本树的样子：

tmp2/test-branch*> select dolt_join_cost('SELECT * FROM xy WHERE EXISTS ( select 1 from uv where u = x )');
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| dolt_join_cost('SELECT * FROM xy WHERE EXISTS (  select 1  from uv  where   u = x )')                                        |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| memo:                                                                                   |
| ├── G1: (tablescan: xy 0.0)*                                                                       |
| ├── G2: (tablescan: uv 0.0)*                                                                       |
| ├── G3: (lookupjoin 1 2 6.6) (lookupjoin 6 1 6.6) (project: 5 0.0) (semijoin 1 2 4.0)*                                          |
| ├── G4: (project: 2 0.0)*                                                                         |
| ├── G5: (hashjoin 1 4 8.0) (hashjoin 4 1 8.0) (mergejoin 1 4 4.1) (mergejoin 4 1 4.1) (lookupjoin 1 4 6.6) (lookupjoin 4 1 6.6) (innerjoin 4 1 5.0)* (innerjoin 1 4 5.0)* |
| └── G6: (project: 2 0.0)*                                                                         |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

每个逻辑表达式组 (G) 的物理实现选项现在都具有关联的成本。例如，第一个 G3 实现是 G1 和 G2 之间的 LOOKUP_JOIN，我们估计成本为 6.6 个单位。我们区分 (1) 连接运算符执行的增量工作和 (2) 选择及其依赖项的累积成本。我们打印增量工作而不是累积工作，尽管我们可能会通过打印两者来改进此功能。

一个需要注意的是，Dolt 收集确定性的 table 统计信息。大多数数据库使用近似草图来 (1) 加快刷新时间、(2) 最小化后台工作 IO 开销、(3) 使估算快速和 (4) 使组合高阶综合连接估算更容易。Dolt 的内容可寻址存储引擎使得刷新仅读取数据库的一小部分（对于读取繁重的工作负载更真实）相对容易。确定性对于可预测性也是极好的。实际上，对于我们的在线分析处理 (OLAP) 工作负载，估算开销或高阶估算没有性能瓶颈。

当连接成本估算完成时，我们已经发现了最佳执行策略。

连接提示

成本估算器尽最大努力满足查询中 SELECT token 之后指示的连接提示。文档更详细地介绍了提示选项和用法。源代码位于这里。相互矛盾或逻辑上无效的提示通常会被忽略。

执行

最终计划需要转换为可执行格式。

Dolt 的默认行执行格式反映了计划节点格式。下面的计划将共享一个相同形状的 volcano 迭代器：

tmp2/test-branch*> explain plan select count(*) from xy join uv on x = u;
+----------------------------------------+
| plan                  |
+----------------------------------------+
| Project                |
| ├─ columns: [count(1)]        |
| └─ GroupBy              |
|   ├─ SelectedExprs(COUNT(1))    |
|   ├─ Grouping()           |
|   └─ MergeJoin           |
|     ├─ cmp: (xy.x = uv.u)     |
|     ├─ IndexedTableAccess(xy)   |
|     │  ├─ index: [xy.x]     |
|     │  ├─ filters: [{[NULL, ∞)}] |
|     │  └─ columns: [x]      |
|     └─ IndexedTableAccess(uv)   |
|       ├─ index: [uv.u]     |
|       ├─ filters: [{[NULL, ∞)}] |
|       └─ columns: [u]      |
+----------------------------------------+

即使我们将 GMS 迭代器与 Dolt 自定义的 kvexec 迭代器交换（例如，在这里），在 KV 层上运行的抽象迭代器仍然是 volcano 迭代器。

有一个值得注意的预迭代器转换。在绑定中创建的列引用需要从逻辑标识符转换为基于偏移量的索引访问。简化和连接探索可以自由移动表达式，但执行需要知道值位于数据层的什么位置。此分析器规则设置执行索引。

非物化迭代器从子迭代器中提取并立即返回一行。物化迭代器必须读取一系列子项才能返回。下面的 groupByIter 显示了 GROUP_BY 如何将所有子行 (i.child.Next) 馈送到缓冲区聚合器 (updateBuffers) 中，然后再返回任何行 (evalBuffers)（源代码在这里）：

func (i *groupByIter) Next(ctx *sql.Context) (sql.Row, error) {
	for {
		row, err := i.child.Next(ctx)
		if err != nil {
			if err == io.EOF {
				break
			}
			return nil, err
		}
		if err := updateBuffers(ctx, row); err != nil {
			return nil, err
		}
	}
	row, err := evalBuffers(ctx, i.buf)
	if err != nil {
		return nil, err
	}
	return row, nil
}
func updateBuffers(
	ctx *sql.Context,
	buffers []sql.AggregationBuffer,
	row sql.Row,
) error {
	for _, b := range buffers {
		if err := b.Update(ctx, row); err != nil {
			return err
		}
	}
	return nil
}
func evalBuffers(
	ctx *sql.Context,
	buffers []sql.AggregationBuffer,
) (sql.Row, error) {
	var row = make(sql.Row, len(buffers))
	var err error
	for i, b := range buffers {
		row[i], err = b.Eval(ctx)
		if err != nil {
			return nil, err
		}
	}
	return row, nil
}

我们执行运行时的一个缺点是在运行时动态构造相关查询。相关子查询最初仍然在执行期间表示为计划 IR。运行时在构造新迭代器之前，将作用域的上下文添加到嵌套查询计划中的 table 源。我们不会在这里讨论细节。

IO/假脱机

前一个阶段的 volcano 迭代器产生需要转换为结果格式的结果行。主要代码入口点是这里。

从存储读取和写入网络在概念上是相似的，即使它们位于查询生命周期的两端。数据在存储、运行时和连线时间格式之间移动的方式与查询计划通过不同的中间表示移动的方式相同。Dolt 的分层存储具有各种真实的字节布局，但我们通常将所有这些称为键值 (KV) 层。行在 KV 层中表示为字节数组键/值对。任何 table 集成器 (KV 层) 都通过 Go 本机类型的内存数组与 GMS 接口。最后，MySQL 的连线格式与 KV 或 SQL 格式完全不同！例如，整数在连线格式中表示为字符串。

批处理和缓冲区重用有助于管理这些接口中每一个接口的吞吐量和内存 churn。减少中间人和从 KV->连线层转换是许多查询的有效优化。返回一行的查询很常见，并且具有专门的假脱机接口，这些接口针对延迟而不是吞吐量进行了优化。

客户端协议收集结果字节，直到发送终端数据包，终止命令并释放会话以开始另一个查询。

未来

AST 是用于组织 token 字节的绝佳中间表示，但缺乏语义验证、计划简化和连接计划所需的表达能力。为每个阶段构建额外的 IR 产生了一个组织和性能问题，只有统一才能解决。我们将 SQL 节点上的大部分逻辑重新分配到前面的（绑定）或后面的（memo）阶段。但是缩小差距仍然非常困难，并且可能涉及 (1) 将所有子查询表达式重写为横向连接和 (2) 将别名表示为 SyntheticProject 节点，这些节点将一个列定义附加到树。

Golang 的自动内存管理帮助我们快速启动并运行一个功能齐全的数据库，但内存 churn 仍然是一个瓶颈