如果你喜欢MatrixOne,请在Github上为它点亮⭐️吧!

为什么MatrixOne 0.5变慢了?


Image

作者:MO R&D

导读

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

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

本文字数:3300+字

阅读时间:15分钟

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

Image

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

Image
Image

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

Image

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

Image

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

Image

最后得到:

Image

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

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

Image

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

Image

聚合下推并不是稀罕事,尽管并不是所有的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,在表多的情况下,也因为计算复杂度常常无法搜索到全局最优,而只能用一个次优解来替代。

Image

假设有下图的三张表R1,R2,R3,以及对应的属性A1,A2,A3。如果采用标准的Binary Join,我们可以采用基于A2的Hash Join把R1,R2首先连接,这样就把R1中的(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(N2)级。因此这时就需要一个聪明的计划,形成一棵二叉树,其中叶子是关系,内部节点对应关系的连接。树的根节点代表所有关系的连接,树状结构建议哪些关系可以连接在一起。例如刚才的例子中,如果R2R3首先连接,那么在与R1连接之前只产生两条记录。Worst Case Optimal Join系列算法,就是一种能够确保产生的Tuple数量可以达到O(N3/2)级的算法,在数学上证明是这最低的。

Image

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

Image

因子化提出了一种基于超图的树分解(Hyper Tree Deecomposition)算法,树分解定义为对超图(V,ϵ)的一个变换,它将图分解为一个Pair (T,x),其中T代表一棵树,x代表一个函数,将T中每个节点映射到V的一个子集,称为bag。

树分解满足2个特性:

  • 覆盖性:T需要包含所有超边;

  • 连通性:所有的V形成一棵连通的子树。

下图右侧,就是针对上述查询的一个树分解结果。

Image

树分解算法,其目的就是找到一个合适的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)变得更加高效和独一无二!


Image

欢迎小伙伴们来跟我们交流经验!

官网

matrixorigin.cn

源码

github.com/matrixorigin/matrixone

Slack

matrixoneworkspace.slack.com

Image

扫码加入MatrixOne技术交流群


关键词:MatrixOrigin

Image

知乎   |   CSDN   |   墨天轮   |   OSCHINA   |   InfoQ   |   Bilibili