從順序隨機(jī)I/O原理來(lái)討論MYSQL MRR NLJ BNL BKA

從順序隨機(jī)I/O原理來(lái)討論MYSQL MRR NLJ BNL BKA


本文只討論innodb存儲(chǔ)引擎，并且有部分觀點(diǎn)為作者觀點(diǎn)，如果有誤請(qǐng)指出。

一、機(jī)械磁盤(pán)原理
    機(jī)械盤(pán)由動(dòng)臂，盤(pán)片，讀寫(xiě)磁頭，主軸組成，磁頭是固定不能動(dòng)的，要讀取相應(yīng)的扇區(qū)只能通過(guò)盤(pán)片的
    旋轉(zhuǎn)。
    每一個(gè)盤(pán)片為雙面，每一個(gè)面上分布有同心圓的磁道，磁道又分為扇區(qū)一般為512 BYTES，現(xiàn)代的磁盤(pán)
    一般外邊緣磁道的扇區(qū)多，內(nèi)磁道的扇區(qū)少，那么一般讀寫(xiě)外邊緣磁道的速度更快，因?yàn)檗D(zhuǎn)速為定值。
    同時(shí)各個(gè)不同盤(pán)片上半徑下同的磁道組成了一個(gè)柱面。
    下圖是一個(gè)典型的磁盤(pán)組織(摘取數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版))
    
    
    如果我們計(jì)ts(seek time)為尋道時(shí)間，tl(latency time)為尋道完成后等待盤(pán)片旋轉(zhuǎn)到特定扇區(qū)的時(shí)間
    tw(transmission time)為傳輸時(shí)間，那么讀取一個(gè)扇區(qū)的時(shí)間為：
    T(I/0) = ts+tl+tw
    
    顯然在讀取數(shù)據(jù)一定的情況下，ts和tl的時(shí)間成了決定因素，而事實(shí)上ts尋道時(shí)間相對(duì)其他而言占用更長(zhǎng)，
    尋道時(shí)間在10毫秒的數(shù)量級(jí)，7200轉(zhuǎn)的tl時(shí)間為1000/7200 約為 100微秒數(shù)量級(jí)，而傳輸時(shí)間更短。
    
    大量的隨機(jī)I/O會(huì)造成頻繁的磁道更換導(dǎo)致過(guò)長(zhǎng)的時(shí)間，很可能讀完幾個(gè)扇區(qū)馬上就要跳到另外的磁道，
    而順序I/O則不然一次定位可以讀取更多的扇區(qū)，從而盡量減少讀取時(shí)間。


二、隨機(jī)I/O和順序I/O模擬
    模擬使用C語(yǔ)言調(diào)用LINUX API完成，主要方式如下：
    讀取一個(gè)大文件程序中限制為900M，而程序順序和隨機(jī)讀取20000個(gè)4096大小的數(shù)據(jù)，并且CPY到其他文件中，
    cpy的文件為81920000字節(jié)
    為了將寫(xiě)操作的影響降低，而將讀操作的影響放大，分別使用
    O_CREAT | O_WRONLY |O_EXCL 打開(kāi)寫(xiě)文件，啟用OS BUFFER，write操作寫(xiě)到OS kernel buffer則結(jié)束，同時(shí)不能開(kāi)啟
                               O_SYNC，開(kāi)始O_SYNC每一次wirte會(huì)調(diào)用fsync(),將寫(xiě)的影響將會(huì)放大。
    O_RDONLY | O_DIRECT 打開(kāi)讀取文件，用O_DIRECT打開(kāi)目的在于禁用OS CACHE當(dāng)然也禁用了OS的預(yù)讀，直接讀取文件
    這方面摘取一張圖便于理解，實(shí)際上我O_DIRECT后讀取這個(gè)文件是不過(guò)內(nèi)核高速緩存的。
    
    
    
    當(dāng)然這個(gè)程序有一點(diǎn)補(bǔ)足，我應(yīng)該使用排序算法將隨機(jī)數(shù)組中的數(shù)據(jù)排序后在進(jìn)行讀取，而不是取一個(gè)連續(xù)的數(shù)組。
    這樣更能說(shuō)明問(wèn)題，但這也不重要因?yàn)殡S機(jī)讀已經(jīng)慢得離譜了。下面是我程序跑出的結(jié)果。

./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
    
先輸出部分?jǐn)?shù)組中的隨機(jī)值，可以看到讀取的位置是隨機(jī)的。從而模擬隨機(jī)讀取，
然后輸出順序讀取寫(xiě)入，然后進(jìn)行隨機(jī)讀取寫(xiě)入。可以看到差別非常大，其實(shí)使用
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

---隨機(jī)
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
這里明顯看出了問(wèn)題，程序放到最后給出。
       
三、MRR
有了上面的基礎(chǔ)，我們明白了順序讀取的重要性，那么我們開(kāi)始看看Multi-Range Read (MRR)，因?yàn)檫@個(gè)特性也是BKA的
重要支柱 
如果了解ORACLE的朋友一定不會(huì)忘記索引集群因子，下面是集群因子的描述在索引的分析數(shù)據(jù)上clustering_factor是一
個(gè)很重要的參數(shù)，表示的是索引和表之間的關(guān)系，因?yàn)?，索引是按照一定的順序排列的，但是，?duì)于表來(lái)說(shuō)是按照一種
heap的形式存放，每一行可能分布在段上任何一個(gè)塊上，所以要是通過(guò)索引來(lái)查找數(shù)據(jù)行的時(shí)候，就有可以一個(gè)索引塊
對(duì)應(yīng)多個(gè)，甚至全部表的塊，所以引入了clustering_factor這個(gè)參數(shù)來(lái)表示表上數(shù)據(jù)存放和索引之間的對(duì)應(yīng)關(guān)系。這樣
CBO就可以根據(jù)這個(gè)參數(shù)來(lái)判斷使用這個(gè)索引產(chǎn)生的cost是多少。
具體參考
(http://blog.itpub.net/7728585/viewspace-612691/)


1、描述
      對(duì)于MYSQL的二級(jí)索引也存在如同ORACLE clustering_factor一樣的問(wèn)題，過(guò)于隨機(jī)的回表會(huì)造成隨即讀取過(guò)于嚴(yán)重
      范圍掃描range access中MYSQL將掃描到的數(shù)據(jù)存入read_rnd_buffer_size，然后對(duì)其按照primary key(rowid)排序，
   然后使用排序好的數(shù)據(jù)進(jìn)行順序回表因?yàn)槲覀冎繧NNODB中是葉節(jié)點(diǎn)數(shù)據(jù)是按照PRIMARY KEY(ROWID)進(jìn)行排列的，那么
   這樣就轉(zhuǎn)換隨機(jī)讀取為順序讀取了。
      而在BKA中則將被連接表使用到ref,eq_ref索引掃描方式的時(shí)候?qū)⒌谝粋€(gè)表中掃描到的鍵值放到j(luò)oin_buffer_size中，
   然后調(diào)用MRR接口進(jìn)行排序和順序訪問(wèn)并且通過(guò)join條件得到數(shù)據(jù)，這樣連接條件之間也成為了順序比對(duì)。
   源碼接口handler::multi_range_read_init handler::multi_range_read_next
   如圖(圖片摘取自mariadb官方文檔)：
   
   
2、適用范圍：
---range access:通過(guò)一個(gè)或者多個(gè)范圍限制進(jìn)行讀取數(shù)據(jù)。
                比如
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,因?yàn)镸RR的代價(jià)評(píng)估一般較高所以這里使用mrr_cost_based=off
如圖(圖片摘取自mariadb官方文檔)：


----ref and eq_ref access：當(dāng)使用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、優(yōu)勢(shì)：
   順序讀取不在需要磁盤(pán)動(dòng)臂不斷的移動(dòng)來(lái)尋道和等待帶盤(pán)片旋轉(zhuǎn)的時(shí)間。
   順序讀取有預(yù)讀的優(yōu)勢(shì)。
   每個(gè)塊值需要讀取一次，而不需要多次讀取，這是理所當(dāng)然，因?yàn)橐粋€(gè)塊中一般存儲(chǔ)了多行數(shù)據(jù)，不使用MRR可能會(huì)導(dǎo)致同一塊多次讀取到。
4、劣勢(shì)：
   排序是額外需要時(shí)間的。如果使用order limit n，會(huì)導(dǎo)致更慢
 
四、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
    }
  }
}
   這種方式采用逐層調(diào)用循環(huán)的方式，很顯然這種方式適用于任何場(chǎng)景，不過(guò)在被連接表沒(méi)有索引的情況下，那么效率極低。


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)

總結(jié)：一般用于被鏈接表有索引的方式ref或者eq_ref,并且BKA代價(jià)較高，被連接表沒(méi)有索引一般使用BNL。


2、A Block Nested-Loop (BNL)


很顯然這種方式一般是用來(lái)優(yōu)化被連接表沒(méi)有索引，這被連接表方式為ALL或者index，因?yàn)檫@種join使用NLJ實(shí)在太慢了，需要優(yōu)化他對(duì)內(nèi)層表
驅(qū)動(dòng)的次數(shù)，那么加入一個(gè)緩存叫做join_buffer_size
我們考慮2個(gè)表連接的方式，如下：
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表的相關(guān)字段，至少testzh20.name包含其中，存入join_buffer_size，
當(dāng)join_buffer_size滿(mǎn)后，對(duì)
testzh進(jìn)行一次掃描，并且對(duì)掃描到的值和join_buffer_size中的數(shù)據(jù)根據(jù)條件testzh.name=testzh20.name
進(jìn)行比對(duì)，如果符合則放回，不符合則拋棄，比對(duì)完成后，清空buffer，繼續(xù)掃描testzh20剩下的數(shù)據(jù)，滿(mǎn)了
后又讀取一次testzh和join_buffer_size中的數(shù)據(jù)根據(jù)條件testzh.name=testzh20.name比對(duì)，如此反復(fù)直到
結(jié)束，我們考慮這樣的優(yōu)化方式相對(duì)于BNL確實(shí)減少讀取testzh表的次數(shù)，而且是大大減少，那為什么不使用
MRR排序后在比對(duì)呢？因?yàn)閠estzh 壓根沒(méi)用到索引，你join_buffer_size中的數(shù)據(jù)排序了，但是testzh表中關(guān)
于testzh20.name的數(shù)據(jù)任然是無(wú)序的，沒(méi)有任何意義，使用MRR這種原理類(lèi)似歸并排序，必須兩個(gè)數(shù)據(jù)集都是
排序好的，所以這里用不到MRR。
總結(jié)：一般用于被連接表方式為ALL或者index(索引覆蓋掃描)

3、Batched Key Access Joins (BKA)

這種方式在MRR中已經(jīng)講了很多，其目的在于優(yōu)化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)


這種方式的原理上就是通過(guò)順序的連接條件的比對(duì)，減少隨機(jī)讀取的可能?？梢詤⒖?br /> https://mariadb.com/kb/en/mariadb/block-based-join-algorithms/
Batch Key Access Join

五、ORACLE中連接方式簡(jiǎn)述

1、NEST LOOP JOIN:驅(qū)動(dòng)表結(jié)果集較少，并且被驅(qū)動(dòng)表有索引的情況下，11G后加入VECTOR I/O,其原理感覺(jué)類(lèi)似MYSQL BKA，將多個(gè)單塊讀取
                  合并，獲得更好的NEST LOOP 性能。
2、SORT MERGE JOIN：這種連接方式類(lèi)使用歸并的方式，既然是歸并一般用于連接條件之間排序好了，及都有索引的情況。
3、hash join：只使用于CBO，由于是HASH算法也就只能用于等值連接，他適用于小表和大表做連接，并且nest loop 效果不好的情況下，
                  對(duì)小表根據(jù)連接字段使用HASH算法，然后由于使用hash算法那么小表連接字段的不同值決定了HASH算法散列的分布均勻性，
                 也直接影響了HASH JOIN的性能，比如自增序列就是很好的HASH連接字段。大表的hash會(huì)占用過(guò)多的臨時(shí)表空間是需要注意
                 的。


參考資料：UNIX系統(tǒng)編程手冊(cè)
          Block-Based Join Algorithms(mariadb)
          Multi Range Read Optimization(mariadb)
          數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版本)
          MySQL 5.7 Reference Manual

隨機(jī)順序?qū)懘a

如果覺(jué)得不錯(cuò) 您可以考慮請(qǐng)作者喝杯茶(微信支付)：                                作者微信號(hào)：