MySQL Index Merge

时间:2022-05-23 程序员小潘人气:0

1. 前言

先问大家一个问题，在不考虑多表联查这种复杂的查询场景下，一个简单的单表查询，MySQL可以同时利用几个索引？

当初我学习MySQL的时候，天真的以为只要把WHERE条件涉及到的列全部加上索引，就可以提升查询速度，这个想法其实大错特错。因为一般情况下，单表查询MySQL只能利用一个索引，比如下面这个查询，假设id是主键，a和b分别创建了索引，别天真的以为idx_a和idx_b都能发挥作用，其实不是的。

SELECT id,a,b FROM T WHERE a>100 AND b>200;

因为idx_a索引只存储了列a和id的值，无法判断b>200条件是否成立，所以只能拿着id去回表查询。同样idx_b索引只存储了列b和id的值，无法判断a>100条件是否成立，也只能拿着id去回表查询。可以看到，最大的开销其实是回表操作，通过二级索引匹配到的数据越少，回表的开销也就越低。所以理论上来说，a>100和b>200分别符合这两个条件的记录数越少，MySQL就会使用哪个索引。MySQL是如何判断符合这些条件的记录数量的呢？不也得老老实实的扫描全表吗？MySQL采用预估的方式，通过表的统计数据或访问表中少量的数据来进行预估，并分别计算使用这两个索引进行查询各自的成本是多少，最终选择执行成本更低的索引方案。关于MySQL如何预估执行成本，不在本篇文章的讨论范围内，先跳过。

我们假设最终MySQL使用idx_a索引，那么这个查询过程其实是这样的：

InnoDB从idx_aB+树中获取到第一条a>100的记录，拿记录里的id值回表查询。
回表查询获取到完整的用户记录，判断b>200是否成立，成立则返回给客户端，否则丢弃该记录。
InnoDB继续从idx_aB+树中获取到下一条a>100的记录，重复前面的过程。

建立了这么多索引，每次查询只使用一个，太可惜了不是嘛。能不能同时利用多个索引来完成查询呢？可以的，但是条件有些严苛，这就是我们今天要介绍的索引合并Index Merge。

2. Index Merge

MySQL将这种使用多个索引来完成一次查询的执行方法称为索引合并「index merge」。如何才能知道我们写的SQL语句使用了索引合并呢？通过EXPLAIN分析一下就知道了，如果使用了索引合并，对应的type列显示的值应该是index_merge，key列显示用的到所有索引名称，Extra列会显示具体使用了哪种类型的索引合并。如下所示，同时使用了idx_a和idx_b两个索引完成查询，且索引合并类型为Intersection。

table	type	key	Extra
T	index_merge	idx_a,idx_b	Using intersect(idx_a,idx_b); Using where; Using index

什么？索引合并还分类型？是的，MySQL目前共支持三种类型的索引合并，分别是：

索引合并类型	说明
Intersection	对多个二级索引里符合条件的主键值取交集合并
Union	对多个二级索引里符合条件的主键值去重后取并集合并
Sort Union	对多个二级索引里符合条件的主键值去重并排序后，再取并集合并

我们使用一个具体的例子，来分别演示下三种索引合并。假设有表T如下，id是主键，列a和列b分别创建索引。

CREATE TABLE T(
    `id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `a` INT NOT NULL,
    `b` CHAR(1) DEFAULT NULL,
    KEY `idx_a` (a) USING BTREE,
    KEY `idx_b` (b) USING BTREE
)ENGINE=InnoDB AUTO_INCREMENT=1;

大家可以写个存储过程，向表中批量插入记录，我这里贴一下代码，写的很简陋。

CREATE PROCEDURE insertT()
BEGIN
    DECLARE i INT DEFAULT 0;
    START TRANSACTION;
        WHILE i<=10000 do
            INSERT INTO T (a, b) VALUES (i,CHAR(rand()*(90-65)+65));
            SET i=i+1;
        END WHILE;
    COMMIT;
END;
call insertT();

列a和列b均是普通索引，值是允许重复的，大家可以多调用几次存储，最终的数据就是：a的值在一万以内重复，b的值在A~Z之间重复，主键保持递增。下面我们基于这张表的数据来演示。

2.1 Intersection

SELECT * FROM T WHERE a=1 AND b='A';

针对这个查询，目前我们知道它可以有以下三种查询方式：

全表扫描，判断两个条件是否匹配。
利用idx_a索引将获取到id回表查询再判断条件b是否达成。
利用idx_b索引将获取到id回表查询再判断条件a是否达成。

有了Intersection索引合并，MySQL其实还可以有第四种查询方式，查询过程是这样的：

利用idx_a索引将获取到的id集合记作id_setA。
利用idx_b索引将获取到的id集合记作id_setB。
将id_setA和id_setB取交集，记作id_set。
对id_set回表查询，将结果返回给客户端。

这个过程描述的其实是有问题的，但是大概意思是对的，主要是帮助大家理解。对id取交集的过程，并不是这样的，本质上MySQL并不会存储这些id集合，因为数据量一大是很占用内存的，这个我们待会说。

综上所述，这种通过从多个索引中扫描到的记录的主键值取交集后再回表查询的方式，就是Intersection索引合并。EXPLAIN分析结果如下：

mysql> EXPLAIN SELECT * FROM T WHERE a=1 AND b='A';
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+--------------------------------------------------------+
| id | select_type | table | partitions | type        | possible_keys | key         | key_len | ref  | rows | filtered | Extra                                                  |
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+--------------------------------------------------------+
|  1 | SIMPLE      | T     | NULL       | index_merge | idx_a,idx_b   | idx_a,idx_b | 4,4     | NULL |    1 |   100.00 | Using intersect(idx_a,idx_b); Using where; Using index |
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+--------------------------------------------------------+

需要注意的是，使用Intersection索引合并是有条件的。如果使用到的索引都是二级索引的话，则要求通过二级索引取出的记录是按照主键排好序的。为什么会有这个要求呢？主要是有以下两个好处：

对两个有序集合取交集更简单。
主键有序的情况下，回表将不再是单纯的随机IO，回表的效率更高。

很显然，我们这个查询是能利用Intersection索引合并的。idx_a索引中是先根据a排序再根据id排序的，a=1的情况下，取出的记录是按照id排好序的。idx_b索引中是先根据b排序再根据id排序的，b='A'的情况下，取出的记录也是按照id排好序的。所以是符合要求的。

最后，我们看一下MySQL从两个集合中取交集的过程。假设idx_a过滤出的id是[1,3,5]，idx_b过滤出的id集合是[2,3,4]，取交集的过程其实是这样的：

从idx_a取出第一条记录，id值是1。再从idx_b取出第一条记录，id值是2，因为1<2所以id为1的那条记录直接丢弃。
从idx_a取出第二条记录，id值是3，因为2<3，所以id为2的那条记录直接丢弃。
从idx_b取出第二条记录，id值是3，因为3=3，所以拿3去回表查询，结果返回给客户端，同时id为3的两条记录也直接丢弃。
从idx_a取出第三条记录，id值是5。从idx_b取出第三条记录，id值是4。因为4<5所以id为4的记录被丢弃，又因为双方都没有记录了，id为5的记录也被丢弃，交集过程结束。

通过上述过程，现在你应该很清楚为啥MySQL要求二级索引返回的记录必须根据主键排好序了吧，如此一来，整个求交集的过程将变得非常简单，MySQL也无需使用额外的内存空间来保存这些id集合。

2.2 Union

SELECT * FROM T WHERE a=1 OR b='A';

针对这个查询，我们是无法单独使用idx_a或idx_b索引来完成的，因为它们的条件关系是OR，目前我们已知的查询方式就一种：

全表扫描，判断两者条件满足其一就返回给客户端。

这种方式很明显太笨了，有了Union索引合并，MySQL其实可以有第二种查询方式，过程是这样的：

利用idx_a索引将获取到的id集合记作id_setA。
利用idx_b索引将获取到的id集合记作id_setB。
将id_setA和id_setB取并集，记作id_set。
对id_set回表查询，将结果返回给客户端。

这个过程和Intersection其实很像，只是交集换成了并集而已，所以很好理解。同样的，取并集的过程也并非如此，这里只是方便大家理解。

综上所述，这种通过从多个索引中扫描到的记录的主键值取并集后再回表查询的方式，就是Union索引合并。EXPLAIN分析结果如下：

mysql> EXPLAIN SELECT * FROM T WHERE a=1 OR b='A';
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+---------------------------------------+
| id | select_type | table | partitions | type        | possible_keys | key         | key_len | ref  | rows | filtered | Extra                                 |
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+---------------------------------------+
|  1 | SIMPLE      | T     | NULL       | index_merge | idx_a,idx_b   | idx_a,idx_b | 4,4     | NULL | 1016 |   100.00 | Using union(idx_a,idx_b); Using where |
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+---------------------------------------+

同样，使用Union索引合并也是有条件的。如果使用到的索引都是二级索引的话，则要求通过二级索引取出的记录是按照主键排好序的。为什么会有这个要求呢？主要是有以下两个好处：

对两个有序集合取并集更简单。
主键有序的情况下，回表将不再是单纯的随机IO，回表的效率更高。

至于为啥这个查询可以使用Union索引，其实上面已经说过了，这里不再赘述。

Union索引合并取并集的过程，和Intersection也很像。MySQL依然不需要使用额外的内存存储这些id集合，大家可以按照上述流程自己走一遍，这里不再赘述。

2.3 Sort Union

SELECT * FROM T WHERE a=1 OR b>='Z';

针对这个查询，是不能使用Union索引合并的，因为它不满足条件：从idx_b二级索引取出的记录并非是按照主键排序的。所以目前我们已知的查询方式就一种：

全表扫描，判断两者条件满足其一就返回给客户端。

Intersection和Union使用的条件很严苛，必须要求二级索引取出的记录是按照主键排好序的，针对这个查询无法使用。但是这两个条件a=1和b>='Z'很大概率能过滤掉大部分记录，是可以提升查询效率的，怎么办呢？

MySQL很想利用这两个索引，于是想了个办法。既然二级索引自然取出来的主键不是排好序的，那我就先放到内存里自己排好序再使用Union的方式去查询。整个过程是这样的：

先从idx_b索引中取出所有符合条件记录，提取id集合先去重再排序，记作id_setB。
此时id_setB已经是有序的了，从idx_a中依次取出记录的id值，走正常取并集的过程即可。
对最终的id并集回表，将结果返回给客户端。

综上所述，这种通过从多个索引中扫描到的记录的主键值排好序后，再按照Union索引合并的方式执行查询的方式，就是Sort Union索引合并。相较于Union，其实就是多了一个对主键手动排序的过程。EXPLAIN分析结果如下：

mysql> EXPLAIN SELECT * FROM T WHERE a=1 OR b>='Z';
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table | partitions | type        | possible_keys | key         | key_len | ref  | rows | filtered | Extra                                      |
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+--------------------------------------------+
|  1 | SIMPLE      | T     | NULL       | index_merge | idx_a,idx_b   | idx_a,idx_b | 4,4     | NULL |  975 |   100.00 | Using sort_union(idx_a,idx_b); Using where |
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+--------------------------------------------+

2.4 Sort Intersection

很遗憾，目前MySQL并不支持所谓的“Sort Intersection”索引合并的方式。大家肯定很好奇，既然有Sort Union，为啥没有Sort Intersection呢？不就是先手动排序再取交集吗？

没有查找到相关资料解释为啥不支持，我可以说下我的理解。大家可以想一下，交集的本质是什么？一般情况下是将两个很大的集合，变成一个较小的集合。而并集的本质又是什么呢？一般情况下是将两个较小的集合，变成一个较大的集合。

大家明白了吗？对两个较小的集合在内存中排序，开销可以接受。但是对两个较大的集合在内存中完成排序，这个操作本身的开销可能比回表的开销都大了，那MySQL还不如只利用「单索引+回表」的方式查询呢。

3. 总结

不要天真的给WHERE条件涉及到的列都加上索引，通常情况下这只会让结果更糟。因为一般情况下，对于单表查询MySQL一次只能利用一个索引。但是，如果条件允许，MySQL也可以利用「Index Merge」的方式利用多个索引完成一次查询。MySQL支持三种索引合并的方式，分别是Intersection、Union、Sort Union，其实就是利用二级索引中的主键值取交集、并集后再回表查询。其中Intersection和Union使用条件比较严苛，要求从二级索引取出的记录必须是根据主键排好序的。有时候条件不满足，但是MySQL又很想使用Index Merge，就会尝试自己在内存中手动排序，这就是Sort Union，它只比Union多了个手动排序的过程。至于为啥没有Sort Intersection，作者说了一点自己的思考，不一定对，大家也可以思考一下。

加载全部内容