8.2.1.2-范围扫描优化

range访问方法使用一个单一索引来获取数据表中的一个子集，这个子集分布在单个或多个索引区间。这适用于单区间或多区间。下面的章节介绍在哪些条件下查询优化器会使用范围访问方法。

单列索引的范围访问。
多列索引的范围访问。
多值比较的等值区间优化。
跳过扫描区间优化。
行结构表达式的范围优化。
区间访问的内存使用优化。

单列索引的范围访问 #

对于一个单列索引来说，可以很容易用where条件中的相关条件来标识索引值间隔，这应该表示为范围条件，而不是 “间隔” 。（区间/间隔？）

一个单列索引的范围条件的定义如下：

对BTREE和HASH索引来说，使用=，<=>，IN(),IS NULL,或IS NOT NULL操作符来将键与常数值进行比较，是一个范围条件。
此外，对于BTREE来说，当使用>，>=，<=,BETWEEN，!=，或<>操作符来将键部分与常数值进行比较，或是开头不是通配符的LIKE比较。
对于所有索引类型，使用OR或AND的多区间条件，形成一个范围条件。

先前描述中的“常数值”是指下列情形之一：

查询字符串中的常数值。
来自于同一个连接中的const表或system表的列。
不相关的子查询的结果。
由以上子类型组成的任何表达式。下面是一些在WHERE条件中使用范围条件进行查询的例子：

select * from t1
    where key_col > 1
    and key_col < 10;

select * from t1
    where key_col = 1
    or key_col in(15,18,20);

select * from t1
    where key_col like 'ab%'
    or key_col between 'bar' and 'foo';

在优化器的常量处理阶段，一些非常量值会被转化为常量值。

MySQL尝试从where条件中提取出在每一个可能的索引上的范围条件。在提取过程中，无法形成范围区间的条件会被过滤掉，重叠的区间会被合并，产生空区间的条件会被删除。

在下面的语句中，key1是索引列，nonkey不是索引列：

select * from t1 where
    (key1 < 'abc' and (key1 like 'abcde%' or key1 like '%b')) or
    (key1 < 'bar' and nonkey = 4) or
    (key1 < 'uux' and key1 > 'z');

对于key1，优化器提取范围区间的过程如下：

从原始where条件开始：

(key1 < 'abc' and (key1 like 'abcde%' or key1 like '%b')) or
(key1 < 'bar' and nonkey = 4) or
(key1 < 'uux' and key1 > 'z');

移除nonkey=4和key1 like ‘%b’，因为它们无法用于范围扫描。移除它们的正确方法是使用TRUE替换它们，这样我们在做范围扫描时就不会错误任何记录。替换后如下：

(key1 < 'abc' and (key1 like 'abcde%' or TRUE)) or
(key1 < 'bar' and TRUE) or
(key1 < 'uux' and key1 > 'z');

折叠（简化）使用为true或false的条件：

(key1 like ‘abcde%’ or TRUE) is always true
(key1 < ‘uux’ and key1 > ‘z’) is always false 使用常量替换这些条件：

(key1 < 'abc' and true) or (key1 < 'bar' and true) or (false)

移除不需要的true和false常量：

(key1 < 'abc' or (key1 < 'bar')

合并重叠的区间，得到最终的扫描区间：

(key1 < 'bar')

总而言之，范围扫描使用的条件比where语句中的条件略少。MySQL会做一些额外的检查工作来过滤掉那些符合范围扫描条件，但是不符合where条件的。

范围扫描提取算法可以处理由AND和OR组成的任意深度的嵌套条件，它的输出不依赖于条件在where语句中的顺序。

对于空间索引的range访问，MySQL不支持区间合并。要解决这个限制，可以使用典型的SELECT … UNION 语句。除非，你将每个空间谓词都放在不同的选择中。

多列索引的范围访问 #

多列索引的区间条件是单列索引的区间条件的扩展。多列索引上的一个区间条件是由一个或多个索引键元组间隔组成的。索引键原则间隔跨越一个索引键元组集合，这些集合的排序顺序与索引的排序顺序相同。

举例说明，现在有一个多列索引key1(key_part1,key_part2,key_part3)，下面的索引键元组集合按照索引键顺序排列：

key_part1   key_part2   key_part3
null            1           'abc'
null            1           'xyz'
null            2           'foo'
1               1           'abc'
1               1           'xyz'
1               2           'abc'
2               1           'aaa'

条件key_part1 = 1定义了下面的区间：

(1,-inf,-info) <= (key_part1,key_part2,key_part3) < (1,+inf,+inf)

这个区间覆盖了第4个，第5个，和第6个元组，可以被range访问方法使用。

相反的是，条件key_part3 = ‘abc’ 没有定义一个区间，不能被range访问方法使用。

下面的文字更详细的介绍了多列索引上的区间条件是如何工作的。

对于hash索引，可以是用包含相同值的区间。这意味着只有下面这种条件产生的区间可以被range访问方法使用：

    key_part1 cmp const1
and key_part2 cmp const2
and ...
and key_partN cmp constN;

这里，const1,const2,… 是常来那个，cmp是操作符=, <=>,或is null,且相关条件覆盖所有的索引列。（就是说，有n个条件，对应着一个n列的索引。）例如，下面是一个包含3列的hash索引可以使用的区间：

    key_part1 = 1 and key_part2 is null and key_part3 = 'foo'

对于常量的定义，可以查阅 Range Access Method for Single-Part Indexes。

对于一个BTREE索引来说，使用and连接的多个条件可能会产生一个可用区间，每一个条件都是一个列通过以下操作符与常量值做比较：=、<=>、is null、 >、< 、>= 、<= 、 != 、 <>、between，或like（不能以通配符开头）。只要一个区间可以对应一个包含所有符合条件的单列元组，它就可以被使用。（如果使用了<>或!=，也可能是两个区间。）

只要操作符是=，<=>，或 is null，优化器就会尝试去匹配更多的列来进一步确定区间。如果操作符是>，<，>=，<=，!=，<>，between，或like，优化器会使用这个区间，但是不会继续尝试匹配更多的列。在下面的例子中，优化器会使用第一个判断条件（使用了=），也使用了第二个条件（>=），但是不会再尝试去匹配更多的列，不会使用第三个比较条件来确定扫描区间：

    key_part1 = 1 and key_part2 >= 10 and key_part3 > 10

对应的单区间是：

    ('foo',10,-inf) < (key_part1,key_part2,key_part3) <('foo',+inf,+inf)

这个区间可能比初始条件包含更多的列。例如，这个区间包含值(‘foo’,11,0)，这不满足原始条件。

如果多个查询条件对应的结果集是包含在由or连接的多个区间中，它们形成了一个条件，这个条件由多个区间对应的结果集合的并集组成。如果这些条件使用and连接，他们形成的条件对应着多个区间的结果集合交集。例如，下面的语句对应着一个两列索引：

    (key_part1 = 1 and key_part2 < 2) or (key_part1 > 5)

对应的区间是：

    (1,-inf) < (key_part1,key_part2) < (1,2)
    (5,-inf) < (key_part1,key_part2)

在这个例子中，第一行中的区间的左边界用了一列，右边界用了两列。第二行中的区间只用了一列。explain输出结果中的key_len列显示了使用到的前缀列的最大长度。

在一些场景中，key_len可能只是表示一个索引列被使用，但是这可能不是你想要的。假设key_part1和key_part2可以是null。对于下面的条件，key_len列会展示两个索引列的长度和：

key_part1 >= 1 and key_part2 < 2;

但实际上，这个条件会被转换成下面的条件：

key_part1 >= 1 and key_part2 is not null

想要了解查询优化器会怎样在单列索引扫描中合并或删减条件，请查阅 Range Access Method for Single-Part Indexes。对于多列索引来说，步骤类似。

多值比较的等值区间优化 #

下面的表达式中，col_name是一个索引列：

col_name in(val1, ..., valN)
col_name = val1 or ... or col_name = valN

只要col_name的值等于val1, …, valN中的任意一个，每一个表达式都是true。这些比较和range比较等价（算是单值的range）。在评估读取相关范围比较的记录时，优化器会这样做：

如果col_name是唯一索引，每一个区间的估算行数都是1，因为最多只有一条记录匹配一个特定值。
否则，col_name是非唯一的，查询优化器会使用dives into the index或者索引统计来评估每一个区间的记录数。使用索引俯冲时（姑且这么叫），查询优化器会对每一个区间都进行dive，并使用这个区间的记录数量来作为评估条件。例如，表达式 col_name in(10, 20, 30)有三个等值区间，查询优化器会对每个区间做两次俯冲来评估行数。使用索引统计信息会不如索引俯冲精准，但是在面对值列表很长时，它会更快。

系统变量eq_range_index_dive_limit控制了查询优化器是否切换行数评估策略的值数量的阈值。要想支持对n个等值区间的索引俯冲，需要将eq_range_index_dive_limit的值设置成n+1.而如果要禁止对索引统计信息的使用，总是使用索引俯冲，那可以将这个变量的值设置成0.

要想更新索引统计信息，获取更精准的评估，请使用analyze table。

在MySQL 8.0以前，没有办法来跳过索引俯冲，即使使用索引俯冲进行统计是无用的。在MySQL 8.0中，如果查询满足下面所有条件，则可以跳过索引俯冲：

查询是针对单表的，不是多表join查询。
在单列索引上使用了force index。如果强制使用某个索引，再执行索引俯冲是没有意义的。
索引是非唯一的，且不是全文索引。
没有子查询。
没有使用distinct,group by ,或order by 。对于explain for connection，如果索引俯冲被跳过，输出会产生如下变化：
对于常规输出，rows和filtered列的值会是null。
对于json输出，rows_examined_per_scan和rows_produced_per_join不会消失，skip_index_dive_due_to_force是true，成本评估不准确。如果没有for connection，在跳过索引俯冲时，explain的输出没有变化。如果没有使用索引俯冲，查询执行完成之后，information_schema.optimizer_trace表中,会有一条skipped_due_to_force_index值为index_dives_for_range_access的记录。

跳跃区间扫描 #

考虑下面的场景：

create table t1 (f1 int not null, f2 int not null, primary key(f1,f2));
insert into t1 values(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5);
insert into t1 select f1, f2 + 5 from t1;
insert into t1 select f1, f2 + 10 from t1;
insert into t1 select f1, f2 + 20 from t1;
insert into t1 select f1, f2 + 40 from t1;
analyze table t1;

explain select f1, f2 from t1 where f2 > 40;

要执行这个查询，MySQL可以选择索引扫描，获取所有记录（索引包含被选择的索引列），然后根据where中的条件f2>40来进行过滤，产生最终的结果集。范围扫描会比全索引扫描更高效，但是这个例子没有用到，因为where条件中没有索引中的第一列f1。但是，从8.0.13开始，查询优化器可以进行多区间扫描，就是对f1的每一个值都进行扫描，使用的是一种和松散索引扫描（见章节8.2.1.17， “GROUP BY Optimization”）类似的skip scan技术：

跳过索引前缀列f1中的不同值。
对每一个索引前缀值，用f2>40这个条件进行子区间扫描。

对于之前列出的数据集，算法操作如下：

取出索引前缀列f1的第一个值。
根据第一列和第二列构造区间(f1 = 1 and f2 > 40)。
进行区间扫描。
获取下一个索引前缀列的值（f1=2）。
构造扫描区间（f1 = 2 and f2 > 40）。
执行区间扫描。

使用这种策略减少了扫描的记录数，因为MySQL跳过了哪些不符合每个构造的区间的记录。只有符合下面的条件时，才能使用skip scan策略：

表T至少要有一个联合索引（[A_1,…,A_k]B_1,…,B_m, C[,D_1,…,D_n]）,A和D可能是空的，但是B和C可能是非空。
查询只涉及一张表。
查询是使用到了索引上的列。
A_1,…,A_k上的对比（？？）必须是等值比较。这包括in()操作。
查询必须是一个连接查询，意思是，条件是由where或者and连接起来的。
列C上必须要有一个范围条件。
允许D上的条件，D相关条件必须和C上的区间连接。 skip scan在explain输出中会展示如下：
Extra列中的Using index skip scan。意味着使用了松散索引扫描。
如果skip scan可以使用索引，这个索引就应该出现在possible_keys列中。 optimizer trace 输出中出现元素 “skip scan"意味着使用了skip scan：

"skip_scan_range": {
    "type": "skip_scan",
    "index": index_used_for_skip_scan,
    "key_parts_used_for_access": [key_parts_used_for_access],
    "range": [range]
}

你可能也会看到一个元素 “best_skip_scan_summary”。如果查询优化器认为skip scan是最好的访问方法之一，就会写入这个元素。如果最终选择skip scan为最好的访问方法，会出现"best_access_path"这个元素。

系统变量optimizer_switch变量中的skip_scan参数控制了是否使用skip scan。默认情况下，skip scan是开启的。要想禁用skip scan，可以将这个参数设置成off。

除了使用optimizer_switch系统变量来控制会话级别（？）的skip scan，MySQL还支持使用优化器提示来控制语句级别的使用。详情查阅章节8.9.3， “Optimizer Hints”。

行结构表达式的范围优化 #

查询优化器支持对下面的语句使用范围扫描访问方法：

select ... from t1 where ( col_1, col_2) in (('a', 'b'), ( 'c', 'd'));

以前，要使用范围扫描，需要将查询语句改写为：

select ... from t1 where (col_1 = 'a' and col_2 = 'b') or (col_1 = 'c' and col_2 = 'd');

要让优化器使用范围扫描，查询必须符合下面的条件：

只有in()，没有not in()。
在in()左侧，行构造器只包含列引用。
在in()右侧，行构造器只包含运行时常来那个，它们可能是在执行时绑定到常来那个的文字或本地列引用。
在in()右侧，有不止一个行构造器。想了解更多关于优化器和行构造器的细节，请查阅章节8.2.1.22 “Row Constructor Expression Optimization”。

区间访问的内存使用限制 #

要控制range优化器使用的内存，可以使用系统变量range_optimizer_max_mem_size：

值为0表示没有限制。
值>0，在评估区间访问时，优化器会追踪内存消耗。如果即将超出特定的阈值，就会放弃使用区间访问方法，转而评估其它访问方法。这个可能效果并不好。如果发生这种情形，会产生下面的告警（其中N是range_optimizer_max_mem_size的当前值）：

Warning 3179 Memory capacity of N bytes for 
             'range_optimizer_max_mem_size' exceeded. Range optimization was not done for this query.

对于update和delete语句，如果优化器最终选择全包扫描，sql_safe_updates被开启，就会产生一个错误，而不是告警。因为，这种情况下，没有使用某个键来判断修改哪些记录。像了解更多，请查阅Using Safe-Updates Mode (–safe-updates)。对于范围扫描优化内存超标，导致优化器被迫选择不那么理想的执行计划的单一查询，调大range_optimizer_max_mem_size的值可能会提高性能。

要评估处理range表达式的内存使用量，使用下面的指导原则：

在下面的例子中，范围访问方法有一个候选的key，每一个使用or连接的条件使用大约230bytes的内存。

select count(*) from t
where a=1 or a=2 or a=3 or ... a=N;

在类似下面的语句中，每一个使用and连接的条件大约使用125bytes的内存：

select count(*) from t
where a=1 and b=1 and c=1 ... . a=n;

在一个使用in的查询中：

selec count(*) from t
where a in (1,2, ..., N) and b in (1,2, ..., N);

每一个in()中的值都会被当成一个使用or连接的条件。如果有两个in列表，使用or连接的条件总数是每个in值列表中值个数的乘积。因此，上面的例子中条件(谓词？)数量是M*N.

关于跳跃操作，也可以查阅以下参考资料： http://mysql.taobao.org/monthly/2019/05/06/