基于分布式數(shù)據(jù)庫(kù)的半連接查詢計(jì)劃選擇算法

夏斌

摘 要 為了提高分布式數(shù)據(jù)庫(kù)系統(tǒng)的查詢效率，采用新的代價(jià)模型在執(zhí)行半連接計(jì)劃之前評(píng)估和傳輸執(zhí)行與優(yōu)化代價(jià)。由于剔除與連接無關(guān)的數(shù)據(jù)，有效減少連接操作關(guān)系中的無用數(shù)據(jù)，選擇執(zhí)行代價(jià)更小的執(zhí)行方法。首先對(duì)分布式數(shù)據(jù)庫(kù)查詢執(zhí)行代價(jià)模型進(jìn)行分析，然后對(duì)半連接中的連接運(yùn)算方式、連接關(guān)系的傳輸方法和執(zhí)行場(chǎng)地等問題進(jìn)行研究，并計(jì)算其評(píng)估方法的執(zhí)行代價(jià)，給出一種可行的查詢計(jì)劃選擇算法，最終確定執(zhí)行的場(chǎng)地、連接的方法和傳輸方法。

【關(guān)鍵詞】半連接查詢 分布式數(shù)據(jù)庫(kù) 查詢優(yōu)化 代價(jià)模型

基于直接連接算法的查詢優(yōu)化處理，針對(duì)執(zhí)行場(chǎng)地的不同，針對(duì)連接方式的不同，以及針對(duì)傳輸方法的不同的查詢優(yōu)化已有不少研究。而基于半連接算法的查詢優(yōu)化處理在這三個(gè)方面的綜合評(píng)估和代價(jià)分析研究還較少。因此本文重點(diǎn)研究基于半連接的實(shí)現(xiàn)方法，綜合考慮局部代價(jià)和傳輸代價(jià)的相對(duì)費(fèi)用，計(jì)算所有評(píng)估方法的執(zhí)行代價(jià)，選擇其中執(zhí)行代價(jià)較小的執(zhí)行方法，最終確定執(zhí)行的場(chǎng)地、連接的方法和傳輸?shù)姆椒ā?/p>

1 分布式查詢代價(jià)模型

分布式數(shù)據(jù)庫(kù)的查詢執(zhí)行代價(jià)中主要由以下3部分組成：

（1）訪問輔助存儲(chǔ)器的代價(jià)（簡(jiǎn)稱I/O代價(jià)）；

（2）計(jì)算代價(jià)（簡(jiǎn)稱CPU代價(jià)）；

（3）傳輸代價(jià)。分布式數(shù)據(jù)庫(kù)中，傳輸代價(jià)是總代價(jià)的重要組成部分。

1.1 CPU代價(jià)

由于在實(shí)際運(yùn)算環(huán)境中，傳輸代價(jià)與I/O代價(jià)遠(yuǎn)遠(yuǎn)超過連接操作的代價(jià)，在具體計(jì)算中可忽略不計(jì)。

1.2 I/O代價(jià)

目前，使用較多的輔助存儲(chǔ)器主要是磁盤，其一次訪問的所需的代價(jià)可表示為

CIO=D0+D1*X

其中：X為存取數(shù)據(jù)的大小；D0為與X無關(guān)的I/O代價(jià)，包括尋道時(shí)間和等待時(shí)間；D1為單位數(shù)據(jù)的傳輸時(shí)間。

一般地D0>>D1*X，故CIO≈D0，I/0代價(jià)≈I/0次數(shù)*D0。

由于不同算法在I/O代價(jià)上沒有明顯的差異，因此不作深究，在計(jì)算中用常數(shù)Ti替代。

1.3 傳輸代價(jià)

分布式數(shù)據(jù)庫(kù)系統(tǒng)中的傳輸代價(jià)與網(wǎng)絡(luò)的類型有關(guān)，通常可以近似地表示為

Cconvey（X）=C0+C1*X

其中：X為傳輸數(shù)據(jù)的大小；C0為傳輸一次數(shù)據(jù)所必需的初始代價(jià)；C1為單位數(shù)據(jù)的傳輸代價(jià)（代價(jià)系數(shù)）；C0、C1一般隨網(wǎng)絡(luò)的類型而變化，對(duì)于某一具體的網(wǎng)絡(luò)，其值為常數(shù)；Cconvey（X）一下簡(jiǎn)稱Cc（X）。

2 半連接查詢算法

基于半連接（Semi-Join）算法優(yōu)化查詢，其基本思想是經(jīng)過半連接操作減少操作關(guān)系，從而減少站點(diǎn)間數(shù)據(jù)的傳輸量。

2.1 半連接算法的關(guān)系代數(shù)

假定站點(diǎn)1上的關(guān)系A(chǔ)與站點(diǎn)2上的關(guān)系B在屬性A.x=B.x上進(jìn)行等值連接，采用半連接方法表示這一操作為：

A∞A.x=B.xB=（A∝A.x=B.xB） ∞A.x=B.xB

其中，∝符號(hào)為半連接操作符。

一次完整的半連接方法的連接操作過程關(guān)系代數(shù)可表示為

A∞A.x=B.xB=（A∞A.x=B.x（πB.x（B））） ∞B （1）

其中，∝代表半連接操作，∞代表連接操作，π代表投影操作。

2.2 半連接算法的連接過程

針對(duì)公式（1），半連接的連接過程可分為五步。

（1）在站點(diǎn)2上將B在屬性B.x上進(jìn)行投影獲得B'=πB.x（B）；

（2）將B'傳送到站點(diǎn)1；

（3）在站點(diǎn)1上計(jì)算A'=A∞B'的半連接結(jié)果；

（4）將站點(diǎn)1上的A'與站點(diǎn)2上的B傳送到發(fā)起查詢請(qǐng)求的站點(diǎn)3上；

（5）在站點(diǎn)3上進(jìn)行連接操作。

2.3 半連接算法代價(jià)估計(jì)

查詢發(fā)起請(qǐng)求站點(diǎn)3有3種情況：設(shè)站點(diǎn)3=站點(diǎn)1的Site（A）；設(shè)站點(diǎn)3=站點(diǎn)2的Site（B），等價(jià)于Site（A），不予討論；或者其他場(chǎng)地Site（other）。根據(jù)查詢地點(diǎn)的不同，則傳送的數(shù)據(jù)量和傳輸費(fèi)用會(huì)不同。

為了準(zhǔn)確描述代價(jià)的計(jì)算，作如下定義：

（1）一個(gè)關(guān)系A(chǔ)的元組數(shù)，表示為size（A）；

（2）每個(gè)屬性xi的長(zhǎng)度表示為length（A.xi），并將所有屬性大小的總和，即一個(gè)元組的大小表示為length（A）。

3 半連接查詢優(yōu)化

由于代價(jià)模型已知，因此在查詢開始前如果進(jìn)行查詢計(jì)劃的選擇，可以保證連接代價(jià)的優(yōu)化。

3.1 當(dāng)查詢發(fā)起站點(diǎn)包含其中一個(gè)表時(shí)

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

本文研究了分布式數(shù)據(jù)庫(kù)中以總代價(jià)最小為半連接查詢優(yōu)化準(zhǔn)側(cè)，著重考慮了傳輸代價(jià)，分析了半連接算法實(shí)現(xiàn)過程中影響執(zhí)行總代價(jià)的三方面因素：連接運(yùn)算的方法、連接關(guān)系的傳輸方法、執(zhí)行場(chǎng)地，給出了半連接算法可能的實(shí)施方案并評(píng)估了不同條件下各種方案的執(zhí)行代價(jià)，并給出了一種可行的優(yōu)化算法以實(shí)現(xiàn)查詢計(jì)劃方法。

參考文獻(xiàn)

[1]Shao Peiying.Distributed database system and its application[M].Science Press，2005

[2]Bassiliades N，Vlahavas I.Hierarchical query execution in a parallel object-oriented database system[J].Parallel Computing，2000，22（07）：1017-1048.

[3Li Xuefeng.The use of distributed hash table to build a copy of the checkpoint[J].small and micro computer systems，2011，32（08）：1548-1552.

作者單位

南京航空航天大學(xué) 江蘇省南京市 210000