1 多表查询
1.1 多表简单join
select * from nkeys, aaa where nkeys.c3 = aaa.a3 and aaa.a2 = 2;
具体nkeys，aaa表的表定义，在附录一：aaa表；附录四：nkeys表中给出。
调用主流程：
1. mysql_select ->JOIN::optimize -> make_join_statistics ->SQL_SELECT::test_quick_select ->get_key_scans_params ->
根据查询条件，aaa表指定了查询条件：aaa.a2 = 2，对于指定查询条件的表，可以通过第3章节单表查询的流程找到针对查询条件的最优路径。当然，若aaa.a2列为unique列，那么就通过第3章节单表unique查询来判断。
2. if (join->const_tables != join_tables) ->
此处判断join查询中，指定了unique key查询条件的表的数量，与join中表的数量是否一致？所有指定了unique key查询条件的表，执行计划已经确定，必定是走unique key索引，因此不需要进行查询优化，代价评估。此处不一致，因此需要调用下面的choose_plan函数，确定整个join操作的最优路径。整个join操作的最优路径，包含两层含义：(一) join操作，涉及到的表的join顺序是最优的；(二) 每张表的执行路径同样也是最优的；最终的目标，是保证选择出整个join代价最小的路径。
3. choose_plan ->
4.1 optimize_straight_join -> best_access_path -> return
straight_join，join顺序确定，只需要确定每个table的最优路径。如果是straight_join，也就是说不对查询给定的table顺序进行调整，而仅仅是根据table的顺序，为每一个table找到最优的执行路径，选择4.1的代码路径。此路径相对简单，顺序遍历join结构中的每一张表，找到表的best_access_path，估算代价。一般情况下，不会选择此方案。
4.2 greedy_search ->
greedy_search函数的功能，是用贪心法找到局部最优的join执行计划，与optimize_straight_join函数不同，greedy_search函数会改变表的join顺序。
关于greedy_search函数的详细说明，可见sql_select.cc::greedy_search函数功能说明。简单来说，给定剩余join表集合，每次调用best_extension_by_limited_search函数，从剩余表集合中选择一个代价最小的表，加入到当前执行计划中来，直到剩余join表集合耗尽为止。
给定N张表的join，需要经过O(N!)次(N的阶层，card(5) = 120)的计算，才能找到最优的执行计划，cpu开销较大。Mysql的优化措施为，设置search_depth，控制最优路径的查找限制，search_depth参数在下面提到的best_extension_by_limited_search函数中使用。若N <= search_depth，则一定能找到最优计划；否则只能找到局部最优计划greedy_search函数的伪代码如下：
@code
procedure greedy_search
input: remaining_tables
output: pplan;
{
pplan = <>; // 当前已经选择的表的最优执行计划
do {
(t, a) = best_extension(pplan, remaining_tables);
pplan = concat(pplan, (t, a));
remaining_tables = remaining_tables - t;
} while (remaining_tables != {})
return pplan;
}
5. best_extension_by_limited_search ->
greedy_search函数传入的search_depth参数，在best_extension_by_limited_search函数中使用。
best_extension_by_limited_search函数是一个深度优先的递归调用。调用的深度即为search_depth。
若search_depth >= N(number of remaining tables)，则能够完成所有路径的遍历，找到对于remaining tables的一个最优执行计划。返回greedy_search的QEP，已经是针对于remaining tables则最优执行计划，greedy_search函数直接将此计划返回即可。
若search_depth < N，那么best_extension_by_limited_search函数不能在remaining tables中找到最优的执行计划，而只能找到一个局部最优的计划。此时，函数返回greedy_search，greedy_search会提取出当前局部最优计划的第一张表，作为下一个已经确定的join表。于此同时，greedy_search函数会将选中的table从remaining tables中删除，然后再次调用best_extension_by_limited_search函数，直到N(number of remaining tables) <= search_depth，余下的所有table，一次best_extension_by_limited_search函数调用，就能够找到最优的执行计划。
极端情况下，search_depth = 1，则best_extension_by_limited_search函数退化为宽度优先的策略，每次从remaining tables中提取能够与已经选出的最后一个table做join，并且扫描代价最小的table，然后立即返回greedy_search函数，greedy_search函数提取此表作为当前partial QEP的最后一张表。
best_extension_by_limited_search函数的伪代码实现，可参见附录三。
根据以上的分析，可以总结出greedy_search+ best_extension_by_limited_search两个函数的复杂度。
若N <= search_depth，则复杂度为O(N!)，best_extension_by_limited_search函数通过深度优先递归遍历，找到针对于 N tables的最优执行路径。
若N > search_depth，则复杂度为O(N*N^search_depth/search_depth)，greedy_search不能找到join的最优执行路径。
6. best_access_path ->
对于指定的表s，找到其最优的执行路径。可选的路径，必须是join查询中，可以完成nestloop join的路径，对于4.1章节给定的查询，aaa表，可选的路径有两条：aaa.a2索引(针对于aaa.a2 = 2)；aaa.a3索引(针对于aaa.a3 = nkeys.c3条件)。Best_access_path函数，其对每条路径的代价算法较为复杂，目前暂时不准备详尽分析其过程。
本系列文章主目录：MySQL数据库InnoDB存储引擎查询优化器实现的分析