基于連接依賴信息的分布式連接查詢優(yōu)化算法

趙宇蘭 柳欣

摘 要： 分析分布式數(shù)據庫中站點依賴算法和片段復制算法的特性，提出基于連接依賴信息的多連接查詢優(yōu)化算法。該算法中，連接依賴信息用于邏輯判定基于多個站點的連接查詢是否對站點依賴，以避免不必要的通信代價；片段復制用于重新分布站點數(shù)據，確保局部連接處理滿足站點依賴；利用SQL應用的本地性和站點間多線程的高度并行性以縮減網絡通信代價和局部計算代價。實驗結果證明了該算法的有效性。

關鍵詞： 分布式數(shù)據庫； 站點依賴； 連接依賴； 片段復制

中圖分類號： TN915.1?34； TP311.133.1 文獻標識碼： A 文章編號： 1004?373X（2016）05?0028?05

0 引 言

分布式環(huán)境下的連接查詢優(yōu)化是當今數(shù)據庫理論研究的一個熱點問題。由于分布式數(shù)據庫中數(shù)據的冗余性和數(shù)據分布的復雜性，全局查詢往往涉及多個站點上的關系或關系片段，此時不僅要考慮站點之間數(shù)據傳輸所產生的通信代價，還要兼顧基于站點的局部處理代價，這無疑增加了查詢處理和優(yōu)化技術的難度。為了有效地處理分布式連接操作，國內外文獻提出了多種算法，通常分為半連接算法和直接連接算法。典型的半連接算法有SDD?1算法[1]、AHY算法[2]、雙向半連接算法[3?4]等，這些算法通過半連接操作縮減站點間數(shù)據的傳輸量，但由于需要二次數(shù)據傳輸，當二次數(shù)據傳輸?shù)目偭坎恍∮趥鬏斦军c上某個關系或關系片段的數(shù)據量時，算法將失效。典型的直接連接算法有R*算法[5?6]、利用站點依賴信息（Placement Dependency，PD）的算法[7]等。R*算法直接處理連接操作，通過窮舉所有可能的連接策略，將全局連接操作分解為每個站點上的局部連接操作，最后選擇一個最優(yōu)的連接策略作為執(zhí)行策略，但窮舉的計算方法耗時長，且要傳輸?shù)年P系或關系片段的數(shù)據量大時該算法的處理效率將不理想。PD算法彌補了R*算法的不足，該算法有效利用了局部查詢的本地化特征，在一個設計精良的分布式數(shù)據庫中可以實現(xiàn)全局連接查詢的零數(shù)據傳輸處理。但如果全局連接操作引用的關系片段在不同站點中存在相關聯(lián)的元組時，該算法將失效。

本文借鑒了PD算法在并行處理方面的優(yōu)越性，提出了基于連接依賴信息（Join Dependency，JD）的連接查詢優(yōu)化算法。該算法利用連接依賴信息判斷基于多站點的數(shù)據分布是否符合站點依賴，以降低遠程訪問的次數(shù)，對于不滿足連接依賴的站點數(shù)據，則采用片段復制方法重新分布數(shù)據，確保其適用站點依賴算法。站點間關系或者關系片段的復制時間開銷是該算法的惟一通信代價，但是這種代價會被站點間多線程的高度并行所彌補。

3 實驗設計與實驗結果分析

實驗使用的硬件環(huán)境為Intel? CoreTM i5?3230M CPU @2.60 GHz（2 600 MHz），內存為4 GB，SCSI硬盤1 TB，轉速為10 000 r/min。操作系統(tǒng)為GNU/Linux，開發(fā)環(huán)境為JDK1.6，在實驗環(huán)境中，采用上述所列配置Hadoop集群工作站，共計3臺，其中1臺為MapReduce主節(jié)點，作為HDFS名稱節(jié)點，另外2臺為MapReduce從節(jié)點，作為HDFS數(shù)據節(jié)點。

使用LUBM工具分別生成50，150，300所大學的測試數(shù)據，并在Hadoop集群工作站中部署測試數(shù)據，使測試數(shù)據的分布滿足站點依賴。分別從LUBM的14個標準查詢中選取其中6個查詢語句進行測試實驗。LUBM數(shù)據集文件大小如表5所示。

本實驗重點比較PD算法、JD算法和R*算法在數(shù)據集LUBM（50）、LUBM（150）和LUBM（300）上的查詢性能。通過比較6個標準查詢的計劃生成代價和查詢響應時間，驗證算法的有效性。每個算法執(zhí)行5次，取其均值。對比實驗結果如表6～表8所示。

從實驗對比結果可見，在數(shù)據量較小的情況下，基于JD算法的計劃生成代價稍劣于PD算法，但要優(yōu)于[R*]算法。隨著數(shù)據量的增加，基于[R*]算法的查詢計劃生成代價值呈指數(shù)級增長，查詢性能急劇惡化，而JD算法的計劃生成代價仍近似于PD算法。這是由于[R*]算法不考慮站點依賴問題，需要將各站點的關系或者關系的片段分別復制到指定站點執(zhí)行局部處理，然后選擇總代價最小的策略作為最優(yōu)策略，站點間的通信代價和局部處理代價隨著數(shù)據量增加而急劇上升，查詢效率急劇下降。

下面對三種算法在數(shù)據集LUBM（300）上的查詢響應時間進行對比分析，實驗進行5次，取平均值，實驗結果如圖2所示。

由圖2可以看出，JD算法具有較好的查詢響應時間，在大數(shù)據量環(huán)境下，與PD算法的響應時間差別不大，但明顯優(yōu)于R*算法。因此，本文提出的基于連接依賴信息的連接查詢優(yōu)化算法是可行的，具有較好的尋優(yōu)效果和實際價值。

4 結 語

本文在分析利用站點依賴信息的算法和分片復制算法特性的基礎上提出了利用連接依賴信息的分布式連接查詢優(yōu)化算法。算法的測試與結果表明，在基于多站點的連接查詢中，該算法可極大地縮減網絡的通信代價和局部計算代價。尤其當基于連接查詢的大部分元組都能在本地站點找到，僅有少量元組需要從遠程站點獲取時，該算法可獲得最佳性能。反之，該算法將退化為R*算法。

由于本文提出的算法的查詢優(yōu)化過程沒有考慮查詢結果向目標站點的傳輸代價，因此在連接操作返回的元組數(shù)較大的情況下，將產生額外的通信開銷，從而給該算法帶來負面影響。

參考文獻

[1] 趙光亮.基于半連接算法的分布式數(shù)據庫系統(tǒng)查詢優(yōu)化技術[D].杭州：浙江工業(yè)大學，2013.

[2] 錢磊，于洪濤.改進的半連接查詢優(yōu)化算法[J].燕山大學學報，2012，36（2）：178?182.

[3] 魏士偉，黃文明，康亞娜，等.分布式數(shù)據庫中基于半連接的查詢優(yōu)化算法研究[J].計算機應用，2007，27（6）：34?39.

[4] 仝武寧，冉崇善，李宏斌.半連接查詢優(yōu)化算法的研究[J].計算機工程與設計，2011，32（3）：972?975.

[5] 陳鐘，葉雪梅，青憲，等.一種改進的分布式數(shù)據庫查詢優(yōu)化算法[J].計算機應用，2008，28（2）：233?237.

[6] FAN Y Y， MI X F. Distributed database system query optimization algorithm research [C]// Proceedings of 2010 3rd IEEE International Conference on Computer Science and Information Technology. Chengdu， China： IEEE， 2010： 657?660.

[7] KUMAR T V， VIKRAM S， AJAY K V. Distributed query processing plans generation using genetic algorithm [C]// Procee?dings of 2010 International Conference on Data Storage and Data Engineering. Bangalore： IEEE， 2010： 38?45.

[8] 邵佩英.分布式數(shù)據庫系統(tǒng)及其應用[M].3版.北京：科學出版社，2012：123?127.

[9] 龔浩.分布式數(shù)據庫查詢處理和優(yōu)化算法的研究[D].重慶：重慶大學，2005.

[10] 張瑞芳.分布式數(shù)據庫的查詢優(yōu)化方法設計與實現(xiàn)[D].成都：電子科技大學，2010.

[11] OSMAN R， KNOTTENBELT W J. Database system performance evaluation models： a survey [J]. Performance evaluation， 2012， 69（10）： 471?493.