关于sql:从零到跑通TPCH如何快速实现查询计划

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