这篇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这样的标准结构，整个代码变得更加简洁，而且更注重执行效率了。
