索引合并

索引合并访问方法可以在查询中对一个表使用多个索引,对它们同时扫描，并且合并结果(intersect/union)。此访问方法合并来自单个表的索引扫描; 它不会将扫描合并到多个表中。

使用索引合并的示例查询：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


SELECT * FROM tbl_name WHERE key1 = 10 OR key2 = 20;

SELECT * FROM tbl_name
  WHERE (key1 = 10 OR key2 = 20) AND non_key = 30;

SELECT * FROM t1, t2
  WHERE (t1.key1 IN (1,2) OR t1.key2 LIKE 'value%')
  AND t2.key1 = t1.some_col;

SELECT * FROM t1, t2
  WHERE t1.key1 = 1
  AND (t2.key1 = t1.some_col OR t2.key2 = t1.some_col2);

解释：

对于第一条语句：使用索引合并并集访问算法，得到key1=10的主键有序集合，得到key2=20的主键有序集合，再进行求并集；最后回表
对于第二条语句：先丢弃non_key=30,因为它使用不到索引，where语句就变成了where key10 or key2=20,使用索引先根据索引合并并集访问算法
对于第三条语句：索引合并并集访问算法求出(t1.key1 IN (1,2) OR t1.key2 LIKE ‘value%’；然后是join操作

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

注意事项：

索引合并优化算法有以下已知的缺陷：

如果您的查询具有深度AND或OR嵌套的复杂WHERE子句，并且MySQL不选择最佳计划，请尝试使用以下标识转换来分配条件：
1 2

(x AND y) OR z => (x OR z) AND (y OR z) (x OR y) AND z => (x AND z) OR (y AND z)
索引合并(Index Merge)不适应与全文索引(full-text indexes)
如果某个键上的范围扫描是可能的，则优化器将不考虑使用Index Merge Union或Index Merge Sort-Union算法。例如，考虑这个查询：
1

SELECT * FROM t1 WHERE (goodkey1 < 10 OR goodkey2 < 20) AND badkey < 30;
对于这个查询，有两种处理方案：
- 索引合并(Index Merge)使用条件(goodkey1 < 10 OR goodkey2 < 20)
- 范围扫描(range scan)使用条件 badkey < 30
但是，优化器只考虑第二种方案。

索引合并(Index Merge)访问方法有几种算法，这些算法显示在EXPLAIN输出的Extra字段中：

Using intersect(…)
Using union(…)
Using sort_union(…)

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

索引合并(Index Merge)的使用取决于optimizer_switch系统变量的index_merge，index_merge_intersection，index_merge_union和index_merge_sort_union标志的值。默认情况下，所有这些标志都打开。要仅启用特定算法，请将index_merge设置为关闭，并仅启用其他应允许的其他算法。

索引合并交集访问算法(The Index Merge Intersection Access Algorithm)

它的工作流程是：对于每一个使用到的索引进行查询，查询主键值集合，然后进行合并，求交集，也就是and运算。下面是使用到该算法的两种必要条件：

二级索引是等值查询；如果是组合索引，组合索引的每一位都必须覆盖到，不能只是部分.
1

key_part1 = const1 AND key_part2 = const2 ... AND key_partN = constN
主键上的任何范围条件

例如：

1
2
3
4
5
6
7


-- 主键可以是范围查询，二级索引只能是等值查询
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;

会有这两条条件的原因：

它是会根据不同的索引条件查询出主键集合，然后进行归并（并集）
当二级索引的值相同时，其叶子节点上的数据也是根据主键排序的
如果存在主键和二级索引同时存在的情况，主键不是用来查询数据的，而是用来过滤数据。
针对一个必要条件：如果二级索引上的条件是范围条件，那么得到的数据就没有按照主键顺序排序，合并之前需要排序。（根据求并集的算法）。
针对组合索引：同理，组合索引也必须满足等值（即所有部分都等值查询）
针对主键：主键可以是范围查询而不是等值查询，是因为主键就是根据主键值排好序的

求交集的算法：

针对两个升序排序的数组，进行归并：逐个取出两个数组中的最小的值，如果相等，就放入结果集，否则将较小的数指针向后移动。时间复杂度O（N）

索引合并并集访问算法(The Index Merge Union Access Algorithm)

该算法的标准与索引合并交集访问算法相似。当将表的WHERE子句转换由OR组合的不同键上的几个范围条件时，该算法是适用的，必要条件是:

二级索引是等值查询；如果是组合索引，组合索引的每一位都必须覆盖到，不能只是部分：
1

key_part1 = const1 AND key_part2 = const2 ... AND key_partN = constN
InnoDB表上的主键是范围查询条件。
任何符合索引合并交集的where条件

例如：

1
2
3
4
5
6
7
8


-- 无主键，or 连接
SELECT * FROM t1
  WHERE key1 = 1 OR key2 = 2 OR key3 = 3;

-- 既有and 也有or
SELECT * FROM innodb_table
  WHERE (key1 = 1 AND key2 = 2)
     OR (key3 = 'foo' AND key4 = 'bar') AND key5 = 5;

第一个例子中：就是简单的求并集

第二个例子中：现根据key1 = 1 AND key2 = 2和key3 = 'foo' AND key4 = 'bar'使用了两次index merge interset 得到两个主键集合进行合并；然后再根据key5=5得到主键集合，然后进行两个主键集合的合并；然后根据有序的主键序列进行回表。

求并集的算法：

两个有序的升序数组，从两个数组中取出最小的数，然后比较，如果相等并且等于目前最小值，就放入结果集中，向后移动两个指针；否则，将小的数添加到结果集中。

索引合并排序并集访问算法(The Index Merge Sort-Union Access Algorithm)

从上可以看到使用 index merge union 算法的条件太苛刻，更多的时候，会对二级索引适用范围查询而不是等值查询。因此出现了新的算法。

必要条件:

二级索引不必等值查询，联合索引也不必匹配所有的索引项

执行流程:

根据索引查询得到主键集合，对于每个主键集合进行排序，然后求并集。

这样做的好处是扩展了使用条件，增加了使用的范围；缺点就是消耗更大了。

例如：

1
2
3
4
5


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;

验证

通过实践验证上述分析是否正确。

先创建一个一个表，包含主键，联合索引，单列索引，然后插入10000行数据。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


create table t2(id int primary key, a int not null, b int not null,c int not null, d int not null,f int not null ,index idx_abc(a,b,c), index idx_d(d),index idx_f(f));

DELIMITER $$
CREATE PROCEDURE t2_copy()
BEGIN
SET @i=1;
WHILE @i<=10000 DO
INSERT INTO t2 VALUES(@i,@i,@i,@i,@i,@i);
SET @i=@i+1;
END WHILE;
END $$
DELIMITER ;

call tw_copy;

复现 intersect

执行sql语句：

1
2
3
4
5
6


mysql> explain select * from t2 where id>1000 and f=1000;
+----+-------------+-------+------------+-------------+---------------+---------------+---------+------+------+----------+---------------------------------------------+
| id | select_type | table | partitions | type        | possible_keys | key           | key_len | ref  | rows | filtered | Extra                                       |
+----+-------------+-------+------------+-------------+---------------+---------------+---------+------+------+----------+---------------------------------------------+
|  1 | SIMPLE      | t2    | NULL       | index_merge | PRIMARY,idx_f | idx_f,PRIMARY | 8,4     | NULL |    1 |   100.00 | Using intersect(idx_f,PRIMARY); Using where |
+----+-------------+-------+------------+-------------+---------------+---------------+---------+------+------+----------+---------------------------------------------+

type列是index_merge,extra列是using intersect。

分析：使用了主键范围查找，二级索引等值查询

复现因为组合索引没有完全覆盖而导致没有使用intersect

sql语句：

1
2
3
4
5
6
7


mysql> explain select * from t2 where id>1000 and a=1000;
+----+-------------+-------+------------+------+-----------------+---------+---------+-------+------+----------+-----------------------+
| id | select_type | table | partitions | type | possible_keys   | key     | key_len | ref   | rows | filtered | Extra                 |
+----+-------------+-------+------------+------+-----------------+---------+---------+-------+------+----------+-----------------------+
|  1 | SIMPLE      | t2    | NULL       | ref  | PRIMARY,idx_abc | idx_abc | 4       | const |    1 |    49.99 | Using index condition |
+----+-------------+-------+------------+------+-----------------+---------+---------+-------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

复现因为二级索引不是等值查询而导致没有使用intersect

sql语句：

1
2
3
4
5
6


mysql> explain select * from t2 where id>1000 and d<1000;
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | t2    | NULL       | range | PRIMARY,idx_d | PRIMARY | 4       | NULL | 4973 |    10.04 | Using where |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------------+

复现 union

执行sql语句

1
2
3
4
5
6
7


mysql> explain select * from t2 where f=1000 or d=1000;

+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+---------------------------------------+
| id | select_type | table | partitions | type        | possible_keys | key         | key_len | ref  | rows | filtered | Extra                                 |
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+---------------------------------------+
|  1 | SIMPLE      | t2    | NULL       | index_merge | idx_d,idx_f   | idx_f,idx_d | 4,4     | NULL |    2 |   100.00 | Using union(idx_f,idx_d); Using where |
+----+-------------+-------+------------+-------------+---------------+-------------+---------+------+------+----------+---------------------------------------+

复现 sort-union

可以看见tpye 是index_merge ,并且extra里实现using union(idx_f,idx_d)，也就是使用了 index merge union access algorithm。

分析sql语句：使用了二级索引等值查询。

再执行sql 语句：

1
2
3
4
5
6


mysql> explain select * from t2 where id >1000 or a=2;
+----+-------------+-------+------------+-------------+-----------------+-----------------+---------+------+------+----------+------------------------------------------------+
| id | select_type | table | partitions | type        | possible_keys   | key             | key_len | ref  | rows | filtered | Extra                                          |
+----+-------------+-------+------------+-------------+-----------------+-----------------+---------+------+------+----------+------------------------------------------------+
|  1 | SIMPLE      | t2    | NULL       | index_merge | PRIMARY,idx_abc | idx_abc,PRIMARY | 4,4     | NULL | 4974 |   100.00 | Using sort_union(idx_abc,PRIMARY); Using where |
+----+-------------+-------+------------+-------------+-----------------+-----------------+---------+------+------+----------+------------------------------------------------+

type是index_merge, extra 是using sort_union(idx_abc,primary),使用了 index merge sort-union access algorithm算法。

分析sql 语句：使用了组合索引，但是没有使用联合索引中的所有项，使用了主键范围查询。

死锁

mysql innodb引擎使用索引来实现行级别的锁，以下描述一下死锁发生的场景。

业务上需要更新排序值，采用事务来更新，而且更新前为i_sort_id添加了redis锁，但仍然有死锁的情况发生

事务A更新：

1
2


update * where i_sort_id=1 and brand_id=1
update * where i_sort_id=1 and brand_id=2

事务B更新：

1
2


update * where i_sort_id=2 and brand_id=2
update * where i_sort_id=2 and brand_id=1

由于更新使用了2个索引，idx_brand_id是造成死锁的关键。事务A更新了brand_id=1，但发现brand_id=2被事务B锁定，事务B发现brand_id=1被事务A锁定。2个事务均无法执行。

解决方案：

其实也很简单，为i_sort_id和brand_id建立复合索引即可。这个问题是由于索引建立不合理导致的，同时也没有考虑到index merge的影响。

性能问题及替代方案

该新特性可以在一些场景中大幅度提升查询性能，但受限于MySQL糟糕的统计信息，也导致很多场景查询性能极差甚至导致数据库崩溃。

以SELECT * FROM TB1 WHERE c1="xxx" AND c2=""xxx" 为例：

当c1列和c2列选择性较高时，按照c1和c2条件进行查询性能较高且返回数据集较小，再对两个数据量较小的数据集求交集的操作成本也较低，最终整个语句查询高效；
当c1列或c2列选择性较差且统计信息不准时，比如整表数据量2000万，按照c2列条件返回1500万数据，按照c1列返回1000条数据，此时按照c2列条件进行索引扫描+聚集索引查找的操作成本极高(可能是整表扫描的百倍消耗)，对1000条数据和1500万数据求交集的成本也极高，最终导致整条SQL需要消耗大量CPU和IO资源且相应时间超长，而如果值使用c1列的索引，查询消耗资源较少且性能较高。

替代方案

最近系统中发现SQL执行异常，SQL类似为:

1
2
3
4
5


SELECT *
FROM tb_xxxx_xxxx
WHERE yn=0
AND C1=‘123456789’
OR C2=‘123456789’;

表上C1和C2列分别建有索引，但OR条件导致仅扫描任何一个索引都无法得到满足条件的全部数据，需要同时扫描两个索引并对两个临时结果求并集，但由于我们关闭了Index merge特性，导致执行优化器只能对表进行全表扫描并导致执行性能不佳。

该问题的临时解决办法为开启Index merge特性，但存在未知风险，因此我们建议修改SQL，将OR操作修改为UNION操作，使得不开启Index merge特性的情况下语句依然能使用多个索引，优化SQL为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


SELECT *
FROM tb_xxxx_xxxx
WHERE yn=0
AND C1=‘123456789’
UNION ALL
SELECT *
FROM tb_xxxx_xxxx
WHERE yn=0
AND C2=‘123456789’
AND C1<>‘123456789’

PS： 1、在第二个SELECT语句中增加第一个SELECT语句条件的反操作，从而保证两个SELECT 语句中没有重复数据，可以使用UNION ALL来求交集，避免UNION所带来的排序消耗。 2、在编写SQL语句时，需要注意OR条件的书写，

原SQL为：

1
2
3


WHERE yn=0
AND C1=‘123456789’
OR C2=‘123456789’

等价于：

1
2


WHERE (yn=0 AND C1=‘123456789’)
OR C2=‘123456789’

而实际需求要求所有返回数据满足yn=0的条件，应正确写为:

1
2
3


WHERE yn=0
AND (C1=‘123456789’
OR C2=‘123456789’)

参考: https://gentlezuo.github.io/2019/09/11/MySQL%EF%BC%9A%E7%B4%A2%E5%BC%95%E5%90%88%E5%B9%B6/#%E7%B4%A2%E5%BC%95%E5%90%88%E5%B9%B6 https://www.jianshu.com/p/67b39af2f851

MySQL的索引合并

文章目录