SQL夯實基礎（九）MySQL聯接查詢算法

SQL夯實基礎（九）MySQL聯接查詢算法

　　書接上文《 SQL夯實基礎（八）：聯接運算符算法歸類》。

　　這裡先解釋下EXPLAIN 結果中，第一行出現的表就是驅動表（Important!）。

　　對驅動表可以直接排序，對非驅動表（的字段排序）需要對循環查詢的合并結果（臨時表）進行排序（Important!）

一、聯接過程介紹

　　為了後面一些測試案例，我們事先建立了兩張表，表資料如下：

CREATE TABLE t1 (m1 int, n1 char(1));
CREATE TABLE t2 (m2 int, n2 char(1));
INSERT INTO t1 VALUES(1, 'a'), (2, 'b'), (3, 'c');
INSERT INTO t2 VALUES(2, 'b'), (3, 'c'), (4, 'd'), (5, 'e'), (6, 'f');      

　　聯接操作的本質就是把各個聯接表中的記錄都取出來依次比對的組合加入結果集并傳回給使用者。如果沒有任何限制條件的話，多表聯接起來産生的笛卡爾積可能是非常巨大的。比方說3個100行記錄的表聯接起來産生的笛卡爾積就有100×100×100=1000000行資料！是以在聯接的時候過濾掉特定記錄組合是有必要的，在聯接查詢中的過濾條件可以分成兩種，我們以一個JOIN查詢為例：

SELECT * FROM t1, t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';      

1 涉及單表的條件

WHERE條件也可以稱為搜尋條件，比如t1.m1 > 1是隻針對t1表的過濾條件，t2.n2 < ‘d’是隻針對t2表的過濾條件。

2 涉及兩表的條件

比如t1.m1 = t2.m2、t1.n1 > t2.n2等，這些條件中涉及到了兩個表，我們稍後會仔細分析這種過濾條件是如何使用的。

在這個查詢中我們指明了這三個過濾條件：

1. t1.m1 > 1

2. t1.m1 = t2.m2

3. t2.n2 < ‘d’

那麼這個聯接查詢的大緻執行過程如下：

　　首先确定第一個需要查詢的表，這個表稱之為驅動表。怎樣在單表中執行查詢語句，隻需要選取代價最小的那種通路方法去執行單表查詢語句就好了（就是說從const、ref、ref_or_null、range、index、all這些執行方法中選取代價最小的去執行查詢）。此處假設使用t1作為驅動表，那麼就需要到t1表中找滿足t1.m1 > 1的記錄，假設這裡并沒有給t1字段添加索引，是以此處查詢t1表的通路方法就設定為all吧，也就是采用全表掃描的方式執行單表查詢。關于如何提升聯接查詢的性能我們之後再說，現在先把基本概念捋清楚哈。是以查詢過程就如下圖所示：

　　針對上一步驟中從驅動表産生的結果集中的每一條記錄，分别需要到t2表中查找比對的記錄，所謂比對的記錄，指的是符合過濾條件的記錄。因為是根據t1表中的記錄去找t2表中的記錄，是以t2表也可以被稱之為被驅動表（非驅動表）。比如上一步驟從驅動表中得到了2條記錄，是以需要查詢2次t2表。此時涉及兩個表的列的過濾條件t1.m1 = t2.m2就派上用場了：

當t1.m1 = 2時，過濾條件t1.m1 = t2.m2就相當于t2.m2 = 2，是以此時t2表相當于有了t1.m1 = 2、t2.n2 < ‘d’這兩個過濾條件，然後到t2表中執行單表查詢。

當t1.m1 = 3時，過濾條件t1.m1 = t2.m2就相當于t2.m2 = 3，是以此時t2表相當于有了t1.m1 = 3、t2.n2 < ‘d’這兩個過濾條件，然後到t2表中執行單表查詢。

是以整個聯接查詢的執行過程就如下圖所示：

也就是說整個聯接查詢最後的結果隻有兩條符合過濾條件的記錄：

+------+------+------+------+

| m1   | n1   | m2   | n2   |

+------+------+------+------+

|    2 | b    |    2 | b    |

|    3 | c    |    3 | c    |

+------+------+------+------+      

　　從上邊兩個步驟可以看出來，我們上邊說的這個兩表聯接查詢共需要查詢1次t1表，2次t2表。當然這是在特定的過濾條件下的結果，如果我們把t1.m1 > 1這個條件去掉，那麼從t1表中查出的記錄就有3條，就需要查詢3次t2表了。也就是說在兩表聯接查詢中，驅動表隻需要通路一次，被驅動表可能被通路多次，這種方式在MySQL中有一個專有名詞，叫Nested-Loops Join（嵌套循環聯接）。我們在真正使用MySQL的時候表動不動就是幾百上千萬資料，如果都按照Nested-Loops Join算法，一次Join查詢的代價也太大了。是以下面就來看看MySQL支援的Join算法都有哪些？

二、聯接算法介紹

　　聯接算法是MySQL資料庫用于處理聯接的實體政策。目前MySQL資料庫僅支援Nested-Loops Join算法。而MySQL的分支版本MariaDB除了支援Nested-Loops Join算法外，還支援Classic Hash Join算法。當聯接的表上有索引時，Nested-Loops Join是非常高效的算法。根據B+樹的特性，其聯接的時間複雜度為O(N)，若沒有索引，則可視為最壞的情況，時間複雜度為O(N²)。MySQL資料庫根據不同的使用場合，支援兩種Nested-Loops Join算法，一種是Simple Nested-Loops Join（NLJ）算法，另一種是Block Nested-Loops Join（BNL）算法。

　　在講述MySQL的Join類型與算法前，看看兩張表的Join的過程：

　　上圖的Fetch階段是指當内表關聯的列是輔助索引時，但是需要通路表中的資料，那麼這時就需要再通路主鍵索引才能得到資料的過程，不論表的存儲引擎是InnoDB存儲引擎還是MyISAM，這都是無法避免的，隻是MyISAM的回表速度要快點，因為其輔助索引存放的就是指向記錄的指針，而InnoDB存儲引擎是索引組織表，需要再次通過索引查找才能定位資料。

　　Fetch階段也不是必須存在的，如果是聚集索引聯接，那麼直接就能得到資料，無需回表，也就沒有Fetch這個階段。另外，上述給出了兩張表之間的Join過程，多張表的Join就是繼續上述這個過程。

　　接着計算兩張表Join的成本，這裡有下列幾種概念：

外表的掃描次數，記為O。通常外表的掃描次數都是1，即Join時掃描一次外表（驅動表）的資料即可

内表的掃描次數，記為I。根據不同Join算法，内表（被驅動表）的掃描次數不同

讀取表的記錄數，記為R。根據不同Join算法，讀取記錄的數量可能不同

Join的比較次數，記為M。根據不同Join算法，比較次數不同

回表的讀取記錄的數，記為F。若Join的是輔助索引，可能需要回表取得最終的資料

　　評判一個Join算法是否優劣，就是檢視上述這些操作的開銷是否比較小。當然，這還要考慮I/O的通路方式，順序還是随機，總之Join的調優也是門藝術，并非想象的那麼簡單。

Simple Nested-Loops Join（SNLJ，簡單嵌套循環聯接）

　　Simple Nested-Loops Join算法相當簡單、直接。即外表（驅動表）中的每一條記錄與内表（被驅動表）中的記錄進行比較判斷。對于兩表聯接來說，驅動表隻會被通路一遍，但被驅動表卻要被通路到好多遍，具體通路幾遍取決于對驅動表執行單表查詢後的結果集中的記錄條數。對于内聯接來說，選取哪個表為驅動表都沒關系，而外聯接的驅動表是固定的，也就是說左（外）聯接的驅動表就是左邊的那個表，右（外）聯接的驅動表就是右邊的那個表。（這個隻是一般情況，也有左聯接驅動表選擇右邊的表，mysql優化器有時候會進行優化）

用僞代碼表示一下這個過程就是這樣：

For each row r in R do                         -- 掃描R表（驅動表）
    For each row s in S do                     -- 掃描S表（被驅動表）
        If r and s satisfy the join condition  -- 如果r和s滿足join條件
            Then output the tuple <r, s>       -- 傳回結果集       

下圖能更好地顯示整個SNLJ的過程：

　　其中R表為外部表（Outer Table），S表為内部表（Inner Table）。這是一個最簡單的算法，這個算法的開銷其實非常大。假設在兩張表R和S上進行聯接的列都不含有索引，外表的記錄數為RN，内表的記錄數位SN。根據上一節對于Join算法的評判标準來看，SNLJ的開銷如下表所示：

　　可以看到讀取記錄數的成本和比較次數的成本都是SN*RN，也就是笛卡兒積。假設外表内表都是1萬條記錄，那麼其讀取的記錄數量和Join的比較次數都需要上億。實際上資料庫并不會使用到SNLJ算法。

Index Nested-Loops Join（INLJ，基于索引的嵌套循環聯接）

SNLJ算法雖然簡單明了，但是也是相當的粗暴，需要多次通路内表（每一次都是全表掃描）。是以，在Join的優化時候，通常都會建議在内表建立索引，以此降低Nested-Loop Join算法的開銷，減少内表掃描次數，MySQL資料庫中使用較多的就是這種算法，以下稱為INLJ。來看這種算法的僞代碼：

For each row r in R do                     -- 掃描R表
    lookup s in S index                    -- 查詢S表的索引（固定3~4次IO，B+樹高度）
        If find s == r                     -- 如果r比對了索引s
            Then output the tuple <r, s>   -- 傳回結果集      

　　由于内表上有索引，是以比較的時候不再需要一條條記錄進行比較，而可以通過索引來減少比較，進而加速查詢。整個過程如下圖所示：

　　可以看到外表中的每條記錄通過内表的索引進行通路，就是讀取外部表一行資料，然後去内部表索引進行二分查找比對；而一般B+樹的高度為3~4層，也就是說比對一次的io消耗也就3~4次，是以索引查詢的成本是比較固定的，故優化器都傾向于使用記錄數少的表作為外表（這裡是否又會存在潛在的問題呢？）。故INLJ的算法成本如下表所示：

　　上表Smatch表示通過索引找到比對的記錄數量。同時可以發現，通過索引可以大幅降低内表的Join的比較次數，每次比較1條外表的記錄，其實就是一次indexlookup（索引查找），而每次index lookup的成本就是樹的高度，即IndexHeight。

　　INLJ的算法并不複雜，也算簡單易懂。但是效率是否能達到使用者的預期呢？其實如果是通過表的主鍵索引進行Join，即使是大資料量的情況下，INLJ的效率亦是相當不錯的。因為索引查找的開銷非常小，并且通路模式也是順序的（假設大多數聚集索引的通路都是比較順序的）。

　　大部分人诟病MySQL的INLJ慢，主要是因為在進行Join的時候可能用到的索引并不是主鍵的聚集索引，而是輔助索引，這時INLJ的過程又需要多一步Fetch的過程，而且這個過程開銷會相當的大：

　　由于通路的是輔助索引，如果查詢需要通路聚集索引上的列，那麼必要需要進行回表取資料，看似每條記錄隻是多了一次回表操作，但這才是INLJ算法最大的弊端。首先，輔助索引的index lookup是比較随機I/O通路操作。其次，根據index lookup再進行回表又是一個随機的I/O操作。是以說，INLJ最大的弊端是其可能需要大量的離散操作，這在SSD出現之前是最大的瓶頸。而即使SSD的出現大幅提升了随機的通路性能，但是對比順序I/O，其還是慢了很多，依然不在一個數量級上。

　　另外，在INNER JOIN中，兩張聯接表的順序是可以變換的，即R INNER JOIN S ON Condition P等效于S INNER JOIN R ON Condition P。根據前面描述的Simple Nested-Loops Join算法，優化器在一般情況下總是選擇将聯接列含有索引的表作為内部表。如果兩張表R和S在聯接列上都有索引，并且索引的高度相同，那麼優化器會選擇記錄數少的表作為外部表，這是因為内部表的掃描次數總是索引的高度，與記錄的數量無關。是以，聯接列隻要有一個字段有索引即可，但最好是資料集多的表有索引；但是，但有WHERE條件的時候又另當别論了。

然後我們給上面的 t1.m1 和 t2.m2 分别添加主鍵，看一下下面這個内聯接的執行計劃：

mysql> EXPLAIN SELECT * FROM t1 INNER JOIN t2 on t1.m1 = t2.m2;      

　　可以看到執行計劃是将 t1 表作為驅動表，将 t2 表作為被驅動表，因為對 t2.m2 列的條件是等值查找，比如 t2.m2=2、t2.m2=3 等，是以MySQL把在聯接查詢中對被驅動表使用主鍵值或者唯一二級索引列（二級索引也叫非聚簇索引，唯一就是unique屬性）的值進行等值查找的查詢執行方式稱之為eq_ref。

Tips：如果被驅動表使用了非唯一二級索引列的值進行等值查詢，則查詢方式為 ref。另外，如果被驅動表使用了主鍵或者唯一二級索引列的值進行等值查找，但主鍵或唯一二級索引如果有多個列的話，則查詢類型也會變成 ref。

　　有時候聯接查詢的查詢清單和過濾條件中可能隻涉及被驅動表的部分列，而這些列都是某個索引的一部分，這種情況下即使不能使用eq_ref、ref、ref_or_null或者range這些通路方法執行對被驅動表的查詢的話，也可以使用索引掃描，也就是index的通路方法來查詢被驅動表。是以我們建議在真實工作中最好不要使用*作為查詢清單，最好把真實用到的列作為查詢清單。

這裡為什麼将 t1 作為驅動表？因為表 t1 中的記錄少于表 t2，這樣聯接需要比對的次數就少了，是以SQL優化器選擇表 t1 作為驅動表。

　　若我們執行的SQL帶有WHERE條件時呢？看看不一樣的執行計劃。如果條件為表 t1 的主鍵，執行計劃如下：

mysql> EXPLAIN SELECT * FROM t1 INNER JOIN t2 on t1.m1 = t2.m2 WHERE t1.m1 = 2;

　　可以看到執行計劃算是極優，同時 t1 表還是驅動表，因為經過WHERE條件過濾後的資料隻有一條（我們知道在單表中使用主鍵值或者唯一二級索引列的值進行等值查找的方式稱之為const，是以我們可以看到 t1 的type為const；如果這裡條件為 t1.m1 > 1，那麼自然 type 就為 range），同時 t2.m2 也是主鍵，自然隻有一條資料，type也為const。

　　如果WHERE條件是一個沒有索引的字段呢？執行計劃如下：

mysql> EXPLAIN SELECT * FROM t1 INNER JOIN t2 on t1.m1 = t2.m2 WHERE t1.n1='a';

　　從執行計劃上看跟不加WHERE條件幾乎差不多，但是可以看到filtered為33%了，而不是100%，說明需要傳回的資料量變少了。另外Extra字段中辨別使用了WHERE條件過濾。

如果WHERE條件是一個有索引的字段呢（比如給 t2.n2 添加一個非唯一二級索引）？這裡就不得不提MySQL一個非常重要的特性了，pushed-down conditions（條件下推）優化。就是把索引條件下推到存儲引擎層進行資料的過濾并傳回過濾後的資料。那麼此時的執行計劃就如下：

mysql> EXPLAIN SELECT * FROM t1 INNER JOIN t2 on t1.m1 = t2.m2 WHERE t2.n2='a';

可以看到 t2 表成為了驅動表（經過二級索引過濾後資料隻有1條，是以這裡使用到ref的通路方法）。

如果我們把 t2.n2 換為範圍查詢呢？看執行計劃如下：

mysql> EXPLAIN SELECT * FROM t1 INNER JOIN t2 on t1.m1 = t2.m2 WHERE t2.n2>'a';

可以看到雖然WHERE條件有索引，但由于t2.n2>’a’ 過濾後的資料還是比 t1 表多，是以優化器就選擇了 t1 表作為驅動表。而此時 t2 表的查詢條件類似如下：

SELECT * FROM t2 WHERE t2.m2 = 1 AND t2.n2 > 'a';

由于 t2.m2 是主鍵，t2.n2 有二級索引，優化器平衡了一下，可能覺得 t2.n2 過濾後的資料占全表比例太大，回表的成本比直接通路主鍵成本要高，是以就直接使用了主鍵。如果說 t2.n2 過濾後的資料占全表資料比例較小，是有可能會選擇 idx_n2 索引。

最後，我們使用 t1.n1 與 t2.n2 作為條件，看一下執行計劃如下：

mysql> EXPLAIN SELECT * FROM t1 INNER JOIN t2 on t1.n1 = t2.n2;

　　一切按照我們預想的結果在工作，就是由于 t2.n2 不是主鍵或唯一索引，type類型變成了 ref。

Tips：雖然在INNER JOIN中可以使用pushed-down conditions的優化方式，但是不能直接在OUTER JOIN中使用該方式，因為有些不滿足聯接條件的記錄會通過外部表行的方式再次添加到結果中，是以需要有條件地使用pushed-down conditions的優化。在優化器内部對于聯接查詢會設定一個标志來表示是否啟用pushed-down conditions的過濾。

Block Nested-Loops Join（BNL，基于塊的嵌套循環聯接）

掃描一個表的過程其實是先把這個表從磁盤上加載到記憶體中，然後從記憶體中比較比對條件是否滿足。但記憶體裡可能并不能完全存放的下表中所有的記錄，是以在掃描表前邊記錄的時候後邊的記錄可能還在磁盤上，等掃描到後邊記錄的時候可能記憶體不足，是以需要把前邊的記錄從記憶體中釋放掉。我們前邊又說過，采用Simple Nested-Loop Join算法的兩表聯接過程中，被驅動表可是要被通路好多次的，如果這個被驅動表中的資料特别多而且不能使用索引進行通路，那就相當于要從磁盤上讀好幾次這個表，這個I/O代價就非常大了，是以我們得想辦法：盡量減少通路被驅動表的次數。

當被驅動表中的資料非常多時，每次通路被驅動表，被驅動表的記錄會被加載到記憶體中，在記憶體中的每一條記錄隻會和驅動表結果集的一條記錄做比對，之後就會被從記憶體中清除掉。然後再從驅動表結果集中拿出另一條記錄，再一次把被驅動表的記錄加載到記憶體中一遍，周而複始，驅動表結果集中有多少條記錄，就得把被驅動表從磁盤上加載到記憶體中多少次。是以我們可不可以在把被驅動表的記錄加載到記憶體的時候，一次性和多條驅動表中的記錄做比對，這樣就可以大大減少重複從磁盤上加載被驅動表的代價了。這也就是Block Nested-Loop Join算法的思想。

也就是說在有索引的情況下，MySQL會嘗試去使用Index Nested-Loop Join算法，在有些情況下，可能Join的列就是沒有索引，那麼這時MySQL的選擇絕對不會是最先介紹的Simple Nested-Loop Join算法，因為那個算法太粗暴，不忍直視。資料量大些的複雜SQL估計幾年都可能跑不出結果。而Block Nested-Loop Join算法較Simple Nested-Loop Join的改進就在于可以減少内表的掃描次數，甚至可以和Hash Join算法一樣，僅需掃描内表一次。其使用Join Buffer（聯接緩沖）來減少内部循環讀取表的次數。

For each tuple r in R do                             -- 掃描外表R
    store used columns as p from R in Join Buffer    -- 将部分或者全部R的記錄儲存到Join Buffer中，記為p
    For each tuple s in S do                         -- 掃描内表S
        If p and s satisfy the join condition        -- p與s滿足join條件
            Then output the tuple                    -- 傳回為結果集      

　　可以看到相比Simple Nested-Loop Join算法，Block Nested-LoopJoin算法僅多了一個所謂的Join Buffer，為什麼這樣就能減少内表的掃描次數呢？下圖相比更好地解釋了Block Nested-Loop Join算法的運作過程：

　　可以看到Join Buffer用以緩存聯接需要的列（是以再次提醒我們，最好不要把*作為查詢清單，隻需要把我們關心的列放到查詢清單就好了，這樣還可以在join buffer中放置更多的記錄呢），然後以Join Buffer批量的形式和内表中的資料進行聯接比較。就上圖來看，記錄r1，r2 … rT的聯接僅需掃内表一次，如果join buffer可以緩存所有的外表列，那麼聯接僅需掃描内外表各一次，進而大幅提升Join的性能。

MySQL資料庫使用Join Buffer的原則如下：

* 系統變量Join_buffer_size決定了Join Buffer的大小。

* Join Buffer可被用于聯接是ALL、index、和range的類型。

* 每次聯接使用一個Join Buffer，是以多表的聯接可以使用多個Join Buffer。

* Join Buffer在聯接發生之前進行配置設定，在SQL語句執行完後進行釋放。

* Join Buffer隻存儲要進行查詢操作的相關列資料，而不是整行的記錄。

Join_buffer_size變量

　　是以，Join Buffer并不是那麼好用的。首先變量join_buffer_size用來控制Join Buffer的大小，調大後可以避免多次的内表掃描，進而提高性能。也就是說，當MySQL的Join有使用到Block Nested-Loop Join，那麼調大變量join_buffer_size才是有意義的。而前面的Index Nested-Loop Join如果僅使用索引進行Join，那麼調大這個變量則毫無意義。

　　變量join_buffer_size的預設值是256K，顯然對于稍複雜的SQL是不夠用的。好在這個是會話級别的變量，可以在執行前進行擴充。建議在會話級别進行設定，而不是全局設定，因為很難給一個通用值去衡量。另外，這個記憶體是會話級别配置設定的，如果設定不好容易導緻因無法配置設定記憶體而導緻的當機問題。

Join Buffer緩存對象

　　另外，Join Buffer緩存的對象是什麼，這個問題相當關鍵和重要。然在MySQL的官方手冊中是這樣記錄的：Only columns of interest to the join are stored in the join buffer, not whole rows.

可以發現Join Buffer不是緩存外表的整行記錄，而是緩存“columns of interest”，具體指所有參與查詢的列都會儲存到Join Buffer，而不是隻有Join的列。比如下面的SQL語句，假設沒有索引，需要使用到Join Buffer進行連結：

SELECT a.col3
FROM a,
     b
WHERE a.col1 = b.col2
  AND a.col2 > ….
  AND b.col2 = …      

　　假設上述SQL語句的外表是a，内表是b，那麼存放在Join Buffer中的列是所有參與查詢的列，在這裡就是（a.col1，a.col2，a.col3）。

通過上面的介紹，我們現在可以得到内表的掃描次數為:

Scaninner_table = (RN * used_column_size) / join_buffer_size + 1

對于有經驗的DBA就可以預估需要配置設定的Join Buffer大小，然後盡量使得内表的掃描次數盡可能的少，最優的情況是隻掃描内表一次。

Join Buffer的配置設定

需要牢記的是，Join Buffer是在Join之前就進行配置設定，并且每次Join就需要配置設定一次Join Buffer，是以假設有N張表參與Join，每張表之間通過Block Nested-Loop Join，那麼總共需要配置設定N-1個Join Buffer，這個記憶體容量是需要DBA進行考量的。

在MySQL 5.6（包括MariaDB 5.3）中，優化了Join Buffer在多張表之間聯接的記憶體使用效率。MySQL 5.6将Join Buffer分為Regular join buffer和Incremental join buffer。假設B1是表t1和t2聯接使用的Join Buffer，B2是t1和t2聯接産生的結果和表t3進行聯接使用的join buffer，那麼：

* 如果B2是Regular join buffer，那麼B2就會包含B1的Join Buffer中r1相關的列，以及表t2中相關的列。

* 如果B2是Incremental join buffer，那麼B2包含表t2中的資料及一個指針，該指針指向B1中r1相對應的資料。

是以，對于第一次聯接的表，使用的都是Regular join buffer，之後再聯接，則使用Incremental join buffer。又因為Incremental join buffer隻包含指向之前Join Buffer中資料的指針，是以Join Buffer的記憶體使用效率得到了大幅的提高。

此外，對于NULL類型的列，其實不需要存放在Join Buffer中，而對于VARCHAR類型的列，也是僅需最小的記憶體即可，而不是以CHAR類型在Join Buffer中儲存。最後，在MySQL 5.5版本中，Join Buffer隻能在INNER JOIN中使用，在OUTER JOIN中則不能使用，即Block Nested Loop算法不支援OUTER JOIN。從MySQL 5.6及MariaDB 5.3開始，Join Buffer的使用得到了進一步擴充，在OUTER JOIN中使join buffer得到支援。

Block Nested-Loop Join開銷

　　Block Nested-Loop Join極大的避免了内表的掃描次數，如果Join Buffer可以緩存外表的資料，那麼内表的掃描僅需一次，這和Hash Join非常類似。但是Block Nested-Loop Join依然沒有解決的是Join比較的次數，其仍然通過Join判斷式進行比較。綜上所述，到目前為止各Join算法的成本比較如下所示：

　　這個算法很好測試，我們可以随便建構兩張沒有索引的字段進行聯接，然後檢視一下執行計劃。下面是我在`MySQL 5.7版本上的執行計劃。（這裡把表的主鍵删除掉）

EXPLAIN SELECT * FROM t1 INNER JOIN t2 on t1.m1 = t2.m2 WHERE t2.n2>'c';

　　可以看到，SQL 執行計劃的 Extra 列中提示 Using join buffer (Block Nested Loop)，很明顯使用了BNL算法。

　　另外，可以看出這條 SQL 先根據索引進行了條件過濾，然後拿過濾後的結果集作為驅動表，也是為了減少被驅動表掃描次數。如果 t2.n2 沒有索引呢？使用 BNL 算法來 join 的話，這個語句的執行流程是這樣的，假設表 t1 是驅動表，表 t2 是被驅動表：

1. 把表 t1 的所有字段取出來，存入 join_buffer 中。

2. 掃描表 t2，取出每一行資料跟 join_buffer 中的資料進行對比；如果不滿足 t1.m1=t2.m2，則跳過； 如果滿足 t1.m1=t2.m2，再判斷其他條件，也就是是否滿足 t2.n2>’c’ 的條件，如果是，就作為結果集的一部分傳回，否則跳過。

對于表 t2 的每一行，判斷 join 是否滿足的時候，都需要周遊 join_buffer 中的所有行。是以判斷等值條件的次數是 t1表行數*t2表行數，資料量稍微大點時，這個判斷的次數都是上億次。如果不想在表 t2 的字段 n2 上建立索引，又想減少比較次數。那麼，有沒有兩全其美的辦法呢？這時候，我們可以考慮使用臨時表。使用臨時表的大緻思路是：

1. 把表 t2 中滿足條件的資料放在臨時表 tmp_t 中；

2. 為了讓 join 使用 BKA 算法，給臨時表 tmp_t 的字段 n2 加上索引；

3. 讓表 t1 和 tmp_t 做 join 操作。

Block Nested-Loop Join影響

　　在使用 Block Nested-Loop Join(BNL) 算法時，可能會對被驅動表做多次掃描。如果這個被驅動表是一個大的冷資料表，除了會導緻 IO 壓力大以外，還會對 buffer poll 産生嚴重的影響。

　　如果了解 InnoDB 的 LRU 算法就會知道，由于 InnoDB 對 Bufffer Pool 的 LRU 算法做了優化，即：第一次從磁盤讀入記憶體的資料頁，會先放在 old 區域。如果 1 秒之後這個資料頁不再被通路了，就不會被移動到 LRU 連結清單頭部，這樣對 Buffer Pool 的命中率影響就不大。

　　但是，如果一個使用 BNLe 算法的 join 語句，多次掃描一個冷表，而且這個語句執行時間超過 1 秒，就會在再次掃描冷表的時候，把冷表的資料頁移到 LRU 連結清單頭部。這種情況對應的，是冷表的資料量小于整個 Buffer Pool 的 3/8，能夠完全放入 old 區域的情況。如果這個冷表很大，就會出現另外一種情況：業務正常通路的資料頁，沒有機會進入 young 區域。

　　由于優化機制的存在，一個正常通路的資料頁，要進入 young 區域，需要隔 1 秒後再次被通路到。但是，由于我們的 join 語句在循環讀磁盤和淘汰記憶體頁，進入 old 區域的資料頁，很可能在 1 秒之内就被淘汰了。這樣，就會導緻這個 MySQL 執行個體的 Buffer Pool 在這段時間内，young 區域的資料頁沒有被合理地淘汰。

　　也就是說，這兩種情況都會影響 Buffer Pool 的正常運作。 大表 join 操作雖然對 IO 有影響，但是在語句執行結束後，對 IO 的影響也就結束了。但是，對 Buffer Pool 的影響就是持續性的，需要依靠後續的查詢請求慢慢恢複記憶體命中率。

　　為了減少這種影響，你可以考慮增大 join_buffer_size 的值，減少對被驅動表的掃描次數。

　　也就是說，BNL 算法對系統的影響主要包括三個方面： 可能會多次掃描被驅動表，占用磁盤 IO 資源； 判斷 join 條件需要執行 M*N 次對比（M、N 分别是兩張表的行數），如果是大表就會占用非常多的 CPU 資源； 可能會導緻 Buffer Pool 的熱資料被淘汰，影響記憶體命中率。

Tips：思考這麼一個問題，假設被驅動表全在記憶體中，這個時候 SNLJ 和 BNL 算法還有性能差别嗎？當然是有的，由于 SNLJ 這個算法天然會對被驅動表的資料做多次通路，是以更容易将這些資料頁放到 Buffer Pool 的頭部，進而污染 Buffer Pool。另外，即使被驅動表資料都在記憶體中，但每次查找“下一個記錄的操作”，都是類似指針操作。而 BNL 算法中的 join_buffer 是數組，周遊的成本更低，從被驅動表讀取一條資料去 join_buffer 中周遊。

Batched Key Access Join（BKA，批量鍵通路聯接）

這部分我測試的效果有問題，雖然我也安裝了mysql employee資料庫

　　Index Nested-Loop Join雖好，但是通過輔助索引進行聯接後需要回表，這裡需要大量的随機I/O操作。若能優化随機I/O，那麼就能極大的提升Join的性能。為此，MySQL 5.6（MariaDB 5.3）開始支援Batched Key Access Join算法（簡稱BKA），該算法通過常見的空間換時間，随機I/O轉順序I/O，以此來極大的提升Join的性能。

　　在說明Batched Key Access Join前，首先介紹下MySQL 5.6的新特性mrr——multi range read。因為這個特性也是BKA的重要支柱。MRR優化的目的就是為了減少磁盤的随機通路，InnoDB由于索引組織表的特性，如果你的查詢是使用輔助索引，并且有用到表中非索引列（投影非索引字段，及條件有非索引字段），是以需要回表讀取資料做後續處理，過于随機的回表會伴随着大量的随機I/O。這個過程如下圖所示：

　　而mrr的優化在于，并不是每次通過輔助索引讀取到資料就回表去取記錄，範圍掃描（range access）中MySQL将掃描到的資料存入由read_rnd_buffer_size 變量定義的記憶體大小中，預設256K。然後對其按照Primary Key（RowID）排序，然後使用排序好的資料進行順序回表，因為我們知道InnoDB中葉子節點資料是按照PRIMARY KEY（ROWID）進行順序排列的，是以我們可以認為，如果按照主鍵的遞增順序查詢的話，對磁盤的讀比較接近順序讀，能夠提升讀性能。這對于IO-bound類型的SQL查詢語句帶來性能極大的提升。

　　MRR 能夠提升性能的核心在于，這條查詢語句在索引上做的是一個範圍查詢（也就是說，這是一個多值查詢），可以得到足夠多的主鍵id。這樣通過排序以後，再去主鍵索引查資料，才能展現出“順序性”的優勢。是以MRR優化可用于range，ref，eq_ref類型的查詢，工作方式如下圖：

　　要開啟mrr還有一個比較重的參數是在變量optimizer_switch中的mrr和mrr_cost_based選項。mrr選項預設為on，mrr_cost_based選項預設為off。mrr_cost_based選項表示通過基于成本的算法來确定是否需要開啟mrr特性。然而，在MySQL目前版本中，基于成本的算法過于保守，導緻大部分情況下優化器都不會選擇mrr特性。為了確定優化器使用mrr特性，請執行下面的SQL語句：

set optimizer_switch='mrr=on,mrr_cost_based=off';

但如果強制開啟MRR，那在某些SQL語句下，性能可能會變差；因為MRR需要排序，假如排序的時間超過直接掃描的時間，那性能就會降低。optimizer_switch可以是全局的，也可以是會話級的。

當然，除了調整參數外，資料庫也提供了語句級别的開啟或關閉MRR，使用方法如下：

mysql> explain select /*+ MRR(employees)*/ * from employees where birth_date >= '1996-01-01'\G

了解了 MRR 性能提升的原理，我們就能了解 MySQL 在 5.6 版本後開始引入的 Batched Key Acess(BKA) 算法了。這個 BKA 算法，其實就是對 INLJ 算法的優化。

　　我們知道 INLJ 算法執行的邏輯是：從驅動表一行行地取出 join 條件值，再到被驅動表去做 join。也就是說，對于被驅動表來說，每次都是比對一個值。這時，MRR 的優勢就用不上了。那怎麼才能一次性地多傳些值給被驅動表呢？方法就是，從驅動表裡一次性地多拿些行出來，一起傳給被驅動表。既然如此，我們就把驅動表的資料取出來一部分，先放到一個臨時記憶體。這個臨時記憶體不是别人，就是 join_buffer。

　　我們知道 join_buffer 在 BNL 算法裡的作用，是暫存驅動表的資料。但是在 NLJ 算法裡并沒有用。那麼，我們剛好就可以複用 join_buffer 到 BKA 算法中。NLJ 算法優化後的 BKA 算法的流程，整個過程如下所示：

　　對于多表join語句，當MySQL使用索引通路第二個join表的時候，使用一個join buffer來收集第一個操作對象生成的相關列值。BKA建構好key後，批量傳給引擎層做索引查找。key是通過MRR接口送出給引擎的，這樣，MRR使得查詢更有效率。

　　如果外部表掃描的是主鍵，那麼表中的記錄通路都是比較有序的，但是如果聯接的列是非主鍵索引，那麼對于表中記錄的通路可能就是非常離散的。是以對于非主鍵索引的聯接，Batched Key Access Join算法将能極大提高SQL的執行效率。BKA算法支援内聯接，外聯接和半聯接操作，包括嵌套外聯接。

Batched Key Access Join算法的工作步驟如下：

1. 将外部表中相關的列放入Join Buffer中。

2. 批量的将Key（索引鍵值）發送到Multi-Range Read（MRR）接口。

3. Multi-Range Read（MRR）通過收到的Key，根據其對應的ROWID進行排序，然後再進行資料的讀取操作。

4. 傳回結果集給用戶端。

　　Batched Key Access Join算法的本質上來說還是Simple Nested-Loops Join算法，其發生的條件為内部表上有索引，并且該索引為非主鍵，并且聯接需要通路内部表主鍵上的索引。這時Batched Key Access Join算法會調用Multi-Range Read（MRR）接口，批量的進行索引鍵的比對和主鍵索引上擷取資料的操作，以此來提高聯接的執行效率，因為讀取資料是以順序磁盤IO而不是随機磁盤IO進行的。

　　在MySQL 5.6中預設關閉BKA（MySQL 5.7預設打開），必須将optimizer_switch系統變量的batched_key_access标志設定為on。BKA使用MRR，是以mrr标志也必須打開。目前，MRR的成本估算過于悲觀。是以，mrr_cost_based也必須關閉才能使用BKA。以下設定啟用BKA：

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

　　因為BKA算法的本質是通過MRR接口将非主鍵索引對于記錄的通路，轉化為根據ROWID排序的較為有序的記錄擷取，是以要想通過BKA算法來提高性能，不但需要確定聯接的列參與match的操作（聯接的列可以是唯一索引或者普通索引，但不能是主鍵），還要有對非主鍵列的search操作。例如下列SQL語句：

mysql> explain select a.gender, b.dept_no from employees a, dept_emp b where a.birth_date=b.from_date

　　列a.gender是表employees的資料，但不是通過搜尋idx_birth_date索引就能得到資料，還需要回表通路主鍵來擷取資料。是以這時可以使用BKA算法。但是如果聯接不涉及針對主鍵進一步擷取資料，内部表隻參與聯接判斷，那麼就不會啟用BKA算法，因為沒有必要去調用MRR接口。比如search的主鍵（a.emp_no），那麼肯定就不需要BKA算法了，直接覆寫索引就可以傳回資料了（二級索引有主鍵值）。

mysql> explain select a.emp_no, b.dept_no from employees a, dept_emp b where a.birth_date=b.from_date;

　　在EXPLAIN輸出中，當Extra值包含Using join buffer（Batched Key Access）且類型值為ref或eq_ref時，表示使用BKA。

Classic Hash Join（CHJ）

　　MySQL資料庫雖然提供了BKA Join來優化傳統的JOIN算法，的确在一定程度上可以提升JOIN的速度。但不可否認的是，仍然有許多使用者對于Hash Join算法有着強烈的需求。Hash Join不需要任何的索引，通過掃描表就能快速地進行JOIN查詢，通過利用磁盤的帶寬帶最大程度的解決大資料量下的JOIN問題。

　　MariaDB支援Classic Hash Join算法，該算法不同于Oracle的Grace Hash Join，但是也是通過Hash來進行聯接，不需要索引，可充分利用磁盤的帶寬。

　　其實MariaDB的Classic Hash Join和Block Nested Loop Join算法非常類似（Classic Hash Join也稱為Block Nested Loop Hash Join），但并不是直接通過進行JOIN的鍵值進行比較，而是根據Join Buffer中的對象建立哈希表，内表通過雜湊演算法進行查找，進而在Block Nested Loop Join算法的基礎上，又進一步減少了内表的比較次數，進而提升JOIN的查詢性能。過程如下圖所示：

　　Classic Hash Join算法先将外部表中資料放入Join Buffer中，然後根據鍵值産生一張散清單，這是第一個階段，稱為build階段。随後讀取内部表中的一條記錄，對其應用散列函數，将其和散清單中的資料進行比較，這是第二個階段，稱為probe階段。

　　如果将Hash查找應用于Simple Nested-Loops Join中，則執行計劃的Extra列會顯示BNLH。如果将Hash查找應用于Batched Key Access Join中，則執行計劃的Extra列會顯示BKAH。

同樣地，如果Join Buffer能夠緩存所有驅動表（外表）的查詢列，那麼驅動表和内表的掃描次數都将隻有1次，并且比較的次數也隻是内表記錄數（假設雜湊演算法沖突為0）。反之，需要掃描多次内部表。為了使Classic Hash Join更有效果，應該更好地規劃Join Buffer的大小。

　　要使用Classic Hash Join算法，需要将join_cache_level設定為大于等于4的值，并顯示地打開優化器的選項，設定過程如下：

set join_cache_join=4;

set optimizer_switch='join_cache_hashed=on';

　　最後，各JOIN算法成本之間的比較如下表所示：

　　Hash Join算法雖好，但是僅能用于等值聯接，非等值聯接的JOIN查詢，其就顯得無能為力了。另外，建立哈希表也是費時的工作，但是一旦建立完成後，其就能大幅提升JOIN的速度。是以通常情況下，大表之間的JOIN，Hash Join算法會比較有優勢。小表通過索引查詢，利用BKA Join就已經能很好的完成查詢。目前MySQL 8.0已經出了，但目前還沒有看到Hash Join的身影，不知未來會不會加入。

三、總結

經過上面的學習，我們能發現聯接查詢成本占大頭的就是“驅動表記錄數乘以單次通路被驅動表的成本”，是以我們的優化重點其實就是下面這兩個部分：

1 盡量減少驅動表的記錄數

2 對被驅動表的通路成本盡可能降低

這兩點對于我們實際書寫聯接查詢語句時十分有用，我們需要盡量在被驅動表的聯接列上建立索引（主鍵或唯一索引最優，其次是非唯一二級索引），這樣就可以使用 eq_ref 或 ref 通路方法來降低通路被驅動表的成本了。

<摘錄>

InnoDB存儲引擎 – 姜

MySQL Join算法與調優白皮書 – 姜

https://dev.mysql.com/doc/refman/5.7/en/bnl-bka-optimization.html