分布式數(shù)據(jù)庫查詢策略的優(yōu)化方法

王立峰

摘要：分布式數(shù)據(jù)庫是數(shù)據(jù)庫和計算機網(wǎng)絡技術有機的結合，它可以將不同區(qū)域的資源進行共享，從而有效的提高工作效率。從邏輯上講分布式數(shù)據(jù)庫是一個整體，具有冗余性和分布性，使得查詢數(shù)據(jù)變得較為麻煩，因此如何優(yōu)化分布式數(shù)據(jù)庫的查詢策略，提高其查詢效率成為該文的一個研究重點。

關鍵詞：分布式數(shù)據(jù)庫；查詢策略；優(yōu)化方法

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）21-4967-02

1 緒論

從物理上來講，分布式數(shù)據(jù)庫的數(shù)據(jù)分布在計算機的各個不同站點上，這些數(shù)據(jù)是一個邏輯的整體，同由分布式數(shù)據(jù)庫進行全局的管理。分布式數(shù)據(jù)庫的作用主要是存儲數(shù)據(jù)和方便、快捷的查詢數(shù)據(jù)，因此查詢策略的優(yōu)化已經(jīng)成為了分布式數(shù)據(jù)庫的一個核心問題。該文主要論述了分布式數(shù)據(jù)庫的查詢策略以及一些有效的優(yōu)化方法和提高策略。

2 分布式數(shù)據(jù)庫及查詢優(yōu)化分析

分布式數(shù)據(jù)庫系統(tǒng)從物理上來講是分散的，而從邏輯上來講是一個統(tǒng)一的系統(tǒng)，它是將分布在不同站點上的邏輯單位通過計算機網(wǎng)絡連接起來。按照數(shù)據(jù)模型的類型，分布式數(shù)據(jù)庫系統(tǒng)可以分為同構同質(zhì)型DDBS、同構異質(zhì)型DDBS以及異構型DDBS三種[1]。同構同質(zhì)型DDBS中多種數(shù)據(jù)庫類型采用了同樣的型號，而且數(shù)據(jù)庫內(nèi)的數(shù)據(jù)模型屬于一個類型；同構異質(zhì)型DDBS數(shù)據(jù)庫內(nèi)的數(shù)據(jù)模型采用的也是同一型號，但是數(shù)據(jù)庫類型卻不相同；異構型DDBS中的數(shù)據(jù)庫類型和數(shù)據(jù)模型均不一樣。

按照分布式數(shù)據(jù)庫的控制系統(tǒng)可以將分布式數(shù)據(jù)庫系統(tǒng)分為集中式DDBS、分散性DDBS以及可變型DDBS。集中式DDBS在一個節(jié)點上保存全局的控制信息，所以容易實現(xiàn)整個分布式系統(tǒng)的數(shù)據(jù)一致性；但是這一種分布式系統(tǒng)存在一定的單點故障，一旦存放全局控制信息的節(jié)點出現(xiàn)問題，整個分布式系統(tǒng)將不能繼續(xù)使用。分散性DDBS在每個節(jié)點上都保存了全局控制信息的一個副本，雖然這樣可以保證整個分布式系統(tǒng)的穩(wěn)定性，但是卻難以保證所有節(jié)點上數(shù)據(jù)的一致性。可變型DDBS綜合了上述兩種分布式系統(tǒng)的優(yōu)勢，只有一部分節(jié)點保存全局控制信息，這些節(jié)點被稱為主節(jié)點；沒有保存全局控制信息的節(jié)點稱為輔節(jié)點。

對分布式數(shù)據(jù)庫系統(tǒng)而言，數(shù)據(jù)庫中數(shù)據(jù)的分布性使其查詢操作比一般的數(shù)據(jù)庫更加復雜，而且目前還沒有一種能夠適用于所有分布式數(shù)據(jù)庫系統(tǒng)的有效方案。從眾多的數(shù)據(jù)查詢方法中找到一種最優(yōu)方案就成了衡量分布式數(shù)據(jù)庫系統(tǒng)的重要依據(jù)。一般而言，衡量數(shù)據(jù)查詢方法優(yōu)劣的重要依據(jù)是查詢代價和響應時間，即在數(shù)據(jù)查詢期間，數(shù)據(jù)查詢操作所耗費的處理器代價是否足夠小，數(shù)據(jù)查詢的響應時間是否足夠短。除此之外，分布式數(shù)據(jù)庫數(shù)據(jù)的分布性，使得在進行數(shù)據(jù)查詢的優(yōu)化時，還要考慮網(wǎng)絡通信因素。在對分布式數(shù)據(jù)庫的查詢策略優(yōu)化時，一般有兩種優(yōu)化目標[2]：降低查詢代價或縮短數(shù)據(jù)查詢的響應時間。查詢代價由處理器的執(zhí)行時間和輸入/輸出的處理時間兩部分組成，在降低網(wǎng)絡通信代價的同時可以減小查詢代價，從而起到優(yōu)化分布式數(shù)據(jù)庫查詢操作的作用。分布式數(shù)據(jù)庫能夠進行數(shù)據(jù)的并行查詢，并行處理操作降低了查詢時間。

在分布式數(shù)據(jù)庫系統(tǒng)中，查詢操作主要有遠程查詢、本地查詢以及全局查詢?nèi)N類型。本地查詢只在本節(jié)點上查詢數(shù)據(jù)庫數(shù)據(jù)，遠程查詢可能在其他節(jié)點上查詢數(shù)據(jù)，全局查詢會在多個節(jié)點上查詢數(shù)據(jù)，所以可以認為是局部查詢和全局查詢的結合。遠程查詢和全局查詢會查詢其他節(jié)點上的數(shù)據(jù)，所以會涉及到網(wǎng)絡通信，研究查詢優(yōu)化算法時，這二者是經(jīng)常需要研究的該節(jié)點。進行遠程查詢時，由于不同節(jié)點的通信代價不同，所以選擇不同的分布式數(shù)據(jù)庫節(jié)點可能會得到不同的查詢效率，如何選擇分布式節(jié)點以得到最小的查詢代價，就是查詢優(yōu)化的一個重要問題。全局查詢會涉及到多個節(jié)點，比遠程查詢更復雜；為使執(zhí)行全局查詢時得到較好的優(yōu)化結果，通常要完成四種優(yōu)化策略[3]：（1） 數(shù)據(jù)副本個數(shù)的確定。分布式數(shù)據(jù)庫的數(shù)據(jù)一般是冗余存儲的，即一份數(shù)據(jù)可能保存到多個分布式節(jié)點上。如果一個查詢涉及到的所有數(shù)據(jù)都只有一份副本，那么此查詢過程就可以稱為非冗余具體化，否則的話就稱為冗余具體化。當查詢數(shù)據(jù)有多個副本時，不同的數(shù)據(jù)片段會影響查詢效率，所以首先需要確定查詢數(shù)據(jù)的副本個數(shù)。（2） 確定操作順序。分布式數(shù)據(jù)查詢一般包括投影、選擇以及排序等操作，選擇和投影操作會從全部數(shù)據(jù)集中選擇一小部分數(shù)據(jù)，會減少查詢的數(shù)據(jù)量，所以一般可以先執(zhí)行；連接等查詢操作會增加數(shù)據(jù)量，而且會涉及到多個分片，所以一般后執(zhí)行。（3） 確定執(zhí)行方法和執(zhí)行節(jié)點。有的操作會產(chǎn)生比較大的時間開銷或代價，所以可以選擇其替代方案；同時要盡量選擇系統(tǒng)空閑、效率比較高的節(jié)點執(zhí)行查詢操作。

分布式數(shù)據(jù)庫查詢操作從過程上分為四層[4]：分布式數(shù)據(jù)查詢分解、數(shù)據(jù)庫數(shù)據(jù)的本地化、全局優(yōu)化以及局部優(yōu)化。

作為分布式數(shù)據(jù)庫查詢優(yōu)化的第一層，查詢分解（query decomposition）的作用是將全局模式中轉換為SQL語句。數(shù)據(jù)庫數(shù)據(jù)的本地化（data loclization）根據(jù)數(shù)據(jù)庫的分片信息，把全局查詢轉換為數(shù)據(jù)庫分片上的查詢，從而實現(xiàn)全局查詢操作的本地化。全局優(yōu)化（global optimization）從本地化查詢中找到一個最佳的查詢次序，以盡量降低查詢的代價；在全局優(yōu)化過程中，對數(shù)據(jù)庫表的連接操作進行優(yōu)化將是一個重要方向；經(jīng)過全局優(yōu)化后，原來的數(shù)據(jù)會變?yōu)橐粋€經(jīng)過優(yōu)化的、數(shù)據(jù)庫分片上的關系代數(shù)查詢。局部優(yōu)化（local optimization）在每個分布式節(jié)點上執(zhí)行數(shù)據(jù)分片的查詢，并進行此節(jié)點上的優(yōu)化。這四層在分布式數(shù)據(jù)查詢優(yōu)化上起到的作用是不盡相同的，第二層和第三層是優(yōu)化的核心；不論是哪層的優(yōu)化操作，都離不開對連接操作的優(yōu)化，連接操作由于會涉及到在多個節(jié)點間進行數(shù)據(jù)傳輸，所以會有較大的網(wǎng)絡通信開銷，當前處理連接操作的優(yōu)化算法主要分為基于連接的查詢優(yōu)化算法和基于非連接的查詢優(yōu)化算法。

3 基于哈希算法的分布式查詢優(yōu)化方法

分布式數(shù)據(jù)庫的數(shù)據(jù)關系一般會分布到不同節(jié)點上，如果要對兩個關系做連接操作，最佳情況是盡可能少的傳輸數(shù)據(jù)；只要節(jié)點上存儲的數(shù)據(jù)和應用的相關性越大，連接操作所涉及的數(shù)據(jù)傳輸就越小，這種依賴關系稱為“站點依賴”。如果兩個關系不滿足站點依賴，就需要先將元組個數(shù)少的那個關系復制到另外一個關系所在的節(jié)點上，然后進行連接操作。如果兩個關系元組個數(shù)都很多，那么就需要對它們進行數(shù)據(jù)分片，Hash算法是一種有效的數(shù)據(jù)分片方法。

Hash算法對要進行連接操作的某屬性進行運算，計算此關系中所有元組的Hash值，并把Hash值相同的元組放到同一個節(jié)點上，在每個節(jié)點上的關系片段都滿足站點依賴關系。最簡單的Hash函數(shù)是對關系進行取模運算，并將Hash值為奇數(shù)的元組劃分到同一節(jié)點，Hash值為偶數(shù)的元組分到其他節(jié)點。對于多個關系的運算，Hash算法會首先分析這些關系在某一屬性列上的元組值，如果多數(shù)元組值呈現(xiàn)奇偶均勻分布，那么就可以對這些關系進行模2取余操作，并按照簡單Hash函數(shù)的元組劃分策略進行分配。如果在這一屬性列上的元組值呈現(xiàn)大小寫字母均勻分布，那么可以類似的將Hash值為大寫字母的元組分配到一個站點，Hash值為小寫字母的元組分配到另外一個站點。

當分布式數(shù)據(jù)庫關系的個數(shù)多于兩個時，利用Hash算法劃分元組的情況更加復雜。以三個關系R1、R2以及R3為例，它們的元組可能分布在兩個、三個甚至更多的節(jié)點上；元組分布的節(jié)點越多，越難以選擇合適的Hash函數(shù)，此處先考慮兩個節(jié)點的情況。當只有兩個節(jié)點時，這三個關系的連接可能是相同屬性列的連接，也可能是不同屬性列的連接；當對相同屬性列進行連接時相對簡單，可以先求得元組在某一屬性列上的Hash值，然后對這三個關系進行劃分，得到滿足站點依賴關系的分布式數(shù)據(jù)。當對不同屬性列進行連接操作時，由于連接操作是在兩個不同屬性上進行的，所以只選擇一個Hash函數(shù)會得到兩組不同、可能有沖突的Hash值，也就是說一個關系上的同一元組，根據(jù)不同的屬性列得到的分配節(jié)點可能不同，既可能被分配到節(jié)點1，也可能被分配到節(jié)點2，無疑會造成困擾。對這種問題的解決方法是[5]：以某一屬性列作為關鍵詞，對其做Hash運算后，分別將關系R1、R2分配到節(jié)點1和節(jié)點2上，然后再用同一個Hash函數(shù)對另外一個屬性列做Hash運算，并分別將關系R2、R3分配到節(jié)點1和節(jié)點2上；此時關系R2上的元組雖然可能分布在節(jié)點1和節(jié)點2上，但R1和R3都完全分布在一個節(jié)點上，使占原來2/3的數(shù)據(jù)完全滿足站點依賴關系，從而提高了分布式數(shù)據(jù)查詢的效率。對于多于三個的關系時，對相同屬性的連接操作也比較簡單；當要連接的是不同的屬性時，可以先對要連接的屬性列進行分組，再對每組的屬性按照上面的方法進行連接即可。

4 結論

本文首先講述了分布式數(shù)據(jù)庫系統(tǒng)，并分析了分布式數(shù)據(jù)庫系統(tǒng)中可以進行查詢優(yōu)化之處，最后對分布式查詢的方法進行了優(yōu)化，提出一種基于哈希算法的分布式查詢優(yōu)化方法；本文提出的基于哈希算法的分布式查詢優(yōu)化方法可以有效優(yōu)化分布式數(shù)據(jù)庫查詢效率，對后續(xù)研究有一定的參考價值。

參考文獻：

[1] 朱建生，汪健雄，張軍鋒.基于NoSQL數(shù)據(jù)庫的大數(shù)據(jù)查詢技術的研究與應用[J].中國鐵道科學，2014，1（16）.

[2] 于洪濤，錢磊.一種改進的分布式查詢優(yōu)化算法[J].計算機工程與應用，2013，6（8）.

[3] 趙榮.分布式數(shù)據(jù)庫查詢優(yōu)化方法[J].科技視界，2013，5（28）.

[4] 何愛華，戚曉明.半聯(lián)接計劃的全局查詢優(yōu)化策略研究[J].重慶科技學院學報：自然科學版， 2012，5（1）.

[5] 鄧松，林為民，張濤，馬媛媛.基于禁忌GEP的分布式數(shù)據(jù)庫查詢優(yōu)化算法[J].計算機與數(shù)字工程，2013，10（17）.