資源描述：
《一種新的高速緩存敏感的磁盤連接算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第27屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議DBCC-Join:一種新的高速緩存敏感的磁盤連接算法韓希先，李建中，楊東華數(shù)據(jù)與知識(shí)工程研究中心哈爾濱工業(yè)大學(xué)Outline?研究動(dòng)機(jī)?DBCC-Join算法?實(shí)驗(yàn)及分析?結(jié)論研究動(dòng)機(jī)?CPU的處理速度每18個(gè)月增長(zhǎng)一倍?主存的讀取速度每6年提高一倍?CPU和主存的性能差異每21個(gè)月增大一倍?高速緩存的引入彌補(bǔ)該性能差異?高速緩存對(duì)查詢處理的重要性研究動(dòng)機(jī)?連接操作?常用并耗時(shí)的數(shù)據(jù)庫(kù)操作，影響數(shù)據(jù)庫(kù)整體性能?傳統(tǒng)連接算法沒(méi)有考慮高速緩存的使用?已提出內(nèi)存數(shù)據(jù)庫(kù)中的高速緩存敏感的
2、連接算法，實(shí)際情況中更多的是基于磁盤的連接算法?以hashjoin為例討論?低高速緩存利用率的原因?面向元組的處理模式?較大的內(nèi)關(guān)系塊Outline?研究動(dòng)機(jī)?DBCC-Join算法?實(shí)驗(yàn)及分析?結(jié)論DBCC-Join算法?DBCC-Join(Disk-BasedCache-ConsciousJoinAlgorithm)?充分利用高速緩存?方法?面向?qū)傩缘奶幚砟Ｊ?vs.面向元組的處理模式)?減小內(nèi)關(guān)系塊(vs.較大的內(nèi)關(guān)系塊)DBCC-Join算法?一些有用的定義?位置索引(PI:PositionalIn
3、dex)?連接位置索引對(duì)表(JPIPT:JoinPositionalIndexPairTable)數(shù)據(jù)表T11元組T22JPIPTPI1PI2位置索引為ii元組355286N元組DBCC-Join算法?兩階段執(zhí)行?JPIPT構(gòu)建階段(JCS:JPIPTConstructionStage)?獲得需要的連接位置索引對(duì)表JPIPT?結(jié)果輸出階段(ROS:ResultOutputStage)?利用獲得的JPIPT，來(lái)輸出最終的連接結(jié)果DBCC-Join算法?JPIPT構(gòu)建階段C1(PI1,key1)C2(PI2,k
4、ey12)112PIPI21233534524586566778現(xiàn)有連接算法對(duì)8cache的利用率較低selectPI,PI[BonczVLDB99]12fromC,C12whereC.key=C.key1122DBCC-Join算法?JPIPT構(gòu)建階段：C3-JPIPT(高速緩存意識(shí)構(gòu)建算法)?第一次劃分-磁盤劃分?第二次劃分-內(nèi)存劃分磁盤磁盤C1,1C2,1C1C2C1,2C2,2內(nèi)存…………C1,iC2,iC1,iC2,i…………C1,Np1C2,Np1DBCC-Join算法?JPIPT構(gòu)建階段：C3
5、-JPIPT(高速緩存意識(shí)構(gòu)建算法)?第二次劃分-內(nèi)存劃分內(nèi)存內(nèi)存C1,iC2,i高速緩存…………構(gòu)建哈希表探測(cè)哈希表…………DBCC-Join算法?JPIPT的性質(zhì)：JPIPT在PI上有序1內(nèi)存內(nèi)存C1,iC2,i高速緩存…………構(gòu)建哈希表…………探測(cè)哈希表PI１PI2每個(gè)分片中的元組的位置索引屬性是有序排列的DBCC-Join算法?結(jié)果輸出階段:利用獲得JPIPT，返回連接結(jié)果?JPIPT劃分?外關(guān)系掃描?內(nèi)關(guān)系掃描DBCC-Join算法?結(jié)果輸出?JPIPT劃分?劃分原則?外關(guān)系掃描：每個(gè)JPIPT分
6、片可以放入內(nèi)存?內(nèi)關(guān)系掃描：每個(gè)JPIPT分片及其對(duì)應(yīng)的T元組可2以放入內(nèi)存PS={[1,10],…,[PI,PI],…,[N-9,N]}11i1(i+1)11PS={[1,3],…,[PI,PI],…,[N-2,N]}22j2(j+1)22DBCC-Join算法根據(jù)該元組對(duì)應(yīng)的PI屬2性屬于PS2的那個(gè)元素?結(jié)果輸出階段JPIPTT1?外關(guān)系掃描PI1順序……排……列……PS={[1,10],…,[PI,PI],…,[N-9,N]}11i1(i+1)11PS={[1,3],…,[PI,PI],…,[N-2
7、,N]}22j2(j+1)22DBCC-Join算法根據(jù)該元組對(duì)應(yīng)的PI1屬性屬于PS的那個(gè)元素1JPIPTT2ofile_1_i?結(jié)果輸出階段PI1,PI2根據(jù)PI2有排序有根據(jù)PI1序序排序?內(nèi)關(guān)系掃描ofile_1_jofile_1_k………………PS={[1,10],…,[PI,PI],…,[N-9,N]}11i1(i+1)11PS={[1,3],…,[PI,PI],…,[N-2,N]}22j2(j+1)22DBCC-Join算法?結(jié)果輸出階段?PS1包括m個(gè)元素?PS2包括n個(gè)元素?共獲得m×n對(duì)
8、文件，lfile_i_j和ofile_i_j(1≤i≤m,1≤j≤n)?lfile_i_j和ofile_i_j中，具有相等位置索引的元組構(gòu)成一個(gè)連接元組?定理3：結(jié)果輸出階段獲得的結(jié)果是正確的。Outline?研究動(dòng)機(jī)?高速緩存結(jié)構(gòu)?當(dāng)前連接算法利用緩存的問(wèn)題?DBCC-Join算法?實(shí)驗(yàn)及分析?結(jié)論實(shí)驗(yàn)及分析?實(shí)驗(yàn)配置?HPxw8600Workstation(8個(gè)2.8GHzXeonCPU+6MBL2cache
