本文主要是介绍记一次 MySQL Intersection 索引合并,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、 概述
在一次 MySQL 慢 SQL 优化过程中, 用 EXPLAIN
发现某表访问 type
为 index_merge
, 在 Extra
列中提示 Using intersect
,而且 Using intersect
中两列均为等值匹配。
什么是 index_merge
呢?
index_merge
其实也是 MySQL 单表访问方法, 通常情况下访问单表是只会用到一个索引,MySQL将查询一张表时使用了多个索引的情况称之为index_merge
,即索引合并,Intersection
是索引合并的一种算法,除了 Intersection
索引合并,还有 Union
索引合并和 Sort-Union
合并。
二、 Intersection 合并
Extra
列中提示 Using intersect
, 那什么又是 Intersection
合并呢? MySQL什么情况下会使用Intersection
合并呢?
1. What’s
Intersection
意为取交集,我们知道逻辑与 &&
有取交集的意思,在 SQL 中则为 and
,所以如果对某一表数据列 and
匹配且有多列均使用索引时,这种访问方式成为 Intersection
合并。
例如,如下 SQL:
SELECT * FROM single_table WHERE key1 = 'foo' AND key2 = 'bar';
假设 single_table
表 key1
建有索引 idx_key1
, key2
建有索引 idx_key2
,且查询时这两个索引都用上了,那么以上 SQL 通过 Intersection
合并方式访问表 single_table
。
MySQL 执行以上 Intersection(idx_key1, idx_key2)
合并过程大致过程如下:
- 从
idx_key1
B+
树中取出key1 = 'foo'
的索引记录,记为result1
; - 从
idx_key2
B+
树中取出key2 = 'bar'
的索引记录,记为result2
; - 步骤一和步骤二返回二级索引记录由索引列 + 主键构成,这一步需要求
result1
和result2
中主键交集; - 根据上一步交集结果回表, 从聚簇索引根据主键取出完整记录;
2. When
那么,在什么情况下 MySQL 会使用Intersection
合并呢?
以上 SQL 还有另外一种执行方式,使用 idx_key1
和 idx_key2
任一索引查询其二级索引 B+
树,然后直接回表,并在回表过程中使用另外一个条件过滤数据。MySQL 执行引擎会选择代价更低的访问方式执行查询。
Intersection
合并关键步骤在第三步 —— 求二级索引结果交集。
LeetCode 上 intersection-of-two-arrays 和这个问题很类似,官方提供的解法将两个数组先转换成 Set
(去重,且 in/contains
时间复杂度为 O ( 1 ) O(1) O(1)),然后用一个 Set
中每条记录在在另外一个Set
中查找。总时间复杂度为 O ( n + m ) O(n+m) O(n+m),空间复杂度也为 O ( n + m ) O(n+m) O(n+m)。
如果按照这种解法,这对于Intersection
合并会有一个致命问题,需要从两个索引中分别把满足 key1 = 'foo'
和 key2 = 'bar'
记录全部加载以建 Set
。如 果 key1 = 'foo'
匹配的数据量比较大呢?比如 key1
存的是状态(通常不会在区分度不高的列上建索引),再比如 key1
不是等值匹配,而是范围匹配 key1 > 'foo'
。更坏的情况是 SQL 中加了 LIMIT
条数限制,而这里却把两个索引中所有匹配索引记录加载到内存。
其实, 如果加一个条件,这个问题就会解决 —— result1
和 result2
中主键有序。
如果 result1
和 result2
中主键有序,可用双指针法求交集,定义两个指针 i
, j
分别指向 result1
和 result2
第一个元素,步骤如下:
- 如果
i
,j
指向元素相等,则将其指向元素加入到交集结果中,i
,j
分别后移一位; - 否则,将
i
,j
指向元素较小则后移一位; - 重复执行以上两个步骤直到某一指针超出范围;
其时间复杂度为 O ( n + m ) O(n+m) O(n+m), 而且几乎没有额外空间开销,这样可以边加载 result1
, result2
边求交集,不用先将其完全加载。
例如 result1
索引记录主键分别为 7, 9, 17, 28, 31
, result2
索引记录主键分别为 9, 11, 28, 31, 37
,其求交集过程如下图:
所以 MySQL 决定使用 Intersection
合并访问单表必要条件是各个索引记录中主键有序。
有两种情况可以保证索引记录中主键有序:
- 索引本来就是聚簇索引, 进行范围匹配;
- 二级索引等值匹配,特别地,联合索引每列都必须等值匹配。因为 MySQL 二级索引中相同的键按照主键排序;
另外,在这两种情况下,索引中的数据均在一起,MySQL 使用顺序 IO 访问访问,效率比较高。
对比使用一个索引 + 回表 + 另外索引过滤访问方式,使用 Intersection
合并由于提前取交集,回表的数据少了,而回表属于随机 IO,比较耗时,所以如果使用的索引满足如上两个条件, MySQL 会使用 Intersection
合并,所从前文 SQL MySQL 会使用 Intersection
合并。
总结,在如下情况下 MySQL 可能使用 Intersection
合并:
- 二级索引列等值匹配,联合索引每列都必须等值匹配;
- 主键列可以是范围匹配;
3. 思考
对于前文 SQL,MySQL 为什么会使用 Intersection
合并,主要是想把索引 idx_key1
和 idx_key2
都用上,那为什么不在 key1
和 key2
上建联合索引呢?这样既不用读多棵 B+
树,也不用求交集,还能过滤多个条件。
三、 Union 合并
Intersection
合并为取交集, Union
合并则为取多个索引并集, 同理 SQL 用 OR
连接多个条件访问单表时可能使用Union
合并。例如:
SELECT * FROM single_table WHERE key1 = 'foo' OR key2 = 'bar';
和Intersection
合并类似, MySQL 在某些特定的情况下才可能会使用到 Union
合并:
- 二级索引列是等值匹配的情况,联合索引每列都必须等值匹配;
- 主键列可以是范围匹配;
- 使用
Intersection
索引合并的搜索条件;
对于第三种情况,因为 Intersection
索引合并结果中也是主键有序的,那么其结果又可以和其他索引构成 Union
合并;
例如:
SELECT * FROM single_table WHERE key1 = 'foo' OR (key2 = 'bar' AND key3 = 'foo-bar');
single_table
表中,列 key1
, key2
, key3
分别建有二级索引 idx_key1
,idx_key2
,idx_key3
, 如上 SQL 可以先使用idx_key2
,idx_key3
进行Intersection
索引合并,然后再将其结果和 idx_key1
进行Union
合并,最后再把Union
合并结果回表。
三、 Sort-Union 合并
Union
索引合并都需要索引记录主键有序,如果无序呢?在数据量不是很大情况下可以排序,这就是 Sort-Union
合并。
所以 Sort-Union
合并条件相对Union
索引比较松散些,二级索引可以是范围匹配,但匹配出的数据量不能很大。
例如:
SELECT * FROM single_table WHERE key1 > 'foo' OR key2 > 'bar';
如果条件 key1 > 'foo'
和 key2 > 'bar'
查询二级索引结果记录数据量不是很大的情况下,可能使用 Sort-Union
合并方式访问 single_table
表,访问过程如下:
- 从
idx_key1
B+
树中取出key1 > 'foo'
的索引记录,并按主键排序, 结果记为result1
; - 从
idx_key2
B+
树中取出key2 > 'bar'
的索引记录,并按主键排序, 结果记为result2
; - 求
result1
和result2
并集; - 将上一步求得的结果回表;
那有没有 Sort-Intersection
索引合并呢?即,求交集前,先对无序的二级索引记录主键排序,答案是否定的。因为 Intersection
合并使用场景是二级索引记录太多导致回表随机 IO 开销较大,如果先对二级索引排序的话,可能排序开销更大。
这篇关于记一次 MySQL Intersection 索引合并的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!