概述&背景
MySQL因?yàn)闆]有實(shí)現(xiàn)hashjoin而受到批評(píng)惶岭。最新的8.0.18版本帶來了這一功能涎拉，令人欣慰泳秀。有時(shí)候我想知道為什么MySQL不支持hashjoin丐枉？我認(rèn)為這可能是因?yàn)镸ySQL主要用于簡單的OLTP場景，而且它廣泛應(yīng)用于Internet應(yīng)用程序中髓霞，所以需求并不那么迫切冕杠。另一方面，這可能是因?yàn)橐郧巴耆蕾嚿鐓^(qū)酸茴。畢竟MySQL的進(jìn)化速度是有限的分预。甲骨文收購mysql后，mysql發(fā)布的演進(jìn)速度明顯加快薪捍。

源點(diǎn)：提供流的節(jié)點(diǎn)（入度為0）笼痹，類比成為一個(gè)無限放水的水廠
匯點(diǎn)：接受流的節(jié)點(diǎn)（出度為0），類比成為一個(gè)無限收水的小區(qū)
焕掖：類比為水管
弧的容量：類比為水管的容量凳干；用函數(shù)c(x,y)c(x,y)表示弧(x,y)(x,y)的容量
弧的流量：類比為當(dāng)前在水管中水的量；用函數(shù)f(x,y)f(x,y)表示弧(x,y)(x,y)的流量
弧的殘量：即容量-流量
容量網(wǎng)絡(luò)：對(duì)于一個(gè)網(wǎng)絡(luò)流模型被济，每一條弧都給出了容量救赐，則構(gòu)成一個(gè)容量網(wǎng)絡(luò)。
流量網(wǎng)絡(luò)：對(duì)于一個(gè)網(wǎng)絡(luò)流模型只磷，每一條弧都給出了流量经磅，則構(gòu)成一個(gè)流量網(wǎng)絡(luò)。
殘量網(wǎng)絡(luò)：對(duì)于一個(gè)網(wǎng)絡(luò)流模型钮追，每一條弧都給出了殘量预厌，則構(gòu)成一個(gè)殘量網(wǎng)絡(luò)。最初的殘量網(wǎng)絡(luò)就是容量網(wǎng)絡(luò)元媚。
hashjoin本身的算法實(shí)現(xiàn)并不復(fù)雜轧叽。要說它很復(fù)雜苗沧，可能是優(yōu)化器選擇執(zhí)行計(jì)劃時(shí)，是否選擇hashjoin炭晒，選擇外觀待逞，內(nèi)部表可能更復(fù)雜。無論如何网严，現(xiàn)在使用hashjoin飒焦，優(yōu)化器在選擇join算法時(shí)還有另一個(gè)選擇。MySQL基于實(shí)用主義屿笼。我相信這個(gè)增強(qiáng)也回答了一些問題。有些職能并非無能翁巍，而是有優(yōu)先權(quán)驴一。

在8.0.18之前，MySQL只支持nestlopjoin算法灶壶。最簡單的是簡單的nestloop連接肝断。MySQL對(duì)該算法進(jìn)行了一些優(yōu)化，包括塊嵌套循環(huán)連接驰凛、索引嵌套循環(huán)連接和批密鑰訪問胸懈。通過這些優(yōu)化，可以在一定程度上緩解hashjoin的緊迫性恰响。接下來趣钱，我們將用一個(gè)單獨(dú)的章節(jié)來討論MySQL的這些連接優(yōu)化。接下來胚宦，我們將討論hashjoin首有。

Hash Join算法
Nestloopjoin algorithm is simply a double loop, which traverses the surface (drive table), for each row of records on the surface, then traverses the inner table, and then determines whether the join conditions are met, and then determines whether to spit out the records to the last execution node. In terms of algorithm, this is a complexity of M * n. Hash join is an optimization for equal join scenarios. The basic idea is to load the external data into memory and establish a hash table. In this way, you can complete the join operation and output the matching records only by traversing the internal table once. If all the data can be loaded into memory, of course, the logic is simple. Generally speaking, this kind of join is called CHJ (classic hash join). MariaDB has implemented this kind of hash join algorithm before. If all the data cannot be loaded into memory, it needs to be loaded into memory in batches, and then joined in batches. The following describes the implementation of these join algorithms.

In-Memory Join(CHJ)

HashJoin一般包括兩個(gè)過程，創(chuàng)建hash表的build過程和探測(cè)hash表的probe過程枢劝。

1).build phase

遍歷外表井联，以join條件為key，查詢需要的列作為value創(chuàng)建hash表您旁。這里涉及到一個(gè)選擇外表的依據(jù)烙常，主要是評(píng)估參與join的兩個(gè)表(結(jié)果集)的大小來判斷，誰小就選擇誰鹤盒，這樣有限的內(nèi)存更容易放下hash表蚕脏。

2).probe phase

hash表build完成后，然后逐行遍歷內(nèi)表侦锯，對(duì)于內(nèi)表的每個(gè)記錄蝗锥，對(duì)join條件計(jì)算hash值，并在hash表中查找率触，如果匹配终议，則輸出，否則跳過。所有內(nèi)表記錄遍歷完穴张，則整個(gè)過程就結(jié)束了细燎。過程參照下圖，來源于MySQL官方博客

左側(cè)是build過程皂甘，右側(cè)是probe過程玻驻，country_id是equal_join條件，countries表是外表偿枕，persons表是內(nèi)表璧瞬。

On-Disk Hash Join

CHJ的局限性在于需要內(nèi)存來適應(yīng)整個(gè)曲面。在mysql中渐夸，join可以使用的內(nèi)存由join buffer size參數(shù)控制嗤锉。如果一個(gè)連接所需的內(nèi)存超過了連接緩沖區(qū)的大小，CHJ會(huì)忍不住將曲面分成幾個(gè)段墓塌，逐個(gè)構(gòu)建每個(gè)段瘟忱，然后遍歷內(nèi)部表，再次探測(cè)每個(gè)段苫幢。假設(shè)表面被分成n塊访诱，然后掃描內(nèi)表n次。當(dāng)然韩肝，這種方式比較弱触菜。在MySQL 8.0中，如果一個(gè)join所需的內(nèi)存超過了join緩沖區(qū)的大小哀峻，那么構(gòu)建階段將首先使用哈希計(jì)算來劃分外表面并生成一個(gè)臨時(shí)的磁盤分區(qū)玫氢；然后在探測(cè)階段，使用相同的哈希算法來劃分內(nèi)表谜诫。由于相同的哈希函數(shù)漾峡，相同的鍵（相同的連接條件）必須在相同的分區(qū)號(hào)中。接下來喻旷，對(duì)外部表和內(nèi)部表中具有相同分區(qū)號(hào)的數(shù)據(jù)執(zhí)行CHJ生逸。在所有的CHJ片段完成之后，整個(gè)連接過程就完成了且预。該算法的代價(jià)是外部表讀IO兩次槽袄，內(nèi)部表寫IO一次。與以往的n掃描內(nèi)表IO相比锋谐，目前的處理方法更好遍尺。

include<cstdio>

include<algorithm>

include<queue>

include<cstring>

using namespace std;
struct data
{
int to,next,val;
}e[2*100005];
int cnt,head[10005],prep[10005],pree[10005],flow[10005],ans;
queue<int> que;
int n,m,s,t,u,v,w;
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].val=w;
}
int bfs(int s,int t)
{
while (!que.empty()) que.pop();
flow[s]=0x3f3f3f3f;//flow記錄的是在增廣路上經(jīng)過該點(diǎn)的流量
que.push(s);
for (int i=1;i<=n;i++)
{
prep[i]=-1;//用于記錄前驅(qū)節(jié)點(diǎn)
pree[i]=0;//用于記錄前驅(qū)邊的編號(hào)
}
prep[s]=0;
while (!que.empty())
{
int now=que.front();
que.pop();
if (now==t) break;
for (int i=head[now];i;i=e[i].next)
{
if (e[i].val>0&&prep[e[i].to]==-1)
{
que.push(e[i].to);
flow[e[i].to]=min(flow[now],e[i].val);
pree[e[i].to]=i;
prep[e[i].to]=now;
}
}
}
if (prep[t]!=-1) return flow[t];
else return -1;
}
void EK(int s,int t)
{
int delta=bfs(s,t);//尋找最短增廣路的最大流量
while (delta!=-1)
{
ans+=delta;
for (int j=t;j;j=prep[j])
{
e[pree[j]].val-=delta;
e[pree[j]^1].val+=delta;
//鏈?zhǔn)角跋蛐谴孢厪木幪?hào)2開始存儲(chǔ)可以通過異或1快速取得反向邊的編號(hào)。
}
delta=bfs(s,t);
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
cnt=1;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(v,u,0);
add(u,v,w);
//加入正反邊
}
EK(s,t);
printf("%d",ans);
return 0;

左上側(cè)圖是外表的分片過程涮拗，右上側(cè)圖是內(nèi)表的分片過程乾戏，最下面的圖是對(duì)分片進(jìn)行build+probe過程迂苛。

Grace Hash Join

與GraceHashJoin的區(qū)別在于，如果緩存能緩存足夠多的分片數(shù)據(jù)鼓择，會(huì)盡量緩存三幻，那么就不必像GraceHash那樣，嚴(yán)格地將所有分片都先讀進(jìn)內(nèi)存呐能，然后寫到外存念搬，然后再讀進(jìn)內(nèi)存去走build過程。這個(gè)是在內(nèi)存相對(duì)于分片比較充裕的情況下的一種優(yōu)化摆出，目的是為了減少磁盤的讀寫IO朗徊。目前Oceanbase的HashJoin采用的是這種join方式。

GraceHash在遇到這種情況時(shí)偎漫，會(huì)繼續(xù)分片進(jìn)行二次Hash爷恳，直到內(nèi)存足夠放下一個(gè)hash表為止。但是骑丸，這里仍然有極端情況，如果輸入join條件都相同妒貌，那么無論進(jìn)行多少次Hash通危，都沒法分開，那么這個(gè)時(shí)候GraceHashJoin也退化成和MySQL的處理方式一樣灌曙。

主流數(shù)據(jù)庫Oracle菊碟、SQL server和PostgreSQL長期以來都支持hashjoin。連接算法類似在刺。這里我們介紹Oracle使用的grace散列連接算法逆害。實(shí)際上，整個(gè)過程與MySQL的hashjoin類似蚣驼，有一個(gè)主要區(qū)別魄幕。當(dāng)連接緩沖區(qū)大小不足時(shí)，MySQL對(duì)外觀進(jìn)行分段并執(zhí)行CHJ進(jìn)程颖杏。但是纯陨，在極端情況下，如果數(shù)據(jù)分布不均勻留储，經(jīng)過哈希處理后會(huì)有大量數(shù)據(jù)分布在一個(gè)bucket中翼抠，導(dǎo)致分段后連接緩沖區(qū)大小不足。MySQL的處理方法是一次讀取多條記錄获讳，并讀取它們建立一個(gè)哈希表阴颖，然后相應(yīng)出現(xiàn)的探針就會(huì)被碎片化。處理批處理后丐膝，清除哈希表并重復(fù)上述過程量愧，直到處理完此分區(qū)的所有數(shù)據(jù)钾菊。當(dāng)連接緩沖區(qū)大小不足時(shí)，此過程與CHJ的處理邏輯相同侠畔。

hybrid hash join

MySQL-Join算法優(yōu)化
BlockNestLoopJoin(BNLJ)

MySQL采用了批量技術(shù)结缚，即一次利用join_buffer_size緩存足夠多的記錄，每次遍歷內(nèi)表時(shí)软棺，每條內(nèi)表記錄與這一批數(shù)據(jù)進(jìn)行條件判斷红竭，這樣就減少了掃描內(nèi)表的次數(shù)，如果內(nèi)表比較大喘落，間接就緩解了IO的讀壓力茵宪。

在MySQL 8.0.18之前，也就是說瘦棋，MySQL數(shù)據(jù)庫中很久沒有hashjoin了稀火。主要的連接算法是嵌套環(huán)連接。SimpleNetLoopJoin顯然效率低下赌朋。它需要對(duì)內(nèi)部表進(jìn)行n次全表掃描凰狞。實(shí)際的復(fù)雜度是n*m，n是外部記錄的數(shù)目沛慢，m是記錄的數(shù)目赡若，它代表內(nèi)部表的一次掃描的成本。為此团甲，MySQL對(duì)simplenetloopjoin做了一些優(yōu)化逾冬，下面的圖片都是來自網(wǎng)絡(luò)的。

IndexNestLoopJoin(INLJ)

如果我們能對(duì)內(nèi)表的join條件建立索引躺苦，那么對(duì)于外表的每條記錄身腻，無需再進(jìn)行全表掃描內(nèi)表，只需要一次Btree-Lookup即可匹厘，整體時(shí)間復(fù)雜度降低為N*O(logM)嘀趟。對(duì)比HashJoin，對(duì)于外表每條記錄愈诚，HashJoin是一次HashTable的search去件，當(dāng)然HashTable也有build時(shí)間，還需要處理內(nèi)存不足的情況扰路，不一定比INLJ好尤溜。

Batched Key Access

IndexNestLoopJoin利用join條件的索引，通過Btree-Lookup去匹配減少了遍歷內(nèi)表的代價(jià)汗唱。如果join條件是非主鍵列宫莱，那么意味著大量的回表和隨機(jī)IO。BKA優(yōu)化的做法是哩罪，將滿足條件的一批數(shù)據(jù)按主鍵排序授霸，這樣回表時(shí)巡验，從主鍵的角度來說就相對(duì)有序，緩解隨機(jī)IO的代價(jià)碘耳。BKA實(shí)際上是利用了MRR特性(MultiRangeRead)显设，訪問數(shù)據(jù)之前，先將主鍵排序辛辨，然后再訪問捕捂。主鍵排序的緩存大小通過參數(shù)read_rnd_buffer_size控制。

總結(jié)
在MySQL 8.0之后斗搞，對(duì)服務(wù)器層代碼進(jìn)行了大量重構(gòu)指攒。盡管優(yōu)化器仍然遠(yuǎn)遠(yuǎn)落后于Oracle，但它一直在改進(jìn)僻焚。在hashjoin的支持下允悦，MySQL優(yōu)化器有了更多的選擇，SQL的執(zhí)行路徑也會(huì)更好虑啤，特別是在等價(jià)連接的情況下隙弛。盡管MySQL以前對(duì)join做過一些優(yōu)化，如nblj狞山、inlj全闷、BKA等，但是它們不能替代hashjoin的角色铣墨。一個(gè)好的數(shù)據(jù)庫應(yīng)該具有豐富的基本功能室埋。使用優(yōu)化器分析適當(dāng)?shù)膱鼍鞍炀缓竽贸鱿鄳?yīng)的基本功能以最有效的方式響應(yīng)請(qǐng)求伊约。