多核處理器中并行自適應(yīng)索引算法優(yōu)化

袁 通,劉志鏡,劉 慧

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

多核處理器中并行自適應(yīng)索引算法優(yōu)化

袁 通,劉志鏡,劉 慧

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

針對(duì)現(xiàn)有的多核并行自適應(yīng)索引算法不能高效地利用多核處理器的并行資源,且不能較好處理順序查詢的問(wèn)題,提出了一種改進(jìn)的多核并行自適應(yīng)索引算法.該算法在優(yōu)化現(xiàn)有Refined Partition Merge算法的基礎(chǔ)上,將加鎖并行方法與Refined Partition Merge算法相結(jié)合,在索引中數(shù)據(jù)塊較少時(shí),使用優(yōu)化的Refined Partition Merge算法,降低線程之間沖突的概率,減少線程等待時(shí)間,提高線程利用率.當(dāng)索引中數(shù)據(jù)塊較多時(shí),使用加鎖并行方法,充分利用了多核處理器的并行資源.除此之外,還提出了一種提升自適應(yīng)索引魯棒性的優(yōu)化方法,使多核并行自適應(yīng)索引算法能夠適應(yīng)兩種常用查詢樣式.實(shí)驗(yàn)結(jié)果表明,該算法使多核并行自適應(yīng)索引在查詢時(shí)間上明顯降低,使查詢速度提升25.7%～33.2%,并且能夠適應(yīng)多種常用查詢樣式.

自適應(yīng)索引;多核處理器;Database Cracking算法;數(shù)據(jù)庫(kù)系統(tǒng)

隨著海量數(shù)據(jù)時(shí)代的到來(lái),系統(tǒng)數(shù)據(jù)庫(kù)的規(guī)模越來(lái)越大,如何快速檢索數(shù)據(jù)成為數(shù)據(jù)庫(kù)領(lǐng)域一個(gè)重要的課題.索引技術(shù)可以大幅提高檢索數(shù)據(jù)的效率,常用的索引包括:平衡二叉樹、B+樹索引、哈希索引[1]、ART樹索引[2]等.但這些索引技術(shù)有以下缺點(diǎn):索引需要在查詢之前創(chuàng)建完成,這個(gè)過(guò)程消耗大量的時(shí)間和空間;索引需要涵蓋表中的所有行,即使其中的一些行極少的被查詢.

自適應(yīng)索引技術(shù)[3]自提出以來(lái),受到了廣泛的關(guān)注[4-8],較好地解決了傳統(tǒng)索引的缺點(diǎn).與傳統(tǒng)的索引不同,自適應(yīng)索引的核心思想是根據(jù)查詢條件動(dòng)態(tài)地、自適應(yīng)地建立和優(yōu)化索引結(jié)構(gòu),索引的建立是查詢?nèi)蝿?wù)的一個(gè)部分.該技術(shù)對(duì)表中經(jīng)常查詢到的行會(huì)建立更好的索引,對(duì)那些沒(méi)有被查詢到的行不會(huì)建立索引.

當(dāng)今的中央處理器(Central Processing Unit,CPU)擁有更多的核心,每個(gè)核心擁有更多的線程.IBM推出了新一代的POWER 8處理器,支持12核心96線程,共享96 MB的三級(jí)緩存,這說(shuō)明多核CPU具有廣闊的應(yīng)用前景.但目前對(duì)于多核并行自適應(yīng)索引技術(shù)的研究還不是很多,僅有的一些研究成果[4-5]也存在一定的不足.文獻(xiàn)[4]提出用加鎖的方式避免線程之間的沖突,實(shí)現(xiàn)并行索引,然而頻繁的加鎖和解鎖操作耗費(fèi)了大量的時(shí)間.文獻(xiàn)[5]提出了Partition Merge算法,在該算法中所有線程每次共同處理一個(gè)查詢?nèi)蝿?wù).該算法雖然避免了頻繁的加鎖解鎖操作,但當(dāng)所有線程共同處理一個(gè)較小的查詢?nèi)蝿?wù)時(shí),不能高效利用處理器并行資源,容易造成資源浪費(fèi).

針對(duì)上述問(wèn)題,筆者提出了一種改進(jìn)的多核并行自適應(yīng)索引算法,該算法在優(yōu)化傳統(tǒng)并行自適應(yīng)索引的基礎(chǔ)上,將加鎖并行方法與優(yōu)化的Refined Partition Merge算法相結(jié)合,充分利用了多核處理器的并行資源,取得良好的效果.除此之外,文中提出的優(yōu)化方法使自適應(yīng)索引能夠較好地適應(yīng)常用的兩種查詢樣式(隨機(jī)查詢和順序查詢),提升了自適應(yīng)索引的魯棒性.

圖1　Database Cracking算法流程示例

1　相關(guān)工作

Database Cracking算法[3]作為自適應(yīng)索引的核心被廣泛采用.Database Cracking首先將表中需要建立索引的數(shù)據(jù)復(fù)制到一個(gè)連續(xù)的空間作為索引的物理結(jié)構(gòu),其次根據(jù)每次查詢條件對(duì)索引進(jìn)行重新劃分,重新劃分的過(guò)程類似快速排序,查詢的邊界點(diǎn)類似快速排序中的支點(diǎn).最后還需要一個(gè)二叉樹來(lái)保存劃分信息(該二叉樹稱為Cracker index),樹節(jié)點(diǎn)〈X,Y〉表示在索引中從位置Y開始的所有數(shù)據(jù)都大于X.圖1給出了Database Cracking方法的基本流程.當(dāng)進(jìn)行查詢(10,30)時(shí),索引被劃分為了3塊:小于10的部分、(10,30)的部分、大于30的部分,其中(10,30)的部分作為查詢結(jié)果返回.節(jié)點(diǎn)〈10,2〉和〈30,7〉也同時(shí)保存在樹中.當(dāng)進(jìn)行第2次查詢(25,40)時(shí),(10,30)的塊再次被分成(10,25)和(25,30)兩塊,大于30的部分也被分成(30,40)和大于40的兩塊,其中,(25,30)和(30,40)兩塊作為查詢結(jié)果返回.同時(shí),節(jié)點(diǎn)〈25,5〉和〈40,10〉也保存在樹結(jié)構(gòu)中以便后續(xù)查詢使用.Database Cracking算法的優(yōu)勢(shì)是:每次查詢只需處理索引中包含查詢邊界的兩個(gè)數(shù)據(jù)塊,并不需要處理整個(gè)查詢范圍之間的數(shù)據(jù)塊.所以當(dāng)查詢次數(shù)越多,索引被劃分的越細(xì),索引中每塊數(shù)據(jù)越小,則索引被建立的越好,該范圍內(nèi)后續(xù)查詢所用的時(shí)間越短.

目前針對(duì)Database Cracking算法的研究主要在以下3個(gè)方面:提高算法收斂速度、提高算法魯棒性以及利用并行提高算法效果.Hybrid Cracking算法[6]結(jié)合了Adaptive Merging算法[7]和標(biāo)準(zhǔn)Database Cracking算法各自的優(yōu)勢(shì),在保證較低初始化花銷的同時(shí),提高了算法的收斂速度.Buffered-swapping算法[9]利用兩個(gè)堆結(jié)構(gòu)存儲(chǔ)需要交換元素,提升了算法的收斂速度.文獻(xiàn)[10]針對(duì)順序查詢樣式引出的問(wèn)題,提出了DDR,DDC以及MDD1R等算法,以提高算法魯棒性,其中DDR算法取得了較好的效果.文獻(xiàn)[4]研究了并行Database Cracking算法,通過(guò)加鎖的方式避免線程間的沖突,實(shí)現(xiàn)算法并行化.文獻(xiàn)[5]提出了Refined Partition Merge算法,在該算法中所有線程每次共同處理一個(gè)查詢?nèi)蝿?wù).

2　多核并行自適應(yīng)索引優(yōu)化

2.1實(shí)驗(yàn)環(huán)境

文中的實(shí)驗(yàn)環(huán)境基于新型英特爾Sandy Bridge架構(gòu)的Xeon 8核處理器(E5-2670 2.6 GHz),每核包含2個(gè)線程.具體配置為:核數(shù)為8,線程數(shù)為16,一級(jí)緩存大小為每核32 KB;二級(jí)緩存大小為每核256 KB;三級(jí)緩存大小為共享20 MB;內(nèi)存大小為4×8 GB DDR3內(nèi)存(1 600 Hz);Cache line大小為64 B.

實(shí)驗(yàn)采用與相關(guān)論文相同的數(shù)據(jù)集.該數(shù)據(jù)集有108條數(shù)據(jù),每條數(shù)據(jù)是大小為4 B的整型數(shù),108條數(shù)據(jù)在[0,108)范圍內(nèi)隨機(jī)產(chǎn)生且均勻分布.

采用的查詢格式為:SELECT SUM(R.A)FROM R WHERE Ql＜R.A＜Qh.

文中討論兩種查詢樣式:隨機(jī)查詢和順序查詢,這兩種查詢均為相關(guān)論文所討論的主要查詢方式.圖2給出隨機(jī)查詢樣式和順序查詢樣式,其中黑圈表示查詢下限Ql,白圈表示查詢上限Qh,兩種查詢的選擇率均為1%.

圖2　文中所用的兩種查詢樣式

2.2Refined Partition Merge算法的優(yōu)化

文獻(xiàn)[5]提出了Refined Partition Merge算法,所有線程共同處理一條查詢?nèi)蝿?wù).假設(shè)索引結(jié)構(gòu)中有S個(gè)元素,線程數(shù)量為T,現(xiàn)將索引結(jié)構(gòu)劃分為T塊.前T-1塊中,每塊含有S/T個(gè)元素,且由兩個(gè)不相鄰的子塊組成,每個(gè)子塊有S/(2T)個(gè)元素,每個(gè)子塊的位置對(duì)稱于索引中心位置的兩側(cè);第T塊含有剩余元素(考慮元素不能等分的情況),其元素連續(xù)的分布于索引中心位置兩側(cè),如圖3所示.在劃分階段,每一個(gè)線程負(fù)責(zé)一塊數(shù)據(jù),并行地執(zhí)行標(biāo)準(zhǔn)Database Cracking算法;在合并階段,將位置錯(cuò)誤的元素進(jìn)行位置交換,最終得到正確的Database Cracking結(jié)果.在該算法中每一個(gè)線程負(fù)責(zé)兩個(gè)不相連的數(shù)據(jù)子塊,這樣避免了Merge階段大量元素的交換,提高了合并階段的效率.

圖3　Refined Partition Merge算法示例

圖4　并行合并示例

在Refined Partition Merge算法中,合并階段是由一個(gè)線程獨(dú)立完成的,沒(méi)有充分利用處理器的并行資源.文中的優(yōu)化是對(duì)合并階段進(jìn)行并行化處理,利用多路并行歸并的思想,分層將塊中位置錯(cuò)誤的元素進(jìn)行交換.在圖4中,L代表小于支點(diǎn)的數(shù)據(jù),H代表大于支點(diǎn)的數(shù)據(jù).塊1和塊2分別經(jīng)過(guò)Database Craking處理后,塊內(nèi)相對(duì)有序,塊間無(wú)序.如圖4所示,一個(gè)線程將塊1和塊2中位置錯(cuò)誤的元素進(jìn)行交換后,形成一個(gè)新塊,等待進(jìn)行下一層的交換.每層之中的交換可以多線程并行處理,經(jīng)過(guò)多層交換以后最終得到元素位置正確的索引.圖4舉例說(shuō)明并行合并過(guò)程,其中每層的交換可以并行處理,經(jīng)過(guò)兩層交換后得到最終正確的結(jié)果.

2.3改進(jìn)的多核并行自適應(yīng)索引算法

在加鎖并行方法中,每一個(gè)線程每次負(fù)責(zé)一條查詢?nèi)蝿?wù),索引中的每一個(gè)數(shù)據(jù)塊有一個(gè)讀寫鎖,整個(gè)Cracker index(即保存劃分信息的二叉樹)有一個(gè)讀寫鎖,這些讀寫鎖避免了線程之間的沖突.當(dāng)一個(gè)線程對(duì)某一數(shù)據(jù)塊處理時(shí),會(huì)對(duì)該數(shù)據(jù)塊加鎖.這時(shí)對(duì)數(shù)據(jù)塊進(jìn)行任何操作的其他線程都會(huì)被阻塞,直至該數(shù)據(jù)塊被解鎖.算法對(duì)Cracker index允許多線程并行讀操作,但不允許并行寫操作.

圖5　兩種并行算法性能比較

以上兩種算法都有各自的優(yōu)缺點(diǎn),圖5給出了兩種算法在8線程環(huán)境下進(jìn)行1次至1 000次隨機(jī)查詢時(shí)分別所需的時(shí)間.從圖5可以看出,當(dāng)查詢次數(shù)較少時(shí)優(yōu)化Refined Partition Merge算法效果較好,當(dāng)查詢次數(shù)較多時(shí)加鎖并行Database Cracking算法效果較好.這是因?yàn)?當(dāng)查詢次數(shù)較少,索引中數(shù)據(jù)塊較少時(shí),特別是前幾次查詢時(shí),加鎖并行Database Cracking算法中線程之間沖突的概率增大,算法性能降低.以第1次查詢?yōu)槔f(shuō)明:當(dāng)進(jìn)行第1條查詢?nèi)蝿?wù)時(shí),整個(gè)索引只是一整塊數(shù)據(jù),沒(méi)有任何劃分,此時(shí)只有一個(gè)線程可以工作,其余線程需要等待.這耗費(fèi)了大量時(shí)間,浪費(fèi)了并行資源,特別是當(dāng)索引數(shù)據(jù)特別大時(shí).此時(shí)優(yōu)化Refined Partition Merge算法不會(huì)浪費(fèi)其他線程的計(jì)算資源,所以取得較好的效果.當(dāng)查詢次數(shù)較多,索引中數(shù)據(jù)塊較多時(shí),加鎖并行Database Cracking算法中線程之間沖突的概率較小,線程等待鎖的平均時(shí)間大大降低,所以此算法效率較高.然而此時(shí),優(yōu)化Refined Partition Merge算法依然讓所有線程并行處理一個(gè)數(shù)據(jù)塊,即使該數(shù)據(jù)塊很小,這樣大部分時(shí)間花費(fèi)到線程建立、數(shù)據(jù)分配等操作上,所以當(dāng)查詢次數(shù)增加,優(yōu)化Refined Partition Merge算法性能降低.文中提出了一種改進(jìn)的多核并行自適應(yīng)索引方法.該方法將優(yōu)化Refined Partition Merge算法和加鎖并行Database Cracking算法相結(jié)合,在前幾次查詢時(shí)或者處理索引中較大的數(shù)據(jù)塊時(shí),使用優(yōu)化的Refined Partition Merge算法,降低線程之間沖突的概率,減少線程等待時(shí)間,提高線程利用率.隨著查詢次數(shù)和索引中數(shù)據(jù)塊的增加,之后的查詢則使用加鎖解鎖方法,避免了Refined Partition Merge在處理索引中小數(shù)據(jù)塊時(shí)的不足.在此提出的優(yōu)化方法適用于同一數(shù)據(jù)集上的多次范圍查詢.當(dāng)查詢次數(shù)較少時(shí),利用2.2節(jié)提出算法即可.

2.4提升算法魯棒性的優(yōu)化

魯棒性是自適應(yīng)索引算法一個(gè)關(guān)鍵的因素,強(qiáng)壯的魯棒性可以使文中算法適應(yīng)多種樣式的查詢.標(biāo)準(zhǔn)的Database Cracking算法(單線程)和加鎖并行Database Cracking算法(多線程)都不能很好的處理順序查詢.圖6給出了加鎖并行Database Cracking算法處理隨機(jī)查詢和順序查詢的實(shí)驗(yàn)結(jié)果,從圖中可以看出,加鎖并行Database Cracking算法能夠很好處理隨機(jī)查詢,但對(duì)順序查詢處理效果不佳.主要因?yàn)?加鎖并行Database Cracking算法僅根據(jù)每個(gè)查詢的邊界對(duì)數(shù)據(jù)塊進(jìn)行劃分.在順序查詢中,每次劃分將一個(gè)數(shù)據(jù)塊分為兩個(gè)大小相差很大的數(shù)據(jù)塊,其中一個(gè)數(shù)據(jù)塊很大,另一個(gè)卻很小.這使后續(xù)的查詢需要遍歷較大的數(shù)據(jù)塊,增加了開銷.

圖6　兩種查詢樣式的性能比較

圖7　劃分支點(diǎn)位置對(duì)性能的影響

針對(duì)上述問(wèn)題,在DDR算法[10]的基礎(chǔ)上,提出了一種優(yōu)化方法.思路是:在改進(jìn)的多核并行自適應(yīng)索引方法中,無(wú)論優(yōu)化Refined Partition Merge算法還是加鎖并行Database Cracking算法,在進(jìn)行一次由查詢驅(qū)動(dòng)的劃分后,都額外進(jìn)行一次隨機(jī)劃分,并將產(chǎn)生的兩個(gè)新節(jié)點(diǎn)均加入Cracker index之中.

3　實(shí)驗(yàn)結(jié)果及分析

3.1優(yōu)化Refined Partition Merge算法的實(shí)驗(yàn)結(jié)果

為了驗(yàn)證對(duì)原Refined Partition Merge算法的優(yōu)化效果,將優(yōu)化的算法(2.2節(jié))與原算法在不同線程數(shù)下進(jìn)行了比較.實(shí)驗(yàn)采用2.1節(jié)所述的數(shù)據(jù)集和隨機(jī)查詢樣式,實(shí)驗(yàn)結(jié)果如圖8所示.從圖8可以看出:優(yōu)化后的算法與原算法相比,性能有所提高;當(dāng)線程數(shù)為1時(shí),兩個(gè)算法所需時(shí)間一樣;當(dāng)線程數(shù)從8增加到16時(shí),算法性能提升不明顯.這是因?yàn)?首先,采用了并行合并算法,減少了合并階段的時(shí)間消耗,算法性能得到了提升;其次,當(dāng)線程數(shù)為1時(shí),不需要進(jìn)行合并操作,所以兩個(gè)算法所需的時(shí)間相同;最后,由于實(shí)驗(yàn)機(jī)器為8核16線程,總線資源和緩存資源按核分配.所以當(dāng)線程數(shù)量為16時(shí),核內(nèi)線程之間會(huì)競(jìng)爭(zhēng)總線、緩存等資源,所以,當(dāng)線程數(shù)從8增加到16時(shí),算法性能提升不明顯.

圖8　優(yōu)化Refined Partition Merge算法的實(shí)驗(yàn)結(jié)果

圖9　改進(jìn)的多核并行自適應(yīng)索引算法實(shí)驗(yàn)結(jié)果

3.2改進(jìn)的多核并行自適應(yīng)索引算法的實(shí)驗(yàn)結(jié)果

圖9給出了改進(jìn)的多核并行自適應(yīng)索引算法(2.3節(jié))與其他兩種常用的并行自適應(yīng)索引算法在不同線程數(shù)量下的對(duì)比結(jié)果.實(shí)驗(yàn)采用2.1節(jié)所述的數(shù)據(jù)集和隨機(jī)查詢樣式,文中算法在前5%次查詢(即前50次)使用優(yōu)化的Refined Partition Merge算法,剩余查詢使用加鎖并行Database Cracking算法.由圖9可以看出,文中算法與原有的算法相比,性能有了明顯的提高.這是由于在前50次查詢時(shí)使用優(yōu)化的Refined Partition Merge算法,提高了算法處理大數(shù)據(jù)塊時(shí)的效率;在剩余查詢時(shí)使用加鎖并行Database Cracking算法時(shí),由于此時(shí)索引中數(shù)據(jù)塊較多,線程之間沖突的概率減小,且與優(yōu)化的Refined Partition Merge算法大幅減少了線程創(chuàng)建、數(shù)據(jù)分配等操作的開銷.當(dāng)線程數(shù)量為16時(shí),核內(nèi)線程之間會(huì)競(jìng)爭(zhēng)總線、緩存等資源,所以當(dāng)線程數(shù)從8增加到16時(shí),算法性能提升不明顯.

3.3算法魯棒性優(yōu)化的實(shí)驗(yàn)結(jié)果

圖10給出了算法魯棒性優(yōu)化(2.4節(jié))的實(shí)驗(yàn)結(jié)果,實(shí)驗(yàn)采用2.1節(jié)所述的數(shù)據(jù)集和順序查詢樣式.圖10進(jìn)一步驗(yàn)證了2.4節(jié)中加鎖并行Database Cracking算法不能很好的處理順序查詢的結(jié)論.實(shí)驗(yàn)結(jié)果表明,并行DDR算法和文中優(yōu)化算法針對(duì)順序查詢時(shí)都取得了較好的效果,且文中優(yōu)化算法效果最好.這是因?yàn)?增加一次隨機(jī)劃分可以避免大數(shù)據(jù)塊的出現(xiàn)而影響后續(xù)查詢;文中優(yōu)化算法可以針對(duì)不同的劃分位置,選取更好的劃分策略(兩次Cracking-into-two操作或者一次Cracking-intothree操作),所以,文中算法比并行DDR算法性能有所提升.

圖10　算法魯棒性優(yōu)化實(shí)驗(yàn)結(jié)果

4　結(jié)束語(yǔ)

為了解決多核并行自適應(yīng)索引算法不能高效地利用多核處理器的并行資源,且不能較好處理順序查詢的問(wèn)題,筆者優(yōu)化了傳統(tǒng)的多核并行自適應(yīng)索引算法.在改進(jìn)Refined Partition Merge算法的基礎(chǔ)上,將加鎖并行方法與改進(jìn)的Refined Partition Merge算法相結(jié)合,在索引中數(shù)據(jù)塊較少時(shí),使用優(yōu)化的Refined Partition Merge算法,降低線程之間沖突的概率,減少線程等待時(shí)間,提高線程利用率.當(dāng)索引中數(shù)據(jù)塊較多時(shí),使用加鎖并行方法,充分利用了多核處理器的并行資源,且提高了算法的魯棒性.實(shí)驗(yàn)證明了筆者提出方法的有效性和魯棒性.

[1]馬艷萍,姬光榮,鄒海林,等.數(shù)據(jù)依賴的多索引哈希算法[J].西安電子科技大學(xué)學(xué)報(bào),2015,42(4):159-164. MA Yanping,JI Guangrong,ZOU Hailin,et al.Data-oriented Multi-index Hashing[J].Journal of Xidian University,2015,42(4):159-164.

[2]LEIS V,KEMPER A,NEUMANN T.The Adaptive Radix Tree:Artful Indexing for Main-memory Databases[C]// Proceedings of the 29th International Conference on Data Engineering.Washington:IEEE Computer Society,2013: 38-49.

[3]IDREOS S,KERSTEN M L,MANEGOLD S.Database Cracking[C]//3rd Biennial Conference on Innovative Data Systems Research.Asilomar:CIDR,2007:68-78.

[4]GRAEFE G,HALIM F,IDREOS S,et al.Concurrency Control for Adaptive Indexing[J].Proceedings of the VLDB Endowment,2012,5(7):656-667.

[5]PIRK H,PETRAKI E,IDREOS S,et al.Database Cracking:Fancy Scan,Not Poor Man’s Sort[C]//10th International Workshop on Data Management on New Hardware.New York:ACM,2014:25-32.

[6]IDREOS S,MANEGOLD S,KUNO H,et al.Merging What’s Cracked,Cracking What’s Merged:Adaptive Indexing in Main-memory Column-stores[J].Proceedings of the VLDB Endowment,2011,4(9):585-597.

[7]GRAEFE G,KUNO H.Self-selecting,Self-tuning,Incrementally Optimized Indexes[C]//13th International Conference on Extending Database Technology.New York:ACM,2010:371-381.

[8]IDREOS S,KERSTEN M,MANEGOLD S.Updating a Cracked Database[C]//2007 ACM SIGMOD International Conference on Management of Data.New York:ACM,2007:416-424.

[9]SCHUHKNECHT F,JINDAL A,DITTRICH J.The Uncracked Pieces in Database Cracking[J].Proceedings of the VLDB Endowment,2014,7(2):97-108.

[10]HALIM F,IDREOS S,KARRAS P,et al.Stochastic Database Cracking:Towards Robust Adaptive Indexing in Mainmemory Column-stores[J].Proceedings of the VLDB Endowment,2012,5(6):502-513.

(編輯:王 瑞)

Optimizing the parallel adaptive indexing algorithm on multi-core CPUs

YUAN Tong,LIU Zhijing,LIU Hui
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

An improved parallel adaptive indexing algorithm on multi-core CPUs is proposed to solve the problems that the parallel adaptive indexing algorithms cannot take full advantage of the CMP’s parallel execution resource,and properly process the sequential query pattern.Based on the optimization of the Refined Partition Merge algorithm,our improved parallel adaptive indexing algorithm combines the Parallel Database Cracking method with the Refined Partition Merge algorithm.In our algorithm,when fewer data chunks are in the index,we use the optimized Refined Partition Merge algorithm so as to reduce the probability of conflict between threads,decrease the waiting time,and increase the utilization of the threads,and when more data chunks are in the index,we use the Parallel Database Cracking method so as to take full advantage of the CMP’s parallel execution resources.Besides,we propose an optimization for the robustness,which makes our algorithm suitable for two common query patterns.Experiments show that our method can reduce the query time by 25.7%～33.2%,and suit with common query patterns.

adaptive indexing;multicore processors;database cracking algorithm;database system

TP392

A

1001-2400(2016)05-0057-06

10.3969/j.issn.1001-2400.2016.05.011

2015-07-22 網(wǎng)絡(luò)出版時(shí)間:2015-12-10

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202177)

袁 通(1987-),男,西安電子科技大學(xué)博士研究生,E-mail:yuantongxd@gmail.com.

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.022.html