4.8 执行计划的选择

这里介绍几个简单的例子帮助大家理解执行计划选择时的一些影响因素。

连接顺序和连接算法的选择

如下图所示，r₁ 到 rₙ 的连接，根据等价规则转换，可以先进行任意表的连接，具体有多少种连接顺序可以根据公式 (2(n-1))!/(n-1)! 计算得出。当 n 等于 3 的时候，有 12 种；当 n 等于 7 的时候，就有六十多万种，大家可以去计算一下这个连接数量是非常可怕的，如果要去遍历搜索每一种连接顺序，这个代价非常的高。

根据上节介绍的等价规则，连接操作是满足交换率的。假设当 n=5 时，可以在前三个的 12 种连接顺序中选择最好的一种与另外的两个进行连接，这样就又有 12 种连接顺序。对比原来的 5 个表进行任意连接导致较大的搜索空间而言，只有 12+12 种，这其实就是一种动态规划的思想。

另外这里面还涉及到 Interesting sort odrer 的概念，假设选择先进行前三个表的连接，采用的是 merge join（ 一般是有序的），即三个表连接之后会产生一个有序的顺序。这时需要判断这个有序的顺序能否在跟第四表和第五张表的连接中起到作用，如果能起到作用，那么这个连接就能产生一种叫做 Interesting sort odrer 的优势，通常也是会优先考虑这个优势的。

计划树形状

如下图中非左深树打了红叉，即这两个计划树不被推荐。在上一节介绍等价转换的例子中，也提到过左深跟右深的一些区别，等价转换之后更有优势的是偏左深的计划树的形状。

根据前文介绍可以总结出，左深树有以下两个明显优势：

• 减少了中间的临时关系，因为许多的算法都是从左边开始迭代的。

• 减少了连接顺序，前面介绍的公式 (2(n-1))!/(n-1)! 是在任意连接的基础上总结归纳得到的，也就是说上图中这三种情况其实都包含在这条公式里面。如果只考虑左深这种情况，那么归纳出来的公式应该是 n 的阶乘，相比于这个公式的计算结果，连接的选择空间就会小很多。

启发式规则

在前文介绍的等价规则转换的基础上，加入代价的判断，有些代价不好估计，但有些规则经过长期的验证，已经确认是有效的。如下列举了一些规则，在优化器里面会考虑这些启发式规则带来的优势，尽量去应用这些启发式的规则。

• 选择尽量下推。

• 投影尽早下推。

• 连接消除避免完全笛卡尔积操作。

• 连接的一个关系在连接属性上有索引，将这关系放在内层循环中采用索引连接。

• 连接的一个参数是排序的，用 merge join 可能比 hash join 好。

• 多个关系的并或交时，先对最小关系进行组合。

• 子查询的消除。

• 嵌套连接的消除。

• 使用等价谓词重写对条件化简。