半連接查詢優(yōu)化技術(shù)研究

倪興旺 （安慶職業(yè)技術(shù)學(xué)院電子信息系，安徽 安慶246003）

分布式數(shù)據(jù)庫技術(shù)是分布性與集中性的統(tǒng)一。分布性表現(xiàn)為數(shù)據(jù)在網(wǎng)絡(luò)中是跨結(jié)點存儲的，集中性表現(xiàn)在用戶邏輯上所見是一個同構(gòu)的、簡單的數(shù)據(jù)庫。分布式系統(tǒng)中的每個網(wǎng)絡(luò)結(jié)點具有獨立處理數(shù)據(jù)的能力，在這種情況下分布式系統(tǒng)可以使用很多處理器，由此可以加速查詢［1］。然而，分布式數(shù)據(jù)庫環(huán)境中的查詢與集中式數(shù)據(jù)庫環(huán)境中的查詢相比較，要增加2個關(guān)鍵問題，首先是數(shù)據(jù)要通過通信線路進(jìn)行傳輸，這將減慢整個查詢的執(zhí)行過程；其次是網(wǎng)絡(luò)中多處理器的存在提供了并行數(shù)據(jù)處理和傳輸?shù)臋C(jī)會，應(yīng)充分利用可以加快查詢的響應(yīng)速度。由于上述原因，在分布式查詢處理技術(shù)中，查詢優(yōu)化就顯得極其重要。為此，筆者以分布式數(shù)據(jù)庫系統(tǒng)為背景，采用“二次半連接拼接算法”對查詢處理進(jìn)行優(yōu)化，進(jìn)而降低系統(tǒng)開銷，有效減少結(jié)點間的數(shù)據(jù)傳輸量，提高查詢的效率［2］。

1 分布式數(shù)據(jù)庫系統(tǒng)中查詢優(yōu)化的基本方法

在分布式查詢處理技術(shù)中，有2種基本的優(yōu)化方法：查詢轉(zhuǎn)換和查詢映射。查詢轉(zhuǎn)換即以不同的順序來執(zhí)行關(guān)系操作，如連接、選擇和投影操作，是使用結(jié)點間的數(shù)據(jù)傳輸來控制查詢的執(zhí)行以及操作順序，查詢優(yōu)化器對這些數(shù)據(jù)傳輸進(jìn)行決策。查詢映射即以一系列高效的算法來存取各種設(shè)備（如采用索引）和實現(xiàn)關(guān)系操作，主要針對關(guān)系操作的執(zhí)行算法（特別是連接操作）來進(jìn)行決策。目前，已經(jīng)出現(xiàn)了許多查詢優(yōu)化處理算法，如直接連接算法或一些基于半連接操作的優(yōu)化算法，以及基于關(guān)系代數(shù)表達(dá)式等價轉(zhuǎn)換的查詢優(yōu)化算法等。

在這些查詢優(yōu)化算法中，半連接方法使得局部數(shù)據(jù)處理有所增加，但數(shù)據(jù)在不同站點之間的傳輸將會減少。直接連接主要用于本地處理開銷遠(yuǎn)遠(yuǎn)大于傳輸開銷的情況。而關(guān)系代數(shù)表達(dá)式等價轉(zhuǎn)換優(yōu)化算法就是把查詢要求求解成關(guān)系代數(shù)表達(dá)式，然后分析得到查詢樹，利用查詢變換方法和等價變換規(guī)則，先執(zhí)行投影和選擇操作，而連接等其他二元操作在其后執(zhí)行，盡量避免大塊的連接數(shù)據(jù)在分布式結(jié)點間傳送，從而實現(xiàn)查詢優(yōu)化的目標(biāo)。這些查詢優(yōu)化方法的主要特點是優(yōu)化操作執(zhí)行的順序和次數(shù)，盡可能“最快”地得到查詢結(jié)果。

2 基于半連接操作的查詢優(yōu)化策略

2.1 半連接操作的原理

半連接與直接連接相比，局部數(shù)據(jù)處理將有所增加，但數(shù)據(jù)在不同站點之間的傳輸將會減少，即減少了遠(yuǎn)程數(shù)據(jù)查詢的通信時間和數(shù)據(jù)傳輸費用。簡單地說，半連接運算是將2個關(guān)系進(jìn)行連接后，再將其結(jié)果在其中一個關(guān)系的屬性上進(jìn)行投影。

假設(shè)“∏i”是在屬性集Ri上的投影，“∝”表示半連接，“∞”表示自然連接，它和半連接操作的連接條件相同，半連接操作可定義為：

也可以等價代替為：

這里∏操作僅作用于連接操作涉及的屬性上。

R2∝R1的計算結(jié)果包含了R2中所有那些至少與R1中的一個元組有連接的元組，換個說法就是，半連接R2∝R1消除了R中那些懸掛的元組。若關(guān)系R1和R2是在不同站點A和B上的2個關(guān)系，并且在第3個站點C執(zhí)行R1和R2的全連接操作，那么第2個公式有潛在的優(yōu)勢。在美國計算機(jī)公司研制的系統(tǒng)SDD－1中，先在站點B執(zhí)行∏R2操作，再將數(shù)據(jù)傳送到站點A，并進(jìn)行局部連接（獲取半連接的執(zhí)行結(jié)果），這被稱之為一個分布式連接的“壓縮階段”。當(dāng)分別在站點A和B的2個壓縮關(guān)系都傳輸?shù)侥繕?biāo)站點C后，將進(jìn)行后處理，這稱之為“處理階段”。當(dāng)在站點C處需要執(zhí)行一個全連接操作時，這種方法可以減少數(shù)據(jù)通信的開銷。對于R1和R2該查詢計劃如圖1所示。當(dāng)然，圖中R1和R2角色互換后有一個對稱的查詢計劃［1］。

圖1 利用半連接使通信開銷最小

2.2 半連接方法的操作過程和代價估算

設(shè)R1是一個半連接操作的關(guān)系，R1和R2的公共屬性為Y［3］，半連接操作的結(jié)果在第3個站點C使用。其操作過程如圖2所示。

①在B處通過對R2關(guān)系使用選擇操作得到R′2關(guān)系，再將關(guān)系R′2在連接中的公共屬性上進(jìn)行投影（＝∏R′2）得到關(guān)系R″2。② 將關(guān)系R″2傳送到站點A 處，傳輸價為C0＋C1×SIZE（Y）×val（Y［R2］），其中C0是在站點A與站點B間傳輸一次的固定開銷，單位為s，C1是單位數(shù)據(jù)傳輸所需要的代價，SIZE（Y）表示B的長度，val（Y［R2］）表示關(guān)系R2在B上不同分量值的個數(shù)。③在站點A處計算R1的半連接結(jié)果。④將R′從站點A傳送到站點B，傳輸開銷為C0＋C1×SIZE（R1）×Card（R′），其中，Card（R′）為關(guān)系R′中元組的個數(shù)。⑤在站點B上執(zhí)行JOIN操作。⑥結(jié)束。

圖2 半連接方法的操作過程

2.3 應(yīng)用舉例

現(xiàn)有2個結(jié)點上的關(guān)系模式分配如表1所示。

表1 關(guān)系分配

假設(shè)醫(yī)院整形科有一位專家懷疑某位病人的weight（體重）和type＿of＿work（工作種類）結(jié)合起來，在某種可能上與該病人所患的一種特殊的骨科疾病有關(guān)。為了進(jìn)行調(diào)查，專家想要檢測1月1號入住整形科治療且體重超標(biāo)的患者的信息。該調(diào)查涉及到HOSPITALIZATION關(guān)系和SURVEY關(guān)系的查詢處理［7］?，F(xiàn)在采用半連接的方法進(jìn)行查詢，結(jié)果提交到醫(yī)院站點處，其步驟如下：

步1 對HOSPITALIZATION關(guān)系執(zhí)行選擇操作（條件是dept＝ ‘骨科’and check＿in＿time＞‘2014－1－1’）；將執(zhí)行選擇操作后的關(guān)系HOSPITALIZATION在屬性pat＿name上投影，其結(jié)果是300個元組的關(guān)系R。

步2 將關(guān)系R傳送至社區(qū)護(hù)理站點，其傳送代價為300×ta（傳送開銷）。

步3 對SURVEY關(guān)系執(zhí)行選擇操作（條件是weight＞55），其結(jié)果有1000個元組；將關(guān)系R與受限制的關(guān)系SURVEY進(jìn)行半連接，生成了100個元組；將該100個元組在所需的屬性上投影：處理開銷為300×1000×ct（每個元組的比較代價）＋100×cc（代價／元組連接）。

步4 將結(jié)果傳送至醫(yī)院站點：傳送開銷為100×3ta。

步5 在站點醫(yī)院處與受限制關(guān)系HOSPITALIZATION作連接操作，處理開銷為300×100×ct＋100×cc。

因此，總開銷為600×ta＋330000×ct＋200×cc。

若使用連接操作代替半連接操作，步驟如下：

步1 將關(guān)系HOSPITALIZATION在3個屬性上進(jìn)行投影后傳送至社區(qū)護(hù)理站點。傳輸開銷＝300×3ta。

步2 在社區(qū)護(hù)理站點與受限關(guān)系SURVEY作連接操作，處理開銷＝300×1000×ct＋100×cc。

步3 將結(jié)果傳送至醫(yī)院，傳送開銷＝100×5ta。

因此，總開銷為1400×ta＋300000×ct＋100×cc。

由此可見，使用半連接操作可以將連接的傳輸開銷減少一半，若傳輸開銷遠(yuǎn)遠(yuǎn)大于處理開銷，則使用半連接操作比直接連接操作的總開銷少［6］。

3 二次半連接拼接算法

半連接方式雖然減少了通信數(shù)據(jù)量，但沒有使通信數(shù)據(jù)量達(dá)到最小，為了解決這個問題，下面對半連接方式進(jìn)行改進(jìn)，即進(jìn)行二次半連接拼接方式來進(jìn)一步減少數(shù)據(jù)的傳輸量［4－5］。關(guān)系R1和R2的二次半連接拼接算法操作過程如下：

1）在站點B上對關(guān)系R2進(jìn)行投影 ∏R2得到R′2關(guān)系。

2）將關(guān)系R′2傳送到A站點，與關(guān)系R1進(jìn)行一次半連接操作，得到關(guān)系R′（R′＝R1∝∏R2）。

3）對關(guān)系R′進(jìn)行投影∏R′。

4）將結(jié)果關(guān)系∏R＇傳送到站點B處，同時需要按公共屬性Y進(jìn)行排序。

5）在站點B處進(jìn)行二次半連接操作R2∝（∏R′），得到結(jié)果關(guān)系R″。

6）將關(guān)系R″按屬性Y進(jìn)行排序，傳送到請求站點C處，并按照排序結(jié)果進(jìn)行簡單的拼接（只保留一個重復(fù)屬性，不必再進(jìn)行自然連接）。

4 實例分析

關(guān)系R1和關(guān)系R2分別如表2和表3所示。

令y＝R2.pat＿name，在站點A完成一次半連接操作，得到R′＝R1∝（∏y（R2）），如表4所示。

在站點B進(jìn)行二次半連接操作R2∝（∏y（R′）），并進(jìn)行排序后得到結(jié)果關(guān)系R″如表5所示。

表2 關(guān)系R1

表3 關(guān)系R2

表4 關(guān)系R′

這種算法雖然也有二次通信過程，卻對半連接算法進(jìn)行了優(yōu)化。該查詢方案的總開銷為：

而采用半連接查詢的總開銷為：

可見，采用二次半連接拼接算法將R′關(guān)系縮減為∏y（R′）后傳輸，完成二次半連接，進(jìn)一步減少了網(wǎng)絡(luò)上的通信數(shù)據(jù)量。顯而易見，size（x）×val（Y［R′］）≤size（R′）×Card（R′），節(jié)省了網(wǎng)絡(luò)傳輸開銷，從而實現(xiàn)了分布式查詢操作的優(yōu)化。并且在站點A上的結(jié)果關(guān)系R′與站點B上的結(jié)果關(guān)系R″形成了一一對應(yīng)，在站點C上只需對它們進(jìn)行簡單的拼接，就能得到所需的查詢結(jié)果。因此，二次半連接拼接算法優(yōu)化了連接查詢，縮減了通信費用，充分提高了連接查詢的效率。

表5 關(guān)系R"

5 結(jié)語

在分布式數(shù)據(jù)庫系統(tǒng)中，連接操作是代價較高且最常用的一種操作，也是影響系統(tǒng)查詢處理效率的關(guān)鍵因素。筆者結(jié)合分布式整形管理系統(tǒng)實例采用半連接查詢優(yōu)化技術(shù)，有效地減少了中間結(jié)果的傳輸，獲得了查詢優(yōu)化。而二次半連接拼接算法更加高效且簡便，可以更大限度地縮減網(wǎng)絡(luò)上的通信處理量，有效地降低分布式系統(tǒng)的總開銷，在處理遠(yuǎn)程站點間海量信息查詢領(lǐng)域里有更明顯的性能優(yōu)勢和實用性。

［1］ （美）Garcia－Molina H.數(shù)據(jù)庫系統(tǒng)實現(xiàn) ［M］.楊冬青，吳愈青，包小源，等譯 .北京：機(jī)械工業(yè)出版社，2010.

［2］ 仝武寧，冉崇善，李宏斌 .半連接查詢優(yōu)化算法的研究 ［J］.計算機(jī)工程與設(shè)計，2011，32（3）：972－975.

［3］ 陳戈，施麗，李也白 .基于半連接的分布式查詢優(yōu)化技術(shù)研究 ［J］.計算機(jī)與現(xiàn)代化，2011（12）：106－108.

［4］ 張偉，劉萬軍 .分布式數(shù)據(jù)庫中半連接查詢優(yōu)化算法的改進(jìn) ［J］.計算機(jī)系統(tǒng)應(yīng)用，2009（9）：57－60.

［5］ 楊旭超 .基于半連接的分布式數(shù)據(jù)庫查詢優(yōu)化算法探討 ［J］.計算機(jī)時代，2012（2）：16－19.

［6］ 張時鵬，陶世群 .大規(guī)模數(shù)據(jù)庫的一種新的分布式查詢優(yōu)化算法：二分劈開縮減計算機(jī)工程與設(shè)計，1998，19（4）：62－65.

［7］ Yoshikawa M，Kambayashi Y.ProcessingInequality Queries Based on Generalized Semi－Joins ［A］.Proceedings of the lOth International Conference on Very LargeData Bases ［C］.1984：416－428.