MySQL执行计划选择--成本模型v1.0

Size: px

Start display at page:

Download "MySQL执行计划选择--成本模型v1.0"

遍蟹简
6 years ago
Views:

1 MySQL 优化器的成本模型年 7 月

2 目录成本模型与关系型数据库简单 JOIN 的执行成本计算 MySQL 常见 access method 的成本计算 MySQL 成本计算中的统计信息成本与执行计划选择其他的细节

3 成本模型与关系型数据库图片来源 : Query Optimization Yannis E. Ioannidis 1996

4 示例 SELECT * FROM a,b WHERE a.num = 6 and a.bid = b.id and b.age > 17; Table: a CREATE TABLE `a` ( `id` int(11) NOT NULL DEFAULT '0', `num` int(11) DEFAULT NULL, `bid` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NUM` (`num`)) ENGINE=InnoDB DEFAULT CHARSET=latin1 Table: b CREATE TABLE `b` ( `id` int(11) NOT NULL DEFAULT '0', `age` int(11) DEFAULT NULL, `nick` char(10) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_AGE` (`age`)) ENGINE=InnoDB DEFAULT CHARSET=latin1

5 可能的执行计划 A B B A B A ref IND_NUM eq_ref PK range IND_AGE ALL range IND_AGE ref IND_NUM SELECT * FROM A,B WHERE A.num = 6 and A.bid = B.id and B.age > 17; 一些事实与说明 : 1. MySQL 只支持 Nested-Loop Join 2. 图示中, 左边表总是 Join 中的 outer table, 右边总是 inner table ( 也有说法, 左边是驱动表 driving table, 右边是被驱动表 )

6 简要的执行过程 for each tuple x in A with index IND_NUM for each tuple y in B with index PK (b.id = a.bid) A B if B.age > 17 return <x,y> endif ref IND_NUM eq_ref PK SELECT * FROM A,B WHERE A.num = 6 and A.bid = B.id and B.age > 17; 说明 :tuple row record 简单理解是指表中的一条记录

7 理解 NLJ( 一 ) for each tuple x in A with index IND_NUM 1. 访问索引 IND_NUM 获取 A.num=6 的 rowid 2. 根据 rowid, 读取 A 表命中的记录 for each tuple y in B with index PK (b.id = a.bid) 1. 读取主键索引中 b.id = a.bid 的页, 取出对应 tuple if B.age > 17 return <x,y> endif 1. 判断取出的 tuple 中 B.age > 17 SELECT * FROM A,B WHERE A.num = 6 and A.bid = B.id and B.age > 17;

8 理解 NLJ( 二 ) for each tuple x in A with index IND_NUM 1. read index page (1) 2. Comparing*keys/records (131) 3. read data page (131) for each tuple y in B with index PK (b.id = a.bid) if B.age > 17 return <x,y> endif 1. 读取主键索引页, 也就是读取了数据页 (read 1 data/index page) 1. evaluating query conditions SELECT * FROM A,B WHERE A.num = 6 and A.bid = B.id and B.age > 17;

9 目录成本模型与关系型数据库简单 JOIN 的执行成本计算 MySQL 常见 access method 的成本计算 MySQL 成本计算中的统计信息成本与执行计划选择其他的细节

10 成本分析 COST = COST of (IO + CPU) PAGE FETCHES RSI CALLS COST = PAGE FETCH + W * (RSI CALLS) 公式来源 :Access Path Selection in a Relational Database Management System P. Griffiths Selinger... IBM 1979

11 MySQL 成本分析 COST = COST of (IO + CPU) PAGE FETCHES RSI CALLS COST = PAGE FETCH + W * (RSI CALLS) Data Page Index Page compare key row evaluating MySQL 成本细节

12 Nested Loop JOIN 的成本计算 Cost(NLJ) = C(A) + P_ROW(A) * C(B) 涉及的名词 A B C(A) P_ROW(A) C(B) 解释 outer table inner table cost of outer table prefix row cost of every time evaluating inner table

引入概念 : 权重 W for each tuple x in A with index IND_NUM 1. read index page (1) 2. Comparing*keys/records (131) 3. read data page (131) for each tuple y in B with index PK (b.id = a.

13 引入概念 : 权重 W for each tuple x in A with index IND_NUM 1. read index page (1) 2. Comparing*keys/records (131) 3. read data page (131) for each tuple y in B with index PK (b.id = a.bid) if B.age > 17 return <x,y> endif 1. 读取主键索引页, 也就是读取了数据页 (read 1 data/index page) 1. evaluating query conditions SELECT * FROM A,B WHERE A.num = 6 and A.bid = B.id and B.age > 17; (MySQL 5.7)

14 成本计算 for each tuple x in A with index IND_NUM 1. read index page (1) 2. Comparing*keys/records (131) 3. read data page (131) for each tuple y in B with index PK (b.id = a.bid) if B.age > 17 return <x,y> endif 1. 读取主键索引页, 也就是读取了数据页 (read 1 data/index page) 1. evaluating query conditions SELECT * FROM A,B WHERE A.num = 6 and A.bid = B.id and B.age > 17; Cost(NLJ) = C(A) + P_ROW(A) * C(B) Cost(NLJ) = * *(1+1*0.2)

15 成本模型与关系型数据库简单 JOIN 的执行与成本成本计算 MySQL 常见 access method 的成本计算 MySQL 成本计算中的统计信息成本与执行计划选择其他的细节

16 回到前面的例子 A B B A B A ref IND_NUM eq_ref PK range IND_AGE ALL range IND_AGE ref IND_NUM SELECT * FROM A,B WHERE A.num = 6 and A.bid = B.id and B.age > 17; 问题 1: 解释第二个执行计划的执行过程和成本计算? 问题 2: 一共有多少种执行计划? 问题 3: 能否列举其中的一个?

17 MySQL 主要的 access method table scan where TRUE index scan order by ind_a range scan ind_a = 5 and ind_b > 10 ref where ind_a = 97 / A.ind_a = B.col

18 table scan 的成本计算 SELECT * FROM a WHERE a.bid < 6 Table: a CREATE TABLE `a` ( `id` int(11) NOT NULL DEFAULT '0', `num` int(11) DEFAULT NULL, `bid` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NUM` (`num`)) ENGINE=InnoDB DEFAULT CHARSET=latin1 全表扫描, 逐行读取所有记录评估 WHERE 条件是否满足 Cost = Page(Table A) * ROW(Table A) s->table->file->scan_time() s->table->file->stats.records;

19 index scan 的成本计算 SELECT * FROM a ORDER BY num Table: a CREATE TABLE `a` ( `id` int(11) NOT NULL DEFAULT '0', `num` int(11) DEFAULT NULL, `bid` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NUM` (`num`)) ENGINE=InnoDB DEFAULT CHARSET=latin1 全索引扫描, 并返回对应的 rowid 根据 rowid 读取每一个记录 Cost = Page(INDEX IND_NUM) + ROW(Table A) handler::index_only_read_time s->table->file->stats.records; stats.block_size key_length/ref_length records 问题 : 如何计算索引页数

20 上一页问题的 MySQL 实现 Cost = Page(INDEX IND_NUM) + ROW(Table A) handler::index_only_read_time s->table->file->stats.records; stats.block_size key_length/ref_length records 问题 : 如何计算索引页数

21 index scan 的成本计算 ( 覆盖扫描 ) SELECT num FROM a ORDER BY num Table: a CREATE TABLE `a` ( `id` int(11) NOT NULL DEFAULT '0', `num` int(11) DEFAULT NULL, `bid` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NUM` (`num`)) ENGINE=InnoDB DEFAULT CHARSET=latin1 全索引扫描 Cost = Page(INDEX IND_NUM) handler::index_only_read_time

22 range scan 的成本计算 SELECT * FROM a WHERE num > 6 and num <10 Table: a CREATE TABLE `a` ( `id` int(11) NOT NULL DEFAULT '0', `num` int(11) DEFAULT NULL, `bid` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NUM` (`num`)) ENGINE=InnoDB DEFAULT CHARSET=latin1 读取索引范围, 并返回对应的 rowid 根据 rowid 读取每一个记录 Cost = E_ROW(A) + E_ROW(A) * 0.1 records_in_range(keynr, * min_key, * max_key)

23 ref 的成本计算 (1) SELECT * FROM a WHERE num = 6 ( 注 : 有索引有取值 ) Table: a CREATE TABLE `a` ( `id` int(11) NOT NULL DEFAULT '0', `num` int(11) DEFAULT NULL, `bid` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NUM` (`num`)) ENGINE=InnoDB DEFAULT CHARSET=latin1 读取索引范围, 并返回对应的 rowid 根据 rowid 读取每一个记录 Cost = E_ROW(A) + E_ROW(A) * 0.1 records_in_range(keynr, * min_key, * max_key)

24 ref 的成本计算 (2) SELECT * FROM b STRAIGHT_JOIN a WHERE a.num = b.age and b.age > 10 ( 注 : 有索引无取值 ) Table: a CREATE TABLE `a` ( `id` int(11) NOT NULL DEFAULT '0', `num` int(11) DEFAULT NULL, `bid` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NUM` (`num`)) ENGINE=InnoDB DEFAULT CHARSET=latin1 读取索引范围, 并返回对应的 rowid 根据 rowid 读取每一个记录 Cost(A) = E_ROW(A) + E_ROW(A) * 0.1 (records= keyinfo->rec_per_key[actual_key_parts(keyinfo)-1])

25 部分 MySQL 统计信息 s->table->file->scan_time() s->table->file->stats.records stats.block_size key_length/ref_length records_in_range keyinfo->rec_per_key 全表扫描页数表总记录数块大小索引信息范围中的记录数单个索引值引用的 rowid 数量更新策略 : ANALYZE TABLE SHOW TABLE STATUS 第一次访问表访问表 : INFORMATION_SCHEMA.TABLES INFORMATION_SCHEMA.STATISTICS 在变更记录数超过 1/16 的时候更新策略的控制 : innodb_stats_on_metadata

26 小节至此, 我们知道了 : 各种单表各种 access method 的成本计算方法两个表做 NJL 的成本计算方法那么, 进一步, 我们可以计算 : 多表 NLJ 的成本计算 : 这个是一个递归计算我们可以比较不同的执行计划的成本差异

27 目录成本模型与关系型数据库简单 JOIN 的执行成本计算 MySQL 常见 access method 的成本计算 MySQL 成本计算中的统计信息成本与执行计划选择其他的细节

28 三个表 JOIN 的场景 N 个表 JOIN 的场景

29 约定 : 简化的写法 A B 简化的写法 A (ref IND_NUM) B (eq_ref PK) ref IND_NUM eq_ref PK

30 示例 SELECT * FROM A,B,C WHERE A.num = 6 and B.id = 100 and C.age > 17 and A.cid = C.id and B.aid = A.id

31 可能的执行计划 C (range IND_AGE) A (table scan) A B (ref IND_NUM) (eq_ref PK) B (eq_ref PK) C (range IND_AGE) 一共有多少个这样的执行计划?

32 N 个表的执行计划如何找到这个问题的最优解? 1. 穷举复杂度 :O(N!) X (all) 2. 贪婪搜索复杂度 3. 启发式 (heuristics) 的搜索 C (range) 注 : 简化了如下场景只考虑 NLJ, 不考虑 sort-merge 和 hash join 没有加入关于 interesting order 的情况 A (ref) B (eq_ref)

33 N 个表的执行计划 - 贪婪搜索如何找到这个问题的最优解? 1. 穷举复杂度 :O(N!) X (all) 2. 贪婪搜索复杂度 3. 启发式 (heuristics) 的裁枝 C (range) 注 : 简化了如下场景只考虑 NLJ, 不考虑 sort-merge 和 hash join 没有加入关于 interesting order 的情况 A (ref) B (eq_ref)

34 N 个表的执行计划 - 贪婪搜索如何贪婪 : 把局部最优解当做全局最优解这里假设局部最优解的计算深度是 depth, 那么复杂度为 : X (all) N N &'()* O( depth ) C (range) 问题 : 如果 depth=1, 蜕化后的情况是怎样的? A (ref) B (eq_ref)

35 N 个表的执行计划 - 贪婪搜索如何找到这个问题的最优解? 1. 穷举复杂度 :O(N!) X (all) 2. 贪婪搜索复杂度 3. 启发式 (heuristics) 的裁枝 skip certain plans based on estimates of the number of rows accessed for each table 注 : 简化了如下场景只考虑 NLJ, 不考虑 sort-merge 和 hash join 没有加入关于 interesting order 的情况 A (ref) B (eq_ref) C (range)

36 理论很复杂, 实际很简单一般的,N < depth = 64, 且 prune_level = 1 基本上都是穷举 X (all) 贪婪搜索过程中, 要选择下一个被 JOIN 的表的时候, 只看这个表返回的行数 C (range) A (ref) B (eq_ref)

37 看起来简单, 但细节非常多这里只考虑的 NLJ, 忽略 sort-merge 和 hash join 没有考虑 NLJ 的一些优化 Block Nested Loops Join (MySQL) 为了简化, 忽略了 interesting order (order by/group by 等 ) 没有讨论为什么总是 left-deep tree 没有考虑 nested query(subquery) 的成本计算或者 semi-join 转换为了简化, 没有考虑多个谓词, 对 prefix row 的影响 (filter) 没有考虑 condition_fanout_filter (MySQL5.7) 没有讨论 GROUP BY/ORDER BY/DISTINCT 等优化

38 参考和扩展阅读 Paper Query Optimization Yannis E. Ioannidis 文章链接 Access Path Selection in a Relational Database Management System P. Griffiths Selinger... IBM 一些 slide: MySQL queryoptimizer internalsand upcomingfeatures in v. 5.2 Implementing Joins Implementation of Database Systems MySQL Cost Model 其他 MySQL Internals Manual MySQL source code MySQL 查询优化浅析何登成

39 示例 SELECT * FROM a,b WHERE a.num = 6 and a.bid = b.id and b.age > 17; Table: a CREATE TABLE `a` ( `id` int(11) NOT NULL DEFAULT '0', `num` int(11) DEFAULT NULL, `bid` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NUM` (`num`)) ENGINE=InnoDB DEFAULT CHARSET=latin1 Table: b CREATE TABLE `b` ( `id` int(11) NOT NULL DEFAULT '0', `age` int(11) DEFAULT NULL, `nick` char(10) DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_AGE` (`age`)) ENGINE=InnoDB DEFAULT CHARSET=latin1

40 数据 for i in `seq `;do mysql -v -uroot test -e insert into a values (rand()*10000,rand()*10000,rand()*10000) ; done select substring(md5(concat("adfasdfasfasdf",rand()* )),1,rand()*10); for i in `seq 0 500`;do mysql -v -uroot test -e "insert into b values (rand()*100000,rand()*100000,substring(md5(concat('adfasdfasfasdf',rand()* )),1,rand()*10))"; done

41 附录 2:Blocked Nested-Loop Join for each tuple x in A with index IND_NUM store used columns from A in join buffer for each tuple y in B with index PK (b.id = a.bid) A B for each items z in join buffer if B.age > 17 return <z,y> endif inner table 被扫描的次数 : (S * C)/join_buffer_size + 1 S Size of (x interesting column) C Row return from A ref IND_NUM eq_ref PK SELECT * FROM A,B WHERE A.num = 6 and A.bid = B.id and B.age > 17; 说明 :tuple row record 简单理解是指表中的一条记录

季刊9web.indd

季刊9web.indd 在全国现场会上成功展示全国烟叶收购暨现代烟草农业建设现场会 7 月 6 日至 8 日在昆明召开在国家局的领导下, 由我司技术开发的烟站 ( 单元 ) 烟叶管理信息系统在现场会上成功展示, 并得到参会领导及代表们的关注与认可该系统