MySQL优化之Index Merge

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索引，那么这个查询过程其实是这样的：

1. InnoDB 从idx_aB+树中获取到第一条a>100的记录，拿记录里的 id 值回表查询。
2. 回表查询获取到完整的用户记录，判断b>200是否成立，成立则返回给客户端，否则丢弃该记录。
3. 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。

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

我们使用一个具体的例子，来分别演示下三种索引合并。假设有表 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';

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

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

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

1. 利用idx_a索引将获取到的 id 集合记作id_setA。
2. 利用idx_b索引将获取到的 id 集合记作id_setB。
3. 将id_setA和id_setB取交集，记作id_set。
4. 对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]，取交集的过程其实是这样的：

1. 从idx_a取出第一条记录，id 值是 1。再从idx_b取出第一条记录，id 值是 2，因为1<2所以 id 为 1 的那条记录直接丢弃。
2. 从idx_a取出第二条记录，id 值是 3，因为2<3，所以 id 为 2 的那条记录直接丢弃。
3. 从idx_b取出第二条记录，id 值是 3，因为3=3，所以拿 3 去回表查询，结果返回给客户端，同时 id 为 3 的两条记录也直接丢弃。
4. 从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，目前我们已知的查询方式就一种：

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

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

1. 利用idx_a索引将获取到的 id 集合记作id_setA。
2. 利用idx_b索引将获取到的 id 集合记作id_setB。
3. 将id_setA和id_setB取并集，记作id_set。
4. 对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二级索引取出的记录并非是按照主键排序的。所以目前我们已知的查询方式就一种：

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

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

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

1. 先从idx_b索引中取出所有符合条件记录，提取 id 集合先去重再排序，记作id_setB。
2. 此时id_setB已经是有序的了，从idx_a中依次取出记录的 id 值，走正常取并集的过程即可。
3. 对最终的 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，作者说了一点自己的思考，不一定对，大家也可以思考一下。