作者：龙冉 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全副查问这样一个当时看起来不可能实现的工作。靠近一年起初回顾，咱们依然对过后几位共事通力合作付出的艰苦，一直踩坑时的丧气，以及达到目标后的惊喜深有感触。这段经验也继续激励咱们在数据库根底软件这个方向上持续致力。