从顺序随机I/O原理来讨论MYSQL MRR NLJ BNL BKA

从顺序随机I/O原理来讨论MYSQL MRR NLJ BNL BKA


本文只讨论innodb存储引擎，并且有部分观点为作者观点，如果有误请指出。

一、机械磁盘原理
    机械盘由动臂，盘片，读写磁头，主轴组成，磁头是固定不能动的，要读取相应的扇区只能通过盘片的
    旋转。
    每一个盘片为双面，每一个面上分布有同心圆的磁道，磁道又分为扇区一般为512 BYTES，现代的磁盘
    一般外边缘磁道的扇区多，内磁道的扇区少，那么一般读写外边缘磁道的速度更快，因为转速为定值。
    同时各个不同盘片上半径下同的磁道组成了一个柱面。
    下图是一个典型的磁盘组织(摘取数据结构(C语言版))
    
    
    如果我们计ts(seek time)为寻道时间，tl(latency time)为寻道完成后等待盘片旋转到特定扇区的时间
    tw(transmission time)为传输时间，那么读取一个扇区的时间为：
    T(I/0) = ts+tl+tw
    
    显然在读取数据一定的情况下，ts和tl的时间成了决定因素，而事实上ts寻道时间相对其他而言占用更长，
    寻道时间在10毫秒的数量级，7200转的tl时间为1000/7200 约为 100微秒数量级，而传输时间更短。
    
    大量的随机I/O会造成频繁的磁道更换导致过长的时间，很可能读完几个扇区马上就要跳到另外的磁道，
    而顺序I/O则不然一次定位可以读取更多的扇区，从而尽量减少读取时间。


二、随机I/O和顺序I/O模拟
    模拟使用C语言调用LINUX API完成，主要方式如下：
    读取一个大文件程序中限制为900M，而程序顺序和随机读取20000个4096大小的数据，并且CPY到其他文件中，
    cpy的文件为81920000字节
    为了将写操作的影响降低，而将读操作的影响放大，分别使用
    O_CREAT | O_WRONLY |O_EXCL 打开写文件，启用OS BUFFER，write操作写到OS kernel buffer则结束，同时不能开启
                               O_SYNC，开始O_SYNC每一次wirte会调用fsync(),将写的影响将会放大。
    O_RDONLY | O_DIRECT 打开读取文件，用O_DIRECT打开目的在于禁用OS CACHE当然也禁用了OS的预读，直接读取文件
    这方面摘取一张图便于理解，实际上我O_DIRECT后读取这个文件是不过内核高速缓存的。
    
    
    
    当然这个程序有一点补足，我应该使用排序算法将随机数组中的数据排序后在进行读取，而不是取一个连续的数组。
    这样更能说明问题，但这也不重要因为随机读已经慢得离谱了。下面是我程序跑出的结果。

./a.out p10404530_112030_Linux-x86-64_1of7.zip
fisrt sca array: 134709
fisrt sca array: 198155
fisrt sca array: 25305
fisrt sca array: 46515
fisrt sca array: 91550
fisrt sca array: 137262
fisrt sca array: 46134
fisrt sca array: 10208
fisrt sca array: 142115
......    
sequential cpy begin Time: Fri Dec  2 01:36:55 2016
begin cpy use sequential read buffer is 4k:
per 25 % ,Time:Fri Dec  2 01:36:56 2016
per 50 % ,Time:Fri Dec  2 01:36:57 2016
per 75 % ,Time:Fri Dec  2 01:36:57 2016
per 100 % ,Time:Fri Dec  2 01:36:58 2016

scattered cpy begin Time: Fri Dec  2 01:36:58 2016
begin cpy use scattered read read buffer is 4k:
per 25 % ,Time:Fri Dec  2 01:37:51 2016
per 50 % ,Time:Fri Dec  2 01:38:40 2016
per 75 % ,Time:Fri Dec  2 01:39:29 2016
per 100 % ,Time:Fri Dec  2 01:40:20 2016
    
先输出部分数组中的随机值，可以看到读取的位置是随机的。从而模拟随机读取，
然后输出顺序读取写入，然后进行随机读取写入。可以看到差别非常大，其实使用
iostat vmstat 都能看到读取的速度非常慢。下面给出比较：
--顺序
Device:         rrqm/s   wrqm/s     r/s     w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
sda               0.00     0.00 4979.38    2.06 19967.01    32.99     8.03     0.76    0.15   0.14  70.21
Device:         rrqm/s   wrqm/s     r/s     w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
sda               0.00     0.00 7204.12    0.00 28816.49     0.00     8.00     0.98    0.14   0.14  98.04
Device:         rrqm/s   wrqm/s     r/s     w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
sda               0.00     9.09 7114.14    9.09 28456.57    96.97     8.02     1.04    0.15   0.13  95.86

---随机
Device:         rrqm/s   wrqm/s     r/s     w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
sda               0.00     0.00  107.14    0.00   428.57     0.00     8.00     1.01    9.49   9.42 100.92
Device:         rrqm/s   wrqm/s     r/s     w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
sda               0.00     0.00  104.17    1.04   416.67     0.52     7.93     1.04    9.79   9.81 103.23
Device:         rrqm/s   wrqm/s     r/s     w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
sda               0.00     0.00  104.12    2.06   465.98    32.99     9.40     1.17   11.02   9.68 102.78
这里明显看出了问题，程序放到最后给出。
       
三、MRR
有了上面的基础，我们明白了顺序读取的重要性，那么我们开始看看Multi-Range Read (MRR)，因为这个特性也是BKA的
重要支柱 
如果了解ORACLE的朋友一定不会忘记索引集群因子，下面是集群因子的描述在索引的分析数据上clustering_factor是一
个很重要的参数，表示的是索引和表之间的关系，因为，索引是按照一定的顺序排列的，但是，对于表来说是按照一种
heap的形式存放，每一行可能分布在段上任何一个块上，所以要是通过索引来查找数据行的时候，就有可以一个索引块
对应多个，甚至全部表的块，所以引入了clustering_factor这个参数来表示表上数据存放和索引之间的对应关系。这样
CBO就可以根据这个参数来判断使用这个索引产生的cost是多少。
具体参考
(http://blog.itpub.net/7728585/viewspace-612691/)


1、描述
      对于MYSQL的二级索引也存在如同ORACLE clustering_factor一样的问题，过于随机的回表会造成随即读取过于严重
      范围扫描range access中MYSQL将扫描到的数据存入read_rnd_buffer_size，然后对其按照primary key(rowid)排序，
   然后使用排序好的数据进行顺序回表因为我们知道INNODB中是叶节点数据是按照PRIMARY KEY(ROWID)进行排列的，那么
   这样就转换随机读取为顺序读取了。
      而在BKA中则将被连接表使用到ref,eq_ref索引扫描方式的时候将第一个表中扫描到的键值放到join_buffer_size中，
   然后调用MRR接口进行排序和顺序访问并且通过join条件得到数据，这样连接条件之间也成为了顺序比对。
   源码接口handler::multi_range_read_init handler::multi_range_read_next
   如图(图片摘取自mariadb官方文档)：
   
   
2、适用范围：
---range access:通过一个或者多个范围限制进行读取数据。
                比如
mysql> set optimizer_switch='mrr_cost_based=off';
Query OK, 0 rows affected (0.00 sec)


mysql> explain select * from testzh force index(id2) where id2=100 and id3<100;
+----+-------------+--------+------------+-------+---------------+------+---------+------+------+----------+----------------------------------+
| id | select_type | table  | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                            |
+----+-------------+--------+------------+-------+---------------+------+---------+------+------+----------+----------------------------------+
|  1 | SIMPLE      | testzh | NULL       | range | id2           | id2  | 10      | NULL |    1 |   100.00 | Using index condition; Using MRR |
+----+-------------+--------+------------+-------+---------------+------+---------+------+------+----------+----------------------------------+
1 row in set, 1 warning (0.00 sec)


使用了ICP和MRR,因为MRR的代价评估一般较高所以这里使用mrr_cost_based=off
如图(图片摘取自mariadb官方文档)：


----ref and eq_ref access：当使用BKA(Batched Key Access),使用到连接索引，键值唯一(非主键)或者不唯一或者使用组合索引前缀
比如：
mysql> set optimizer_switch='mrr_cost_based=off,batched_key_access=on';
Query OK, 0 rows affected (0.00 sec)                 
mysql> explain select * from testzh,testzh20 where  testzh.id2=testzh20.id2 ;
+----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref             | rows   | filtered | Extra                                  |
+----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+
|  1 | SIMPLE      | testzh   | NULL       | ALL  | id2,id2_2     | NULL | NULL    | NULL            | 100031 |   100.00 | Using where                            |
|  1 | SIMPLE      | testzh20 | NULL       | ref  | id2           | id2  | 5       | test.testzh.id2 |      1 |   100.00 | Using join buffer (Batched Key Access) |
+----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+
2 rows in set, 1 warning (0.00 sec)
如图(图片摘取自mariadb官方文档)：


3、优势：
   顺序读取不在需要磁盘动臂不断的移动来寻道和等待带盘片旋转的时间。
   顺序读取有预读的优势。
   每个块值需要读取一次，而不需要多次读取，这是理所当然，因为一个块中一般存储了多行数据，不使用MRR可能会导致同一块多次读取到。
4、劣势：
   排序是额外需要时间的。如果使用order limit n，会导致更慢
 
四、NLJ、BNL、BKA   


1、A simple nested-loop join (NLJ) 
  使用MYSQL文档中伪代码的描述：
for each row in t1 matching range {
   for each row in t2 matching reference key {
      for each row in t3 {
         if row satisfies join conditions,
          send to client
    }
  }
}
   这种方式采用逐层调用循环的方式，很显然这种方式适用于任何场景，不过在被连接表没有索引的情况下，那么效率极低。


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


---ref 索引扫描
mysql> explain select * from testzh force index(id2),testzh20 where  testzh.id2=testzh20.id2;
+----+-------------+----------+------------+------+---------------+------+---------+-------------------+-------+----------+-------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref               | rows  | filtered | Extra       |
+----+-------------+----------+------------+------+---------------+------+---------+-------------------+-------+----------+-------------+
|  1 | SIMPLE      | testzh20 | NULL       | ALL  | id2           | NULL | NULL    | NULL              | 99900 |   100.00 | Using where |
|  1 | SIMPLE      | testzh   | NULL       | ref  | id2           | id2  | 5       | test.testzh20.id2 |     1 |   100.00 | NULL        |
+----+-------------+----------+------------+------+---------------+------+---------+-------------------+-------+----------+-------------+
2 rows in set, 1 warning (0.00 sec)


---ALL 全表扫描
mysql> explain select * from testzh force index(id2),testzh20 where  testzh.name=testzh20.name;
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | testzh20 | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  99900 |   100.00 | NULL        |
|  1 | SIMPLE      | testzh   | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 100031 |    10.00 | Using where |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+
2 rows in set, 1 warning (0.00 sec)

总结：一般用于被链接表有索引的方式ref或者eq_ref,并且BKA代价较高，被连接表没有索引一般使用BNL。


2、A Block Nested-Loop (BNL)


很显然这种方式一般是用来优化被连接表没有索引，这被连接表方式为ALL或者index，因为这种join使用NLJ实在太慢了，需要优化他对内层表
驱动的次数，那么加入一个缓存叫做join_buffer_size
我们考虑2个表连接的方式，如下：
mysql> explain select * from testzh ,testzh20 where  testzh.name=testzh20.name;
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra                                              |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
|  1 | SIMPLE      | testzh20 | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  99900 |   100.00 | NULL                                               |
|  1 | SIMPLE      | testzh   | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 100031 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
2 rows in set, 1 warning (0.00 sec)


扫描testzh20表的相关字段，至少testzh20.name包含其中，存入join_buffer_size，
当join_buffer_size满后，对
testzh进行一次扫描，并且对扫描到的值和join_buffer_size中的数据根据条件testzh.name=testzh20.name
进行比对，如果符合则放回，不符合则抛弃，比对完成后，清空buffer，继续扫描testzh20剩下的数据，满了
后又读取一次testzh和join_buffer_size中的数据根据条件testzh.name=testzh20.name比对，如此反复直到
结束，我们考虑这样的优化方式相对于BNL确实减少读取testzh表的次数，而且是大大减少，那为什么不使用
MRR排序后在比对呢？因为testzh 压根没用到索引，你join_buffer_size中的数据排序了，但是testzh表中关
于testzh20.name的数据任然是无序的，没有任何意义，使用MRR这种原理类似归并排序，必须两个数据集都是
排序好的，所以这里用不到MRR。
总结：一般用于被连接表方式为ALL或者index(索引覆盖扫描)

3、Batched Key Access Joins (BKA)

这种方式在MRR中已经讲了很多，其目的在于优化ref或者eq_ref使用NLJ连接的方式
mysql> explain select * from testzh ,testzh20 where  testzh.id2=testzh20.id2;
+----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref             | rows   | filtered | Extra                                  |
+----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+
|  1 | SIMPLE      | testzh   | NULL       | ALL  | id2           | NULL | NULL    | NULL            | 100031 |   100.00 | Using where                            |
|  1 | SIMPLE      | testzh20 | NULL       | ref  | id2           | id2  | 5       | test.testzh.id2 |      1 |   100.00 | Using join buffer (Batched Key Access) |
+----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+
2 rows in set, 1 warning (0.00 sec)


这种方式的原理上就是通过顺序的连接条件的比对，减少随机读取的可能。可以参考
https://mariadb.com/kb/en/mariadb/block-based-join-algorithms/
Batch Key Access Join

五、ORACLE中连接方式简述

1、NEST LOOP JOIN:驱动表结果集较少，并且被驱动表有索引的情况下，11G后加入VECTOR I/O,其原理感觉类似MYSQL BKA，将多个单块读取
                  合并，获得更好的NEST LOOP 性能。
2、SORT MERGE JOIN：这种连接方式类使用归并的方式，既然是归并一般用于连接条件之间排序好了，及都有索引的情况。
3、hash join：只使用于CBO，由于是HASH算法也就只能用于等值连接，他适用于小表和大表做连接，并且nest loop 效果不好的情况下，
                  对小表根据连接字段使用HASH算法，然后由于使用hash算法那么小表连接字段的不同值决定了HASH算法散列的分布均匀性，
                 也直接影响了HASH JOIN的性能，比如自增序列就是很好的HASH连接字段。大表的hash会占用过多的临时表空间是需要注意
                 的。


参考资料：UNIX系统编程手册
          Block-Based Join Algorithms(mariadb)
          Multi Range Read Optimization(mariadb)
          数据结构(C语言版本)
          MySQL 5.7 Reference Manual

随机顺序写代码