MySQL源码:Range和Ref优化的成本评估

在开始介绍index merge/ror优化之前，打算先介绍mysql是如何对range/ref做成本评估的。mysql是基于成本(cost)模型选择执行计划，在多个range，全表扫描，ref之间会选择成本最小的作为最终的执行计划。仍然强烈建议先阅读登博的slide：《查询优化浅析》，文中

在开始介绍index merge/ror优化之前，打算先介绍mysql是如何对range/ref做成本评估的。mysql是基于成本(cost)模型选择执行计划，在多个range，全表扫描，ref之间会选择成本最小的作为最终的执行计划。仍然强烈建议先阅读登博的slide：《查询优化浅析》，文中较为详细的介绍mysql在range优化时成本的计算。

本文将继续介绍range/ref执行计划选择的一些不容忽略的细节。希望看客能够通过此文能够了解更多细节。

目录

• 0. 成本计算的总原则
• 1. range成本的计算与分析
  • 1.1 range返回的记录数
  • 1.2 cpu cost
  • 1.3 io cost
  • 1.4 全表扫描的成本
  • 1.5 关于range执行计划的分析
  • 1.6 验证
  • 1.7 一些限制
• 2. ref成本的计算与分析
  • 2.1 ref返回的记录数
  • 2.2 cpu cost
  • 2.3 io cost
  • 2.4 全表扫描的成本
  • 2.5 关于ref执行计划的分析
  • 2.6 验证
• 3. 上面计算的局限性
• 4. 案例中使用的数据和表

0. 成本计算的总原则

mysql的一个执行计划，有两部分成本，cpu成本(cpu cost)和io成本(io cost)。cpu cost是指查询出纪录后，需要做过滤等处理的时候的cpu消耗，io cost是指，从存储引擎读取数据时需要做的io消耗。

总成本 ＝ cpu cost + io cost

补充说明：(1) io成本计算不考虑缓存的影响。因为在优化器本身是无法预知需要的数据到底在内存中还是磁盘上。

1. range成本的计算与分析

mysql使用一颗sel_arg的树形结构描述了where条件中的range，如果有多个range，则使用递归的方式遍历sel_arg结构，在前面详细的介绍range的红黑树结构，以及mysql如何遍历之。

接上文，这里将看看，遍历到最后，mysql如何计算一个简单range的成本。

1.1 range返回的记录数

mysql首先计算range需要返回都少纪录，通过函数check_quick_select返回对某个索引做range查询大约命中多少条纪录。

found_records= check_quick_select(param, idx, *key, update_tbl_stats); 1.2 cpu cost #define time_for_compare 5 // 5 compares == one read double cpu_cost= (double) found_records / time_for_compare; 1.3 io cost

对于innodb的二级索引，且不是覆盖扫描：

found_read_time := number of ranges + found_records

这里，found_records是主要部分，number of ranges表示一共有多少个range，这是一个修正值，表示io cost不小于range的个数。

1.4 全表扫描的成本

具体的，对于innodb表，我们来看：

read_time= number of total page + （records / time_for_compare + 1） + 1.1;

对于innodb取值为：主键索引(数据)所使用的page数量(stat_clustered_index_size)

对于myisam取值为：stats.data_file_length/io_size + file->tables

1.5 关于range执行计划的分析

这里来看看，range的选择度(selectivty)大概为多少的时候，会放弃range优化，而选择全表扫描。下面时一个定量的分析：

(1) 假设总记录数为r；range需要返回的纪录数为r

(2) 假设该表的总页面数(io cost)为p；单个页面纪录数为c

[r+1frac{r}{5} > p + frac{r}{5} + 1 + 1.1 ]

[ frac{r}{r} > frac{1}{6} + frac{5}{6} * frac{p}{r} + frac{5.5}{6*r} ]

[ frac{r}{r} > frac{1}{6} + frac{5}{6} * frac{1}{c} frac{5.5}{6*r} ]

在我的测试案例中，p=4，r=1016 ，有

[ frac{r}{r} > 0.171 ]

也就是说这个案例中，如果选择度(selectivity)高于17.1%就会放弃range优化，而走全表扫描。这里纪录数超过1016*0.171＝173时将放弃range优化。

1.6 验证

mysql通过函数check_quick_select返回range可能扫描的记录数，所以，这里通过对该函数设置断点，并手动设置返回值，通过此来验证上面对selectivity的计算，详细地：

(gdb) p head->file->stats.records $1 = 1016 (gdb) p head->file->scan_time() $3 = 4 (gdb) p 1016*(1.0/6+(5.0/6)*(4.0/1016)+5.5/(6*1016)) $43 = 173.58333333333329 (gdb) b check_quick_select breakpoint 5 at 0x679377: file opt_range.cc, line 7436. (gdb) c continuing. 遇到断点： (gdb) return 173 看到： root@test 05:07:52>explain select * from users where reg_date >= '2012-09-20 12:00:00'; +----+-------------+-------+-------+---------------+-------------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | extra | +----+-------------+-------+-------+---------------+-------------+---------+------+------+-------------+ | 1 | simple | users | range | ind_regdate | ind_regdate | 9 | null | 173 | using where | +----+-------------+-------+-------+---------------+-------------+---------+------+------+-------------+ (gdb) return 174 看到 root@test 05:08:05>explain select * from users where reg_date >= '2012-09-20 12:00:00'; +----+-------------+-------+------+---------------+------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | extra | +----+-------------+-------+------+---------------+------+---------+------+------+-------------+ | 1 | simple | users | all | ind_regdate | null | null | null | 1016 | using where | +----+-------------+-------+------+---------------+------+---------+------+------+-------------+

上面可以看到，如果range命中的记录数超过173的时候，就会放弃range，选择全表扫描。

1.7 一些限制

(1) 无论时innodb还是myisam的scan_time，range返回的记录数都不是精确值，而且对于innodb，总记录数也不是精确值，所以上面只是一个high level的预估。

(2) 上面案例中，条纪录很短，所以看到总page很少，实际情况，单条纪录更大，也就是上面的单个页面纪录数为c更小，所以通常选择度更高的时候，才会选择全表扫描。

2. ref成本的计算与分析 2.1 ref返回的记录数

ref优化的时候，计算返回的记录数从代码上来看要复杂很多，但是思想很简单。

思路：在range优化阶段，任何等值都会当作范围条件（参考1，参考2）。

对于kp1 = const and kp2 = const这类ref，mysql将直接使用range优化时返回的结果，这个结果是通过存储引擎接口records_in_range返回。

还有一类较为特殊的ref，kp1 = const and kp2 > const，对于此类ref，range优化的时候，会使用两个索引列，但是ref只能用一个索引列。这时，ref首先根据索引统计信息(show index from users中cardinality的值)预估。因为这里有range优化的值，还会做一次修正，因为range使用了更多的索引字段。修正逻辑为：如果发现索引统计信息太过保守(例如数据分布不均匀时，遇到一个热点)，这时会用range优化的值修正。

所以，返回的纪录数，使用如下代码获取：

records= keyinfo->rec_per_key[max_key_part-1] if(records < (double)table->quick_rows[key]...) records= (double)table->quick_rows[key]; 2.2 cpu cost cpu cost := records/(double) time_for_compare; 2.3 io cost

ref在做io成本评估的时候，基本同range相同，ref命中多少纪录则需要多少个io cost。但是跟range优化打不同的是，这里做了一个修正(range优化并没有做)，也是io cost最坏不会超过全表扫描io消耗的3倍(或者总记录数除以10)，有下面的代码：

s->worst_seeks= min((double) s->found_records / 10, (double) s->read_time*3); io cost := record_count*min(tmp,s->worst_seeks);

这里record_count是前一次关联后的记录数。tmp是当前ref命中的记录数。这个修正的逻辑是很好理解的：即使加上索引扫描其io cost仍然是有限度的。因为range的评估并没有加上这个修正，所以就导致了一些奇怪的事情发生了，后面我们再详细分析这一点。

2.4 全表扫描的成本

简单版本(不考虑多表关联)：

scan_time() + s->records/time_for_compare

scan_time()为存储引擎返回的全表扫描io次数；s->records为存储引擎维护的单表总纪录数。

复杂版本(有多表关联)：

假设前面关联后的纪录数为record_count，当前表的where条件将过滤后剩余3/4的纪录（不满足where条件的为1/4），并将这个值记为rnd_records。

(s->records - rnd_records)/time_for_compare + record_count * (rnd_records/time_for_compare)

这里假设将过滤1/4数据，实际代码中还将做一次修正，如果有range计算，假设其命中q条纪录，那么就认为将过滤s->records-q条纪录。

2.5 关于ref执行计划的分析

上面的分析，可以看到，ref成本有一部分是取min函数的，为了分析ref和全表扫描的临界条件，为了简化做下面的假设：

(1) scan_time()*3 < s->records / 10 (2) scan_time()*3 < r

第一个条件表示约30条纪录一个page；第二个条件是ref命中的记录数为总页面的3倍。

那么放弃ref全表扫描的条件是：

scan_time()*3 + r/5 > scan_time() + r/5 即： scan_time()*2 > (r-r)/5 scan_time() > (r-r)/10 具体的：

(1) 假设总记录数为r；ref需要返回的纪录数为r

(2) 假设该表的总页面数(io cost)为p；单个页面纪录数为c

那么range的代价超过全表扫描代价，则有：

[3*p + frac{r}{5} > p + frac{r}{5} ]

[frac{r}{r} > 1 - frac{10*p}{r}]

[frac{r}{r} > 1 - frac{10}{c}]

在我的测试案例中，p=6.4，r=900 ，有

[ frac{r}{r} > 0.929 ]

对于具体的案例，由于取整的问题，会和上面有小小的偏差：

3*((int)6.39) + r/5 > 6.39453125 + 900/5 r > 841.97 2.6 验证

这里再通过gdb修改r的值来验证，因为ref命中纪录的预估是取range的计算值，所以：

gdb) set s->table->quick_rows[1]=841 (gdb) c root@test 04:37:16>explain select * from users where reg_date = '2012-09-21 12:00:00'; +----+-------------+-------+------+---------------+-------------+---------+-------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | extra | +----+-------------+-------+------+---------------+-------------+---------+-------+------+-------------+ | 1 | simple | users | ref | ind_regdate | ind_regdate | 9 | const | 841 | using where | +----+-------------+-------+------+---------------+-------------+---------+-------+------+-------------+ 1 row in set (47.61 sec) (gdb) set s->table->quick_rows[1]=842 (gdb) c root@test 04:38:46>explain select * from users where reg_date = '2012-09-21 12:00:00'; +----+-------------+-------+------+---------------+------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | extra | +----+-------------+-------+------+---------------+------+---------+------+------+-------------+ | 1 | simple | users | all | ind_regdate | null | null | null | 900 | using where | +----+-------------+-------+------+---------------+------+---------+------+------+-------------+

另一个结论是，如果当条记录很小，单个页面的记录数很多的话，只有选择度(selectivity)非常高的时候，mysql才会放弃ref，走全表扫描，这也是，vadim在2006年吐槽mysql的一点。

3. 上面计算的局限性

上面的推倒尝试介绍一些通用的情况，但是实际上优化器中计算ref/range的成本时，会有一些不同：

(1) 无论时innodb还是myisam的scan_time，range返回的记录数都不是精确值，而且对于innodb，总记录数也不是精确值，所以上面只是一个high level的预估

(2) 上面案例中，条纪录很短，所以看到总page很少，实际情况，单条纪录更大，也就是上面的单个页面纪录数为c更小，所以通常选择度更高的时候，才会选择全表扫描。

(3) 上面的计算，都不是覆盖扫描的情况，覆盖扫描的时候，成本计算与上面略有不同

(4) 上面都是使用gdb修改某些值的方式来验证。如果想通过创建一个表，够造某个索引的区分度/选制度，因为scan_time和返回的记录数都是预估的，这样的方式是不行的

4. 案例中使用的数据和表 create table `users` ( `id` int(11) not null, `nick` varchar(32) default null, `reg_date` datetime default null, key `ind_nick` (`nick`), key `ind_regdate` (`reg_date`), key `ind_id` (`id`) ) engine=myisam for id in `seq 1 886`; do mysql -uroot test -e "insert into users values($id,char(round(ord('a') + rand()*(ord('z')-ord('a')))), '2012-09-21 12:00:00')" ;done for id in `seq 887 900`; do mysql -uroot test -e "insert into users values($id,char(round(ord('a') + rand()*(ord('z')-ord('a')))), '2012-09-20 12:00:00')" ;done
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！