技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> MySQL --> MySQL数据库InnoDB存储引擎查询优化器实现的分析之best_access_path函数分析

MySQL数据库InnoDB存储引擎查询优化器实现的分析之best_access_path函数分析

浏览:1553次  出处信息

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查询优化器浅析(上)    (阅读:2536)
  2. MySQL数据库InnoDB存储引擎查询优化器实现的分析之单表查询    (阅读:2483)
  3. Mysql查询优化器浅析(下)    (阅读:2094)
  4. MySQL数据库InnoDB存储引擎查询优化器实现的分析之单表unique查询    (阅读:2105)
  5. MySQL数据库InnoDB存储引擎查询优化器实现的分析    (阅读:1981)
  6. MySQL数据库InnoDB存储引擎查询优化器实现的分析之多表简单JOIN查询    (阅读:2026)
  7. MySQL数据库InnoDB存储引擎查询优化器实现的分析之optimizer_search_depth参数    (阅读:1909)
  8. MySQL数据库InnoDB存储引擎查询优化器实现的分析之附录    (阅读:1859)
  9. MySQL数据库InnoDB存储引擎查询优化器实现的分析之统计信息    (阅读:1657)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1