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

分布式數(shù)據(jù)庫查詢優(yōu)化方法【摘要】本文介紹分布式數(shù)據(jù)庫系統(tǒng)查詢優(yōu)化的目標(biāo)、策略，著重討論了一種分布式數(shù)據(jù)庫系統(tǒng)查詢優(yōu)化策略是如何影響查詢的，并對(duì)分布式數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化的典型方法進(jìn)行了分析、總結(jié)。分布式數(shù)據(jù)庫系統(tǒng)由于數(shù)據(jù)的分布和冗余使得分布式查詢處理增加了許多新的內(nèi)容和復(fù)雜性，對(duì)于一個(gè)給定的查詢，通常會(huì)有多種可能的策略，查詢優(yōu)化就是從這許多策略中找出最有效查詢計(jì)劃的一種處理過程。并針對(duì)分布式數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化，討論了三個(gè)典型的算法：INGRES算法、SystemR*算法、SDD-1算法。【關(guān)鍵詞】分布式數(shù)據(jù)庫；分布式查詢；查詢優(yōu)化；查詢處理策略；算法0引言近年來，隨著計(jì)算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)庫技術(shù)的發(fā)展，對(duì)分布式數(shù)據(jù)庫的應(yīng)用越來越廣泛；隨著應(yīng)用不斷擴(kuò)大，數(shù)據(jù)的查詢也越來越復(fù)雜，對(duì)查詢的效率要求也越來越高，因此查詢處理成為分布式數(shù)據(jù)庫系統(tǒng)中的一個(gè)關(guān)鍵性的問題［1］。在分布式數(shù)據(jù)庫中，由于數(shù)據(jù)的分布與冗余，使得查詢處理中一般需要站點(diǎn)間的數(shù)據(jù)傳遞及通信費(fèi)用，成為查詢優(yōu)化的主要矛盾；另一方面，數(shù)據(jù)的分布與冗余也增加了查詢的并發(fā)處理的可能性，從而可以縮短查詢處理的響應(yīng)時(shí)間，提高處理速度。總之，分布式查詢的規(guī)模與優(yōu)化的因素，都與集中式查詢優(yōu)化不同，因此許多數(shù)據(jù)庫專家學(xué)者致力于研究分布式數(shù)據(jù)庫查詢優(yōu)化技術(shù)這一重要課題，并且己經(jīng)在這一領(lǐng)域作了大量的工作，也找到了規(guī)律，包括一些大家公認(rèn)的經(jīng)典算法；然而由于分布式數(shù)據(jù)庫本身的靈活性，要想設(shè)計(jì)一個(gè)算法對(duì)于各種情況都是最優(yōu)的幾乎不太現(xiàn)實(shí)，只能說設(shè)計(jì)一個(gè)較優(yōu)的優(yōu)化算法，它可以解決某一類型的問題⑵。分布式數(shù)據(jù)庫中查詢優(yōu)化是一項(xiàng)復(fù)雜問題，已經(jīng)被證明屬于NP完全問題，至今都沒有得到徹底地解決，里面尚有許多問題值得研究和探討。1分布式查詢優(yōu)化的目標(biāo)分布式數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化有兩種不同的目標(biāo)：一種目標(biāo)，是以總代價(jià)最小為標(biāo)準(zhǔn)；另一種目標(biāo)，是以查詢響應(yīng)時(shí)間最短為標(biāo)準(zhǔn)，這一點(diǎn)在分布式數(shù)據(jù)庫系統(tǒng)中具有重要的意義。因?yàn)榉植际綌?shù)據(jù)庫系統(tǒng)是由多臺(tái)計(jì)算機(jī)組成的系統(tǒng)，數(shù)據(jù)的分布和冗余也增加了查詢的并行處理的可能性，從而可以縮減查詢處理的響應(yīng)時(shí)間，加快查詢處理速度。在分布式查詢優(yōu)化中也常同時(shí)使用這兩種標(biāo)準(zhǔn)，根據(jù)系統(tǒng)應(yīng)用的不同，一種作為主要標(biāo)準(zhǔn)，另一種作為輔助標(biāo)準(zhǔn)［3］。在分布式數(shù)據(jù)庫系統(tǒng)中，查詢優(yōu)化包括兩個(gè)內(nèi)容：查詢策略優(yōu)化和局部處理優(yōu)化，而查詢策略優(yōu)化尤為重要。分布式查詢策略的優(yōu)劣將直接影響計(jì)算機(jī)網(wǎng)絡(luò)資源耗費(fèi)的多少。在集中式數(shù)據(jù)庫系統(tǒng)中，查詢優(yōu)化的目的可以總結(jié)為以下三個(gè)方面：1）為每個(gè)用戶查詢尋求總代價(jià)最小的執(zhí)行策略；2） 總代價(jià)是以查詢處理期間的CPU代價(jià)和I/O代價(jià)來衡量的；3） 總代價(jià)最小就意味著查詢的響應(yīng)時(shí)間最短。從上可看出，在集中式數(shù)據(jù)庫系統(tǒng)中，一個(gè)查詢策略的選擇是以執(zhí)行查詢的預(yù)期代價(jià)為依據(jù)的。由于系統(tǒng)大都運(yùn)行在單個(gè)處理器的計(jì)算機(jī)上，所以查詢執(zhí)行總代價(jià)為CPU代價(jià)加I/O代價(jià)［4］。而在分布式數(shù)據(jù)庫系統(tǒng)中，由于數(shù)據(jù)的分布在多個(gè)不同的站點(diǎn)上，使得查詢處理中需要考慮站點(diǎn)間傳輸數(shù)據(jù)的通信費(fèi)用，所以除了考慮CPU代價(jià)和I/O代價(jià)之外，還應(yīng)該包括數(shù)據(jù)在網(wǎng)絡(luò)上的傳輸代價(jià)。所以在分布式數(shù)據(jù)庫系統(tǒng)中，常以兩種不同的目標(biāo)來考慮查詢優(yōu)化：以總代價(jià)最小為標(biāo)準(zhǔn)和以每個(gè)查詢的響應(yīng)時(shí)間最短為標(biāo)準(zhǔn)。2分布式查詢優(yōu)化的基本方法在分布式查詢處理技術(shù)中，查詢優(yōu)化有兩種基本方法：第一，是查詢轉(zhuǎn)化，即以不同的順序執(zhí)行關(guān)系操作，如連接和投影操作：第二，是查詢映射，即使用一系列高效的算法來存取各種設(shè)備和實(shí)現(xiàn)關(guān)系操作。查詢轉(zhuǎn)化是指關(guān)系運(yùn)算集合運(yùn)算順序的改變，對(duì)查詢的性能有重要影響［5］。在多站點(diǎn)下，查詢轉(zhuǎn)化可以減少通信量，從而達(dá)到減少查詢代價(jià)的目的［6］。查詢映射則是針對(duì)關(guān)系的存取方法和操作的執(zhí)行算法進(jìn)行決策。2.1查詢轉(zhuǎn)化的處理過程查詢轉(zhuǎn)化處理一般經(jīng)歷三個(gè)階段：1） 建立關(guān)系代數(shù)表達(dá)式。根據(jù)查詢問題，編寫關(guān)系代數(shù)表達(dá)式。2） 建立查詢語法樹。根據(jù)關(guān)系代數(shù)表達(dá)式，生成查詢語法樹。3） 全局優(yōu)化。按照優(yōu)化策略，對(duì)查詢語法樹進(jìn)行全局優(yōu)化。優(yōu)化策略：查詢優(yōu)化策略按以下步驟進(jìn)行：1） 將關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換成選擇串接形式。2） 盡可能把選擇和投影操作移近樹的葉端，即盡可能早地執(zhí)行選擇和投影策略，以得到較小的中間關(guān)系，減少運(yùn)算量。3） 把選擇和投影合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇和投影能同時(shí)執(zhí)行或在一次掃描中同時(shí)完成。4）將上述步驟得到的查詢語法樹的內(nèi)結(jié)點(diǎn)分組。每個(gè)二元運(yùn)算結(jié)點(diǎn)與其直接祖先的一元結(jié)點(diǎn)分為一組。如果它的子孫結(jié)點(diǎn)一直到葉結(jié)點(diǎn)都是一元運(yùn)算符，則并入該組。5）生成一個(gè)程序，每一組結(jié)點(diǎn)的計(jì)算是程序中的一步，各步的順序是任意的，只要保證任何一組不會(huì)在它的子孫組之前計(jì)算。2.2查詢優(yōu)化的三種典型算法INGRES算法INGRES算法是動(dòng)態(tài)的優(yōu)化算法。這個(gè)算法主要分為兩個(gè)步驟：（1） 將含有多個(gè)變量的查詢分解為一系列的只含有一個(gè)變量的單關(guān)系查詢。（2） 通過執(zhí)行其每一個(gè)單關(guān)系查詢：用啟發(fā)式的方法選擇一個(gè)初始化的執(zhí)行計(jì)劃，通過中間關(guān)系的大小來確定查詢執(zhí)