MySQL优化(5):SELECT 之 Range范围优化

范围访问方法使用单个索引来检索包含在一个或多个索引值区间内的表行的子集。

它可用于 single-part 或 multiple-part 索引。 以下部分描述了优化器使用范围访问的条件。

Single-Part索引的范围访问方法

对于 single-part 索引,索引值区间可以方便地用 WHERE 子句中的相应条件表示,表示为范围条件而不是“区间”。

single-part索引的范围条件定义如下:

  • 对于 BTREE 和 HASH 索引,在使用 =、<=>、IN()、IS NULLIS NOT NULL 运算符时,将条件列与常量值进行比较是一个范围条件。
  • 此外,对于 BTREE 索引,当使用 >、<、>=、<=、BETWEEN、!=<> 运算符或 LIKE 比较时,若LIKE参数是不以通配符开头的常量字符串,条件列与常量值的比较是一个范围条件 。
  • 对于所有索引类型,多个范围条件与 OR 或 AND 组合形成一个范围条件。

上述说明中的 常量值 是指下列情况之一:

  • 查询字符串中的常量
  • 来自同一联接的常量或系统表的列
  • 不相关子查询的结果
  • 完全由上述类型的子表达式组成的任何表达式

以下是 WHERE 子句中具有范围条件的查询的一些示例:

1
2
3
4
5
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 非索引列:

1
2
3
4
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');

key 的提取过程如下:

  1. 开始于原始的 where 子句

    1
    2
    3
    (key1 < 'abc' AND (key1 LIKE 'abcde%' OR key1 LIKE '%b')) OR
    (key1 < 'bar' AND nonkey = 4) OR
    (key1 < 'uux' AND key1 > 'z')
  2. 移除 nonkey = 4 和 key1 LIKE ‘%b’ ,因为它们不能用于范围扫描。 移除它们的正确方法是将它们替换为 TRUE,这样我们在进行范围扫描时就不会遗漏任何匹配的行。 用 TRUE 替换它们会产生:

    1
    2
    3
    (key1 < 'abc' AND (key1 LIKE 'abcde%' OR TRUE)) OR
    (key1 < 'bar' AND TRUE) OR
    (key1 < 'uux' AND key1 > 'z')
  3. 始终为 true 或 false 的折叠条件:

    • (key1 LIKE 'abcde%' OR TRUE) is always true
    • (key1 < 'uux' AND key1 > 'z') is always false

    将这些条件替换为常量会产生:

    1
    (key1 < 'abc' AND TRUE) OR (key1 < 'bar' AND TRUE) OR (FALSE)

    移除不必要的 true 常量和 false 常量会产生:

    1
    (key1 < 'abc') OR (key1 < 'bar')

    将重叠的区间合并为一个,得到用于范围扫描的最终条件:

    1
    key1 < 'bar')

一般来说(如前面的示例所示),用于范围扫描的条件比 WHERE子 句的限制性小。MySQL执行额外的检查来过滤出满足范围条件但不满足完整WHERE子句的行。

范围条件提取算法可以处理任意深度的嵌套 AND/OR 结构,其输出不依赖于条件在 WHERE 子句中出现的顺序。

MySQL 不支持为空间索引的范围访问方法合并多个范围。 要解决此限制,可以使用具有相同 SELECT 语句的 UNION,只是将每个空间断言(判断)放在不同的 SELECT 中。

Multiple-Part索引的范围访问方法

multiple-part 索引的范围条件是 single-part 索引范围条件的扩展。

multiple-part 索引的范围条件将索引行限制在一个或多个 Key 元组区间内。 Key 元组区间是在一组 Key元组上定义的,使用索引的顺序。

例如,考虑定义为 key1(key_part1, key_part2, key_part3) 的 multiple-part 索引,以及以下按 Key 顺序列出的Key元组集:

1
2
3
4
5
6
7
8
  key_part1  key_part2  key_part3
1 NULL 1 'abc'
2 NULL 1 'xyz'
3 NULL 2 'foo'
4 1 1 'abc'
5 1 1 'xyz'
6 1 2 'abc'
7 2 1 'aaa'

条件 key_part1 = 1 定义了这个区间:

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

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

相比之下,条件 key_part3 = ‘abc’ 没有定义单个区间,不能被范围访问方法使用。

以下描述更详细地说明了范围条件如何适用于 multiple-part 索引。

  • 对于 HASH 索引,可以使用包含相同值的每个区间。 这意味着只能为以下形式的条件生成区间:

    1
    2
    3
    4
        key_part1 cmp const1
    AND key_part2 cmp const2
    AND ...
    AND key_partN cmp constN;

    这里,const1、const2、...是常量,cmp=、<=>IS NULL比较运算符之一,条件覆盖所有索引部分。 (也就是说,有N个条件,一个N-part索引的每个部分一个)

    例如,以下是一个三部分 HASH 索引的范围条件:

    1
    key_part1 = 1 AND key_part2 IS NULL AND key_part3 = 'foo'
  • 对于 BTREE 索引,区间可能可用于与 AND 组合的条件,其中每个条件使用 =、<=>、IS NULL、>、<、>=、<=、!= 将 Key部分与常量值进行比较, <>、BETWEENLIKE 'pattern'(其中 ‘pattern’ 不以通配符开头)。

    只要可以确定包含与条件匹配的所有行的单个 Key元组(如果使用 <> 或 != 则为两个区间),就可以使用区间。

    只要比较运算符为 =、<=>IS NULL,优化器就会尝试使用其他 Key 部分来确定区间。

    如果运算符是 >、<、>=、<=、!=、<>、BETWEENLIKE,优化器会使用它但不再考虑 Key 部分。

    对于以下表达式,优化器使用来自第一次比较的 =。 它还使用第二次比较中的 >= ,但不考虑其他 Key 部分,也不使用第三次比较进行区间构造:

    1
    key_part1 = 'foo' AND key_part2 >= 10 AND key_part3 > 10

    单个区间为:

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

    创建的间隔可能包含比初始条件更多的行。 例如,前面的区间包含不满足原始条件的值(‘foo’, 11, 0),因为 key_part3 没有被考虑。

    如果覆盖包含在区间内的行集的条件与 OR 组合,则它们形成一个条件,该条件覆盖包含在其区间联合中的一组行。

    如果条件与 AND 组合,则它们形成一个条件,该条件桥头包含在其区间交集内的一组行。 例如,对于由两部分组成的索引的这种情况:

    1
    (key_part1 = 1 AND key_part2 < 2) OR (key_part1 > 5)

    区间为:

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

    在本例中,第一行的区间使用一个 Key 部分作为左边界,两个关键部分作为右边界。

    第二行的区间只使用一个 Key 部分。

    EXPLAIN 输出中的 key_len 列指示所用 Key 前缀的最大长度。

    在某些情况下,key_len 可能表示使用了 Key 部分,但这可能不是您所期望的。

    假设 key_part1 和 key_part2 可以为 NULL。 然后 key_len 列显示以下条件的两个 Key 部分长度:

    1
    key_part1 >= 1 AND key_part2 < 2

    但是,实际上,条件转换为:

    1
    key_part1 >= 1 AND key_part2 IS NOT NULL

多值比较的相等范围优化

考虑这些表达式,其中 col_name 是一个索引列:

1
2
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 BYORDER BY 子句。

对于 EXPLAIN FOR CONNECTION,如果跳过索引深入,输出更改如下:

  • 对于传统输出,行和过滤的值是 NULL。
  • 对于JSON输出,rows_examined_per_scanrows_produced_per_join没有出现,skip_index_dive_due_to_force为 true,cost 计算不准确。

如果没有 FOR CONNECTION,跳过索引深入时 EXPLAIN 输出不会改变。

在执行跳过索引深入的查询后,INFORMATION_SCHEMA.OPTIMIZER_TRACE 表中的相应行包含一个 index_dives_for_range_access 值,即 skipped_due_to_force_index

跳过扫描范围访问方法

考虑以下场景:

1
2
3
4
5
6
7
8
9
10
11
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 值一个,使用的是类似于松散索引扫描的称为跳跃扫描的方法。

  • 在第一个索引部分 f1(索引前缀)的不同值之间跳过。
  • 对剩余索引部分的 f2 > 40 条件的每个不同前缀值执行子范围扫描。

对于前面显示的数据集,算法的运行方式如下:

  • 获取第一个 key 部分的第一个不同值 (f1 = 1)。
  • 根据第一个和第二个关键部分构建范围(f1 = 1 AND f2 > 40)。
  • 执行范围扫描。
  • 获取第一个关键部分的下一个不同值 (f1 = 2)。
  • 根据第一个和第二个关键部分构建范围(f1 = 2 AND f2 > 40)。
  • 执行范围扫描。

使用此策略会减少访问的行数,因为 MySQL 会跳过不符合每个构造范围的行。 此跳过扫描访问方法适用于以下条件:

  • 表 T 至少有一个复合索引,其 Key 部分的形式为 ([A_1, …, A_k,] B_1, …, B_m, C [, D_1, …, D_n])。 Key 部分 A 和 D 可以为空,但 B 和 C 必须为非空。
  • 查询仅引用一张表。
  • 该查询不使用 GROUP BY 或 DISTINCT。
  • 查询仅引用索引中的列。
  • A_1, …, A_k 上的断方必须是等式断言并且它们必须是常量。 这包括 IN() 运算符。
  • 查询必须是连接查询; 即 OR 条件的 AND : (cond1(key_part1) OR cond2(key_part1)) AND (cond1(key_part2) OR …) AND …
  • C 上必须有一个范围条件。
  • D 列上的条件是允许的。 D 上的条件必须与 C 上的范围条件一起使用。

EXPLAIN 输出中指示使用跳过扫描,如下所示:

  • Extra列中的Using index for skip scan表示使用的是松散索引Skip Scan访问方式。
  • 如果该索引可用于跳过扫描,则该索引应在 possible_keys 列中可见。

在优化器跟踪输出中使用这种形式的“跳过扫描”元素指示使用跳过扫描:

1
2
3
4
5
6
"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”元素。 如果选择跳过扫描作为最佳范围访问变量,则写入“chosen_range_access_summary”。 如果选择跳过扫描作为总体最佳访问方法,则存在“best_access_path”元素。

跳过扫描的使用取决于 optimizer_switch 系统变量的 skip_scan 标志的值。默认情况下,此标志处于打开状态。 要禁用它,请将 skip_scan 设置为 off。

除了使用 optimizer_switch 系统变量来控制优化器在会话范围内使用跳过扫描之外,MySQL 还支持优化器提示以在每个语句的基础上影响优化器。

行构造函数表达式的范围优化

优化器能够将范围扫描访问方法应用于这种形式的查询:

1
SELECT ... FROM t1 WHERE ( col_1, col_2 ) IN (( 'a', 'b' ), ( 'c', 'd' ));

以前,要使用范围扫描,必须将查询编写为:

1
2
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 值):

    1
    2
    3
    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 系统变量,则会发生错误而不是警告,因为实际上没有使用 Key 来确定要修改哪些行。

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

要估计处理范围表达式所需的内存量,请使用以下准则:

  • 或者像下面这样的简单查询,其中范围访问方法有一个备选键,每个与 OR 组合的条件使用大约 230 个字节:

    1
    2
    SELECT COUNT(*) FROM t
    WHERE a=1 OR a=2 OR a=3 OR .. . a=N;
  • 类似地,对于如下查询,每个与 AND 组合的谓词使用大约 125 个字节:

    1
    2
    SELECT COUNT(*) FROM t
    WHERE a=1 AND b=1 AND c=1 ... N;
  • 对于带有 IN() 谓词的查询:

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

    IN() 列表中的每个文字值都算作与 OR 组合的谓词。 如果有两个 IN() 列表,则与 OR 组合的谓词数量是每个列表中文字值数量的乘积。 因此,在前一种情况下与 OR 组合的谓词数量为 M × N。

MySQL优化(5):SELECT 之 Range范围优化

http://blog.gxitsky.com/2021/07/08/MySQL-Optimization-05-Range/

作者

光星

发布于

2021-07-08

更新于

2023-03-06

许可协议

评论