趙宇蘭 柳欣

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

關(guān)鍵詞： 分布式數(shù)據(jù)庫(kù)； 站點(diǎn)依賴； 連接依賴； 片段復(fù)制

中圖分類號(hào)： TN915.1?34； TP311.133.1 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）05?0028?05

0 引 言

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

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

3 實(shí)驗(yàn)設(shè)計(jì)與實(shí)驗(yàn)結(jié)果分析

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

使用LUBM工具分別生成50，150，300所大學(xué)的測(cè)試數(shù)據(jù)，并在Hadoop集群工作站中部署測(cè)試數(shù)據(jù)，使測(cè)試數(shù)據(jù)的分布滿足站點(diǎn)依賴。分別從LUBM的14個(gè)標(biāo)準(zhǔn)查詢中選取其中6個(gè)查詢語(yǔ)句進(jìn)行測(cè)試實(shí)驗(yàn)。LUBM數(shù)據(jù)集文件大小如表5所示。

本實(shí)驗(yàn)重點(diǎn)比較PD算法、JD算法和R*算法在數(shù)據(jù)集LUBM（50）、LUBM（150）和LUBM（300）上的查詢性能。通過(guò)比較6個(gè)標(biāo)準(zhǔn)查詢的計(jì)劃生成代價(jià)和查詢響應(yīng)時(shí)間，驗(yàn)證算法的有效性。每個(gè)算法執(zhí)行5次，取其均值。對(duì)比實(shí)驗(yàn)結(jié)果如表6～表8所示。

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

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

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

4 結(jié) 語(yǔ)

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

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

參考文獻(xiàn)

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

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

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

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

[5] 陳鐘，葉雪梅，青憲，等.一種改進(jìn)的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，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ù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用[M].3版.北京：科學(xué)出版社，2012：123?127.

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

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

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