王立峰

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）21-4967-02

1 緒論

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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