在看MySQL优化器代码过程中，这应该是相对较简单/代码较清晰的部分了。MySQL优化器有两个自由度：单表访问方式，多表顺序选择。前文已经介绍过MySQL单表访问的一些考量(ref/range等)，本文将介绍JOIN在顺序选择上的复杂度分析。

   当有多个表需要JOIN的时候，MySQL首先会处理两类特殊情况，一个是常数表，一个是由于外连接导致顺序依赖关系。前者总是放在关联的最前面，后者会在遍历的时候考虑。本文将忽略上面两点，从较宏观角度看JOIN顺序选择时候的复杂度。

   在设置了参数prune_level(默认设置)后，MySQL使用"极其"贪婪的方式获取顺序。如果未设置，则使用了有限穷举获取"最优"的执行计划。

1. 有限穷举

   有限穷举只在参数prune_level关闭时才使用，默认情况prune_level时打开的。所以，MySQL一般不这么做。如果只想了解prune_level打开的时候，直接跳过本节，参考贪婪的MySQL。

   在关闭参数prune_level后，MySQL基本上就是穷举了，说"有限"是指，当关联表的数量超过63时(search_depth的默认值)，达到最大深度， MySQL将分多个阶段穷举。当关联表的数量较少的时候(小于search_depth)，MySQL会穷举所有可能，然后计算每个JOIN顺序的成本，选择成本最低的作为其执行计划。关于这部分的算法复杂度，在代码注释中有较为详细的描述，建议阅读函数greedy_search的注释先。下面是注释部分的两段伪代码，很好的描述了整个过程：
1.1 greedy_search

   这里的(t , a)表示，每次best_extension返回下一个需要JOIN的表t，并且确定的访问方式是a。上面的代码中，执行计划的扩展由函数best_extension，初始pplan为空，do循环结束输出最终的执行计划。
1.2 best_extension

   best_extension中调用函数best_extension_by_limited_search完成递归遍历，其输入是部分执行计划(pplan)和它的成本，函数目的是找到下一个关联的表。思路很简单，遍历所有剩余表，对每一个表，计算对应的"局部"最优执行计划，当然计算这个“局部”最优仍然是调用这个函数，所以这是一个深度优先的遍历。

   伪代码(是不是又有人说我总贴代码了)：

   一个说明：在每次遍历的时候，一旦发现成本大于当前的最优成本，则放弃，不再继续深入。
1.3 简单的小结

函数的输入：
    部分执行计划 partial plan
    N个剩余表
函数输出：
    当 N   search_depth，返回search_depth个表的最优执行计划，并合并到部分执行计划
        递归调用该函数，输入为：当前部分执行计划   剩余表N-depth

1.4 复杂度分析

   所以，复杂度可能是O(N*N^search_depth/search_depth)。如果search_depth > N 那么算法的复杂度就是O(N!)。通常MySQL优化器分析的复杂度都是O(N!)。
1.5 边界情形

   有两个比较极端的情况：

   – 当需要JOIN的表的数量小于search_depth时，这里就退化为一个深度优先的穷举确定最优执行计划

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

   剩余的情况就是介于上面两者之间。

2. 贪婪的MySQL

   在打开了参数prune_level(默认开启)后，MySQL不再使用穷举的方式扩展执行计划，而是在剩余表中直接选取访问最少纪录数的表。按照MySQL手册上的描述是：根据经验来看，这种”educated guess”基本不会漏掉最优的执行计划，但是却可以大大(dramatically )缩小搜索空间。要是你怀疑漏掉了某个最优的执行计划，你可以考虑关闭参数试试，当然这会导致搜索空间增大，优化器执行时间偏长。

   这个参数在深度优先搜索中起作用，在进行深度探索时，根据current_record_count和current_read_time，来确定，这是不是一个好的执行计划。(原本是需要递归调用计算成本确定)

   下面是一个简单的伪代码描述：

场景：
pplan             当前部分执行计划(初始为空) short for partial plan
N remaining table     当前剩余表(初始化时，为除了常数表之外的所有表)
    这N表记为T[0] T[1] ... T[N-1]

计算代码：

   说明：

   (1) 伪代码中未考虑依赖关系。第一个表的COST总是会计算出来。

   (2) 面对pplan和T[0...N-1]时，只计算pplan与T[0],T[1]…T[N-1]的关联后各自的current_record_count，并以此为依据选择，pplan应该跟哪一个表JOIN。除了第一个表(搜索树的最左边的那各分支)会递推计算其代价，其他所有分支都只是蜻蜓点水般只计算一级，而不会深度递归计算。

   (3) 这看起来这是一个非常激进的优化方式。

3. 开始前的排序

   MySQL在开始确定JOIN顺序之前会根据每个表可能访问的纪录数，进行一次排序。这一步看似多余，但是当穷举搜索时，可以大大的减少执行计划需要探测的深度。

   当评估某个执行计划的时候，如果某一步发现当前的cost已经大于最优的执行计划时，则立即退出评估。这意味着，如果最先找到最优的执行计划，那么需要做的评估将会少很多。如果某个表需要扫描的行数越少，那么可以初步认为越先使用越好。当然，因为这里的排序评估是没有使用JOIN条件的，所以，看起来需要扫描很多的，也可能加上JOIN以后只需要扫描很少的记录。
4. 函数调用栈

--转自