概述
跟傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)類(lèi)似，分布式環(huán)境中的join在提供優(yōu)化器“hint”（提示）以告訴優(yōu)化器選擇一些執(zhí)行策略颂翼。目前一些優(yōu)化提示主要針對(duì)批處理中的連接（join）晃洒。在批處理中共有三個(gè)跟連接有關(guān)的轉(zhuǎn)換函數(shù)：
join:默認(rèn)為等值連接（Equi-join），即我們平時(shí)看到的inner join朦乏；
outerjoin：外連接球及，具體細(xì)分為left-outer join、righ-outer join呻疹、full-outer join吃引；
cross：交叉連接，求兩個(gè)數(shù)據(jù)集的笛卡爾積。
1.算法分析
常用來(lái)實(shí)現(xiàn)連接的算法有：hash join镊尺、sort-merge join以及nested loop join朦佩，下面我們對(duì)這三種算法進(jìn)行簡(jiǎn)單介紹。首先hash算法實(shí)現(xiàn)連接時(shí)庐氮，通常分為兩個(gè)階段：
build：為參與連接的兩個(gè)數(shù)據(jù)集中較小的數(shù)據(jù)集準(zhǔn)備好哈希表语稠，哈希表中的記錄包含著連接的屬性以及它對(duì)應(yīng)的行。因?yàn)楣１硎峭ㄟ^(guò)對(duì)連接屬性應(yīng)用一個(gè)哈希函數(shù)來(lái)訪問(wèn)的弄砍，因此通過(guò)它將比掃描初始數(shù)據(jù)集更快地發(fā)現(xiàn)給定的連接屬性對(duì)應(yīng)的行仙畦；
probe：一旦哈希表構(gòu)建完成，會(huì)掃描更大的數(shù)據(jù)集并通過(guò)從更小的數(shù)據(jù)集匹配哈希表以發(fā)現(xiàn)相關(guān)的行输枯。
而使用sort-merge算法實(shí)現(xiàn)連接時(shí)议泵，通常也劃分為兩個(gè)階段：
sort：對(duì)兩個(gè)數(shù)據(jù)集在他們的連接屬性上進(jìn)行排序；
merge：合并排過(guò)序的數(shù)據(jù)集桃熄。
nested loop實(shí)現(xiàn)連接相對(duì)更容易理解先口，它使用兩層嵌套循環(huán)分別作用于兩個(gè)參與連接的數(shù)據(jù)集。
2.連接策略
通過(guò)上面的介紹瞳收，我們得知當(dāng)選擇hash算法來(lái)實(shí)現(xiàn)連接時(shí)碉京，需要確定以哪個(gè)輸入端作為build端，哪個(gè)輸入端作為probe端螟深，這是影響其執(zhí)行效率的因素之一（因?yàn)橥ǔ＿x擇數(shù)據(jù)量較小的數(shù)據(jù)集作為build端）谐宙。而當(dāng)以sort-merge算法來(lái)實(shí)現(xiàn)連接時(shí)，不會(huì)區(qū)分輸入端的特殊職責(zé)界弧，也就不存在build階段和probe階段凡蜻。
為了理清算法跟參與連接的輸入端的關(guān)系，F(xiàn)link將它們區(qū)分成兩種不同策略的：本地策略以及傳輸（ship）策略垢箕。其中傳輸策略表示如何移動(dòng)兩個(gè)輸入端中的數(shù)據(jù)使得它們具備連接的條件划栓；本地策略則指兩個(gè)已在本地的輸入端數(shù)據(jù)集所執(zhí)行的連接算法。
我們來(lái)解釋一下這兩種策略条获，假設(shè)有兩個(gè)待連接的數(shù)據(jù)集（R和S）忠荞。傳輸策略有如下兩種：
Broadcast-Forward strategy (BF)：該策略會(huì)將一個(gè)完整的數(shù)據(jù)集，比如R帅掘，廣播到數(shù)據(jù)集S的每一個(gè)分區(qū)上委煤，而數(shù)據(jù)集S的所有數(shù)據(jù)則一直處于本地，無(wú)需網(wǎng)絡(luò)傳輸修档；
Repartition-Repartition strategy (RR)：以相同的分區(qū)函數(shù)以及用于連接的鍵屬性分區(qū)兩個(gè)數(shù)據(jù)集R碧绞、S；
正如上面已經(jīng)提及的吱窝，本地策略也即連接的實(shí)現(xiàn)算法也有兩種：
Sort-Merge-Join strategy (SM)：首先對(duì)兩個(gè)輸入端的數(shù)據(jù)集在它們的連接鍵屬性上進(jìn)行排序（排序階段）讥邻，然后合并排過(guò)序的數(shù)據(jù)集（合并階段）寓免；
Hybrid-Hash-Join strategy (HH)：分為構(gòu)建階段和探索階段；
在不指定“Hint”的情況下计维，F(xiàn)link在進(jìn)行批處理優(yōu)化時(shí)會(huì)根據(jù)成本自動(dòng)選擇傳輸策略以及本地策略袜香。優(yōu)化器的一個(gè)關(guān)鍵特征是它會(huì)根據(jù)已經(jīng)存在的數(shù)據(jù)屬性來(lái)進(jìn)行推理。就連接運(yùn)算而言鲫惶，如果某一個(gè)輸入端的數(shù)據(jù)量遠(yuǎn)小于另一輸入端蜈首，F(xiàn)link會(huì)傾向于選擇BF傳輸策略，將較小的輸入端廣播給較大的輸入端的每一個(gè)分區(qū)欠母，并在本地策略中選擇HH且以較小的輸入端作為HH的構(gòu)建端欢策；如果優(yōu)化器得知某個(gè)（或兩個(gè)）輸入端已排好序，那么生成的候選計(jì)劃將不再重分區(qū)該輸入端赏淌，此時(shí)它更傾向于選擇RR傳輸策略以及SM本地策略踩寇。
除了優(yōu)化器的自動(dòng)選擇，當(dāng)用戶(hù)對(duì)數(shù)據(jù)集非常了解的情況下六水，F(xiàn)link定義了JoinHint允許用戶(hù)為join（inner join）指定連接策略給予優(yōu)化器提示俺孙。JoinHint提供了人為選擇連接策略的靈活性，其使用方式有兩種掷贾，一種是直接指定兩個(gè)輸入端的大芯﹂：
另一種是直接指定連接策略：
