数据库内核月报 - 2016 / 01

MySQL · 特性分析 · 优化器 MRR & BKA

上一篇文章咱们对 ICP 进行了一次全面的分析,本篇文章小编继续为大家分析优化器的另外两个选项: MRR & batched_key_access(BKA) ,分析一下他们的作用、原理、相互关系、源码实现以及使用范围。

什么是 MRR

MRR 的全称是 Multi-Range Read Optimization,是优化器将随机 IO 转化为顺序 IO 以降低查询过程中 IO 开销的一种手段,咱们对比一下 mrr=on & mrr=off 时的执行计划:

其中表结构如下:

mysql> show create table t1\G
*************************** 1. row ***************************
       Table: t1
Create Table: CREATE TABLE `t1` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  `c` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `mrrx` (`a`,`b`),
  KEY `xx` (`c`)
) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

操作如下:

mysql> set optimizer_switch='mrr=off';
Query OK, 0 rows affected (0.00 sec)

mysql>  explain select * from test.t1 where (a between 1 and 10) and (c between 9 and 10) ;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                              |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------+
|  1 | SIMPLE      | t1    | range | mrrx,xx       | xx   | 5       | NULL |    2 | Using index condition; Using where |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------+
1 row in set (0.00 sec)

当把 MRR 关掉的情况下,执行计划使用的是索引 xx(c),即从索引 xx 上读取一条数据后回表,取回该主键的完整数据,当数据较多且比较分散的情况下会有比较多的随机 IO, 导致性能低下,我们将 MRR 打开,执行以下操作:

mysql> set optimizer_switch='mrr=on';
Query OK, 0 rows affected (0.00 sec)

mysql>  explain select * from test.t1 where (a between 1 and 10) and (c between 9 and 10) ;
+----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                         |
+----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------------------------+
|  1 | SIMPLE      | t1    | range | mrrx,xx       | xx   | 5       | NULL |    2 | Using index condition; Using where; Using MRR |
+----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------------------------+
1 row in set (0.00 sec)

可以看到 extra 的输出中多了 “Using MRR” 信息,即使用了 MRR Optimization IO 层面进行了优化,减少 IO 方面的开销,更详细的说明可以参考这里

MRR 原理

在不使用 MRR 时,优化器需要根据二级索引返回的记录来进行“回表”,这个过程一般会有较多的随机 IO, 使用 MRR 时,SQL 语句的执行过程是这样的:

  • 优化器将二级索引查询到的记录放到一块缓冲区中;
  • 如果二级索引扫描到文件的末尾或者缓冲区已满,则使用快速排序对缓冲区中的内容按照主键进行排序;
  • 用户线程调用 MRR 接口取 cluster index,然后根据cluster index 取行数据;
  • 当根据缓冲区中的 cluster index 取完数据,则继续调用过程 2) 3),直至扫描结束;

通过上述过程,优化器将二级索引随机的 IO 进行排序,转化为主键的有序排列,从而实现了随机 IO 到顺序 IO 的转化,提升性能。

MRR 源码分析

首先,咱们来看一下 mrr 相对应的内存结构:

class DsMrr_impl
{
  ...
  handler *h;
  TABLE *table; /* Always equal to h->table */
private:
  /* Secondary handler object.  It is used for scanning the index */
  handler *h2;

  /* Buffer to store rowids, or (rowid, range_id) pairs */
  uchar *rowids_buf;
  uchar *rowids_buf_cur;   /* Current position when reading/writing */
  uchar *rowids_buf_last;  /* When reading: end of used buffer space */
  uchar *rowids_buf_end;   /* End of the buffer */

  bool dsmrr_eof; /* TRUE <=> We have reached EOF when reading index tuples */

  int dsmrr_init(handler *h, RANGE_SEQ_IF *seq_funcs, void *seq_init_param,
                 uint n_ranges, uint mode, HANDLER_BUFFER *buf);
  ….
  int dsmrr_fill_buffer();
  int dsmrr_next(char **range_info);
  bool get_disk_sweep_mrr_cost(uint keynr, ha_rows rows, uint flags, uint *buffer_size, Cost_estimate *cost);
  ….
}

简单说明:h2 指的是 MRR 使用的 second index 或主键索引, h 是指利用 h2 返回的主建来查询的句柄,rowids_buf 是 MRR 执行过程中存储有序主键的缓存区,大小由 MySQL 的变量 read_rnd_buffer_size 设置,下面我们结合程序的执行过程来看一下源码。

  1. MRR 中有序主建的收集过程
    优化器对查询语句的条件进行分析并选择合适的二级索引,并对二级索引的条件进行筛选拼装成 DYNAMIC_ARRAY ranges,在执行的时候将 ranges 传入初始化函数 ha_myisam::multi_range_read_init ,继而会调用 dsmrr_fill_buffer 函数,在dsmrr_fill_buffer中会使用二级索引的句柄查找符合 ranges 的数据并添加至 rowids_buf 中,在扫描结束或缓冲区满的时候会对 rowids_buf 进行快速排序,详细过程可以参考函数:dsmrr_fill_buffer,其调用堆栈如下:

     #0  DsMrr_impl::dsmrr_fill_buffer (this=0x2aab0000cf00)
     #1  0x00000000006e49dd in DsMrr_impl::dsmrr_init(...)
     #2  0x00000000017d35e4 in ha_myisam::multi_range_read_init(...)
     #3  0x0000000000d134c6 in QUICK_RANGE_SELECT::reset (this=0x2aab00014070)
     #4  0x00000000009a266f in join_init_read_record (tab=0x2aab0000f5b8)
     #5  0x000000000099d6d4 in sub_select
     #6  0x000000000099c914 in do_select (join=0x2aab000064b0)
     #7  0x00000000009982f8 in JOIN::exec (this=0x2aab000064b0)
     #8  0x0000000000a5bd7c in mysql_execute_select
     ........
    
  2. MRR 中主建缓冲区的使用过程

    物理执行阶段,调用 ha_myisam::multi_range_read_next,在使用 MRR 的情况下会从过程1)中收集的有序主建的缓冲区取主建,然后再调用引擎层的 rnd_pos 直接找到数据,其中使用 mrr 的调用堆栈如下:

     #0  DsMrr_impl::dsmrr_next (this=0x2aab0000cf00, range_info=0x2aaafc03de70)
     #1  0x00000000017d3634 in ha_myisam::multi_range_read_next (this=0x2aab0000ca40, range_info=0x2aaafc03de70)
     #2  0x0000000000d138cc in QUICK_RANGE_SELECT::get_next (this=0x2aab00014070)
     #3  0x0000000000d46908 in rr_quick (info=0x2aab0000f648)
     #4  0x00000000009a2791 in join_init_read_record (tab=0x2aab0000f5b8)
     #5  0x000000000099d6d4 in sub_select (join=0x2aab000064b0, join_tab=0x2aab0000f5b8, end_of_records=false)
     #6  0x000000000099c914 in do_select (join=0x2aab000064b0)
    

    二缓索引(h2)& 主建索引(h) 的协同是通过rowids_buf_cur来进行的。最初的初始化过程中,h2 会首先将数据填冲到 rowids_buf 中,如果发现缓冲区中的数据已经取完,则会继续调用 dsmrr_fill_buffer 往 rowids_buf 填主键并进行排序,如此反复,直至 h2 扫描至文件末尾,详情可以参考函数 DsMrr_impl::dsmrr_next

通过上面的分析,是不是感觉 MRR 有点像二级索引与主键的 join 操作,那就是有点和 BKA 有些类似的概念了,咱们下面看一下 BKA 是如何实现的。

BKA 原理

BKA 是指在表连接的过程中为了提升 join 性能而使用的一种 join buffer,其作用是在读取被 join 表的记录的时候使用顺序 IO,BKA 被使用的标识是执行计划的 extra 信息中会有 “Batched Key Access” 信息, 我们首先看一个例子:

DROP TABLE t1, t2;
CREATE TABLE t1 (a int PRIMARY KEY, b int);
CREATE TABLE t2 (a int PRIMARY KEY, b int);
INSERT INTO t1 VALUES (1,2), (2,1), (3,2), (4,3), (5,6), (6,5), (7,8), (8,7), (9,10);
INSERT INTO t2 VALUES (3,0), (4,1), (6,4), (7,5);

mysql> set optimizer_switch="mrr=on,mrr_cost_based=off,batched_key_access=on";
mysql> explain SELECT * FROM t1 LEFT JOIN t2 ON t1.a = t2.a WHERE t2.b <= t1.a AND t1.a <= t1.b;
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-----------------------------------------------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref       | rows | Extra                                               |
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-----------------------------------------------------+
|  1 | SIMPLE      | t2    | ALL    | PRIMARY       | NULL    | NULL    | NULL      |    4 | Using where                                         |
|  1 | SIMPLE      | t1    | eq_ref | PRIMARY       | PRIMARY | 4       | test.t2.a |    1 | Using where; Using join buffer (Batched Key Access) |
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-----------------------------------------------------+
2 rows in set (0.00 sec)

从以上的例子中我们可以看到,在读取表 t1 的时候使用了带 BKA 功能的 join buffer, 其中 BKA & join buffer 的关系与实现我们放在后面详解。

BKA & MRR 之间的关系

使用 BKA 的表的 JOIN 过程如下:

  1. 连接表将满足条件的记录放入JOIN_CACHE,并将两表连接的字段放入一个 DYNAMIC_ARRAY ranges 中,此过程类似于 MRR 操作的过程,且在内存中使用的是同样的结构体 DsMrr_impl;
  2. 在进行表的过接过程中,会将 ranges 相关的信息传入 DsMrr_impl::dsmrr_fill_buffer,并进行被连接表主建的查找及排序等操作操作,这个过程比较复杂,包括需要判断使用的 key、key 是主建时的特殊操作等;
  3. JOIN_CACHE_BKA::join_matching_records 会调用过程2中产生的有序主建,然后顺序读取数据并进入下一步的操作(evaluate_join_record 等);
  4. 当缓冲区的数据被读完后,会重复进行过程2,3, 直到记录被读取完。

由上面的分析可以看出,BKA将有序主建投递到存储引擎是通过 MRR 的接口的调用来实现的(DsMrr_impl::dsmrr_next),所以BKA 依赖 MRR,如果要使用BKA, MRR 是需要打开的,另外 batched_key_access 是默认关闭的,如果要使用,需要打开此选项。
BKA 的详细说明可参考这里

BKA 源码实现

表之间的连接操作是通过 JOIN_CACHE 来做的,5.6 目前实现了 BNL, BKA (JOIN_CACHE_BKA & JOIN_CACHE_BKA_UNIQUE) 两种表连接的优化方式,其中 BKA 就是其中减少随机 IO 的一种方式,BKA内存中对应的结构是 JOIN_CACHE_BKA,咱们首先看一下多表 JOIN 之间的过程;

  1. 优化器生成的执行计划是由一个 JOIN_TAB 的左支树组成,每个 JOIN_TAB 包含了相关的表、使用的索引、语句中包含的条件等信息;
  2. 进入物理执行计划后,会对每一个表进行读数据,然后进入 evaluate_join_record, 当发现满足条件的记录时,则会将该记录添加到下一个JOIN_TAB 中的JOIN_CACHE 中,其堆栈如下:

     #0  JOIN_CACHE::put_record (this=0x2aab00019d20)
     #1  0x000000000099d29c in sub_select_op (join=0x2aab00016268, join_tab=0x2aab00018ed8, end_of_records=false)
     #2  0x000000000099ee1c in evaluate_join_record (join=0x2aab00016268, join_tab=0x2aab00018bd8)
     #3  0x000000000099d984 in sub_select (join=0x2aab00016268, join_tab=0x2aab00018bd8, end_of_records=false)
     #4  0x000000000099c914 in do_select (join=0x2aab00016268)
     #5  0x00000000009982f8 in JOIN::exec (this=0x2aab00016268)
     #6  0x0000000000a5bd7c in mysql_execute_select (thd=0x314d690, select_lex=0x31503a8, free_join=true)
    
  3. 当缓冲区满或者读到文件的末尾时,会调用下一个JOIN_TAB 中 JOIN_CACHE::join_records 方法(BKA 使用时 JOIN_CACHE 为 JOIN_CACHE_BKA),然后会进入 MRR 的相关逻辑,其完整的堆栈为:

     #0  DsMrr_impl::dsmrr_fill_buffer (this=0x2aab000128e0)
     #1  0x00000000006e49dd in DsMrr_impl::dsmrr_init
     #2  0x00000000017d35e4 in ha_myisam::multi_range_read_init
     #3  0x0000000000d838aa in JOIN_CACHE_BKA::init_join_matching_records (this=0x2aab00019d20, seq_funcs=0x2aaafc03dd80, ranges=4)
     #4  0x0000000000d8335c in JOIN_CACHE_BKA::join_matching_records (this=0x2aab00019d20, skip_last=false)
     #5  0x0000000000d812e8 in JOIN_CACHE::join_records (this=0x2aab00019d20, skip_last=false)
     #6  0x0000000000d86ed3 in JOIN_CACHE::end_send (this=0x2aab00019d20)
     #7  0x000000000099d0d1 in sub_select_op (join=0x2aab00016268, join_tab=0x2aab00018ed8, end_of_records=true)
     #8  0x000000000099d3c4 in sub_select (join=0x2aab00016268, join_tab=0x2aab00018bd8, end_of_records=true) at
     #9  0x000000000099c97d in do_select (join=0x2aab00016268)
     #10 0x00000000009982f8 in JOIN::exec (this=0x2aab00016268)
     #11 0x0000000000a5bd7c in mysql_execute_select
    
  4. dsmrr_fill_buffer 的过程相对复杂,需要首先取出两表相连接的字段的索引,如果没有索引,则会使用主建并直接读取,如果使用了索引,则需要从上一个JOIN_TAB中将索引的信息读出来并从 join_cache 的 buffer 中取出该索引的数据,然后再进行回表,查找主建、排序等操作,其堆栈如下:

     #0  JOIN_CACHE_BKA::get_next_key (this=0x2aab00019d20, key=0x2aab0001e178)
     #1  0x0000000000d82f83 in bka_range_seq_next (rseq=0x2aab00019d20, range=0x2aab0001e178)
     #2  0x00000000006e3cac in handler::multi_range_read_next (this=0x2aab0001e020, range_info=0x2aaafc03dc10)
     #3  0x00000000006e5466 in DsMrr_impl::dsmrr_fill_buffer (this=0x2aab000128e0)
     #4  0x00000000006e49dd in DsMrr_impl::dsmrr_init (…)
     #5  0x00000000017d35e4 in ha_myisam::multi_range_read_init (…)
     #6  0x0000000000d838aa in JOIN_CACHE_BKA::init_join_matching_records (this=0x2aab00019d20, seq_funcs=0x2aaafc03dd80, ranges=4)
    

此过程只是两个表的使用 BKA 时的过程,当是多表时,过程将更为复杂。

小结

本篇文章中我们详细的介绍了 MRR、BKA 以及 MRR & BKA 之间的关系等内容,测试用例都是在mrr_cost_based=OFF 的情况下进行的,因为SQL 语句是否使用 MRR 优化依赖于其代价的大小,优化器的代价计算是一个比较复杂的过程,无论是 MRR 还是 BKA 都只是优化器进行优化的方法,当其发现优化后的代价过高时就会不使用该项优化,因此在使用 MRR 相关的优化时,尽量设置 mrr_cost_based=ON,毕竟大多数情况下优化器是对的。