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存储引擎查询优化器实现的分析

建议继续学习：

1. HBase二级索引与Join    (阅读：5790)
2. SQL里是否可以使用JOIN    (阅读：4929)
3. Oracle hash join    (阅读：3185)
4. MySQL 连接    (阅读：3074)
5. Mysql查询优化器浅析（上）    (阅读：2536)
6. MySQL数据库InnoDB存储引擎查询优化器实现的分析之单表查询    (阅读：2483)
7. Mysql查询优化器浅析（下）    (阅读：2094)
8. MySQL数据库InnoDB存储引擎查询优化器实现的分析之单表unique查询    (阅读：2105)
9. MySQL数据库InnoDB存储引擎查询优化器实现的分析    (阅读：1981)
10. MySQL数据库InnoDB存储引擎查询优化器实现的分析之optimizer_search_depth参数    (阅读：1909)