分布式數(shù)據(jù)庫(kù)查詢處理和優(yōu)化算法

摘 要：隨著大數(shù)據(jù)時(shí)代的到來(lái)和云服務(wù)的發(fā)展，分布式數(shù)據(jù)庫(kù)系統(tǒng)（DDBS）的應(yīng)用越來(lái)越普遍化，分布式數(shù)據(jù)庫(kù)系統(tǒng)是通過(guò)分布式查詢處理與分布式數(shù)據(jù)庫(kù)（DDB）交互的綜合性應(yīng)用。無(wú)論是集中式數(shù)據(jù)庫(kù)系統(tǒng)，還是分布式數(shù)據(jù)庫(kù)。數(shù)據(jù)的查詢處理都貫穿于整個(gè)應(yīng)用項(xiàng)目的始終，而查詢處理的優(yōu)化也就顯得非常重要。分布式數(shù)據(jù)庫(kù)的數(shù)據(jù)具有分布性和冗余度的特點(diǎn)。這樣在處理查詢優(yōu)化時(shí)一些技術(shù)的實(shí)現(xiàn)和問(wèn)題的思考就相對(duì)復(fù)雜。本文從分布式數(shù)據(jù)庫(kù)查詢處理基本原理出發(fā)，對(duì)各優(yōu)化策略和算法進(jìn)行了闡述，并且針對(duì)性的提出了各個(gè)算法選擇的思路和途徑。

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

中圖分類號(hào)：TP311.13

分布式數(shù)據(jù)庫(kù)系統(tǒng)是在集中式數(shù)據(jù)庫(kù)技術(shù)的基礎(chǔ)上結(jié)合計(jì)算機(jī)網(wǎng)絡(luò)相關(guān)技術(shù)，與集中式數(shù)據(jù)庫(kù)的最大區(qū)別是：分布式數(shù)據(jù)庫(kù)中的數(shù)據(jù)是分散性存儲(chǔ)在網(wǎng)絡(luò)中不同場(chǎng)所（結(jié)點(diǎn)），并且每個(gè)場(chǎng)地的數(shù)據(jù)庫(kù)都有獨(dú)立處理能力。并且可以在局部完成功能應(yīng)用，除此之外，每個(gè)場(chǎng)地也要參與全局應(yīng)用程序的執(zhí)行，全局應(yīng)用程序是通過(guò)已有的網(wǎng)絡(luò)拓?fù)溥M(jìn)行通信來(lái)訪問(wèn)各個(gè)場(chǎng)地的數(shù)據(jù)。在實(shí)際應(yīng)用和操作當(dāng)中，其實(shí)是感覺(jué)不到這個(gè)分布式網(wǎng)絡(luò)存在的，操作的仍然是一個(gè)整體數(shù)據(jù)庫(kù)系統(tǒng)[1]，這說(shuō)明，分布式數(shù)據(jù)庫(kù)物理上是分散各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)上的，但邏輯上仍是同一數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)集。這樣就導(dǎo)致了在優(yōu)化處理過(guò)程中與集中數(shù)據(jù)庫(kù)系統(tǒng)的一些區(qū)別：

在集中式數(shù)據(jù)庫(kù)中，查詢優(yōu)化是基于關(guān)系代數(shù)的優(yōu)化整合，是一元運(yùn)算符運(yùn)算，主要目標(biāo)是盡量減少數(shù)據(jù)冗余。

在分布式數(shù)據(jù)庫(kù)中，網(wǎng)絡(luò)數(shù)據(jù)的異步傳輸通信會(huì)有一定的代價(jià)，是二元運(yùn)算符操作。需要通過(guò)冗余數(shù)據(jù)提高系統(tǒng)可靠性，從而改善系統(tǒng)性能。

基于分布式數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)的分散性和冗余性，決定了其查詢處理的優(yōu)化也具有一定的復(fù)雜性。在實(shí)際應(yīng)用當(dāng)中，分布式查詢處理和優(yōu)化在整個(gè)項(xiàng)目周期中對(duì)工程質(zhì)量的保證也是非常重要的環(huán)節(jié)。

1 分布式數(shù)據(jù)庫(kù)查詢處理代價(jià)分析

分布式數(shù)據(jù)庫(kù)的查詢處理操作是基于多點(diǎn)進(jìn)行的數(shù)據(jù)傳遞，這樣的數(shù)據(jù)查詢也是并行化處理的一種。分布式數(shù)據(jù)庫(kù)查詢優(yōu)化的目標(biāo)是確保整個(gè)傳輸處理成本盡可能的小，主要包括CPU處理成本、I/O和通信開銷[2]。對(duì)于不同的網(wǎng)絡(luò)拓?fù)漕愋涂梢栽O(shè)計(jì)不同的查詢處理算法。主要分兩種情況考慮：

（1）在一般的遠(yuǎn)程網(wǎng)絡(luò)通信中，網(wǎng)絡(luò)傳輸?shù)耐ㄐ艜r(shí)間往往比本地局部數(shù)據(jù)處理時(shí)間要長(zhǎng)，因而可以忽略本地的數(shù)據(jù)處理時(shí)間，以網(wǎng)絡(luò)傳輸?shù)耐ㄐ艜r(shí)間為主要優(yōu)化方向，那么減少傳輸?shù)臄?shù)據(jù)量和傳輸次數(shù)即為主要目標(biāo)和途徑。

（2）在高速的局域網(wǎng)絡(luò)中，網(wǎng)絡(luò)傳輸非?？欤啾染植康奶幚頃r(shí)間就短很多。這種情況下減少局部處理時(shí)間是主要的優(yōu)化方向。

一般以響應(yīng)時(shí)間作為網(wǎng)絡(luò)傳輸?shù)囊粋€(gè)重要指標(biāo)。響應(yīng)時(shí)間包括通信和處理時(shí)間。根據(jù)網(wǎng)絡(luò)類型的不同各有側(cè)重點(diǎn)。

基于以上分析，分布式數(shù)據(jù)查詢的代價(jià)可以歸結(jié)為CPU代價(jià)、I/O和網(wǎng)絡(luò)通信代價(jià)之和。

網(wǎng)絡(luò)通訊代價(jià)和數(shù)據(jù)傳輸量和網(wǎng)絡(luò)傳輸速率相關(guān)。其公式可以估算為：

T=C0+C1*P （1）

C0為兩端通信初始化的總時(shí)間，C1為網(wǎng)絡(luò)傳輸速率，P為傳輸數(shù)據(jù)的總量。

2 分布式數(shù)據(jù)庫(kù)查詢處理過(guò)程

分布式數(shù)據(jù)庫(kù)系統(tǒng)中查詢處理需要考慮：

先將查詢轉(zhuǎn)換為等價(jià)的關(guān)系代數(shù)表達(dá)式，然后從各等價(jià)表達(dá)式中選擇最優(yōu)代數(shù)表達(dá)式進(jìn)行查詢優(yōu)化處理。

需要涉及到網(wǎng)絡(luò)各節(jié)點(diǎn)之間的數(shù)據(jù)交互，選擇最優(yōu)的節(jié)點(diǎn)路徑和數(shù)據(jù)傳輸方式。

2.1 查詢分類處理

分布式環(huán)境的查詢類型包括本地查詢、遠(yuǎn)程查詢和全局查詢，本地查詢即局部查詢，它同集中式數(shù)據(jù)庫(kù)的優(yōu)化技術(shù)一致。遠(yuǎn)程和全局查詢描述如下：

（1）遠(yuǎn)程查詢。單點(diǎn)數(shù)據(jù)的遠(yuǎn)程通信。若數(shù)據(jù)是冗余分配的，要減少查詢處理的通信代價(jià)應(yīng)該盡可能的選擇從發(fā)出查詢的節(jié)點(diǎn)最近的節(jié)點(diǎn)上的數(shù)據(jù)或者數(shù)據(jù)片作為查詢對(duì)象

（2）全局查詢。多點(diǎn)數(shù)據(jù)處理，其過(guò)程為：首先要確定查詢對(duì)象，然后根據(jù)可用訪問(wèn)路徑和必要的算法確定二元操作連接以及并操作的次序，最后確定執(zhí)行節(jié)點(diǎn)（站點(diǎn)），需要考慮通信代價(jià)、執(zhí)行效率以及查詢速度，選擇原則為：盡量選擇距離提供站點(diǎn)數(shù)據(jù)的站點(diǎn)較近的站點(diǎn)；另外盡量選擇較空閑的站點(diǎn)執(zhí)行查詢。

總之，選擇最佳的查詢處理策略，要確定好必要的物理片段以執(zhí)行查詢，也要確定在查詢處理中各操作執(zhí)行的次序和執(zhí)行站點(diǎn)，此外，還取決于具體實(shí)現(xiàn)算法的操作。

從分布式數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)，分布式查詢處理過(guò)程有四個(gè)層次：查詢分解、數(shù)據(jù)本地化、全局優(yōu)化和局部?jī)?yōu)化，其層次結(jié)構(gòu)如圖1。

圖1 分布式查詢層次

3 分布式查詢優(yōu)化算法

分布式數(shù)據(jù)庫(kù)中查詢優(yōu)化是圍繞著查詢策略優(yōu)化和局部處理的優(yōu)化展開的。不同的結(jié)構(gòu)、不同的應(yīng)用中執(zhí)行策略也不相同，系統(tǒng)資源的消耗和傳輸響應(yīng)時(shí)間也有差異。

查詢優(yōu)化的基本方法有二：查詢轉(zhuǎn)化和查詢映射。

查詢轉(zhuǎn)化：例如：連接或投影等關(guān)系操作，執(zhí)行順序不同。

查詢映射：使用優(yōu)化算法實(shí)現(xiàn)關(guān)系操作、訪問(wèn)設(shè)備。

本文主要闡述分布式數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理半連接方法。

3.1 半連接查詢優(yōu)化基本方法

半連接方法是利用連接和投影操作產(chǎn)生的一種關(guān)系代數(shù)，主要適用于帶寬較低的遠(yuǎn)程廣域網(wǎng)絡(luò)。其基本原理是網(wǎng)絡(luò)中僅傳輸參與連接的數(shù)據(jù)，而不傳遞其他無(wú)用數(shù)據(jù)或者不參與連接數(shù)據(jù)[3]。數(shù)據(jù)傳輸為片段或整個(gè)關(guān)系，此為一種冗余方法。

設(shè)有兩個(gè)關(guān)系R和S，分別屬于不同站點(diǎn)。在屬性R.A=S.B上做半連接操作。表示為如下形式：

R∝A=BS=∏（R∞A=BS）=R∞A=B（∏B（S））

采用直接連接方法進(jìn)行R∞A=BS，通過(guò)兩站點(diǎn)關(guān)系進(jìn)行連接按公式（1）得此過(guò)程代價(jià)：

T全=C0+C1*size（B）*card（R） （2）

使用半連接方法，需要兩次數(shù)據(jù)傳輸，整個(gè)過(guò)程的代價(jià)：

T半=2C0+C1*（size（B）*val（B[s]）+size（R′）*card（R′）） （3）

sizeB表示B屬性的長(zhǎng)度；val（B[s]）表示關(guān)系S中屬性B上不同值的個(gè)數(shù)；card（R′）表示為R′的元組數(shù)。

一般情況下，有T半<

3.2 二次半連接算法

在實(shí)際應(yīng)用中，有時(shí)候請(qǐng)求結(jié)果集存放的站點(diǎn)不是請(qǐng)求站點(diǎn)，在結(jié)果集數(shù)據(jù)量較大時(shí)，會(huì)造成數(shù)據(jù)傳輸網(wǎng)絡(luò)堵塞，導(dǎo)致網(wǎng)絡(luò)負(fù)載不均衡，通信次數(shù)和響應(yīng)時(shí)間增加。

二次半連接在半連接算法的基礎(chǔ)上進(jìn)行改進(jìn)，用以進(jìn)一步減少通信數(shù)據(jù)量，提高各站點(diǎn)通信并行性。其算法如下圖：

圖2 二次半連接算法

（1）在站點(diǎn)B做關(guān)系S在R和S連接屬性B的投影∏B（S）。

（2）將∏B（S）發(fā)送到站點(diǎn)A。

（3）站點(diǎn)A依據(jù)接收到的投影值計(jì)算半連接結(jié)果R′=R∞A=B∏B（S）。

（4）R′的投影為∏A（R′）。

（5）發(fā)送∏A（R′）到站點(diǎn)B。

（6）在B站點(diǎn)執(zhí)行∏A（R′）∞A=BS連接操作。

二次半連接算法在請(qǐng)求站點(diǎn)時(shí)比半連接算法增加一次連接過(guò)程，可以為A、B屬性進(jìn)行排序，在所屬的站點(diǎn)也進(jìn)行排序或者索引用以減少連接的開銷，這樣在請(qǐng)求站點(diǎn)傳輸數(shù)據(jù)的時(shí)候，按屬性傳輸可以減少請(qǐng)求站點(diǎn)連接時(shí)間。在大型的分布式數(shù)據(jù)庫(kù)系統(tǒng)中，二次半連接算法在傳輸量和響應(yīng)時(shí)間的性能優(yōu)化上相比版連接算法效果更明顯。

3.3 其他算法

分布式數(shù)據(jù)庫(kù)中除了半連接算法還有許多其他的優(yōu)化算法。如：利用半連接縮減元組大小和減少數(shù)據(jù)傳輸?shù)腟DD-1算法的優(yōu)化、基于遺傳算法的優(yōu)化、基于查詢圖和收益代價(jià)比因子的貪心算法的優(yōu)化和粗糙集的查詢優(yōu)化等。

4 結(jié)束語(yǔ)

分布式查詢優(yōu)化算法的研究重點(diǎn)是如今高速發(fā)展的分布式應(yīng)用系統(tǒng)和云計(jì)算平臺(tái)。本文分析了分布式數(shù)據(jù)庫(kù)查詢優(yōu)化處理的原理和過(guò)程，并針對(duì)其主要代價(jià)進(jìn)行分析，基于查詢優(yōu)化的主要因素，對(duì)具體問(wèn)題選擇合適的優(yōu)化算法。綜合考慮，選擇代價(jià)最小的優(yōu)化方案來(lái)進(jìn)行處理。

此外，雖然分布式數(shù)據(jù)庫(kù)系統(tǒng)的環(huán)境是復(fù)雜的，但隨著Web的發(fā)展及其技術(shù)內(nèi)容的綜合性也越來(lái)越豐富，對(duì)于研究分布式數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化技術(shù)也會(huì)越來(lái)越優(yōu)秀，即使在今后的發(fā)展中還存在許多問(wèn)題需要研究和解決。隨著物聯(lián)網(wǎng)和大數(shù)量的不斷發(fā)展，分布式查詢優(yōu)化技術(shù)的發(fā)展必將越來(lái)越完善。

參考文獻(xiàn)：

[1]于秀霞，趙建平.分布式數(shù)據(jù)庫(kù)直接連接查詢優(yōu)化算法的研究[J].長(zhǎng)春理工大學(xué)學(xué)報(bào)，2005.

[2]錢磊.分布式數(shù)據(jù)庫(kù)多連接查詢優(yōu)化算法研究[D].燕山大學(xué)，2012.

[3]孫婷婷.分布式數(shù)據(jù)庫(kù)多連接查詢優(yōu)化算法的研究[D].曲阜師范大學(xué)，2010.

作者簡(jiǎn)介：張鵬宇（1982.06-）.男，河南鄭州人，工程碩士在讀，講師，研究方向：軟件工程。

作者單位：河南職業(yè)技術(shù)學(xué)院，鄭州 450000；鄭州大學(xué)信息工程學(xué)院，鄭州 450000