Block Nested-Loop Join：BNLJ，緩存塊嵌套循環(huán)連接;
掃描一個(gè)表的過(guò)程其實(shí)是先把這個(gè)表從磁盤上加載到內(nèi)存中遏弱，然后從內(nèi)存中比較匹配條件是否滿足。但內(nèi)存里可能并不能完全存放的下表中所有的記錄衙四，所以在掃描表前邊記錄的時(shí)候后邊的記錄可能還在磁盤上液样，等掃描到后邊記錄的時(shí)候可能內(nèi)存不足呢堰，所以需要把前邊的記錄從內(nèi)存中釋放掉搓彻。我們前邊又說(shuō)過(guò)凛篙，采用SNLJ 算法的兩表聯(lián)接過(guò)程中峦甩，被驅(qū)動(dòng)表可是要被訪問(wèn)好多次的赘来。被驅(qū)動(dòng)表具體的訪問(wèn)次數(shù)就是由驅(qū)動(dòng)表返回結(jié)果集記錄數(shù)決定！如果這個(gè)被驅(qū)動(dòng)表中的數(shù)據(jù)特別多而且不能使用索引進(jìn)行訪問(wèn)凯傲，那就相當(dāng)于要從磁盤上讀好幾次這個(gè)表犬辰，這個(gè)I/O代價(jià)就非常大了，所以我們得想辦法：
盡量減少訪問(wèn)被驅(qū)動(dòng)表的次數(shù)冰单。 可以讓被驅(qū)動(dòng)表盡量的谢戏臁（小表驅(qū)動(dòng)大表思想！）
當(dāng)被驅(qū)動(dòng)表中的數(shù)據(jù)非常多時(shí)诫欠，每次訪問(wèn)被驅(qū)動(dòng)表涵卵，被驅(qū)動(dòng)表的記錄會(huì)被加載到內(nèi)存中浴栽，在內(nèi)存中的每一條記錄只會(huì)和驅(qū)動(dòng)表結(jié)果集的一條記錄做匹配，之后就會(huì)被從內(nèi)存中清除掉缘厢。然后再?gòu)尿?qū)動(dòng)表結(jié)果集中拿出另一條記錄吃度，再一次把被驅(qū)動(dòng)表的記錄加載到內(nèi)存中一遍，周而復(fù)始贴硫，驅(qū)動(dòng)表結(jié)果集中有多少條記錄椿每，就得把被驅(qū)動(dòng)表從磁盤上加載到內(nèi)存中多少次。
所以我們可不可以在把被驅(qū)動(dòng)表的記錄加載到內(nèi)存的時(shí)候英遭，一次性和多條驅(qū)動(dòng)表中的記錄做匹配间护，
這樣就可以大大減少重復(fù)從磁盤上加載被驅(qū)動(dòng)表的代價(jià)了。這也就是Block Nested-Loop Join算法的思想挖诸。
也就是說(shuō)在有索引的情況下汁尺，MySQL會(huì)嘗試去使用Index Nested-Loop Join算法，在有些情況下多律，可能Join的列就是沒(méi)有索引痴突，那么這時(shí)MySQL的選擇絕對(duì)不會(huì)是最先介紹的Simple Nested-Loop Join算法，SNLJ算法是最慢的join狼荞，畢竟是笛卡爾積辽装！
而Block Nested-Loop Join算法較Simple Nested-Loop Join的改進(jìn)就在于可以減少內(nèi)表的掃描次數(shù)，甚至可以和Hash Join算法一樣相味，僅需掃描內(nèi)表一次拾积。其使用Join Buffer（聯(lián)接緩沖）來(lái)減少內(nèi)部循環(huán)讀取表的次數(shù)。
關(guān)于 join buffer http://www.reibang.com/p/3c0816862cc9
For each tuple r in R do -- 掃描外表R
store used columns as p from R in Join Buffer -- 將部分或者全部R的記錄保存到Join Buffer中丰涉，記為p
For each tuple s in S do -- 掃描內(nèi)表S
If p and s satisfy the join condition -- p與s滿足join條件
Then output the tuple -- 返回為結(jié)果集
可以看到相比Simple Nested-Loop Join算法拓巧，Block Nested-LoopJoin算法僅多了一個(gè)所謂的Join Buffer，為什么這樣就能減少內(nèi)表的掃描次數(shù)呢一死？下圖相比更好地解釋了Block Nested-Loop Join算法的運(yùn)行過(guò)程：
可以看到Join Buffer用以緩存聯(lián)接需要的列（所以再次提醒我們肛度，最好不要把*作為查詢列表，只需要把我們關(guān)心的列放到查詢列表就好了投慈，這樣還可以在join buffer中放置更多的記錄呢）贤斜，然后以Join Buffer批量的形式和內(nèi)表中的數(shù)據(jù)進(jìn)行聯(lián)接比較。就上圖來(lái)看逛裤，記錄r1瘩绒，r2 … rT的聯(lián)接僅需掃內(nèi)表一次，如果join buffer可以緩存所有的外表列带族，那么聯(lián)接僅需掃描內(nèi)外表各一次锁荔，從而大幅提升Join的性能。
Block Nested-Loop Join開銷
Block Nested-Loop Join極大的避免了內(nèi)表的掃描次數(shù)蝙砌，如果Join Buffer可以緩存外表的數(shù)據(jù)阳堕，那么內(nèi)表的掃描僅需一次跋理，這和Hash Join非常類似。但是Block Nested-Loop Join依然沒(méi)有解決的是Join比較的次數(shù)恬总，其仍然通過(guò)Join判斷式進(jìn)行比較前普。綜上所述，到目前為止各Join算法的成本比較如下所示：
Block Nested-Loop Join影響
在使用 Block Nested-Loop Join(BNL) 算法時(shí)壹堰，還是可能會(huì)對(duì)被驅(qū)動(dòng)表做多次掃描（盡管可能已經(jīng)將驅(qū)動(dòng)表中大部分關(guān)聯(lián)字段數(shù)據(jù)存入join buffer）拭卿。如果這個(gè)被驅(qū)動(dòng)表是一個(gè)大的冷數(shù)據(jù)表，除了會(huì)導(dǎo)致 IO 壓力大以外贱纠，還會(huì)對(duì) buffer pool產(chǎn)生嚴(yán)重的影響峻厚！
如果了解 InnoDB 的 LRU 算法就會(huì)知道，由于 InnoDB 對(duì) Bufffer Pool 的 LRU 算法做了優(yōu)化谆焊，即：第一次從磁盤讀入內(nèi)存的數(shù)據(jù)頁(yè)惠桃，會(huì)先放在 old 區(qū)域。如果 1 秒之后這個(gè)數(shù)據(jù)頁(yè)不再被訪問(wèn)了辖试，就不會(huì)被移動(dòng)到 LRU 鏈表頭部辜王，這樣對(duì) Buffer Pool 的命中率影響就不大。
但是罐孝，如果一個(gè)使用 BNL 算法的 join 語(yǔ)句誓禁，多次掃描一個(gè)冷表，而且這個(gè)語(yǔ)句執(zhí)行時(shí)間超過(guò) 1 秒肾档，就會(huì)在再次掃描冷表的時(shí)候，把冷表的數(shù)據(jù)頁(yè)移到 LRU 鏈表頭部辫继。這種情況對(duì)應(yīng)的怒见，是冷表的數(shù)據(jù)量小于整個(gè) Buffer Pool 的 3/8，能夠完全放入 old 區(qū)域的情況姑宽。如果這個(gè)冷表很大遣耍，就會(huì)出現(xiàn)另外一種情況：業(yè)務(wù)正常訪問(wèn)的數(shù)據(jù)頁(yè)，沒(méi)有機(jī)會(huì)進(jìn)入 young 區(qū)域炮车。(導(dǎo)致正常業(yè)務(wù)sql查詢因?yàn)闆](méi)有剩余buffer pool空間進(jìn)一步讓磁盤IO變多而變得緩慢)
由于優(yōu)化機(jī)制的存在舵变，一個(gè)正常訪問(wèn)的數(shù)據(jù)頁(yè)，要進(jìn)入 young 區(qū)域瘦穆，需要隔 1 秒后再次被訪問(wèn)到纪隙。但是，由于我們的 join 語(yǔ)句在循環(huán)讀磁盤和淘汰內(nèi)存頁(yè)扛或，進(jìn)入 old 區(qū)域的數(shù)據(jù)頁(yè)绵咱，很可能在 1 秒之內(nèi)就被淘汰了。這樣熙兔，就會(huì)導(dǎo)致這個(gè) MySQL 實(shí)例的 Buffer Pool 在這段時(shí)間內(nèi)悲伶，young 區(qū)域的數(shù)據(jù)頁(yè)沒(méi)有被合理地淘汰艾恼。
也就是說(shuō)，這兩種情況都會(huì)影響 Buffer Pool 的正常運(yùn)作麸锉。 大表 join 操作雖然對(duì) IO 有影響钠绍，但是在語(yǔ)句執(zhí)行結(jié)束后，對(duì) IO 的影響也就結(jié)束了花沉。但是柳爽，對(duì) Buffer Pool 的影響就是持續(xù)性的，需要依靠后續(xù)的查詢請(qǐng)求慢慢恢復(fù)內(nèi)存命中率主穗。
為了減少這種影響泻拦，你可以考慮增大 join_buffer_size 的值，減少對(duì)被驅(qū)動(dòng)表的掃描次數(shù)!
也就是說(shuō)忽媒，BNL 算法對(duì)系統(tǒng)的影響主要包括三個(gè)方面： 可能會(huì)多次掃描被驅(qū)動(dòng)表争拐，占用磁盤 IO 資源； 判斷 join 條件需要執(zhí)行 M*N 次對(duì)比（M晦雨、N 分別是兩張表的行數(shù)）架曹，如果是大表就會(huì)占用非常多的 CPU 資源； 可能會(huì)導(dǎo)致 Buffer Pool 的熱數(shù)據(jù)被淘汰闹瞧，影響內(nèi)存命中率绑雄。
那么假設(shè)被驅(qū)動(dòng)表全在內(nèi)存中，這個(gè)時(shí)候 SNLJ 和 BNL 算法還有性能差別嗎奥邮？當(dāng)然是有的万牺，由于 SNLJ 這個(gè)算法天然會(huì)對(duì)被驅(qū)動(dòng)表的數(shù)據(jù)做多次訪問(wèn)，所以更容易將這些數(shù)據(jù)頁(yè)放到 Buffer Pool 的頭部洽腺，從而污染 Buffer Pool脚粟。另外，即使被驅(qū)動(dòng)表數(shù)據(jù)都在內(nèi)存中蘸朋，但每次查找“下一個(gè)記錄的操作”核无，都是類似指針操作。而 BNL 算法中的 join_buffer 是數(shù)組藕坯，遍歷的成本更低团南，從被驅(qū)動(dòng)表讀取一條數(shù)據(jù)去 join_buffer 中遍歷。
BNL的相關(guān)設(shè)置
mysql默認(rèn)開啟BNL
SHOW VARIABLES LIKE '%optimizer_switch%'
index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,
block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on
開關(guān)BNL
SET optimizer_switch = 'block_nested_loop=on';
SET optimizer_switch = 'block_nested_loop=off';
總結(jié)下
1炼彪、 緩存塊嵌套循環(huán)連接通過(guò)一次性緩存多條數(shù)據(jù)吐根，把參與查詢的列緩存到Join Buffer 里，然后拿join buffer里的數(shù)據(jù)批量與內(nèi)層表的數(shù)據(jù)進(jìn)行匹配辐马，從而減少了內(nèi)層循環(huán)的次數(shù)佑惠、減少了內(nèi)部表訪問(wèn)次數(shù)（遍歷一次內(nèi)層表就可以批量匹配一次Join Buffer里面的外層表數(shù)據(jù)）。
2、什么時(shí)候會(huì)使用BNL? 當(dāng)內(nèi)表關(guān)聯(lián)字段上沒(méi)有索引時(shí)膜楷，不使用Index Nested-Loop Join的時(shí)候旭咽，默認(rèn)使用Block Nested-Loop Join。
3赌厅、join buffer的相關(guān)概念：
待續(xù)穷绵。。特愿。仲墨。。
4揍障、使用Block Nested-Loop Join算法需要開啟優(yōu)化器管理配置的optimizer_switch的設(shè)置block_nested_loop為on目养，默認(rèn)為開啟。
