MySQL·源码分析·索引选择

Author: 冯惠(谈青)

优化器什么时候执行索引选择？

PolarDB 在做完永久的基于规则的转换（包括外连接转换成内连接、嵌套连接消除、合并视图或者派生表、子查询转换等）以及一些逻辑转换（如NOT消除、等值传递、常量计算和条件移除）之后，会选择表的最优访问方式，这时候会判断是否能使用索引加快数据获取。
表访问方式主要分为 Table Scan（全表扫描）、Index Look Up （ref访问）方式、Index Scan（索引扫描），Range Index Scan（索引范围查询）和一些替代的 Quick Range Scan（快速范围访问方式）。每一种分类是可以独立计算选出最佳方案，最终在所有类型的最佳方案中选择代价最低的访问方式。除了 Table Scan 是全表扫描方式之外，其余都属于索引扫描，只是根据索引的定义情况和利用索引的执行方式不同，区分了多种类型而已。
通常优化器使用索引的原则如下：

  • 索引列作为过滤条件出现在 WHERE、HAVING、ON 子句中，这样有利于利用索引过滤元组
  • 索引列是被连接的表（内表）对象的列且存在于连接条件中，连接条件会出现在 WHERE、ON、USING 子句中
  • 索引列出现在 AGGRE 子句中，例如在索引列上求 MIN、MAX 值等
  • 索引列出现在 GROUP BY 、ORDER BY 、DISTINCT，可以利用有序索引避免排序操作

MYSQL 访问类型介绍

访问类型，是较为重要的一个指标，结果值从好到坏依次是：
system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL ，一般来说，得保证查询至少达到range级别，最好能达到ref。

  • system：表仅有一行（=系统表）。
  • const：表中最多一个匹配行，它将在查询开始前先被读取。因为仅有一行，在这行的列值可被优化器的剩余部分认为是常数。const 类型用于用常数值比较 primary key 或 unique 索引的所有部分时。
  • eq_ref：对于每个来自于前面的表的行组合，从该表中读取一行。这可能是除了 const 类型外最好的连接类型。它用在一个索引的所有部分被连接使用并且索引是 UNIQUE 或 PRIMARY KEY 时。eq_ref 可以用于使用 = 操作符比较的带索引的列。比较值可以为常量或一个使用在该表前面所读取的表的列的表达式。
  • ref：对于每个来自于前面的表的行组合，所有匹配索引值的行将从这张表中读取。同时需要满足连接只使用键的最左前缀，且键不是 UNIQUE 或 PRIMARY KEY（换句话说，如果连接不能基于关键字选择单个行的话），则使用 ref。如果使用的键仅仅匹配少量行，该连接类型是不错的。ref 可以用于使用 = 或 <=> 操作符的带索引的列。
  • ref_or_null：该联接类型如同 ref，但是添加 了MySQL 可以专门搜索包含 NULL 值的行。在解决子查询中经常使用该连接类型的优化。
  • index_merge：该连接类型表示使用了索引合并优化方法。在这种情况下，key 列包含了使用的索引的清单，key_len 包含了使用的索引的最长的关键元素。
  • unique_subquery：该类型替换了下面形式的 IN 子查询的 ref：value IN (SELECT primary_key FROM single_table WHERE some_expr); unique_subquery 是一个索引查找函数，可以完全替换子查询，效率更高。
  • index_subquery：该类型类似于 unique_subquery。可以替换 IN 子查询，但只适合下列形式的子查询中的非唯一索引：value IN SELECT key_column FROM single_table WHERE some_expr
  • range：只检索给定范围的行，使用一个索引来选择行。key 列显示使用了哪个索引。key_len 包含所使用索引的最长关键元素。在该类型中 ref 列为 NULL。当使用=、<>、>、>=、<、<=、IS NULL、<=>、BETWEEN 或者 IN 操作符，用常量比较关键字列时，可以使用 range
  • index：该联接类型与 ALL 相同，除了只有索引树被扫描。这通常比 ALL 快，因为索引文件通常比数据文件小。
  • all：对于每个来自于先前的表的行组合，进行完整的表扫描。如果表是第一个没被标记为 const 的表，这通常性能很差。通常可以增加更多的索引而不要使用 ALL，使得行能基于前面的表中的常数值或列值被检索出。

使用 OPTIMIZER TRACE 查看索引选择

OPTIMIZER TRACE 可以展示 MYSQL 是如何进行优化并选择出最终执行计划的。我们可以使用这个工具看到所有可用的索引。
更详细的介绍可以看这篇文章：
https://zhuanlan.zhihu.com/p/475410214 庖丁解牛-图解查询分析和调优利器Optimizer Trace

开启优化器跟踪

  1. SET optimizer_trace = "enabled=on";
  2. SET optimizer_trace_max_mem_size=655350;
  3. <SQL>
  4. SELECT trace FROM information_schema.optimizer_trace 
  5. INTO OUTFILE <filename> LINES TERMINATED BY '';
  6. # 或者
  7. SELECT trace FROM information_schema.optimizer_trace \G
  8. SET optimizer_trace ="enabled=off";

Ref 方式（包括 ref/eq_ref/ref_or_null）

首先，PolarDB 优化器会递归的访问 WHERE 条件、挂在 outer joins 内表上的条件以及嵌套 joins 上携带的条件，并将其中出现的所有等值表达式都存储到Key_field对象的数组中。然后遍历该Key_field数组，并同时对比所有索引列，找到哪些字段是在索引列中出现，这些字段则可能可以使用索引，PolarDB 将所有这些字段都存储在对象Key_use数组中。最后，对Key_use进行处理，包括排序、删除无法使用的索引列。这时Key_use数组就是所有可以使用REF的索引列了。

Key_field 数据结构

  1. struct Key_field {
  2.   Key_field(Item_field *item_field, Item *val, uint level, uint optimize,
  3.             bool eq_func, bool null_rejecting, bool *cond_guard,
  4.             uint sj_pred_no)
  5.       : item_field(item_field),
  6.         val(val),
  7.         level(level),
  8.         optimize(optimize),
  9.         eq_func(eq_func),
  10.         null_rejecting(null_rejecting),
  11.         cond_guard(cond_guard),
  12.         sj_pred_no(sj_pred_no) {}
  13.   Item_field *item_field;  ///< Item representing the column
  14.   Item *val;               ///< May be empty if diff constant
  15.   uint level;
  16.   uint optimize;  ///< KEY_OPTIMIZE_*
  17.   bool eq_func;
  18.   /**
  19.     If true, the condition this struct represents will not be satisfied
  20.     when val IS NULL.
  21.     @sa Key_use::null_rejecting .
  22.   */
  23.   bool null_rejecting;
  24.   bool *cond_guard;  ///< @sa Key_use::cond_guard
  25.   uint sj_pred_no;   ///< @sa Key_use::sj_pred_no
  26. };

Key_use 数据结构

  1. class Key_use {
  2.  public:
  3.   TABLE_LIST *table_ref;  ///< table owning the index
  5.   /**
  6.     Value used for lookup into @c key. It may be an Item_field, a
  7.     constant or any other expression. If @c val contains a field from
  8.     another table, then we have a join condition, and the table(s) of
  9.     the field(s) in @c val should be before @c table in the join plan.
  10.   */
  11.   Item *val;
  13.   /**
  14.     All tables used in @c val, that is all tables that provide bindings
  15.     for the expression @c val. These tables must be in the plan before
  16.     executing the equi-join described by a Key_use.
  17.   */
  18.   table_map used_tables;
  19.   uint key;                  ///< number of index
  20.   uint keypart;              ///< used part of the index
  21.   uint optimize;             ///< 0, or KEY_OPTIMIZE_*
  22.   key_part_map keypart_map;  ///< like keypart, but as a bitmap
  23.   ha_rows ref_table_rows;    ///< Estimate of how many rows for a key value
  24.   /**
  25.     If true, the comparison this value was created from will not be
  26.     satisfied if val has NULL 'value'.
  27.     Not used if the index is fulltext (such index cannot be used for
  28.     equalities).
  29.   */
  30.   bool null_rejecting;
  31.   /**
  32.     !NULL - This Key_use was created from an equality that was wrapped into
  33.             an Item_func_trig_cond. This means the equality (and validity of
  34.             this Key_use element) can be turned on and off. The on/off state
  35.             is indicted by the pointed value:
  36.               *cond_guard == true @<=@> equality condition is on
  37.               *cond_guard == false @<=@> equality condition is off
  39.     NULL  - Otherwise (the source equality can't be turned off)
  41.     Not used if the index is fulltext (such index cannot be used for
  42.     equalities).
  43.   */
  44.   bool *cond_guard;
  45.   /**
  46.      0..63    @<=@> This was created from semi-join IN-equality # sj_pred_no.
  47.      UINT_MAX  Otherwise
  49.      Not used if the index is fulltext (such index cannot be used for
  50.      semijoin).
  52.      @see get_semi_join_select_list_index()
  53.   */
  54.   uint sj_pred_no;
  56.   /*
  57.     The three members below are different from the rest of Key_use: they are
  58.     set only by Optimize_table_order, and they change with the currently
  59.     considered join prefix.
  60.   */
  62.   /**
  63.      The key columns which are equal to expressions depending only of earlier
  64.      tables of the current join prefix.
  65.      This information is stored only in the first Key_use of the index.
  66.   */
  67.   key_part_map bound_keyparts;
  69.   /**
  70.      Fanout of the ref access path for this index, in the current join
  71.      prefix.
  72.      This information is stored only in the first Key_use of the index.
  73.   */
  74.   double fanout;
  76.   /**
  77.     Cost of the ref access path for the current join prefix, i.e. the
  78.     cost of using ref access once multiplied by estimated number of
  79.     partial rows from tables earlier in the join sequence.
  80.     read_cost does NOT include cost of processing rows on the
  81.     server side (row_evaluate_cost).
  83.     Example: If the cost of ref access on this index is 5, and the
  84.     estimated number of partial rows from earlier tables is 10,
  85.     read_cost=50.
  87.     This information is stored only in the first Key_use of the index.
  88.   */
  89.   double read_cost;
  90. };

update_ref_and_keys()

代码实现在 update_ref_and_keys() 函数中。
函数调用栈如下：

  1. #0 update_ref_and_keys
  2. #1 make_join_plan
  3. #2 JOIN::optimize
  1. 函数通过add_key_fields()将所有的可能用到的索引字段，全部都放到key_fields数组中
  2. 调用add_key_part()将所有的key_fields存放到KEYUSE数组
  3. 调用sort_and_remove_keyuse()移除KEYUSE数组中无法使用的索引（例如使用了索引的第二个字段），对KEYUSE排序，相同的KEY的字段放一起

对所有条件都是通过调用 add_key_fields() 函数去构造 Key_field 对象的，这些条件可以分为两种情况：

  • FUNC_ITEM，即只由一个 atomic 条件组成
  • COND_ITEM，即由若干个 AND 和 OR 连接起来的条件
  1. FUNC_ITEM 类型：

可以细分为下面四种情况下才能构造可用的 Key_field，总的来说能转化为等值条件的才能建立对应的 Key_field。

  • OPTIMIZE_KEY 类型
    • Item_func::BETWEEN : ‘a between low and high’ 转换为 ‘a >= low AND a <= high’
      • 当 low=high 时，可以创建对应的 Key_field
    • Item_func::MEMBER_OF_FUN : The predicate is IN ()
    • Item_func::IN_FUNC 和 Item_func::NE_FUNC(即 <>)
    • 条件为 (column1, column2, … ) IN ((const1_1, const1_2), …)，同时存在 (column1, column2, …) 上的索引
  • OPTIMIZE_OP 类型
    • Item_bool_func2 : 2个 string 做计算
    • Item_func_like
  • OPTIMIZE_NULL 类型
    • column IS [NOT] NULL：对 column IS NULL 才会生成 Key_field，column IS NOT NULL 不是等值表达式，因此不会有对应的 Key_field 生成。
  • OPTIMIZE_EQUAL 类型
    • field1=field2=…=const_item 类型的条件，可以对每个 field=const_item 条件生成对应的 Key_field
    • field1=field2=…=fieldn 类型的条件，对于任意两个不同的 field 组成的等值式，尽可能生成 Key_field
  1. COND_ITEM 类型

这种条件是指由 AND 和 OR 连接起来的条件。
关系型运算符优先级高到低为：NOT > AND > OR
如果 where 后面有 OR 条件的话，则 OR 自动会把左右的查询条件分开。也就是说，在没有小括号 () 的干预下，总是先执行 AND 语句，再执行 OR 语句。

  1. select * from table where  条件1 AND 条件2 OR 条件3
  2. 等价于
  3. select * from table where  ( 条件1 AND 条件2 ) OR 条件3
  5. select * from table where  条件1 AND 条件2 OR 条件3 AND 条件4
  6. 等价于
  7. select * from table where  ( 条件1 AND 条件2 ) OR ( 条件3 AND 条件4 )
  • 如果是 COND_AND_FUNC，即由 AND 连接的 predicate，递归处理由 AND 连接的每个谓词，and_level 不变。换句话说，and_level 相同的 Key_field 之间是由同一层的 AND 连接的，它的作用是将 conjunctions 聚集在一起。
  • 如果是 COND_OR_FUNC，即由 OR 连接的 predicate，递归处理由 OR 连接的每个谓词，每次处理之前 and_level 需要自增。这里还有一个 merge_key_fields() 的逻辑，是对 OR 连接的谓词之间尽可能做 merge 操作：
    1. t2.key = t1.field OR t2.key = t1.field 合并之后，null_rejecting=true
    2. t2.key = t1.field OR t2.key <=> t1.field 合并之后，null_rejecting=false
    3. Key_field(field = expression) OR Key_field(field IS NULL) 可以做 merge，生成 Key_field(field = expression, optimize = KEY_OPTIMIZE_REF_OR_NULL, null_rejecting = false)
    4. 对于即使两个 Key_field 中的 field 相同，也不能 merge 的 Key，例如 field=2 OR field=3，这种情况不能使用 Index Look Up 方式，所以会去掉这些 Key_field，在后续以 Range 方式访问的时候再处理。
    5. 最后将 OR 两边无法 merge 的 key_field 都去掉
  1. 例：
  2. 对于 a=0 AND b=0 OR a IS NULL，
  3. 可以生成三个 Key_field:
  4. 1. Key_field(a=0, and_level=1)
  5. 2. Key_field(a=0, and_level=1)
  6. 3. Key_field(a IS NULL, and_level=2)
  8. merge 由 OR 连接的左右条件的流程：
  10. ->对于 a=0：
  11.     ->判断 a IS NULL 是否可以合并
  12.       ->可以合并
  13.           ->将 a IS NULL 合并入 a=0 中，标注 KEY_OPTIMIZE_REF_OR_NULL，null_rejecting 为 false
  14. ->对于 b=0：
  15.     ->判断 a IS NULL 是否可以合并
  16.       ->不能合并
  17. ->将所有没有被合并的 Key_field 去掉
  19. 最终剩下一个 Key_field：
  20. Key_field(a=0, and_level=3, KEY_OPTIMIZE_REF_OR_NULL, null_rejecting=false)

除此之外，如果是 TRIG_COND_FUNC。这种情况是对子查询的优化，可以被下推到子查询的条件会被构造为 Item_func_trig_cond，也对其调用 add_key_fields() 获取可用的 Key_field。
最后，排序和删除不可用的索引列之后，剩下的 KEY_USE 数组是所有可用的 ref 访问方式的索引列。

使用 OPTIMIZER TRACE 查看 ref 类型索引

通过 OPTIMIZER TRACE 可以查看每个表可以使用的 ref 索引，用于后续计算访问和连接代价。

  1. {
  2.   "ref_optimizer_key_uses": [
  3.     {
  4.     "table": "`part`",
  5.     "field": "p_partkey",
  6.     "equals": "`lineitem`.`l_partkey`",
  7.     "null_rejecting": true
  8.     },
  9.     {
  10.     "table": "`supplier`",
  11.     "field": "s_suppkey",
  12.     "equals": "`lineitem`.`l_suppkey`",
  13.     "null_rejecting": true
  14.     },
  15.     ......
  16.     {
  17.     "table": "`region`",
  18.     "field": "r_regionkey",
  19.     "equals": "`n1`.`n_regionkey`",
  20.     "null_rejecting": true
  21.     }
  22.   ]
  23. },

Range 方式

接下来需要遍历每张表并评估访问方式的代价。首先会计算全表扫描的代价，接着会对 Index Scan 访问的几种方式进行代价评估。
Index Scan 可以分为下面几种方式：

  • Index Scan (covering) 覆盖索引
    • 可用的覆盖索引已经被标记在 TABLE->covering_keys 中，会从中寻找最短的覆盖索引，即包含的 key_parts 尽可能少的覆盖索引。
    • 有的时候即使有覆盖索引，但由于过滤性不强可能导致全表扫描方式代价和覆盖索引代价相近，从而会选择全表扫描。
  • Index Range Scan（实现类 QUICK_RANGE_SELECT）
  • Index for grouping（实现类 QUICK_GROUP_MIN_MAX_SELECT）
  • Index skip scan（实现类 QUICK_SKIP_SCAN_SELECT）
  • Index Merge（实现类 QUICK_INDEX_MERGE_SELECT）
  • Row Order Merge
    • 实现类 QUICK_ROR_INTERSECT_SELECT
    • 实现类 QUICK_ROR_UNION_SELECT

除了 outer join 的内表，对其余的每张表，需要获取最优的 QUICK access method。代码实现在test_quick_select 函数中。

Quick Range Scan 介绍

Quick Range Scan 含义如下：

  1. QUICK_RANGE_SELECT

在单一索引上进行范围扫描。records 会按照索引次序返回。

  1. QUICK_INDEX_MERGE_SELECT

使用 QUICK_RANGE_SELECT 完成元组的获取，使用 Unique 类完成消除重复行的工作。

  1. QUICK_ROR_INTERSECT_SELECT

Rowid-Ordered Retrieval (ROR)，基于元组标识即 rowid 顺序的元组获取方式。
使用多个 QUICK_RANGE_SELECTs 完成数据获取，每个 QUICK_RANGE_SELECT 返回的数据按照 rowid 排序，对返回的多组数据取交集。

  1. QUICK_ROR_UNION_SELECT

使用多个 QUICK_RANGE_SELECTs 完成数据获取，每个 QUICK_RANGE_SELECT 返回的数据按照 rowid 排序，对返回的多组数据取并集。

  1. QUICK_GROUP_MIN_MAX_SELECT

对于单表查询中包含 GROUP BY 子句且有 MIN/MAX 聚集函数（或包含有 SELECT DISTINCT 子句）的SQL 进行索引扫描，提供依据索引或索引的前缀进行索引扫描，从而完成分组操作下的最值求解。

  1.   This class provides a specialized index access method for GROUP-BY queries
  2.   of the forms:
  4.        SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
  5.          FROM T
  6.         WHERE [RNG(A_1,...,A_p ; where p <= k)]
  7.          [AND EQ(B_1,...,B_m)]
  8.          [AND PC(C)]
  9.          [AND PA(A_i1,...,A_iq)]
  10.        GROUP BY A_1,...,A_k;
  12.     or
  14.        SELECT DISTINCT A_i1,...,A_ik
  15.          FROM T
  16.         WHERE [RNG(A_1,...,A_p ; where p <= k)]
  17.          [AND PA(A_i1,...,A_iq)];
  1. QUICK_SKIP_SCAN_SELECT

MySQL 从 8.0.13 版本开始支持一种新的 range scan 方式，称为 Loose Skip Scan。在之前的版本中，如果要使用索引进行扫描，条件必须满足索引前缀列，比如索引 idx(col1,col2), 如果 where 条件只包含 col2 的话，是无法有效的使用 idx 的, 它需要扫描索引上所有的行，然后再根据 col2 上的条件过滤。
而 Loose Skip Scan 可以避免全量索引扫描，而是根据每个 col1 上的值 + col2 上的条件，启动多次 range scan。每次 range scan 根据构建的 key 值直接在索引上定位，直接忽略了那些不满足条件的记录。
但是，必须满足下面条件的查询才能使用 skip scan ：

  1. 查询语句需要是下面的形式
  1. 查询语句需要是下面的形式：
  3.        SELECT A_1,...,A_k, B_1,...,B_m, C
  4.          FROM T
  5.         WHERE
  6.          EQ(A_1,...,A_k)
  7.          AND RNG(C);
  1. 表 T 至少拥有一个索引 I 是下面展示的形式，其中，Keyparts A 和 D 可能为空，但是 B 和 C 必须为非空。
  1. I = <A_1,...,A_k, B_1,..., B_m, C ,[D_1,...,D_n]>
  1. 单表
  2. 不能包含 GROUP BY 子句或者 SELECT DISTINCT
  3. 查询语句中涉及的列必须都在索引中，换言之，必须是覆盖索引
  4. 在 A_1…A_k 上的谓词必须是等值谓词，同时需要值为常量，’IN’ 操作符是被允许的。
  5. 查询语句必须是合取查询，换言之，顶层是由 AND 连接，且下层只能由 OR 连接
  1. (COND1(kp1) OR COND2(kp1)) AND (COND1(kp2) OR ...) AND ...
  1. 在 C 列上的必须是一个 range 条件
  2. 允许在 D 列上拥有条件，但在 D 上的条件必须与 C 上的范围条件之间以 AND 连接。

test_quick_select()

test_quick_select()函数流程如下：

  1. 计算 table scan cost
  2. 分配 PARAM 结构，初始化相关字段
  3. 对表上每个可用的 key，加入 param.key[] 数组，其中每个 key_part，对应一个 KEY_PART 对象(param.key_parts数组)
  4. 考虑是否能使用覆盖索引，首先调用find_shortest_key()函数，选择KEY::key_length最小的可用索引。接着计算索引扫描代价，比较是否比 table scan 代价更低。
  5. 考虑各种 range scan
    1. 调用get_mm_tree()函数，根据 ON/WHERE 携带的条件，构建 range tree。
    2. get_best_group_min_max() 尝试为 group by 构建 QUICK_GROUP_MIN_MAX_SELECT。
    3. get_best_skip_scan()，对于单表非 group by，尝试构建 skip scan
    4. get_key_scans_params()函数对 PARAM.key[] 中的 key，依次调用 check_quick_select，计算得到的行数 found_records 和代价 cost。选择更低代价的 range，创建 TRP_RANGE 结构。
    5. get_best_ror_intersect
    6. get_best_disjunct_quick，计算 index merge union 的代价
  6. make_quick()，找到最优的 best_trp 后，创建 QUICK_SELECT_I 对应的子类对象，设置给JOIN_TAB

possible keys 收集

在进行 Range 分析前，会将所有可能用于分析的索引都放入：

  • join_tab->const_keys
  • join_tab->skip_scan_keys

最后分析的索引合集为：join_tab->const_keys 和 join_tab->skip_scan_keys 的并集，再与 TABLE->keys_in_use_for_query 取交集得到的集合。对这个集合中的 keys 调用 test_quick_select() 进行分析。

join_tab->const_keys 中添加可用索引的时机：

  1. 对查询中的条件，进行 ref 索引分析时，会将满足条件的索引加入到 join_tab->const_keys 和 join_tab->keys 集合中，代码实现在 add_key_field 函数中。
  2. 对常量表添加谓词之后，同样会将满足条件的索引加入到 join_tab->const_keys 和 join_tab->keys 集合中，代码实现在 update_sargable_from_const 函数中。
  3. 如果查询包含 GROUP BY 子句，寻找包含全部 GROUP BY fields 的索引，这些索引会被加入到 join_tab->const_keys 和 join_tab->keys。代码实现在 add_loose_index_scan_and_skip_scan_keys 函数中。
  4. 如果查询包含 SELECT DISTINCT 子句，寻找包含全部 SELECT fields 的索引，这些索引会被加入到 join_tab->const_keys 和 join_tab->keys。后续会判断能否使用 QUICK_GROUP_MIN_MAX_SELECT 快速访问方式。代码实现在 add_loose_index_scan_and_skip_scan_keys 函数中。
  5. 如果查询中包含 SELECT AGGFN(DISTINCT col)，寻找包含聚合函数作用的字段的索引，这些索引会被加入到 join_tab->const_keys 和 join_tab->keys，用于判断后续是否可以使用 loose index scan（QUICK_GROUP_MIN_MAX_SELECT）。详细来说，会检查每一个出现的 COUNT(DISTINCT)、AVG(DISTINCT) 和 SUM(DISTINCT)，只要 SELECT clause 中所有的 aggregate distinct functions 引用相同的字段，就可以使用 loose index scan。例如：
    1. SELECT AGGFN(DISTINCT a, b), AGGFN(DISTINCT b, a)… => can use LIS
    2. SELECT AGGFN(DISTINCT a), AGGFN(DISTINCT a) … => can use LIS
    3. SELECT AGGFN(DISTINCT a, b), AGGFN(DISTINCT a) … => cannot use LIS
    4. SELECT AGGFN(DISTINCT a), AGGFN(DISTINCT b) … => cannot use LIS

代码实现在 add_loose_index_scan_and_skip_scan_keys 函数中。

join_tab->skip_scan_keys 中添加可用索引的时机：

  1. 如果查询既不包含 GROUP BY 子句，又不包含 SELECT AGGFN(DISTINCT col)，也不包含 SELECT DISTINCT，收集 where 条件中出现的列，将包含这些列的所有索引，加入到 join_tab->skip_scan_keys 中，用于后续判断能否使用 skip scan 访问方式。代码实现在 add_loose_index_scan_and_skip_scan_keys 函数中。

使用 OPTIMIZER TRACE 查看 range 类型索引

  1. "rows_estimation": [
  2.   {
  3.     "table": "`salaries`",
  4.     "range_analysis": {
  5.       "table_scan": {
  6.         "rows": 2838216,
  7.         "cost": 286799
  8.       } /* table_scan */,
  9.       "potential_range_indexes": [
  10.         {
  11.           "index": "PRIMARY",
  12.           "usable": false,
  13.           "cause": "not_applicable"
  14.         },
  15.         {
  16.           "index": "salaries_from_date_to_date_index",
  17.           "usable": true,
  18.           "key_parts": [
  19.             "from_date",
  20.             "to_date",
  21.             "emp_no"
  22.           ] /* key_parts */
  23.         }
  24.       ] /* potential_range_indexes */,
  25.       "setup_range_conditions": [
  26.       ] /* setup_range_conditions */,
  27.       "group_index_range": {
  28.         "chosen": false,
  29.         "cause": "not_group_by_or_distinct"
  30.       } /* group_index_range */,
  31.       "skip_scan_range": {
  32.         "potential_skip_scan_indexes": [
  33.           {
  34.             "index": "salaries_from_date_to_date_index",
  35.             "usable": false,
  36.             "cause": "query_references_nonkey_column"
  37.           }
  38.         ] /* potential_skip_scan_indexes */
  39.       } /* skip_scan_range */,
  40.       "analyzing_range_alternatives": {
  41.         "range_scan_alternatives": [
  42.           {
  43.             "index": "salaries_from_date_to_date_index",
  44.             "ranges": [
  45.               "0xda840f <= from_date <= 0xda840f AND 0xda860f <= to_date <= 0xda860f"
  46.             ] /* ranges */,
  47.             "index_dives_for_eq_ranges": true,
  48.             "rowid_ordered": true,
  49.             "using_mrr": false,
  50.             "index_only": false,
  51.             "rows": 86,
  52.             "cost": 50.909,
  53.             "chosen": true
  54.           }
  55.         ] /* range_scan_alternatives */,
  56.         "analyzing_roworder_intersect": {
  57.           "usable": false,
  58.           "cause": "too_few_roworder_scans"
  59.         } /* analyzing_roworder_intersect */
  60.       } /* analyzing_range_alternatives */,
  61.       "chosen_range_access_summary": {
  62.         "range_access_plan": {
  63.           "type": "range_scan",
  64.           "index": "salaries_from_date_to_date_index",
  65.           "rows": 86,
  66.           "ranges": [
  67.             "0xda840f <= from_date <= 0xda840f AND 0xda860f <= to_date <= 0xda860f"
  68.           ] /* ranges */
  69.         } /* range_access_plan */,
  70.         "rows_for_plan": 86,
  71.         "cost_for_plan": 50.909,
  72.         "chosen": true
  73.       } /* chosen_range_access_summary */
  74.     } /* range_analysis */}
  75. ] /* rows_estimation */

参考资料

https://zhuanlan.zhihu.com/p/475410214 庖丁解牛-图解查询分析和调优利器Optimizer Trace
https://dev.mysql.com/doc/refman/8.0/en/group-by-optimization.html
https://dev.mysql.com/doc/refman/8.0/en/order-by-optimization.html
https://dev.mysql.com/doc/refman/8.0/en/range-optimization.html
https://dev.mysql.com/doc/refman/8.0/en/index-merge-optimization.html
https://dev.mysql.com/doc/refman/8.0/en/distinct-optimization.html

原文：http://mysql.taobao.org/monthly/2023/07/02/