澳门新浦京娱乐场网站-www.146.net-新浦京娱乐场官网
做最好的网站

澳门新浦京娱乐场网站:Range和Ref优化的成本评估

http://www.cnblogs.com/LBSer/p/3333881.html

MySQL统计信息以及预估方式初探,mysql统计信息初探

澳门新浦京娱乐场网站:Range和Ref优化的成本评估,MySQL统计信息以及预估方式初探。 

数据库中的统计信息在不同(精确)程度上描述了表中数据的分布情况,执行计划通过统计信息获取符合查询条件的数据大小(行数),来指导执行计划的生成。
在以Oracle和SQLServer为代表的商业数据库,和以开源的PostgreSQL为代表的数据库中,直方图是统计信息的一个重要组成部分。
在生成执行计划的时候,通过统计信息以及统计信息的直方图来预估符合条件的数据行数,从而影响执行计划的生成。
统计信息对执行计划的影响,具体体现在:索引的查找与扫描,多表连接时表之间的驱动顺序,表之间的JOIN方式,以及对sql查询语句的资源分配等等。
但是在MySQL数据库中,执行计划的方式相对简单,表之间的JOIN只有LOOPJOIN一种方式,且没有并行执行计划等,也就说通过预估结果集的行数对执行计划的影响有限。
但是对于某些情况,依旧需要预估的方式来指导执行计划的生成,
比如常见的多表连接时驱动顺序,多数情况下是小表驱动大表(不完全一定)的方式来实现查询的,因此MySQL中一样需要预估来指导执行计划的生成。

不过MySQL中的统计信息只有一个cardinality信息来预估索引的选择性(show index from table),并不包含直方图的信息,也就是无法通过直方图来预估查询数据的大小,mysql是通过其他方式来实现预估的。
对于有直方图的数据来说,直方图为预估提供了重要的依据,对于没有直方图的MySQL,执行计划是如何预估的?预估的准确性有如何?
笔者在研究这个问题的时候,一开始也遇到不少疑惑的地方,还是看了博客园大神的问题才得以释惑,后面会给出链接。

 

首先通过例子,通过一个非常简单的查询来观察一个有意思的现象。

新建测试表,测试表如下:

create table test_statistics
(
    id int auto_increment primary key,
    col2 varchar(200),
    col3 varchar(200),
    create_date datetime,
    index idx_create_date(create_date)
)ENGINE=InnoDB;

存储过程通过循环插入数据,调用存储过程生成100W行数据(100W行的数据,在实际应用中已经是一个非常小的数据量了),create_date字段上生成一个范围之内的随机时间。

CREATE DEFINER=`root`@`%` PROCEDURE `p_insert_test_data`(
    IN `loop_count` INT
)
BEGIN
    declare i int;
    while (loop_count>0) 
    do    
        insert into test_statistics(col2,col3,create_date) values (uuid(),uuid(), DATE_ADD(sysdate(), INTERVAL  -rand()*2400  hour));
        set loop_count = loop_count -1;
    end while;
END

写入测试数据完成之后,进行如下两个查询做测试。

简单地使用select count(1)的来做测试
首先看第一个查询:查询的时间范围是: where create_date>'2017-11-01 12:00:00' and create_date<'2017-11-01 16:00:00'
可以发现:explain预估的行数,与实际行数完全一致。

澳门新浦京娱乐场网站 1

继续第二个查询,扩大查询的时间范围,查询的时间范围是:where create_date>'2017-11-01 12:00:00' and create_date<'2017-11-03 16:00:00'
可以发现,此时的explain执行计划的预估,与实际行数出现了严重的偏差

澳门新浦京娱乐场网站 2

为什么第一个查询做到了精确的预估,而第二个查询的预估出现严重的偏差?

这一点要从预估的计算方式入手来说。

首先,第一个查询和第二个查询,唯一的不同是,第二个查询的时间范围放宽了,为什么时间放宽之后,执行计划的预估的准确性就大大下降?
其他数据库的预估是通过直方图获取的,统计信息中包含的直方图中的准确性,就决定了预估的准确性。
既然是“预估”,就一定是存在误差,只不过是误差大与小的问题,误差的大下与预估的方式有关。
任何预估的实现,都是以一种在不同程度上“以偏概全”的方式进行的,比如SQL Server是以对相关数据page的通过某种百分比来取样,然后存储在直方图中做预估依据的。
当然,这种“以偏概全”的预估方式,是在性能与精确度之间权衡折中的结果,在考虑收集统计信息对性能和资源影响的前提下,预估策略各种方式或者代价尽可能减少对预估产生误差的因素。
而MySQL是在查询的时候,直接是以查询条件范围内的数据页做统计之后预估的,但是取样的数据页面有一定的限制,不会无限制取样做统计预估。
如果符合条件的数据页超出了预定的范围,则会取部分页进行预估,而不是全部页(为什么不是全部样做统计预估,原因就不用说了吧)。

 

比如下图中,不管是聚集索引还是二级索引(非聚集索引),理论上说都是一颗平衡树,暂不探究其细节。
假如符合条件的数据是一个范围,位于两个矩形框之间。矩形框分别是范围的左右节点,中间可以想象成多个叶子节点
参考zhanlijun大神的文章,
上述参考链接中得知,MySQL在5.5之后的预估原理如下:
其预估扫描的数据页分别是前后两个数据页,以及从左边开始连续8个数据页,得到平均每个page的行数,根据总的page个数预估出这个范围的数据行数。
具体说,也就是取左右两个叶子节点,以及从左叶子节点开始连续8个页的数据做统计,中间可能有多个数据页,但也会被忽略,这就是上面提到的“以偏概全”的方式。
这里面就存在一个最明显的问题,也就是符合条件的数据页面与预估时候采集的页面的大小关系。
如果符合条件的数据页的分布少于10个,当然在预估的时候,会全部扫描这些page,当然预估是完全精确的,这也是第一个查询执行计划预估的实际行数完全不一致的原因。
如果符合条件的数据页的分布大于10个,当然在预估的时候,会部分扫描这些page,预估的误差情况就此产生,这也是第二个查询执行计划预估的实际行数差异较大的原因。

澳门新浦京娱乐场网站 3

 当然MySQL的每个版本可能都有所改进或者差异,笔者并没有从源码中找到具体的算法,当前测试的是5.7.20版本。

 

但目前仍不清楚,
1,在create_date字段上,时间是按照DATE_ADD(sysdate(), INTERVAL -rand()*2400 hour)生成的,从整体分布看,基本按照时间均匀分布的.
  理论上根据这种方式推到,得到的预估结果偏差应该不会很大,但尚不清楚为什么预估与实际存在如此大的差异。
2,尝试找到预估值从精确到产生差异的临界点,通过查询实际行数,根据key_len的值以及B树索引的存储原理(二级索引叶子节点存储的二级索引的key值 聚集索引的key值).
  理论上计算出来当前查询一个大概的取样的page个数,发现这个值预报理论上的10个page差异较大,可能是推到方式有问题,或者是MySQL预估本身有一些不知道的细节问题。
3,没有详细翻MySQL的源码,尚未找到具体的实现细节。

 

对于有直方图的数据库来说,直方图的信息也不是没有代价,或者是万能的,直方图也有直方图的局限性,这里暂不表述。
对于尚没有直方图的MySQL数据库来说,其预估原理是每次查询的时候进行对相关的数据页面进行采样预估的,而不是从直方图中获取到预估信息的,这是一个很消耗性能的操作。
详情参考:
这可能会导致MySQL不适合做较大数据量或者较为复杂的JOIN操作,当然这也取决于具体的业务设计方案以及对数据的依赖程度,或者主观上的查询提示操作。
说这句话是冒着被MySQL的大神以及粉丝们怒喷的风险的。
关于MySQL的预估的知识点,搜索到的文章并不是很多,也拘泥于个人的认识有限,也希望对这方面有关注的大神多多指点。
据说MySQL在8.0之后的版本中会加入直方图信息,以及其他JOIN方式(除了LOOP JOIN),这可能对性能上有比较大的帮助。

 

参考链接:

 

数据库中的统计信息在不同(精确)程度上描述了表中数据的分布情况,执行计划通过...

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

原文链接:

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

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

引子:

0. 成本计算的总原则

MySQL的一个执行计划,有两部分成本,CPU成本(CPU COST)和IO成本(IO COST)。

总成本 = CPU COST IO COST

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

  使用MySQL建立了一张表country,总共有才3121行记录。

1. range成本的计算与分析

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

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

  但是使用explain select count(*) from country;的时候,发现行数rows达到6897,让我大吃一惊。

1.1 range返回的记录数

澳门新浦京娱乐场网站,MySQL首先计算range需要返回都少纪录,通过函数check_quick_select返回对某个索引做range查询大约命中多少条纪录。

found_records= check_quick_select(param, idx, *key, update_tbl_stats);

mysql> explain select count(*) from country;

 ---- ------------- --------- ------ --------------- ------ --------- ------ ------ ------- 

| id | select_type | table   | type | possible_keys | key  | key_len | ref  | rows | Extra |

 ---- ------------- --------- ------ --------------- ------ --------- ------ ------ ------- 

|  1 | SIMPLE      | country | ALL  | NULL          | NULL | NULL    | NULL | 6897 | NULL  |

 ---- ------------- --------- ------ --------------- ------ --------- ------ ------ ------- 

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的个数。

问题:为什么explain的结果和真实的结果运行不一致,并且产生这么大的误差?

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

  针对这个问题,上网查了些资料,特此发博文总结下,当然自己也是刚刚使用mysql,有很多不了解的地方,希望多多指正。

1.5 关于range执行计划的分析

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

 

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

(2) 假设该表的总页面数(IO COST)为P;单个页面纪录数为c

 澳门新浦京娱乐场网站 4

在我的测试案例中,P=4,R=1016 ,有

 澳门新浦京娱乐场网站 5

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

一、explain是什么?

1.6 验证

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

澳门新浦京娱乐场网站 6

澳门新浦京娱乐场网站 7

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

  通过explain可以查看MySQL的执行计划,从而知道MySQL是如何处理我们的SQL语句。具体来说通过explain我们能得到一系列的关键信息,比如哪些索引被实际使用,查询了多少行等等。

1.7 一些限制

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

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

  explain使用Rows来告知我们数据库即将要阅读的行数,但是实际将要阅读的行数和explain所记载的将要阅读的行数可能会有差异,这是因为explain并没有真的去执行sql语句从而得出行数,而是进行了某种预估。

2. ref成本的计算与分析

二、explain怎么预估行数

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];

  找了半天得知真相的我眼泪掉下来:http://lists.mysql.com/commits/115810

2.2 CPU COST

CPU COST := records/(double) TIME_FOR_COMPARE;

1)mysql-5.5之前

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的评估并没有加上这个修正,所以就导致了一些奇怪的事情发生了,后面我们再详细分析这一点。

  首先找到查询第一个记录所在的page(记为PLeft),统计PLeft里的记录数(记为Records_PLeft),之后找到最后一个记录所在的page(记为PRight),统计PRight的记录数(Records_PRight),之后将Records_PLeftRecords_PRight取平均,最后乘以总共的page数目(记为Page_Num)。公式如下:

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条纪录。

Rows = ((Records_PLeft   Records_PRight)/2)*Page_Num

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的代价超过全表扫描代价,则有:

澳门新浦京娱乐场网站 8

在我的测试案例中,P=6.4,R=900 ,有

 澳门新浦京娱乐场网站 9

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

3*((int)6.39) r/5 > 6.39453125 900/5
r > 841.97

  统计上讲这个预估方法是很有偏的。比如总共4个page:page1(999 records), page2(1 record), page3(1 record), page4(1 record),这样预估出来的Rows=((999 1)/2)*4 = 2000,然而实际上才总共才有1002个记录。

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的一点。

2)mysql-5.5之后

3. 上面计算的局限性

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

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

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

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

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

(5) (update) range的cost计算,最终的公式是:#rows (#rows/5)*2 1 解释如下,

** #rows 为IO成本,因为读取的记录都需要回表查找完整记录,而这些都是离散IO,所以多少条记录,多少个IO

** (#rows/5)*2 是CPU成本,分两部分,第一部分是扫描索引时,确定在查找范围内;第二部分是找到记录后判断是否满足WHERE条件;(这部分成本,在range analysis的时候没有计算)

** 1是一个修正值,防止0成本出现

  上述预估偏差大的关键在于有偏,而有偏的关键在于采样的page数太少了,事实上只采样了边界2个,新算法的思路很简单,增加采样数目,比如采样10个page,这样可以在一定程度上降低偏差。

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

 

  具体来说,mysql除了边界2个外,还沿着左侧page往右连续查找8个page,如果总的page数目小于等于10个,那么预估的Rows和真实的Rows一致。

Rows = ((Records_PLeft    Records_P1   Records_P2   ...   Records_P8   Records_PRight)/10)*Page_Num

   上述方法只是在一定程度上缓解了有偏的问题,但是不准确还是存在的,事实上楼主的mysql版本是5.6版本,可见还是没有解决的很好

 三、思考

  为什么是从左往右连续选8个page,而不是在首尾之间随机选择8个page,既然要缓解采样有偏的问题,那么随机选应该更好。猜想可能有两个原因:1)随机选择每次explain得到的Rows不一样,不方便应用;2)随机选会造成I/O开销,尤其是数据量大的时候,毕竟explain是希望能快速得到预估结果。

  我觉得应该还有更好的算法,能实现explain效率与精度的tradeoff,希望大家能给出建议。

本文由澳门新浦京娱乐场网站发布于数据库,转载请注明出处:澳门新浦京娱乐场网站:Range和Ref优化的成本评估