MySQL无疑是现在开源关系型数据库系统的霸主，在DBEngine的最新排名中仍然稳居第2位，与第3位SQL Server的积分差距并不算小，可以说是最受欢迎，使用度最高的数据库系统，这一点看看有多少新型数据库要兼容MySQL的协议和语法就知道了。
但作为数据库内核的研发，相信看过MySQL源码的人都知道，其代码是有多么一言难尽。。。尤其是Server层，混乱的代码结构，交织的模块逻辑，随处可见的hack，在MySQL里你甚至看不到清晰的logic plan tree和算子优化流程。对比下Postgres的源码，真是让我们这些MySQL内核开发泪流满面。
这一点官方自然也很清楚，在CMU前段时间的Quarantine Database Tech Talks (2020)中，MySQL优化执行层的leader Norvald Ryeng谈起了MySQL的历史以及形成如此糟糕代码的原因，主要就是
- 从早期开始，MySQL的设计就围绕着NestLoop join这种单一的场景做设计，优化的方方面面都遵循了这样的执行方式，因此才能在5.6/5.7中看到那种围绕QEP_TAB序列循环递归调用的代码逻辑。
- 一直以来官方都在为满足用户需求而努力，而MySQL的快速发展使得这种需求连绵不断，没有机会做大的重构，只能不停的打补丁+ 做hack，导致越来越糟糕。
因此从5.7开始，他们已经在逐渐开始对SQL层代码的重构，而到了8.0这个步伐陡然加快了。
前几天社区release了8.0.24，其执行引擎已经完成了重构，变为了标准的Volcano iterator，不过优化器仍然是传统的greedy search + heuristic，因此只能生成left-deep的join tree，同时针对semi-join/left join的情况实现了嵌套的join来模拟bushy tree。
但与此同时，社区已经开始推出了新的优化器，利用Hypergraph算法做DP-based join ordering enumeration，从而可以充分的探索plan space，枚举bushy join tree。
原谅我啰嗦了上面一大堆，其实就是为了推出这个Hypergraph算法，这是一种基于动态规划的自底向上的join顺序枚举算法，是由Guido Moerkotte和Thomas Neumann两位大神提出的，相信熟悉HyPer数据库的同学对他们并不陌生，不过今天我们先不直接讲解Hypergraph，而是先从它的前继算法开始说起，也就是本篇标题中的paper。
有关动态规划算法就不深入介绍了，忘却的同学可以参看一些经典的算法书籍或者网上资料。
基本介绍
这篇文章在两个基本前提下（1. join graph是连通的，也就是不考虑笛卡尔积的情况 2. 只考虑inner equal join），分析了基于动态规划做join order enumeration的本质。
首先给出了2种已有的DP-based的算法，并通过理论分析+实验的方式，说明了这两种方法针对不同的join graph形态，各有优劣。并给出了DP-based算法理论上的复杂度下界，同时说明这两种基于"generate and test" 的方法，会产生大量无效的组合，导致test失败的情况比成功的情况多很多，因此无效枚举过多，不是最优的算法。
注: join graph是用来描述一个query中各个表的相互join关系的图，可以用G(V,E)来表示，其中V的顶点集合，每个顶点对应一张表，在有join关系的两个顶点之间构成一条无向边(inner join满足交换律)。例如如下4种形态
两种常见算法
业界比较常见的枚举算法有以下两种：
DPsize
从算法可以看出，它先从单表开始并不断扩大，以s作为本次循环的目标表集合大小，针对每一种可能的s个表的集合，尝试s内所有可能的join，依次进行"test"。如果test通过，就认为找到了一种有效的join组合，开始计算代价。大家应该发现了，这和Postgres中做join ordering的算法是比较类似的：
{t1,t2,t3} .....
{t1,t2} {t2,t1} {t1,t3} {t3,t1} {t2,t3} {t3,t2}
{t1} {t2} {t3}
由于枚举过程是跟着s从 1 -> n不断扩大表集合的大小，因此叫做DPsize。
DPsub
算法2和DPsize的思路其实是一致的，只是它枚举表组合的方式不是通过扩大表集合的大小，而是用bitmap来描述：
假设3个表t1,t2,t3，则用一个3 bit的数来表示，枚举其所有可能的取值 1 -> 7
001 -> 010 -> 011 -> 100 -> 101 -> 110 -> 111
在对应位上值为1的，表示本次表集合里有这张表，否则没有，所以上面序列也就表示
{t1} -> {t2} -> {t1,t2}/{t2,t1} -> {t3} -> {t1,t3}/{t3,t1} -> ....
可以看到和DPsize相比本质没有变化，所有可能的表组合都被枚举出来了。
例如一条join是这样的：
t1 join t2 join t3
那么{t1,t3}/{t3,t1} 这样的组合没有意义，等于白白枚举。这只是最简单的例子，如果join graph复杂，各种表的组合会指数级膨胀，而有效join只有那些，导致枚举效率低下。（注意有效join和算法无关，只和join graph描述的语义相关）
上面2个算法中都有两个计数器，InnerCounter/CsgCmpPairCounter，每枚举出一种表组合，InnerCounter会递增，而当组合可以构成有效join时，CsgCmpPairCounter会递增，因此算法效率就取决于：CsgCmpPairCounter/InnerCounter。理论分析表明，以上两种算法中InnerCounter比CsgCmpPairCounter大1-4个数量级，随着表数量n的增大复杂度急剧上升。
那么什么叫有效join组合呢？在本paper中，如果2个表集合S1，S2满足如下条件，就认为他们构成了有效的表组合：
- S1内部连通，没有笛卡尔积，内部的表可以构成一个join tree
2. S2内部连通，没有笛卡尔积，内部的表可以构成一个join tree
3. S1 S2没有交集
4. S1中存在顶点V1，与S2中的顶点V2之间有边相连（有join条件）
paper中称这种情况为构成了一组CsgCmpPair，Csg是ConnectedSubGraph即连通子图，Cmp是Complement，表示他们互补且无交集。
从理论上来说，无论采用什么样的枚举算法，给定一个join graph后，所有可能的CsgCmpPair的数量是确定的（join语义决定），那么最高效的算法，就是只枚举CsgCmpPair的join组合。那么有没有这种能够达到理论下界的枚举算法呢？paper给出了答案。
DPccp
新提出的算法思路很直接，仍然遵循动态规划那种子问题 -> 父问题的路线，但在扩展问题规模（也就是扩展表组合时），要保证扩展前后的表集合，始终满足CsgCmpPair的要求，这样就不会产生无效的组合，达到最高的枚举效率。
大概想想的话，这其实也不难办到，假设我们从一个表开始，基于join graph给出的连通性，总是能把和它连通的表不断包含进来，这样一个个连通子集S1就算得到了，那么S2就在剩余表中找，过程类似，先找到一个和S1中的表有join条件的顶点，这也就是S2枚举的起点，然后从这个点不断基于连通性扩展，就可以枚举各种S2组合，过程中注意始终不和S1的表集合重复，这样就找到了各种CsgCmpPair。
实际会更复杂一些，因为算法的目标是完全不会有重复的枚举，这就要求有更多的控制，首先，我们先对表从一个起点出发，按照广度优先遍历的顺序，做一个编号，例如下图的join graph 构成序列 { R0 R1 R2 R3 R4 }
我们分解来看每个子功能
- 首先是从一个单点出发，枚举所有连通子图的能力。为了不重复枚举相同的子图集合，算法中用了一个巧妙的方法：
针对表的序列 { R0 R1 R2 R3 R4 }，从后向前执行探索过程！也就是说先以R4作为起点，再以R3作为起点，同时为了保证不重复枚举，以Ri作为起点时，只考虑Ri -> Rn的这个集合中的各种可能组合！这样既可以保证不重复，又可以保证枚举全。
如何保证不重复？由于每次枚举时面向的集合S就是{Ri -> Rn}，且S1总是以Ri为起点向外扩展，这样无论怎么构建{S1 S2}，其中一定有Ri，当迭代到前一个Ri-1时，{S1 S2}组合则一定会有Ri-1，这就保证了不会和前一次迭代(Ri起点）的集合有重叠。
如何保证覆盖全？在以Ri为起点枚举时，Ri-1 -> R0的部分是没有涉及到的，但随着迭代向前推移，每个顶点Rj都会被加入到考虑中，最终所有都在考虑范围内，所以不会有遗漏。
具体算法如下：
给定一个顶点v , 记 N(v) 为该顶点的所有邻居节点集合（有一条join edge连接），而对于一个顶点集合S, 记 N(S) 为S所有的邻居节点的集合（去掉S内部的节点），即
EnumerateCsg这个函数是总体的迭代，沿着Vi-1 -> V0的降序方向，对Vi这个顶点，从{Vi}单点集合开始，扩展其连通子图，找到所有可能的连通集合S1。
EnumerateCsgRec负责枚举连通子集S1，是个递归的过程，其输入S标识当前的已有集合，X标识不需要考虑进来的节点集合。N(S)标识S这个连通子集的邻居节点集合，通过将N(S)中各种节点组合加入到S中，就产生了各种可能的"一跳"连通子集，然后再以邻居节点为起点，递归到下一层处理"二跳"的邻居节点，依次类推。这里要注意进入下一层时，要把本层枚举的所有邻居节点都排除出去，因为N已经在所属的本层EnumerateCsgRec的for循环中，通过枚举的方式都覆盖到了，等于覆盖了S + N的范围，进入下层就不用考虑了。
还是用上图的例子看下就明白了
上图从R4 -> R0方向，每个红框表示以一个Ri为起点向后枚举的过程。
- 首先观察，每个红框中枚举出的集合，都包含了Ri顶点，因此各个红框中的集合，是没有重叠的。
- 再以R1为例，向后看R1和R4连通，因此通过一跳，可以枚举的集合只有{1,4}，然后以新加入的4为起点，继续扩展，R4与R2/R3都连通，因此二跳枚举的邻居集合包括{1,4,2} {1,4,3} {1,4,2,3}，这时1,2,3,4都被考虑到了，没有再可以扩展的邻居了，这次迭代就结束了。
- 找到一个连通子图S1时，如何枚举互补的连通子图S2 ?
非常符合直觉的方式，就是当枚举出一个S1时，可以对S1的邻居N(S1)中的每个节点，作为出发点，扩展所有可能S2（当然这里不能再包含S1中的元素），这样的S2即是csg，也同时和S1连通，符合要求，这个过程直接用EnumerateCsgRec函数就可以实现。
注意这里仍然利用顺序，枚举S2是在枚举S1的过程中执行的，由于枚举S1时没有考虑S1之前的元素，S2也仍然不考虑S1之前的节点+S1自身的节点。
- 有了枚举S1 + S2的算法，现在只要组合起来就可以了
可以看到对每对(S1,S2)，他们都是某个子问题S的csg-cmp-pair，因此总是有效的，此外，在得到S1,S2后，{S1,S2} / {S2,S1} 两种join选择在这个算法里处理。由于这种只会生成互补对，因此没有浪费的无效集合，算法效率达到理论值。
paper后面给出了各个步骤的正确性证明，但我没看懂。。。所以也就略过了 :)
总结
这篇paper中的算法是理想化的，只考虑了单点之间的inner join（也就是单表之间的join），没有考虑复杂情况如outer/semi/anti join...或嵌套情况如t1 left join (t2 join t3)，这时join关系就可能变为在一个表的集合和另一个表的集合之间。
在后继的paper中，作者引入了hypergraph来描述这种复杂且不对称的join关系，用hyper-edge来表示复杂join条件。但总体思路是类似的，只是问题变成了，在hypergraph的情况下如何去枚举所有的csg-cmp-pair。我们后续会聊下那篇paper。
