Author: 冯惠(谈青)
PolarDB 在做完永久的基于规则的转换（包括外连接转换成内连接、嵌套连接消除、合并视图或者派生表、子查询转换等）以及一些逻辑转换（如NOT消除、等值传递、常量计算和条件移除）之后，会选择表的最优访问方式，这时候会判断是否能使用索引加快数据获取。
表访问方式主要分为 Table Scan（全表扫描）、Index Look Up （ref访问）方式、Index Scan（索引扫描），Range Index Scan（索引范围查询）和一些替代的 Quick Range Scan（快速范围访问方式）。每一种分类是可以独立计算选出最佳方案，最终在所有类型的最佳方案中选择代价最低的访问方式。除了 Table Scan 是全表扫描方式之外，其余都属于索引扫描，只是根据索引的定义情况和利用索引的执行方式不同，区分了多种类型而已。
通常优化器使用索引的原则如下：
访问类型，是较为重要的一个指标，结果值从好到坏依次是：
system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL ，一般来说，得保证查询至少达到range级别，最好能达到ref。
OPTIMIZER TRACE 可以展示 MYSQL 是如何进行优化并选择出最终执行计划的。我们可以使用这个工具看到所有可用的索引。
更详细的介绍可以看这篇文章：
https://zhuanlan.zhihu.com/p/475410214 庖丁解牛-图解查询分析和调优利器Optimizer Trace
SET optimizer_trace = "enabled=on";
SET optimizer_trace_max_mem_size=655350;
<SQL>
SELECT trace FROM information_schema.optimizer_trace
INTO OUTFILE <filename> LINES TERMINATED BY '';
# 或者
SELECT trace FROM information_schema.optimizer_trace \G
SET optimizer_trace ="enabled=off";
首先，PolarDB 优化器会递归的访问 WHERE 条件、挂在 outer joins 内表上的条件以及嵌套 joins 上携带的条件，并将其中出现的所有等值表达式都存储到Key_field对象的数组中。然后遍历该Key_field数组，并同时对比所有索引列，找到哪些字段是在索引列中出现，这些字段则可能可以使用索引，PolarDB 将所有这些字段都存储在对象Key_use数组中。最后，对Key_use进行处理，包括排序、删除无法使用的索引列。这时Key_use数组就是所有可以使用REF的索引列了。
struct Key_field {
Key_field(Item_field *item_field, Item *val, uint level, uint optimize,
bool eq_func, bool null_rejecting, bool *cond_guard,
uint sj_pred_no)
: item_field(item_field),
val(val),
level(level),
optimize(optimize),
eq_func(eq_func),
null_rejecting(null_rejecting),
cond_guard(cond_guard),
sj_pred_no(sj_pred_no) {}
Item_field *item_field; ///< Item representing the column
Item *val; ///< May be empty if diff constant
uint level;
uint optimize; ///< KEY_OPTIMIZE_*
bool eq_func;
/**
If true, the condition this struct represents will not be satisfied
when val IS NULL.
@sa Key_use::null_rejecting .
*/
bool null_rejecting;
bool *cond_guard; ///< @sa Key_use::cond_guard
uint sj_pred_no; ///< @sa Key_use::sj_pred_no
};
class Key_use {
public:
TABLE_LIST *table_ref; ///< table owning the index
/**
Value used for lookup into @c key. It may be an Item_field, a
constant or any other expression. If @c val contains a field from
another table, then we have a join condition, and the table(s) of
the field(s) in @c val should be before @c table in the join plan.
*/
Item *val;
/**
All tables used in @c val, that is all tables that provide bindings
for the expression @c val. These tables must be in the plan before
executing the equi-join described by a Key_use.
*/
table_map used_tables;
uint key; ///< number of index
uint keypart; ///< used part of the index
uint optimize; ///< 0, or KEY_OPTIMIZE_*
key_part_map keypart_map; ///< like keypart, but as a bitmap
ha_rows ref_table_rows; ///< Estimate of how many rows for a key value
/**
If true, the comparison this value was created from will not be
satisfied if val has NULL 'value'.
Not used if the index is fulltext (such index cannot be used for
equalities).
*/
bool null_rejecting;
/**
!NULL - This Key_use was created from an equality that was wrapped into
an Item_func_trig_cond. This means the equality (and validity of
this Key_use element) can be turned on and off. The on/off state
is indicted by the pointed value:
*cond_guard == true @<=@> equality condition is on
*cond_guard == false @<=@> equality condition is off
NULL - Otherwise (the source equality can't be turned off)
Not used if the index is fulltext (such index cannot be used for
equalities).
*/
bool *cond_guard;
/**
0..63 @<=@> This was created from semi-join IN-equality # sj_pred_no.
UINT_MAX Otherwise
Not used if the index is fulltext (such index cannot be used for
semijoin).
@see get_semi_join_select_list_index()
*/
uint sj_pred_no;
/*
The three members below are different from the rest of Key_use: they are
set only by Optimize_table_order, and they change with the currently
considered join prefix.
*/
/**
The key columns which are equal to expressions depending only of earlier
tables of the current join prefix.
This information is stored only in the first Key_use of the index.
*/
key_part_map bound_keyparts;
/**
Fanout of the ref access path for this index, in the current join
prefix.
This information is stored only in the first Key_use of the index.
*/
double fanout;
/**
Cost of the ref access path for the current join prefix, i.e. the
cost of using ref access once multiplied by estimated number of
partial rows from tables earlier in the join sequence.
read_cost does NOT include cost of processing rows on the
server side (row_evaluate_cost).
Example: If the cost of ref access on this index is 5, and the
estimated number of partial rows from earlier tables is 10,
read_cost=50.
This information is stored only in the first Key_use of the index.
*/
double read_cost;
};
update_ref_and_keys()代码实现在 update_ref_and_keys() 函数中。
函数调用栈如下：
#0 update_ref_and_keys
#1 make_join_plan
#2 JOIN::optimize
add_key_fields()将所有的可能用到的索引字段，全部都放到key_fields数组中add_key_part()将所有的key_fields存放到KEYUSE数组sort_and_remove_keyuse()移除KEYUSE数组中无法使用的索引（例如使用了索引的第二个字段），对KEYUSE排序，相同的KEY的字段放一起对所有条件都是通过调用 add_key_fields() 函数去构造 Key_field 对象的，这些条件可以分为两种情况：
可以细分为下面四种情况下才能构造可用的 Key_field，总的来说能转化为等值条件的才能建立对应的 Key_field。
这种条件是指由 AND 和 OR 连接起来的条件。
关系型运算符优先级高到低为：NOT > AND > OR
如果 where 后面有 OR 条件的话，则 OR 自动会把左右的查询条件分开。也就是说，在没有小括号 () 的干预下，总是先执行 AND 语句，再执行 OR 语句。
select * from table where 条件1 AND 条件2 OR 条件3
等价于
select * from table where ( 条件1 AND 条件2 ) OR 条件3
select * from table where 条件1 AND 条件2 OR 条件3 AND 条件4
等价于
select * from table where ( 条件1 AND 条件2 ) OR ( 条件3 AND 条件4 )
Key_field 之间是由同一层的 AND 连接的，它的作用是将 conjunctions 聚集在一起。merge_key_fields() 的逻辑，是对 OR 连接的谓词之间尽可能做 merge 操作：
Key_field 中的 field 相同，也不能 merge 的 Key，例如 field=2 OR field=3，这种情况不能使用 Index Look Up 方式，所以会去掉这些 Key_field，在后续以 Range 方式访问的时候再处理。key_field 都去掉例：
对于 a=0 AND b=0 OR a IS NULL，
可以生成三个 Key_field:
1. Key_field(a=0, and_level=1)
2. Key_field(a=0, and_level=1)
3. Key_field(a IS NULL, and_level=2)
merge 由 OR 连接的左右条件的流程：
->对于 a=0：
->判断 a IS NULL 是否可以合并
->可以合并
->将 a IS NULL 合并入 a=0 中，标注 KEY_OPTIMIZE_REF_OR_NULL，null_rejecting 为 false
->对于 b=0：
->判断 a IS NULL 是否可以合并
->不能合并
->将所有没有被合并的 Key_field 去掉
最终剩下一个 Key_field：
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 索引，用于后续计算访问和连接代价。
{
"ref_optimizer_key_uses": [
{
"table": "`part`",
"field": "p_partkey",
"equals": "`lineitem`.`l_partkey`",
"null_rejecting": true
},
{
"table": "`supplier`",
"field": "s_suppkey",
"equals": "`lineitem`.`l_suppkey`",
"null_rejecting": true
},
......
{
"table": "`region`",
"field": "r_regionkey",
"equals": "`n1`.`n_regionkey`",
"null_rejecting": true
}
]
},
接下来需要遍历每张表并评估访问方式的代价。首先会计算全表扫描的代价，接着会对 Index Scan 访问的几种方式进行代价评估。
Index Scan 可以分为下面几种方式：
除了 outer join 的内表，对其余的每张表，需要获取最优的 QUICK access method。代码实现在test_quick_select 函数中。
Quick Range Scan 含义如下：
在单一索引上进行范围扫描。records 会按照索引次序返回。
使用 QUICK_RANGE_SELECT 完成元组的获取，使用 Unique 类完成消除重复行的工作。
Rowid-Ordered Retrieval (ROR)，基于元组标识即 rowid 顺序的元组获取方式。
使用多个 QUICK_RANGE_SELECTs 完成数据获取，每个 QUICK_RANGE_SELECT 返回的数据按照 rowid 排序，对返回的多组数据取交集。
使用多个 QUICK_RANGE_SELECTs 完成数据获取，每个 QUICK_RANGE_SELECT 返回的数据按照 rowid 排序，对返回的多组数据取并集。
对于单表查询中包含 GROUP BY 子句且有 MIN/MAX 聚集函数（或包含有 SELECT DISTINCT 子句）的SQL 进行索引扫描，提供依据索引或索引的前缀进行索引扫描，从而完成分组操作下的最值求解。
This class provides a specialized index access method for GROUP-BY queries
of the forms:
SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
FROM T
WHERE [RNG(A_1,...,A_p ; where p <= k)]
[AND EQ(B_1,...,B_m)]
[AND PC(C)]
[AND PA(A_i1,...,A_iq)]
GROUP BY A_1,...,A_k;
or
SELECT DISTINCT A_i1,...,A_ik
FROM T
WHERE [RNG(A_1,...,A_p ; where p <= k)]
[AND PA(A_i1,...,A_iq)];
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 ：
查询语句需要是下面的形式：
SELECT A_1,...,A_k, B_1,...,B_m, C
FROM T
WHERE
EQ(A_1,...,A_k)
AND RNG(C);
I = <A_1,...,A_k, B_1,..., B_m, C ,[D_1,...,D_n]>
(COND1(kp1) OR COND2(kp1)) AND (COND1(kp2) OR ...) AND ...
test_quick_select()test_quick_select()函数流程如下：
PARAM 结构，初始化相关字段find_shortest_key()函数，选择KEY::key_length最小的可用索引。接着计算索引扫描代价，比较是否比 table scan 代价更低。get_mm_tree()函数，根据 ON/WHERE 携带的条件，构建 range tree。get_best_group_min_max() 尝试为 group by 构建 QUICK_GROUP_MIN_MAX_SELECT。get_best_skip_scan()，对于单表非 group by，尝试构建 skip scanget_key_scans_params()函数对 PARAM.key[] 中的 key，依次调用 check_quick_select，计算得到的行数 found_records 和代价 cost。选择更低代价的 range，创建 TRP_RANGE 结构。get_best_ror_intersectget_best_disjunct_quick，计算 index merge union 的代价make_quick()，找到最优的 best_trp 后，创建 QUICK_SELECT_I 对应的子类对象，设置给JOIN_TAB在进行 Range 分析前，会将所有可能用于分析的索引都放入：
最后分析的索引合集为：join_tab->const_keys 和 join_tab->skip_scan_keys 的并集，再与 TABLE->keys_in_use_for_query 取交集得到的集合。对这个集合中的 keys 调用 test_quick_select() 进行分析。
join_tab->const_keys 中添加可用索引的时机：
add_key_field 函数中。update_sargable_from_const 函数中。add_loose_index_scan_and_skip_scan_keys 函数中。add_loose_index_scan_and_skip_scan_keys 函数中。代码实现在 add_loose_index_scan_and_skip_scan_keys 函数中。
join_tab->skip_scan_keys 中添加可用索引的时机：
add_loose_index_scan_and_skip_scan_keys 函数中。"rows_estimation": [
{
"table": "`salaries`",
"range_analysis": {
"table_scan": {
"rows": 2838216,
"cost": 286799
} /* table_scan */,
"potential_range_indexes": [
{
"index": "PRIMARY",
"usable": false,
"cause": "not_applicable"
},
{
"index": "salaries_from_date_to_date_index",
"usable": true,
"key_parts": [
"from_date",
"to_date",
"emp_no"
] /* key_parts */
}
] /* potential_range_indexes */,
"setup_range_conditions": [
] /* setup_range_conditions */,
"group_index_range": {
"chosen": false,
"cause": "not_group_by_or_distinct"
} /* group_index_range */,
"skip_scan_range": {
"potential_skip_scan_indexes": [
{
"index": "salaries_from_date_to_date_index",
"usable": false,
"cause": "query_references_nonkey_column"
}
] /* potential_skip_scan_indexes */
} /* skip_scan_range */,
"analyzing_range_alternatives": {
"range_scan_alternatives": [
{
"index": "salaries_from_date_to_date_index",
"ranges": [
"0xda840f <= from_date <= 0xda840f AND 0xda860f <= to_date <= 0xda860f"
] /* ranges */,
"index_dives_for_eq_ranges": true,
"rowid_ordered": true,
"using_mrr": false,
"index_only": false,
"rows": 86,
"cost": 50.909,
"chosen": true
}
] /* range_scan_alternatives */,
"analyzing_roworder_intersect": {
"usable": false,
"cause": "too_few_roworder_scans"
} /* analyzing_roworder_intersect */
} /* analyzing_range_alternatives */,
"chosen_range_access_summary": {
"range_access_plan": {
"type": "range_scan",
"index": "salaries_from_date_to_date_index",
"rows": 86,
"ranges": [
"0xda840f <= from_date <= 0xda840f AND 0xda860f <= to_date <= 0xda860f"
] /* ranges */
} /* range_access_plan */,
"rows_for_plan": 86,
"cost_for_plan": 50.909,
"chosen": true
} /* chosen_range_access_summary */
} /* range_analysis */}
] /* 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