半連接查詢優化技術研究

倪興旺 （安慶職業技術學院電子信息系，安徽 安慶246003）

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

1 分布式數據庫系統中查詢優化的基本方法

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

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

2 基于半連接操作的查詢優化策略

2.1 半連接操作的原理

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

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

也可以等價代替為：

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

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

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

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

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

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

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

2.3 應用舉例

現有2個結點上的關系模式分配如表1所示。

表1 關系分配

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

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

步2 將關系R傳送至社區護理站點，其傳送代價為300×ta（傳送開銷）。

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

步4 將結果傳送至醫院站點：傳送開銷為100×3ta。

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

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

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

步1 將關系HOSPITALIZATION在3個屬性上進行投影后傳送至社區護理站點。傳輸開銷＝300×3ta。

步2 在社區護理站點與受限關系SURVEY作連接操作，處理開銷＝300×1000×ct＋100×cc。

步3 將結果傳送至醫院，傳送開銷＝100×5ta。

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

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

3 二次半連接拼接算法

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

1）在站點B上對關系R2進行投影 ∏R2得到R′2關系。

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

3）對關系R′進行投影∏R′。

4）將結果關系∏R＇傳送到站點B處，同時需要按公共屬性Y進行排序。

5）在站點B處進行二次半連接操作R2∝（∏R′），得到結果關系R″。

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

4 實例分析

關系R1和關系R2分別如表2和表3所示。

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

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

表2 關系R1

表3 關系R2

表4 關系R′

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

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

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

表5 關系R"

5 結語

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

［1］ （美）Garcia－Molina H.數據庫系統實現 ［M］.楊冬青，吳愈青，包小源，等譯 .北京：機械工業出版社，2010.

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

［3］ 陳戈，施麗，李也白 .基于半連接的分布式查詢優化技術研究 ［J］.計算機與現代化，2011（12）：106－108.

［4］ 張偉，劉萬軍 .分布式數據庫中半連接查詢優化算法的改進 ［J］.計算機系統應用，2009（9）：57－60.

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

［6］ 張時鵬，陶世群 .大規模數據庫的一種新的分布式查詢優化算法：二分劈開縮減計算機工程與設計，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.