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

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

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

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

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