查看“范围优化”的源代码

范围访问方法使用单个索引来检索包含在一个或多个索引值区间内的表行子集。它可用于单个部分索引或多个部分索引。以下部分描述了优化器使用范围访问的条件。


==单个部分索引的范围访问方法==


对于单个部分索引，索引值区间可以通过WHERE子句中的相应条件来方便地表示，这些条件被称为范围条件，而不是“区间”。


对于单个部分索引的范围条件定义如下：

*对于BTREE和HASH索引，使用=，<=>，IN()，IS NULL或IS NOT NULL操作符将关键部分与常量值进行比较时，被视为范围条件。

*此外，对于BTREE索引，如果使用>，<，>=，<=，BETWEEN，!=或<>操作符进行关键部分与常量值的比较，或者如果LIKE比较的参数是以非通配符字符开头的常量字符串，则也被视为范围条件。

*对于所有索引类型，多个范围条件结合使用OR或AND形成一个范围条件。


上述描述中的“常量值”指的是以下之一：

*查询字符串中的常量

*来自相同连接的const或系统表的列

*无关子查询的结果

*完全由前述类型的子表达式组成的任何表达式


以下是一些带有范围条件的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，这样我们在进行范围扫描时不会错过任何匹配的行。将它们替换为TRUE得到：

 (key1 < 'abc' AND (key1 LIKE 'abcde%' OR TRUE)) OR
 (key1 < 'bar' AND TRUE) OR
 (key1 < 'uux' AND key1 > 'z')


*合并始终为真或假的条件：

 (key1 LIKE 'abcde%' OR TRUE)始终为真
 
 (key1 < 'uux' AND key1 > 'z')始终为假


*用常量替换这些条件得到：
 (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子句中出现的顺序。


MySQL不支持合并多个范围的空间索引的范围访问方法。为了绕过这个限制，可以使用一个带有相同SELECT语句的UNION，只是在每个SELECT中将每个空间谓词放在不同的位置。


==多部分索引的范围访问方法==

对于多部分索引，范围条件是对单部分索引的范围条件的扩展。多部分索引上的范围条件将索引行限制在一个或多个键元组区间内。键元组区间是使用索引的排序定义的一组键元组。


例如，考虑一个定义为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,-inf) <= (key_part1,key_part2,key_part3) < (1,+inf,+inf)


该区间覆盖了前面数据集中的第4、第5和第6个元组，并可以被范围访问方法使用。


相反，条件key_part3 = 'abc'没有定义一个单独的区间，不能被范围访问方法使用。


以下描述更详细地说明了多部分索引的范围条件是如何工作的。


*对于HASH索引，每个包含相同值的区间都可以使用。这意味着区间只能针对以下形式的条件生成：

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


在这里，const1、const2等是常量，cmp是=、<=>或IS NULL比较运算符中的一个，条件涵盖了所有索引部分。（也就是说，对于一个N部分索引，有N个条件。）例如，以下是一个三部分HASH索引的范围条件：

 key_part1 = 1 AND key_part2 IS NULL AND key_part3 = 'foo'


有关什么被视为常量的定义，请参阅单部分索引的范围访问方法。


*对于BTREE索引，一个区间可能在与AND组合的条件中可用，其中每个条件使用=、<=>、IS NULL、>、<、>=、<=、!=、<>、BETWEEN或LIKE 'pattern'（其中'pattern'不以通配符开头）将一个键部分与常量值进行比较。只要能确定一个包含所有与条件匹配的行的单个键元组（如果使用<>或!=，则使用两个区间），就可以使用该区间。


优化器在比较运算符为=、<=>或IS NULL时，尽量使用额外的键部分来确定区间。如果运算符为>、<、>=、<=、!=、<>、BETWEEN或LIKE，则优化器使用它，但不考虑更多的键部分。对于以下表达式，优化器使用第一个比较中的=。它还使用第二个比较中的>=，但不考虑进一步的键部分，并且不使用第三个比较来构建区间：

 key_part1 = 'foo' 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


有关如何通过合并或消除单个部分索引上的范围条件的区间来执行优化的描述，请参见单个部分索引的范围访问方法。类似的步骤也适用于多部分索引上的范围条件。


==多值比较的等值范围优化==
考虑以下表达式，其中col_name是一个有索引的列：

 col_name IN(val1, ..., valN)
 col_name = val1 OR ... OR col_name = valN


如果col_name等于多个值中的任何一个，那么每个表达式都为真。这些比较是等值范围比较（其中“范围”是一个单一的值）。优化器根据以下方式估计对于等值范围比较读取符合条件行的成本：

*如果col_name上有唯一索引，每个范围的行估计值为1，因为最多只有一行可以具有给定的值。

*否则，col_name上的任何索引都是非唯一的，优化器可以使用索引或索引统计信息的潜入来估计每个范围的行数。


通过索引潜入，优化器在范围的每一端进行一次潜入，并使用范围内的行数作为估计值。例如，表达式col_name IN (10, 20, 30)有三个等值范围，优化器每个范围进行两次潜入来生成行估计值。每对潜入提供了具有给定值的行数的估计值。


索引潜入提供准确的行估计值，但随着表达式中的比较值数量的增加，优化器生成行估计值的时间也会增长。使用索引统计信息的准确性不如索引潜入，但可以更快地对大型值列表进行行估计。

eq_range_index_dive_limit系统变量允许你配置在多少个值时优化器从一种行估计策略切换到另一种。要允许在最多N个等值范围的比较中使用索引潜入，请将eq_range_index_dive_limit设置为N + 1。要禁用使用统计数据，并始终使用索引潜入，而不考虑N的值，请将eq_range_index_dive_limit设置为0。


要更新表索引统计数据以获得最佳估计值，请使用ANALYZE TABLE。


在MySQL 8.0之前，除了使用eq_range_index_dive_limit系统变量之外，没有办法跳过使用索引潜入来估计索引的有效性。在MySQL 8.0中，对于满足以下所有条件的查询，可以跳过索引潜入：

*查询是针对单个表而不是多个表的连接。

*存在单个索引的FORCE INDEX索引提示。这个想法是，如果强制使用索引，那么执行索引潜入的额外开销是没有意义的。

*该索引是非唯一索引，且不是FULLTEXT索引。

*查询中没有子查询。

*查询中没有DISTINCT、GROUP BY或ORDER BY子句。


对于EXPLAIN FOR CONNECTION，如果跳过了索引潜入，输出将发生以下更改：

*对于传统输出，行数和过滤值为NULL。

*对于JSON输出，rows_examined_per_scan和rows_produced_per_join不会出现，skip_index_dive_due_to_force为true，成本计算也不准确。


没有FOR CONNECTION时，当跳过索引潜入时，EXPLAIN输出不会发生变化。


在执行跳过索引潜入的查询后，Information Schema的OPTIMIZER_TRACE表中相应的行包含一个index_dives_for_range_access值，其值为skipped_due_to_force_index。


==跳过扫描范围访问方法==
考虑以下情况：

 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条件来生成最终的结果集。


范围扫描比完整的索引扫描更高效，但在这种情况下不能使用范围扫描，因为对于第一个索引列f1没有条件。然而，从MySQL 8.0.13开始，优化器可以执行多个范围扫描，每个f1的值执行一次，使用一种称为跳跃扫描（Skip Scan）的方法，类似于松散索引扫描：

*在第一个索引部分f1（索引前缀）的不同值之间进行跳跃。

*对于剩余的索引部分，对于每个不同的前缀值执行f2 > 40条件的子范围扫描。


对于前面展示的数据集，算法操作如下：

*获取第一个不同的第一个键部分的值（f1 = 1）。

*基于第一个和第二个键部分构建范围（f1 = 1 AND f2 > 40）。

*执行范围扫描。

*获取下一个不同的第一个键部分的值（f1 = 2）。

*基于第一个和第二个键部分构建范围（f1 = 2 AND f2 > 40）。

*执行范围扫描。


使用这种策略可以减少访问的行数，因为MySQL会跳过不符合每个构建范围条件的行。跳跃扫描访问方法适用于以下条件：

*表T至少有一个复合索引，索引键部分的形式为（[A_1，...，A_k，] B_1，...，B_m，C [, D_1，...，D_n]）。键部分A和D可以为空，但B和C必须非空。

*查询只引用一个表。

*查询不使用GROUP BY或DISTINCT。

*查询仅引用索引中的列。

*A_1，...，A_k上的谓词必须是等值谓词，并且它们必须是常量。包括IN()操作符。

*查询必须是一个合取查询，即AND的OR条件：（cond1（key_part1）OR cond2（key_part1））AND（cond1（key_part2）OR ...）AND ...

*C上必须有一个范围条件。

*允许在D列上添加条件。D上的条件必须与C上的范围条件一起使用。


在EXPLAIN输出中:

*使用“Using index for skip scan”在Extra列中表示使用了松散索引的跳跃扫描访问方法。

*如果索引可用于跳跃扫描，则在possible_keys列中应显示该索引。


在优化器跟踪输出中，通过以下形式的“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作为最佳范围访问变体，则会写入一个"chosen_range_access_summary"。如果选择Skip Scan作为整体最佳访问方法，则会存在一个"best_access_path"元素。


使用Skip Scan取决于optimizer_switch系统变量的skip_scan标志的值。默认情况下，该标志是打开的。要禁用它，请将skip_scan设置为off。


除了使用optimizer_switch系统变量来全局控制优化器使用Skip Scan之外，MySQL还支持优化器提示来在每个语句的基础上影响优化器。



==行构造器表达式的范围优化==
优化器能够将范围扫描访问方法应用于以下形式的查询：


 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()谓词的右侧，存在多个行构造器。


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

*值为0表示“无限制”。

*如果值大于0，优化器在考虑范围访问方法时会跟踪内存消耗情况。如果即将超出指定的限制，将放弃范围访问方法，而考虑其他方法，包括完整表扫描。这可能不是最优的。如果发生这种情况，将会出现以下警告（其中N为当前range_optimizer_max_mem_size值）：

 Warning    3170    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系统变量，则会产生错误而不是警告，因为实际上没有使用键来确定要修改的行。要了解更多信息，请参阅使用安全更新模式（--safe-updates）。


对于超出可用范围优化内存并且优化器回退到较差计划的单个查询，增加range_optimizer_max_mem_size值可能会提高性能。


要估计处理范围表达式所需的内存量，可以使用以下准则：

*对于简单查询，例如下面的查询，其中对于范围访问方法，有一个候选键，每个与OR组合的谓词大约使用230个字节：

 SELECT COUNT(*) FROM t
 WHERE a=1 OR a=2 OR a=3 OR .. . a=N;


*类似地，对于下面的查询，每个与AND组合的谓词大约使用125个字节：

 SELECT COUNT(*) FROM t
 WHERE a=1 AND b=1 AND c=1 ... N;


*对于带有IN()谓词的查询：

 SELECT COUNT(*) FROM t
 WHERE a IN (1,2, ..., M) AND b IN (1,2, ..., N);


在IN()列表中的每个字面值都视为与OR组合的谓词。如果有两个IN()列表，则与OR组合的谓词数量是每个列表中字面值的数量的乘积。因此，前面的情况中与OR组合的谓词数量为M×N。