Join在Spark中是如何組織運(yùn)行的

Join作為SQL中一個(gè)重要語(yǔ)法特性，幾乎所有稍微復(fù)雜一點(diǎn)的數(shù)據(jù)分析場(chǎng)景都離不開(kāi)Join，如今Spark SQL(Dataset/DataFrame)已經(jīng)成為Spark應(yīng)用程序開(kāi)發(fā)的主流，作為開(kāi)發(fā)者，我們有必要了解Join在Spark中是如何組織運(yùn)行的。

SparkSQL總體流程介紹

在闡述Join實(shí)現(xiàn)之前，我們首先簡(jiǎn)單介紹SparkSQL的總體流程，一般地，我們有兩種方式使用SparkSQL，一種是直接寫(xiě)sql語(yǔ)句，這個(gè)需要有元數(shù)據(jù)庫(kù)支持，例如Hive等，另一種是通過(guò)Dataset/DataFrame編寫(xiě)Spark應(yīng)用程序。如下圖所示，sql語(yǔ)句被語(yǔ)法解析(SQL AST)成查詢(xún)計(jì)劃，或者我們通過(guò)Dataset/DataFrame提供的APIs組織成查詢(xún)計(jì)劃，查詢(xún)計(jì)劃分為兩大類(lèi)：邏輯計(jì)劃和物理計(jì)劃，這個(gè)階段通常叫做邏輯計(jì)劃，經(jīng)過(guò)語(yǔ)法分析(Analyzer)、一系列查詢(xún)優(yōu)化(Optimizer)后得到優(yōu)化后的邏輯計(jì)劃，最后被映射成物理計(jì)劃，轉(zhuǎn)換成RDD執(zhí)行。

對(duì)于語(yǔ)法解析、語(yǔ)法分析以及查詢(xún)優(yōu)化，本文不做詳細(xì)闡述，本文重點(diǎn)介紹Join的物理執(zhí)行過(guò)程。

Join基本要素

如下圖所示，Join大致包括三個(gè)要素：Join方式、Join條件以及過(guò)濾條件。其中過(guò)濾條件也可以通過(guò)AND語(yǔ)句放在Join條件中。

Spark支持所有類(lèi)型的Join，包括：

inner join

left outer join

right outer join

full outer join

left semi join

left anti join

下面分別闡述這幾種Join的實(shí)現(xiàn)。

Join基本實(shí)現(xiàn)流程

總體上來(lái)說(shuō)，Join的基本實(shí)現(xiàn)流程如下圖所示，Spark將參與Join的兩張表抽象為流式遍歷表(streamIter)和查找表(buildIter)，通常streamIter為大表，buildIter為小表，我們不用擔(dān)心哪個(gè)表為streamIter，哪個(gè)表為buildIter，這個(gè)spark會(huì)根據(jù)join語(yǔ)句自動(dòng)幫我們完成。

在實(shí)際計(jì)算時(shí)，spark會(huì)基于streamIter來(lái)遍歷，每次取出streamIter中的一條記錄rowA，根據(jù)Join條件計(jì)算keyA，然后根據(jù)該keyA去buildIter中查找所有滿足Join條件(keyB==keyA)的記錄rowBs，并將rowBs中每條記錄分別與rowAjoin得到j(luò)oin后的記錄，最后根據(jù)過(guò)濾條件得到最終join的記錄。

從上述計(jì)算過(guò)程中不難發(fā)現(xiàn)，對(duì)于每條來(lái)自streamIter的記錄，都要去buildIter中查找匹配的記錄，所以buildIter一定要是查找性能較優(yōu)的數(shù)據(jù)結(jié)構(gòu)。spark提供了三種join實(shí)現(xiàn)：sort merge join、broadcast join以及hash join。

sort merge join實(shí)現(xiàn)

要讓兩條記錄能join到一起，首先需要將具有相同key的記錄在同一個(gè)分區(qū)，所以通常來(lái)說(shuō)，需要做一次shuffle，map階段根據(jù)join條件確定每條記錄的key，基于該key做shuffle write，將可能join到一起的記錄分到同一個(gè)分區(qū)中，這樣在shuffle read階段就可以將兩個(gè)表中具有相同key的記錄拉到同一個(gè)分區(qū)處理。前面我們也提到，對(duì)于buildIter一定要是查找性能較優(yōu)的數(shù)據(jù)結(jié)構(gòu)，通常我們能想到hash表，但是對(duì)于一張較大的表來(lái)說(shuō)，不可能將所有記錄全部放到hash表中，另外也可以對(duì)buildIter先排序，查找時(shí)按順序查找，查找代價(jià)也是可以接受的，我們知道，spark shuffle階段天然就支持排序，這個(gè)是非常好實(shí)現(xiàn)的，下面是sort merge join示意圖。

在shuffle read階段，分別對(duì)streamIter和buildIter進(jìn)行merge sort，在遍歷streamIter時(shí)，對(duì)于每條記錄，都采用順序查找的方式從buildIter查找對(duì)應(yīng)的記錄，由于兩個(gè)表都是排序的，每次處理完streamIter的一條記錄后，對(duì)于streamIter的下一條記錄，只需從buildIter中上一次查找結(jié)束的位置開(kāi)始查找，所以說(shuō)每次在buildIter中查找不必重頭開(kāi)始，整體上來(lái)說(shuō)，查找性能還是較優(yōu)的。

broadcast join實(shí)現(xiàn)

為了能具有相同key的記錄分到同一個(gè)分區(qū)，我們通常是做shuffle，那么如果buildIter是一個(gè)非常小的表，那么其實(shí)就沒(méi)有必要大動(dòng)干戈做shuffle了，直接將buildIter廣播到每個(gè)計(jì)算節(jié)點(diǎn)，然后將buildIter放到hash表中，如下圖所示。

從上圖可以看到，不用做shuffle，可以直接在一個(gè)map中完成，通常這種join也稱(chēng)之為map join。那么問(wèn)題來(lái)了，什么時(shí)候會(huì)用broadcast join實(shí)現(xiàn)呢？這個(gè)不用我們擔(dān)心，spark sql自動(dòng)幫我們完成，當(dāng)buildIter的估計(jì)大小不超過(guò)參數(shù)spark.sql.autoBroadcastJoinThreshold設(shè)定的值(默認(rèn)10M)，那么就會(huì)自動(dòng)采用broadcast join，否則采用sort merge join。

hash join實(shí)現(xiàn)

除了上面兩種join實(shí)現(xiàn)方式外，spark還提供了hash join實(shí)現(xiàn)方式，在shuffle read階段不對(duì)記錄排序，反正來(lái)自?xún)筛癖淼木哂邢嗤琸ey的記錄會(huì)在同一個(gè)分區(qū)，只是在分區(qū)內(nèi)不排序，將來(lái)自buildIter的記錄放到hash表中，以便查找，如下圖所示。

不難發(fā)現(xiàn)，要將來(lái)自buildIter的記錄放到hash表中，那么每個(gè)分區(qū)來(lái)自buildIter的記錄不能太大，否則就存不下，默認(rèn)情況下hash join的實(shí)現(xiàn)是關(guān)閉狀態(tài)，如果要使用hash join，必須滿足以下四個(gè)條件：

buildIter總體估計(jì)大小超過(guò)spark.sql.autoBroadcastJoinThreshold設(shè)定的值，即不滿足broadcast join條件

開(kāi)啟嘗試使用hash join的開(kāi)關(guān)，spark.sql.join.preferSortMergeJoin=false

每個(gè)分區(qū)的平均大小不超過(guò)spark.sql.autoBroadcastJoinThreshold設(shè)定的值，即shuffle read階段每個(gè)分區(qū)來(lái)自buildIter的記錄要能放到內(nèi)存中

streamIter的大小是buildIter三倍以上

所以說(shuō)，使用hash join的條件其實(shí)是很苛刻的，在大多數(shù)實(shí)際場(chǎng)景中，即使能使用hash join，但是使用sort merge join也不會(huì)比hash join差很多，所以盡量使用hash

下面我們分別闡述不同Join方式的實(shí)現(xiàn)流程。

inner join

inner join是一定要找到左右表中滿足join條件的記錄，我們?cè)趯?xiě)sql語(yǔ)句或者使用DataFrame時(shí)，可以不用關(guān)心哪個(gè)是左表，哪個(gè)是右表，在spark sql查詢(xún)優(yōu)化階段，spark會(huì)自動(dòng)將大表設(shè)為左表，即streamIter，將小表設(shè)為右表，即buildIter。這樣對(duì)小表的查找相對(duì)更優(yōu)。其基本實(shí)現(xiàn)流程如下圖所示，在查找階段，如果右表不存在滿足join條件的記錄，則跳過(guò)。

left outer join

left outer join是以左表為準(zhǔn)，在右表中查找匹配的記錄，如果查找失敗，則返回一個(gè)所有字段都為null的記錄。我們?cè)趯?xiě)sql語(yǔ)句或者使用DataFrmae時(shí)，一般讓大表在左邊，小表在右邊。其基本實(shí)現(xiàn)流程如下圖所示。

right outer join

right outer join是以右表為準(zhǔn)，在左表中查找匹配的記錄，如果查找失敗，則返回一個(gè)所有字段都為null的記錄。所以說(shuō)，右表是streamIter，左表是buildIter，我們?cè)趯?xiě)sql語(yǔ)句或者使用DataFrame時(shí)，一般讓大表在右邊，小表在左邊。其基本實(shí)現(xiàn)流程如下圖所示。

full outer join

full outer join相對(duì)來(lái)說(shuō)要復(fù)雜一點(diǎn)，總體上來(lái)看既要做left outer join，又要做right outer join，但是又不能簡(jiǎn)單地先left outer join，再right outer join，最后union得到最終結(jié)果，因?yàn)檫@樣最終結(jié)果中就存在兩份inner join的結(jié)果了。因?yàn)榧热煌瓿蒷eft outer join又要完成right outer join，所以full outer join僅采用sort merge join實(shí)現(xiàn)，左邊和右表既要作為streamIter，又要作為buildIter，其基本實(shí)現(xiàn)流程如下圖所示。

由于左表和右表已經(jīng)排好序，首先分別順序取出左表和右表中的一條記錄，比較key，如果key相等，則joinrowA和rowB，并將rowA和rowB分別更新到左表和右表的下一條記錄；如果keyAkeyB，則說(shuō)明左表中沒(méi)有與右表rowB對(duì)應(yīng)的記錄，那么joinnullRow與rowB，緊接著，rowB更新到右表的下一條記錄。如此循環(huán)遍歷直到左表和右表的記錄全部處理完。

left semi join

left semi join是以左表為準(zhǔn)，在右表中查找匹配的記錄，如果查找成功，則僅返回左邊的記錄，否則返回null，其基本實(shí)現(xiàn)流程如下圖所示。

left anti join

left anti join與left semi join相反，是以左表為準(zhǔn)，在右表中查找匹配的記錄，如果查找成功，則返回null，否則僅返回左邊的記錄，其基本實(shí)現(xiàn)流程如下圖所示。

總結(jié)

Join是數(shù)據(jù)庫(kù)查詢(xún)中一個(gè)非常重要的語(yǔ)法特性，在數(shù)據(jù)庫(kù)領(lǐng)域可以說(shuō)是“得join者得天下”，SparkSQL作為一種分布式數(shù)據(jù)倉(cāng)庫(kù)系統(tǒng)，給我們提供了全面的join支持，并在內(nèi)部實(shí)現(xiàn)上無(wú)聲無(wú)息地做了很多優(yōu)化，了解join的實(shí)現(xiàn)將有助于我們更深刻的了解我們的應(yīng)用程序的運(yùn)行軌跡。

責(zé)任編輯：xj

原文標(biāo)題：面試必知的 Spark SQL 幾種 Join 實(shí)現(xiàn)

文章出處：【微信公眾號(hào)：人工智能與大數(shù)據(jù)技術(shù)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。