MySQL Index-Merge代价估算原理

Author: zhishu

线上高频慢查

在PolarDB-MySQL线上慢查问题中，经常遇到因选中Index-Merge索引反而导致查询更慢的情况，这种情况一般是没有太好的通用解决办法，一般是建议客户针对查询force index来固化某个索引，或者使用NO_INDEX_MERGE 的hint关闭index merge选项。

比如下面一个PolarDB客户的查询（已脱敏），优化器选择了Index Merge，但查询变的更慢了：


1. *************************** 1. row ***************************
2. id: 1
3. select_type: SIMPLE
4. table: p
5. partitions: NULL
6. type: index_merge
7. possible_keys: key1,key6,key8,key5,key7,key2,key4,key3
8. key: key7,key5
9. key_len: 254,17
10. ref: NULL
11. rows: 63220
12. filtered: 10.00
13. Extra: Using intersect(key7,key5); Using where

15. ## 查看Trace信息：
16. {   ## range扫描的代价
17. "index": "key5",
18. "index_dives_for_eq_ranges": true,
19. "rowid_ordered": true,
20. "using_mrr": false,
21. "index_only": false,
22. "in_memory": 0.0892,
23. "rows": 83730,
24. "cost": 92104,    ## key5 range扫描代价
25. "chosen": true,
26. "cause": "cost"
27. },

29. { ## range扫描的代价
30. "index": "key7",
31. "index_dives_for_eq_ranges": true,
32. "rowid_ordered": true,
33. "using_mrr": false,
34. "index_only": false,
35. "in_memory": 0.0161,
36. "rows": 188308,
37. "cost": 207140,        ## key7 range扫描代价
38. "chosen": false,
39. "cause": "cost"
40. },

43. "analyzing_roworder_intersect": {
44. ### Index Merge的代价估算
45. "intersecting_indexes": [
46. {
47. "index": "key7",
48. "index_scan_cost": 5814.5,
49. "cumulated_index_scan_cost": 5814.5,
50. "disk_sweep_cost": 166598,
51. "cumulated_total_cost": 172412,  ## ror scan cost
52. "usable": true,
53. "matching_rows_now": 188308,
54. "isect_covering_with_this_index": false,
55. "chosen": true
56. },
57. {
58. "index": "key5",
59. "index_scan_cost": 239.13,
60. "cumulated_index_scan_cost": 6053.7,
61. "disk_sweep_cost": 59370,
62. "cumulated_total_cost": 65423,  ## ror intersect代价
63. "usable": true,
64. "matching_rows_now": 64048,
65. "isect_covering_with_this_index": false,
66. "chosen": true
67. }
68. ],
69. "clustered_pk": {
70. "clustered_pk_added_to_intersect": false,
71. "cause": "no_clustered_pk_index"
72. },
73. "rows": 64047,
74. "cost": 65423,
75. "covering": false,
76. "chosen": true
77. }

从trace中看到，Using intersect的代价估算比两个索引独立range scan都要小，最终选择了index merge。从结果上我们知道选择index merge并不是最优的，还变的更差了，本文将带着如下几个问题去探讨index merge：

  1. 什么是Index Merge，都有哪些类型及基本原理；
  2. 为什么要有Index Merge，解决了什么问题，它的优势在哪?
  3. 了解Index Merge代价估算原理，为什么总遇到bad case？
  4. 是否有减少bad case的解决思路

Index Merge简介

Index Merge是通过同时扫描多个索引，再将数据合并到一起的访问方式。只适用于单表有多个索引可选的情况，不支持用多表场景。合并数据的种类有：unions，intersections。


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

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

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

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

Inerge-Merge的使用限制： ● 如果where条件中有复杂的AND/OR嵌套，可能选不中较优的计划。建议做如下变换： ○ (x AND y) OR z => (x OR z) AND (y OR z) ○ (x OR y) AND z => (x AND z) OR (y AND z) ● 不支持full-text索引。

Index-Merge有多种执行方式，会在在Explain的Extra信息中显示： ● Using intersect(…) ● Using union(…) ● Using sort_union(…)

详细可以阅读官网介绍，下面简单总结下要点。

ROR-Intersection

适用多个AND组合的range条件上都有索引，且索引必须满足如下条件之一： ● 如果是联合索引，索引的多个keyparts必须都被使用； ● 二级索引扫描是ROR(rowid ordered) ● 在主键上的range条件；

ROR-Intersection策略： ● 优先扫描二级索引，结果按照rowid进行合并取交集 ● 主键索引条件只作为filter，并不做scan ● 合并后如果变为覆盖索引，可以避免回表

ROR-Union

适用多个OR组合的range条件上都有索引，索引需满足的条件和Intersection一致。 Union策略： ● 如果是联合索引，索引的多个keyparts必须都被使用； ● 二级索引扫描是ROR(rowid ordered) ● 扫描多个索引数据，按照rowid进行去重取并集。

Sort-Union

索引不满足ROR的，先对索引扫描的数据按照rowid进行排序，再进行去重取并集。

Index Merge的意义

在AND组合条件中，选择Index Merge进行intersection，每个索引都要扫描一遍再取交集，扫描行数明显会变多，但取交集后结果集会变少，能减少回表的开销。若多个索引组合起来能覆盖所有访问的列，就变成了覆盖索引，可以直接避免回表。 在OR组合条件中，如果不选Index Merge，就只能全表扫描了，通过扫描多个索引取并集，可以避免全表扫描。

如何选择Index Merge

本章节主要介绍Index Merge代价估算原理。

MySQL索引扫描代价计算

在介绍Index Merge代价估算原理前，先简单介绍下MySQL索引扫描方式代价计算原理：

全表扫描，在主键上做全表扫描的代价

// table_scan_pages是扫描主键的pages数 table_scan_cost = table_scan_pages * page_read_cost + row_evaluate_cost(rows)

索引扫描，覆盖索引

// index_scan_pages是扫描索引的pages数 index_scan_cost = index_scan_pages * index_page_read_cost

索引扫描，非覆盖索引，考虑回表代价

//非覆盖索引扫描，MySQL认为每一行都要回表，将rows视为pages来计算整体代价 index_read_cost = (index_scan_rows + ranges) * page_read_cost

另外补充下page_read_cost和index_page_read_cost的区别，因为有的pages是在buffer pool缓存中，有的pages是在磁盘中，代价公式需要考虑pages在缓存中的比率来计算代价。区别就是page_read_cost中使用table_in_memory_estimate来计算，index_page_read_cost使用index_in_memory_estimate来计算。


1. page_read_cost = mem_read_cost(table_pages_in_mem) + io_read_cost(table_pages_on_disk)
2. index_page_read_cost = mem_read_cost(index_pages_in_mem) + io_read_cost(index_pages_on_disk)

ROR Intersection代价计算

使用non-covering ROR-intersection搜索算法找到最优的ROR-intersection计划。返回的计划，有可能是覆盖所有列的计划，无需再回表。


1. # 检索最优的ROR-intersection
2. find_min_ror_intersection_scan()
3. {
4. R= select all ROR scans;  ## Sort indexes in an order that is likely to be a
5. ## good index merge intersection order.

7. S= first(R); -- set of scans that will be used for ROR-intersection
8. R= R-first(S);
9. min_cost= cost(S);
10. min_scan= make_scan(S);
11. while (R is not empty)
12. {
13. firstR= R - first(R);
14. if (!(selectivity(S + firstR) < selectivity(S)))
15. continue;

17. S= S + first(R);
18. if (cost(S) < min_cost)
19. {
20. min_cost= cost(S);
21. min_scan= make_scan(S);
22. }
23. }
24. return min_scan;
25. }

算法思路为：

  1. 首先对ROR scan索引进行排序，目标是选择尽量少的索引进行ROR-intersection。 a. 首先索引num_covered_fields_remaining（剩余未被覆盖的fields个数）少的排在前面，更容易组合成覆盖索引； b. 其次扫描行数少的排在前面；
  2. 按照顺序依次计算合并后选择率、代价 a. 计算合并后的选择率，若合并后的选择率不低于合并前，则跳过这个索引，继续考虑后面的 b. 计算合并后的代价，比较并保存min_cost, min_scan组合
  3. 最后输出认为代价最低的 min_scan

ROR-Intersection 选择率计算

整体算法思路比较清晰，算法关键点是ror-scan 合并后选择率的计算，前面提到的慢查问题，也多是这里存在当前算法不适用的场景，产生了bad case。下面介绍下选择率估算算法。


1. # 假设有如下的多个索引的条件：
2. cond=k_11=c_11 AND k_12=c_12 AND ...  // key_parts of first key
3. k_21=c_21 AND k_22=c_22 AND ...  // key_parts of second key
4. ...
5. k_n1=c_n1 AND k_n3=c_n3 AND ...  // key_parts of n key

7. # 其中k_ij 和 k_pq 可能是相同的列

假设已计算完前n-1个ror-scan索引合并的代价为例，现在需要计算合并第n个索引的选择率乘数selectivity_mult，目的是计算合并后的out_rows和代价。

Index Merge选择率

如上图示例中，合并第n个索引前，前面的索引合并起来已经覆盖到a,b,c,d（顺序无关）等列，第n个索引中部分keyparts和已合并的有重叠，这里selectivity_mult计算的是剩余非覆盖列的选择率乘数，计算方法如下：


1. selectivity_mult = prefix_scan_records(..., j) /  prefix_scan_records(..., b)
2. * prefix_scan_records(..., y) / prefix_scan_records(..., c)
3. * ...

其中prefix_scan_records(…, b)的含义是索引按照这些前缀keyparts要扫描的行数，对应代码中的records_per_key[keyparts]，或者利用直方图、index dive来估算的固定索引前缀keyparts的扫描行数。


1. info->out_rows *= selectivity_mult     ## 计算合并后的输出行数
2. info->index_records += quick_rows[ror_scan->keynr]; ## 扫描行数累计
3. info->index_scan_cost += ror_scan->index_read_cost;  ## index-only的扫描代价累计
4. bitmap_union(&info->covered_fields, &ror_scan->covered_fields); ##合并covered_fields

6. info->total_cost = info->index_scan_cost;
7. if 非覆盖索引：
8. sweep_cost = get_sweep_read_cost ## sweep就是计算回表的IO代价
9. info->total_cost += sweep_cost;  ##

info->total_cost为ROR-intersection合并后的总代价，若info->total_cost比任意其它range scan的代价低的话，最终将选择index merge来替代range scan。

问题：虽然在计算选择率乘数时，已经排除了重叠的fields，但非重叠的fields的selectivity_mult还是基于非相关的假设来计算的。如果两个索引中的列有强相关性，索引合并后并不能如预期的降低out_rows，也就是代价估算偏低选中了Index-Merge，但实际执行开销可能更高了。

Sort-Union代价计算

如果查询语句包含多个OR条件索引，同时扫描多个索引，再去重后取并集。正常情况or条件无法选中索引，只能全表扫描，需要计算合并索引的代价是否低于best_plan。


1. ## ROR-Union的代价计算：
2. ## 计算流程：(a = 1 and b = 2) or (c = 3 and d = 3)
3. Loop 'OR' range 条件tree：
4. - cur_child = get_key_scans_params  ## 获取当前range条件best range scan方式
5. ## 如果没有找到best range，则设置imerge_too_expensive = true
6. - imerge_cost += (*cur_child)->cost_est;  ## 累加对应range scan的代价
7. - non_cpk_scan_records += (*cur_child)->records;

9. sweep_cost = get_sweep_read_cost  ## 计算回表代价，回表行数就是non_cpk_scan_records
10. imerge_cost += sweep_cost

12. dup_removal_cost = Unique::get_use_cost  ##计算
13. imerge_cost.add_cpu(dup_removal_cost);

15. # imerge_cost 为总代价

ROR-Union的代价计算比Intersection简单很多，基本思想就是将多个索引扫描代价累加，加上去重后回表的代价，再加上union去重的代价。

ROR-Union代价计算

如果多个OR条件的索引都是ROR(rowid ordered)的，可以利用rowid有序的特性，快速去重，节省掉了Unique_set的开销。


1. ## ROR-Union的代价公式：

3. ## 计算流程：(a = 1 and b = 2) or (c = 3 and d = 3)
4. Loop cur_child in range_scans:  ## range_scans已经在计算sort-union时填充好了，这里无需再调用get_key_scans_params
5. - cur_roru_plan = get_best_ror_intersect ## 复用ror-intersection来计算(a = 1 and b = 2) 单独某部分range条件的代价
6. - roru_index_cost += (*cur_roru_plan)->index_scan_cost;
7. - roru_total_records += (*cur_roru_plan)->records;
8. - roru_intersect_part *=
9. (*cur_roru_plan)->records / param->table->file->stats.records;  # 计算去重率

11. # 估算去重后的行数
12. roru_total_records -=
13. (ha_rows)(roru_intersect_part * param->table->file->stats.records);

15. sweep_cost = get_sweep_read_cost  ## 回表行数roru_total_records

17. # Calculate cost:
18. roru_total_cost += roru_index_cost ## index only scan cost
19. roru_total_cost += sweep_cost   # 回表代价
20. roru_total_cost.add_cpu(cost_model->key_compare_cost(
21. rows2double(roru_total_records) * std::log2(n_child_scans)));  ## queue_use_cost(rowid_len, n)

ROR-Union和Sort-Union的主要区别，一个是计算了去重率，回表代价按照去重后的行数来计算，但Sort-Union并没有计算去重率。第二个区别就是去重的代价，Sort-Union使用的是Unique_set，ROR-Union使用的是优先级queue来实现的。

总结

Index Merge原理是通过扫描多个索引，将各索引扫描的数据进行合并（交集、并集），预期是更快的计算出目标结果。比如ROR-intersection方式在合并后能减少回表的次数，甚至多个索引组合成覆盖索引可直接避免回表，大幅提升性能；ROR-Union方式通过扫描多个索引进行并集合并，避免扫描全表从而提升效率。

Index Merge并不总是能提升性能，比如ROR-intersection中，多个索引扫描的数据重叠路非常高，合并取交集并不会减少found_rows，这样既没有减少回表次数，又额外增加了N多个索引的扫描，开销反而增加了。再比如ROR-Union中，若多个OR条件的扫描行数都很大，加起来扫描行数可能比全表rows都要大，就不如直接扫全表了。所以基于代价的选择Index Merge成为了影响查询性能的关键: ● Intersection代价，关键在计算索引合并后的out_rows，也就是合并后的交集选择率乘数。 ● Union的代价相对简单些，主要是将多个索引扫描的代价累加

ROR-Intersection的Index Merge在线上出现慢查的频率最高，主要问题出在索引合并选择率乘数的计算上，它是基于非相关性假设计算的。若真实业务数据两列存在较大的相关性，既两个索引扫描出的数据有大量重叠，这样两个索引相交后out_rows比预期要大很多，但代价计算中无法识别列间的相关性，估算的Index Merge代价通常会偏小，导致错选Index Merge引发慢查询。

解决路径 这个问题的优化思路就是支持列和列之间的相关性统计，一般称为dependency扩展统计信息，提升索引合并选择率的准确度。MySQL的统计信息仅支持索引前缀的基数估算，还有index dive作为补充。如果是非索引列，或者是索引的非前缀列，是没有单独的基数统计，这些条件的选择率计算就偏差非常大。 社区8.0开始也支持了Histogram，但并不支持自动更新，很难在生产环境被广泛使用。

PolarDB MySQL目前在做统计信息的增强，支持非索引列的ndv,null fraction, mcv，histogram, correlation等，还支持多列的dependency, multi-NDV, multi-MCV等扩展统计信息，并会推出一套完整的统计管理机制，实现扩展统计信息的自动更新、管理等。

原文：http://mysql.taobao.org/monthly/2024/09/04/