Map--reduce環(huán)境下多連接查詢優(yōu)化的研究.pdf

1、隨著社會(huì)的發(fā)展和數(shù)據(jù)產(chǎn)生成本的下降，人類(lèi)產(chǎn)生的數(shù)據(jù)量正在呈指數(shù)級(jí)增長(zhǎng)，所以海量數(shù)據(jù)的分析逐漸被人們所關(guān)注。分布式計(jì)算被越來(lái)越廣泛地應(yīng)用到海量數(shù)據(jù)分析上，因?yàn)榧惺降臄?shù)據(jù)倉(cāng)庫(kù)在面對(duì)爆炸式增長(zhǎng)的數(shù)據(jù)時(shí)不能提供較好的可擴(kuò)展性，而利用分布式計(jì)算可以將一個(gè)任務(wù)分配到多個(gè)節(jié)點(diǎn)上并行執(zhí)行，從而獲得更好的執(zhí)行效果。而google提出的map-reduce框架則為分布式計(jì)算提供了很好的框架，它是業(yè)界廣泛認(rèn)可的解決海量數(shù)據(jù)分析的有效工具。在map-redu

2、ce上執(zhí)行多表連接的方法主要有兩種，分別是層疊法和復(fù)制哈希法。但這兩種方法都有各自的缺點(diǎn)，它們?cè)谀承┣闆r下的效率會(huì)比較差。
　　通過(guò)研究，本文提出一種將層疊法和復(fù)制哈希法相結(jié)合的方法(CRMJ)。在執(zhí)行多連接的過(guò)程中，會(huì)對(duì)一些連接采用復(fù)制哈希法，而對(duì)另外一些連接采用層疊法，這樣會(huì)取得比這兩種方法都好的效果。
　　采用這種方法會(huì)產(chǎn)生很多種執(zhí)行計(jì)劃，從而需要判斷哪種執(zhí)行計(jì)劃所需執(zhí)行代價(jià)最低，所以本文提出了兩種尋優(yōu)算法以找到最優(yōu)執(zhí)

3、行計(jì)劃。第一種是窮舉法尋優(yōu)算法。該算法使用連接圖劃分和遞歸思想近似遍歷所有可能的執(zhí)行計(jì)劃，找到最優(yōu)的執(zhí)行計(jì)劃，并進(jìn)一步通過(guò)剪枝縮減搜索空間。但該種方法通過(guò)減枝進(jìn)行優(yōu)化所消耗的時(shí)間會(huì)隨著連接表個(gè)數(shù)的增加而急劇增加，導(dǎo)致算法復(fù)雜度很高。第二種是基于貪婪的尋優(yōu)算法。該算法在多連接的層疊法最優(yōu)執(zhí)行計(jì)劃的基礎(chǔ)上，尋找代價(jià)節(jié)省最多的復(fù)制哈希連接。應(yīng)用該算法可以在較低的復(fù)雜度下找到近似最優(yōu)的執(zhí)行計(jì)劃。
　　經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，本文提出的CRMJ連接方