多核CPU上數(shù)據(jù)庫散列連接算法的研究與實(shí)現(xiàn).pdf

1、近年來，隨著多核 CPU硬件體系結(jié)構(gòu)的普及與 SMT同步多線程技術(shù)的發(fā)展和成熟，多核CPU以其強(qiáng)大的并行計(jì)算能力越來越成為研究領(lǐng)域中的熱點(diǎn)。人們已經(jīng)開始研究使用多核CPU對(duì)多種數(shù)據(jù)操作進(jìn)行并行加速，其中在數(shù)據(jù)庫操作中最常用、最耗時(shí)的連接操作成為人們研究的重點(diǎn)。
　　在關(guān)系型數(shù)據(jù)庫中，連接操作是實(shí)現(xiàn)關(guān)系型數(shù)據(jù)庫中查詢的重要操作之一，它通過對(duì)兩個(gè)關(guān)系做笛卡爾積運(yùn)算實(shí)現(xiàn)對(duì)這兩個(gè)關(guān)系的信息檢索。連接操作是唯一能從不同的關(guān)系之間組合出新的關(guān)

2、系元組的關(guān)系代數(shù)操作，同時(shí)也是最難找出高效實(shí)現(xiàn)方法的操作之一，因?yàn)椴荒茴A(yù)先確定哪些關(guān)系之間的連接是需要存在的，而且這還會(huì)和網(wǎng)絡(luò)及分布式系統(tǒng)有關(guān)，因?yàn)榭赡懿皇撬械年P(guān)系表都是存放在一起的。由此可見，連接操作的代價(jià)高低與數(shù)據(jù)庫的性能優(yōu)劣息息相關(guān)?；镜臄?shù)據(jù)庫連接操作實(shí)現(xiàn)算法主要有：嵌套循環(huán)連接，排序合并連接和散列連接等，其中散列連接算法以及優(yōu)異的性能而被廣泛地應(yīng)用于數(shù)據(jù)庫管理系統(tǒng)。
　　多核并行技術(shù)的發(fā)展使得這些連接算法的許多變種被提

3、出。它們充分利用多核并行技術(shù)和最新的硬件體系結(jié)構(gòu)來獲得更好的性能。這些研究表明，硬件體系結(jié)構(gòu)對(duì)連接算法的性能有很大的影響。此外，內(nèi)存訪問也是制約連接算法性能的另一個(gè)重要影響因素。本文對(duì)幾種數(shù)據(jù)庫連接操作實(shí)現(xiàn)算法進(jìn)行了系統(tǒng)的研究，重點(diǎn)關(guān)注散列連接算法，結(jié)合多核CPU硬件結(jié)構(gòu)和內(nèi)存局部性原理提出了對(duì)應(yīng)的并行連接優(yōu)化算法，所取得的主要研究成果為：
　　1、針對(duì)多核CPU平臺(tái)提出了一種基于MapReduce模型的并行散列連接算法。通過Ma

4、pReduce模型實(shí)現(xiàn)自動(dòng)化的線程調(diào)度、任務(wù)分配管理、負(fù)載均衡控制和錯(cuò)誤糾正功能，結(jié)合利用內(nèi)存局部性原理提出的任務(wù)劃分策略，增加了內(nèi)存的命中率，提高了內(nèi)存的頁面替換效率，從而進(jìn)一步優(yōu)化了散列連接操作的性能。
　　2、針對(duì)內(nèi)存延遲、數(shù)據(jù)偏移和內(nèi)存壓力造成的性能瓶頸問題提出了三種優(yōu)化策略，實(shí)驗(yàn)結(jié)果表明，這三種策略取得了預(yù)期的效果，較好地解決了存在的問題。
　　實(shí)驗(yàn)結(jié)果表明本文實(shí)現(xiàn)的并行散列連接算法，在多核CPU硬件結(jié)構(gòu)上比傳統(tǒng)的