在數(shù)據(jù)庫處理中，Join操作是最基本且最重要的操作之一，它能將不同的表連接起來，實(shí)現(xiàn)對(duì)數(shù)據(jù)集的更深層次分析。
MySQL作為一款流行的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，其在執(zhí)行Join操作時(shí)使用了多種高效的算法，包括Index Nested-Loop Join（NLJ）和Block Nested-Loop Join（BNL）。這些算法各有優(yōu)缺點(diǎn)，本文將探討這兩種算法的工作原理，以及如何在MySQL中使用它們。
什么是Join
在MySQL中，Join是一種用于組合兩個(gè)或多個(gè)表中數(shù)據(jù)的查詢操作。Join操作通常基于兩個(gè)表中的某些共同的列進(jìn)行，這些列在兩個(gè)表中都存在。MySQL支持多種類型的Join操作，如Inner Join、Left Join、Right Join等。
Inner Join是最常見的Join類型之一。在Inner Join操作中，只有在兩個(gè)表中都存在的行才會(huì)被返回。
例如，如果我們有一個(gè)“customers”表和一個(gè)“orders”表，我們可以通過在這兩個(gè)表中共享“customer_id”列來組合它們的數(shù)據(jù)。
SELECT *
FROM customers
INNER JOIN orders
ON customers.customer_id = orders.customer_id;
上面的查詢將返回所有存在于“customers”和“orders”表中的“customer_id”列相同的行。
Index Nested-Loop Join
Index Nested-Loop Join（NLJ）算法是Join算法中最基本的算法之一。
在NLJ算法中，MySQL首先會(huì)選擇一個(gè)表（通常是小型表）作為驅(qū)動(dòng)表，并迭代該表中的每一行。然后，MySQL在第二個(gè)表中搜索匹配條件的行，這個(gè)搜索過程通常使用索引來完成。一旦找到匹配的行，MySQL將這些行組合在一起，并將它們作為結(jié)果集返回。
工作流程如圖：
例如，執(zhí)行下面這個(gè)語句：
select * from t1 strAIght_join t2 on (t1.a=t2.a);
注：當(dāng)使用
straight_join時(shí)，MySQL會(huì)強(qiáng)制按照在查詢中指定的從左到右的順序執(zhí)行連接。
在這個(gè)語句里，假設(shè) t1 是驅(qū)動(dòng)表，t2 是被驅(qū)動(dòng)表。我們來看一下這條語句的explain結(jié)果。
可以看到，在這條語句里，被驅(qū)動(dòng)表t2的字段a上有索引，join過程用上了這個(gè)索引，因此這個(gè)語句的執(zhí)行流程是這樣的：
-
從表t1中讀入一行數(shù)據(jù) R； -
從數(shù)據(jù)行R中，取出a字段到表t2里去查找； -
取出表t2中滿足條件的行，跟R組成一行，作為結(jié)果集的一部分； -
重復(fù)執(zhí)行步驟1到3，直到表t1的末尾循環(huán)結(jié)束。
這個(gè)過程就跟我們寫程序時(shí)的嵌套查詢類似，并且可以用上被驅(qū)動(dòng)表的索引，所以我們稱之為「Index Nested-Loop Join」，簡稱NLJ。
NLJ是使用上了索引的情況，那如果查詢條件沒有使用到索引呢？
MySQL會(huì)選擇使用另一個(gè)叫作「Block Nested-Loop Join」的算法，簡稱BNL。
Block Nested-Loop Join
Block Nested Loop Join（BNL）算法與NLJ算法不同的是，BNL算法使用一個(gè)類似于緩存的機(jī)制，將表數(shù)據(jù)分成多個(gè)塊，然后逐個(gè)處理這些塊，以減少內(nèi)存和CPU的消耗。
例如，執(zhí)行下面這個(gè)語句：
select * from t1 straight_join t2 on (t1.a=t2.b);
如果 t2 表的字段b上是沒有建立索引的。這時(shí)候，被驅(qū)動(dòng)表上沒有可用的索引，算法的流程是這樣的：
-
把表t1的數(shù)據(jù)讀入線程內(nèi)存 join_buffer中，由于我們這個(gè)語句中寫的是select *，因此是把整個(gè)表t1放入了內(nèi)存； -
掃描表t2，把表t2中的每一行取出來，跟 join_buffer中的數(shù)據(jù)做對(duì)比，滿足join條件的，作為結(jié)果集的一部分返回。
這條SQL語句的explain結(jié)果如下所示：
可以看到，在這個(gè)過程中，MySQL對(duì)表 t1 和 t2 都做了一次全表掃描，因此總的掃描行數(shù)是1100。
由于join_buffer是以無序數(shù)組的方式組織的，因此對(duì)表t2中的每一行，都要做100次判斷，總共需要在內(nèi)存中做的判斷次數(shù)是：100*1000=10萬次。
雖然Block Nested-Loop Join算法是全表掃描。但是是在內(nèi)存中進(jìn)行的判斷操作，速度上會(huì)快很多。但是性能仍然不如NLJ。
join_buffer的大小是由參數(shù)join_buffer_size設(shè)定的，默認(rèn)值是256k。
那如果join_buffer_size的大小不足以放下表t1的所有數(shù)據(jù)呢？
辦法很簡單，就是分段放，執(zhí)行流程如下：
-
順序讀取數(shù)據(jù)行放入 join_buffer中，直到join_buffer滿了。 -
掃描被驅(qū)動(dòng)表跟 join_buffer中的數(shù)據(jù)做對(duì)比，滿足join條件的，作為結(jié)果集的一部分返回。 -
清空 join_buffer，重復(fù)上述步驟。
雖然分成多次放入join_buffer，但是判斷等值條件的次數(shù)還是不變的，依然是10萬次。
MRR & BKA
上篇文章里我們有提到MRR（Multi-Range Read）。MySQL在5.6版本后引入了**Batched Key Acess(BKA)**算法，這個(gè)BKA算法，其實(shí)就是對(duì)NLJ算法的優(yōu)化，而BKA算法正是基于MRR。
NLJ算法執(zhí)行的邏輯是：從驅(qū)動(dòng)表t1，一行行地取出a的值，再到被驅(qū)動(dòng)表t2去做join。也就是說，對(duì)于表t2來說，每次都是匹配一個(gè)值。這時(shí)，MRR的優(yōu)勢(shì)就用不上了。
其實(shí)我們可以從表t1里一次性地多拿些行出來，先放到一個(gè)臨時(shí)內(nèi)存，一起傳給表t2。這個(gè)臨時(shí)內(nèi)存不是別人，就是join_buffer。
通過上一篇文章，我們知道join_buffer 在BNL算法里的作用，是暫存驅(qū)動(dòng)表的數(shù)據(jù)。但是在NLJ算法里并沒有用。那么，我們剛好就可以復(fù)用join_buffer到BKA算法中。
NLJ算法優(yōu)化后的BKA算法的流程，如圖所示：
圖中，在join_buffer中放入的數(shù)據(jù)是R1~R100，表示的是只會(huì)取查詢需要的字段。當(dāng)然，如果join buffer放不下R1~R100的所有數(shù)據(jù)，就會(huì)把這100行數(shù)據(jù)分成多段執(zhí)行上圖的流程。
如果要使用BKA優(yōu)化算法的話，你需要在執(zhí)行SQL語句之前，先設(shè)置
set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
其中，前兩個(gè)參數(shù)的作用是要啟用MRR。這么做的原因是，BKA算法的優(yōu)化要依賴于MRR。
對(duì)于BNL，我們可以通過建立索引轉(zhuǎn)為BKA。但是，有時(shí)候你確實(shí)會(huì)碰到一些不適合在被驅(qū)動(dòng)表上建索引的情況。比如下面這個(gè)語句：
select * from t1 join t2 on (t1.b=t2.b) where t2.b>=1 and t2.b<=2000;
假設(shè)t1表1000行，t2表100萬行，t2.b<=2000過濾后，t2表需要參與join的只有2000行數(shù)據(jù)。
如果這條語句是一個(gè)低頻的SQL語句，那么在表t2的字段b上創(chuàng)建索引就很浪費(fèi)了。
這時(shí)候，我們可以考慮使用臨時(shí)表。使用臨時(shí)表的大致思路是：
-
把表t2中滿足條件的數(shù)據(jù)放在臨時(shí)表tmp_t中； -
為了讓join使用BKA算法，給臨時(shí)表tmp_t的字段b加上索引； -
讓表t1和tmp_t做join操作。
此時(shí)，對(duì)應(yīng)的SQL語句的寫法如下：
create temporary table temp_t(id int primary key, a int, b int, index(b))engine=innodb;
insert into temp_t select * from t2 where b>=1 and b<=2000;
select * from t1 join temp_t on (t1.b=temp_t.b);
總體來看，不論是在原表上加索引，還是用有索引的臨時(shí)表，我們的思路都是讓join語句能夠用上被驅(qū)動(dòng)表上的索引，來觸發(fā)BKA算法，提升查詢性能。
總結(jié)
在MySQL中，不管Join使用的是NLJ還是BNL總是應(yīng)該使用小表做驅(qū)動(dòng)表。更準(zhǔn)確地說，在決定哪個(gè)表做驅(qū)動(dòng)表的時(shí)候，應(yīng)該是兩個(gè)表按照各自的條件過濾，過濾完成之后，計(jì)算參與join的各個(gè)字段的總數(shù)據(jù)量，數(shù)據(jù)量小的那個(gè)表，就是“小表”，應(yīng)該作為驅(qū)動(dòng)表。
另外應(yīng)當(dāng)盡量避免使用BNL算法，如果確認(rèn)優(yōu)化器會(huì)使用BNL算法，就需要做優(yōu)化。優(yōu)化的常見做法是，給被驅(qū)動(dòng)表的join字段加上索引，把BNL算法轉(zhuǎn)成BKA算法。對(duì)于不好在索引的情況，可以基于臨時(shí)表的改進(jìn)方案，提前過濾出小數(shù)據(jù)添加索引。
