查询性能提升利器：CirroData之join order选择算法

在有限的搜索空间下，表连接的排列组合数会随着表个数的增加而迅速增长，如果这个组合数量巨大，连接次数显然是一个很高的数量级，大可能的连接次数是N！，例如参与连接的基表个数为5时，表连接次数为120次；参与连接的基表个数为10时，表连接次数达到了3628800次！

显然，数据库使用者在复杂数据查询场景下编写SQL脚本时，难以对结果进行预判。这时，就需要引入优化器，在有限的时间内找出优的解决方案。Cost-Based Optimizer（CBO） 是数据库查询优化中一种常用的优化器，其通过对表的统计来决定对于结构化查询有效的查询执行计划。

CBO 中的 join order 选择算法对于海量数据查询而言，是性能提升的重要技术手段。Join order 选择算法简单来说就是从可行的 join order 中挑选出一个好的，但是要在有限的时间和空间下做好这件事却是数据库中的难题之一。对于复杂的Join算子优化，采用不同的join order，花费CPU资源、内存资源的差异会比较大，这也意味着不同的join order有不同的执行效率。

例如，A join B join C，A、B表都很大，C表很小，那A join B很显然需要大量的系统资源来运算，执行时间必然不会短。但是使用A join C join B的执行顺序，A与较小的C表join必然会很快得到结果，且结果集-会很小，再使用生成的小的结果集与B做连接，性能显然比种方案好。因此找到一个好的连接顺序，对于查询的性能至关重要。

目前流行的数据库中，针对join order选择普遍采用的算法包括动态规划算法、贪心算法、遗传算法等。动态规划算法需要遍历全部解空间，但一定可以获得优解，是优化算法的一种；而贪心算法和遗传算法都属于启发算法，即基于直观或者经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与优解的偏离程度一般不能预计。

表3-1对动态规划算法和贪心算法进行了简单的对比：

常见的数据库中，PostgreSQL和GreenPlum在表数目较少时采用了动态规划算法，表数目较多时采用遗传算法来解决该问题；而MySQL则主要通过贪心算法来实现join order的选择。

我们在制定CirroData数据库的设计方案时，充分考虑到了CirroData分析型数据库面向的PB级海量数据查询场景，采用了动态规划算法和贪心算法相结合的策略，以达到佳查询效率。

动态规划算法需要遍历全部解空间，一定可以获得优解，因此它是CirroData的方案。但是即使CirroData已经基于表之间的连接关系对搜索范围做了较为仔细的范围限定，算法搜索的可能组合数仍会由于表的增多，造成巨大的搜索耗时。

因此CirroData在对join order选择的过程中采取的策略是，当参与join的表个数不超过8时，采用动态规划算法，超过8时采用贪心算法。

当表数量较少时，CirroData采用迭代的方式，从单个表出发，先初始化基表的代价，然后尝试求两个表的优join order，再逐步迭代求解3个表、4个表...，从而穷举得到优的join order。

显然穷举会造成过多的join order组合，但是实际开发中会基于表之间连接顺序的限制进行剪枝操作，另外由于动态规划本身会记录重复的子问题、连接路径建立也是一个优胜劣汰的过程等因素，有些组合并不会出现，这也在一定程度上控制了算法的时间复杂度。具体可以通过下面的例子了解CirroData基于动态规划的join order选择算法的具体过程。

例:  SELECT * FROM A, B, C, D

WHERE A.col=B.col AND A.col=C.col AND A.col=D.col;

初始化——构造层关系，假设使用path结构存储连接路径，则叶子节点表示为path [1]，在层中，每个关系的优路径就是这个基表本身，如图3-1所示：

图3-1 待连接的基表

归纳——假设已经生成1~L-1层子树，则求解第L层的关系，在满足join key和连接顺序限制的基础上尝试生成左深树和紧密树如图3-2所示，直到终找到优join order。具体求解过程可参考表3-2，其中L表示当前生成连接树的总层次，L <= 总基表数，其中L左表示当前待连接的关系左侧的连接树；L右表示当前待连接关系右侧的连接树，L左= L - L右。

图3-2 左深树和紧密树

表3-2基于动态规划的join order构造过程

为了更清楚的描述紧密树的生成方式，本例再增加两个参与join的基表E，F，通过表3-3描述了6个表做join的时候生成紧密树的过程。左深树的生成过程与上例相似，不再赘述。

表3-3 紧密树的生成

当表数量超过8个时，CirroData采取贪心算法来进行join order的选择。进行贪心选择之前，需要对参与join的基表，基于优先级规则进行排序，因为小表会产生更小的代价，在满足语义的前提下应该尽可能的把元组个数少的的基表排在前面，排序的优先级如下。

相对动态规划算法，CirroData基于贪心的join order选择算法不会再穷举所有的join order，本文通过下面的例子描述CirroData基于贪心的join order选择算法的具体过程。为了方便描述，例中仅以5个基表描述基于贪心的join order选择算法，实际应用场景中join order的构造过程与之类似。

例:  SELECT * FROM A, B, C, D,E

WHERE A.col=B.col AND B.col=C.col AND C.col=D.col AND D.col=E.col;

本例假设没有依赖关系和建引用关系，搜索深度为2，构造过程详见表3-4。其中L表示当前生成的左深树的总层数，best_ref表示使用深度搜索算法获得待定的局部优解，终选出的join order也会保存在这里，position表示在待定的局部优解best_ref基础上贪心选择出的确定的局部优解。

每次贪心选择之前都会将已得到的局部优join order与即将加入的基表及其以后的depth个没有连接过的基表进行一遍深度优先搜索，根据表的代价和限制关系查找新的局部优解。之所以说是局部的，是因为深度优先搜索的搜索深度限制，这个限制可以避免表数量过多造成的大数量级连接组合的情况。在深度优先搜索算法递归调用的过程中，深度会逐层递减，查询树也从叶子逐步向上层构造。

贪心算法体现在每一次深搜的结果总认为是本次循环得到的优结果，并且从best_ref中取出个表作为确定局部优解的一部分，为下一次连接提供依据。当构造的join order的搜索深度等于表的个数，或提前构造出优的join order（深搜遍历到后一层把可连接的基表用光了，没有可连接的基表了）时，join order构造过程结束，得到的优join order存储在best_ref中。

表3-4 基于贪心的join order构造过程

通过了解算法中两个边界情况，可以更清晰的理解基于贪心的join order算法，因为其他情况皆介于二者之间。

当参与JOIN的表的个数小于depth时，基于贪心的join order选择算法将退化为一个深度优先的穷举算法确定优执行计划；

当depth = 1的时候，函数退化为"极其"贪婪的算法，每次从当前的剩余的表中取一个代价小的，来扩展当前的执行计划。

CirroData的Join order选择算法为执行计划找到了更好、甚至好的连接顺序，在大多数情况下提升查询语句的执行效率，这正是CirroData开发工作者愿意深入探索的原因之一。

但是考虑到对CirroData查询性能的进一步优化，想要通过CBO获得更满意的性能效果还要更多的依赖基数估计和代价模型的准确性，但是实际上当前CirroData的基数估计模型和代价模型，尤其是代价模型还有待完善。

因此，CirroData在探索合适的join order选择算法的同时，如何更好的进行基数估计和查询子树各类关键算子的代价估计也是一个值得关注的问题。