为什么 MatrixOne 0.5 变慢了

近期关心 MatrixOne 的小伙伴有反馈，MatrixOne 0.5 的性能比之前慢了不少。在今年初 MatrixOne 0.2 版本的发布文章中，还有 MatrixOne 的 SSB 单表性能超过 ClickHouse，并且多表性能达到 Starrocks 的报道，为什么到了 0.5 反而变慢了呢？

留意当初报道的小伙伴应当会注意到因子化加速引擎的字样，事实上，正是得益于 0.2 版本中因子化引擎，才使得基于 Golang 语言实现的 MPP 计算引擎在性能上能够不落下风，并且在某些场景下碾压其他大多数 OLAP 数据库，比如非主键 Join。那么为什么到了 0.5 版本，所谓的因子化引擎不再提及，性能也由此慢下来了呢？ 这一切均需要从因子化引擎本身来谈起。

因子化是个莫名其妙的称呼，但是也只能这么翻译，因为它的全称叫 Factorisation，如果伙伴们回滚到 MatrixOne 0.4 及其之前的版本，更是可以看到所有的聚合函数都在一个叫做Ring的莫名其妙的目录下。那么什么叫 Factorisation，Ring 又是什么呢？

这是来自于 DBToaster 一族著名的增量物化视图算法，它把数据库的一张表看作由乘积和加法构成的表示，而 Ring 则代表在这种由乘法和加法构成的表示中满足交换律、结合律和分配律的系列操作，比如各种 Count/Sum/Avg/Max 等等的聚合函数，就满足 Ring 的要求。在此基础之上，因子化定义了 3 种基础操作：Union，Join，Marginalization，如下图所示。前两者比较容易理解，最后一个 Marginalization，翻译过来叫边缘化，其实质相当于对一个由加法和乘法构成的表示，基于某列(图中是 A 列)做提取公因数操作，类似分配律，因此才有因子化引擎的叫法。

给定以上三种操作，现假设需要计算 Select count(*) From R(A,B) Natural Join S(A,C,E) Natural Join T(C,D)，Join 关系如下图所示：

假定 R，S，T 三张表的大小都为 N，那么朴素的实现，复杂度则为$O(N^3)$ ，既将三张表完成 Join 后，再进行 count 的计算。在因子化计算中，有了 Marginalization 操作，我们就可以把聚合函数下推：

这里$V_1[A]$代表对 R 基于 B 列做边缘化操作的结果。进一步边缘化，得到$V_2[A,C]$：

最后得到：

在以上不断 Marginalization 计算的过程中，聚合函数一直不断下推，因此尽管有 3 表 Join，但是中间结果一直保持最小，不存在朴素实现那种生成巨大的 Join 结果后才进行聚合实现的问题，这就是为什么基于因子化引擎计算 Join 时，即使是非主键 Join，也无所畏惧，不用担心 Join 产生的笛卡尔积从而 OOM 的问题。因此，从本质上来说，因子化引擎，提供了一种通用的聚合下推的计算框架。任何聚合函数，只要它满足交换律和结合律，就可以实现其对应的 Marginalization 操作，然后在统一的聚合下推框架中得到应用。

以上查询中，每次边缘化所操作的属性叫做 Variable，给定查询进行边缘化操作的顺序叫做 Variable Order，系列边缘化操作可以组成一棵树，叫做 View Tree。这里可以看到用到了 View 字眼，是因为，如果把 View Tree 上的这些 View 物化，那这就是一个物化视图的维护算法。

因子化计算引擎，对于查询是有限制的，Variable 只能为 Group By 和 Join 属性，且根据以上的因式分解可以很容易看出来，它也只能支持等值 Join。因此，简单的讲，因子化计算的第一大主要功能，就是一个用于 CAQ(Conjunctive Aggregation Query)查询的计算框架，在查询包含等值 Inner Join 或者 Group By，以及聚合函数时，它提供了一种统一的聚合下推框架，使得计算的中间状态最小化，因此是非常理想的计算加速手段。下图的例子对一个通用查询做了因子化拆解：

聚合下推并不是稀罕事，尽管并不是所有的 SQL 计算引擎都支持，比如 Presto 也是到了最近几年才支持这个功能，它显然是一种查询加速的有效手段。只是相比之下，一般的 SQL 计算引擎需要对不同的聚合函数采用不同的策略，因为并不存在一个统一的聚合下推方法，比如 AVG 跟 SUM 的下推方式就不一样。因此在因子化框架之下，只需要根据 Ring 的语义实现对应 Agg 函数的接口，即可完成在 CAQ 查询下的聚合下推。

因子化引擎的第二大功能，是推出了一个较优的 Join Order 框架——基于 Hyper Graph 的 Hyper Tree 分解算法，该算法来自于知名的 Worst Cast Optimal Join 系列，意思是在最坏情况下，该 Join 算法的复杂度可以最优。这一族算法区别于标准 SQL 引擎里对 Join 的处理流程——以表为单元处理每一次 Join 操作，该算法则是以属性(列)为单元处理每次 Join。我们知道，标准的 SQL 计算引擎，基本都是两表 Join——根据左深或者右深的原则，很少会有多路 Join，因为即使是两表 Join，它的搜索空间复杂度也会达到$N!$，至于 Bushy Plan(下图的右侧)，它的搜索空间更加巨大，很难得到一个哪怕是局部最优解，即使是左深 Plan，在表多的情况下，也因为计算复杂度常常无法搜索到全局最优，而只能用一个次优解来替代。

假设有下图的三张表$R_1,R_2,R_3$，以及对应的属性$A_1,A_2,A_3$。如果采用标准的 Binary Join，我们可以采用基于$A_2$的 Hash Join 把$R_1,R_2$首先连接，这样就把$R_1$中的(1,x)和(5,x)与$R_2$中的(x,2)和(x,4)连接，此时输出的数据是 4 个三元组：(1,x,2)，(1,x,4)，(5,x,2)和(5,x,4)，记录(1,q)则没有匹配因此不输出。为了进一步完成 Join，需要继续探测其他的表属性，直到所有可能的关系都被探测完，但这可能非常慢。假如每个表的长度都为 N，那么反复做 Binary Join 所输出的 Tuple 数量会在$O(N^2)$级。因此这时就需要一个聪明的计划，形成一颗二叉树，其中叶子是关系，内部节点对应关系的连接。树的根节点代表所有关系的连接，树状结构建议哪些关系可以连接在一起。例如刚才的例子中，如果$R_2$和$R_3$首先连接，那么在与$R_1$连接之前只产生两条记录。Worst Case Optimal Join 系列算法，就是一种能够确保产生的 Tuple 数量可以达到$O(N^{3/2})$级的算法，在数学上证明是这最低的。

Worst Case Optimal Join 包含一系列算法，例如 LeapFrog TrieJoin，NPRR 等，因子化也是其中的一种，它基于超图表达每个查询，超图中的每个节点定义为上文中的 Variable，把查询中每个关系的 Variable 集，是图的一条(超)边$ϵ$。例如针对$R_1(A,B),R_2(A,c),R_3(B,c)$的三角 Join，超图如下图表示，这里 Variable 集合包含{A,B,C}，超边集合包含{{A,B},{A,C},{B,C}}。

因子化提出了一种基于超图的树分解(Hyper Tree Deecomposition)算法，树分解定义为对超图$(V,ϵ)$的一个变换，它将图分解为一个 Pair (T,x)，其中 T 代表一颗树，x 代表一个函数，将 T 中每个节点映射到 V 的一个子集，称为 bag。树分解满足 2 个特性：覆盖性——T 需要包含所有超边；连通性——所有的 V 形成一颗连通的子树。下图右侧，就是针对上述查询的一个树分解结果。

树分解算法，其目的就是找到一个合适的 Variable Order（前文中有提到），因为 Variable Order 可以表达为一个 Pair (F,key)，其中 F 是一个有根的树，查询 Q 中的每个 Variable 都对应树的一个节点；key 是一个函数，将每个 Variable 映射到它在 F 中的祖先 Variable 的子集。通过 Variable Order 决定 View Tree 的结构，就决定了整个查询中 Join Order 和执行的框架。

因此，因子化就是满足 CAQ 查询条件的 Join Order 和 Agg 下推的计算框架。在 MatrixOne 0.2 的代码中，实现了因子化的 Variable Order 和 View Tree 系列算法，使得对于 SSB 这样简单的查询，可以达到性能最优；在 MatrixOne 0.4 的代码中，实现了树分解算法，使得对于任意表 Join，都能给出相对不错的性能。这听起来不错，那么为什么这些实现从 MatrixOne 0.5 拿掉了呢？

通过上面的介绍，大家也可以看出，整个因子化是一个非常另类的计算框架——它没有逻辑计划，直接就进入执行了，而且只能按照它的逻辑来，伴随着一堆莫名其妙的术语比如 Variable/View Tree/Ring 等等，这么一个怪异的框架，使得它在支持更为丰富的 SQL 功能的时候，很难处理，比如 MatrixOne 在 0.5 一开始定下的目标就是在两个多月内跑通 TPCH，如果要继续使用因子化，就需要做个 IF ELSE——如果满足 CAQ 条件，那么执行因子化逻辑，否则就是标准流程——例如 TPCH 必备的子查询，CTE，非等值 JOIN，未来的窗口函数等等。因此，MatrixOne 的研发同学们，从 0.5 版本开始，又把 SQL 计算引擎，从 Parser 后开始的部分，按照标准的 MPP 实现重新做了一份，包含逻辑计划，优化器以及执行器，仅仅历时两个多月就跑通了 TPCH。

目前，MatrixOne 已经进入 0.6 迭代周期，在这个周期中，需要对这套标准的 SQL 执行引擎做加速，包含子查询，各种非等值 Join，Runtime Filtering，Join Order(传统左深树)，使得它能够跟其他 MPP 引擎相提并论。

那么因子化是否还会回到 MatrixOne？这并不困难，因为加入它只是个 IF ELSE，我们需要首先确保标准的 SQL 引擎工作高效；其次，在前文已经提到过，它来自于 IVM 算法，而 MatrixOne 已经喊出了 HSTAP 的口号，或许对于 S(Streaming)来说，才是因子化算法的舞台。

欢迎对这一族看起来比较黑科技的算法感兴趣的同学，一同加入 MO 大家庭来一起把计算引擎(含 S)变得更加高效和独一无二。