MySQL使用 Nested-Loop Join (NLJ) 算法來執行表之間的連接，NLJ有以下三種實現：
Simple Nested-Loop Join
Index Nested-Loop Join
Bolck Nested-Loop Join
通過下面這段 SQL 我們來分析下這三者的區別。
-- 創建表t1CREATE TABLE t1 ( id INT NOT NULL PRIMARY KEY, a INT NOT NULL, b INT NOT NULL, KEY idx_a ( a ) ) ENGINE = INNODB;
-- 往t1裡初始化1000條數據delimiter;;CREATE PROCEDURE initdata () BEGIN DECLARE i INT; SET i = 1; WHILE i <= 1000 DO INSERT INTO t1 VALUES ( i, i, i ); SET i = i + 1; END WHILE;END;;declimiter;CALL initdata ();
-- 創建表t2，並插入100條數據CREATE TABLE t2 LIKE t1;INSERT INTO t2 ( SELECT * FROM t1 WHERE id <= 100 );
SELECT * FROM t1 INNER JOIN t2 ON t1.a = t2.a;如上，t1 和 t2 都有主鍵索引 id 和索引 a，欄位 b 無索引。存儲過程 initdata() 往 t1 插入1000條數據，再往 t2 插入100條數據。最後 t1 和 t2 做了連表查詢，我特意用了 STRAIGHT_JOIN ，目的是讓優化器按照指定的連接方式執行查詢，如果用 INNER JOIN 的話，則優化器會以小表 t2 為驅動表，然後取每行欄位 a 去 t1 表的索引 idx_a 上做匹配，這樣會影響我們分析 SQL 的執行過程。
Index Nested-Loop Join
下圖是上面 join 語句的 explain 結果：
圖 1 使用索引欄位 join 的 explain 結果
可以看到，表 t1 是驅動表，而且做了全表掃描，被驅動表 t2 的欄位 a 上有索引，join 的過程中用上了這個索引，因此這條 SQL 的執行過程是：
從表 t1 讀入一條數據記為 R；
從 R 中取出 a 欄位，去 t2 表 a 欄位的索引 (idx_a) 中查找；
取出表 t2 中滿足條件的行，跟 R 組成一行，作為結果集的一部分；
重複執行步驟 1 到 3，直至表 t1 的末尾，循環結束。
這就是「Index Nested-Loop Join」 (NLJ) 算法的執行流程，整個過程中表 t1 做了全表掃描，需要掃描 1000 行。對於每一行 R，根據欄位 a 去表 t2 中查找，走的是樹搜索，因為數據是一一對應的，所以每次只掃描一行。因此掃描的總行數是 1100 行。
Simple Nested-Loop Join
現在，我們把 join 語句改成這樣：
SELECT * FROM t1 STRAIGHT_JOIN t2 ON t1.a = t2.b;然後看看這條 SQL 的 explain 結果：
圖 2 不使用索引欄位 join 的 explain 結果
與 NLJ 不同的是，由於欄位 b 沒有建索引，所以 t1 每次去 t2 匹配的時候，都要做一次全表掃描，因此整個過程需要掃描的行數是 1000 * 100 = 10萬行，這個算法就是「Simple Nested-Loop Join」。
類似我們寫程序時的嵌套循環，將外層循環的數據傳遞到內層循環依次去匹配，只要還有表去 join，那麼這個過程就會循環下去。如果 t1 和 t2 都是 10萬行的表，就要掃描 100 億行，這個算法看上去太「笨重」了。
事實上，MySQL 並沒有使用 Simple Nested-Loop Join 算法，從圖2可以看到，表 t2 的 Extra 是 Using where; Using join buffer (Block Nested Loop)，所以 MySQL 使用的是「Bolck Nested-Loog Join」算法，簡稱 BNL。
Bolck Nested-Loog Join
BNL 是通過緩存驅動表的數據來減少被驅動表的掃描次數，MySQL 官方文檔以「Join Buffer」來命名這個緩存。
算法的流程是：
將驅動表 t1 的數據讀入到線程內存 join buffer 中，由於 SQL 語句是 SELECT *，因此是把整行數據放入；
掃描被驅動表 t2，取出每行數據跟 join buffer 中的數據對比，滿足條件的，作為結果集的一部分。
與 Simple Nested-Loop Join 將外層循環的數據傳遞到內層循環依次去匹配的思想不同，BNL 是掃描被驅動表然後與 join buffer 中緩存的驅動表的數據做匹配，所以整個過程總共掃描的行數是 1000 + 100 = 1100 行，數據匹配過程中，需要判斷 1000 * 100 = 10 萬次，因為是內存操作，所以速度會快很多，性能也更好。
在實際應用場景下，join buffer 可能放不下驅動表的數據。join buffer 的大小是由參數 join_buffer_size 設置的，默認是256k。如果放不下驅動表所有數據，MySQL的策略是分段放。
如果 join buffer 放不下 t1 的所有數據，執行過程就變成：
將驅動表 t1 的數據讀入到線程內存 join buffer 中，假設到第 800 行 join buffer 滿了；
掃描被驅動表 t2，取出每行數據跟 join buffer 中的數據對比，滿足條件的，作為結果集的一部分；
清空 join buffer；
繼續掃描 t1，把剩下的 200 行數據放入到 join buffer 中，然後繼續執行第 2 步。
小結
這篇我介紹了 MySQL 執行 join 語句可能使用的三種算法，這三種算法主要是由能否使用被驅動表的索引決定的。通過對三種算法的執行流程，可以得到以下結論：
能否用上被驅動表的索引，對 join 語句的性能影響很大；
不能使用被驅動表的索引，只能使用 Bolck Nested-Loog Join 算法，這樣的 SQL 儘量不要用，需要去優化。尤其是在大表上的 join 操作，可能要掃描被驅動表很多次，會佔用大量系統資源；
在使用 join 語句時，應該讓小表做驅動表。
Reference:
https://dev.mysql.com/doc/refman/5.6/en/nested-loop-joins.html
極客時間《MySQL實戰45講》