基于成本的优化

标签： MySQL 是怎样运行的

什么是成本

我们之前老说MySQL执行一个查询可以有不同的执行方案，它会选择其中成本最低，或者说代价最低的那种方案去真正的执行查询。不过我们之前对成本的描述是非常模糊的，其实在MySQL中一条查询语句的执行成本是由下边这两个方面组成的：

• I/O成本

  我们的表经常使用的MyISAM、InnoDB存储引擎都是将数据和索引都存储到磁盘上的，当我们想查询表中的记录时，需要先把数据或者索引加载到内存中然后再操作。这个从磁盘到内存这个加载的过程损耗的时间称之为I/O成本。

• CPU成本

  读取以及检测记录是否满足对应的搜索条件、对结果集进行排序等这些操作损耗的时间称之为CPU成本。

对于InnoDB存储引擎来说，页是磁盘和内存之间交互的基本单位，设计MySQL的大叔规定读取一个页面花费的成本默认是1.0，读取以及检测一条记录是否符合搜索条件的成本默认是0.2。1.0、0.2这些数字称之为成本常数，这两个成本常数我们最常用到，其余的成本常数我们后边再说哈。

小贴士：
​
需要注意的是，不管读取记录时需不需要检测是否满足搜索条件，其成本都算是0.2。

单表查询的成本

准备工作

为了故事的顺利发展，我们还得把之前用到的single_table表搬来，怕大家忘了这个表长啥样，再给大家抄一遍：

CREATE TABLE single_table (
    id INT NOT NULL AUTO_INCREMENT,
    key1 VARCHAR(100),
    key2 INT,
    key3 VARCHAR(100),
    key_part1 VARCHAR(100),
    key_part2 VARCHAR(100),
    key_part3 VARCHAR(100),
    common_field VARCHAR(100),
    PRIMARY KEY (id),
    KEY idx_key1 (key1),
    UNIQUE KEY idx_key2 (key2),
    KEY idx_key3 (key3),
    KEY idx_key_part(key_part1, key_part2, key_part3)
) Engine=InnoDB CHARSET=utf8;

还是假设这个表里边儿有10000条记录，除id列外其余的列都插入随机值。下边正式开始我们的表演。

基于成本的优化步骤

在一条单表查询语句真正执行之前，MySQL的查询优化器会找出执行该语句所有可能使用的方案，对比之后找出成本最低的方案，这个成本最低的方案就是所谓的执行计划，之后才会调用存储引擎提供的接口真正的执行查询，这个过程总结一下就是这样：

1. 根据搜索条件，找出所有可能使用的索引

2. 计算全表扫描的代价

3. 计算使用不同索引执行查询的代价

4. 对比各种执行方案的代价，找出成本最低的那一个

下边我们就以一个实例来分析一下这些步骤，单表查询语句如下：

SELECT * FROM single_table WHERE 
    key1 IN ('a', 'b', 'c') AND 
    key2 > 10 AND key2 < 1000 AND 
    key3 > key2 AND 
    key_part1 LIKE '%hello%' AND
    common_field = '123';

乍看上去有点儿复杂哦，我们一步一步分析一下。

1. 根据搜索条件，找出所有可能使用的索引

我们前边说过，对于B+树索引来说，只要索引列和常数使用=、<=>、IN、NOT IN、IS NULL、IS NOT NULL、>、<、>=、<=、BETWEEN、!=（不等于也可以写成<>）或者LIKE操作符连接起来，就可以产生一个所谓的范围区间（LIKE匹配字符串前缀也行），也就是说这些搜索条件都可能使用到索引，设计MySQL的大叔把一个查询中可能使用到的索引称之为possible keys。

我们分析一下上边查询中涉及到的几个搜索条件：

• key1 IN ('a', 'b', 'c')，这个搜索条件可以使用二级索引idx_key1。

• key2 > 10 AND key2 < 1000，这个搜索条件可以使用二级索引idx_key2。

• key3 > key2，这个搜索条件的索引列由于没有和常数比较，所以并不能使用到索引。

• key_part1 LIKE '%hello%'，key_part1通过LIKE操作符和以通配符开头的字符串做比较，不可以适用索引。

• common_field = '123'，由于该列上压根儿没有索引，所以不会用到索引。

综上所述，上边的查询语句可能用到的索引，也就是possible keys只有idx_key1和idx_key2。

2. 计算全表扫描的代价

对于InnoDB存储引擎来说，全表扫描的意思就是把聚簇索引中的记录都依次和给定的搜索条件做一下比较，把符合搜索条件的记录加入到结果集，所以需要将聚簇索引对应的页面加载到内存中，然后再检测记录是否符合搜索条件。由于查询成本=I/O成本+CPU成本，所以计算全表扫描的代价需要两个信息：

• 聚簇索引占用的页面数

• 该表中的记录数

这两个信息从哪来呢？设计MySQL的大叔为每个表维护了一系列的统计信息，关于这些统计信息是如何收集起来的我们放在本章后边详细唠叨，现在看看怎么查看这些统计信息哈。设计MySQL的大叔给我们提供了SHOW TABLE STATUS语句来查看表的统计信息，如果要看指定的某个表的统计信息，在该语句后加对应的LIKE语句就好了，比方说我们要查看order_by_demo这个表的统计信息可以这么写：

mysql> USE xiaohaizi;
Database changed
​
mysql> SHOW TABLE STATUS LIKE 'single_table'\G
*************************** 1. row ***************************
           Name: single_table
         Engine: InnoDB
        Version: 10
     Row_format: Dynamic
           Rows: 9693
 Avg_row_length: 163
    Data_length: 1589248
Max_data_length: 0
   Index_length: 2752512
      Data_free: 4194304
 Auto_increment: 10001
    Create_time: 2018-12-10 13:37:23
    Update_time: 2018-12-10 13:38:03
     Check_time: NULL
      Collation: utf8_general_ci
       Checksum: NULL
 Create_options:
        Comment:
row in set (0.01 sec)

虽然出现了很多统计选项，但我们目前只关心两个：

• Rows

  本选项表示表中的记录条数。对于使用MyISAM存储引擎的表来说，该值是准确的，对于使用InnoDB存储引擎的表来说，该值是一个估计值。从查询结果我们也可以看出来，由于我们的single_table表是使用InnoDB存储引擎的，所以虽然实际上表中有10000条记录，但是SHOW TABLE STATUS显示的Rows值只有9693条记录。

• Data_length

  本选项表示表占用的存储空间字节数。使用MyISAM存储引擎的表来说，该值就是数据文件的大小，对于使用InnoDB存储引擎的表来说，该值就相当于聚簇索引占用的存储空间大小，也就是说可以这样计算该值的大小：

  Data_length = 聚簇索引的页面数量 x 每个页面的大小

  我们的single_table使用默认16KB的页面大小，而上边查询结果显示Data_length的值是1589248，所以我们可以反向来推导出聚簇索引的页面数量：

  聚簇索引的页面数量 = 1589248 ÷ 16 ÷ 1024 = 97

我们现在已经得到了聚簇索引占用的页面数量以及该表记录数的估计值，所以就可以计算全表扫描成本了，但是设计MySQL的大叔在真实计算成本时会进行一些微调，这些微调的值是直接硬编码到代码里的，由于没有注释，我也不知道这些微调值是个啥子意思，但是由于这些微调的值十分的小，并不影响我们分析，所以我们也没有必要在这些微调值上纠结了。现在可以看一下全表扫描成本的计算过程：

• I/O成本

  97 x 1.0 + 1.1 = 98.1

  97指的是聚簇索引占用的页面数，1.0指的是加载一个页面的成本常数，后边的1.1是一个微调值，我们不用在意。

• CPU成本：

  9639 x 0.2 + 1.0 = 1939.6

  9639指的是统计数据中表的记录数，对于InnoDB存储引擎来说是一个估计值，0.2指的是访问一条记录所需的成本常数，后边的1.0是一个微调值，我们不用在意。

• 总成本：

  98.1 + 1939.6 = 2037.7

综上所述，对于single_table的全表扫描所需的总成本就是2037.7。

小贴士：

我们前边说过表中的记录其实都存储在聚簇索引对应B+树的叶子节点中，所以只要我们通过根节点获得了最左边的叶子节点，就可以沿着叶子节点组成的双向链表把所有记录都查看一遍。也就是说全表扫描这个过程其实有的B+树内节点是不需要访问的，但是设计MySQL的大叔们在计算全表扫描成本时直接使用聚簇索引占用的页面数作为计算I/O成本的依据，是不区分内节点和叶子节点的，有点儿简单暴力，大家注意一下就好了。

3. 计算使用不同索引执行查询的代价

从第1步分析我们得到，上述查询可能使用到idx_key1和idx_key2这两个索引，我们需要分别分析单独使用这些索引执行查询的成本，最后还要分析是否可能使用到索引合并。这里需要提一点的是，MySQL查询优化器先分析使用唯一二级索引的成本，再分析使用普通索引的成本，所以我们也先分析idx_key2的成本，然后再看使用idx_key1的成本。

使用idx_key2执行查询的成本分析

idx_key2对应的搜索条件是：key2 > 10 AND key2 < 1000，也就是说对应的范围区间就是：(10, 1000)，使用idx_key2搜索的示意图就是这样子：

对于使用二级索引 + 回表方式的查询，设计MySQL的大叔计算这种查询的成本依赖两个方面的数据：

• 范围区间数量

  不论某个范围区间的二级索引到底占用了多少页面，查询优化器粗暴的认为读取索引的一个范围区间的I/O成本和读取一个页面是相同的。本例中使用idx_key2的范围区间只有一个：(10, 1000)，所以相当于访问这个范围区间的二级索引付出的I/O成本就是：

  1 x 1.0 = 1.0

• 需要回表的记录数

  优化器需要计算二级索引的某个范围区间到底包含多少条记录，对于本例来说就是要计算idx_key2在(10, 1000)这个范围区间中包含多少二级索引记录，计算过程是这样的：

  • 步骤1：先根据key2 > 10这个条件访问一下idx_key2对应的B+树索引，找到满足key2 > 10这个条件的第一条记录，我们把这条记录称之为区间最左记录。我们前头说过在B+数树中定位一条记录的过程是贼快的，是常数级别的，所以这个过程的性能消耗是可以忽略不计的。

  • 步骤2：然后再根据key2 < 1000这个条件继续从idx_key2对应的B+树索引中找出第一条满足这个条件的记录，我们把这条记录称之为区间最右记录，这个过程的性能消耗也可以忽略不计的。

  • 步骤3：如果区间最左记录和区间最右记录相隔不太远（在MySQL 5.7.21这个版本里，只要相隔不大于10个页面即可），那就可以精确统计出满足key2 > 10 AND key2 < 1000条件的二级索引记录条数。否则只沿着区间最左记录向右读10个页面，计算平均每个页面中包含多少记录，然后用这个平均值乘以区间最左记录和区间最右记录之间的页面数量就可以了。那么问题又来了，怎么估计区间最左记录和区间最右记录之间有多少个页面呢？解决这个问题还得回到B+树索引的结构中来：

     

    如图，我们假设区间最左记录在页b中，区间最右记录在页c中，那么我们想计算区间最左记录和区间最右记录之间的页面数量就相当于计算页b和页c之间有多少页面，而每一条目录项记录都对应一个数据页，所以计算页b和页c之间有多少页面就相当于计算它们父节点（也就是页a）中对应的目录项记录之间隔着几条记录。在一个页面中统计两条记录之间有几条记录的成本就贼小了。

    不过还有问题，如果页b和页c之间的页面实在太多，以至于页b和页c对应的目录项记录都不在一个页面中该咋办？继续递归啊，也就是再统计页b和页c对应的目录项记录所在页之间有多少个页面。之前我们说过一个B+树有4层高已经很了不得了，所以这个统计过程也不是很耗费性能。

  知道了如何统计二级索引某个范围区间的记录数之后，就需要回到现实问题中来，根据上述算法测得idx_key2在区间(10, 1000)之间大约有95条记录。读取这95条二级索引记录需要付出的CPU成本就是：

   95 x 0.2 + 0.01 = 19.01

  其中95是需要读取的二级索引记录条数，0.2是读取一条记录成本常数，0.01是微调。

  在通过二级索引获取到记录之后，还需要干两件事儿：

  • 根据这些记录里的主键值到聚簇索引中做回表操作

    这里需要大家使劲儿睁大自己滴溜溜的大眼睛仔细瞧，设计MySQL的大叔评估回表操作的I/O成本依旧很豪放，他们认为每次回表操作都相当于访问一个页面，也就是说二级索引范围区间有多少记录，就需要进行多少次回表操作，也就是需要进行多少次页面I/O。我们上边统计了使用idx_key2二级索引执行查询时，预计有95条二级索引记录需要进行回表操作，所以回表操作带来的I/O成本就是：

    95 x 1.0 = 95.0

    其中95是预计的二级索引记录数，1.0是一个页面的I/O成本常数。

  • 回表操作后得到的完整用户记录，然后再检测其他搜索条件是否成立

    回表操作的本质就是通过二级索引记录的主键值到聚簇索引中找到完整的用户记录，然后再检测除key2 > 10 AND key2 < 1000这个搜索条件以外的搜索条件是否成立。因为我们通过范围区间获取到二级索引记录共95条，也就对应着聚簇索引中95条完整的用户记录，读取并检测这些完整的用户记录是否符合其余的搜索条件的CPU成本如下：

     

    设计MySQL的大叔只计算这个查找过程所需的I/O成本，也就是我们上一步骤中得到的95.0，在内存中的定位完整用户记录的过程的成本是忽略不计的。在定位到这些完整的用户记录后，需要检测除key2 > 10 AND key2 < 1000这个搜索条件以外的搜索条件是否成立，这个比较过程花费的CPU成本就是：

    95 x 0.2 = 19.0

    其中95是待检测记录的条数，0.2是检测一条记录是否符合给定的搜索条件的成本常数。

所以本例中使用idx_key2执行查询的成本就如下所示：

• I/O成本：

  1.0 + 95 x 1.0 = 96.0 (范围区间的数量 + 预估的二级索引记录条数)

• CPU成本：

  95 x 0.2 + 0.01 + 95 x 0.2 = 38.01 （读取二级索引记录的成本 + 读取并检测回表后聚簇索引记录的成本）

综上所述，使用idx_key2执行查询的总成本就是：

96.0 + 38.01 = 134.01

使用idx_key1执行查询的成本分析

idx_key1对应的搜索条件是：key1 IN ('a', 'b', 'c')，也就是说相当于3个单点区间：

• ['a', 'a']

• ['b', 'b']

• ['c', 'c']

使用idx_key1搜索的示意图就是这样子：

与使用idx_key2的情况类似，我们也需要计算使用idx_key1时需要访问的范围区间数量以及需要回表的记录数：

• 范围区间数量

  使用idx_key1执行查询时很显然有3个单点区间，所以访问这3个范围区间的二级索引付出的I/O成本就是：

  3 x 1.0 = 3.0

• 需要回表的记录数

  由于使用idx_key1时有3个单点区间，所以每个单点区间都需要查找一遍对应的二级索引记录数：

  • 查找单点区间['a', 'a']对应的二级索引记录数

    计算单点区间对应的二级索引记录数和计算连续范围区间对应的二级索引记录数是一样的，都是先计算区间最左记录和区间最右记录，然后再计算它们之间的记录数，具体算法上边都唠叨过了，就不赘述了。最后计算得到单点区间['a', 'a']对应的二级索引记录数是：35。

  • 查找单点区间['b', 'b']对应的二级索引记录数

    与上同理，计算得到本单点区间对应的记录数是：44。

  • 查找单点区间['c', 'c']对应的二级索引记录数

    与上同理，计算得到本单点区间对应的记录数是：39。

  所以，这三个单点区间总共需要回表的记录数就是：

  35 + 44 + 39 = 118

  读取这些二级索引记录的CPU成本就是：

  118 x 0.2 + 0.01 = 23.61

  得到总共需要回表的记录数之后，就要考虑：

  • 根据这些记录里的主键值到聚簇索引中做回表操作

    所需的I/O成本就是：

    118 x 1.0 = 118.0

  • 回表操作后得到的完整用户记录，然后再比较其他搜索条件是否成立

    此步骤对应的CPU成本就是：

    118 x 0.2 = 23.6

所以本例中使用idx_key1执行查询的成本就如下所示：

• I/O成本：

  3.0 + 118 x 1.0 = 121.0 (范围区间的数量 + 预估的二级索引记录条数)

• CPU成本：

  118 x 0.2 + 0.01 + 118 x 0.2 = 47.21 （读取二级索引记录的成本 + 读取并检测回表后聚簇索引记录的成本）

综上所述，使用idx_key1执行查询的总成本就是：

121.0 + 47.21 = 168.21

是否有可能使用索引合并（Index Merge）

本例中有关key1和key2的搜索条件是使用AND连接起来的，而对于idx_key1和idx_key2都是范围查询，也就是说查找到的二级索引记录并不是按照主键值进行排序的，并不满足使用Intersection索引合并的条件，所以并不会使用索引合并。

小贴士：

MySQL查询优化器计算索引合并成本的算法也比较麻烦，所以我们这也就不展开唠叨了。

4. 对比各种执行方案的代价，找出成本最低的那一个

下边把执行本例中的查询的各种可执行方案以及它们对应的成本列出来：

• 全表扫描的成本：2037.7

• 使用idx_key2的成本：134.01

• 使用idx_key1的成本：168.21

很显然，使用idx_key2的成本最低，所以当然选择idx_key2来执行查询喽。

小贴士：

考虑到大家的阅读体验，为了最大限度的减少大家在理解优化器工作原理的过程中遇到的懵逼情况，这里对优化器在单表查询中对比各种执行方案的代价的方式稍稍的做了简化，不过毕竟大部分同学不需要去看MySQL的源码，把大致的精神传递正确就好了哈。

基于索引统计数据的成本计算

有时候使用索引执行查询时会有许多单点区间，比如使用IN语句就很容易产生非常多的单点区间，比如下边这个查询（下边查询语句中的...表示还有很多参数）：

SELECT * FROM single_table WHERE key1 IN ('aa1', 'aa2', 'aa3', ... , 'zzz');

很显然，这个查询可能使用到的索引就是idx_key1，由于这个索引并不是唯一二级索引，所以并不能确定一个单点区间对应的二级索引记录的条数有多少，需要我们去计算。计算方式我们上边已经介绍过了，就是先获取索引对应的B+树的区间最左记录和区间最右记录，然后再计算这两条记录之间有多少记录（记录条数少的时候可以做到精确计算，多的时候只能估算）。设计MySQL的大叔把这种通过直接访问索引对应的B+树来计算某个范围区间对应的索引记录条数的方式称之为index dive。

小贴士：

dive直译为中文的意思是跳水、俯冲的意思，原谅我的英文水平捉急，我实在不知道怎么翻译 index dive，索引跳水？索引俯冲？好像都不太合适，所以压根儿就不翻译了。不过大家要意会index dive就是直接利用索引对应的B+树来计算某个范围区间对应的记录条数。

有零星几个单点区间的话，使用index dive的方式去计算这些单点区间对应的记录数也不是什么问题，可是你架不住有的孩子憋足了劲往IN语句里塞东西呀，我就见过有的同学写的IN语句里有20000个参数的