MySQL查询优化：Index Merge

一、为什么会有Index Merge？

Index Merge 访问方法检索具有多个 range 扫描的行并将它们的结果合并为一个。这里的 range 就是 explain 中的 type: range。此访问方法简单来说就是对单个表的多个索引分别进行条件扫描，然后将它们各自的结果进行集合运算（Intersect/Union）。

MySQL 5.0之前，一个表一次只能使用一个索引，无法同时使用多个索引分别进行条件扫描。但是从5.1开始，引入了Index Merge优化技术，对同一个表可以使用多个索引分别进行条件扫描。

什么情况下，同时使用多个索引会有利呢？比如说WHERE条件是“C1=10 AND C2 =100”，但是只有分别针对C1和C2的索引，而没有(C1,C2)这种索引，两个索引同时使用才有意义，通过两个索引都可以快速定位到一批数据，然后对这一批数据进行进一步的求交或求和操作即可，这样的效率可能比全表扫描或者只使用其中一个索引进行扫描然后再去主索引查询要快，但也不是绝对的，后面会细说。

索引合并优化算法具有以下已知限制：

如果我们的条件比较复杂，用到多个 and/or 条件运算，而MySQL没有使用最优的执行计划，那么可以使用下面的两个等式将条件进行转换一下。

(x AND y) OR z = (x OR z) AND (y OR z)

(x OR y) AND z = (x AND z) OR (y AND z)

索引合并不适用于全文索引。

在EXPLAIN输出中，索引合并方法在Type列中显示为index_merge。在这种情况下，key列包含使用的索引列表，key_len包含这些索引的最长 key 部分列表。

Index Merge方法根据合并算法的不同分成了三种：Intersect，Union，Sort_union。

Using intersect(...)
Using union(...)
Using sort_union(...)

它们显示在EXPLAIN输出的Extra字段中。Intersect和Union都需要使用的索引是ROR的，也就是Rowid Ordered Retrieval，即针对不同的索引扫描出来的数据必须是同时按照ROWID排序的，这里的ROWID其实也就是InnoDB的主键（如果不定义主键，InnoDB会隐式添加ROWID列作为主键）。只有每个索引是ROR的，才能进行归并排序，你懂的。当然你可能会有疑惑，查记录后内部进行一次sort不一样么，何必必须要ROR呢，不错，所以有了Sort-union。Sort-union就是对每个非ROR的索引排序后再进行Merge。MySQL至于为什么没有Sort-Intersect，后面说明，但是MariaDB从5.3版本就支持了Sort-Intersect。

以下部分更详细地描述了这些算法，优化器根据各种可用选项的成本估算在不同的索引合并算法和其他访问方法之间进行选择。

二、Index Merge算法

索引合并交集访问算法（Index Merge Intersection Access Algorithm）

简单而言，Index Merge Intersect就是多个索引条件扫描得到的结果进行交集运算。显然在多个索引条件之间是 AND 运算时，才会出现Index Merge Intersect。下面两种where条件或者它们组合时会进行Index Merge Intersect。

情况一：二级索引列是等值匹配的情况，对于联合索引来说，在联合索引中的每个列都必须等值匹配，不能出现只出现匹配部分列的情况

key_part1 = key_part1 = const1 ... AND key_partN = constN

1	key_part1 = key_part1 = const1 ... AND key_partN = constN

情况二：主键上的任何范围条件

SELECT * FROM innodb_table
  WHERE primary_key < 10 AND key_col1 = 20;

SELECT * FROM tbl_name
  WHERE (key1_part1 = 1 AND key1_part2 = 2) AND key2 = 2;

SELECT * FROM innodb_table

WHERE primary_key < 10 AND key_col1 = 20;

SELECT * FROM tbl_name

WHERE (key1_part1 = 1 AND key1_part2 = 2) AND key2 = 2;

为啥有这两个规定呢？这话还得从InnoDB的索引结构说起。对于InnoDB的二级索引来说，记录先是按照索引列进行排序，如果该二级索引是一个联合索引，那么会按照联合索引中的各个列依次排序。而二级索引的记录是由索引列 + 主键构成的，二级索引列的值相同的记录可能会有好多条，这些索引列的值相同的记录又是按照主键的值进行排序的。所以重点来了，之所以在二级索引列都是等值匹配的情况下才可能使用Intersection索引合并，是因为只有在这种情况下根据二级索引查询出的结果集是按照主键值排序的。如果从各个二级索引中查询的到的结果集本身就是已经按照主键排好序的，那么求交集的过程就很容易了。

那么求交集的过程就是这样：逐个取出这两个结果集中最小的主键值，如果两个值相等，则加入最后的交集结果中，否则丢弃当前较小的主键值，再取该丢弃的主键值所在结果集的后一个主键值来比较，直到某个结果集中的主键值用完了。

对于单字段二级索引进行Index Merge Intersect处理，比如下面的查询：

select * from tab where key1=xxx and key2=xxx

1	select * from tab where key1=xxx and key2=xxx

那这个过程就是下面这样的：

A. 从key1二级索引对应的B+树中取出key1 = xxx的相关记录。

B. 从key2二级索引对应的B+树中取出key2 = xxx的相关记录。

C. 二级索引的记录都是由索引列 + 主键构成的，所以我们可以计算出这两个结果集中ROWID（主键）值的交集。

D. 按照上一步生成的ROWID值列表进行回表操作，也就是从聚簇索引中把指定ROWID值的完整用户记录取出来，返回给用户。

交集计算方式：

比如，从key1中获取到已经排好序的主键值：1、3、5；从key2中获取到已经排好序的主键值：2、3、4。

A. 先取出这两个结果集中较小的主键值做比较，因为1 < 2，所以把idx_key1的结果集的主键值1丢弃，取出后边的3来比较。

B. 因为3 > 2，所以把idx_key2的结果集的主键值2丢弃，取出后边的3来比较。

C. 因为3 = 3，所以把3加入到最后的交集结果中，继续两个结果集后边的主键值来比较。

D. 后边的主键值也不相等，所以最后的交集结果中只包含主键值3。

这个过程非常快，时间复杂度是O(n)，但是如果从各个二级索引中查询出的结果集并不是按照主键排序的话，那就要先把结果集中的主键值排序完再来做上边的那个过程，就比较耗时了。

另外，不仅是多个二级索引之间可以采用Intersection索引合并，索引合并也可以有聚簇索引参加，也就是我们上边写的情况二：在搜索条件中有主键的范围匹配的情况下也可以使用Intersection索引合并索引合并。为啥主键这就可以范围匹配了？还是得回到应用场景里，比如看下边这个查询：

select * from tab where id>100 and key1=xxx

1	select * from tab where id>100 and key1=xxx

假设这个查询可以采用Intersection索引合并，我们理所当然的以为这个查询会分别按照 id>100 这个条件从聚簇索引中获取一些记录，在通过key1 = xxx这个条件从key1二级索引中获取一些记录，然后再求交集，其实这样就把问题复杂化了，没必要从聚簇索引中获取一次记录。别忘了二级索引的记录中都带有主键值的，所以可以在从key1中获取到的主键值上直接运用条件 id>100 过滤就行了，这样多简单。所以涉及主键的搜索条件只不过是为了从别的二级索引得到的结果集中过滤记录罢了，是不是等值匹配不重要。

当然，上边说的情况一和情况二只是发生Intersection索引合并的必要条件，不是充分条件。也就是说即使情况一、情况二成立，也不一定发生Intersection索引合并，这得看优化器了。比如，等值查询条件下（也就是情况一）优化器也可以直接使用key1或者key2只根据某个搜索条件去读取一个二级索引，然后回表后再过滤另外一个搜索条件。具体使用哪种方案，这里要分析一下两种查询执行方式之间需要的成本代价，这个要靠优化器根据成本估算的。

虽然读取多个二级索引比读取一个二级索引消耗性能，但是读取二级索引的操作是顺序I/O，而回表操作是随机I/O，所以如果只读取一个二级索引时需要回表的记录数特别多，而读取多个二级索引之后取交集的记录数非常少，当节省的因为回表而造成的性能损耗比访问多个二级索引带来的性能损耗更高时，读取多个二级索引后取交集比只读取一个二级索引的成本更低。反之亦然。

索引合并并集访问算法（Index Merge Union Access Algorithm）

简单而言，Index Merge Union就是多个索引条件扫描，对得到的结果进行并集运算，显然是多个条件之间进行的是 OR 运算。

下面几种类型的 where 条件，以及他们的组合可能会使用到Index Merge Union算法。

情况一：二级索引列是等值匹配的情况，对于联合索引来说，在联合索引中的每个列都必须等值匹配，不能出现只出现匹配部分列的情况

情况二：主键上的任何范围条件

情况三：任何符合Index Merge Intersect的where条件

上面三种 where 条件进行 OR 运算时，可能会使用 Index Merge Union 算法。比如下面的例子：

SELECT * FROM t1
  WHERE key1 = 1 OR key2 = 2 OR key3 = 3;

SELECT * FROM innodb_table
  WHERE (key1 = 1 AND key2 = 2)
     OR (key3 = 'foo' AND key4 = 'bar') AND key5 = 5;

SELECT * FROM t1

WHERE key1 = 1 OR key2 = 2 OR key3 = 3;

SELECT * FROM innodb_table

WHERE (key1 = 1 AND key2 = 2)

OR (key3 = 'foo' AND key4 = 'bar') AND key5 = 5;

第一个例子，就是三个单字段索引进行 OR 运算，所以他们可能会使用Index Merge Union算法。

第二个例子，复杂一点，它就符合“情况三”，就是搜索条件的某些部分使用Intersection索引合并的方式得到的主键集合和其他方式得到的主键集合取交集。其中 (key1=1 AND key2=2) 是符合Index Merge Intersect。 (key3=’foo’ AND key4=’bar’) AND key5=5也是符合Index Merge Intersect，所以二者之间进行 OR 运算，自然可能会使用Index Merge Union算法。

优化器可能采用这样的方式来执行这个查询：

先按照搜索条件key1 = 1 AND key2 = 2从索引key1和key2中使用Intersection索引合并的方式得到一个主键集合。
再按照搜索条件key3 = ‘foo’ AND key4 = ‘bar’ AND key5 = 5从索引key3和key4和key5中得到另一个主键集合。
采用Union索引合并的方式把上述两个主键集合取并集，然后进行回表操作，将结果返回给用户。

但下面这个例子就无法使用Index Merge Union：

SELECT * FROM t1
  WHERE key1 > 1 OR key2 = 2;

1 2	SELECT * FROM t1 WHERE key1 > 1 OR key2 = 2;

主要是因为对key1进行了范围匹配，Union索引合并不支持非主键范围查询，主要还是因为范围查询得到的主键是无序的。

索引合并排序并集访问算法（Index Merge Sort-Union Access Algorithm）

Index Merge Union索引合并的使用条件太苛刻，必须保证各个二级索引列在进行等值匹配的条件下才可能被用到，比方说下边两个官方文档给出的例子就无法使用到Union索引合并：

SELECT * FROM tbl_name
  WHERE key_col1 < 10 OR key_col2 < 20;

SELECT * FROM tbl_name
  WHERE (key_col1 > 10 OR key_col2 = 20) AND nonkey_col = 30;

SELECT * FROM tbl_name

WHERE key_col1 < 10 OR key_col2 < 20;

SELECT * FROM tbl_name

WHERE (key_col1 > 10 OR key_col2 = 20) AND nonkey_col = 30;

我们就说第一个例子，这是因为根据key_col1 < 10从key_col1索引中获取的二级索引记录的主键值不是排好序的，根据key_col2 < 20从key_col2索引中获取的二级索引记录的主键值也不是排好序的，但是key_col1 < 10和key_col2 < 20这两个条件又特别让我们动心，所以我们可以这样：

先根据key_col1 < 10条件从key_col1二级索引总获取记录，并按照记录的主键值进行排序
再根据key_col2 < 20条件从key_col2二级索引总获取记录，并按照记录的主键值进行排序
因为上述的两个二级索引主键值都是排好序的，剩下的操作和Union索引合并方式就一样了

我们把上述这种先按照二级索引记录的主键值进行排序，之后按照Union索引合并方式执行的方式称之为Sort-Union索引合并，很显然，这种Sort-Union索引合并比单纯的Union索引合并多了一步对二级索引记录的主键值排序的过程。

NOTE

为啥有Sort-Union索引合并，就没有Sort-Intersection索引合并么？是的，MySQL的确没有Sort-Intersection索引合并这么一说， Sort-Union的适用场景是单独根据搜索条件从某个二级索引中获取的记录数比较少（少的结论是：在使用or条件时，如果使用两个索引获取的记录多时，排序成本和回表成本就会很大，所以可能选择直接扫表，也就不需要Sort-intersection索引合并了），这样即使对这些二级索引记录按照主键值进行排序的成本也不会太高。而Intersection索引合并的适用场景是单独根据搜索条件从某个二级索引中获取的记录数太多（多的结论是：使用and条件时，如果使用某个索引已经可以返回非常少的记录了，那就没必要再去使用另一个索引了，也就不需要Intersection索引合并了），导致回表开销太大，合并后可以明显降低回表开销，但是如果加入Sort-Intersection后，就需要为大量的二级索引记录按照主键值进行排序，这个成本可能比回表查询都高了，所以也就没有引入Sort-Intersection这个玩意儿。

三、对Index Merge的进一步优化

Index Merge使得我们可以使用到多个索引同时进行扫描，然后将结果进行合并。听起来好像是很好的功能，但是如果出现了Index Merge Intersect，那么一般同时也意味着我们的索引建立得不太合理，因为Index Merge Intersect是可以通过建立复合索引进行更一步优化的。

比如下面的查询：

SELECT * FROM t1 WHERE key1=1 AND key2=2 AND key3=3;

1	SELECT * FROM t1 WHERE key1=1 AND key2=2 AND key3=3;

显然我们是可以在这三个字段上建立一个复合索引来进行优化的，这样就只需要扫描一个索引一次，而不是对三个所以分别扫描一次。

Percona官网有一篇比较复合索引和Index Merge的好文章：Multi Column indexes vs Index Merge

四、生产案例

对于TicketINF表大概有一百多万数据左右，结合上面的学习来看看索引合并到底如何工作。下面先从一个简单的 OR 查询开始。

mysql> explain SELECT * FROM TicketINF WHERE memberSysId = 'tb.main' OR memberId = '123456';
+------+-------------+-----------+-------------+----------------------------------------------+----------------------------------------------+---------+------+------+-----------------------------------------------------------------------------+
| id   | select_type | table     | type        | possible_keys                                | key                                          | key_len | ref  | rows | Extra                                                                       |
+------+-------------+-----------+-------------+----------------------------------------------+----------------------------------------------+---------+------+------+-----------------------------------------------------------------------------+
|    1 | SIMPLE      | TicketINF | index_merge | idx_memberSysId_memberSysUserId,idx_memberId | idx_memberSysId_memberSysUserId,idx_memberId | 153,303 | NULL | 7449 | Using sort_union(idx_memberSysId_memberSysUserId,idx_memberId); Using where |
+------+-------------+-----------+-------------+----------------------------------------------+----------------------------------------------+---------+------+------+-----------------------------------------------------------------------------+
1 row in set (0.01 sec)

mysql> explain SELECT * FROM TicketINF WHERE memberSysId = 'tb.main' OR memberId = '123456';

+------+-------------+-----------+-------------+----------------------------------------------+----------------------------------------------+---------+------+------+-----------------------------------------------------------------------------+

1 row in set (0.01 sec)

根据执行计划看出，两个字段都使用到了索引（两个普通索引，memberSysId字段是组合索引的第一个字段，memberId是一个普通索引），使用了索引合并技术，且使用的是sort-union合并算法。

根据我们上面说的，如果查询字段是复合索引的第二个字段，那么是无法使用到索引的，如下执行计划。

mysql> explain SELECT * FROM TicketINF WHERE memberSysUserId = '456789' OR memberId = '123456'; 
+------+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
| id   | select_type | table     | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+------+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
|    1 | SIMPLE      | TicketINF | ALL  | idx_memberId  | NULL | NULL    | NULL | 850450 | Using where |
+------+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
1 row in set (0.00 sec)

mysql> explain SELECT * FROM TicketINF WHERE memberSysUserId = '456789' OR memberId = '123456';

+------+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

+------+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

+------+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

1 row in set (0.00 sec)

然后对上一个查询再加上一个 AND 运算。

mysql> explain SELECT * FROM TicketINF WHERE (memberSysId = 'tb.main' AND memberSysUserId = '123456') OR memberId = '123456';
+------+-------------+-----------+-------------+----------------------------------------------+----------------------------------------------+---------+------+------+------------------------------------------------------------------------+
| id   | select_type | table     | type        | possible_keys                                | key                                          | key_len | ref  | rows | Extra                                                                  |
+------+-------------+-----------+-------------+----------------------------------------------+----------------------------------------------+---------+------+------+------------------------------------------------------------------------+
|    1 | SIMPLE      | TicketINF | index_merge | idx_memberSysId_memberSysUserId,idx_memberId | idx_memberSysId_memberSysUserId,idx_memberId | 456,303 | NULL |    2 | Using union(idx_memberSysId_memberSysUserId,idx_memberId); Using where |
+------+-------------+-----------+-------------+----------------------------------------------+----------------------------------------------+---------+------+------+------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> explain SELECT * FROM TicketINF WHERE (memberSysId = 'tb.main' AND memberSysUserId = '123456') OR memberId = '123456';

1 row in set (0.00 sec)

从执行计划来看，同样使用到了索引合并，但这回使用的合并算法是union。

再往下，我们再次添加一个 OR 运算，增加一个mobile字段的检索。

mysql> explain SELECT * FROM TicketINF WHERE (memberSysId = 'tb.main' AND memberSysUserId = '123456') OR memberId = '123456' OR mobile = '12100001111';
+------+-------------+-----------+------+----------------------------------------------+------+---------+------+--------+-------------+
| id   | select_type | table     | type | possible_keys                                | key  | key_len | ref  | rows   | Extra       |
+------+-------------+-----------+------+----------------------------------------------+------+---------+------+--------+-------------+
|    1 | SIMPLE      | TicketINF | ALL  | idx_memberSysId_memberSysUserId,idx_memberId | NULL | NULL    | NULL | 850385 | Using where |
+------+-------------+-----------+------+----------------------------------------------+------+---------+------+--------+-------------+
1 row in set (0.00 sec)

mysql> explain SELECT * FROM TicketINF WHERE (memberSysId = 'tb.main' AND memberSysUserId = '123456') OR memberId = '123456' OR mobile = '12100001111';

+------+-------------+-----------+------+----------------------------------------------+------+---------+------+--------+-------------+

+------+-------------+-----------+------+----------------------------------------------+------+---------+------+--------+-------------+

+------+-------------+-----------+------+----------------------------------------------+------+---------+------+--------+-------------+

1 row in set (0.00 sec)

从执行计划上看，走了全表扫描，一个索引也没有用上，更没有用上索引合并。此条SQL在此表执行时间为2s左右，导致慢查询过多，服务器负载到了200。

此时，我们再给mobile字段增加一个普通索引，再次看执行计划，如下。

mysql> explain SELECT * FROM TicketINF WHERE  (memberSysId = 'tb.main' AND memberSysUserId = '123456') OR memberId = '123456' OR mobile = '12100001111';
+------+-------------+-----------+-------------+---------------------------------------------------------+---------------------------------------------------------+-------------+------+------+-----------------------------------------------------------------------------------+
| id   | select_type | table     | type        | possible_keys                                           | key                                                     | key_len     | ref  | rows | Extra                                                                             |
+------+-------------+-----------+-------------+---------------------------------------------------------+---------------------------------------------------------+-------------+------+------+-----------------------------------------------------------------------------------+
|    1 | SIMPLE      | TicketINF | index_merge | idx_memberSysId_memberSysUserId,idx_memberId,idx_mobile | idx_memberSysId_memberSysUserId,idx_memberId,idx_mobile | 456,303,153 | NULL |    3 | Using union(idx_memberSysId_memberSysUserId,idx_memberId,idx_mobile); Using where |
+------+-------------+-----------+-------------+---------------------------------------------------------+---------------------------------------------------------+-------------+------+------+-----------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> explain SELECT * FROM TicketINF WHERE (memberSysId = 'tb.main' AND memberSysUserId = '123456') OR memberId = '123456' OR mobile = '12100001111';

+------+-------------+-----------+-------------+---------------------------------------------------------+---------------------------------------------------------+-------------+------+------+-----------------------------------------------------------------------------------+