本篇文章帶大家了解mysql中的join語句算法，并介紹一下join語句優(yōu)化的方法。
一、join語句算法
創(chuàng)建兩個表t1和t2
CREATE?TABLE?`t2`?( ??`id`?int(11)?NOT?NULL, ??`a`?int(11)?DEFAULT?NULL, ??`b`?int(11)?DEFAULT?NULL, ??PRIMARY?KEY?(`id`), ??KEY?`a`?(`a`) )?ENGINE=InnoDB; CREATE?DEFINER=`root`@`%`?PROCEDURE?`idata`() BEGIN declare?i?int; ??set?i=1; ??while(i<p>這兩個表都有一個主鍵索引id和一個索引a，字段b上無索引。存儲過程idata()往表t2里插入了1000行數(shù)據(jù)，在表t1里插入的是100行數(shù)據(jù)</p><h3><strong>1、Index Nested-Loop Join</strong></h3><pre class="brush:sql;toolbar:false;">select?*?from?t1?straight_join?t2?on?(t1.a=t2.a);
如果直接使用join語句，mysql優(yōu)化器可能會選擇表t1或t2作為驅(qū)動表，通過straight_join讓MySQL使用固定的連接方式執(zhí)行查詢，在這個語句里，t1是驅(qū)動表，t2是被驅(qū)動表
被驅(qū)動表t2的字段a上有索引，join過程用上了這個索引，因此這個語句的執(zhí)行流程是這樣的：
1.從表t1中讀入一行數(shù)據(jù)R
2.從數(shù)據(jù)行R中，取出a字段到表t2里去查找
3.取出表t2中滿足條件的行，跟R組成一行，作為結(jié)果集的一部分
4.重復(fù)執(zhí)行步驟1到3，直到表t1的末尾循環(huán)結(jié)束
這個過程可以用上被驅(qū)動表的索引，稱之為Index Nested-Loop Join，簡稱NLJ
在這個流程里：
1.對驅(qū)動表t1做了全表掃描，這個過程需要掃描100行
2.而對于每一行R，根據(jù)a字段去表t2查找，走的是樹搜索過程。由于我們構(gòu)造的數(shù)據(jù)都是一一對應(yīng)的，因此每次的搜索過程都只掃描一行，也是總共掃描100行
3.所以，整個執(zhí)行流程，總掃描行數(shù)是200
假設(shè)不使用join，只能用單表查詢：
1.執(zhí)行select * from t1，查出表t1的所有數(shù)據(jù)，這里有100行
2.循環(huán)遍歷這100行數(shù)據(jù)：
- 從每一行R取出字段a的值$R.a
- 執(zhí)行select * from t2 where a=$R.a
- 把返回的結(jié)果和R構(gòu)成結(jié)果集的一行
這個查詢過程，也是掃描了200行，但是總共執(zhí)行了101條語句，比直接join多了100次交互。客戶端還要自己拼接SQL語句和結(jié)果。這么做還不如直接join好
在可以使用被驅(qū)動表的索引的情況下：
- 使用join語句，性能比強行拆成多個單表執(zhí)行SQL語句的性能要好
- 如果使用join語句的話，需要讓小表做驅(qū)動表
2、Simple Nested-Loop Join
select?*?from?t1?straight_join?t2?on?(t1.a=t2.b);
由于表t2的字段b上沒有索引，因此每次到t2去匹配的時候，就要做一次全表掃描。這個算法叫做Simple Nested-Loop Join
這樣算來，這個SQL請求就要掃描表t2多達100次，總共掃描100*100=10萬行
MySQL沒有使用這個Simple Nested-Loop Join算法，而是使用了另一個叫作Block Nested-Loop Join的算法，簡稱BNL
3、Block Nested-Loop Join
被驅(qū)動表上沒有可用的索引，算法的流程如下：
1.把表t1的數(shù)據(jù)讀入線程內(nèi)存join_buffer中，由于這個語句中寫的是select *，因此是把整個表t1放入了內(nèi)存
2.掃描表t2，把表t2中的每一行取出來，跟join_buffer中的數(shù)據(jù)作比對，滿足join條件的，作為結(jié)果集的一部分返回
在這個過程中，對表t1和表t2都做了一次全表掃描，因此總的掃描行數(shù)是1100。由于join_buffer是以無序數(shù)組的方式組織的，因此對表t2中的每一行，都要做100次判斷，總共需要在內(nèi)存中做的判斷次數(shù)是100*1000=10萬次
使用Simple Nested-Loop Join算法進行查詢，掃描行數(shù)也是10萬行。因此，從時間復(fù)雜度上來說，這兩個算法是一樣的。但是，Block Nested-Loop Join算法的這10萬次判斷是內(nèi)存操作，速度上會快很多，性能也更好
這時候選擇大表還是小表做驅(qū)動表，執(zhí)行耗時是一樣的
join_buffer的大小是由參數(shù)join_buffer_size設(shè)定的，默認值是256k。如果放不下表t1的所有數(shù)據(jù)話，策略很簡單，就是分段放
1）掃描表t1，順序讀取數(shù)據(jù)行放入join_buffer中，假設(shè)放到第88行join_buffer滿了
2）掃描表t2，把t2中的每一行取出來，跟join_buffer中的數(shù)據(jù)做對比，滿足join條件的，作為結(jié)果集的一部分返回
3）清空join_buffer
4）繼續(xù)掃描表t1，順序讀取最后的12行放入join_buffer中，繼續(xù)執(zhí)行第2步
由于表t1被分成了兩次放入join_buffer中，導(dǎo)致表t2會被掃描兩次。雖然分成兩次放入join_buffer，但是判斷等值條件的此時還是不變的
4、能不能使用join語句？
1.如果可以使用Index Nested-Loop Join算法，也就是說可以用上被驅(qū)動表上的索引，其實是沒問題的
2.如果使用Block Nested-Loop Join算法，掃描行數(shù)就會過多。尤其是在大表上的join操作，這樣可能要掃描被驅(qū)動表很多次，會占用大量的系統(tǒng)資源。所以這種join盡量不要用
5、如果使用join，應(yīng)該選擇大表做驅(qū)動表還是選擇小表做驅(qū)動表
1.如果是Index Nested-Loop Join算法，應(yīng)該選擇小表做驅(qū)動表
2.如果是Block Nested-Loop Join算法：
- 在join_buffer_size足夠大的時候，是一樣的
- 在join_buffer_size不夠大的時候，應(yīng)該選擇小表做驅(qū)動表
在決定哪個表做驅(qū)動表的時候，應(yīng)該是兩個表按照各自的條件過濾，過濾完成以后，計算參數(shù)join的各個字段的總數(shù)據(jù)量，數(shù)據(jù)量小的那個表，就是小表，應(yīng)該作為驅(qū)動表
二、join語句優(yōu)化
創(chuàng)建兩個表t1、t2
create?table?t1(id?int?primary?key,?a?int,?b?int,?index(a));create?table?t2?like?t1;CREATE?DEFINER?=?CURRENT_USER?PROCEDURE?`idata`()BEGIN declare?i?int; ??set?i=1; ??while(i<p>在表t1中，插入了1000行數(shù)據(jù)，每一行的a=1001-id的值。也就是說，表t1中字段a是逆序的。同時，在表t2中插入了100萬行數(shù)據(jù)</p><h3><strong>1、Multi-Range Read優(yōu)化</strong></h3><p>Multi-Range Read（MRR）優(yōu)化主要的目的是盡量使用順序讀盤</p><pre class="brush:js;toolbar:false;">select?*?from?t1?where?a>=1?and?a<p>主鍵索引是一棵B+樹，在這棵樹上，每次只能根據(jù)一個主鍵id查到一行數(shù)據(jù)。因此，回表是一行行搜索主鍵索引的<br><img src="https://img.php.cn/upload/article/000/000/024/036a1e7fbaec3a5a0d9513924b35e8ce-5.png" alt="在這里插入圖片描述"><br> 如果隨著a的值遞增順序查找的話，id的值就變成隨機的，那么就會出現(xiàn)隨機訪問，性能相對較差</p><p><strong>因為大多數(shù)的數(shù)據(jù)都是按照主鍵遞增順序插入得到的，所以如果按照主鍵的遞增順序查詢，對磁盤的讀比較接近順序讀，能夠提升讀性能</strong></p><p>這就是MRR優(yōu)化的設(shè)計思路，語句的執(zhí)行流程如下：</p><p>1.根據(jù)索引a，定位到滿足條件的記錄，將id值放入read_rnd_buffer中</p><p>2.將read_rnd_buffer中的id進行遞增排序</p><p>3.排序后的id數(shù)組，依次到主鍵id索引中查記錄，并作為結(jié)果返回</p><p>read_rnd_buffer的大小是由read_rnd_buffer_size參數(shù)控制的。如果步驟1中，read_rnd_buffer放滿了，就會先執(zhí)行完步驟2和3，然后清空read_rnd_buffer。之后繼續(xù)找索引a的下個記錄，并繼續(xù)循環(huán)</p><p>如果想要穩(wěn)定地使用MRR優(yōu)化的話，需要設(shè)置set optimizer_switch="mrr_cost_based=off"</p><p><img src="https://img.php.cn/upload/article/000/000/024/036a1e7fbaec3a5a0d9513924b35e8ce-6.png" alt="在這里插入圖片描述"></p><p><img src="https://img.php.cn/upload/article/000/000/024/6cb8ae5574ee9994ac5c650427546acf-7.png" alt="在這里插入圖片描述"><br>explain結(jié)果中，Extra字段多了using MRR，表示的是用上了MRR優(yōu)化。由于在read_rnd_buffer中按照id做了排序，所以最后得到的結(jié)果也是按照主鍵id遞增順序的<br></p><p><strong>MRR能夠提升性能的核心在于，這條查詢語句在索引a上做的是一個范圍查詢，可以得到足夠多的主鍵id。這樣通過排序以后，再去主鍵索引查數(shù)據(jù)，才能體現(xiàn)出順序性的優(yōu)勢</strong></p><h3><strong>2、Batched Key Access</strong></h3><p>MySQL5.6引入了Batched Key Access（BKA）算法。這個BKA算法是對NLJ算法的優(yōu)化</p><p>NLJ算法流程圖：</p><p><img src="https://img.php.cn/upload/article/000/000/024/6cb8ae5574ee9994ac5c650427546acf-8.png" alt="在這里插入圖片描述"></p><p>NLJ算法執(zhí)行的邏輯是從驅(qū)動表t1，一行行地取出a的值，再到被驅(qū)動表t2去做join<br></p><p>BKA算法流程圖：</p><p><img src="https://img.php.cn/upload/article/000/000/024/5d50e33d9b279af171fdc7f121240e30-9.png" alt="在這里插入圖片描述"></p><p>BKA算法執(zhí)行的邏輯是把表t1的數(shù)據(jù)取出來一部分，先放到一個join_buffer，一起傳給表t2。在join_buffer中只會放入查詢需要的字段，如果join_buffer放不下所有數(shù)據(jù)，就會將數(shù)據(jù)分成多段執(zhí)行上圖的流程<br></p><p>如果想要使用BKA優(yōu)化算法的話，執(zhí)行SQL語句之前，先設(shè)置</p><pre class="brush:js;toolbar:false;">set?optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
其中前兩個參數(shù)的作用是啟用MRR，原因是BKA算法的優(yōu)化要依賴與MRR
3、BNL算法的性能問題
InnoDB對Buffer Pool的LRU算法做了優(yōu)化，即：第一次從磁盤讀入內(nèi)存的數(shù)據(jù)頁，會先放在old區(qū)域。如果1秒之后這個數(shù)據(jù)頁不再被訪問了，就不會被移動到LRU鏈表頭部，這樣對Buffer Pool的命中率影響就不大
如果一個使用BNL算法的join語句，多次掃描一個冷表，而且這個語句執(zhí)行時間超過1秒，就會在再次掃描冷表的時候，把冷表的數(shù)據(jù)頁移到LRU鏈表頭部。這種情況對應(yīng)的，是冷表的數(shù)據(jù)量小于整個Buffer Pool的3/8，能夠完全放入old區(qū)域的情況
如果這個冷表很大，就會出現(xiàn)另外一種情況：業(yè)務(wù)正常訪問的數(shù)據(jù)頁，沒有機會進入young區(qū)域。
由于優(yōu)化機制的存在，一個正常訪問的數(shù)據(jù)頁，要進入young區(qū)域，需要隔1秒后再次被訪問到。但是，由于join語句在循環(huán)讀磁盤和淘汰內(nèi)存頁，進入old區(qū)域的數(shù)據(jù)頁，很可能在1秒之內(nèi)就被淘汰了。這樣就會導(dǎo)致MySQL實例的Buffer Pool在這段時間內(nèi)，young區(qū)域的數(shù)據(jù)頁沒有被合理地淘汰
4、BNL轉(zhuǎn)BKA
一些情況下，我們可以直接在被驅(qū)動表上建索引，這時就可以直接轉(zhuǎn)成BKA算法了
如果碰到一些不適合在被驅(qū)動表上建索引的情況，可以考慮使用臨時表。大致思路如下：
select?*?from?t1?join?t2?on?(t1.b=t2.b)?where?t2.b>=1?and?t2.b<p>1）把表t2中滿足條件的數(shù)據(jù)放在臨時表tmp_t中</p><p>2）為了讓join使用BKA算法，給臨時表tmp_t的字段b加上索引</p><p>3）讓表t1和tmp_t做join操作</p><p>SQL語句寫法如下：</p><pre class="brush:js;toolbar:false;">create?temporary?table?temp_t(id?int?primary?key,?a?int,?b?int,?index(b))engine=innodb; insert?into?temp_t?select?*?from?t2?where?b>=1?and?b<h3><strong>5、擴展hash join</strong></h3><p>MySQL的優(yōu)化器和執(zhí)行器不支持哈希join，可以自己實現(xiàn)在業(yè)務(wù)端，實現(xiàn)流程大致如下：</p><p>1.select * from t1;取得表t1的全部1000行數(shù)據(jù)，在業(yè)務(wù)端存入一個hash結(jié)構(gòu)</p><p>2.select * from t2 where b>=1 and b</p><p>3.把這2000行數(shù)據(jù)，一行一行地取到業(yè)務(wù)端，到hash結(jié)構(gòu)的數(shù)據(jù)表中尋找匹配的數(shù)據(jù)。滿足匹配的條件的這行數(shù)據(jù)，就作為結(jié)果集的一行</p><p>相關(guān)學(xué)習(xí)推薦：<a href="https://www.php.cn/course/list/51.html" target="_blank">mysql教程</a>(視頻)</p>
