高性能MySQL之索引深入原理分析

一、背景

我们工作中经常打交道的就是索引,那么到底什么是索引呢?例如,当一个SQL查询比较慢的时候,你可能会说给“某个字段加个索引吧”之类的解决方案。

总的来说索引的出现其实就是为了提高数据查询的效率,就像书的目录一样。一本上千页页的英语字典,如果你想快速找到其中的某一个单词,在不借助目录的情况下,那我估计你可得找一会儿。同样,对于数据库的表而言,索引其实就是它的“目录”。实现索引的方式却有很多种,所以这里也就引入了索引模型的概念。可以用于提高读写效率的数据结构很多,接下里主要介绍常见、也比较简单的数据结构,它们分别是哈希表、有序数组和搜索树。接下来用半篇文章的篇幅给大家介绍不同的数据结构,以及它们的适用场景,你可能会觉得有些枯燥。但是,我们还是要多花一些时间来理解下面的内容,毕竟这是数据库处理数据的核心概念之一,在分析问题的时候会经常用到。当你理解了索引的模型后,就会发现在分析问题的时候会有一个更清晰的视角,体会到引擎设计的精妙之处。

数据库底层存储的核心就是基于这些数据模型的。每碰到一个新数据库,我们需要先关注它的数据模型,这样才能从理论上分析出这个数据库的适用场景。

 

二、哈希表

  哈希表是以键值对 (key-value) 存储数据的结构,我们只需要通过key,就可以快速的找到对应的value。哈希表的实现思路很简单,把值放在数据里,用一个哈希函数把key换算成一个确定的位置,然后把value放在数组的这个位置,不可避免地,多个key值经过哈希函数的换算,会出现同一个值的情况。处理这种情况的一种方法是,拉出一个链表。这跟HashMap底层table数组很相似的。如果有小伙伴不了结果HashMap的底层的话,可以看一下我篇文章 https://www.cnblogs.com/*ncong/p/9465414.html 。

接下来,用一个学生信息卡信息和姓名的的表来进行举例子,需要根据身份证号查找对应的名字,这时对应的哈希索引的示意图如下所示:

高性能MySQL之索引深入原理分析

可以看到student 2 和student 4根据学号计算哈希计算得到数据的位置是 4 ,那不是冲突了吗?,放心这没关系的,后面还跟着一个连表呢。假设,这时候你要查student_id_2 对应的名字是什么,这时候处理的步骤就是:

  1.首先,将student_id_2通过哈希函数计算出 4,

  2.然后按顺序遍历下去,找到student 2。

需要注意的是,图中四个student_id_n的值并不是递增的,这样做的好处是增加新的student时速度会很快,只需要往后追加。但缺点是,因为不是有序的,所以哈希索引做区间查询的速度是很慢的。你可以设想下,如果你现在要找学号在[student_id_X, student_id_Y]这个区间的所有的学生,就必须全部扫描一遍了。所以,哈希表这种结构适用于只有等值查询的场景,比如Memcached及其他一些NoSQL引擎。

 

三、有序数组

我们知道有序数组在等值查询和范围查询场景中的性能就都非常优秀。还是上面这个根据学号号查学生名字的例子,如果我们使用有序数组来实现的话,示意图如下所示:

高性能MySQL之索引深入原理分析

我们知道一个学号是不可能有重复的,这个数组就是学号号递增的顺序保存的。这时候如果你要查student_id_n2对应的名字,用二分法就可以快速得到,这个时间复杂度是O(log(N))。

有数据结构基础的人,很明显看到这个索引结构支持范围查询。你要查身份证号在[student_id_X, student_id_Y]区间的student,可以先用二分法找到 student_id_X,(如果不存在student_id_X,,就找到大于student_id_X,的第一个stduent),然后向右遍历,直到查到第一个大于student_id_Y的学号,退出循环。

如果仅仅看查询效率,有序数组就是最好的数据结构了。但是,在需要更新数据的时候就麻烦了,你往中间插入一个记录就必须得挪动后面所有的记录,成本太高。所以,有序数组索引只适用于静态存储引擎,比如你要保存的是某一年某个城市的所有人口信息,这类不会再修改的数据。

 

四、二叉树

二叉搜索树的特点是:每个节点的左儿子小于父节点,父节点又小于右儿子。我们继续根据学号号查学生名字的例子,如果我们用二叉搜索树来实现的话,示意图如下所示:

高性能MySQL之索引深入原理分析

如果你要查student_id_n2的话,按照图中的搜索顺序就是按照studentA -> studentC -> studentF -> student2这个路径得到。这个时间复杂度是O(log(N))。当然为了维持O(log(N))的查询复杂度,你就需要保持这棵树是平衡二叉树。为了做这个保证,更新的时间复杂度也是O(log(N))。树可以有二叉,也可以有多叉。多叉树就是每个节点有多个儿子,儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的,但是实际上大多数的数据库存储却并不使用二叉树。其原因是,索引不止存在内存中,还要写到磁盘上。

你可以想象一下一棵100万节点的平衡二叉树,树高20。一次查询可能需要访问20个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要10 ms左右的寻址时间。也就是说,对于一个100万行的表,如果使用二叉树来存储,单独访问一个行可能需要20个10 ms的时间,这个查询可真够慢的。为了让一个查询尽量少地读磁盘,就必须让查询过程访问尽量少的数据块。那么,我们就不应该使用二叉树,而是要使用“N叉”树。这里,“N叉”树中的“N”取决于数据块的大小。

以InnoDB的一个整数字段索引为例,这个N差不多是1200。这棵树高是4的时候,就可以存1200的3次方个值,这已经17亿了。考虑到树根的数据块总是在内存中的,一个10亿行的表上一个整数字段的索引,查找一个值最多只需要访问3次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。

N叉树由于在读写上的性能优点,以及适配磁盘的访问模式,已经被广泛应用在数据库引擎中了。不管是哈希还是有序数组,或者N叉树,它们都是不断迭代、不断优化的产物或者解决方案。数据库技术发展到今天,跳表、LSM树等数据结构也被用于引擎设计中。我们脑中要有个概念,数据库底层存储的核心就是基于这些数据模型的。每碰到一个新数据库,我们需要先关注它的数据模型,这样才能从理论上分析出这个数据库的适用场景。

 

五、InnoDB索引模型

在InnoDB中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表。由于InnoDB使用了B+树索引模型,所以数据都是存储在B+树中的。每一个索引在InnoDB里面对应一棵B+树。假设,我们有一个主键列为ID的表,表中有字段k,并且在k上有索引。

create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中R1~R5的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6),两棵树的示例示意图如下。

高性能MySQL之索引深入原理分析

从上图可以看到,根据叶子节点的内容,索引类型分为主键索引和非主键索引。主键索引的叶子节点存的是整行数据。在InnoDB里,主键索引也被称为聚簇索引(clustered index)。

非主键索引的叶子节点内容是主键的值。在InnoDB里,非主键索引也被称为二级索引(secondary index)。

那么基于主键索引和普通索引的查询有什么区别?

  • 如果语句是select * from T where ID=500,即主键查询方式,则只需要搜索ID这棵B+树;
  • 如果语句是select * from T where k=5,即普通索引查询方式,则需要先搜索k索引树,得到ID的值为500,再到ID索引树搜索一次。这个过程称为回表。

因此,基于非主键索引的查询需要多扫描一棵索引树。因此,我们在应用中应该尽量使用主键查询。

B+树为了维护索引有序性,在插入新值的时候需要做必要的维护。以上面这个图为例,如果插入新的行ID值为700,则只需要在R6的记录后面插入一个新记录。如果新插入的ID值为450,就相对麻烦了,需要逻辑上挪动后面的数据,空出位置。而更糟的情况是,如果R6所在的数据页已经满了,根据B+树的算法,这时候需要申请一个新的数据页,然后挪动部分数据过去。这个过程称为页分裂。在这种情况下,性能自然会受影响。

除了性能外,页分裂操作还影响数据页的利用率。原本放在一个页的数据,现在分到两个页中,整体空间利用率降低大约50%。当然有分裂就有合并。当相邻两个页由于删除了数据,利用率很低之后,会将数据页做合并。合并的过程,可以认为是分裂过程的逆过程。

 

接下来用一个例子,来分析一下哪些场景下应该使用自增主键,而哪些场景下不应该。

自增主键是指自增列上定义的主键,在建表语句中一般是这么定义的: NOT NULL PRIMARY KEY AUTO_INCREMENT。插入新记录的时候可以不指定ID的值,系统会获取当前ID最大值加1作为下一条记录的ID值。也就是说,自增主键的插入数据模式,正符合了我们前面提到的递增插入的场景。每次插入一条新记录,都是追加操作,都不涉及到挪动其他记录,也不会触发叶子节点的分裂。

而有业务逻辑的字段做主键,则往往不容易保证有序插入,这样写数据成本相对较高。除了考虑性能外,我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段,比如字符串类型的学生的学号,那应该用学号做主键,还是用自增字段做主键呢?由于每个非主键索引的叶子节点上都是主键的值。如果用学号做主键,那么每个二级索引的叶子节点占用约20个字节,而如果用整型做主键,则只要4个字节,如果是长整型(bigint)则是8个字节。

显然,主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。所以,从性能和存储空间方面考量,自增主键往往是更合理的选择。

有没有什么场景适合用业务字段直接做主键的呢?还是有的。比如,有些业务的场景需求是这样的:

  1. 只有一个索引;

  2. 该索引必须是唯一索引。

没错,这就是就是典型的KV场景。由于没有其他索引,所以也就不用考虑其他索引的叶子节点大小的问题。这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则,直接将这个索引设置为主键,可以避免每次查询需要搜索两棵树。

 

六、覆盖索引

如果执行 select * from T where k between 3 and 5这条SQL语句,需要执行几次树的搜索操作,会扫描多少行?

 结合上面的图,可以分析得到这条SQL的执行流程如下:

  1. 在k索引树上找到k=3的记录,取得 ID = 300;

  2. 再到ID索引树查到ID=300对应的R3;

  3. 在k索引树取下一个值k=5,取得ID=500;

  4. 再回到ID索引树查到ID=500对应的R5;

  5. 在k索引树取下一个值k=6,不满足条件,循环结束。

大家看到这个过程不就是上面所讲到的回表吗?是的,回到主键索引树搜索的过程,我们称为回表。可以看到,这个查询过程读了k索引树的3条记录(步骤1、3和5),回表了两次(步骤2和4)。

由于查询结果所需要的数据只在主键索引上有,因此逼不得已不得不进行回表。那么,有没有可能经过索引优化,避免回表过程呢?

当时是有措施避免回表,这就是接下来要进行讲解的通过覆盖索引避免回表操作。

何为覆盖索引?

如果一个索引包含(或覆盖)所有需要查询的字段的值,称为‘覆盖索引’。即只需扫描索引而无须回表。

如果执行的语句是select ID from T where k between 3 and 5,这时只需要查ID的值,而ID的值已经在k索引树上了,因此可以直接提供查询结果,不需要回表。也就是说,在这个查询里面,索引k已经“覆盖了”我们的查询需求。这就是所谓的覆盖索引。

由于覆盖索引可以减少树的搜索次数,极大的提升查询性能,因此使用覆盖索引是一个常用的性能优化有段,这个要切记。

这里需要注意一点,引擎内部使用覆盖索引在索引k上其实读了三个记录,R3~R6(对应的索引k上的记录项),但是对于MySQL的Server层来说,它就是找引擎拿到了3条记录,因此MySQL认为扫描行数是3。

 

结合上面的覆盖索引,我们思考一个问题:在一个市民信息表上,是否有必要将身份证号和名字建立联合索引?

市民表的建表语句如下:

CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

身份证号是市民的唯一标识。也就是说,如果有根据身份证号查询市民信息的需求,我们只要在身份证号字段上建立索引就够了。而再建立一个(身份证号、姓名)的联合索引,是不是浪费空间?

有根据身份证号查询市民信息的需求而再建立联合索引确实是很浪费空间,但是如果现在有一个高频请求,要根据市民的身份证号查询他的姓名,这个联合索引就有意义了。它可以在这个高频请求上用到覆盖索引,不再需要回表查整行记录,减少语句的执行时间。

我们知道索引字段的维护总是有代价的。因此,在建立冗余索引来支持覆盖索引时就需要权衡考虑了。

 

七、最左匹配原则

如果为每一种查询都设计一个索引,这无疑索引的数量越来越多,所占用的空间也就越来越大。如果我现在要按照市民的身份证号去查他的家庭地址呢?虽然这个查询需求在业务中出现的概率不高,但总不能让它走全表扫描吧?反过来说,单独为一个不频繁的请求创建一个(身份证号,地址)的索引又感觉有点浪费。应该怎么做呢?

 办法还是有的,这就是解析来通过索引的最左前缀来定位数据记录,为了很好讲解,接下里用联合索引进行举例子:

高性能MySQL之索引深入原理分析

从图虫可以看到,索引项是按照索引定义里面出现的字段顺序排序的。当你的逻辑需求是查到所有名字是“张三”的人时,可以快速定位到ID4,然后向后遍历得到所有需要的结果。

当你要查的是所有名字第一个字是“张”的人,你的SQL语句的条件是"where name like ‘张%’"。这时,你也能够用上这个索引,查找到第一个符合条件的记录是ID3,然后向后遍历,直到不满足条件为止。注意前百分号是不走索引的,如 ‘%张’。

因此可以看到,不只是索引的全部定义,只要满足最左前缀,就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左N个字段,也可以是字符串索引的最左M个字符。

 

接下来让我们思考一个问题:在建立联合索引的时候,如何安排索引内的字段顺序?

  第一原则是,如果通过调整顺序,可以少维护一个索引,那么这个顺序往往就是需要优先考虑采用的。

评估标准是索引的复用能力。因为可以支持最左前缀,所以当已经有了(a,b)这个联合索引后,一般就不需要单独在a上建立索引了。

因此,现在我们知道上面为什么要为高频请求创建(身份证号,姓名)这个联合索引,并用这个索引支持“根据身份证号查询地址”的需求了。

如果既有联合查询,又有基于a、b各自的查询呢?查询条件里面只有b的语句,是无法使用(a,b)这个联合索引的,这时候你不得不维护另外一个索引,也就是说你需要同时维护(a,b)、(b) 这两个索引。这时候,需要我们考虑的原则就是空间了。比如上面这个市民表的情况,name字段是比age字段大的 ,那我就建议你创建一个(name,age)的联合索引和一个(age)的单字段索引。

 

八、索引下推优化

满足最左前缀原则的时候,最左前缀可以用于在索引中定位记录。这时,你可能要问,那些不符合最左前缀的部分,会怎么样呢?

以市民表的联合索引(name, age)为例。如果现在有一个需求:检索出表中“名字第一个字是张,而且年龄是10岁的所有男孩”。那么,SQL语句是这么写的:

select * from tuser where name like 张% and age=10 and ismale=1;

知道了前缀索引规则,所以这个语句在搜索索引树的时候,只能用 “张”,找到第一个满足条件的记录ID3。当然,这还不错,总比全表扫描要好。有没有什么条件可以进一步判断呢?

在MySQL 5.6之前,只能从ID3开始一个个回表。到主键索引上找出数据行,再对比字段值。

而MySQL 5.6 引入的索引下推优化(index condition pushdown), 可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。

索引下推优化执行流程图如下所示:

无索引下推的执行流程图:

高性能MySQL之索引深入原理分析

索引下推优化执行流程图如下:

高性能MySQL之索引深入原理分析

上面两个图里面,每一个虚线箭头表示回表一次。

无索引下推的执行流程图中,在(name,age)索引里面我特意去掉了age的值,这个过程InnoDB并不会去看age的值,只是按顺序把“name第一个字是’张’”的记录一条条取出来回表。因此,需要回表4次。

索引下推优化执行流程图跟无索引下推的执行流程图的区别是,InnoDB在(name,age)索引内部就判断了age是否等于10,对于不等于10的记录,直接判断并跳过。在我们的这个例子中,只需要对ID4、ID5这两条记录回表取数据判断,就只需要回表2次。

可以看到,在满足语句需求的情况下, 尽量少地访问资源是数据库设计的重要原则之一。我们在使用数据库的时候,尤其是在设计表结构时,也要以减少资源消耗作为目标。

 

九、普通索引与唯一索引

在不同的业务场景下,应该选择普通索引,还是唯一索引?

假设你在维护一个市民系统,每个人都有一个唯一的身份证号,而且业务代码已经保证了不会写入两个重复的身份证号。如果市民系统需要按照身份证号查姓名,就会执行类似这样的SQL语句:

select name from CUser where id_card = xxxxxxxyyyyyyzzzzz;

我们第一反应就是考虑在id_card字段上建索引。

从这条SQL可以看到身份证号字段比较大,因此不建议你把身份证号当做主键,那么现在你有两个选择,要么给id_card字段创建唯一索引,要么创建一个普通索引。如果业务代码已经保证了不会写入重复的身份证号,那么这两个选择逻辑上都是正确的。

从性能的角度考虑,你选择唯一索引还是普通索引呢?选择的依据是什么呢?

接下来,我们就从这两种索引对查询语句和更新语句的性能影响来进行分析。还是使用上面一个例子的图,如下:

高性能MySQL之索引深入原理分析

查询过程:

假设,执行查询的语句是 select id from T where k=5。这个查询语句在索引树上查找的过程,先是通过B+树从树根开始,按层搜索到叶子节点,也就是图中右下角的这个数据页,然后可以认为数据页内部通过二分法来定位记录。

  1.对于普通索引来说,查找到满足条件的第一个记录(5,500)后,需要查找下一个记录,直到碰到第一个不满足k=5条件的记录。

  2.对于唯一索引来说,由于索引定义了唯一性,查找到第一个满足条件的记录后,就会停止继续检索。

那么,这两者不同所带来的性能差距有大呢?

答案是 微乎其微。

我们知道,InnoDB的数据是按数据页为单位来读写的。也就是说,当需要读一条记录的时候,并不是将这个记录本身从磁盘读出来,而是以页为单位,将其整体读入内存。在InnoDB中,每个数据页的大小默认是16KB。正是因为引擎是按页读写的,所以说,当找到k=5的记录的时候,它所在的数据页就都在内存里了。那么,对于普通索引来说,要多做的那一次“查找和判断下一条记录”的操作,就只需要一次指针寻找和一次计算。

当然,如果k=5这个记录刚好是这个数据页的最后一个记录,那么要取下一个记录,必须读取下一个数据页,这个操作会稍微复杂一些。但是,我们之前计算过,对于整型字段,一个数据页可以放近千个key,因此出现这种情况的概率会很低。所以,我们计算平均性能差异时,仍可以认为这个操作成本对于现在的CPU来说可以忽略不计。

 

更新过程:

为了说明普通索引和唯一索引对更新语句性能的影响这个问题之前,必须要先了解change buffer。

当需要更新一个数据页时,如果数据页在内存中就直接更新,而如果这个数据页还没有在内存中的话,在不影响数据一致性的前提下,InooDB会将这些更新操作缓存在change buffer中,这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候,将数据页读入内存,然后执行change buffer中与这个页有关的操作。通过这种方式就能保证这个数据逻辑的正确性。实际上它是可以持久化的数据。也就是说,change buffer在内存中有拷贝,也会被写入到磁盘上。

将change buffer中的操作应用到原数据页,得到最新结果的过程称为merge。除了访问这个数据页会触发merge外,系统有后台线程会定期merge。在数据库正常关闭(shutdown)的过程中,也会执行merge操作。显然,如果能够将更新操作先记录在change buffer,减少读磁盘,语句的执行速度会得到明显的提升。而且,数据读入内存是需要占用buffer pool的,所以这种方式还能够避免占用内存,提高内存利用率。

 

哪种索引可以使用change buffer呢?

对于唯一索引来说,所有的更新操作都要先判断这个操作是否违反唯一性约束。比如,要插入(4,400)这个记录,就要先判断现在表中是否已经存在k=4的记录,而这必须要将数据页读入内存才能判断。如果都已经读入到内存了,那直接更新内存会更快,就没必要使用change buffer了。因此,唯一索引的更新就不能使用change buffer,实际上也只有普通索引可以使用。

change buffer用的是buffer pool里的内存,因此不能无限增大。change buffer的大小,可以通过参数innodb_change_buffer_max_size来动态设置。这个参数设置为50的时候,表示change buffer的大小最多只能占用buffer pool的50%。

如果要在上图中插入一个新记录(4.5,450)的话,InnoDB的处理流程是怎样的呢?

第一种情况是,这个记录要更新的目标页在内存中。这时,InnoDB的处理流程如下:

  • 对于唯一索引来说,找到4和5之间的位置,判断到没有冲突,插入这个值,语句执行结束;
  • 对于普通索引来说,找到4和5之间的位置,插入这个值,语句执行结束。

这样看来,普通索引和唯一索引对更新语句性能影响的差别,只是一个判断,只会耗费微小的CPU时间。

 

第二种情况是,这个记录要更新的目标页不在内存中。这时,InnoDB的处理流程如下:

  • 对于唯一索引来说,需要将数据页读入内存,判断到没有冲突,插入这个值,语句执行结束;
  • 对于普通索引来说,则是将更新记录在change buffer,语句执行就结束了。

 

将数据从磁盘读入内存涉及随机IO的访问,是数据库里面成本最高的操作之一。change buffer因为减少了随机磁盘访问,所以对更新性能的提升是会很明显的。

注意一下,当业务中有大量的插入数据的时候,而且原先存在普通索引的时候,千万不要把普通索引改成唯一索引,因为这样会导致整个系统处于阻塞状态,更新语句全部堵住,并且库内存命中率急剧下降。

 

到这里,我们在反思一下:难道普通索引的所有场景,使用change buffer都可以起到加速作用吗?

因为merge的时候是真正进行数据更新的时刻,而change buffer的主要目的就是将记录的变更动作缓存下来,所以在一个数据页做merge之前,change buffer记录的变更越多(也就是这个页面上要更新的次数越多),收益就越大。

因此,对于写多读少的业务来说,页面在写完以后马上被访问到的概率比较小,此时change buffer的使用效果最好。这种业务模型常见的就是账单类、日志类的系统。

反过来,假设一个业务的更新模式是写入之后马上会做查询,那么即使满足了条件,将更新先记录在change buffer,但之后由于马上要访问这个数据页,会立即触发merge过程。这样随机访问IO的次数不会减少,反而增加了change buffer的维护代价。所以,对于这种业务模式来说,change buffer反而起到了副作用。

 

回到我们上面一开始所提到的问题,普通索引和唯一索引应该怎么选择。其实,这两类索引在查询能力上是没差别的,主要考虑的是对更新性能的影响。因此尽量选择普通索引。

如果所有的更新后面,都马上伴随着对这个记录的查询,那么你应该关闭change buffer。而在其他情况下,change buffer都能提升更新性能。在实际使用中,你会发现,普通索引和change buffer的配合使用,对于数据量大的表的更新优化还是很明显的。特别地,在使用机械硬盘时,change buffer这个机制的收效是非常显著的。所以,当你有一个类似“历史数据”的库,并且出于成本考虑用的是机械硬盘时,那你应该特别关注这些表里的索引,尽量使用普通索引,然后把change buffer 尽量开大,以确保这个“历史数据”表的数据写入速度。

 

十、MySQL对索引的选择

在MySQL中一张表其实是可以支持多个索引的。但是,你写SQL语句的时候,并没有主动指定使用哪个索引。也就是说,使用哪个索引是由MySQL来确定的。

在我们实际开发中,肯定遇到过这种情况:一条加了索引的SQL本来可以执行很快的,但是由于MySQL选错索引导致执行速度变慢。

下面使用一个例子来看一下MySQL选择索引的例子,如下:

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `a` (`a`),
  KEY `b` (`b`)
) ENGINE=InnoDB;

可以看到表中有两个索引,分别是a b,现在往表中插入10万行数据,执行的存储过程如下:

delimiter ;;
create procedure idata()
begin
  declare i int;
  set i=1;
  while(i<=100000)do
    insert into t values(i, i, i);
    set i=i+1;
  end while;
end;;
delimiter ;
call idata();

 

接下来,我们先执行以下一条SQL,脚本如下:

select * from t where a between 10000 and 20000;

可以看到这条语句肯定是使用索引a的,接着我们使用explain命令看这条SQL的执行状态如下:

高性能MySQL之索引深入原理分析

 

 高性能MySQL之索引深入原理分析

 

 这条查询语句的执行也确实符合预期,key这个字段值是’a’,表示优化器选择了索引a。不过先别着急,如果我们做以下的操作,这个例子就不会这么简单了,操作如下图:

高性能MySQL之索引深入原理分析

session t1时间 A开启了一个事务。随后,session B 在 t2 时间内把数据都删除后,又调用了 idata这个存储过程,插入了10万行数据。

这时候,session B t3时间内的查询语句select * from t where a between 10000 and 20000就不会再选择索引a了。我们可以通过慢查询日志(slow log)来查看一下具体的执行情况。

为了说明优化器选择的结果是否正确,我增加了一个对照,即:使用force index(a)来让优化器强制使用索引a(这部分内容,我还会在这篇文章的后半部分中提到)。

下面的三条SQL语句,就是这个实验过程。

set long_query_time=0;
select * from t where a between 10000 and 20000; /*Q1*/
select * from t force index(a) where a between 10000 and 20000;/*Q2*/

第一句,是将慢查询日志的阈值设置为0,表示这个线程接下来的语句都会被记录入慢查询日志中;

第二句,Q1是session B原来的查询;

第三句,Q2是加了force index(a)来和session B原来的查询语句执行情况对比。

这三条SQL语句执行完成后的慢查询日志如下所示:

 

接下来看这三条的慢查询日志。如下所示:

高性能MySQL之索引深入原理分析

可以看到,Q1扫描了10万行,显然是走了全表扫描,执行时间是40毫秒。Q2扫描了10001行,执行了21毫秒。也就是说,我们在没有使用force index的时候,MySQL用错了索引,导致了更长的执行时间。

 

这个例子对应的是我们平常不断地删除历史数据和新增数据的场景。这时,MySQL竟然会选错索引,是不是有点奇怪呢?

我们之前的文章讲到,索引的选择是优化器的工作,优化器选择索引的目的,是找到一个最优的执行方案,并用最小的代价去执行语句。在数据库里面,扫描行数是影响执行代价的因素之一。扫描的行数越少,意味着访问磁盘数据的次数越少,消耗的CPU资源越少。然而,扫描行数并不是唯一的判断标准,优化器还会结合是否使用临时表、是否排序等因素进行综合判断。

我们这个简单的查询语句并没有涉及到临时表和排序,所以MySQL选错索引肯定是在判断扫描行数的时候出问题了。

那么问题来了,扫描行数是如何判断的呢?

其实MySQL在真正开始执行语句之前,并不能精确地知道满足这个条件的记录有多少条,而只能根据统计信息来估算记录数。这个统计信息就是索引的“区分度”。显然,一个索引上不同的值越多,这个索引的区分度就越好。而一个索引上不同的值的个数,我们称之为“基数”(cardinality)。也就是说,这个基数越大,索引的区分度越好。

我们可以使用show index方法,看到一个索引的基数。如图4所示,就是表t的show index 的结果 。虽然这个表的每一行的三个字段值都是一样的,但是在统计信息中,这三个索引的基数值并不同,而且其实都不准确。

SHOW INDEX FROM t;

高性能MySQL之索引深入原理分析

 

 

那么,MySQL是怎样得到索引的基数的呢?其实MySQL采样统计的方法。

为什么要采样统计呢?

因为把整张表取出来一行行统计,虽然可以得到精确的结果,但是代价太高了,所以只能选择“采样统计”。采样统计的时候,InnoDB默认会选择N个数据页,统计这些页面上的不同值,得到一个平均值,然后乘以这个索引的页面数,就得到了这个索引的基数。而数据表是会持续更新的,索引统计信息也不会固定不变。所以,当变更的数据行数超过1/M的时候,会自动触发重新做一次索引统计。

在MySQL中,有两种存储索引统计的方式,可以通过设置参数innodb_stats_persistent的值来选择:

  • 设置为on的时候,表示统计信息会持久化存储。这时,默认的N是20,M是10。
  • 设置为off的时候,表示统计信息只存储在内存中。这时,默认的N是8,M是16。

由于是采样统计,所以不管N是20还是8,这个基数都是很容易不准的。

从 上图中看到,这次的索引统计值(cardinality列)虽然不够精确,但大体上还是差不多的,选错索引一定还有别的原因。

其实索引统计只是一个输入,对于一个具体的语句来说,优化器还要判断,执行这个语句本身要扫描多少行。

接下来,我们再一起看看优化器预估的,这两个语句的扫描行数是多少。

高性能MySQL之索引深入原理分析

 

rows这个字段表示的是预计扫描行数。其中,Q1的结果还是符合预期的,rows的值是104620;但是Q2的rows值是37116,偏差就大了。而图1中我们用explain命令看到的rows是只有10001行,是这个偏差误导了优化器的判断。

化器为什么放着扫描37000行的执行计划不用,却选择了扫描行数是100000的执行计划呢?

这是因为,如果使用索引a,每次从索引a上拿到一个值,都要回到主键索引上查出整行数据,这个代价优化器也要算进去的。而如果选择扫描10万行,是直接在主键索引上扫描的,没有额外的代价。优化器会估算这两个选择的代价,从结果看来,优化器认为直接扫描主键索引更快。当然,从执行时间看来,这个选择并不是最优的。

使用普通索引需要把回表的代价算进去,在图1执行explain的时候,也考虑了这个策略的代价 ,但图1的选择是对的。也就是说,这个策略并没有问题。

MySQL选错索引,这件事儿还得归咎到没能准确地判断出扫描行数。既然是统计信息不对,那就修正。analyze table t 命令,可以用来重新统计索引信息。我们来看一下执行效果。

高性能MySQL之索引深入原理分析

 

从图中看,结果正确了,因此在实践中,如果你发现explain的结果预估的rows值跟实际情况差距比较大,可以采用这个方法来处理。如果只是索引统计不准确,通过analyze命令可以解决很多问题,但是前面我们说了,优化器可不止是看扫描行数。例如下面这个例子,依然是基于表 t,语句如下:

select * from t where (a between 1 and 1000)  and (b between 50000 and 100000) order by b limit 1;

从条件上看,这个查询没有符合条件的记录,因此会返回空集合。在开始执行这条语句之前,你可以先设想一下,如果你来选择索引,会选择哪一个呢?

为了便于分析,我们先来看一下a、b这两个索引的结构图。

高性能MySQL之索引深入原理分析

如果使用索引a进行查询,那么就是扫描索引a的前1000个值,然后取到对应的id,再到主键索引上去查出每一行,然后根据字段b来过滤。显然这样需要扫描1000行。

如果使用索引b进行查询,那么就是扫描索引b的最后50001个值,与上面的执行过程相同,也是需要回到主键索引上取值再判断,所以需要扫描50001行。

所以你一定会想,如果使用索引a的话,执行速度明显会快很多。那么,下面我们就来看看到底是不是这么一回事儿。

高性能MySQL之索引深入原理分析

 

 可以看到,返回结果中key字段显示,这次优化器选择了索引b,而rows字段显示需要扫描的行数是50128。

因此可以得到的结论是:

  1. 扫描行数的估计值依然不准确;

  2. 这个例子里MySQL又选错了索引。

 

十一、索引选择异常与处理

第一种方法是,采用force index强行选择一个索引。MySQL会根据词法解析的结果分析出可能可以使用的索引作为候选项,然后在候选列表中依次判断每个索引需要扫描多少行。如果force index指定的索引在候选索引列表中,就直接选择这个索引,不再评估其他索引的执行代价。例子如下:

高性能MySQL之索引深入原理分析

可以看到,原本语句需要执行2.23秒,而当你使用force index(a)的时候,只用了0.05秒,比优化器的选择快了40多倍。也就是说,优化器没有选择正确的索引,force index起到了“矫正”的作用。

不过很多程序员不喜欢使用force index,一来这么写不优美,二来如果索引改了名字,这个语句也得改,显得很麻烦。而且如果以后迁移到别的数据库的话,这个语法还可能会不兼容。

其实使用force index最主要的问题还是变更的及时性。因为选错索引的情况还是比较少出现的,所以开发的时候通常不会先写上force index。而是等到线上出现问题的时候,你才会再去修改SQL语句、加上force index。但是修改之后还要测试和发布,对于生产系统来说,这个过程不够敏捷。

 

第二种方法就是,我们可以考虑修改语句,引导MySQL使用我们期望的索引。比如,在这个例子里,显然把“order by b limit 1” 改成 “order by b,a limit 1” ,语义的逻辑是相同的。效果如下图所示:

高性能MySQL之索引深入原理分析

之前优化器选择使用索引b,是因为它认为使用索引b可以避免排序(b本身是索引,已经是有序的了,如果选择索引b的话,不需要再做排序,只需要遍历),所以即使扫描行数多,也判定为代价更小。现在order by b,a 这种写法,要求按照b,a排序,就意味着使用这两个索引都需要排序。因此,扫描行数成了影响决策的主要条件,于是此时优化器选了只需要扫描1000行的索引a。

这种修改并不是通用的优化手段,只是刚好在这个语句里面有limit 1,因此如果有满足条件的记录, order by b limit 1和order by b,a limit 1 都会返回b是最小的那一行,逻辑上一致,才可以这么做。

如果你觉得修改语义这件事儿不太好,这里还有一种改法,SQL脚本如下:

mysql> select * from  (select * from t where (a between 1 and 1000)  and (b between 50000 and 100000) order by b limit 100)alias limit 1;

高性能MySQL之索引深入原理分析

在这个例子里,我们用limit 100让优化器意识到,使用b索引代价是很高的。其实是我们根据数据特征诱导了一下优化器,也不具备通用性。

 

第三种方法是,在有些场景下,我们可以新建一个更合适的索引,来提供给优化器做选择,或删掉误用的索引。

 

高性能MySQL之索引深入原理分析

上一篇:Mysql 常用函数(40)- time_to_sec 函数


下一篇:MySQL数据结构-页结构