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

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

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

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

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