李甜甜 于 戈 郭朝鵬 宋 杰

1（東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽(yáng) 110819）2（東北大學(xué)軟件學(xué)院 沈陽(yáng) 110819）（litiantian＿neu＠163．com）

基于MapReduce的多元連接優(yōu)化方法

李甜甜1于 戈1郭朝鵬2宋 杰2

1（東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽(yáng) 110819）2（東北大學(xué)軟件學(xué)院 沈陽(yáng) 110819）（litiantian＿neu＠163．com）

多元連接是數(shù)據(jù)分析最常用的操作之一，MapReduce是廣泛用于大規(guī)模數(shù)據(jù)分析處理的編程模型，它給多元連接優(yōu)化帶來(lái)新的挑戰(zhàn)：傳統(tǒng)的優(yōu)化方法不能簡(jiǎn)單地適用到MapReduce中；MapReduce連接執(zhí)行算法尚存優(yōu)化空間．針對(duì)前者，考慮到I?O代價(jià)是連接運(yùn)算的主要代價(jià)，首先以降低I?O代價(jià)為目標(biāo)提出一種啟發(fā)式算法確定多元連接執(zhí)行順序，并在此基礎(chǔ)上進(jìn)一步優(yōu)化，最后針對(duì)MapReduce設(shè)計(jì)一種并行執(zhí)行策略提高多元連接的整體性能．針對(duì)后者，考慮到負(fù)載均衡能夠有效減少M(fèi)apReduce的“木桶效應(yīng)”，通過(guò)任務(wù)公平分配算法提高連接內(nèi)部的并行度，并在此基礎(chǔ)上給出Reduce任務(wù)個(gè)數(shù)的確定方法．最后，通過(guò)實(shí)驗(yàn)驗(yàn)證本文提出的執(zhí)行計(jì)劃確定方法以及負(fù)載均衡算法的優(yōu)化效果．該研究對(duì)大數(shù)據(jù)環(huán)境下MapReduce多元連接的應(yīng)用具有指導(dǎo)意義，可以優(yōu)化如OLAP分析中的星型連接、社交網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)的鏈?zhǔn)竭B接等應(yīng)用的性能．

多元連接；執(zhí)行計(jì)劃；I?O代價(jià)；性能優(yōu)化；MapReduce編程模型；負(fù)載均衡

連接運(yùn)算根據(jù)連接條件把2個(gè)或多個(gè)關(guān)系中的記錄組合為一個(gè)結(jié)果數(shù)據(jù)集，包含連接運(yùn)算的查詢簡(jiǎn)稱為連接查詢．連接查詢?cè)跀?shù)據(jù)分析中很常見(jiàn)，TPC－H提供的22個(gè)查詢用例中有16個(gè)涉及到此類查詢［1］．當(dāng)一個(gè)連接查詢涉及n個(gè)關(guān)系時(shí)，稱為n元連接；當(dāng)n＞2時(shí)，稱為多元連接，多元連接是數(shù)據(jù)分析中最常用的操作之一．此外，在當(dāng)今的大數(shù)據(jù)環(huán)境下，MapReduce［2］編程模型被廣泛用于大規(guī)模數(shù)據(jù)集的分析處理．目前，MapReduce中數(shù)據(jù)分析的優(yōu)化工作包括索引、數(shù)據(jù)布局、查詢優(yōu)化、迭代處理、公平負(fù)載分配以及交互式處理等方面［3］．基于此，我們分析MapReduce給多元連接的優(yōu)化帶來(lái)的新挑戰(zhàn)．

首先，多元連接查詢依賴良好的執(zhí)行計(jì)劃．傳統(tǒng)的執(zhí)行計(jì)劃確定方法［4］不滿足MapReduce特性，無(wú)法通過(guò)簡(jiǎn)單的適應(yīng)性更改應(yīng)用到現(xiàn)有的優(yōu)化中．另外，現(xiàn)有基于MapReduce的執(zhí)行計(jì)劃確定方法［5－6］復(fù)雜度較高，應(yīng)用范圍受限．因此，亟需提出一種新的滿足MapReduce特性且復(fù)雜度較低的執(zhí)行計(jì)劃確定方法．此外，我們還注意到，無(wú)論是傳統(tǒng)研究還是現(xiàn)有研究，其執(zhí)行計(jì)劃都只確定了連接的執(zhí)行順序，并未考慮無(wú)依賴關(guān)系的連接操作間的并行執(zhí)行策略．

其次，良好的執(zhí)行計(jì)劃固然重要，對(duì)執(zhí)行框架的優(yōu)化同樣可以有效地提高多元連接的性能，這一點(diǎn)在分布式環(huán)境中尤為重要．一種公平的并行任務(wù)負(fù)載分配方法可以有效地減少M(fèi)apReduce中的“木桶效應(yīng)”，從而提高連接操作內(nèi)部的并行度．然而，就我們所知，目前沒(méi)有針對(duì)連接運(yùn)算的MapReduce負(fù)載均衡方法，且現(xiàn)有的通用方法［7－9］僅考慮了任務(wù)的輸入代價(jià)，不適用于連接運(yùn)算，因?yàn)樗妮敵龃鷥r(jià)也不可忽略．

本文研究MapReduce環(huán)境下多元連接的優(yōu)化方法，基于上述分析提出以下問(wèn)題：1）多元連接執(zhí)行計(jì)劃的解空間很大，短時(shí)間內(nèi)很難找到最優(yōu)解，那么能否通過(guò)某個(gè)復(fù)雜度較小的算法快速找到一個(gè)近似最優(yōu)解；2）連接運(yùn)算屬于I?O密集型運(yùn)算，I?O為主要代價(jià)，那么能否針對(duì)MapReduce特性提出I?O代價(jià)模型，并選擇代價(jià)最小的執(zhí)行計(jì)劃；3）連接順序確定后，不存在依賴關(guān)系的連接操作可以并行執(zhí)行，那么當(dāng)存在多個(gè)滿足并行執(zhí)行的連接操作時(shí)該如何選擇；4）執(zhí)行框架的優(yōu)化中，負(fù)載均衡能夠有效地減少“短板效應(yīng)”，那么此處的連接負(fù)載又該如何定義．這些問(wèn)題的求解存在一定程度的挑戰(zhàn)，就我們目前所知，尚未發(fā)現(xiàn)能夠完全解決上述問(wèn)題的研究工作．

本文首先通過(guò)分析多元連接執(zhí)行計(jì)劃解空間的縮減方法、MapReduce連接算法的I?O代價(jià)模型、Replicated Join①的優(yōu)劣以及MapReduce作業(yè)的并行執(zhí)行特性，最終確定了執(zhí)行計(jì)劃的優(yōu)化方法；接著，結(jié)合MapReduce框架分析連接運(yùn)算的特性，提出負(fù)載均衡模型及其對(duì)應(yīng)的均衡算法，并在此基礎(chǔ)上提出Reduce任務(wù)個(gè)數(shù)的確定方法．大量實(shí)驗(yàn)驗(yàn)證了本文提出的優(yōu)化方法的有效性．

1 相關(guān)工作

現(xiàn)有多元連接的優(yōu)化研究可歸為以下3類：執(zhí)行計(jì)劃的優(yōu)化、連接算法的優(yōu)化和執(zhí)行框架的優(yōu)化．

對(duì)于第1類研究，文獻(xiàn)［4］將n元連接拆分為n－1個(gè)2元連接，每個(gè)2元連接對(duì)應(yīng)一個(gè)MapReduce作業(yè)（后文如不特殊指明，作業(yè)均為MapReduce作業(yè)），然而該方法針對(duì)的是傳統(tǒng)的多處理器計(jì)算環(huán)境，不適用于MapReduce，且該方法在n較大時(shí)會(huì)導(dǎo)致較高的作業(yè)初始化代價(jià)以及中間結(jié)果的存儲(chǔ)代價(jià)．文獻(xiàn)［10］針對(duì)鏈?zhǔn)竭B接提出使用平衡二叉樹(shù)的方式來(lái)執(zhí)行多元連接，但其并未給出平衡二叉樹(shù)的構(gòu)建規(guī)則．文獻(xiàn)［11］在一個(gè)作業(yè)中完成所有的連接運(yùn)算，然而該方法在n較大時(shí)會(huì)因?yàn)閿?shù)據(jù)需要傳輸

①Replicated Join：在一個(gè)MRJ中執(zhí)行多個(gè)連接操作．此時(shí)，同一個(gè)Key－Value對(duì)需要被復(fù)制到多個(gè)Reducer上，因此稱為Replicated Join．該算法犧牲部分網(wǎng)絡(luò)I?O代價(jià)來(lái)?yè)Q取MRJ的初始化以及HDFS讀寫(xiě)代價(jià)．到多個(gè)Reducer而導(dǎo)致較高的網(wǎng)絡(luò)I?O代價(jià)．文獻(xiàn)［5－6］將n元連接劃分為若干個(gè)組，每組涉及若干個(gè)關(guān)系并由一個(gè)作業(yè)完成，而后采用Replicated Join連接所有組生成的中間結(jié)果，然而該方法因?yàn)橐F舉所有可能的m（m＜n）元連接作為候選集而導(dǎo)致算法復(fù)雜度較高，從而使其應(yīng)用范圍較窄．此外，上述所有研究確定的執(zhí)行計(jì)劃都只確定了連接的執(zhí)行順序，并未考慮無(wú)依賴關(guān)系的連接操作間的并行執(zhí)行策略．

本文首先基于MapReduce特性提出多元連接順序的確定方法，該方法復(fù)雜度較低且能夠很好地均衡中間結(jié)果的存儲(chǔ)代價(jià)與網(wǎng)絡(luò)傳輸代價(jià)．確定連接順序后，本文還給出一種算法來(lái)確定無(wú)依賴關(guān)系的連接操作間的并行執(zhí)行順序，該算法通過(guò)對(duì)節(jié)點(diǎn)資源的充分利用來(lái)提高多元連接的執(zhí)行效率．

對(duì)于第2類研究，文獻(xiàn)［12］針對(duì)theta－join提出一種隨機(jī)算法1－Bucket－Theta以及它的一個(gè)擴(kuò)展算法M－Bucket；文獻(xiàn)［13］對(duì)文獻(xiàn)［12］中提出的算法進(jìn)行下界分析，并通過(guò)聚類方法提高了M－Bucket算法的效率．文獻(xiàn)［14－15］總結(jié)現(xiàn)有實(shí)現(xiàn)算法為Map Join，Reduce Join，Semi Join等，這些算法分別適用于不同的查詢場(chǎng)景，如Map Join僅適用于數(shù)據(jù)量較小的關(guān)系能夠裝入內(nèi)存的查詢．MapReduce連接算法的優(yōu)化研究相對(duì)比較成熟，不在本文的研究范圍之內(nèi)．因此，不失一般性，本文采用沒(méi)有任何約束條件的通用的Reduce Join作為研究對(duì)象．

連接運(yùn)算的執(zhí)行效率依賴于實(shí)現(xiàn)算法和運(yùn)行環(huán)境，由此衍生出第3類研究．文獻(xiàn)［16］基于MapReduce提出一個(gè)改進(jìn)的執(zhí)行框架Map－Reduce－Merge，新添加的Merge階段為Reduce Join的執(zhí)行節(jié)省了一次作業(yè)．文獻(xiàn)［17］對(duì)MapReduce框架進(jìn)行修改，允許不同操作間的數(shù)據(jù)管道式傳輸，支持在線聚集以及持續(xù)查詢，然而改進(jìn)后的框架使得失效恢復(fù)（fail recovery）機(jī)制變得非常復(fù)雜，且對(duì)于批處理性能的提高也很不明顯．文獻(xiàn)［7－9］給出了通用的MapReduce負(fù)載均衡方法，但他們都只考慮了任務(wù)的輸入代價(jià)，不適用于連接運(yùn)算，因?yàn)樗妮敵龃鷥r(jià)也不可忽略．本文提出的MapReduce負(fù)載均衡方法著重考慮連接任務(wù)的負(fù)載特性，與傳統(tǒng)的負(fù)載均衡方法有所不同．具體來(lái)講，本文提出的負(fù)載均衡方法基于的Reduce Join的Map階段僅負(fù)責(zé)將參與連接的數(shù)據(jù)表中的記錄解析成Key－Value對(duì)（此時(shí)I?O操作很少），并通過(guò)Shuffle階段傳輸?shù)綄?duì)應(yīng)的Reduce任務(wù)中，而真正的連接操作是在Reduce階段中完成的（此時(shí)會(huì)產(chǎn)生大量I?O操作）．考慮到I?O代價(jià)是影響連接查詢的主要因素，我們對(duì)產(chǎn)生大量I?O操作的Reduce階段進(jìn)行讀寫(xiě)分析，綜合考慮Reduce任務(wù)的輸入和輸出代價(jià)及其對(duì)應(yīng)的讀寫(xiě)權(quán)重，最終基于這一綜合代價(jià)給出了Reduce任務(wù)的負(fù)載均衡方法．文獻(xiàn)［18］中實(shí)現(xiàn)的負(fù)載均衡是通過(guò)均衡數(shù)據(jù)塊實(shí)現(xiàn)的，本文與其有本質(zhì)上的區(qū)別．

2 連接執(zhí)行計(jì)劃

多元連接執(zhí)行計(jì)劃的解空間很大，短時(shí)間內(nèi)很難找到最優(yōu)解．本節(jié)首先通過(guò)查詢樹(shù)模型確定解的一個(gè)子空間，而后通過(guò)復(fù)雜度較小的啟發(fā)式算法從中找到一個(gè)近似最優(yōu)解，并在此基礎(chǔ)上做進(jìn)一步的優(yōu)化以均衡中間結(jié)果的存儲(chǔ)代價(jià)與網(wǎng)絡(luò)傳輸代價(jià)．最后，根據(jù)MapReduce框架特性給出一種算法來(lái)確定無(wú)依賴關(guān)系的連接操作間的并行執(zhí)行順序，該算法通過(guò)對(duì)節(jié)點(diǎn)資源的充分利用來(lái)提高多元連接的效率．

2．1 查詢樹(shù)模型

多元連接可以用一個(gè)查詢圖G＝（V，E）來(lái)表示［46］，其中V是節(jié)點(diǎn)的集合，每個(gè)節(jié)點(diǎn)代表一個(gè)關(guān)系（記為Ri），E是邊的集合，每條邊?Ri，Rj?連接2個(gè)之間存在連接屬性（A，B，C等）的關(guān)系，如圖1所示．圖1（a）所示的查詢圖包含6個(gè)關(guān)系，為6元連接；同理，圖1（b）所示的查詢圖為8元連接．

Fig．1 Example queries of multi－way join．圖1 多元連接查詢示例

多元連接執(zhí)行計(jì)劃的最優(yōu)解確定是個(gè)P完全問(wèn)題［6］，傳統(tǒng)優(yōu)化方法通常采用查詢樹(shù)模型限定解的一個(gè)子空間，并設(shè)計(jì)算法從中獲取一個(gè)最優(yōu)解．如圖2所示，主流的查詢樹(shù)模型有Left－deep Tree，Right－deep Tree，Zigzag Tree，Bushy Tree［19］四種，其中前3種為順序執(zhí)行，最后1種為并行執(zhí)行．很多研究工作［4－5］顯示，并行執(zhí)行的Bushy Tree更適用于分布式環(huán)境．從圖2也可以看出，只有基于Bushy Tree確定的連接順序中不同連接操作間不是完全的依賴關(guān)系，是可以并行的．因此，本文選取Bushy Tree作為MapReduce多元連接的查詢樹(shù)模型．

Fig．2 Query trees．圖2 查詢樹(shù)模型

2．2 查詢樹(shù)模型

一個(gè)n元連接的執(zhí)行方式有2種：1）將其拆分為n－1個(gè)2元連接分別執(zhí)行，每個(gè)2元連接對(duì)應(yīng)一個(gè)作業(yè)；2）在一個(gè)作業(yè)中執(zhí)行所有連接操作．然而，當(dāng)n較大時(shí)，第1種執(zhí)行方式的作業(yè)初始化代價(jià)以及中間結(jié)果的存儲(chǔ)代價(jià)也隨之增大，第2種執(zhí)行方式也因?yàn)閿?shù)據(jù)的多次傳輸而產(chǎn)生較大的網(wǎng)絡(luò)代價(jià)．為解決該問(wèn)題，本文首先基于Bushy Tree初步確定多元連接的執(zhí)行順序，而后根據(jù)是否受益將部分2元連接合并成多元連接．

1）基于I?O代價(jià)的連接順序確定方法

通過(guò)Bushy Tree確定多元連接的執(zhí)行順序首先需要給出樹(shù)的構(gòu)建規(guī)則．考慮到連接運(yùn)算屬于I?O密集型計(jì)算，連接代價(jià)以I?O代價(jià)為主，本文針對(duì)MapReduce特性給出連接運(yùn)算的I?O代價(jià)模型，并選擇I?O代價(jià)最小的連接順序．

正如第1節(jié)中的描述，本文選擇Reduce Join作為連接算法，下面以2元連接為例對(duì)其進(jìn)行簡(jiǎn)單介紹．Reduce Join由Map階段和Reduce階段組成．Map階段主要完成如下操作：①M(fèi)ap任務(wù)讀?。ㄍǔ楸镜刈x）參與連接的2個(gè)關(guān)系；②以連接屬性為鍵、記錄為值，按鍵排序后輸出鍵值對(duì)到本地磁盤；③將中間結(jié)果通過(guò)網(wǎng)絡(luò)傳輸給Reduce任務(wù)．Reduce階段主要完成如下操作：①接收來(lái)自Map任務(wù)的鍵值對(duì)并按鍵排序；②執(zhí)行連接操作，并將結(jié)果寫(xiě)入分布式文件系統(tǒng)（HDFS）．

基于該分析，我們給出關(guān)系Ri和Rj進(jìn)行Reduce Join的I?O代價(jià)計(jì)算方法，見(jiàn)式（1）：

其中，C1，C2，C3分別為本地、網(wǎng)絡(luò)和HDFS的I?O代價(jià)權(quán)重，三者均與系統(tǒng)硬件相關(guān)（其中C3還與HDFS的副本個(gè)數(shù)設(shè)置有關(guān)），其值均可事先通過(guò)文件讀寫(xiě)實(shí)驗(yàn)測(cè)出（在本文的實(shí)驗(yàn)環(huán)境中，副本個(gè)數(shù)為3，通過(guò)實(shí)驗(yàn)測(cè)得3個(gè)參數(shù)的值分別為C1＝3．67s?GB，C2＝8．93s?GB，C3＝13．37s?GB，三者之間的比值為1：2．4：3．6）；｜Ri｜代表關(guān)系的基數(shù)．另外，Map階段操作②首先需要溢出寫(xiě)文件，而后讀取并排序輸出，因此共需3次讀寫(xiě)操作；Reduce階段的操作①使用內(nèi)存和磁盤進(jìn)行混合式排序，因此我們用參數(shù)λ表示該混洗比例，其值可通過(guò)經(jīng)驗(yàn)設(shè)定．

通過(guò)Bushy Tree確定連接順序時(shí)，我們每次從查詢圖G＝（V，E）中選擇I?O代價(jià)最小的連接操作執(zhí)行，而后更新圖G及其對(duì)應(yīng)的關(guān)系的特征參數(shù)，直到執(zhí)行完所有連接運(yùn)算（見(jiàn)算法1）．算法1的復(fù)雜度為O（log（｜V｜｜E｜）），小于文獻(xiàn)［5－6］的復(fù)雜度O（log（｜V｜2｜E｜））．

算法1．PMC算法．?＊基于MC（minimal cost）的執(zhí)行計(jì)劃（plan）確定算法＊?

輸入：G＝（V，E），query profile；?＊包括關(guān)系的基數(shù)、連接屬性的基數(shù)等相關(guān)參數(shù)＊?

輸出：Bushy Tree．

PMC算法中計(jì)算最小代價(jià)時(shí)，｜Ri｜和｜Rj｜均已知，｜RiRj｜未知，需要我們計(jì)算．目前關(guān)于｜RiRj｜的計(jì)算方法通常假設(shè)Ri和Rj在連接屬性A上均勻分布［4，9］，具體計(jì)算方法見(jiàn)式（2）：

其中，｜A｜為連接屬性的基數(shù)．然而，事實(shí)上Ri和Rj通常不滿足均勻分布這一假設(shè)，因此在實(shí)際應(yīng)用中，我們應(yīng)該考慮數(shù)據(jù)傾斜因素．設(shè)Fi和Fj為A在Ri和Rj中出現(xiàn)的頻數(shù)分布，則定義傾斜度如下：

定義1．傾斜度．定義傾斜度δ為頻數(shù)分布Fi和Fj偏離均勻分布的程度，表達(dá)式見(jiàn)式（3）：

在實(shí)際計(jì)算中，傾斜度可以通過(guò)采樣獲?。辛藘A斜度，｜RiRj｜的計(jì)算方法見(jiàn)式（4）：

因?yàn)?/p>

考慮傾斜度因素計(jì)算出的｜RiRj｜更精確，同時(shí)基于最小代價(jià)的PMC算法確定的連接順序也更優(yōu)．

2）基于Replicated Join的優(yōu)化

通過(guò)Bushy Tree確定的執(zhí)行順序僅包含2元連接，這樣的執(zhí)行計(jì)劃會(huì)導(dǎo)致較高的作業(yè)初始化代價(jià)和中間結(jié)果的存儲(chǔ)代價(jià)．考慮到算法1在復(fù)雜度上的優(yōu)越性，我們保留由它確定的執(zhí)行順序，并在此基礎(chǔ)上做進(jìn)一步的優(yōu)化．

解決上述問(wèn)題的直觀想法為減少作業(yè)個(gè)數(shù)，也即增加每個(gè)作業(yè)執(zhí)行的連接操作個(gè)數(shù)．Replicated Join滿足該需求，但該算法中同一個(gè)鍵值對(duì)需要被復(fù)制到多個(gè)Reduce任務(wù)上，網(wǎng)絡(luò)代價(jià)較高．為此，本文分別計(jì)算查詢圖采用Replicated Join以及采用多個(gè)2元連接這2種執(zhí)行方法的I?O代價(jià)，定義“受益（benefit）”為二者的代價(jià)差．當(dāng)受益為正時(shí)，合并這些2元連接，如圖3所示．2元連接的I?O代價(jià)見(jiàn)式（1），下面給出Replicated Join的I?O代價(jià)計(jì)算方法．

設(shè)查詢圖G＝（V，E），關(guān)系集合V＝｛R1，R2，…，Rn｝，E關(guān)聯(lián)的連接屬性集合為E－，Ri關(guān)聯(lián)的連接屬性集合為E－i，Replicated Join的I?O代價(jià)計(jì)算見(jiàn)式（5）：

Fig．3 Optimization based on replicated join．圖3 基于Replicated Join的優(yōu)化

基于Replicated Join的優(yōu)化需要對(duì)PMC算法確定的Bushy Tree進(jìn)行遍歷，以合并所有可能的2元連接．然而，這樣做的代價(jià)很高，本文考慮到對(duì)無(wú)依賴關(guān)系的連接操作執(zhí)行Replicated Join明顯會(huì)導(dǎo)致較高的網(wǎng)絡(luò)I?O代價(jià)，因此僅判定具有依賴關(guān)系的連接操作（也即圖3（a）中只能順序執(zhí)行的子樹(shù)）．另外，如果一個(gè)順序執(zhí)行的子樹(shù)進(jìn)行Replicated Join時(shí)受益為負(fù)，那么包含該子樹(shù)的順序執(zhí)行子樹(shù)的受益也為負(fù)．通過(guò)以上方法能夠大大降低樹(shù)的遍歷代價(jià)．基于Replicated Join的優(yōu)化算法見(jiàn)算法2．

OPTB的算法復(fù)雜度小于PMC算法確定的Bushy Tree中所有最大順序執(zhí)行子樹(shù)的高度之和．又考慮到順序執(zhí)行子樹(shù)的最大高度為n－1，故OPTB的算法復(fù)雜度為O（n）．

2．3 并行執(zhí)行順序

很多關(guān)于多元連接執(zhí)行計(jì)劃的優(yōu)化研究［4－6］都只確定了連接的執(zhí)行順序，并未考慮MapReduce環(huán)境下無(wú)依賴關(guān)系的連接操作間的并行執(zhí)行策略．

若圖3（b）為2．2節(jié)中最終優(yōu)化的多元連接順序，那么連接操作R2R7，R4R8，R3R5R6之間無(wú)依賴關(guān)系，可以并行執(zhí)行．下面結(jié)合MapReduce特性對(duì)并行執(zhí)行的優(yōu)勢(shì)進(jìn)行分析．

MapReduce集群中每個(gè)節(jié)點(diǎn)最多可執(zhí)行的Map任務(wù)個(gè)數(shù)是預(yù)設(shè)的，因此最多可并行執(zhí)行的Map任務(wù)數(shù)也是確定的．對(duì)于連接運(yùn)算，Reduce Join中的Map任務(wù)負(fù)責(zé)將關(guān)系中的元組按照連接屬性值進(jìn)行分區(qū)，其執(zhí)行時(shí)間僅取決于處理數(shù)據(jù)量．又因?yàn)槊總€(gè)Map任務(wù)處理一個(gè)固定大小的分片，我們可以認(rèn)為同時(shí)分配的Map任務(wù)同時(shí)結(jié)束．設(shè)MapReduce每次最多可并行的Map任務(wù)個(gè)數(shù)為M，M個(gè)任務(wù)的并行執(zhí)行稱為一輪［2，20－21］．若每輪Map任務(wù)的執(zhí)行時(shí)間為T，作業(yè)Ji需要的Map任務(wù)個(gè)數(shù)Mi＝ai×M＋bi，其中ai，bi∈NN，bi∈［0，M），那么可以認(rèn)為Ji的執(zhí)行時(shí)間為（ai＋ bi?M ）T．若作業(yè)Jj需要的Map任務(wù)個(gè)數(shù)Mj＝aj×M＋bj，那么當(dāng)bi＋bj≤M時(shí)，2個(gè)作業(yè)的并行執(zhí)行時(shí)間為（ai＋aj＋1）T，而串行執(zhí)行時(shí)間為（ai＋aj＋2）T，此時(shí)并行執(zhí)行可節(jié)省T時(shí)間；當(dāng)bi＋bj＞M時(shí)，并行執(zhí)行時(shí)間和串行執(zhí)行時(shí)間同為（ai＋aj＋2）T．綜上，當(dāng)bi＋bj≤M時(shí)，作業(yè)Ji和Jj并行執(zhí)行的效率高于串行．

當(dāng)有多個(gè)作業(yè)滿足這一條件時(shí)，我們選取bi＋bj最大的2個(gè)作業(yè)并行執(zhí)行，從而充分利用計(jì)算資源．下面給出具體的算法實(shí)現(xiàn)：

2．4 小 結(jié)

通過(guò)2．2節(jié)和2．3節(jié)給出的優(yōu)化算法，我們最終動(dòng)態(tài)確定多元連接的執(zhí)行計(jì)劃．圖4以流程圖的方式描述了執(zhí)行計(jì)劃的優(yōu)化步驟．

Fig．4 Optimization flow of the execution plan．圖4 執(zhí)行計(jì)劃優(yōu)化流圖

給定查詢圖G，首先通過(guò)PMC算法初步確定Bushy Tree，而后分別通過(guò)算法OPTB和PEE進(jìn)行優(yōu)化，直到更新后的樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)小于3．

3 負(fù)載均衡

良好的執(zhí)行計(jì)劃固然重要，但對(duì)執(zhí)行框架的優(yōu)化同樣可以有效地提高多元連接的執(zhí)行效率，這一點(diǎn)在分布式環(huán)境中尤為重要．一種公平的并行任務(wù)負(fù)載分配方法可以有效地減少M(fèi)apReduce中的“短板效應(yīng)”，從而提高連接操作內(nèi)部的并行度．

連接運(yùn)算的MapReduce實(shí)現(xiàn)算法有很多，分別適用于不同的查詢場(chǎng)景．不失一般性，本文選擇沒(méi)有任何約束條件的Reduce Join作為連接執(zhí)行算法．該算法包括Map和Reduce 2個(gè)階段，Map階段只負(fù)責(zé)將關(guān)系中的元組按照連接屬性值進(jìn)行分區(qū)以輸出到不同的Reduce任務(wù)，運(yùn)算完全相同，因此Map任務(wù)的負(fù)載完全取決于處理數(shù)據(jù)量．又因?yàn)镸apReduce中每個(gè)Map任務(wù)只負(fù)責(zé)處理一個(gè)數(shù)據(jù)分片（split，默認(rèn)64MB），所以Map階段各個(gè)Map任務(wù)是負(fù)載均衡的．很多研究工作也都作出Map任務(wù)均衡的假設(shè)，如文獻(xiàn)［6，22］．因此，本文僅研究連接運(yùn)算的Reduce任務(wù)負(fù)載均衡．

Reduce Join算法在Reduce階段執(zhí)行連接運(yùn)算，連接屬性值的不均勻分布將會(huì)導(dǎo)致由默認(rèn)Hash分區(qū)函數(shù)確定的Reduce任務(wù)負(fù)載不均衡．為提高Reduce任務(wù)間的并行度，本節(jié)給出一種針對(duì)連接運(yùn)算的負(fù)載均衡優(yōu)化方法．

3．1 負(fù)載均衡模型

設(shè)R1和R2為參與連接的2個(gè)關(guān)系，連接屬性值的集合記為A，A在R1和R2中的頻數(shù)分布分別為F1和F2．在計(jì)算Reduce任務(wù)的負(fù)載之前，我們先給出連接屬性值a∈A的負(fù)載貢獻(xiàn)定義如下：

定義2．負(fù)載貢獻(xiàn)．連接屬性值a∈A的負(fù)載貢獻(xiàn)（LCa）是指執(zhí)行該連接操作的代價(jià)，見(jiàn)式（6）：

LCa＝ω1（f1a＋f2a）＋ω2（f1a×f2a），（6）其中，f1a和f2a分別為R1和R2中連接屬性值為a的元組個(gè)數(shù)；ω1和ω2為Reduce任務(wù)輸入數(shù)據(jù)和輸出數(shù)據(jù)的處理代價(jià)權(quán)重，輸入數(shù)據(jù)為網(wǎng)絡(luò)I?O，輸出數(shù)據(jù)寫(xiě)到HDFS上，二者的比值是由運(yùn)行多元連接的分布式集群系統(tǒng)決定的．此處，我們認(rèn)為連接運(yùn)算代價(jià)中I?O占主導(dǎo)地位，CPU處理代價(jià)可以忽略，文獻(xiàn)［5－6］中也有同樣結(jié)論．文獻(xiàn)［8］給出的當(dāng)前最好的負(fù)載均衡方法中采用的代價(jià)模型僅考慮輸入數(shù)據(jù)對(duì)Reduce任務(wù)負(fù)載的影響，而事實(shí)上對(duì)于連接運(yùn)算輸出數(shù)據(jù)的代價(jià)不容忽略．

通過(guò)對(duì)MapReduce運(yùn)行機(jī)制的分析可知，Reduce任務(wù)的負(fù)載取決于分區(qū)函數(shù)．分區(qū)函數(shù)將連接屬性值劃分成若干個(gè)組，每組對(duì)應(yīng)一個(gè)Reduce任務(wù)．設(shè)分區(qū)函數(shù)將連接屬性值的集合A劃分為A1，A2，…，AR一共R個(gè)組，那么組Ai的處理代價(jià)

第i個(gè)Reduce任務(wù)的負(fù)載Load（Ri）＝Load（Ai），Reduce任務(wù)負(fù)載均衡這一目標(biāo)可以等價(jià)表示如下：

負(fù)載均衡模型中最關(guān)鍵的是獲取連接屬性A在R1和R2中的頻數(shù)分布F1和F2．獲取這2個(gè)分布，最精確的方法是對(duì)不同鍵值進(jìn)行頻數(shù)統(tǒng)計(jì)［23］，但當(dāng)鍵值個(gè)數(shù)很多時(shí)，會(huì)耗費(fèi)大量存儲(chǔ)，且在匯總各個(gè)Map任務(wù)的統(tǒng)計(jì)信息時(shí)還會(huì)帶來(lái)很高的網(wǎng)絡(luò)傳輸代價(jià)．針對(duì)該問(wèn)題，文獻(xiàn)［5，7－9］對(duì)鍵值進(jìn)行Hash從而降低統(tǒng)計(jì)信息的規(guī)模．然而，文獻(xiàn)［9］在Map任務(wù)執(zhí)行的同時(shí)對(duì)頻數(shù)信息進(jìn)行統(tǒng)計(jì)，這樣會(huì)導(dǎo)致第2輪Map任務(wù)無(wú)法執(zhí)行，還會(huì)造成數(shù)據(jù)到Reduce的傳輸延遲，因?yàn)楸仨毜鹊礁鶕?jù)頻數(shù)信息確定Partition函數(shù)后才能進(jìn)行傳輸．文獻(xiàn)［5，7－8］則單獨(dú)開(kāi)啟一個(gè)作業(yè)進(jìn)行頻數(shù)統(tǒng)計(jì)，避免了上述問(wèn)題．基于以上分析，本文可以采用類似的方法獲取連接屬性值的頻數(shù)信息，并據(jù)此確定Reduce任務(wù)的個(gè)數(shù)以及Partition函數(shù)．

3．2 負(fù)載均衡算法

文獻(xiàn)［6］指出Reduce任務(wù)的負(fù)載均衡是一個(gè)NP難問(wèn)題，不能夠在多項(xiàng)式時(shí)間內(nèi)獲取最優(yōu)解，因此我們僅專注于尋找盡可能接近最優(yōu)解的近似解．由于連接屬性值的不可分割性，擁有相同連接屬性值的鍵值對(duì)必須發(fā)送到同一Reduce任務(wù)節(jié)點(diǎn)進(jìn)行連接運(yùn)算，Reduce任務(wù)的負(fù)載均衡問(wèn)題可以轉(zhuǎn)換成盡可能降低Reduce任務(wù)的最大負(fù)載max｛Load（Ri）｝．

理想情況下，所有Reduce任務(wù)的負(fù)載完全相同，此時(shí)max｛Load（Ri）｝＝Avg｛Load（Ri）｝．然而，這種情況不總發(fā)生，本文給出一種樸素的均衡算法來(lái)獲取近似解．該算法首先對(duì)A中所有連接屬性值的負(fù)載貢獻(xiàn)值按降序排序，然后每次將連接屬性值為a的鍵值對(duì)分配給當(dāng)前負(fù)載最小的Reduce任務(wù)（詳見(jiàn)算法4）．

為評(píng)估算法4，我們將由該算法獲取的Reduce任務(wù)負(fù)載最大值Lmax與最優(yōu)算法獲取的最大值L＊max進(jìn)行對(duì)比，并得出Lmax的上界如下：Lmax≤1．5L＊max．

本文給出的負(fù)載均衡方法是以等值連接為例進(jìn)行描述的，它還適用于其他連接，也可以擴(kuò)展到連接以外的其他類型作業(yè)．例如，進(jìn)行近似連接時(shí)，只需將連接屬性值a（鍵值對(duì)中的鍵）替換為一個(gè)滿足近似條件（如｜a1－a2｜≤δ）的2元組?a1，a2?，并將負(fù)載貢獻(xiàn)值的計(jì)算公式中f1a和f2a分別替換為R1中連接屬性值為a1的元組個(gè)數(shù)以及R2中連接屬性值為a2的元組個(gè)數(shù)．執(zhí)行Replicated Join時(shí)，鍵值對(duì)中的鍵將會(huì)變成多個(gè)連接屬性構(gòu)成的多元組．對(duì)于連接以外的其他作業(yè)，我們可以將Reduce任務(wù)輸入數(shù)據(jù)的處理代價(jià)函數(shù)（頻數(shù)的加和）以及輸出數(shù)據(jù)的處理代價(jià)函數(shù)（頻數(shù)的乘積）進(jìn)行適應(yīng)性的更改．

3．3 Reduce任務(wù)個(gè)數(shù)的確定

現(xiàn)有通用的Reduce端負(fù)載均衡的方法［7－9］均未考慮Reduce任務(wù)個(gè)數(shù)的確定方法，本文根據(jù)獲取的鍵值頻數(shù)統(tǒng)計(jì)信息給出一種簡(jiǎn)單的確定規(guī)則．

設(shè)Map任務(wù)的輸出中不同鍵值的個(gè)數(shù)為k，所有鍵值的負(fù)載貢獻(xiàn)和為Sum，其中鍵值的最大負(fù)載貢獻(xiàn)為L(zhǎng)Cmax，Reduce任務(wù)個(gè)數(shù)為R，通過(guò)優(yōu)化算法獲取的Reduce任務(wù)最大負(fù)載為L(zhǎng)max．當(dāng)LCmax≥Sum?R時(shí)，也即R≥Sum?LCmax時(shí)，Lmax的取值不再下降，始終為L(zhǎng)Cmax，這意味著作業(yè)的性能不再提高，而它的資源消耗卻隨著R的增加而增大．因此，有必要找到R的一個(gè)臨界值使得連接的執(zhí)行效率最高．另外，考慮到Lmax的取值還與Sum有關(guān)，本文給出均衡算法的度量函數(shù)g（Lmax，R）的表達(dá)式如下：

其中，α是性能與能耗之間的權(quán)重比，度量值越小，均衡效果越好．函數(shù)g（Lmax，R）應(yīng)該存在一個(gè)極小值點(diǎn)R0，使得在該點(diǎn)處性能與資源消耗達(dá)到一個(gè)很好的折中，且該值有可能比Sum?LCmax?。?．2節(jié)中通過(guò)大量實(shí)驗(yàn)得出，當(dāng)α＝0．05時(shí)，函數(shù)g（Lmax，R）的極小值點(diǎn)正好就是Lmax不再下降的臨界值．

另外，考慮到不同鍵值的個(gè)數(shù)可能會(huì)很大，這將導(dǎo)致頻數(shù)統(tǒng)計(jì)信息不能存入內(nèi)存，針對(duì)該問(wèn)題，我們可以采用文獻(xiàn)［8］中提出的optimal sketch packing算法，該方法通過(guò)Hash函數(shù)將鍵值（這里是負(fù)載貢獻(xiàn)值）進(jìn)行哈希后再進(jìn)行均衡分配，從而降低鍵的規(guī)模，節(jié)省統(tǒng)計(jì)信息占用的內(nèi)存．本質(zhì)上，該方法是犧牲精確度來(lái)降低統(tǒng)計(jì)信息的存儲(chǔ)空間．

4 實(shí)驗(yàn)與范例分析

本節(jié)設(shè)計(jì)實(shí)驗(yàn)對(duì)提出的連接執(zhí)行計(jì)劃優(yōu)化方法以及連接負(fù)載均衡方法進(jìn)行驗(yàn)證和分析．其中，4．1節(jié)中的實(shí)驗(yàn)是依托圖1中給出的查詢圖生成的虛擬數(shù)據(jù)表進(jìn)行多元連接查詢?cè)O(shè)計(jì)的，該實(shí)驗(yàn)?zāi)軌蚝芎玫仳?yàn)證本文提出的執(zhí)行計(jì)劃的優(yōu)化效果；4．2節(jié)中的實(shí)驗(yàn)則是依托TPC－H數(shù)據(jù)集中提供的邏輯數(shù)據(jù)表進(jìn)行設(shè)計(jì)的，本文通過(guò)控制其數(shù)據(jù)的生成方式來(lái)設(shè)計(jì)實(shí)驗(yàn)以驗(yàn)證文中提出的連接負(fù)載均衡方法．實(shí)驗(yàn)的具體設(shè)置在4．1節(jié)和4．2節(jié)中均有對(duì)應(yīng)的詳細(xì)描述．

4．1 執(zhí)行計(jì)劃的優(yōu)化效果分析

以圖1中查詢圖為例對(duì)本文提出的執(zhí)行計(jì)劃優(yōu)化方法進(jìn)行效果分析，相應(yīng)的特征參數(shù)見(jiàn)表1和表2．

Table 1 Cardinalities of the Relations in Fig．1（a）表1 圖1（a）對(duì)應(yīng)的關(guān)系特征參數(shù)

Table 2 Cardinalities of the Relations in Fig．1（b）表2 圖1（b）對(duì)應(yīng)的關(guān)系特征參數(shù)

首先，為了驗(yàn)證本文提出的連接順序確定PMC算法的優(yōu)化效果，本文將其與最優(yōu)解（可用分支限定法獲?。┻M(jìn)行對(duì)比．圖5中，POPT代表最優(yōu)解，從圖5可以看出PMC的代價(jià)比最優(yōu)解稍高，二者的比值分別為1．003和1．034．由此可見(jiàn)，PMC算法能夠確定一個(gè)很好的連接順序，從而降低連接的I?O代價(jià)．

接著，我們分析了2種查詢圖下算法OPTB和PEE的優(yōu)化效果．從表3可以看出，OPTB算法能夠找出可以合并為多元連接的2元連接，一定程度上降低了I?O代價(jià)；PEE算法能夠找出最大限度使用集群計(jì)算資源的可并行連接操作，從而節(jié)省多元連接的整體運(yùn)行時(shí)間．

Fig．5 I?O cost comparison of PMCand POPT．圖5 PMC算法與POPT的I?O代價(jià)對(duì)比

Table 3 Optimization Results of Algorithms OPTBand PEE表3 算法OPTB和PEE的優(yōu)化效果

4．2 負(fù)載均衡方法驗(yàn)證

文獻(xiàn)［5，7－9］中均提到采用模擬實(shí)驗(yàn)驗(yàn)證其提出的負(fù)載均衡方法，假設(shè)鍵值服從Zipf分布．不失一般性，本文也采用該方法來(lái)驗(yàn)證第3節(jié)中針對(duì)連接運(yùn)算設(shè)計(jì)的負(fù)載均衡方法．以等值2元連接為例，假設(shè)參與連接的2個(gè)關(guān)系表R1和R2服從相同的Zipf分布，數(shù)據(jù)條數(shù)分別為｜R1｜和｜R2｜，不同連接屬性值的個(gè)數(shù)為k，則R1和R2中第i個(gè)最頻繁出現(xiàn)的連接屬性值的出現(xiàn)概率pi＝1?（iz×Hk），其中z代表數(shù)據(jù)的傾斜度，Hk是調(diào)和系數(shù)，那么第i個(gè)連接屬性值的負(fù)載貢獻(xiàn)值計(jì)算如下：

依托TPC－H數(shù)據(jù)集中提供的邏輯數(shù)據(jù)表，我們?cè)O(shè)計(jì)具體的測(cè)試用例為：｜R1｜＝109，｜R2｜＝2×109，k＝3×104，3×105，3×106，z的取值范圍為［0，1］．這里需要指出的是，z僅代表關(guān)系R1和R2中連接屬性值的傾斜程度，并不代表負(fù)載貢獻(xiàn)值集合的傾斜度（記為δ），但δ與z值是成正相關(guān)的，且比z大．

首先，我們對(duì)比不同因素下負(fù)載均衡算法的效果，采用IR（imbalance ratio）來(lái)度量，它是所有Reduce任務(wù)中的最大負(fù)載（Lmax）與平均負(fù)載（Avg＝Sum?R）之間的比值．從圖6可以看出，IR的影響因素有δ（受z影響），k和R，與δ和R成正相關(guān)，與k成負(fù)相關(guān)．從圖6我們還可以看出，IR的值早在z＝0．5，R＝64時(shí)已經(jīng)超過(guò)1．5，這是因?yàn)镮R是Lmax與Avg之間的比值，而通過(guò)最優(yōu)負(fù)載均衡算法獲取的L＊max通常會(huì)因?yàn)棣妮^大而遠(yuǎn)大于Avg．例如，當(dāng)一個(gè)鍵的頻數(shù)占總頻數(shù)的80%時(shí)，因?yàn)殒I的不可分割性，Lmax和L＊max會(huì)遠(yuǎn)大于Avg．

其次，為了驗(yàn)證本文設(shè)計(jì)的負(fù)載均衡算法的有效性，我們將其得到的最大負(fù)載值與默認(rèn)Hash函數(shù)得到的最大負(fù)載值進(jìn)行對(duì)比．從圖7可以看出，在3種傾斜度、3種Reduce個(gè)數(shù)下，我們的算法均比默認(rèn)Hash的好．從圖7（a）可以看出，隨著Reduce個(gè)數(shù)的增加，負(fù)載均衡算法的優(yōu)勢(shì)越來(lái)越明顯；而在圖7（b）和圖7（c）中，Reduce個(gè)數(shù)為100和1 000時(shí)，均衡算法得到的最大負(fù)載值均未發(fā)生變化，這是因?yàn)榇藭r(shí)數(shù)據(jù)太過(guò)傾斜而產(chǎn)生了“二八現(xiàn)象”，圖7（b）和圖7（c）對(duì)應(yīng)的最大負(fù)載值分別在Reduce個(gè)數(shù)大于95以及16后不再發(fā)生變化（從圖8中可以看出），這也驗(yàn)證了我們?cè)?．3節(jié)中的理論分析．另外，在圖7（b）和圖7（c）中，雖然默認(rèn)Hash得到的最大負(fù)載值依然隨著Reduce個(gè)數(shù)的增加而降低，但該值由于數(shù)據(jù)傾斜以及鍵值不可分割等原因而不會(huì)低于均衡算法得到的值．

最后，為了驗(yàn)證3．3節(jié)中提出的Reduce任務(wù)個(gè)數(shù)的確定方法，我們分析了正規(guī)化后的最大負(fù)載Lmax與負(fù)載均衡算法的評(píng)估函數(shù)g（Lmax，R）隨Reduce任務(wù)個(gè)數(shù)R的變化情況．通過(guò)大量實(shí)驗(yàn)，我們發(fā)現(xiàn)當(dāng)函數(shù)g（Lmax，R）中的α＝0．05時(shí)，它的極小值點(diǎn)正好就是Lmax不再下降的臨界值R0．另外，在實(shí)驗(yàn)過(guò)程中，我們發(fā)現(xiàn)z值越大，臨界值R0的下降趨勢(shì)越不明顯，因此，為直觀起見(jiàn)，本文選取了其中5個(gè)具有代表性的z值進(jìn)行展示．從圖8（a）可以看出，隨著R的增長(zhǎng)，Lmax不斷減小，最終趨向平穩(wěn)值，圖中5個(gè)z值對(duì)應(yīng)的臨界R值分別為974，95，16，6，4，這與我們通過(guò)均衡算法度量函數(shù)g（Lmax，R）得到的極小值點(diǎn)是完全吻合的（見(jiàn)圖8（b））．

Fig．6 Imbalance ratios of the load balancing algorithm under different skew degrees．圖6 不同傾斜度下負(fù)載均衡算法的IR比較

Fig．7 Max load comparison between the load balancing algorithm and the default Hash under 3million keys．圖7 k＝3×106時(shí)不同傾斜度下負(fù)載均衡算法與默認(rèn)Hash的最大負(fù)載對(duì)比

Fig．8 Relationships between the formalized Lmax，g（Lmax，R）and Runder 3million keys．圖8 k＝3×106時(shí)正規(guī)化的最大負(fù)載Lmax以及函數(shù)g（Lmax，R）隨R的變化曲線

5 總 結(jié)

本文基于MapReduce研究多元連接的優(yōu)化方法，主要從以下2部分展開(kāi)研究：連接的執(zhí)行計(jì)劃和連接的負(fù)載均衡．

針對(duì)前者，本文首先分析現(xiàn)有主流的查詢樹(shù)模型，確定適合本文研究環(huán)境的Bushy Tree；隨后通過(guò)白盒分析給出MapReduce連接算法的I?O代價(jià)模型，并選擇I?O代價(jià)最小的連接順序作為初步的執(zhí)行計(jì)劃；接著對(duì)執(zhí)行計(jì)劃做進(jìn)一步的優(yōu)化，根據(jù)是否受益將查詢樹(shù)中的2元連接合并成Replicated Join，以降低多個(gè)作業(yè)引起的中間結(jié)果代價(jià)；最后結(jié)合MapReduce特性提出一種作業(yè)并行執(zhí)行算法，以提高集群資源的使用率．

針對(duì)后者，本文首先分析連接運(yùn)算的特性，給出連接負(fù)載的定義以及負(fù)載均衡目標(biāo)；接著給出具體的均衡算法，并證明該算法的上界；最后在實(shí)驗(yàn)中分析Reduce任務(wù)個(gè)數(shù)的確定與性能之間的關(guān)系．

實(shí)驗(yàn)證明，本文提出的連接執(zhí)行計(jì)劃以及負(fù)載均衡的優(yōu)化算法是有效的．本研究對(duì)大數(shù)據(jù)環(huán)境下MapReduce多元連接的應(yīng)用具有指導(dǎo)意義，可以優(yōu)化如OLAP分析中的星型連接，社交網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)的鏈?zhǔn)竭B接等應(yīng)用的性能．

［1］Han Xixian，Yang Donghua，Li Jianzhong．Approximate join aggregate on massive data［J］．Chinese Journal of Computers，2010，33（10）：1919 1933（in Chinese）（韓希先，楊東華，李建中．海量數(shù)據(jù)上的近似連接聚集操作［J］．計(jì)算機(jī)學(xué)報(bào)，2010，33（10）：1919 1933）

［2］Dean J，Ghemawat S．MapReduce：Simplified data processing on large clusters［J］．Communications of the ACM，2008，51（1）：107 113

［3］Doulkeridis C，Norvag K．A survey of large－scale analytical query processing in MapReduce［J］．The VLDB Journal，2013，23（3）：355 380

［4］Chen M S，Yu P S，Wu K．Optimization of parallel execution for multi－join queries［J］．IEEE Trans on Knowledge and Data Engineering，1996，8（3）：416 428

［5］Wu S，Li F，Mehrotra S，et al．Query optimization for massively parallel data processing［C］??Proc of the 2nd ACM Symp on Cloud Computing．New York：ACM，2011：1 13

［6］Zhang X F，Chen L，Wang M．Efficient multi－way theta－join processing using MapReduce［J］．Proceedings of the VLDB Endowment，2012，5（11）：1184 1195

［7］Gufler B，Augsten N，Reiser A，et al．Load balancing in MapReduce based on scalable cardinality estimates［C］??Proc of the Int Conf on Data Engineering．Piscataway，NJ：IEEE，2012：522 533

［8］Yan W，Xue Y，Malin B．Scalable and robust key group size estimation for reducer load balancing in MapReduce［C］?? Proc of the IEEE Int Conf on Big Data．Piscataway，NJ：IEEE，2013：156 162

［9］Gufler B，Augsten N，Reiser A，et al．Handling data skew in MapReduce［C］??Proc of the 1st Int Conf on Cloud Computing and Services Science．Boca Raton，F(xiàn)lorida：CRC Press，2011：574 583

［10］Zhou M Q，Zhang R，Zeng D D，et al．Join optimization in the MapReduce environment for column－wise data store［C］??Proc of the 6th Int Conf on Semantics Knowledge and Grid．Piscataway，NJ：IEEE，2010：97 104

［11］Afrati F N，Ullman J D．Optimizing multiway joins in a Map－Reduce environment［J］．IEEE Trans on Knowledge and Data Engineering，2011，23（9）：1282 1298

［12］Okcan A，Riedewald M．Processing theta－joins using MapReduce［C］??Proc of the ACM SIGMOD Int Conf on Management of Data Athens．New York：ACM，2011：949 960

［13］Koumarelas I K，Naskos A，Gounaris A．Binary theta－joins using MapReduce：Efficiency analysis and improvements［C］??Proc of the Workshops of the EDBT ICDT 2014Joint Conf．Boca Raton，F(xiàn)lorida：CRC Press，2014：6 9

［14］Blanas S，Patel J M，Ercegovac V，et al．A comparison of join algorithms for log processing in MapReduce［C］??Proc of the ACM SIGMOD Int Conf on Management of Data．New York：ACM，2010：975 986

［15］Luo G，Dong L．Adaptive join plan generation in Hadoop，NC27705［R］．Durham，NC：Duke University，2010

［16］Yang H，Dasdan A，Hsiao R，et al．Map－reduce－merge：Simplified relational data processing on large clusters［C］?? Proc of the ACM SIGMOD Int Conf on Management of Data．New York：ACM，2007：1029 1040

［17］Condie T，Conway N，Alvaro P，et al．Online aggregation and continuous query support in MapReduce［C］??Proc of the ACM SIGMOD Int Conf on Management of Data．New York：ACM，2010：1115 1118

［18］Ding Youwei，Qin Xiaolin，Liu Liang，et al．An energy efficient algorithm for big data processing in heterogeneous cluster［J］．Journal of Computer Research and Development，2015，52（2）：377 390（in Chinese）（丁有偉，秦小麟，劉亮，等．一種異構(gòu)集群中能量高效的大數(shù)據(jù)處理算法［J］．計(jì)算機(jī)研究與發(fā)展，2015，52（2）：377 390）

［19］Aljanaby A，Abuelrub E，Odeh M．A survey of distributed query optimization［J］．Int Arab Journal of Information Technology，2005，2（1）：48 57

［20］Agrawal P，Kifer D，Olston C．Scheduling shared scans of large data files［J］．Proceedings of the VLDB Endowment，2008，1（1）：958 969

［21］Li F，Ooi B C，Ozsu M T，et al．Distributed data management using MapReduce［J］．ACM Computing Surveys，2014，46（3）：31：1 42

［22］Nykiel T，Potamias M，Mishra C，et al．MRShare：Sharing across multiple queries in MapReduce［J］．Proceedings of the VLDB Endowment，2010，3（1）：494 505

［23］Ibrahim S，Jin H，Lu L，et al．LEEN：Locality?fairnessaware key partitioning for MapReduce in the cloud［C］??Proc of the 2nd IEEE Int Conf on Cloud Computing Technology and Science．Piscataway，NJ：IEEE，2010：17 24 Li Tiantian，born in 1989．PhD candidate．Student member of China Computer Federation．Her main research interests include energy efficient computing，and data intensive computing．

Yu Ge，born in 1962．Professor and PhD supervisor in Northeastern University．His main research interests include database theory and data flow．

Guo Chaopeng，born in 1990．Master．His main research interests include iterative computing，and data intensive computing．

Song Jie，born in 1980．PhD and associate professor in Northeastern University．His main research interests include cloud computing，data intensive computing and big data．

Multi－Way Join Optimization Approach Based on MapReduce

Li Tiantian1，Yu Ge1，Guo Chaopeng2，and Song Jie21（College of Computer Science and Engineering，Northeastern University，Shenyang110819）2（Software College，Northeastern University，Shenyang110819）

Multi－way join is one of the most common data analysis operations，and MapReduce programming model that has been widely used to process large scale data sets has brought new challenges to multi－way join optimization．Traditional optimization approaches cannot be simply adapted to fit MapReduce feature，so there is still optimization room for MapReduce join algorithm．As to the former，we think I?O is the main cost of join．This paper first proposes an I?O cost based heuristic algorithm to initially determine a join sequence，and conducts further optimization．After the optimization，we also design a parallel execution algorithm to improve the whole performance of multiway join．As to the latter，we think load balancing can effectively decrease the“buckets effect”of MapReduce．This paper proposes a fair task load allocation algorithm to improve the intra－join parallelism，and also analyzes the method to decide the appropriate number of Reduce tasks．Experiments verify the effectiveness of the proposed optimization approaches．This study contributes to multi－way join applications in big data environment，such as the star－join in OLAP and the chainjoin in social network．

multi－way join；execution plan；I?O cost；performance optimization；MapReduce programming model；load balancing

TP393

2014－11－24；

2015－03－04

國(guó)家自然科學(xué)基金重大項(xiàng)目（61433008）；國(guó)家自然科學(xué)基金青年基金項(xiàng)目（61202088）；國(guó)家博士后科學(xué)基金面上項(xiàng)目（2013M540232）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金項(xiàng)目（N120817001）；教育部高等學(xué)校博士學(xué)科點(diǎn)博導(dǎo)基金項(xiàng)目（20120042110028）

This work was supported by the Major Program of the National Natural Science Foundation of China（61433008），the National Natural Science Foundation for Young Scholars（61202088），the Science Foundation of China for Post－doctor（2013M540232），the Fundamental Research Funds for the Central Universities（N120817001），and the PhD Programs Foundation of Ministry of Education of China（20120042110028）．