Index-merge原理
站长
· 阅读数 27
参考链接中都是很有深度的文章，本文还是浅显化输出+结合实际应用
后面有时间再研究下一些细节的地方
前言
在生产中，经常会看到有SQL where条件有普通索引等值+主键范围查询+order by limit 命名走普通索引效率更高，但是选择走了索引合并，因此对这种情况进行了梳理。
官方对于Index Merge的介绍：
The Index Merge access method retrieves rows with multiple range scans and merges their results into one.
在一般情况下，对于一个单表，优化器选择一个索引，但在索引合并的情况下，优化器可以使用多个索引来获取数据并对其结果进行合并
需要注意的是：这里实际上是先通过二级索引获取到主键，对主键进行排序合并，然后根据主键回表，来避免随机IO
归并排序算法
在介绍索引合并的方式及算法前，先来简单看下归并排序算法，以可以更好地理解MySQL中的索引合并。
归并算法是分治思想的应用，递归地将列表分成更小的子列表，将子列表进行排序，然后合并来得到有序列表。
可直接前往下面文章链接查看，简单直观：
图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园
下面是几种常见算法的时间复杂度：可以看到归并排序还是比较快的
| 算法名称 | 平均时间复杂度 | 空间复杂度 |
|---|---|---|
| 归并排序 | O(n log n) | O(n) |
| 选择排序 | O(n^2) | O(1) |
| 冒泡排序 | O(n^2） | O(1) |
| 插入排序 | O(n^2) | O(1) |
| 快速排序 | O(n log n) | O(n) |
| 堆排序 | O(n log n) | O(1) |
| 桶排序 | O(n+k) | O(n) |
| 计数排序 | O(n+k) | O(n+k) |
| 基数排序 | O(nk) | O(n+d) |
索引合并算法
在MySQL中，索引合并算法有下面几种：
- index_merge_intersection ：交集，对应执行计划Extra：Using intersect(...)，对应源码中的QUICK_ROR_INTERSECT_SELECT类
- index_merge_union ：并集，对应执行计划Extra：Using union(...)，对应源码中的QUICK_ROR_UNION_SELECT类
- index_merge_sort_union：有序并集，对应执行计划Extra：Using sort_union(...)，对应源码中的QUICK_INDEX_MERGE_SELECT类
（为什么没有sort_merge算法）
这里可以看到在前两种方式中，实现类名都有ROR关键字，ROR的含义是Rowid-Ordered Retrieval，表示单个索引返回的结果集是按照主键有序排列的。这样，根据归并排序算法，进行合并结果集的时候就省去了递归排序的步骤，而只需要将有序列表合并即可
而对于第三种方式，由于返回的结果不是按照主键排序的，则需要先进行归并排序
因此，对于前2种情况，在下面条件返回的结果集主键是有序的，则其where条件需要满足下面的条件：
- 二级索引的条件满足：where条件需要有所有的索引字段，且是等值匹配。例如一个索引idx(a,b,c)，则使用该索引的where条件需要是：a=? and b=? and c=?
- 主键范围查询
其中，
- 用到交集（intersection）算法的，通常是用and连接的各索引条件，经过索引合并后的主键结果集比走一个索引的主键结果集更小的情况下比较有优势
- 使用到并集（union)算法的，通常是or连接的各部分条件，走两个索引比走全表扫描成本更低的情况下有优势
而对于第3种情况，在不能使用前两种算法的情况下，如果经过计算走索引合并的成本更低，会选择，该种算法需要去重和排序，这里去重和排序使用到树结构，去扒了一点点源码，放在这里
sql opt_range.cc
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
-- 该函数的作用是：
在索引合并中，扫描使用到的所有索引（除了CPK-Clustered Primary key，即主键）并将其rowid合并
如果某个记录能从主键范围条件中扫描获取到，则跳过该行
否则后续执行unique_add方法，该方法向树结构中插入元素，实现了排序和去重
/* skip row if it will be retrieved by clustered PK scan */
if (pk_quick_select && pk_quick_select->row_in_ranges())
continue;
cur_quick->file->position(cur_quick->record);
result= unique->unique_add((char*)cur_quick->file->ref);
if (result)
DBUG_RETURN(1);
unique_add方法，在其中调用了tree_insert
inline bool unique_add(void *ptr)
{
DBUG_ENTER("unique_add");
DBUG_PRINT("info", ("tree %u - %lu", tree.elements_in_tree, max_elements));
if (tree.elements_in_tree > max_elements && flush())
DBUG_RETURN(1);
DBUG_RETURN(!tree_insert(&tree, ptr, 0, tree.custom_arg));
}
-- tree_insert中，在遍历树的过程中，有一行代码，
如下：表示如果不是树的null节点，则进行比较元素是否和要插入的值相等，相等则跳出循环（这样也就保证了树上不会有重复的值）
for (;;)
{
if (element == &tree->null_element ||
(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
key)) == 0)
break;
...
综上，以下三种算法的示例SQL：
-- 前2种：来自官方
SELECT * FROM innodb_table
WHERE primary_key < 10 AND/OR key1_part1 = 20;
SELECT * FROM innodb_table
WHERE (key1_part1 = 1 AND key1_part2 = 2) AND/OR key2 = 2;
-- 第3种：来源参考链接，官方案例不对
SELECT * FROM innodb_table
WHERE (key1_part1 = 2 or key1_part1 = 7) or key2_part1 = 4
SELECT * FROM innodb_table
WHERE key1_part1 < 10 OR key2_part1 < 20;
官方案例：
1.
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;
2.
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;
3. -- 这两种情况无法走到索引，示例有错误
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;
一个特殊的情况是，index_merge_intersection情况下，其中有一个条件是主键范围，这个情况主键条件只起到数据过滤的作用，而并不需要将满足该条件的记录取出再做合并，具体是：
- 在遍历二级索引取出rowid时，判断该rowid是否在主键范围内，如果是则保留，否则忽略这个rowid
这里，再回到文章开头遇到的问题，即"where条件有普通索引等值+主键范围查询+order by limit "，很多情况走单个二级索引要比走索引合并更快。
其主要原因在于：
- 走索引合并需要将满足二级索引条件的记录都扫描出来
- 走单个二级索引，由于limit的存在，实际上并不需要扫描满足条件的全部记录，而在获取到满足条件的记录后就停止扫描，因此在一些情况下效果会更好
这里，实际上MySQL在计算成本的时候，先没有考虑limit语句，但是成本计算完之后，对于一些场景会有rechecking_index_usage的动作，其中有一个recheck_reason是：LOW_LIMIT，其判断逻辑是，当limit的行数小于表的“扇出”（rows_fetched * filter） ：
- 检查是否有索引可用于order by 子句，并经过一些逻辑判断是否需要改变执行计划（后面再看看逻辑）
recheck index的代码如下：
扒出一段源码，如下：也就是在满足一些条件的情况下，会重新检查时候可以使用一个索引来完成，其中包括索引合并的情况
if ((tab->type() == JT_ALL || tab->type() == JT_RANGE ||
tab->type() == JT_INDEX_MERGE || tab->type() == JT_INDEX_SCAN) &&
tab->use_quick != QS_RANGE)
{/*
We plan to scan (table/index/range scan).
Check again if we should use an index. We can use an index if:
1a) There is a condition that range optimizer can work on, and
1b) There are non-constant conditions on one or more keys, and
1c) Some of the non-constant fields may have been read
already. This may be the case if this is not the first
table in the join OR this is a subselect with
non-constant conditions referring to an outer table
(dependent subquery)
or,
2a) There are conditions only relying on constants
2b) This is the first non-constant table
2c) There is a limit of rows to read that is lower than
the fanout for this table, predicate filters included
(i.e., the estimated number of rows that will be
produced for this table per row combination of
previous tables)
2d) The query is NOT run with FOUND_ROWS() (because in that
case we have to scan through all rows to count them anyway)
*/
enum { DONT_RECHECK, NOT_FIRST_TABLE, LOW_LIMIT }
recheck_reason= DONT_RECHECK;
assert(tab->const_keys.is_subset(tab->keys()));
const join_type orig_join_type= tab->type();
const QUICK_SELECT_I *const orig_quick= tab->quick();
if (cond && // 1a
(tab->keys() != tab->const_keys) && // 1b
(i > 0 || // 1c
(join->select_lex->master_unit()->item &&
cond->used_tables() & OUTER_REF_TABLE_BIT)))
recheck_reason= NOT_FIRST_TABLE;
else if (!tab->const_keys.is_clear_all() && // 2a
i == join->const_tables && // 2b
(join->unit->select_limit_cnt <
(tab->position()->rows_fetched *
tab->position()->filter_effect)) && // 2c
!join->calc_found_rows) // 2d
recheck_reason= LOW_LIMIT;
...
if (recheck_reason == LOW_LIMIT)
{
int read_direction= 0;
/*
If the current plan is to use range, then check if the
already selected index provides the order dictated by the
ORDER BY clause.
*/
if (tab->quick() && tab->quick()->index != MAX_KEY)
{
const uint ref_key= tab->quick()->index;
read_direction= test_if_order_by_key(join->order,
tab->table(), ref_key);
/*
If the index provides order there is no need to recheck
index usage; we already know from the former call to
test_quick_select() that a range scan on the chosen
index is cheapest. Note that previous calls to
test_quick_select() did not take order direction
(ASC/DESC) into account, so in case of DESC ordering
we still need to recheck.
*/
if ((read_direction == 1) ||
(read_direction == -1 && tab->quick()->reverse_sorted()))
{
recheck_reason= DONT_RECHECK;
}
}
/*
We do a cost based search for an ordering index here. Do this
only if prefer_ordering_index switch is on or an index is
forced for order by
*/
if (recheck_reason != DONT_RECHECK &&
(tab->table()->force_index_order ||
thd->optimizer_switch_flag(
OPTIMIZER_SWITCH_PREFER_ORDERING_INDEX)))
{
int best_key= -1;
ha_rows select_limit= join->unit->select_limit_cnt;
/* Use index specified in FORCE INDEX FOR ORDER BY, if any. */
if (tab->table()->force_index)
usable_keys.intersect(tab->table()->keys_in_use_for_order_by);
/* Do a cost based search on the indexes that give sort order */
test_if_cheaper_ordering(tab, join->order, tab->table(),
usable_keys, -1, select_limit,
&best_key, &read_direction,
&select_limit);
if (best_key < 0)
recheck_reason= DONT_RECHECK; // No usable keys
else
{
// Only usable_key is the best_key chosen
usable_keys.clear_all();
usable_keys.set_bit(best_key);
interesting_order= (read_direction == -1 ? ORDER::ORDER_DESC :
ORDER::ORDER_ASC);
}
}
}
案例
一个常见的走索引合并反而效率更差的场景：select * from t where c1 ='d' and id>=600000 order by id limit 1000;
-- 表结构
CREATE TABLE `t` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`c1` char(64) NOT NULL,
`c2` char(64) NOT NULL,
`c3` char(64) NOT NULL,
`c4` char(64) NOT NULL,
PRIMARY KEY (`id`),
KEY `idx_c1` (`c1`)
) ENGINE=InnoDB AUTO_INCREMENT=978914 DEFAULT CHARSET=utf8mb4
-- 涉及到的条件记录
mysql> select count(*) from t where c1='d';
+----------+
| count(*) |
+----------+
| 65536 |
+----------+
1 row in set (0.12 sec)
mysql> select count(*) from t where id>=600000;
+----------+
| count(*) |
+----------+
| 313385 |
+----------+
1 row in set (0.39 sec)
mysql> select count(*) from t where c1 ='d' and id>=600000;
+----------+
| count(*) |
+----------+
| 26112 |
+----------+
1 row in set (0.11 sec)
-- 这里有个注意的地方：实际上不加order by id，返回的记录已经是有序的了，但是执行计划中还是有Using filesort
mysql> explain select * from t where c1 ='d' and id>=600000 order by id limit 1000;
+----+-------------+-------+------------+-------------+----------------+----------------+---------+------+-------+----------+--------------------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------------+----------------+----------------+---------+------+-------+----------+--------------------------------------------------------------+
| 1 | SIMPLE | t | NULL | index_merge | PRIMARY,idx_c1 | idx_c1,PRIMARY | 260,4 | NULL | 26667 | 100.00 | Using intersect(idx_c1,PRIMARY); Using where; Using filesort |
+----+-------------+-------+------------+-------------+----------------+----------------+---------+------+-------+----------+--------------------------------------------------------------+
1 row in set, 1 warning (0.00 sec)
-- 执行时间：170ms
1000 rows in set (0.17 sec)
-- slowlog中可以看到其扫描行数为：27112
# Time: 2024-06-13T19:00:38.741184+08:00
# User@Host: root[root] @ VMS184912 [10.61.250.57] Id: 148
# Query_time: 0.174327 Lock_time: 0.000802 Rows_sent: 1000 Rows_examined: 27112
SET timestamp=1718276438;
select * from t where c1 ='d' and id>=600000 order by id limit 1000;
-- 如果去掉order by语句：10ms，其执行计划仍然是索引合并但是没有了Using filesort
mysql> explain select * from t where c1 ='d' and id>=600000 limit 1000;
+----+-------------+-------+------------+-------------+----------------+----------------+---------+------+-------+----------+----------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------------+----------------+----------------+---------+------+-------+----------+----------------------------------------------+
| 1 | SIMPLE | t | NULL | index_merge | PRIMARY,idx_c1 | idx_c1,PRIMARY | 260,4 | NULL | 26667 | 100.00 | Using intersect(idx_c1,PRIMARY); Using where |
+----+-------------+-------+------------+-------------+----------------+----------------+---------+------+-------+----------+----------------------------------------------+
1 row in set, 1 warning (0.00 sec)
-- 执行时间
1000 rows in set (0.01 sec)
-- slow log内容：这里只有1000行，并不需要读取全部满足二级索引的记录
# Time: 2024-06-13T19:00:59.217427+08:00
# User@Host: root[root] @ VMS184912 [10.61.250.57] Id: 148
# Query_time: 0.010773 Lock_time: 0.000145 Rows_sent: 1000 Rows_examined: 1000
SET timestamp=1718276459;
select * from t where c1 ='d' and id>=600000 limit 1000;
-- 如果原本的sql强制走二级索引
mysql> explain select * from t force index(idx_c1) where c1 ='d' and id>=600000 order by id limit 1000;
+----+-------------+-------+------------+-------+---------------+--------+---------+------+-------+----------+-----------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+--------+---------+------+-------+----------+-----------------------+
| 1 | SIMPLE | t | NULL | range | idx_c1 | idx_c1 | 260 | NULL | 53334 | 100.00 | Using index condition |
+----+-------------+-------+------------+-------+---------------+--------+---------+------+-------+----------+-----------------------+
1 row in set, 1 warning (0.01 sec)
-- 执行时间：10ms
1000 rows in set (0.01 sec)
对于慢日志中row_examinded的解释：
/**
Number of rows read and/or evaluated for a statement. Used for
slow log reporting.
An examined row is defined as a row that is read and/or evaluated
according to a statement condition, including in
create_sort_index(). Rows may be counted more than once, e.g., a
statement including ORDER BY could possibly evaluate the row in
filesort() before reading it for e.g. update.
*/
针对这种情况的优化：
- 对于order by id asc的情况，可省略order by语句
- id范围条件改为id+0>= ，使sql走二级索引
建议采用方式1
小结
通常情况下对于一张表的访问，MySQL选择一个索引，在where条件中range condition满足下面条件的情况下，有可能使用到两个索引，即索引合并：
-
二级索引的条件满足：where条件需要有所有的索引字段，且是等值匹配。例如一个索引idx(a,b,c)，则使用该索引的where条件需要是：a=? and b=? and c=?
-
主键范围查询
有3中索引合并算法：
-
index_merge_intersection ：交集，对应执行计划Extra：Using intersect(...)，对应源码中的QUICK_ROR_INTERSECT_SELECT类
-
index_merge_union ：并集，对应执行计划Extra：Using union(...)，对应源码中的QUICK_ROR_UNION_SELECT类
-
index_merge_sort_union：有序并集，对应执行计划Extra：Using sort_union(...)，对应源码中的QUICK_INDEX_MERGE_SELECT类
对于前两种，在分别使用两个索引返回的结果集主键有序的情况下适用，第三种情况则是分别使用两个索引返回的主键无序的情况下使用
另外，在交集索引合并中，当range condition中有个条件是主键范围查询时，该条件仅做过滤数据使用，并不需要将满足该条件的记录取出再做合并后回表
一种常见走索引合并反而效率差的场景：
- 其中一个条件是主键，如id的范围查询，且有order by id limit N的情况
差的原因：
- 该种情况下使用索引合并需要取出满足条件的所有二级索引记录
- 而使用单个索引，则获取到满足limit的记录后就不需要再扫描
为什么这种情况会走索引合并：MySQL在计算成本的时候不考虑limit语句，但在最后会recheck index usage，检查是否需要改变执行计划
对于该场景的优化方式：
-
如果order by id是增序排列的情况下，实际上根据二级索引回表显示的结果已经是按照主键增序显示，可去掉order by语句 – 推荐
-
通过调整sql使走二级索引
参考链接
转载自:https://juejin.cn/post/7381137533596336191