从零到跑通TPC-H：如何快速实现查询计划
作者：龙冉 MO研发工程师
导读
MatrixOne在0.4之前的版本中，计算引擎的整体架构是基于因子化的方案实现。然而因子化的方案缺乏通用性，例如无法支持非等值条件join，因此在0.5版本开始的时候，我们正式决定放弃因子化方案，从零开始实现一个新的计算引擎。笔者当时作为新的查询计划的主要开发者之一，亲身经历了从毫无查询计划开发经验到三个月跑通1G数据TPC-H。本文在此分享一些相关的经验。
下面是本文目录概览：
1.
整体架构
2.
Binder
3.
Planner
4.
Optimizer
5.
小结
本文字数：2800字+ 阅读时间：5分钟+
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 {baseBinderinsideAgg 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语句各子句逻辑执行顺序，把不同的关系代数结点拼接成一棵查询计划树。
From
Where
Group by
Having
Window
Qualify
Distinct
Order by
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需要的优化器规则不多，必要的只有这四条：
列裁剪
and-or分配律
简单的贪心法join order
SELECT子句中定义的别名
列裁剪不用多说，如果不做的话会导致磁盘IO和内存占用增长数倍。分配律是跑q19所必需，也不用多说，大家看看下面的q19就明白。若没有实现分配律，就是笛卡尔积加过滤，实现了之后才可以转成等值join，并且多个过滤条件可以下推。这两条规则行为很确定，一旦写好也不用更改。
selectsum(l_extendedprice* (1 - l_discount)) as revenuefromlineitem,partwhere(p_partkey = l_partkeyand p_brand = 'Brand#23'and p_container in ('SM CASE', 'SM BOX', 'SM PACK', 'SM PKG')and l_quantity >= 5 and l_quantity <= 5 + 10and p_size between 1 and 5and l_shipmode in ('AIR', 'AIR REG')and l_shipinstruct = 'DELIVER IN PERSON')or(p_partkey = l_partkeyand p_brand = 'Brand#15'and p_container in ('MED BAG', 'MED BOX', 'MED PKG', 'MED PACK')and l_quantity >= 14 and l_quantity <= 14 + 10and p_size between 1 and 10and l_shipmode in ('AIR', 'AIR REG')and l_shipinstruct = 'DELIVER IN PERSON')or(p_partkey = l_partkeyand p_brand = 'Brand#44'and p_container in ('LG CASE', 'LG BOX', 'LG PACK', 'LG PKG')and l_quantity >= 28 and l_quantity <= 28 + 10and p_size between 1 and 15and 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：
用所有带主键的join条件生成一棵或多棵有向树（polytree）。
对每棵有向树，从根节点开始，先递归把所有子结点处理完成，再把当前结点依次和所有子结点生成的join结点做join。
对这些有向树的根节点，使用第一版的贪心法生成右深树
改进的贪心法很好地解决了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/
