Dynamic Programming Strikes Back - MySQL8.0的新优化器

这篇paper是著名的DPccp算法的延续,仍然是讨论如何最高效的基于Dynamic Programing,实现join ordering这个SQL查询优化中最为核心的功能。

概略的来说,这个算法通过在多表join中,限定表的枚举方向且只考虑连通子图的方式,不断从小的connected subgraph扩展到更大的subgraph,然后找到有效的join组合,也就是csg-cmp-pair,来枚举所有可能的join方式并计算最优代价。

尽管其具有先进性和高效性,但很遗憾,这个算法只能是学术界的研究产物,无法应用于实践,因为它存在两个功能缺陷:

  • 无法支持复杂连接谓词 (e.g t1.a + t2.b + t3.c = t4.d + t5.e ),也就是join的任一侧可能有多个表
  • 无法支持非inner join,而现实场景中,left outer join/ant join/semi join是很常见的

而今天的这篇paper就是针对这两个问题进行的改进,形成了新的算法DPhyp

上一篇文章中也说到了,MySQL从5.7便开始了对SQL层的优化,先从Parser搞起,而到了8.0这个步伐显著加快,目前已经完全重构了Executor层,变为了经典的Volcano Iterator。剩下的missing piece便是优化器了,而从8.0.20之后,我们可以在社区的代码中,看到一个新的东西:JoinHypergraph,这是MySQL新的join ordering算法,基本上就是DPhyp的严格实现,目前还属于实验阶段,按照社区之前的分享,大概在9.0这个大版本会GA。

基本定义

在开始分析算法前,有必要对Hypergraph这个概念详细描述下,DPhyp的基本思路和DPccp是完全一样的,只不过将只有简单join条件的join graph扩展到了hypergraph。

  • Definition 1 hypergraph是一个二元组H = (V, E) ,其中
  1. V 是非空节点集合
  2. E 是hyperedge集合,hyperedge是一个无序的二元组(u, v),u, v则各是一个节点的子集,且u, v无交集!
  3. 第2条中的每个节点子集成为一个hypernode

从定义可以看到,其实就是将普通join graph的连接边进行了扩展,变为了hyperedge,可以描述多个节点间的连接关系,因此(t1.a + t2.b + t3.c = t4.d + t5.e )这样的连接条件就可以用{t1 t2 t3} - {t4, t5} 这么一条超边来描述,而如果连接的两端hypernode都只有一个节点,则变为simple edge。

注意在DPccp中提到的节点间有序性对于高效无重复的枚举仍然成立,节点间仍然有个全序关系,这也导致了可以join的hypernode间存在先后关系(不是全序,只是每个join的两端):

每个hypernode是一个集合S,其中最小编号的节点记为min(S),由于hyperedge的两端是无交集的,因此 S1 join S2时,min(S1) 和 min(S2)也就体现了2个集合的先后关系。

Dynamic Programming Strikes Back - MySQL8.0的新优化器

上图就是一个简单的hypergraph,可以看到在{r1, r2, r3} 与 { r4, r5, r6} 之间形成了超边。对于节点间没有边连接的情况,也就是笛卡尔积,算法的处理方式是也将其连接上一条简单边,只不过选择率是1而已,这样就可以统一处理了,参看MySQL的代码实现,也采用了这种方式。

  • Definition 2 连通子图与互补对 (csg / cmp)

有了hyperedge的扩展概念后,连通子图的概念也相应扩展,连通性变为:只要在subgraph集合内,存在超边连接,且其连通的两端分割了节点集合,且两个子集合各自也是连通的,则整个subgraph认为是连通的。而complement pair这个概念也一样,它本身是个连通子图,与另一半没有节点交集,且两个集合之间,存在边的连接。两个csg就构成了一个有效的csg-cmp-pair

类似于DPccp,在枚举中我们每碰到一个有效csg-cmp-pair {S1, S2},也就等于碰到了{S2, S1},通过刚才描述的集合间有序性可以保证只会单向枚举出{S1, S2},其中min(S1) < min(S2),从而保证了无重复的枚举。同时算法本身的实现必须保证枚举顺序先生成小的集合,再生成大的,前者被后者复用。

  • Definition 3 邻居 (neighborhood)

这个概念在没有hypernode时很好理解,只要找到不在已有集合中,且有连接边的新节点就可以了。但这里有了超边,问题变得有些复杂,而且这里是论文中,讲解的比较不清晰的地方。首先在已有集合S的基础上,在考虑邻居时分为2步:

  1. 首先找到所谓的interesting hypernode,也就是与集合当中的simple/hyper node有一条边连接,且其自身没有节点在已有集合S中这种hypernode放入一个集合 Dynamic Programming Strikes Back - MySQL8.0的新优化器
    E\downarrow'(S, X) 

Dynamic Programming Strikes Back - MySQL8.0的新优化器

其中X 是本身就不在考虑范围内的节点集合,枚举过程中会使用。

2. 从 Dynamic Programming Strikes Back - MySQL8.0的新优化器 E\downarrow'(S, X) 中删除被包含的hypernode,生成 Dynamic Programming Strikes Back - MySQL8.0的新优化器E\downarrow(S, X) ,所谓被包含的hypernode,也就是说,如果在S外的一个集合,它是候选邻居,但存在一个更大的节点集合(包含它),也是候选邻居,那么可以把小的删除的,这是可以理解的,因为无论在后续“找互补”对时还是“扩大连通子集”时,早晚能覆盖到这个大集合的所有节点,自然也就能覆盖到小集合。

例如给出的样例hypergraph中,现有集合是{r1, r2, r3},那么它的候选邻居就是{r4, r5, r6}。

由于枚举算法每次无法扩展出一整个hypernode,它只能从一个单节点出发执行枚举算法,因此需要对 Dynamic Programming Strikes Back - MySQL8.0的新优化器E\downarrow(S, X) 中的每个hypernode,选出其“代表”节点,即min(v),作为邻居加入进来。因此

Dynamic Programming Strikes Back - MySQL8.0的新优化器

注意这样只考虑一个代表节点是没有问题的,每个hypernode内部总是可以从一个单节点,扩展到整个node(内部也是一个join tree,节点间总有边相连哪怕是笛卡尔积的边)。因此在不断单节点的扩展中,自然就能考虑到整个hypernode。

在样例中,N({r1, r2, r3}, NULL} = {r4}

搜索算法

算法思路与DPccp完全一致:

在节点间建立全序,然后从后向前迭代,每次迭代只考虑当前节点和其后所有节点,找到包含当前节点的所有的连通子图与他们的互补对,每找到一对csg-cmp-pair,就计算其join代价,并更新其所对应的最优join cost便于后续复用,最终迭代到第一个节点(也就覆盖了全局),算法完成,得到了最终的最优join cost。

现在有了hypernode/hyperedge的引入,增加了一些复杂情况,算法中提到了dpTable[]这个结构,可以认为是一个hash table,key就是节点集合,value是这个节点集合下,join产生的最优cost,只要某个节点集合存在于table中,就说明已找到过这个集合对应的csg-cmp-pair,说明这个集合是连通的。

入口函数

初始时,每个单个节点就是一个连通子图,为其选择最优access path,记录到dpTable中。

然后对单节点{v}这个连通子图,调用EmitCsg,执行找到一个csg后的相应操作。在处理完当前Csg后,调用EnumerateCsgRec,开始扩展Csg。

处理一个连通子图

Dynamic Programming Strikes Back - MySQL8.0的新优化器

这个函数要做的就是给定连通子图S1,找到所有它的互补对,当然S1最小节点之前的节点和S1本身都应不再考虑(参考DPccp),那么对其每个邻居节点 v:

v本身作为一个连通子图,判断其与已有S1是否连通(注意由于v可能只是“代表性”节点,其存在于一个hypernode中,有可能与S1不直接连通!),如果连通则我们找到了一个csg-cmp-pair,调用EmitCsgCmp处理这一对。然后基于S1,以这个{v}为起点,扩展出所有可以与S1成为互补对的集合,这个通过EnumerateCmpRec来实现(注意无论{v}与S1是否连通,这种扩展都要做,否则会漏掉潜在连通的hypernode!

扩展互补对

Dynamic Programming Strikes Back - MySQL8.0的新优化器

函数的参数包括S1当前已有连通子图,S2当前扩展集合,和X(不再考虑内的集合)

和DPccp一样,由于我们限定了枚举的后 -> 前的顺序,每个S1可以认为在S2之前( min(S1) < min(S2) ),而互补对S2的扩展本身和连通子图的扩展思路是完全相同的,也是从基于当前节点(集合),向后扩展。

对S2的每个邻居N(代表节点),先去dpTable中查看S2与N是否连通,这里为什么可以直接去看dpTable呢?因为算法是从后向前迭代,在考虑S1的互补对时,S1后面的各种集合已经都考虑完了,而S2就是在S1的后面,因此在之前的迭代中,这个范围内的各种连通子图已经都考虑并记录在dpTable中了。如果确实连通说明找到个潜在的互补对,测试它和S1的连通性(这时只能找edge了,因为S1没被考虑过),如果连通则找到csg-cmp-pair,调用EmitCsgCmp处理。

在考虑所有“一跳”邻居后,加入一跳邻居到S2中,进入下一层互补对的扩展,也就是递归调用自身。

扩展连通子图

回到入口函数那,当前的csg处理完成后,就要扩展连通子图了。

Dynamic Programming Strikes Back - MySQL8.0的新优化器

S1就是当前的连通子图,X是不应考虑的,X应该包含的是min(S1)之前的节点和S1自身。

那么对S1的每个“代表”邻居N,判断其和S1是否连通,这个仍然可以用dpTable[],因为扩展S1是在为S1寻找互补对之后的,在寻找互补对时,S1与后续节点的连通性已经完成测试(就是EnumerateCmpRec算法中那个找连通边的过程!),因此dpTable中已有记录。如果N与S1直接连通,则 Dynamic Programming Strikes Back - MySQL8.0的新优化器Dynamic Programming Strikes Back - MySQL8.0的新优化器构成了连通子图,调用EmitCsg去处理。

无论是否与N连通,都要扩展为Dynamic Programming Strikes Back - MySQL8.0的新优化器,这样才不会错过hypernode,然后以这个新的集合递归调用,继续向后续节点扩展。

处理csg-cmp-pair

Dynamic Programming Strikes Back - MySQL8.0的新优化器

没找到一对{S1, S2},他们所涉及的表集合是S,那么通过计算所有S1与S2之间join pred的conjunction后的选择率,来计算S1 join S2 (S2 join S1)的cost,并更新dpTable[S]。

上述除入口solve()外的4个函数,互相嵌套递归的调用,配合严格的后 -> 先的迭代顺序,就可以枚举所有可能的csg-cmp-pair,从而找到最优计划!

这个过程有些绕,我们以示例中的hypergraph {R1-R2-R3} - {R4-R5-R6}来看一个枚举过程:

Dynamic Programming Strikes Back - MySQL8.0的新优化器

Dynamic Programming Strikes Back - MySQL8.0的新优化器

上图中描述了整个过程,我们以最复杂部分的为例,也就是从R6迭代到R1,然后开始向后枚举(R2 -> R6 在step15之前已处理完)。

R1初始是一个Csg,因此进入EmitCsg,它的neighbor只有R2,且R1,R2连通,因此建立一个csg-cmp-pair,如step16所示。

然后以S2为seed扩展互补对,R2的邻居只有R3,且R1与{R2,R3}这个集合也是连通的,因此又找到一个csg-cmp-pair。以{R2,R3}为基础继续扩展,由于没有邻居了(没有合法edge),扩展结束。此时{R1}的所有互补对已找完,开始向后扩展{R1},扩大为更新的连通子图再递归找互补对。

因为只有R2一个邻居,step18中{R1,R2}就是新的csg,再重复EmitCsg过程(step19),再继续扩展csg变为{R1,R2,R3} (step20),再找互补对。{R1,R2,R3}的邻居是“代表”节点R4,但测试R4与其没有连通性,调用EnumerateCmpRec扩展R4,直到{R4,R5,R6},这时测试与{R1,R2,R3}连通性成功,找到csg-cmp-pair(step23)。{R4,R5,R6}这个互补对已无法扩展。

回到{R1,R2,R3},扩展连通子图,但此时扩张的R4,R5都无法让新的S1满足连通性要求,直到R6加入进来(step26),此时构成连通子图{R1 -> R6},但已是全员不再有邻居,算法结束。

算法总结

总的来说,算法的大思路是递归+嵌套,从后->前迭代,以当前节点为起点向后看,先找csg,每找到一个就以此为基础找所有可能cmp。找完后扩展当前csg来建立新的csg,然后再找所有可能cmp。当这些都结束,当前节点就算处理完了,再迭代到前一个节点,重复以上过程直到第一个节点。

对比DPccp的话,我们可以看到一些为了兼容hyperedge做的操作,例如集合与其邻居节点间的连通性检查,以及无论当前集合(csg/cmp)是否连通,都继续扩展。


处理Non-inner join

如果查询中没有上面提到的涉及多表的join条件,那么即使有outer join/semi join这些,join graph仍然是一个simple graph,但实际join operator之间是存在一定的重排序约束的:

首先不经推导给出一个结论,对于任一join operator(LOP),任意可满足的重排序规则如下:

Dynamic Programming Strikes Back - MySQL8.0的新优化器

那么如果存在如下情况:

Dynamic Programming Strikes Back - MySQL8.0的新优化器

则就无法实现join order的重排,这个称为conflict。当然还有更复杂情况

Dynamic Programming Strikes Back - MySQL8.0的新优化器

即存在冲突的两个算子Op1/Op2并不直接构成父子关系,但Op1在Op2子树下,如果子树自身允许做重排序,那么也会在变换后形成冲突的join tree。

引入了两个概念SES/TES:

  • SES(syntactic eligibility set)是一个join operator从语法上要依赖的表集合,例如这个join condition中涉及的表列都对应哪些表,很显然这是最基本的要求,没有这些列condition是无法计算的
  • TES(total eligibility set)则不仅包含SES的语义,还用来表示对于operator的自身属性以及operator之间重排序的依赖关系的约束,举2个栗子:
t1 left outer join t2 where t2.b is NULL

这里t2.b is NULL这个condition,其SES是{t2},因为只涉及到t2表,但由于是where中的,且t2有可能在join中产生NULL列,因此TES就是{t1, t2},表示在t1,t2都包含的子树上才能做这个operator操作。

t1 left anti join (t2 join t3 on t2.a = t3.a) on t1.b = t2.b

这里由于left join的约束,{t2, t3}的join必须先完成,才能做t1与nest部分的LOJ,为了表示这个约束,TES(LOJ)中,必须右子树包含 {t2, t3},而TES(nest) = SES(nest) = {t2, t3}。

构建TES的算法:

Dynamic Programming Strikes Back - MySQL8.0的新优化器

其中STO(o)是算子o下所有算子集合。基本思路就是,对Op1下任一侧,如果有算子Op2与自己有不可重排序的conflict,则把Op2的TES集合加入到自己的TES集合中,这样就利用算子树上TES的包含关系建立了重排序的约束。

假设给定一个join operator tree,我们已经建立好了每个operator的TES集合,那么怎么去使用它呢?最符合直觉的方法,就是当每找到一个csg-cmp-pair {S1, S2}时,检查其hyperedge上对应的join operator(o),看是否满足 

Dynamic Programming Strikes Back - MySQL8.0的新优化器

注意算法在构建节点顺序时,要遵从join的天然顺序,也就是如果S1 LOJ S2,则节点顺序中 S1一定在 S2 前面,这样枚举出的S1, S2也遵守这个顺序,因此我们就不用交换S1/S2再探测。

如果测试满足要求,则当前是一个合法的csg-cmp-pair,否则是非法的,放弃掉。

这是一个可行的办法,但等于会枚举出很多无效的pair,效率有所降低,因此论文中提出了一种更高效的方法:用hyperedge来描述这种约束!

具体来说,当join operator存在一定的TES约束时,则不用普通的simple edge来描述这个operator,而是用hyperedge,对应的hyperedge(l, r)是:

Dynamic Programming Strikes Back - MySQL8.0的新优化器

Dynamic Programming Strikes Back - MySQL8.0的新优化器

也就是说,将TES(left(o)) / TES(right(o))各自作为一个hypernode,这样这个join在执行时,必须满足hypernode中这些节点集合都存在的前提,也就满足了TES本身的约束,而且这种edge都是在构建hypergraph时预先完成的,直接作为算法输入执行即可,枚举算法本身无需修改。

注:这篇paper发表于2008年,以上所描述的构建TES算法,在作者后续的paper中被证明是存在漏洞的。不过其整体的思路是一致的,准确的算法可以参考《On the Correct and Complete Enumeration of the Core Search Space》 ,后面会针对paper写一篇文章。


MySQL 8.0 新优化器

算法已经讲了很多,我们来看一下MySQL是怎么实现的 

获取8.0.24 codebase,我们可以看到在sql目录下多了join_optimizer这个子目录,其中就是新的join optimizer实现。

总的来说,代码实现是严格按照DPhyp算法来的,只不过现在处于实验阶段,有很多trace/log等信息,comments里也有很多TODO,此外对于non-inner join的处理还不精细。

新优化器通过set optimizer_switch="hypergraph_optimizer=on"; 来打开,其代码流程如下:

FindBestQueryPlan
-> MakeJoinHypergraph 构建hypergraph
  -> MakeRelationalExpressionFromJoinList 基于top_join_list构建operator tree
  ...
  -> MakeJoinGraphFromRelationalExpression 基于operator tree => hypergraph
     目前对non-inner join的约束比较粗暴:
     1. Inner join,且左右子树都只有inner join,只约束SES
     2. Inner join,但子树有非inner join: 将那颗子树整个固定在当前operator下,作为hypernode
     3. 非Inner join,直接把左右子树都固定死,变成2个hypernode
...
-> EnumerateAllConnectedPartitions 开始算法流程 (Solve)
  -> EnumerateComplementsTo 找互补对 (EmitCsg)
     -> FoundSubgraphPair 找到csg-cmp-pair (EmitCsgCmp)
     -> ExpandComplement 扩展互补对 (EnumerateCmpRec)
  -> ExpandSubgraph 扩展连通子图 (EnumerateCsgRec)
辅助函数 FindNeighborhood 获取neighbors

可以看到与paper算法有严格对应关系,而且代码中的很多注释算是对论文的补充,可以看看加深理解。

在FoundSubgraphPair函数中,MySQL使用了CostingReceiver这个类来计算代价,算是一种插件形态吧,通过回调来处理,这样可以插接不同的cost model。在优化完成后,生成用AccessPath描述的一棵physical join tree。

AccessPath是MySQL8.0.2x 引入的,用来解耦优化器与执行器的结构,是对物理plan的描述,executor利用这个结构来生成iterator tree。由于历史原因,这个结构目前没有完全做到与优化器层解耦,还保留了一些引用关系,相信随着社区不断重构,最终会完全解耦。

具体看一个极简例子:

explain format=tree select * from t1 join (t2 join t3) where t1.c2 =t2.c2+t3.c2;

其构建的原始join tree:

Dynamic Programming Strikes Back - MySQL8.0的新优化器

optimizer输出的debug信息如下,其中R1 <-> t1, R2 <-> t2, R3 <-> t3,可以看到整个枚举过程:

Dynamic Programming Strikes Back - MySQL8.0的新优化器

optimizer_trace如下,是更简洁的枚举结果以及相关代价。

{\
            "join_optimizer": [\
              "Join list after simplification:",\
              "* t3  join_type=inner",\
              "* t2  join_type=inner",\
              "* t1  join_type=inner",\
              "",\
              "Made this relational tree; WHERE condition is (t1.c2 = (t2.c2 + t3.c2)):",\
              "* Inner join (no join conditions)",\
              "  * Inner join (no join conditions)",\
              "    * t1",\
              "    * t2",\
              "  * t3",\
              "",\
              "After pushdown; remaining WHERE conditions are (none), table filters are (none):",\
              "* Inner join (extra join condition = (t1.c2 = (t2.c2 + t3.c2)))",\
              "  * Cartesian product",\
              "    * t1",\
              "    * t2",\
              "  * t3",\
              "",\
              "Selectivity of join [cartesian product]:",\
              "Selectivity of join (t1.c2 = (t2.c2 + t3.c2)):",\
              " - fallback selectivity for (t1.c2 = (t2.c2 + t3.c2)) = 0.100",\
              "",\
              "Constructed hypergraph:",\
              "digraph G {  # 2 edges",\
              "  t1 -> t2 [label=\\"[cartesian product]\\"]",\
              "  e2 [shape=circle,width=.001,height=.001,label=\\"\\"]",\
              "  t1 -> e2 [arrowhead=none,label=\\"\\"]",\
              "  t2 -> e2 [arrowhead=none,label=\\"\\"]",\
              "  e2 -> t3 [label=\\"(t1.c2 = (t2.c2 + t3.c2))\\"]",\
              "}",\
              "Node mappings, for reference:",\
              "  R1 = t1",\
              "  R2 = t2",\
              "  R3 = t3",\
              "",\
              "",\
              "",\
              "Enumerating subplans:",\
              "Found node t3 [rows=1]",\
              " - {cost=0.2, init_cost=0.0} is first alternative, keeping",\
              "Found node t2 [rows=1]",\
              " - {cost=0.2, init_cost=0.0} is first alternative, keeping",\
              "Found node t1 [rows=1]",\
              " - {cost=0.2, init_cost=0.0} is first alternative, keeping",\
              "Found sets {t1} and {t2}, connected by condition [cartesian product] [rows=1]",\
              " - {cost=0.7, init_cost=0.3} [hash join] is first alternative, keeping",\
              " - {cost=0.5, init_cost=0.0} [nested loop] is better than previous {cost=0.7, init_cost=0.3}, replacing",\
              " - {cost=0.5, init_cost=0.0} [nested loop] is not better than existing path {cost=0.5, init_cost=0.0}, discarding",\
              "Found sets {t1,t2} and {t3}, connected by condition (t1.c2 = (t2.c2 + t3.c2)) [rows=0]",\
              " - {cost=1.0, init_cost=0.3} [hash join] is first alternative, keeping",\
              " - fallback selectivity for (t1.c2 = (t2.c2 + t3.c2)) = 0.100",\
              " - {cost=0.8, init_cost=0.0} [nested loop] is better than previous {cost=1.0, init_cost=0.3}, replacing",\
              " - fallback selectivity for (t1.c2 = (t2.c2 + t3.c2)) = 0.100",\
              " - {cost=0.8, init_cost=0.0} [nested loop] is not better than existing path {cost=0.8, init_cost=0.0}, discarding",\
              "",\
              "Enumerated 5 subplans, got 1 candidate(s) to finalize:",\
              "Adding final predicates",\
              "Final cost is 0.8."\
            ]\
          }\

最终生成的join plan是:

| EXPLAIN
                                                                                                                                 |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------+
| -> Nested loop inner join  (cost=0.75..0.75 rows=0)
    -> Nested loop inner join  (cost=0.50..0.50 rows=1)
        -> Table scan on t1  (cost=0.25..0.25 rows=1)
        -> Table scan on t2  (cost=0.25..0.25 rows=1)
    -> Filter: (t1.c2 = (t2.c2 + t3.c2))  (cost=0.35..0.35 rows=0)
        -> Table scan on t3  (cost=0.25..0.25 rows=1)

顺带吐槽下,新optimizer还很不稳定,调试过程中经常崩溃。。。不过对于我们这些基于MySQL的开发人员来说,看到社区有了如此大的动作还是激动不已的,从DPhyp的实现可以看到其optimizer也走上了规范化的道路,我们也看到了expr tree这样的标准结构,整个代码变得更加简洁,而且更注重执行效率了。

上一篇:云栖大会|盛宴之下,共赴一场视频云的进化论


下一篇:直播短视频源码,最后的变现道路被打通,是否代表现阶段已无敌