1.1     best_access_path函数分析

同样是使用4.1章节中的测试语句：

select * from nkeys, aaa where nkeys.c3 = aaa.a3 and aaa.a2 = 2;

1.1.1  总流程分析

根据4.1章节的分析，join涉及到两张表，同时search_depth参数设置为62. N < search_depth，复杂度为O(N!) = 2! = 2(任何一张表，都可以做驱动表)，同时，查询优化能够找到最优的执行计划。

以上join，调用best_access_path的流程如下：

第一次：

best_access_path(table = aaa, key = 9, a2索引) -> best_access_path(table = nkeys, key = 2, c3索引) -> 得到(aaa, nkeys) join顺序的执行计划，记为P1。代价为CP1.

 

第二次：

best_access_path(table = nkeys, key = 2, c3索引) -> 得到一个partial执行计划PP2，代价为CPP2.

 

由于CP1 < CPP2，因此执行计划P1要由于partial执行计划PP2，P1为最优执行计划，直接退出即可。为何P1的代价CP1要小于PP2的代价CPP2，下一章节会给出详细的分析。

1.1.2  代价估计分析

首先，best_access_path函数，需要计算的代价包括：

• records_read: 选择此路径，需要读取多少记录。
• read_time:       选择此路径，需要多少读取时间。

 

其次，best_extension_by_limited_search函数，如何计算一个已选择的路径的代价：

• current_record_count = record_count * join->positions[idx].records_read;

当前路径读取的记录数，是所有路径中的表返回的记录数的乘积。

• current_read_time = read_time + join->positions[idx].read_time;

当前路径读取需要的时间，是所有路径中的表的读取时间的总和。

• 路径总代价 = current_read_time + (current_record_count / TIME_FOR_COMPARE)

路径总代价，为底层IO时间，加上上层CPU时间，这与前面的代价模型一致

• 若 路径总代价 < join->best_read，同时当前路径已经是完整路径，则认为当前路径是目前最优的。
• 在测试的join语句中，P1的代价CP1 = 2.1990000000000003；PP2的代价CPP2 = 1.0 + (6/5) = 2.2000000000000000，因此CPP2 > CP1，确定P1为最优执行计划。

1.1.3  best_access_path函数流程

接下来，我们详细分析这两个代价在best_access_path函数中是如何计算？

 

best_access_path主流程：

if (s->keyuse)

1. 若当前表s可以进行索引扫描，则首先判断各索引扫描的代价；若不能进行索引扫描，则直接判断全表扫描的代价。以下将重点分析索引扫描代价计算模型。索引扫描代价计算，主要分这么几种情况：

 

if (found_part == PREV_BITS(uint, keyinfo->key_parts) && !ref_or_null_part)

1. 情况1：指定查询条件覆盖索引全部列，索引所有的列，都给定了查询条件(没有给定is null条件。例如：aaa.a2 = 2；2为常量条件，同时索引只有a2一个字段，满足情况1的约束。)

if (!found_ref)

a)         情况1.1：指定查询条件均为常量条件，没有与其他表之间的join条件(aaa.a2 = 2，2为常量条件，可走此路径)。

针对情况1.1，可参考best_access_path函数中的#ReuseRangeEstimateForRef-1#说明。简单来说，就是可以使用单表range查询优化中给出的records估计值。

records = (double) table->quick_rows[key];

其中，quick_rows[key]在单表range查询优化中赋值。

 

b)         情况1.2：指定的查询条件覆盖索引中的所有列。但是包含了到其他表的引用，不全是常量查询条件，与情况1.1有所不同。例如：nkeys.c3 = aaa.a3，对于表nkeys，其有一个c3索引，正好只包含c3列，索引列全覆盖；同时查询条件引用到了aaa表的a3列，非常量条件，不属于情况1.1，而属于情况1.2。

针对情况1.2，可参考best_access_path函数中的#ResueRangeEstimateForRef-2#说明。

由于情况1.2包含了到其他表的引用，因此range查询优化可能包含部分条件(常量条件部分)，或者是未经过range查询优化(所有的条件均为引用条件，无常量条件)。

1.                          i.              首先，判断存储引擎层面是否收集、设置rec_per_key参数。若设置，则

records = keyinfo->rec_per_key[keyinfo->keypars - 1]

包含所有索引键值的rec_per_key的取值。例如idx1[c1,c2,c3]，那么此处的是rec_per_key[c1,c2,c3]。

1.                        ii.              其次，若rec_per_key未收集。那么则根据全表数据量来预估。

records = s->records / rec * …

一个复杂的计算公式，其中s->records为全表数据量；rec为unique records的估计值。

1.                       iii.              最后，做一次微调。若有常量查询条件，那么range查询优化可能已经针对常量条件部分做了索引的预估。若i，ii步骤计算的records值 > range查询优化中计算出来的部分keys的records，则，调整records取值.

records = table->quick_rows[key];

若table->quick_rows[key]小于records，则调整records的取值。

 

c)         根据情况1.1，1.2计算出来的records取值，统计将s表通过当前索引加入partial执行计划之后，partial执行计划的records开销。

partial_plan_records = record_count * records;

其中，records_count为当前partial plan的开销，records为当前表s选择索引的开销，根据情况1.1或情况1.2计算得来。

 

1. 情况2：查询条件未覆盖索引中的所有列，仅仅只包含部分索引列，或者是包含了索引所有列，但是部分列上的条件为is null判断(例如：索引idx(c1,c2,c3)，给定的查询条件为c1 = 1 and c2 = 2，没有指定c3上的查询条件)。

 

if ( table->quick_keys.is_set(key) && !found_ref &&                         // C1

table->quick_key_parts[key] == max_key_part &&                      // C2

table->quick_n_ranges[key] == 1+test(ref_or_null_part) )                   // C3

a)         情况2.1：情况2.1与情况1.1类似。情况2.1处理的也是全指定const条件的index scan，与情况1.1不同之处在于，所有这些const条件，没有覆盖索引全部列。条件C1为range查询优化选择了此索引同时查询条件中没有引用条件；条件C2，C3的原理，可参考best_access_path函数中的#ReuseRangeEstimateForRef-3#说明。

tmp = records = (double) table->quick_rows[key];

在情况2.1下，records的计算，可以直接才有range查询优化中计算出来的取值。

 

b)         情况2.2：情况2.2与情况1.2类似。指定的查询条件中，包括到其他表的引用。此时range查询优化计算出的records是放大的(没有考虑引用条件的过滤，因为引用条件在真正执行之前，无法获取其实际取值)。

1.                          i.              首先，判断存储引擎层面是否收集、设置rec_per_key参数。若收集，则将records设置为max_key_part的rec_per_key取值。

records = keyinfo->rec_per_key[max_key_part - 1];

当然，此时也需要微调，若rec_per_key的取值过于乐观，过大，甚至大于range查询优化中计算的部分const查询条件返回的records，则重设records取值。

records = table->quick_rows[key];

1.                        ii.              若rec_per_key未收集。则根据以下算法，计算records。

records = (x * (b-a) + a*c - b) / (c - 1)

b = records matched by whole key

a = records matched by first key part (1% of all records)

c = number of key parts in key

x = used key parts (1 <= x <= c)

1.                       iii.              对于i，ii步骤中计算出来的records进行微调。仍旧使用一直以来的调整策略。若计算出来的records取值过于乐观，甚至大于range查询优化针对部分const条件计算而来的records取值，则重设records。

tmp = records = table->quick_rows[key];

 

1. 在情况1，情况2确定了当前表s在给定索引key下的records计算，并得到partial_plan_records之后，判断当前key是否为最优选择；若是，则将当前表s的最优访问路径设置为key；否则跳过key，选择下一个表s的可选路径，继续。

if (partial_plan_records < best_time - records/ TIME_FOR_COMPARE) {

best_time = tmp + records / TIME_FOR_COMPARE;

best = tmp;

best_records = records;

best_key = start_key;

}

其中，best_time为当前partial plan的最优路径(包括s表)；tmp = partial_plan_records。

 

1. 继续步骤1，直到完成s->keyuse中所有的索引，根据步骤4的判断，获取当前表s上的最优索引。
2. 在步骤5完成，遍历所有可选索引之后，判断是否需要对全表扫描进行判断。mysql查询优化，将全表扫描的权重放的较低，一般情况下，不会在join情况下，选择全表扫描做nestloop join，否则性能一定较差。

在完成以上6个步骤之后，best_access_path函数结束。当前表s，s的最优路径key，都已经得到，同时加入s表之后，当前partial plan的代价已经得到。在best_extension_by_limited_search函数中，根据search_depth参数的设置，会获取一个完整的plan，然后将此plan与已有最优的plan进行比较，若更优则替换；否则放弃当前plan，进行寻找下一个。

本系列文章主目录：MySQL数据库InnoDB存储引擎查询优化器实现的分析

建议继续学习：

1. Mysql查询优化器浅析（上）    (阅读：2503)
2. MySQL数据库InnoDB存储引擎查询优化器实现的分析之单表查询    (阅读：2364)
3. Mysql查询优化器浅析（下）    (阅读：2051)
4. MySQL数据库InnoDB存储引擎查询优化器实现的分析之单表unique查询    (阅读：1975)
5. MySQL数据库InnoDB存储引擎查询优化器实现的分析    (阅读：1879)
6. MySQL数据库InnoDB存储引擎查询优化器实现的分析之多表简单JOIN查询    (阅读：1849)
7. MySQL数据库InnoDB存储引擎查询优化器实现的分析之optimizer_search_depth参数    (阅读：1776)
8. MySQL数据库InnoDB存储引擎查询优化器实现的分析之附录    (阅读：1744)
9. MySQL数据库InnoDB存储引擎查询优化器实现的分析之统计信息    (阅读：1549)