在《浅析MySQL代价估计器》中，对JOIN::estimate_rowcount()进行了浅析。在这个函数中，主要是针对各种单表的Access Path的代价估计算法。当不存在多表Join时，上篇文章所写的内容基本就是完整的代价估计。 但如果存在多表Join，就需要决定多个表进行Join的顺序，不同的Join顺序还可能会影响表的Access Path。生成最终物理执行计划的过程也就是决定各个表Access Path的过程。
还是先举个例子，创建两个最简单的表，执行一条两个表的Join语句：
CREATE TABLE t1 ( id INT PRIMARY KEY, col1 INT, col2 INT, KEY index_col1 (col1)) ENGINE=INNODB; CREATE TABLE t2 ( id INT PRIMARY KEY, col1 INT, col2 INT, KEY index_col1 (col1)) ENGINE=INNODB;SELECT t1.*, t2.* FROM t1, t2 WHERE t1.col1 = t2.col2 AND t2.col2 < 10;就这个简单的SQL，都会产生很多种Access Path。
优化器首先会生成单表的Access Path，然后开始决定Join Order。我们来看一下上面的SELECT在不同Join Order下的Access Path选择：
先读t1再读t2先读t1表，此时可用的过滤条件有t1.col1 < 10（因为t2.col2 < 10并且t1.col1 = t2.col2）。此时，就t1表而言，可用的Access Path有：
• Table Scan 全表扫描• 在index_col1上使用t1.col1 < 10做Index Range Scan再读t2表，由于col2上没有建立索引，只能对采用全表扫描。MySQL-8.0种实现了Hash Join，这种情况下会采用Hash Join的方式实现Inner Join。
• 在t1表获得的记录上建立hash table，然后对t2表全表扫描，将读出的记录进行probe。先读t2再读t1先读t2表，由于col2上没有建立索引，只能全表扫描，并且过滤得到满足t2.col2 < 10的记录。
再读t1表，此时，可用的Access Path有：
• 全表扫描做hash join，将扫描得到的数据和之前t2表读到的数据逐行看是否匹配。• 在index_col1上使用t1.col1 < 10进行Index Range Scan做Hash join，将得到的数据与t2表读到的数据逐行看是否匹配，如果匹配，再回表获得t1表完整的数据。• 使用t2表得到的数据，根据t2.col2在t1上利用index_col1做查找，如果找到匹配的数据行，则回表获得t1表的完整数据。不同顺序的差异• 假如t2表上满足t2.col2 <10的记录有一万条，但t1表上没有记录满足t1.col1 <10，那么肯定是先读t1表，再读t2表最快。• 假如t2表上满足t2.col < 10的只有一条，并且t2表是个小表，同时t1表上满足t1.col1 < 10的记录很多，但是满足t1.col1 = t2.col2的记录数很少，那么此时先读t1表，再读t2表就非常耗时，反而应该先读t2表。根据以上分析我们有以下发现：
• 表中的数据非常影响Join Order的选择。• 上面两个例子中，其实都是先读记录数较少的表更好。其实，这也就是我们常说的将小表做为驱动表。因此预估会从表中读取多少数据的操作是十分重要的，它将极大影响Join Order。• 当先读t2，再读t1表时，其实多了一种Access Path：利用从前一个表读出数据，在这个表上利用索引做查找。因此读第二个表的Access Path可以分为两类：• scan/range：与前一篇中bool JOIN::estimate_rowcount()的Access Path相同，如果用了这种Access Path，对应的Join算法其实就是Hash Join。• ref/eq_ref：只在多表Join时才会出现的Access Path，利用前面表读到的记录在这个表的索引上进行检索。对应的Join算法其实就是Index Nested-Loop Join。在MySQL中，决定Join Order的基本思路概括起来就是枚举+代价估计。因此，我们在本文章中主要解决以下几个问题：
• 如何枚举不同的Join Order？• 对于每种Join Order，如何计算代价？• 如何在枚举的过程中剪枝来加速？Join Reorder我们先来看一下问题，n个表做Join，一共有几种Join的方式。我们假设所有的Join都是Inner Join。
Join Reorder的Search Space我们先来看三个表A，B，C做join：
,
,
,
,
,
共计12种Orders。如果用公式表示，n个表进行Join，其实有
种。
当n=4，有120种Join的方式。
当n=5，有1680种Join的方式。
当n=6，有30240种Join的方式。
...
想要完美找到多个表Join的最佳顺序，是个NP难问题，不存在多项式复杂度的算法。而把所有Join Order全部遍历的话，算法复杂度过高。
因此对于数据库优化器，就必须去限制Join Reorder的搜索空间（Search Space）。在一个较小的搜索空间，尽可能找到接近最优的Join Order。
在MySQL中，不会枚举所有Join Order。MySQL每次都是选择两个表进行Join，将Join后的结果做为驱动表再与第三个表进行Join。因此MySQL只会对至多对 种Join方式进行代价计算。
如果用树表示Join Order的话，MySQL搜索的所有的Join Order都会是同一种相似的结构，以 为例：
这棵树只是单向地向左延展，每个Inner Join的右节点永远只是一个单表，这种树我们叫左深树（Left Deep Tree）。而完整的Join Order空间还包括如下图的Bushy Tree，但MySQL永远不会搜索到这种Join Order：
Join Reorder 的搜索算法我们上一节说过，MySQL只会搜索满足左深树的Join Order。但左深树还是有 种，阶乘复杂度也是难以接受的，因此MySQL使用了参数optimizer_search_depth去进一步控制Join Order的搜索空间。
我们先来说一下参数optimizer_search_depth的作用，假设我们有10个表要参加Join，但optimizer_search_depth=3，那么我们的搜索过程其实是这样的：
第一次搜索，确定完整执行计划中第一个参与Join的表。确定方法是在10个表内选3个表进行全排列，计算每种排列下的cost，得到代价最小的3个表的Join Order，这个Join Order中第一个表就是确定为完整Join Order的第一个表。
第二次搜索，确定完整执行计划中第二个参与Join的表。确定方法是在剩下9个表内选3个表进行全排列，计算每种排列下的cost（此处计算cost是加上第一个表的完整计划的cost），得到代价最小的3个表的排列，这个排列中第一个表就是确定为完整执行计划中参与Join的第二个表。
......
第七次搜索，确定完整Join Order中第七个参与Join的表，确定方法是在剩下4个表内选3个表进行全排列，计算每种排列下的cost（此处计算cost是加上前六个表的完整计划的cost），得到代价最小的3个表的排列，这个排列中第一个表就是确定为完整执行计划中参与Join的第七个表。
第八次搜索，确定完整执行计划中最后三个参与Join的表，由于只剩下三个表了，则计算剩下三个表的的全排列的cost（此处计算cost是加上前七个表的完整计划的cost），得到代价最小的3个表的排列，将其加入到完整执行计划中。
用伪代码表示如下：
procedure greedy_searchinput: remaining_tablesoutput: pplan;{ pplan = <>; // 部分查询计划 do { // 得到下一个参与Join的表t以及位置n (t, n) = best_extension(pplan, remaining_tables); //将t与部分查询计划拼接，即t就是第n个参与Join的表 pplan = concat(pplan, (t, n)); // 维护还剩下哪些表没参加Join remaining_tables = remaining_tables - t; } while (remaining_tables != {}) return pplan;}现在，来计算一下算法复杂度，第一次搜索，需要从10个表里选出3个表全排列，有 种选取方式，第二次搜索有 种选取方式，...，最后一次搜索，有 种搜索方式。因此，求和后：
所以，如果有N个表参与Join，并给定optimizer_search_depth=d，则算法复杂度为 。当 时，算法复杂度为直接枚举所有左深树，复杂度为 。
MySQL官方代码中给出的算法复杂度估计为 ，暂不清楚官方的复杂度计算方法，如果大家有任何想法，欢迎讨论。
源码解读决定Join Order的代码都在函数choose_table_order()中 。代码结构和注释也都相对清楚，大家感兴趣地可以直接看源码，在这里，做一个简单的介绍。
预排序在MySQL中，optimizer_search_depth的默认值是62，意味着，大多数情况下，其实算法复杂度都会是 。因此，很多时候，剪枝承担了更多降低算法耗时的功能(剪枝算法在后面绍)。 而想要减枝更好发挥作用，就必须尽早搜索到较优的Join Order。
我们在引言中的例子发现，一般而言都是先读行数较少的表，然后再读行数较多表，这样得到的Join Order可能会更好，如果我们先枚举的Join Order都是先读小表，就有可能尽早找到较优的Join Order。因此，在选择order之前一个重要操作就是预排序，这个函数会按照有无Outer Join/Straight Join的依赖关系、有无key的引用、estimate_rowcount()中对表记录数的估计进行排序：
1. Outer Join和Straight会强制要求Join的顺序，因此先判断表之间有无Outer Join或者Straight Join的依赖关系2. 判断两个表之间有无key的依赖关系，假如t1和t2的join cond中，有t1.no_key = t2.key，那么先读t13. 如果上述都不满足，那么就比较在estimate_count()函数中得到的行数估计，小表在前。bool Join_tab_compare_default::operator()(const JOIN_TAB *jt1, const JOIN_TAB *jt2) const { // Sorting distinct tables, so a table should not be compared with itself assert(jt1 != jt2); // Outer Join和Straight会强制要求Join的顺序，因此先判断表之间有无Outer Join或者Straight Join的依赖关系 if (jt1->dependent & jt2->table_ref->map()) return false; if (jt2->dependent & jt1->table_ref->map()) return true; // 判断两个表之间有无key的依赖关系，假如t1和t2的join cond中，有t1.no_key = t2.key，那么先读t1 const bool jt1_keydep_jt2 = jt1->key_dependent & jt2->table_ref->map(); const bool jt2_keydep_jt1 = jt2->key_dependent & jt1->table_ref->map();if (jt1_keydep_jt2 && !jt2_keydep_jt1) return false; if (jt2_keydep_jt1 && !jt1_keydep_jt2) return true; // 如果上述都不满足，那么就比较在estimate_count()函数中得到的行数估计，小表在前。 if (jt1->found_records > jt2->found_records) return false; if (jt1->found_records < jt2->found_records) return true; return jt1 < jt2;}greedy_search搜索函数之后就会进入到greedy_search()函数中。
greedy_search()函数的伪代码在Join Reorder的搜索算法一节中已经展示过了，MySQL实际源码也差不多，我这里把主要逻辑列出来，感兴趣的读者可以看一下：
bool Optimize_table_order::greedy_search(table_map remaining_tables) { // const_tables不参与Join uint idx = join->const_tables; // index into 'join->best_ref' // 当前搜索到的best_idx uint best_idx; POSITION best_pos; JOIN_TAB *best_table; // the next plan node to be added to the curr QEP DBUG_TRACE; /* Number of tables that we are optimizing */ // remaining_tables是个bitmap，在这里计算还有多少表待优化 const uint n_tables = my_count_bits(remaining_tables); /* Number of tables remaining to be optimized */ uint size_remain = n_tables; ... // 循环开始，开始执行Join Reorder的搜索算法中提及的搜索流程 do { /* Find the extension of the current QEP with the lowest cost */ // 当前最好的完整查询计划的cost估计 join->best_read = DBL_MAX; // 当前最好的完整查询计划的rowcount join->best_rowcount = HA_POS_ERROR; found_plan_with_allowed_sj = false; // 开始第一次搜索，由于0～idx-1个表都是const_table，因此不参与搜索，直接从第idx个表开始搜索， // 搜索深度为search_depth if (best_extension_by_limited_search(remaining_tables, idx, search_depth)) return true; /* 'best_read < DBL_MAX' means that optimizer managed to find some plan and updated 'best_positions' array accordingly. */ assert(join->best_read < DBL_MAX); // 如果当前剩余待优化的表的数量小于search_depth，则意味着是最后一次搜索，已经可以结束了 if (size_remain <= search_depth || use_best_so_far) { /* 'join->best_positions' contains a complete optimal extension of the current partial QEP. */ DBUG_EXECUTE( "opt", print_plan(join, n_tables, idx ? join->best_positions[idx - 1].prefix_rowcount : 1.0, idx ? join->best_positions[idx - 1].prefix_cost : 0.0, idx ? join->best_positions[idx - 1].prefix_cost : 0.0, "optimal");); return false; } /* select the first table in the optimal extension as most promising */ // join->best_positions[idx]记录当前搜索到的cost最低的部分查询计划中的第一个表，这个表其实就是我们想要的表 best_pos = join->best_positions[idx]; best_table = best_pos.table; /* Each subsequent loop of 'best_extension_by_limited_search' uses 'join->positions' for cost estimates, therefore we have to update its value. */ // join->positions维护了当前的搜索状态 join->positions[idx] = best_pos; ... /* find the position of 'best_table' in 'join->best_ref' */ // 维护best_ref，best_ref是当前的最优的查询计划 best_idx = idx; JOIN_TAB *pos = join->best_ref[best_idx]; while (pos && best_table != pos) pos = join->best_ref[++best_idx]; memmove(join->best_ref + idx + 1, join->best_ref + idx, sizeof(JOIN_TAB *) * (best_idx - idx)); join->best_ref[idx] = best_table; // 维护remaining_tables remaining_tables &= ~(best_table->table_ref->map()); ... // 剩余待优化的表数量减一 --size_remain; // 下次需要确定的参与Join的表的idx加一 ++idx; } while (true); }best_extension函数greedy_search()函数会调用best_extension_by_limited_search()函数，每次都执行深度为optimizer_search_depth的搜索来确定下一个参与Join的表。
这个函数原理上其实也很简单，就是进行从剩余表中选optimizer_search_depth个表进行排列并且计算cost这个过程。best_extension()函数的源码和伪代码结构相似，因此，这里只展示伪代码。
伪代码如下：
procedure best_extension_by_limited_search( pplan in, // in, partial plan of tables-joined-so-far 已经参与join了的表组成部分plan pplan_cost, // in, cost of pplan pplan的cost remaining_tables, // in, set of tables not referenced in pplan 还没在pplan中的tables best_plan_so_far, // in/out, best plan found so far 至今发现的最好plan best_plan_so_far_cost,// in/out, cost of best_plan_so_far 至今发现的最好plan的cost search_depth) // in, maximum size of the plans being considered 当前要被搜索的plans的最大size { for each table T from remaining_tables { // Calculate the cost of using table T as above // 对于每个待优化的表，进行一系列的复杂的cost计算 cost = complex-series-of-calculations; // Add the cost to the cost so far. // 将cost加到pplan_cost pplan_cost+= cost; // 剪枝 prune_by_cost pruned_by_heuristic // 将当前pplan用上面得到best_access_method进行拓展 pplan= expand pplan by best_access_method; remaining_tables= remaining_tables - table T; // 如果还有没参与Join的表并且search_depth还大于1 if (remaining_tables is not an empty set and search_depth > 1) { // 如果table T是通过EQ_REF-joined优化的，用eq_ref_eq_ref_extension_by_limited_search进行拓展 // 否则用best_extension_by_limited_search进行拓展 if (table T is EQ_REF-joined) eq_ref_eq_ref_extension_by_limited_search( pplan, pplan_cost, remaining_tables, best_plan_so_far, best_plan_so_far_cost, search_depth - 1); else best_extension_by_limited_search(pplan, pplan_cost, remaining_tables, best_plan_so_far, best_plan_so_far_cost, search_depth - 1); } else { // 维护当前找到的最优plan的cost best_plan_so_far_cost= pplan_cost; best_plan_so_far= pplan; } } }该函数中的cost计算方式和剪枝方法会在之后章节中详细介绍。
在这个函数中有个特殊的优化，当前参与Join的表如果是通过eq_ref的方式进行Join的（eq_ref是指在被驱动表上通过检索一个唯一键进行Join），那么此时会将其他能够使用EQ_REF进行Join的表也加入到查询计划中。这个优化只在第一次遇到用eq_ref进行Join的表才会进行。
cost 计算在本节中，我们将看一下一个完整的多表Join的执行计划的代价计算。
在MySQL源码中，对Access Path有一个分类access_type：ref，eq_ref，range，scan等。在Join Reorder中的cost计算中，会将这些access_type进一步分为两类处理：
• ref，eq_ref：当被驱动表采用这种Access Path时，对应的Join算法为Index Nested Loop Join• range，scan等：当被驱动表采用这种Access Path时，对应的Join算法为Hash Joinref，eq_ref在讲ref,eq_ref的cost之前，先介绍一个概念：fanout。fanout可以理解为对于驱动表的每一条记录，能够在被驱动表中找出多少条与之能够成功Join的数据。
就eq_ref而言，对于驱动表上的每一条数据，肯定在被驱动表上只有一条数据与之满足Join条件，因此fanout是1。
而对于ref，驱动表上数据满足Join条件的数据其实不止一条，那么如何估计这个值呢？相信看过之前文章的同学很快能够想到，这其实又是records_per_key这个统计信息，也就是我们常说的Cardinality。
这样，对于ref和eq_ref我们就都获得了fanout。有了fanout，其实IO cost计算也就很简单了，无非就是多次读索引，每次读fanout行。而读索引的次数，也就是驱动表的行数（记为prefix_rowcount）。
在join的过程中，需要处理条数据，因此CPU cost 为:
prefix_rowcount * fanout * row_evaluate_cost小结总cost
prefix_rowcount * single_io_cost + prefix_rowcount * fanout * row_evaluate_costscan，range等我们之前在bool JOIN::estimate_rowcount()函数中计算了多种类型Access Path的cost，现在我们就是从中选择cost最小的Access Path在这里使用。
对于IO cost，其实就是要计算读几次被驱动表。在8.0中，虽然join算法从Block Nested Loop Join算法升级到了Hash Join，但cost的计算方式却没有改变，还是沿用Block Nested Loop Join算法的cost计算方式。因此，读被驱动表的次数其实就是 驱动表的数据量除以Join Buffer的大小。总的IO cost就是。
接下来看CPU cost，要计算CPU cost就要计算fanout值，从被驱动表中读出的数据并不是都会直接进行join，还可能会被谓词过滤一部分，这部分的影响用calculate_condition_filter()函数计算，在这里不多展开，假设在过滤后获得rows_after_filtering行数据。那么，其实只有rows_after_filtering行会参与join，会在判断predicate时就被过滤而不会参与join计算，cpu cost也就分为两部分：
join_buffer_cnt * (total_records - rows_after_filtering) *row_evalute_cost + prefix_rowcount * rows_after_filtering * row_evalute_cost说一点题外话，在阅读代码的时候，我发现当被驱动表的Access Path是range时，IO cost计算是直接，没有考虑Join buffer，非常疑惑，然后看到MySQL代码中这样的一行注释：
TODO:
We take into account possible use of join cache for ALL/index
access (see first else-branch below), but we don't take it into
account here for range/index\_merge access. Find out why this is so.
大意是，我们在计算全表扫描/覆盖索引扫描的cost的时候，考虑到Join Buffer的影响，但在计算索引范围扫描的cost的时，却没有考虑到Join Buffer的影响，现在我们也不知道为什么，所以记了个TODO。
小结总cost
Join_buffer_cnt * single_io_cost + join_buffer_cnt * (total_records - rows_after_filtering) *row_evalute_cost + prefix_rowcount * rows_after_filtering * row_evalute_costrowcount计算最后，来看Join之后的行数，对于scan/range方式的Access Path，由于已经提前估计了predicate的影响，因此行数就是，而对于ref/eq_ref，还没有考虑其他predicate的影响，因此利用calculate_condition_filter()函数又计算了filter_effect，所以行数是。
Access Path选择在计算完ref/eq_ref和scan/range的cost之后，选择cost最小的一种作为当前表最后的Access Path。
剪枝算法pruned_by_cost if (position->prefix_cost >= join->best_read && found_plan_with_allowed_sj) { DBUG_EXECUTE("opt", print_plan(join, idx + 1, position->prefix_rowcount, position->read_cost, position->prefix_cost, "prune_by_cost");); trace_one_table.add("pruned_by_cost", true); backout_nj_state(remaining_tables, s); continue; }基于Cost的剪枝最简单，当前的cost已经大于之前找到最小cost，直接剪枝。
pruned_by_heuristic if (prune_level == 1) { if (best_rowcount > position->prefix_rowcount || best_cost > position->prefix_cost || (idx == join->const_tables && // 's' is the first table in the QEP s->table() == join->sort_by_table)) { if (best_rowcount >= position->prefix_rowcount && best_cost >= position->prefix_cost && /* TODO: What is the reasoning behind this condition? */ (!(s->key_dependent & remaining_tables) || position->rows_fetched < 2.0)) { best_rowcount = position->prefix_rowcount; best_cost = position->prefix_cost; } } else if (found_plan_with_allowed_sj) { DBUG_EXECUTE("opt", print_plan(join, idx + 1, position->prefix_rowcount, position->read_cost, position->prefix_cost, "pruned_by_heuristic");); trace_one_table.add("pruned_by_heuristic", true); backout_nj_state(remaining_tables, s); continue; } }启发式剪枝可以通过控制参数optimizer_prune_level来决定是否开启。 这个剪枝影响非常大，只要在当前search depth发现过比现在好的部分查询计划（rowcount和cost都要更低），那么就停止这条分支的继续搜索。事实上，绝大多数的查询计划都会被这条规则剪去，当不开启这条剪枝规则时，在optimizer_search_depth默认62的条件，MySQL会近似穷举，但开启这条规则后，大多数查询计划都会被提前剪枝。
计算最佳Access Path的剪枝这部分剪枝主要是当找到一种ref/eq_ref的Access Path时，会有一些启发式规则来使得MySQL不去计算range/scan的cost。这部分规则很多，详细内容可以看MySQL给出的注释。
We do not consider index/table scan or range access if: 1a) The best 'ref' access produces fewer records than a table scan (or index scan, or range access), and 1b) The best 'ref' executed for all partial row combinations, is cheaper than a single scan. The rationale for comparing COST(ref_per_partial_row) * E(#partial_rows) vs COST(single_scan) is that if join buffering is used for the scan, then scan will not be performed E(#partial_rows) times, but E(#partial_rows)/E(#partial_rows_fit_in_buffer). At this point in best_access_path() we don't know this ratio, but it is somewhere between 1 and E(#partial_rows). To avoid overestimating the total cost of scanning, the heuristic used here has to assume that the ratio is 1. A more fine-grained cost comparison will be done later in this function. (2) The best way to perform table or index scan is to use 'range' access using index IDX. If it is a 'tight range' scan (i.e not a loose index scan' or 'index merge'), then ref access on the same index will perform equal or better if ref access can use the same or more number of key parts. (3) See above note about InnoDB. (4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access path, but there is no quick select) If the condition in the above brackets holds, then the only possible "table scan" access method is ALL/index (there is no quick select). Since we have a 'ref' access path, and FORCE INDEX instructs us to choose it over ALL/index, there is no need to consider a full table scan.总结本文浅析了MySQL Join Reorder算法的流程，cost计算，剪枝算法等，希望通过本文能帮助大家了解MySQL优化器生成执行计划的具体流程。在阅读MySQL优化器代码的过程中，也确实感觉到很多地方做的还是相对简陋，很多cost计算都很近似，我也只能根据自己的理解进行分析，如果有错误之处，欢迎大家指出。
作者简介田镜祺，AliSQL内核研发人员。当前主要从事SQL优化执行、DDL相关的研发和RDS运维工作。
来源-微信公众号:MySQL代码研究
出处:https://mp.weixin.qq.com/s/NLBBeNIvm4JQ-D_DgVoVNA
