多核環(huán)境下的Hash join算法設(shè)計與實現(xiàn).pdf

1、Hash join算法作為數(shù)據(jù)庫領(lǐng)域中典型的連接算法，在現(xiàn)實生活中具有重要的地位和廣泛的應(yīng)用。由于數(shù)據(jù)庫規(guī)模擴展的越來越大，傳統(tǒng)的Hash join串行算法已經(jīng)無法實現(xiàn)在現(xiàn)實生活中遇到的很多問題，所以想辦法提高Hash join的算法性能就變得極為重要。目前對Hash join算法的改進有很多，有的是基于傳統(tǒng)的串行算法進行改進，有的是利用分布式或集群等并行體系結(jié)構(gòu)進行改進，雖然這些改進都能夠使性能得到優(yōu)化，但對于串行算法的研究已出現(xiàn)了瓶

2、頸，并且分布式或集群并行體系結(jié)構(gòu)其自身對算法也有很大的限制，這是由于這些模型的組織結(jié)構(gòu)比較分散，成本又非常高，在利用它們的同時也會增大它們的功能消耗和通信的開銷，這樣提出新的改進算法就變得更加重要?，F(xiàn)代多核處理器(CMP)具有很強大的并行處理能力，運算速度較快，利用CMP處理器來進行運算已經(jīng)成為當(dāng)前并行計算領(lǐng)域的研究熱點。
　　因此，本文的主要研究內(nèi)容是優(yōu)化Hash join算法，并在CMP處理器上實現(xiàn)多表的Hash join算法

3、。主要針對以下兩方面對算法進行改進:
　　一方面，是對兩張關(guān)系表的連接進行優(yōu)化。是把原有的Hash filter和本文提出的Search filter結(jié)合使用。使用這兩個過濾器的好處是過濾掉部分不匹配的元組，加快查找時間。并在多線程之間并行執(zhí)行這些過濾器，加快了查找具有相同屬性元組的速率，極大地提高了Hash join算法的執(zhí)行效率。提高的效率在50％以上，符合預(yù)期。
　　另一方面，是在CMP處理器上實現(xiàn)多表的Hash jo

4、in算法，在線程的分配方面對算法進行優(yōu)化。本文通過使用濃密樹(bushy-tree)的結(jié)構(gòu)對連接中的多重關(guān)系進行分配，樹中的每個葉子節(jié)點代表了一個關(guān)系表。然后把bushy-tree轉(zhuǎn)化成分配樹(allocation-tree)的形式來執(zhí)行，通過給allocation-tree的各個節(jié)點分配線程代替給濃密樹的各個節(jié)點分配線程，這樣的分配好處是節(jié)約線程、關(guān)系之間不存在依賴性可并行處理、能夠開啟多個線程同時執(zhí)行，可以減少多表之間的連接時間，實