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

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

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

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