MySQL数据库InnoDB存储引擎查询优化器实现的分析之best_access_path函数分析
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)
- 若当前表s可以进行索引扫描,则首先判断各索引扫描的代价;若不能进行索引扫描,则直接判断全表扫描的代价。以下将重点分析索引扫描代价计算模型。索引扫描代价计算,主要分这么几种情况:
if (found_part == PREV_BITS(uint, keyinfo->key_parts) && !ref_or_null_part)
- 情况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查询优化(所有的条件均为引用条件,无常量条件)。
- 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]。
- ii. 其次,若rec_per_key未收集。那么则根据全表数据量来预估。
records = s->records / rec * …
一个复杂的计算公式,其中s->records为全表数据量;rec为unique records的估计值。
- 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计算得来。
- 情况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是放大的(没有考虑引用条件的过滤,因为引用条件在真正执行之前,无法获取其实际取值)。
- 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];
- 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)
- iii. 对于i,ii步骤中计算出来的records进行微调。仍旧使用一直以来的调整策略。若计算出来的records取值过于乐观,甚至大于range查询优化针对部分const条件计算而来的records取值,则重设records。
tmp = records = table->quick_rows[key];
- 在情况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,直到完成s->keyuse中所有的索引,根据步骤4的判断,获取当前表s上的最优索引。
- 在步骤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存储引擎查询优化器实现的分析
建议继续学习:
- Mysql查询优化器浅析(上) (阅读:2536)
- MySQL数据库InnoDB存储引擎查询优化器实现的分析之单表查询 (阅读:2483)
- Mysql查询优化器浅析(下) (阅读:2094)
- MySQL数据库InnoDB存储引擎查询优化器实现的分析之单表unique查询 (阅读:2105)
- MySQL数据库InnoDB存储引擎查询优化器实现的分析 (阅读:1981)
- MySQL数据库InnoDB存储引擎查询优化器实现的分析之多表简单JOIN查询 (阅读:2026)
- MySQL数据库InnoDB存储引擎查询优化器实现的分析之optimizer_search_depth参数 (阅读:1909)
- MySQL数据库InnoDB存储引擎查询优化器实现的分析之附录 (阅读:1859)
- MySQL数据库InnoDB存储引擎查询优化器实现的分析之统计信息 (阅读:1657)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:Eugene 来源: MySQLOPS 数据库与运维自动化技术分享
- 标签: best_access_path 查询优化器
- 发布时间:2012-01-08 22:27:17
- [55] IOS安全–浅谈关于IOS加固的几种方法
- [54] android 开发入门
- [54] 图书馆的世界纪录
- [54] 如何拿下简短的域名
- [52] Oracle MTS模式下 进程地址与会话信
- [52] Go Reflect 性能
- [49] 【社会化设计】自我(self)部分――欢迎区
- [48] 读书笔记-壹百度:百度十年千倍的29条法则
- [41] 程序员技术练级攻略
- [35] 视觉调整-设计师 vs. 逻辑