概述
相信許多開發/DBA在使用MySQL的過程中，對于MySQL處理多表關聯的方式或者說性能一直不太滿意。對于開發提交的含有join的查詢，一般比較抗拒，從而建議將join拆分，避免join可能帶來的性能問題，同時也增加了程序和DB的網絡交互。
5.5 版本之前，MySQL本身只支持一種表間關聯方式，就是嵌套循環(Nested Loop)。如果關聯表的數據量很大，則join關聯的執行時間會非常長。在5.5以后的版本中，MySQL通過引入BNL算法來優化嵌套執行,今天主要介紹兩種join算法 Nested-Loop Join (NLJ) 和Block Nested-Loop Join(BNL) .
一、Nested Loop Join （NLJ）算法:
NLJ，顧名思義，是指嵌套循環算法，my.oschina.net 上面有一段代碼對NLJ做出了說明：
即，將驅動表/外部表的結果集作為循環基礎數據，然后循環從該結果集每次一條獲取數據作為下一個表的過濾條件查詢數據，然后合并結果。如果有多表join，則將前面的表的結果集作為循環數據，取到每行再到聯接的下一個表中循環匹配，獲取結果集返回給客戶端。
（此處僅對兩層循環分析，多層循環可以將最內層循環看作一層，將其余的看作一層進行分析）
這里可以將內層表看作被驅動表，外層表看作驅動表。每次join時，從驅動表中先拿出一條數據和被驅動表進行條件匹配，若匹配成功，則將數據連接后放入結果集。接著，外層的驅動表掃描獲取第二條記錄，并和被驅動表進行條件匹配，將成功的記錄連接后放入結果集，剩余數據以此類推。最后，將結果集發給請求的客戶端。
并且，這個模型和C語言的雙層循環（或者多層循環）很相似。
for(;;) //外層循環
{
for(;;) //內層循環
{
...
}
}
二、Block Nested Loop Join （BNLJ）算法:
BNLJ，塊嵌套循環。BNLJ是優化版的NLJ，BNLJ區別于NLJ的地方是它加入了緩沖區join buffer，它的作用是外層驅動表可以先將一部分數據事先存到join buffer中，然后再和內層的被驅動表進行條件匹配，匹配成功的記錄將會連接后存入結果集，等待全部循環結束后，將結果集發給client即完成一次join。
以下是my.oschina.net 上一段對BNLJ的說明：
如果t1, t2參與join的列長度只和為s, c為二者組合數, 那么t3表被掃描的次數為
(S * C)/join_buffer_size + 1
掃描t3的次數隨著join_buffer_size的增大而減少, 直到join buffer能夠容納所有的t1, t2組合, 再增大join buffer size, query 的速度就不會再變快了。
BNLJ相對于NLJ的優點在于，驅動層可以先將部分數據加載進buffer，這種方法的直接影響就是將大大減少內層循環的次數，提高join的效率。
舉個栗子：
如果內層循環有100條記錄，外層循環也有100條記錄，這樣的話，每次外層循環先將10條記錄放到buffer中，內層循環的100條記錄每條與這個buffer中的10條記錄進行匹配，只需要匹配內層循環總記錄數次即可結束一次循環（在這里，即只需要匹配100次即可結束），然后將匹配成功的記錄連接后放入結果集中，接著，外層循環繼續向buffer中放入10條記錄，同理進行匹配，并將成功的記錄連接后放入結果集。后續循環以此類推，直到循環結束，將結果集發給client為止。
可以發現，若用NLJ，則需要100 * 100次才可結束，BNLJ則需要100 / block_size * 100 = 10 * 100次就可結束，減少了9/10。
若是外層驅動表足夠小，或者說恰恰是block_size大小的，那么每次的join將會只進行1 * 內層循環總記錄數 = 內層循環總記錄數 ，即每次只需要循環內層循環總記錄數次就可結束并完成循環，即就是小表驅動大表。
MySQL使用Join Buffer有以下要點:
1. join_buffer_size變量決定buffer大小。
2. 只有在join類型為all, index, range的時候才可以使用join buffer。
3. 能夠被buffer的每一個join都會分配一個buffer, 也就是說一個query最終可能會使用多個join buffer。
4. 第一個nonconst table不會分配join buffer, 即便其掃描類型是all或者index。
5. 在join之前就會分配join buffer, 在query執行完畢即釋放。
6. join buffer中只會保存參與join的列, 并非整個數據行。
總結
5.6版本及以后，優化器管理參數optimizer_switch中中的block_nested_loop參數控制著BNL是否被用于優化器。默認條件下是開啟，若果設置為off，優化器在選擇 join方式的時候會選擇NLJ算法。需要注意的是：并不是所有的場景下Block Nested_Loop Join 都是最優選擇！
