【GreatSQL优化器-16】INDEX_SKIP_SCAN

石小疯  论坛元老 | 2025-3-12 09:46:46 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1856|帖子 1856|积分 5568

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？立即注册

x
【GreatSQL优化器-16】INDEX_SKIP_SCAN

一、INDEX_SKIP_SCAN介绍

GreatSQL 优化器的索引跳跃扫描（Index Skip Scan） 是一种优化查询的技术，尤其在联合索引中用于减少扫描的无效行数。它通过"跳跃"式的扫描方式，避免了对索引中无用部分的扫描，从而提升查询服从。这种技术得当特定场景，并有一定的优缺点。
索引跳跃扫描利用的是联合索引中非首列（非最左前缀）的索引列，来提高查询服从。例如，如果你有一个复合索引 (A, B)，在传统的 B-Tree 索引中，只有当查询条件包含 A 列时，索引才会生效。但在跳跃扫描中，即使 A 没有出现在查询条件中，仍旧可以通过扫描 B 列来有效查询。跳跃扫描会逐步扫描 A 列的每一个可能值，然后在每个 A 值下查找 B 列中符合条件的记录。这样避免了扫描大量无关记录，提升了查询性能。
下面用一个简单的例子来说明INDEX_SKIP_SCAN怎么应用在优化器。
  1. CREATE TABLE t1(c1 INT, c2 INT, c3 INT, c4 INT);
  2. CREATE UNIQUE INDEX i1_t1 ON t1(c1,c2,c3);
  3. INSERT INTO t1 VALUES (1,1,1,1), (1,1,2,2), (1,3,3,3), (1,4,4,4), (1,5,5,5),
  4.                       (2,1,1,1), (2,2,2,2), (2,3,3,3), (2,4,4,4), (2,5,5,5);
  5. INSERT INTO t1 SELECT c1, c2, c3+5, c4+10  FROM t1;
  6. INSERT INTO t1 SELECT c1, c2, c3+10, c4+20 FROM t1;
  7. INSERT INTO t1 SELECT c1, c2, c3+20, c4+40 FROM t1;
  8. INSERT INTO t1 SELECT c1, c2, c3+40, c4+80 FROM t1;
  9. ANALYZE TABLE t1;
  11. -- 下面的结果用到了skip scan
  12. greatsql> EXPLAIN SELECT c1, c2 FROM t1 WHERE c2 > 40;
  13. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+
  14. | id | select_type | table | partitions | type  | possible_keys | key   | key_len | ref  | rows | filtered | Extra                                  |
  15. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+
  16. |  1 | SIMPLE      | t1    | NULL       | range | i1_t1         | i1_t1 | 10      | NULL |   53 |   100.00 | Using where; Using index for skip scan |
  17. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+
  19. /*运行过程：
  20. 1、先找到第一列的不同值，得到结果为1和2
  21. select distinct c1 from t1;
  22. 2、根据第一列的分组结果在分组内执行范围扫描
  23. select c1, c2 from t1 where c1 = 1 and c2 > 40;
  24. select c1, c2 from t1 where c1 = 2 and c2 > 40;*/
复制代码
二、get_best_skip_scan代码解释

skip scan 是根据条件生成 mm tree 以后，根据 mm tree 结果和索引举行判定能不能用 skip scan，其中联合索引中范围条件列之前的列为prefix列，即用来作为分组的依据的列，如果有多个除了第一列之外的范围列，那么选取遇到的第一个列之前的列为前缀举行分组。
  1. int test_quick_select() {
  2.   // 先判断skip_scan是否满足条件，不满足的话执行索引合并。
  3.   AccessPath *skip_scan_path = get_best_skip_scan();
  4.   // 不满足skip_scan执行索引合并，相关知识看上一节介绍
  5. }
  7. AccessPath *get_best_skip_scan() {
  8.   // 先判断sql是否支持skip_scan，见表一
  9.   // 接着开始执行skip_scan，遍历所有索引
  10.   for (uint cur_param_idx = 0; cur_param_idx < param->keys; ++cur_param_idx) {
  11.     // covering_keys代表可以使用的联合索引，sql涉及的所有列必须都在联合索引上才会有值
  12.     if (!table->covering_keys.is_set(cur_index)) {
  13.       cause = "query_references_nonkey_column";
  14.       goto next_index;
  15.     }
  16.     // 从mm tree抽出当前联合索引相关的SEL_ROOT，如果没有那么就不能执行skip scan
  17.     cur_index_range_tree = get_index_range_tree(cur_index, tree, param);
  18.     // 遍历当前索引涉及的所有列
  19.     for (cur_part = cur_index_info->key_part; cur_part != end_part;
  20.          cur_part++, part++) {
  21.       // 从mm tree获取当前列相关的SEL_ROOT，就是查询条件涉及的列
  22.       get_sel_root_for_keypart();
  23.       1、如果找到联合索引前缀列相关条件并且不是等号条件，那么就判断为"prefix_not_const_equality"并且跳到下一个索引
  24.       2、如果找到联合索引前缀列以外的列相关条件，以遇到的第一个条件作为skip scan的条件。
  25.     }
  26.     // 针对联合索引的前缀列估计范围内包含的行数，用在条件包含前缀列有等号条件的情况
  27.     quick_prefix_records = check_quick_select();
  28.     // 计算skip_scan的行数和cost
  29.     cost_skip_scan();
  30.     // 最后生成AccessPath，包含IndexSkipScanParameters
  31.   }
  32. }
  33. // 获取skip scan的行数和cost结果
  34. void cost_skip_scan() {
  35.   table_records = table->file->stats.records;
  36.   // 如果可以根据前缀列估算出行数，那么就用估算的值，如果不能就用全表的行数。
  37.   if (quick_prefix_records == HA_POS_ERROR)
  38.     skip_scan_records = table_records;
  39.   else
  40.     skip_scan_records = quick_prefix_records;
  41.   // 首先根据联合索引前缀列数值获取每个唯一数组包含的相同数的数量
  42.   /* Compute the number of keys in a group. */
  43.   if (index_info->has_records_per_key(distinct_key_parts - 1)) {
  44.     keys_per_group = index_info->records_per_key(distinct_key_parts - 1);
  45.   } else
  46.     keys_per_group = guess_rec_per_key(table, index_info, distinct_key_parts);
  48.   num_groups = (uint)(skip_scan_records / keys_per_group) + 1;
  49.   num_groups = std::max(num_groups, 1U);
  51.   // 接着根据可以用于skip scan的列，获取这个列的不同唯一数值包含的相同数的数量
  52.     if (index_info->has_records_per_key(distinct_key_parts))
  53.       keys_per_range = index_info->records_per_key(distinct_key_parts);
  54.     else
  55.       keys_per_range =
  56.           guess_rec_per_key(table, index_info, distinct_key_parts + 1);
  57.     //
  58.     double max_distinct_values = max(
  59.         1.0, static_cast<double>(uint(keys_per_group) / uint(keys_per_range)));
  60.    // 根据条件估算过滤系数
  61.    float filtering_effect = where_cond->get_filtering_effect();
  62.    // 计算得出的总行数
  63.    *records = max(ha_rows(1), ha_rows(skip_scan_records * filtering_effect));
  64.    // 最后估算IO cost和CPU cost
  65.    Cost_estimate cost_skip_scan =
  66.       table->file->index_scan_cost(key, num_groups, *records);
  67. }
  69. 最后具体实现过程见代码IndexSkipScanIterator::Read()，这里不再展开赘述。
复制代码
表一：不能利用 skip_scan 的场合
[table][tr]场合说明[/tr][tr][td]sql语句带有ORDER DESC[/td][td]倒序排序不支持skip_scan[/td][/tr][tr][td]sql语句带有group by[/td][td][/td][/tr][tr][td]没有生成mm tree[/td][td]条件必须带有列相关的范围[/td][/tr][tr][td]sql语句带有distinct[/td][td][/td][/tr][tr][td]选择项包含聚合函数和DISTINCT[/td][td][/td][/tr][tr][td]查询语句的Item包含不在联合索引的列[/td][td][/td][/tr][tr][td]联合索引前缀列涉及的条件不为等号条件[/td][td]比如where c110[/td][/tr][tr][td]联合索引非前缀列涉及的条件生成的mm tree元素超过1个[/td][td]比如where c2>10 or c2 EXPLAIN SELECT c1, c2 FROM t1 WHERE c2 > 40;+----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+| id | select_type | table | partitions | type  | possible_keys | key   | key_len | ref  | rows | filtered | Extra                                  |+----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+|  1 | SIMPLE      | t1    | NULL       | range | i1_t1         | i1_t1 | 10      | NULL |   53 |   100.00 | Using where; Using index for skip scan |+----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+                  "skip_scan_range": {                    "potential_skip_scan_indexes": [                      {                        "index": "i1_t1",                        "tree_travel_cost": 0.4,                        "num_groups": 3, -- 盘算方式见下面                        "rows": 53, -- 盘算方式见下面                        "cost": 11.483                      }                    ]                  },                  "best_skip_scan_summary": {                    "type": "skip_scan",                    "index": "i1_t1",                    "key_parts_used_for_access": [                      "c1",                      "c2"                    ],                    "range": [                      "40 < c2"                    ],                    "chosen": true                  },/* num_groups和rows盘算过程：skip_scan_records = table->file->stats.records = 160keys_per_group = 条件涉及的第一个列的每个key包含的值 = 80keys_per_range = 条件涉及列的每个key包含的值 = 17.7777786num_groups = (skip_scan_records / keys_per_group) + 1 = 160 / 80 + 1 = 3   --->num_groups结果max_distinct_values = keys_per_group / keys_per_range = 80 / 17.7777786 = 4filtering_effect = max(1/4, COND_FILTER_INEQUALITY) = 0.333records = skip_scan_records * filtering_effect = 160 * 0.333 = 53  --->rows结果 */[/code]下面例子有的没用 skip scan 有的用了，区别仅在于包含的条件，根据条件最后生成的 mm tree 不同导致结果不同。
  1. greatsql> EXPLAIN SELECT c1, c2 FROM t1 WHERE c2 > 40;
  2. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+
  3. | id | select_type | table | partitions | type  | possible_keys | key   | key_len | ref  | rows | filtered | Extra                                  |
  4. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+
  5. |  1 | SIMPLE      | t1    | NULL       | range | i1_t1         | i1_t1 | 10      | NULL |   53 |   100.00 | Using where; Using index for skip scan |
  6. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------------+
  7.                   "skip_scan_range": {
  8.                     "potential_skip_scan_indexes": [
  9.                       {
  10.                         "index": "i1_t1",
  11.                         "tree_travel_cost": 0.4,
  12.                         "num_groups": 3, -- 计算方式见下面
  13.                         "rows": 53, -- 计算方式见下面
  14.                         "cost": 11.483
  15.                       }
  16.                     ]
  17.                   },
  18.                   "best_skip_scan_summary": {
  19.                     "type": "skip_scan",
  20.                     "index": "i1_t1",
  21.                     "key_parts_used_for_access": [
  22.                       "c1",
  23.                       "c2"
  24.                     ],
  25.                     "range": [
  26.                       "40 < c2"
  27.                     ],
  28.                     "chosen": true
  29.                   },
  31. /* num_groups和rows计算过程：
  32. skip_scan_records = table->file->stats.records = 160
  33. keys_per_group = 条件涉及的第一个列的每个key包含的值 = 80
  34. keys_per_range = 条件涉及列的每个key包含的值 = 17.7777786
  35. num_groups = (skip_scan_records / keys_per_group) + 1 = 160 / 80 + 1 = 3   --->num_groups结果
  36. max_distinct_values = keys_per_group / keys_per_range = 80 / 17.7777786 = 4
  37. filtering_effect = max(1/4, COND_FILTER_INEQUALITY) = 0.333
  38. records = skip_scan_records * filtering_effect = 160 * 0.333 = 53  --->rows结果 */
复制代码
四、总结

从上面 skip index 的代码我们了解了跳跃扫描的利用条件和利用场景，以及利用规则，这个功能让一些以前用不到联合索引的查询也可以用到索引，提高了服从，但也有一定的局限和缺点，要看具体表的情况来决定。

Enjoy GreatSQL
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

石小疯

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表