从零到跑通 TPC-H：如何快速实现查询计划

作者：龙冉 MO 研发工程师

导读

MatrixOne 在 0.4 之前的版本中，计算引擎的整体架构是基于因子化的方案实现。然而因子化的方案缺乏通用性，例如无法支持非等值条件 join，因此在 0.5 版本开始的时候，我们正式决定放弃因子化方案，从零开始实现一个新的计算引擎。笔者当时作为新的查询计划的主要开发者之一，亲身经历了从毫无查询计划开发经验到三个月跑通 1G 数据 TPC-H。本文在此分享一些相关的经验。

Part 1 整体架构

一个 SQL 数据库的计算引擎执行过程通常分为以下几个步骤：

• Parser ：对输入的 SQL 语句做词法分析生成抽象语法树（AST）。

• Binder ：结合元信息，将表达式中的表名、列名、函数名等等，映射到数据库内部实际的对象。

• Planner ：根据绑定之后的语法树生成查询计划树。

• Optimizer ：根据优化规则和统计信息，重写等价的查询计划。

• Executor ：根据查询计划，生成具体的算子执行树并放到物理机器上执行。

生成查询计划的过程包括了 Binder/Planner/Optimizer 这 3 个部分的工作。

Part 2 Binder

Parser 的工作是对 SQL 语句字符串做词法分析，找出关键字，解析常量类型。而对非关键字非常量的字符串，Parser 并不知道它们的具体含义。Binder 作为生成查询计划的第一步，所做的就是把这些非关键字的字符串对应到数据库内部的实际对象。这个步骤的关键是正确性和健壮性，一旦完成就基本不需要后续更改。

从实现角度而言，Binder 部分的难点大概有：

• 在 SQL 语句的不同子句中，绑定的行为也不同。例如，WHERE 子句中不能出现聚合函数，LIMIT 子句中只能出现整数常量。

• 需要考虑上下文信息。例如，一旦出现了 GROUP BY 子句，SELECT 和 ORDER BY 子句中就只能出现聚合函数或者已经在 GROUP BY 子句中出现过的列名。

针对这两个问题，我们需要在不同的地方使用不同的 Binder 类，以区分不同的行为。然而这些不同的 Binder 类，在绝大多数场合的行为还是相同的，只在特定场合有所不同，例如对聚合函数的处理。最合理的方式，就是实现一个具有大部分功能的基类，其他类都派生自它且只需实现少量特殊行为即可。有人也许会疑惑，MatrixOne 是 Go 语言实现的，而 Go 语言本身没有类继承的概念。其实 Go 语言也完全可以模拟出类继承和函数重载的效果。

以代码说明：

type Binder interface {  BindExpr(tree.Expr, int32, bool) (*plan.Expr, error)  BindColRef(*tree.UnresolvedName, int32, bool) (*plan.Expr, error)  BindAggFunc(string, *tree.FuncExpr, int32, bool) (*plan.Expr, error)  BindWinFunc(string, *tree.FuncExpr, int32, bool) (*plan.Expr, error)  BindSubquery(*tree.Subquery, bool) (*plan.Expr, error)  GetContext() context.Context}
type baseBinder struct {  ...}
type WhereBinder struct {  baseBinder}
type GroupBinder struct {  baseBinder}
type HavingBinder struct {  baseBinder  insideAgg bool}
var _ Binder = (*WhereBinder)(nil)var _ Binder = (*GroupBinder)(nil)var _ Binder = (*HavingBinder)(nil)...

对于“聚合函数在大多数子句中都不允许出现”这样的行为，我们可以把“基类”baseBinder 的 BindAggFunc 实现为直接报错，然后 WhereBinder 和 GroupBinder 不实现 BindAggFunc 方法，于是在调用 whereBinder.BindAggFunc 的时候，实际调用的是它的第一个匿名成员，也就是 baseBinder 的同名方法。而对于允许聚合函数的 HAVING 子句，我们单独实现 havingBinder.BindAggFunc 方法。这样通过充分利用 Go 语言的特性，我们也实现了类似 C++的派生类若不实现某方法就调用基类方法的行为。

Binder 还有一个容易出错的地方是星号（*）展开结果中各列的顺序。例如有 t1(a, b, e), t2(b, c, d), t3(c, d, e) t4(d, e, f)四张表，以下查询的结果各列的顺序应该是怎样？

SELECT*FROM (t1 JOIN t2 USING(b)) JOIN (t3 JOIN t4 USING(d)) USING(e, c)

有兴趣的读者可以去尝试一下。笔者当初参考过的 DuckDB，对这个问题的处理一直有 bug。

Part 3 Planner

绑定做好之后，Planner 要做的工作其实不多，就是按如下的 SQL 语句各子句逻辑执行顺序，把不同的关系代数结点拼接成一棵查询计划树。

1. From

2. Where

3. Group by

4. Having

5. Window

6. Qualify

7. Distinct

8. Order by

9. Limit

这样就结束了吗？不全是。如果要跑通 TPC-H 的话，我们还漏掉了一个重要的问题：子查询。在绑定阶段，子查询会被递归处理，然后转化为一个特殊的表达式。在生成的查询计划树里，我们当然也可以把子查询直接放进去，然而这样生成的计划是无法被执行器执行的！原则上来说，一个完备的 Planner，即使没有后面优化器，生成的计划也必须是可执行的，因此需要对子查询做一些额外的处理。

对子查询的处理，最理想的方式就是完全消除子查询，将其转化为各种 join 结点，这样通常能达到把时间复杂度从 O(m * n)降到 O(m + n)的效果。然而在 2015 年那篇著名的 Unnesting Arbitrary Queries 出现之前，并没有一种方法能解开所有的子查询，因此各家数据库对无法解开的子查询仍然保留了以嵌套方式执行的算子，一般称作 apply join。

我们当初考察了各种解开子查询的方法，并考虑时间的紧迫性，以及短期目标只是 TPC-H，最后决定只实现把关联列过滤条件上拉的方法。这个方法的局限性是不能解开关联列深度大于 1，或者关联列出现在非等值条件的子查询，但是已经足够覆盖绝大多数的用户使用场景。

举例说明：

SELECT ...FROM part, partsuppWHERE p_partkey = ps_partkeyAND ps_supplycost = (SELECT min(ps_supplycost) FROM partsupp WHERE p_partkey = ps_partkey)

这是截取 TPC-H q2 的一部分。MatrixOne 采用的方法会生成类似如下的执行计划：

• project: ...

• join: ps_partkey = ps1.ps_partkey, ps_supplycost = min(ps1.ps_supplycost)

• join: p_partkey = ps_partkey

• scan: part

• scan: partsupp

• agg: min(ps_supplycost) group by ps1.ps_partkey

• scan: partsupp ps1

另一个基于 TPC-H q21 的例子：

SELECT ...FROM l1WHERE exists (SELECT * FROM l2 WHERE l1_key = l2_key)

会被展开成为

• project: ...

• semi join: l1_key = l2_key

• scan: l1

• scan: l2

Part 4 Optimizer

对数据库引擎来说，优化器是一个永无止境的任务。但是在一个版本迭代的过程中，我们能做的事情非常有限。所幸只是为了跑通 TPC-H 需要的优化器规则不多，必要的只有这四条：

1. 列裁剪

2. and-or 分配律

3. 简单的贪心法 join order

4. SELECT 子句中定义的别名

列裁剪不用多说，如果不做的话会导致磁盘 IO 和内存占用增长数倍。分配律是跑 q19 所必需，也不用多说，大家看看下面的 q19 就明白。若没有实现分配律，就是笛卡尔积加过滤，实现了之后才可以转成等值 join，并且多个过滤条件可以下推。这两条规则行为很确定，一旦写好也不用更改。

select  sum(l_extendedprice* (1 - l_discount)) as revenuefrom  lineitem,  partwhere  (    p_partkey = l_partkey    and p_brand = 'Brand#23'    and p_container in ('SM CASE', 'SM BOX', 'SM PACK', 'SM PKG')    and l_quantity >= 5 and l_quantity <= 5 + 10    and p_size between 1 and 5    and l_shipmode in ('AIR', 'AIR REG')    and l_shipinstruct = 'DELIVER IN PERSON'  )  or  (    p_partkey = l_partkey    and p_brand = 'Brand#15'    and p_container in ('MED BAG', 'MED BOX', 'MED PKG', 'MED PACK')    and l_quantity >= 14 and l_quantity <= 14 + 10    and p_size between 1 and 10    and l_shipmode in ('AIR', 'AIR REG')    and l_shipinstruct = 'DELIVER IN PERSON'  )  or  (    p_partkey = l_partkey    and p_brand = 'Brand#44'    and p_container in ('LG CASE', 'LG BOX', 'LG PACK', 'LG PKG')    and l_quantity >= 28 and l_quantity <= 28 + 10    and p_size between 1 and 15    and l_shipmode in ('AIR', 'AIR REG')    and l_shipinstruct = 'DELIVER IN PERSON'  );

重点谈一下 join order。

在 0.5 版本周期内，我们元数据里能拿到的除了每张表的行数，没有任何其他的统计信息，连 zonemap 都没有。这样能怎么做 join order 呢？第一时间能想到的无非是，把所有表按行数排序，在避免出现笛卡尔积的条件下，从小到大一个个 join 起来形成一个右深树（我们的执行器是以右表建哈希表以左表探测）。1G 数据 TPC-H 这个目标还是比较仁慈，这样就已经可以在可忍受的时间内跑通绝大多数查询了。除了 q5……

经过分析后我们发现，在 q5 中，有一个把 customer 和 supplier 两张表连接起来的条件 c_nationkey = s_nationkey。而由于这两张表都是比较小的表，这会导致我们第一版贪心 join order 算法很早就把这两张表 join 起来。然而 nationkey 的基数非常小，导致两张小表做 join 之后结果行数膨胀到数亿，比最大的表 lineitem 还高两个数量级。而在后续的 join 算子中，又不止一次拿这几亿行的结果去建哈希表，因此执行速度慢到无法忍受。

更多的分析之后，我们仍然找到了解决的途径：TPC-H 的主键约束。对 join order 来说，即使没有任何统计信息，主键约束也是一个非常强的提示。无论多大的两张表做 join，一旦等值 join 条件包含某张表所有的主键列，结果的行数都不会超过另一张表的行数。当时我们的存储引擎也在同时重写，尚未实现主键约束，因此主键这个信息最初被我们忽视。发现这一问题后，我们很快实现出第二版贪心法 join order：

1. 用所有带主键的 join 条件生成一棵或多棵有向树（polytree）。

2. 对每棵有向树，从根节点开始，先递归把所有子结点处理完成，再把当前结点依次和所有子结点生成的 join 结点做 join。

3. 对这些有向树的根节点，使用第一版的贪心法生成右深树

改进的贪心法很好地解决了 q5 的问题，并且 q9 的性能也得到了很大的改善。至此跑通 1G 数据 TPC-H 的目标成功达成！

Part 5 小结

本文简单介绍了如何完成在两三个月内从零开始实现查询计划系统，并且在 1G 数据集上跑通 TPC-H 全部查询这样一个事先看起来不可能完成的任务。接近一年后来回顾，我们仍然对当时几位同事通力合作付出的艰辛，不断踩坑时的沮丧，以及达到目标后的惊喜深有感触。这段经历也持续激励我们在数据库基础软件这个方向上继续努力。

# 参考文献

• Unnesting Arbitrary Queries, https://btw-2015.informatik.uni-hamburg.de/res/proceedings/Hauptband/Wiss/Neumann-Unnesting_Arbitrary_Querie.pdf
  

• The Complete Story of Joins (in HyPer), https://15721.courses.cs.cmu.edu/spring2018/papers/16-optimizer2/hyperjoins-btw2017.pdf
  

• Orthogonal Optimization of Subqueries and Aggregation, https://www.comp.nus.edu.sg/~cs5226/papers/subqueries-sigmod01.pdf
  

• Query Optimization Technology for Correlated Subqueries, https://www.alibabacloud.com/blog/query-optimization-technology-for-correlated-subqueries_597644
  

• DuckDB, https://github.com/duckdb/duckdb and https://duckdb.org/news/