1 Multi-Range Read Optimization 多范围索引扫描读优化

在次级索引上使用范围扫描（range scan）读取行时，当表很大且没有存储再存储引擎的缓存中时，就可能会导致对基础表的的许多磁盘的随机访问。 Mysql 试图通过 Multi-Range Read (MRR) 优化来减少范围扫描时的随机磁盘访问

步骤：

  1. 首先只扫描索引。并收集相关行的键（keys for the relevent rows）
  2. 对这些键进行排序，使用键排序的顺序访基表检索数据行

优化的动机就是减少随机磁盘访问，实现对基表的更多的顺序扫描

优点：

  1. MRR 基于索引对，使得数据行的访问是顺序执行的，而不是随机的。Server 获取满足查询条件的索引对 (index tuple)，根据数据行键（row ID）进行排序，使用排序的结果顺序访问完整的数据行。使得数据访问更高效，较低磁盘IO消耗
  2. MRR 允许批量处理对键访问的请求，这些请求用于需要通过索引对访问数据行的操作，比如范围索引扫描和使用索引连接属性的等值连接。MRR 迭代索引范围序列，获得满足条件的索引对。将这些结果进行聚合，访问对应的数据行。并且没有获取所有的索引对后才进行数据行的读取

MRR 不支持虚拟列上的次级索引.

哪些场景下可以利用 MRR 优化:

  • 场景 A

    InnoDB, MyISAM 表的索引范围扫描或者等值连接操作 (equi-join operations)

    1. 部分索引对被存储 (accumulated) 在缓存区中
    2. 缓冲区中的索引对通过数据行ID进行排序
    3. 根据排序的索引对的顺序访问数据行

  • 场景 B

    MRR 可以用于 NDB 表，用于多范围索引扫描，或者用于通过属性执行等值连接。

    1. 部分范围(可能是单键范围)缓存在查询提交的中心节点上的缓冲区中 (A portion of ranges, possibly single-key ranges, is accumulated in a buffer on the central node
      where the query is submitted)
    2. 这些范围查询被发送到执行节点来访问数据
    3. 数据行被打包发送回中心节点
    4. 将接收到的包 (带有数据行) 存放在缓冲区中
    5. 从缓冲区中返回结果行

如何判断当前查询使用了 MRR 优化

执行计划的 Extra 列为 Using MRR

InnoDB, MyISAM 如果需要进行全表扫描时, 不会使用 MRR 优化. 例如: 如果仅仅基于索引对中的信息就可以获取查询结构, 即 覆盖索引, MRR 不会提供任何优化.

如何开启 MRR

optimizer_switch 系统变量提供了使用 MRR 优化的开关, mrr 标志表示 MRR 是否已开启 (on), 默认开启, mrr_cost_based 标志表示控制查询优化器是否尝试基于性能的选择, 使用或不适用 MRR, 默认开启 (on). 如果希望尽可能的使用 MRR , 将其置为 off

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
SELECT @@optimizer_switch;

index_merge=on,
index_merge_union=on,
index_merge_sort_union=on,
index_merge_intersection=on,
engine_condition_pushdown=on,
index_condition_pushdown=on,
mrr=on,
mrr_cost_based=on,
block_nested_loop=on,
batched_key_access=off,
materialization=on,
semijoin=on,
loosescan=on,
firstmatch=on,
duplicateweedout=on,
subquery_materialization_cost_based=on,
use_index_extensions=on,
condition_fanout_filter=on,
derived_merge=on

read_rnd_buffer_size 系统变量表明可以为缓冲区分配的内存字节大小.

1
2
3
4
-- 默认 262144B = 256KB
SELECT @@read_rnd_buffer_size /1024;

256.0000

示例

1
2
3
4
5
6
7
8
9
10
show create table user_info;

CREATE TABLE `user_info` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `uid` varchar(64) NOT NULL,
  `name` varchar(255) DEFAULT NULL,
  `upd_time` timestamp NULL DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `user_info_uid_index` (`uid`)
) ENGINE=InnoDB AUTO_INCREMENT=22000001 DEFAULT CHARSET=utf8

使用 in 的范围查询

1
2
3
4
5
6
7
8
9
explain select * from user_info where uid in ('204-42-7061','735-14-7777','321-09-5846');


+----+-------------+-----------+------------+-------+---------------------+---------------------+---------+------+------+----------+-----------------------+
| id | select_type | table     | partitions | type  | possible_keys       | key                 | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-----------+------------+-------+---------------------+---------------------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | user_info | NULL       | range | user_info_uid_index | user_info_uid_index | 194     | NULL |    3 |   100.00 | Using index condition |
+----+-------------+-----------+------------+-------+---------------------+---------------------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

image-20200705144752910

1
2
3
4
5
6
7
8
9
-- in 的条件查询有 400 多个,后面的省略了
explain select * from user_info where uid in ('204-42-7061','735-14-7777','321-09-5846','736-50-3975','176-55-0702','466-84-4864','157-95-0925','358-76-6422','275-11-5932','316-90-4137','868-03-2935','020-06-6077','726-08-5008','475-65-1649','059-97-0370','503-92-8111','385-02-6790','451-49-1154','020-16-2354','588-93-7398','657-12-6885','155-98-3036','838-63-2477','780-33-4522','033-70-3319','529-49-3149','006-93-6411','749-94-6620','717-17-1261','377-55-0697','525-59-2422','565-14-3063','686-91-9092','381-99-6716','228-22-7720','431-62-1403','222-46-8484','556-13-2704','053-34-8148','128-05-3170','599-38-5086','722-22-2334', ...)


+----+-------------+-----------+------------+-------+---------------------+---------------------+---------+------+------+----------+----------------------------------+
| id | select_type | table     | partitions | type  | possible_keys       | key                 | key_len | ref  | rows | filtered | Extra                            |
+----+-------------+-----------+------------+-------+---------------------+---------------------+---------+------+------+----------+----------------------------------+
|  1 | SIMPLE      | user_info | NULL       | range | user_info_uid_index | user_info_uid_index | 194     | NULL |  435 |   100.00 | Using index condition; Using MRR |
+----+-------------+-----------+------------+-------+---------------------+---------------------+---------+------+------+----------+----------------------------------+

image-20200705145000247

2 Block Nested-Loop and Batched Key Access Joins

MySQL 中可以使用 Batched Key Access (BKA) 连接算法来同时使用索引来访问被连接的表, 同样也使用一个连接缓冲区. BKA 算法支持内连接, 外连接, 以及半连接 (semijoin operations), 包括前内外连接. BKA 算法由于更高效的表扫描, 可以提升连接的性能. 同时, Block Nested-Loop(BNL) 连接算法也可以被扩展应用与的外连接等操作.

Join Buffer Management for Block Nested-Loop and Batched Key Access Algorithms

Block Nested-Loop Algorithm for Outer Joins and Semijoins

Batched Key Access Joins

Batched Key Access (BKA) 连接算法用于连接表, 当第二个连接操作数( the second join operand - 被驱动表) 表生成的行可以使用索引访问时, 可以使用应用 BKA 算法.

  1. 和 BNL 算法一样, BKA 连接算法会使用一个连接缓冲区 (join buffer) 来缓存连接操作中驱动表行的感兴趣的列.
  2. 然后 BKA 算法会构建缓冲区中所有行的键 (keys 索引) 来访问被连接的表
  3. 以批量的方式将这些 keys 提交给数据库引擎进行索引查询
  4. 提交的 keys 通过 MRR 接口进行处理, 以优化的方式, 使用索引进行查询
  5. 获取由这些 keys 匹配的行, 返回给 BKA 连接算法, 每一个匹配的行同时带了一个指向连接缓冲区中行的引用

使用 BKA 时, join_buffer_size 定义的时每次发给存储引擎的批量 keys 的大小

开启 BKA

optimizer_switch 系统变量的 batched_key_access 需要置为 on, BKA 同时使用 MRR, mrr 也需要置为 on. 并且由于目前对于使用 MRR 所进行的优化效果过于悲观, 需要将 mrr_cost_based 置为 off

1
SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

如何判断当前连接查询使用了 BKA 算法

执行计划的 Extra 列为 Using join buffer (Batched Key Access), 同时, 连接类型 type 是 ref 或者 eq_ref

MRR 的执行由由两种场景

  • 传统的基于磁盘的存储引擎, 如 InnoDB 和 MyISAM, 对于这些引擎. 来自连接缓冲区的所有行的键一次性提交给 MRR. 特定于引擎的 MRR 函数对提交的键进行索引查找, 从他们中获取行 id (或主键), 然后获取所有行 id 对应的行数据. 返回的每一行都带了一个关联引用 (用于访问连接缓冲区中的行). MRR 读取行时使用了行 id的顺序进行读取 (顺序访问而不是随机访问).
  • 远程存储引擎, 如 NDB, MySQL Server (SQL 节点)将连接缓冲区的部分行的键及其关联引用发送到 NDB 集群的数据节点. SQL 节点收到数据节点返回的包(一个或多个), 其中包含了匹配的行以及相应的关联引用. BKA 算法利用这些行并构建新的连接行. 然后想数据节点发送行的键, 知道所有的连接操作匹配已经完成.

示例

开启 BKA 

1
SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
1
2
3
4
5
6
7
8
show create table user_score;

CREATE TABLE `user_score` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `uid` varchar(64) NOT NULL,
  `score` float DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=15 DEFAULT CHARSET=utf8

连接查询, 并且被驱动表的连接类型是 ref, eq_ref

1
2
3
4
5
6
7
8
explain select * from user_score a left join  user_info b on a.uid = b.uid;

+----+-------------+-------+------------+------+---------------------+---------------------+---------+-------------------+------+----------+----------------------------------------+
| id | select_type | table | partitions | type | possible_keys       | key                 | key_len | ref               | rows | filtered | Extra                                  |
+----+-------------+-------+------------+------+---------------------+---------------------+---------+-------------------+------+----------+----------------------------------------+
|  1 | SIMPLE      | a     | NULL       | ALL  | NULL                | NULL                | NULL    | NULL              |    6 |   100.00 | NULL                                   |
|  1 | SIMPLE      | b     | NULL       | ref  | user_info_uid_index | user_info_uid_index | 194     | learning_db.a.uid |    1 |   100.00 | Using join buffer (Batched Key Access) |
+----+-------------+-------+------------+------+---------------------+---------------------+---------+-------------------+------+----------+----------------------------------------+

image-20200705152742898

关掉 BKA, 还原默认设置

1
2
3
SET optimizer_switch='mrr=on,mrr_cost_based=on,batched_key_access=off';

explain select * from user_score a left join  user_info b on a.uid = b.uid;

image-20200705154158520

*被驱动表的连接类型不是 ref, eq_ref * 

1
2
3
4
5
6
7
8
explain select * from user_info a left join user_score b on a.uid = b.uid;

+----+-------------+-------+------------+------+---------------+------+---------+------+----------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows     | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+----------+----------+----------------------------------------------------+
|  1 | SIMPLE      | a     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 21919807 |   100.00 | NULL                                               |
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |        6 |   100.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+----------+----------+----------------------------------------------------+

image-20200705153949927