这篇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) ,其中
-
V 是非空节点集合
-
E 是hyperedge集合,hyperedge是一个无序的二元组(u, v),u, v则各是一个节点的子集,且u, v无交集!
-
第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个集合的先后关系。
上图就是一个简单的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步:
-
首先找到所谓的interesting hypernode,也就是与集合当中的simple/hyper node有一条边连接,且其自身没有节点在已有集合S中。这种hypernode放入一个集合
E\downarrow'(S, X)
其中X 是本身就不在考虑范围内的节点集合,枚举过程中会使用。
2. 从 E\downarrow'(S, X) 中删除被包含的hypernode,生成 E\downarrow(S, X) ,所谓被包含的hypernode,也就是说,如果在S外的一个集合,它是候选邻居,但存在一个更大的节点集合(包含它),也是候选邻居,那么可以把小的删除的,这是可以理解的,因为无论在后续“找互补”对时还是“扩大连通子集”时,早晚能覆盖到这个大集合的所有节点,自然也就能覆盖到小集合。
例如给出的样例hypergraph中,现有集合是{r1, r2, r3},那么它的候选邻居就是{r4, r5, r6}。
由于枚举算法每次无法扩展出一整个hypernode,它只能从一个单节点出发执行枚举算法,因此需要对 E\downarrow(S, X) 中的每个hypernode,选出其“代表”节点,即min(v),作为邻居加入进来。因此
注意这样只考虑一个代表节点是没有问题的,每个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。
处理一个连通子图
这个函数要做的就是给定连通子图S1,找到所有它的互补对,当然S1最小节点之前的节点和S1本身都应不再考虑(参考DPccp),那么对其每个邻居节点 v:
v本身作为一个连通子图,判断其与已有S1是否连通(注意由于v可能只是“代表性”节点,其存在于一个hypernode中,有可能与S1不直接连通!),如果连通则我们找到了一个csg-cmp-pair,调用EmitCsgCmp处理这一对。然后基于S1,以这个{v}为起点,扩展出所有可以与S1成为互补对的集合,这个通过EnumerateCmpRec来实现(注意无论{v}与S1是否连通,这种扩展都要做,否则会漏掉潜在连通的hypernode!)
扩展互补对
函数的参数包括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处理完成后,就要扩展连通子图了。
S1就是当前的连通子图,X是不应考虑的,X应该包含的是min(S1)之前的节点和S1自身。
那么对S1的每个“代表”邻居N,判断其和S1是否连通,这个仍然可以用dpTable[],因为扩展S1是在为S1寻找互补对之后的,在寻找互补对时,S1与后续节点的连通性已经完成测试(就是EnumerateCmpRec算法中那个找连通边的过程!),因此dpTable中已有记录。如果N与S1直接连通,则 构成了连通子图,调用EmitCsg去处理。
无论是否与N连通,都要扩展为,这样才不会错过hypernode,然后以这个新的集合递归调用,继续向后续节点扩展。
处理csg-cmp-pair
没找到一对{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}来看一个枚举过程:
上图中描述了整个过程,我们以最复杂部分的为例,也就是从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),任意可满足的重排序规则如下:
那么如果存在如下情况:
则就无法实现join order的重排,这个称为conflict。当然还有更复杂情况
即存在冲突的两个算子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的算法:
其中STO(o)是算子o下所有算子集合。基本思路就是,对Op1下任一侧,如果有算子Op2与自己有不可重排序的conflict,则把Op2的TES集合加入到自己的TES集合中,这样就利用算子树上TES的包含关系建立了重排序的约束。
假设给定一个join operator tree,我们已经建立好了每个operator的TES集合,那么怎么去使用它呢?最符合直觉的方法,就是当每找到一个csg-cmp-pair {S1, S2}时,检查其hyperedge上对应的join operator(o),看是否满足
注意算法在构建节点顺序时,要遵从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)是:
也就是说,将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:
optimizer输出的debug信息如下,其中R1 <-> t1, R2 <-> t2, R3 <-> t3,可以看到整个枚举过程:
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这样的标准结构,整个代码变得更加简洁,而且更注重执行效率了。