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

夏斌

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

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

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

1 分布式查詢代價模型

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

（1）訪問輔助存儲器的代價（簡稱I/O代價）；

（2）計算代價（簡稱CPU代價）；

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

1.1 CPU代價

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

1.2 I/O代價

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

CIO=D0+D1*X

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

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

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

1.3 傳輸代價

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

Cconvey（X）=C0+C1*X

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

2 半連接查詢算法

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

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

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

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

其中，∝符號為半連接操作符。

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

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

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

2.2 半連接算法的連接過程

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

（1）在站點2上將B在屬性B.x上進行投影獲得B'=πB.x（B）；

（2）將B'傳送到站點1；

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

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

（5）在站點3上進行連接操作。

2.3 半連接算法代價估計

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

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

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

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

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

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

3.1 當(dāng)查詢發(fā)起站點包含其中一個表時

4 結(jié)束語

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