为什么MatrixOne 0.5变慢了？

这是来自于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³)，既将三张表完成Join后，再进行count的计算。在因子化计算中，有了Marginalization操作，我们就可以把聚合函数下推：

这里V₁[A]代表对R基于B列做边缘化操作的结果。进一步边缘化，得到V₂[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₁,R₂,R₃，以及对应的属性A₁,A₂,A₃。如果采用标准的Binary Join，我们可以采用基于A₂的Hash Join把R₁,R₂首先连接，这样就把R₁中的(1,x)和(5,x)与R2中的(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²)级。因此这时就需要一个聪明的计划，形成一棵二叉树，其中叶子是关系，内部节点对应关系的连接。树的根节点代表所有关系的连接，树状结构建议哪些关系可以连接在一起。例如刚才的例子中，如果R₂和R₃首先连接，那么在与R₁连接之前只产生两条记录。Worst Case Optimal Join系列算法，就是一种能够确保产生的Tuple数量可以达到O(N^3/2)级的算法，在数学上证明是这最低的。

Worst Case Optimal Join包含一系列算法，例如LeapFrog TrieJoin，NPRR等，因子化也是其中的一种，它基于超图表达每个查询，超图中的每个节点定义为上文中的Variable，把查询中每个关系的Variable集，是图的一条(超)边ϵ。例如针对R₁(A,B),R₂(A,C),R₃(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)变得更加高效和独一无二！