MySQL 优化器的成本模型 周振兴 @2016 年 7 月
目录 成本模型与关系型数据库简单 JOIN 的执行成本计算 MySQL 常见 access method 的成本计算 MySQL 成本计算中的统计信息成本与执行计划选择其他的细节
成本模型与关系型数据库 图片来源 : Query Optimization Yannis E. Ioannidis 1996
示例 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
可能的执行计划 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, 右边是被驱动表 )
简要的执行过程 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 简单理解是指表中的一条记录
理解 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;
理解 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;
目录 成本模型与关系型数据库简单 JOIN 的执行成本计算 MySQL 常见 access method 的成本计算 MySQL 成本计算中的统计信息成本与执行计划选择其他的细节
成本分析 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
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 成本细节
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.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)
成本计算 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 + 131 + 131*0.1 + 131*(1+1*0.2)
成本模型与关系型数据库简单 JOIN 的执行与成本成本计算 MySQL 常见 access method 的成本计算 MySQL 成本计算中的统计信息成本与执行计划选择其他的细节
回到前面的例子 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: 能否列举其中的一个?
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
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) + 0.2 * ROW(Table A) s->table->file->scan_time() s->table->file->stats.records;
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 问题 : 如何计算索引页数
上一页问题的 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 问题 : 如何计算索引页数
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
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)
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)
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])
部分 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
小节 至此, 我们知道了 : 各种单表各种 access method 的成本计算方法 两个表做 NJL 的成本计算方法 那么, 进一步, 我们可以计算 : 多表 NLJ 的成本计算 : 这个是一个递归计算 我们可以比较不同的执行计划的成本差异
目录 成本模型与关系型数据库简单 JOIN 的执行成本计算 MySQL 常见 access method 的成本计算 MySQL 成本计算中的统计信息成本与执行计划选择其他的细节
三个表 JOIN 的场景 N 个表 JOIN 的场景
约定 : 简化的写法 A B 简化的写法 A (ref IND_NUM) B (eq_ref PK) ref IND_NUM eq_ref PK
示例 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
可能的执行计划 C (range IND_AGE) A (table scan) A B (ref IND_NUM) (eq_ref PK) B (eq_ref PK) C (range IND_AGE) 一共有多少个这样的执行计划?
N 个表的执行计划 如何找到这个问题的最优解? 1. 穷举复杂度 :O(N!) X (all) 2. 贪婪搜索复杂度 3. 启发式 (heuristics) 的搜索 C (range) 注 : 简化了如下场景 只考虑 NLJ, 不考虑 sort-merge 和 hash join 没有加入关于 interesting order 的情况 A (ref) B (eq_ref)
N 个表的执行计划 - 贪婪搜索 如何找到这个问题的最优解? 1. 穷举复杂度 :O(N!) X (all) 2. 贪婪搜索复杂度 3. 启发式 (heuristics) 的 裁枝 C (range) 注 : 简化了如下场景 只考虑 NLJ, 不考虑 sort-merge 和 hash join 没有加入关于 interesting order 的情况 A (ref) B (eq_ref)
N 个表的执行计划 - 贪婪搜索 如何贪婪 : 把局部最优解当做全局最优解 这里假设 局部最优解 的计算深度是 depth, 那么复杂度为 : X (all) N N &'()* O( depth ) C (range) 问题 : 如果 depth=1, 蜕化后的情况是怎样的? A (ref) B (eq_ref)
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)
理论很复杂, 实际很简单 一般的,N < depth = 64, 且 prune_level = 1 基本上都是穷举 X (all) 贪婪搜索过程中, 要选择下一个被 JOIN 的表的时候, 只看这个表返回的行数 C (range) A (ref) B (eq_ref)
看起来简单, 但细节非常多 这里只考虑的 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 等优化
参考和扩展阅读 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 查询优化浅析何登成
示例 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
数据 for i in `seq 0 5000`;do mysql -v -uroot test -e insert into a values (rand()*10000,rand()*10000,rand()*10000) ; done select substring(md5(concat("adfasdfasfasdf",rand()*1000000)),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()*100 0000)),1,rand()*10))"; done
附录 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 简单理解是指表中的一条记录