1、分布式數(shù)據(jù)庫查詢優(yōu)化【摘要】本文針對分布式數(shù)據(jù)庫查詢優(yōu)化進行了分析與探討，講述了其特點，與原理供相關(guān)計算機方面人員參考?！娟P(guān)鍵字】分布式、數(shù)據(jù)、查詢、優(yōu)化一、 分布式數(shù)據(jù)庫及其特點：分布式數(shù)據(jù)庫系統(tǒng)是物理學上分散而邏輯上集中的數(shù)據(jù)庫系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)使用計算機網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位連接起來，共同組成一個統(tǒng)一大業(yè)的數(shù)據(jù)庫系統(tǒng)。因此，分布式數(shù)據(jù)庫系統(tǒng)可以看成是計算機網(wǎng)絡(luò)與數(shù)據(jù)庫系統(tǒng)的有機結(jié)合。一個分布式數(shù)據(jù)庫系統(tǒng)應(yīng)該具有如下特點：數(shù)據(jù)的物理分布性、數(shù)據(jù)的邏輯整體性、站點自治性二、 分布式數(shù)據(jù)庫查詢基本概念1. 分布式數(shù)據(jù)庫查詢優(yōu)化的研究意義：分布式查詢技

2、術(shù)主要把用戶提交的全局查詢請求翻譯為幾個相關(guān)節(jié)點都可以識別的本地查詢請求，以及把各個節(jié)點的查詢結(jié)果匯總返回的問題，它包括分布式查詢處理和分布式查詢優(yōu)化。分布式查詢處理研究整個分布式查詢處理的過程和策略；分布式查詢優(yōu)化研究查詢策略的優(yōu)化問題，即如何從多種方案中選擇查詢代價最少方案。分布式查詢處理作為分布式數(shù)據(jù)庫研究主要問題之一，它是用戶與分布式數(shù)據(jù)庫之間的接口，在分布式數(shù)據(jù)庫中由于數(shù)據(jù)的分布與冗余，使得數(shù)據(jù)在各站點間的傳輸代價成為查詢處理的主要矛盾；另一方面，數(shù)據(jù)的分布與冗余也增加了查詢的并發(fā)處理的可能性，從而可以縮短查詢處理的響應(yīng)時間，提高處理速度。因此，與集中式數(shù)據(jù)庫相比，分布式查詢處理增加

3、了不少新內(nèi)容與復(fù)雜性。2. 分布式查詢處理的層次結(jié)構(gòu)：分布式查詢處理按不同的層次執(zhí)行，符合分布式數(shù)據(jù)庫系統(tǒng)的層次結(jié)構(gòu)。分布式查詢處理可分為如下所示四個層次結(jié)構(gòu)。(1)查詢分解查詢分解是將查詢問題(如SQL語句)轉(zhuǎn)換成一個定義在全局關(guān)系上的關(guān)系代數(shù)表達式。這一層的做法與集中式DBMS相同，因為并未涉及分布問題。本層轉(zhuǎn)換所需要信息在全局概念模式中得到。(2)數(shù)據(jù)本地化數(shù)據(jù)本地化是把一個在全局關(guān)系上的查詢進行具體化到合適片段上的查詢。這一變換所需要信息在分片模式和片段的分配模式中獲得。(3)全局優(yōu)化全局優(yōu)化輸入是分片查詢，全局優(yōu)化是找出分片查詢的最佳操作次序，包括使得代價函數(shù)最小。全局優(yōu)化一個重要方

4、面是關(guān)于連接操作的優(yōu)化，全局優(yōu)化處理層輸出是一個優(yōu)化的、片段上的關(guān)系代數(shù)查詢。這層轉(zhuǎn)換所需要信息來自數(shù)據(jù)庫的統(tǒng)計信息，包括各站點片段統(tǒng)計信息、資源信息和通信信息等。(4)局部優(yōu)化局部優(yōu)化由與查詢有關(guān)片段的各個站點執(zhí)行。它由該站點上的DBMS進行優(yōu)化，采用集中式數(shù)據(jù)庫系統(tǒng)中查詢優(yōu)化的算法，所需要信息來自于局部模式。分布式查詢優(yōu)化通常在分布式查詢層次結(jié)構(gòu)中的數(shù)據(jù)本地化層和全局優(yōu)化層。數(shù)據(jù)本地化階段一般采用的是基于關(guān)系代數(shù)等價變換的優(yōu)化算法。而全局優(yōu)化階段采用的算法，可具體分為基于半連接算法的查詢優(yōu)化和基于直接連接算法的查詢優(yōu)化兩大類。3. 分布式數(shù)據(jù)庫數(shù)據(jù)庫查詢優(yōu)化的一般過程：分布式查詢處理問題是

5、由E-Wong首先提出的，分布式查詢處理的基本思想認為分布式查詢處理是數(shù)據(jù)傳遞和局部處理相交織的過程，分布式查詢處理策略由數(shù)據(jù)傳遞策略與局部處理策略組成;分布式查詢處理的過程實質(zhì)是利用數(shù)據(jù)傳遞策略和局部數(shù)據(jù)處理策略，把分布查詢轉(zhuǎn)化為局部查詢的過程。分布式數(shù)據(jù)庫中的查詢過程可分為邏輯分解、評議轉(zhuǎn)換和優(yōu)化組合幾分。分布式數(shù)據(jù)庫系統(tǒng)中，用戶可以用全局查詢評議對多個數(shù)據(jù)庫同時進行查詢，即為全局查詢。全局查詢一般經(jīng)過以下幾個過程：首先，對全局查詢進行邏輯分解成幾個子查詢，每個子查詢對應(yīng)一個局部數(shù)據(jù)；其次，若全局查詢評議與局部查詢評議不同，則進行語言的等價轉(zhuǎn)換；最后，各個子查詢的結(jié)果優(yōu)化組合后返回。不同的

6、查詢分解對應(yīng)不同的系統(tǒng)性能，因此為了達到優(yōu)化系統(tǒng)性能，需要相應(yīng)查詢優(yōu)化器來確定一個相對較好的執(zhí)行計劃，最后啟動查詢計劃。4. 分布式數(shù)據(jù)庫查詢優(yōu)化的衡量標準：一個查詢策略的選擇是以執(zhí)行查詢的預(yù)期代價為依據(jù)的，由集中式系統(tǒng)大都運行在單個處理器的計算機上，所以查詢執(zhí)行總代價為CPU代價加I/O代價之外。分布式查詢優(yōu)化可用CPU代價、I/O代價、通信代價3個參數(shù)來徇，總代價為三者之和。在分布式數(shù)據(jù)庫系統(tǒng)中，常以兩種不同的目標來考慮查詢優(yōu)化：1. 以總代價最小為標準，除了CPU代價和I/O代價之外，還包括數(shù)據(jù)通過網(wǎng)絡(luò)傳輸?shù)拇鷥r。2. 以每個查詢的響應(yīng)時間最短為標準。響應(yīng)時間就是從接收 查詢到完成查詢所

7、需要的時間。它既與通信時間有關(guān)，又與局部處理時間有關(guān)，而通信費用與所傳輸?shù)臄?shù)據(jù)量和通信次數(shù)成正比。5. 分布式數(shù)據(jù)的查詢優(yōu)化策略：一般來說，在分布式數(shù)據(jù)庫中的查詢優(yōu)化主要考慮以下幾種：1. 操作執(zhí)行的順序：操作執(zhí)行順序的改變主要指關(guān)系運算及集合運算的改變，它們常常對鐵性能產(chǎn)生重要的影響。2. 關(guān)系的存取方法：在關(guān)系數(shù)據(jù)庫系統(tǒng)中，關(guān)系或使用索引，如果關(guān)系中90%的要被訪問，則掃描整個關(guān)系是較好的；如果只有30%的被訪問，則使用索引是更為有效的方法。3. 操作的執(zhí)行算法（尤其是連接操作）：連接操作是將兩個關(guān)系在指定的公共屬性上以相同值為依據(jù)進行合并，連接操作通常有多種：自然連接、造價連接、外連接和

8、半連接等。4. 不同站點間數(shù)據(jù)流動的順序：在多站點中，合理地選擇數(shù)據(jù)的流向，可以大大減少通信量，以便達到減少查詢代價的目的。三、 常用的分布式數(shù)據(jù)庫的查詢優(yōu)化策略：1. 基于關(guān)系代數(shù)等價變換的優(yōu)化算法：基于關(guān)系代數(shù)等價變換的優(yōu)化算法是一種既能減少操作量又能減少操作次數(shù)的算法?；陉P(guān)系代數(shù)等價變換優(yōu)化算法的基本原理:把查詢問題轉(zhuǎn)變?yōu)殛P(guān)系代數(shù)表達式，分析得到查詢樹(語法樹)，進行從全局到片段的變換得到基于片段上的查詢樹，然后利用關(guān)系代數(shù)等價變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行選擇和投影操作。這樣，一方面可以減少其后操作的操作量，另一方面可以減少操作次數(shù)。對該查詢樹進行優(yōu)化，從而達到查詢優(yōu)化的目的。關(guān)系

9、代數(shù)等價變換規(guī)則的優(yōu)化算法:利用關(guān)系代數(shù)等價變換規(guī)則，把查詢樹中連接和合并操作盡可能上提(向樹根方向移)。選擇和投影操作盡可能下移(向樹葉方向移)到片段的定義處。這就是說，盡可能先執(zhí)行選擇和投影操作，后執(zhí)行連接和合并操作。經(jīng)過選擇和投影操作不但可以減少其后操作的操作量，而且還可以減少操作次數(shù)。2. 基于半連接操作的查詢優(yōu)化算法：基于半連接操作的查詢優(yōu)化的思想是經(jīng)過半連接操作，可減少操作關(guān)系的數(shù)據(jù)量，從而減少站點間數(shù)據(jù)的傳輸量。基于半連接操作的查詢優(yōu)化的基本思想：數(shù)據(jù)以整個關(guān)系在網(wǎng)絡(luò)中傳輸，這顯然是一種冗余的方法，在一個關(guān)系傳輸?shù)搅硪粓龅睾螅?并非每個數(shù)據(jù)都參與連接操作或都是有用，因此，不參與連

10、接的數(shù)據(jù)或無用的數(shù)據(jù)不必在網(wǎng)絡(luò)中來回傳輸?；诎脒B接的優(yōu)化策略的基于原理就是采用半連接操作，在網(wǎng)絡(luò)中只傳輸參與連接的數(shù)據(jù)。連接查詢的優(yōu)化問題幾乎是分布式數(shù)據(jù)庫的分布式查詢優(yōu)化算法的全部，在分布式數(shù)據(jù)庫中連接查詢的主要手段是半連接技術(shù)，各種不同算法的差異主要是在連接順序上，即在保證結(jié)果一致的情況下，以什么樣的順序?qū)⑦@些表連接起來最優(yōu)。優(yōu)化的對象一般數(shù)據(jù)傳輸量的總和。3. 基于直接連接操作的查詢優(yōu)化算法:基于直接連接操作的查詢優(yōu)化是一種完全在連接的基礎(chǔ)上考慮查詢處理的策略：有時直接連接也可能會產(chǎn)生好的效果，特別是當有以下情況時：a) 查詢目標表中的屬性很少，也不是某連接條件屬性。b) 半連接的縮減

11、效果較差時。究竟用直接連接還是半連接方案，取決于數(shù)據(jù)傳輸和局部處理的相對費用。一般，如果認為傳輸費用是主要的，那么采用半連接策略比較有利，如果認為局部處理費用是主要的，則采用直接連接策略比較有利。四、 SDD_1算法：1. SDD_1概述：SDD-1算法采用了半聯(lián)接程序處理聯(lián)接操作zs。它的查詢優(yōu)化就是對邏輯關(guān)系使用基本的運算(如選擇，投影，半聯(lián)接)操作來縮減。它有五個主要特征，首先，采用半聯(lián)接是最主要的，其次，各個局部站點沒有重復(fù)，也不進行分片。此外，在它的代價計算中，不考慮最后一個站點傳送代價。這是由于在它的查詢策略中，當使用半聯(lián)接來縮減操作數(shù)關(guān)系的基數(shù)，當最大限度的縮減以后，把所有關(guān)系送

12、到可執(zhí)行查詢的站點上，這個站點不一定是查詢所要求的結(jié)果站點。譬如說，若S是結(jié)果站點(經(jīng)半聯(lián)接縮減后建立的)，;是查詢要求的站點，S I可能相同，可能不同，若不相同，則還有一次傳送代價將S送到I。最后它還能同時減少最小化總時間和響應(yīng)時間。 SDD-1算法有兩部分組成:基本算法和后優(yōu)化?；舅惴ɑ谂郎剿惴?，是爬山算法的迭代。根據(jù)評估縮減程序的費用、效率、收益估算幾個因素，給出全部的半聯(lián)接縮減程序集，決定一個最有益的(收益大的)執(zhí)行策略ES，但效率不一定高，然后選擇一個裝配站點Sa，將已縮減完的關(guān)系傳送到裝配站點Sa上進行聯(lián)接;后優(yōu)化，將基本算法得到的解進行修正，以得到更合理的執(zhí)行策略。2. 基本

13、算法:(1)基礎(chǔ):已有了從查詢樹轉(zhuǎn)換的優(yōu)化模型，且所有關(guān)系己完成局部縮減。(2)方法:根據(jù)己得到的縮減關(guān)系的靜態(tài)特性表，構(gòu)造可能的半聯(lián)接縮減程序;按半聯(lián)接縮減程序的靜態(tài)特性表分別計算其費用和收益，從一組的靜態(tài)特性表中選取一個半聯(lián)接程序，設(shè)為M;以M完成縮減后，又將產(chǎn)生一組新的靜態(tài)特性表再進行計算，再從一組可取的靜態(tài)特性表中選一個半聯(lián)接程序，但是每個半聯(lián)接程序只做一次(避免導(dǎo)致縮減程序太長、效率不高);反復(fù)直到無半聯(lián)接縮減程序為止。(3)結(jié)束:以若干次迭代以后的最后縮減關(guān)系的靜態(tài)特性表為基礎(chǔ)，進行站點選擇(費用計算)，決定執(zhí)行查詢的站點(可能與查詢要求的站點不同)。后優(yōu)化:在基本算法中，每次迭代

14、時只考慮本次迭代時的“改善”，這種“改善”不一定最好。后優(yōu)化有兩種修正;(1)若最后一次半聯(lián)接程序縮減關(guān)系的所在站點恰好是被選中的查詢執(zhí)行站點，則最后一次半聯(lián)接可以取消;(2)對基本算法的主迭代所構(gòu)成的半聯(lián)接程序的流程圖進行修正。因為一開始的(或某一個)半聯(lián)接縮減程序的代價很高，如有，這時可以把S進行縮減后再進行半聯(lián)接縮減，即可修正半聯(lián)接的操作序。3. SDD-1算法總結(jié) 本文說明了SDD-1算法在分布式數(shù)據(jù)庫查詢中是如何應(yīng)用的，可以看到使用該算法可以獲得很多的收益。 SDD-1算法主要使用了半聯(lián)接技術(shù)，使得數(shù)據(jù)傳輸量最小，特別的對于幾個關(guān)系之間的聯(lián)接來說，這種半聯(lián)接策略可以擴展到一系列的半聯(lián)接步驟。 但是該算法也有一些缺陷，比如半聯(lián)接程序依賴數(shù)據(jù)庫的靜態(tài)特性;一個無收益的半聯(lián)接程序可能到最后會變成