摘要：?用事例和圖片簡單的說明了mysql 中兩表join的算法，主要包括Nested-Loop Join Algorithm，Block Nested-Loop Join Algorithm，Batched Key Access Joins算法，以及join buffer在這個過程中起的作用
實為吾之愚見,望諸君酌之!聞過則喜,與君共勉
測試數據
CREATE TABLE `dept_emp` (
? `emp_no` int(11) NOT NULL,
? `dept_no` char(4) NOT NULL,
? `from_date` date NOT NULL,
? `to_date` date NOT NULL,
? PRIMARY KEY (`emp_no`,`dept_no`),
? KEY `from_date` (`from_date`),
? CONSTRAINT `dept_emp_ibfk_1` FOREIGN KEY (`emp_no`) REFERENCES `employees` (`emp_no`) ON DELETE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=latin1
CREATE TABLE `departments` (
? `dept_no` char(4) NOT NULL,
? `dept_name` varchar(40) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=latin1
mysql> select count(1) from departments;
+----------+
| count(1) |
+----------+
|??????? 9 |
+----------+
1 row in set (0.00 sec)
mysql> select count(1) from dept_emp;
+----------+
| count(1) |
+----------+
|?? 331603 |
+----------+
1 row in set (0.08 sec)
其中dept_emp有331603行記錄，departments有9行數據
事例查詢
select e.to_date,d.dept_name from dept_emp e,departments d where e.dept_no=d.dept_no;
這是一個兩表join的query，對應條件是where e.dept_no=d.dept_no，主要找出表dept_emp和departments中，滿足dept_no相等的記錄，然后展示出e.to_date,d.dept_name列其中dept_emp有331603行記錄，departments有9行數據
執(zhí)行計劃對比
關閉block_nested_loop
打開block_nested_loop
打開batched_key_access
Nested-Loop事例
Nested-Loop Join
關閉設置optimizer_switch的block_nested_loop為off，然后查看查詢的執(zhí)行計劃
從上圖可知，執(zhí)行計劃對departments是全表掃描（9行數據），對dept_emp也是全表掃描（331570行數據），當使用Nested-Loop Join算法的時候，先逐行的讀取departments表（此處是全表掃描，僅限于該sql），針對departments的每一行數據，都對表dept_emp的每一行記錄進行匹配（此處是全表掃描，僅限于該sql）滿足條件的行（where e.dept_no=d.dept_no），wiki的偽代碼如下：
For each tuple r in R do
???? For each tuple s in S do
??????? If r and s satisfy the join condition
?????????? Then output the tuple
過程概括如下圖：
上圖所示，departments的row1要和dept_emp每一行做條件匹配，查找符合條件的行，反復循環(huán)，直至departments的記錄掃描完成（最后一條記錄rown與dept_emp的每一行都進行了條件匹配）
Block_nested_loop
先打開設置optimizer_switch的block_nested_loop為on，然后查看查詢的執(zhí)行計劃
從上圖可知，執(zhí)行計劃對departments是全表掃描（9行數據），對dept_emp也是全表掃描（331570行數據），但是extra列多了一部分” Using join buffer (Block Nested Loop)”，當使用Block Nested-Loop Join算法的時候，先逐行的讀取departments表（此處是全表掃描，僅限于該sql），然后把讀取的數據，存儲到join buffer里（如果join buffer足夠大，就可以一次全部存儲departments所需要的join對象了，如果join buffer太小，一次只可以緩存departments的一部分join對象的話，就需要分多次進行緩存departments的join對象），針對join buffer中緩存的數據（注意之前的一次緩存以及多次緩存），批量（不需要與Nested-Loop Join一樣，一條條的比較了，可以多條比較了）的對表dept_emp的每一行記錄進行匹配（此處是全表掃描，僅限于該sql）滿足條件的行（where e.dept_no=d.dept_no），偽代碼可以寫成：
For each tuple r in R do
store used columns from R in join buffer
???? For each tuple s in S do
??????? If r and s satisfy the join condition
?????????? Then output the tuple
過程概括如下圖：
當為dept_emp表的列dept_no添加一個索引的時候（二級索引，已經有主鍵索引），再觀察執(zhí)行計劃：
Join type從all變成了ref,可以理解為對dept_emp執(zhí)行join的時候，使用索引進行匹配（對應之前的全表掃描），這里預估的行數是20723rows，比之前的331570rows少了很多（全表掃描），執(zhí)行計劃從全部掃描和ref（join type）中，選擇了 ref，對比之前的block_nested_loop，過程變化如下：
由于dept_emp下的dept_no是二級索引，查詢中又查詢了e.to_date(單單從二級索引里獲取不到數據)，于是需要通過索引，查詢表里面對應的e.to_date的值，這是如上圖可知，訪問時隨機的（圖例的表現方式是row1對應pk2，row2對應pk1等等），可能會產生隨機io，如果不查詢e.to_date，則不需要再去表里查詢了，同時Extra會顯示Using index，如下：
Batched_key_access
在Block_nested_loop最后部分，使用二級索引查詢的時候，出現了一個現象：當獲取的數據二級索引無法滿足時，需要去查詢原始的數據表來確定數據，查詢數據是通過主鍵去查的，會出現不是按照主鍵順序查的情況，如果有辦法把這些無序的主鍵查詢轉換成有序的去查詢表的數據（聚簇索引），會節(jié)省很多的時間，mysql提供了Batched_key_access算法來實現這個需求，復現如下：
對比之前的Block_nested_loop（有索引和沒有索引兩部分），上面加索引后，開啟了mrr，batched_key_access，同時關閉了mrr_cost_based，這個時候Extra列出現了Using join buffer (Batched Key Access)，使用Batched_key_access的過程如下：
上圖看，join buffer會緩存departments相關的join列，Batched_key_access算法會使用dept_no二級索引去查找，由于是無序的，查找前把這些key（可以大概理解為主鍵信息+join buffer里行的標識信息）的信息反饋給mrr 去，mrr會按照主鍵（沒有主鍵使用row id）排序，然后順序的去dept_emp里去查找信息，并發(fā)信息再次反饋給Batched_key_access算法去和join buffer里的row進行比較
本文為云棲社區(qū)原創(chuàng)內容，未經允許不得轉載，如需轉載請發(fā)送郵件至yqeditor@list.alibaba-inc.com；如果您發(fā)現本社區(qū)中有涉嫌抄襲的內容，歡迎發(fā)送郵件至：yqgroup@service.aliyun.com 進行舉報，并提供相關證據，一經查實，本社區(qū)將立刻刪除涉嫌侵權內容。
