在MySQL的實現中，Nested-Loop Join有3種實現的算法：

• Simple Nested-Loop Join：簡單嵌套循環連接
• Block Nested-Loop Join：緩存塊嵌套循環連接
• Index Nested-Loop Join：索引嵌套循環連接

一、原理篇

1、Simple Nested-Loop Join

比如：

SELECT *
FROM user u
 LEFT JOIN class c ON u.id = c.user_id

我們來看一下當進行 join 操作時，mysql是如何工作的：

當我們進行left join連接操作時，左邊的表是 「驅動表」 ，右邊的表是**「被驅動表」**

特點：

Simple Nested-Loop Join 簡單粗暴容易理解，就是通過雙層循環比較數據來獲得結果，但是這種算法顯然太過于粗魯，如果每個表有1萬條數據，那么對數據比較的次數=1萬 * 1萬 =1億次，很顯然這種查詢效率會非常慢。

「這個全是磁盤掃描！」

?因為每次從驅動表取數據比較耗時，所以MySQL即使在沒有索引命中的情況下也并沒有采用這種算法來進行連接操作,而是下面這種！

?

2、Block Nested-Loop Join

同樣以上面的sql為例，我們看下mysql是如何工作的

SELECT *
FROM user u
 LEFT JOIN class c ON u.id = c.user_id

因為每次從驅動表取一條數據都是磁盤掃描所有比較耗時。

這里就做了優化就是 「每次從驅動表取一批數據放到內存中，然后對這一批數據進行匹配操作」 。

這批數據匹配完畢，再從驅動表中取一批數據放到內存中，直到驅動表的數據全都匹配完畢。

這塊內存在MySQL中有一個專有的名詞，叫做 join buffer，我們可以執行如下語句查看 join buffer 的大小

show variables like '%join_buffer%'

另外，Join Buffer緩存的對象是什么，這個問題相當關鍵和重要。

?Join Buffer存儲的并不是驅動表的整行記錄，具體指所有參與查詢的列都會保存到Join Buffer，而不是只有Join的列。

?

比如下面sql

SELECT a.col3
FROM a JOIN b ON a.col1 = b.col2
WHERE a.col2 > 0 AND b.col2 = 0

上述SQL語句的驅動表是a，被驅動表是b，那么存放在Join Buffer中的列是所有參與查詢的列，在這里就是(a.col1，a.col2，a.col3)。

也就是說查詢的字段越少,Join Buffer可以存的記錄也就越多！

變量join_buffer_size的默認值是256K，顯然對于稍復雜的SQL是不夠用的。好在這個是會話級別的變量，可以在執行前進行擴展。

建議在會話級別進行設置，而不是全局設置，因為很難給一個通用值去衡量。另外，這個內存是會話級別分配的，如果設置不好容易導致因無法分配內存而導致的宕機問題。

-- 調整到1M
set session join_buffer_size = 1024 * 1024 * 1024;
-- 再執行查詢
SELECT a.col3
FROM a JOIN b ON a.col1 = b.col2
WHERE a.col2 > 0 AND b.col2 = 0

3、Index Nested-Loop Join

當我們了解**「Block Nested-Loop Join」** 算法，我們發現雖然可以將驅動表的數據放入 「Join Buffer」 中,但是緩存中的每條記錄都要和被驅動表的所有記錄都匹配一遍，也會非常耗時，所以我們應該如何提高被驅動表匹配的效率呢？

其實很簡單 就是給被驅動表連接的列加上索引，這樣匹配的過程就非常快，如圖所示

上面圖中就是先匹配索引看有沒有命中的數據，有命中數據再回表查詢這條記錄，獲取其它所需要的數據，但列的數據在索引中都能獲取那都不需要回表查詢，效率更高！

二、SQL示例

1、新增表和填充數據

-- 表1 a字段加索引 b字段沒加
CREATE TABLE `t1` (
  `id` int NOT NULL AUTO_INCREMENT COMMENT '主鍵',
  `a` int DEFAULT NULL COMMENT '字段a',
  `b` int DEFAULT NULL COMMENT '字段b',
  PRIMARY KEY (`id`),
  KEY `idx_a` (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

-- 表2
 create table t2 like t1;

-- t1插入10000條數據 t2插入100條數據
 drop procedure if exists insert_data;
 delimiter ;;
 create procedure insert_data()
 begin
 declare i int;
 set i = 1;
 while ( i <= 10000 ) do
 insert into t1(a,b) values(i,i);
  set i = i + 1;
 end while;
 set i = 1;
 while ( i <= 100) do
 insert into t2(a,b) values(i,i);
  set i = i + 1;
 end while;
 end;;
 delimiter ;
 call insert_data();

2、Block Nested-Loop Join算法示例

-- b字段沒有索引
explain select t2.* from t1 inner join t2 on t1.b= t2.b; 
-- 執行結果
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+
|  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |   100 |   100.00 | NULL                                               |
|  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 10337 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+

從執行計劃我們可以得出一些結論：

• 驅動表是t2,被驅動表是t1。所以使用 inner join 時，排在前面的表并不一定就是驅動表。
• Extra 中 的 「Using join buffer (Block Nested Loop)」 說明該關聯查詢使用的是 BNLJ 算法。

上面的sql大致流程是:

1. 將 t2 的所有數據放入到 join_buffer 中
2. 將 join_buffer 中的每一條數據，跟表t1中所有數據進行比較
3. 返回滿足join 條件的數據

3、Index Nested-Loop Join 算法

-- a字段有索引
EXPLAIN select * from t1 inner join t2 on t1.a= t2.a;   
-- 執行結果
+----+-------------+-------+------------+------+---------------+-------+---------+-----------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key   | key_len | ref             | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-------+---------+-----------------+------+----------+-------------+
|  1 | SIMPLE      | t2    | NULL       | ALL  | idx_a         | NULL  | NULL    | NULL            |  100 |   100.00 | Using where |
|  1 | SIMPLE      | t1    | NULL       | ref  | idx_a         | idx_a | 5       | mall_order.t2.a |    1 |   100.00 | NULL        |
+----+-------------+-------+------------+------+---------------+-------+---------+-----------------+------+----------+-------------+

從執行計劃我們可以得出一些結論：

• 我們可以看出 t1的type不在是all而是ref，說明不在是全表掃描，而是走了idx_a的索引。
• 這里并沒有出現 「Using join buffer (Block Nested Loop)」 ，說明走的是Index Nested-Loop Join。

上面的sql大致流程是:

1. 從表 t2 中讀取一行數據
2. 從第 1 步的數據中，取出關聯字段 a，到表 t1 idx_a 索引中查找；
3. 從idx_a 索引上找到滿足條件的數據，如果查詢數據在索引樹都能找到，那就可以直接返回，否則回表查詢剩余字段屬性再返回。
4. 返回滿足join 條件的數據

我們發現這里效率最大的提升在于，t1表中rows=1，也就是說因為idx_a 索引的存在，不需要把t1每條數據都遍歷一遍，而是通過索引1次掃描可以認為最終只掃描 t1 表一行完整數據。

三、join優化總結

根據上面的知識點我們可以總結以下有關join優化經驗:

1. 在關聯查詢的時候，盡量在被驅動表的關聯字段上加索引，讓MySQL做join操作時盡量選擇INLJ算法。

2）小表做驅動表！

當使用left join時，左表是驅動表，右表是被驅動表，當使用right join時，右表是驅動表，左表是被驅動表，當使用join時，mysql會選擇數據量比較小的表作為驅動表，大表作為被驅動表，如果說我們在 join的時候 明確知道哪張表是小表的時候,可以用 「straight_join」 寫法固定連接驅動方式，省去mysql優化器自己判斷的時間。

「對于小表定義的明確」 ：

在決定哪個表做驅動表的時候，應該是兩個表按照各自的條件過濾，過濾完成之后，計算參與 join 的各個字段的總數據量，數據量小的那個表，就是“小表”，應該作為驅動表。

3）在適當的情況下增大 join buffer 的大小，當然這個最好是在會話級別的增大，而不是全局級別。

4）不要用 * 作為查詢列表，只返回需要的列！

這樣做的好處可以讓在相同大小的join buffer可以存更多的數據,也可以在存在索引的情況下盡可能避免回表查詢數據。

審核編輯：劉清