數據庫查詢優化研究

摘要:隨著信息技術的快速發展以及人們對信息依賴程度的提高，數據庫在整個信息化建設中具有更加重要的作用。如何提高數據庫的效率。特別是數據庫查詢的效率十分關鍵。論文分別研究了分布式數據庫和并行數據庫的查詢優化方法。在分布式數據庫中，論文側重基本原理的分析，主要從基于關系代數的優化、基于直接連接查詢的優化、半連接優化、索引優化以及查詢優化搜索策略，這5個方面系統的論述了查詢優化的方法、策略。在并行數據庫部分，論文側重于常見算法的研究，主要論述了基于查詢樹的傳統優化方法、多重加權樹優化方法、語義查詢優化方法以及基于遺傳的優化方法，該4類查詢優化算法是目前并行數據庫查詢優化中應用最廣的，代表了當前的研究水平。論文研究這兩類典型的數據庫查詢優化算法，就是讓我們能了解數據庫優化的發展情況，有利于開發更加有效的查詢優化技術。

關鍵詞:分布式數據庫;并行數據庫;查詢優化技術

中圖分類號:TP312文獻標識碼:A文章編號:1009-3044(2010)21-6103-02

近年來，隨著信息技術的快速發展，數據庫技術應用越來越廣泛，已成為信息化建設的核心。目前應用最廣泛的數據庫主要有兩類，分別是分布式數據庫和并行數據庫。其中，由于網絡技術的快速發展，分布式數據庫已得到了廣泛的應用。并行數據庫在許多方面也得到了很好的應用。所以提高數據庫的效率已成為迫切的任務。其中，查詢是數據庫中最常用操作，同時也是用戶操縱、維護數據庫中的數據的唯一途徑。用戶對數據庫性能的直接感覺就是數據庫管理系統對查詢的處理是否高效、快速。查詢處理的效率在很大程度上決定了數據庫管理系統的性能。所以提高查詢效率已成為數據庫研究的熱點。

現在我們看看，查詢優化的發展:由CCA公司開發的SDD-1采用的查詢優化方法是對邏輯關系用基本的運算操作來縮減;IBM公司設計的R*采用直接連接作為查詢處理策略，同時為提高查詢效率采用了動態規劃的方法;加州大學伯克利分校研制的INGRES采用基于分解的優化算法;ORACLE是一款十分優秀的商業數據庫，采用基于代價的優化或基于規則的優化找出一個執行代價較低的執行計劃，由于在確定數掘的分布時，引入了直方圖來描述數據值的分布而不是假設數據值是均勻分布的，從而大大提高了代價估計的精確度。可見，數據庫查詢優化已得到了快速的發展，從理論研究到了實踐工程應用，并且在實際工程中的作用已經越來越重要了，特別是在實時數據庫系統中尤為突出。數據庫查詢優化已成為數據庫發展的一個重要研究方向。論文主要研究分布式數據庫的查詢優化問題，同時簡單介紹并行數據庫查詢優化的常用方法及發展趨勢。

1 數據庫查詢優化方法詳解

為了讓大家能清晰的了解數據庫查詢優化的主要方法，論文從兩個方面來研究數據庫的優化問題。首先介紹分布式數據庫的查詢優化技術，在該部分側重于方法和策略的描述，不涉及到具體的算法。然后，研究一下并行數據庫的查詢優化技術，在該部分側重于具體算法的論述。通過這兩部分內容，就能較全面的為大家展現數據庫查詢優化技術的內涵。

1.1 常見分布式數據庫查詢優化方法

在分布式數據庫中，我們進行查詢優化的主要目標就是以最小的總代價，在最短的時間內獲得所需的數據。它的實現既與通信時間有關，也與局部處理時間相關，根據不同的互連網絡狀況可以有不同的查詢優化策略。總體上，可分為5個方面。

1) 基于關系代數的優化方法:數據庫查詢操作的基礎就是關系運算，所以利用關系代數變換來實現查詢優化是目前最常見的方法。其主要原理就是通過關系代數的等價變換，從而減少查詢中的計算量，進而實現查詢的優化。主要原則就是在關系運算中盡量避免直接執行運算量較大的笛卡兒積運算，而采用先執行關系代數表達式中的選擇和投影操作，后把笛卡兒積操作之前和之后的一連串選擇和投影合并起來一起做。這樣就能減小運算量。該方法主要用于刪除無用數據，從而減小運算，主要作為預處理使用。

2) 基于直接連接查詢的優化方法:該方法的著眼點在于連接，通過研究關系的靜態屬性來構建一個最好的處理策略和連接順序。在分布式數據庫中，主要采用的優化策略為:

第一種，利用站點依賴信息來實現。就是在關系進行連接運算時，首先將同一站點上的子片段進行連接，然后再傳輸到目標站點上進行合并。該方法的主要優勢是站點間無數據傳送代價，并可利用本地索引信息加速連接。第二種是分片和復制算法。該方法就是將查詢需要的關系的片段分配到選定的站點上，然后將其它關系進行復制，目的是讓選定的站點上都搬出完整的關注，第三步就是在各站點上進行直接連接操作，最好將結合傳到目的站點，該方法的主要優勢是響應時間更短，但存在數據冗余的缺點。第三種是站點依賴和數據復制結合。該方法結合站點依賴信息和數據復制信息，減少關系片段的復制，使特定查詢能以無數據傳輸的方式進行，從而縮短響應時間。最后一種方法是采用Hash劃分策略。該方法采用Hash函數將關系根據連接屬性進行片段劃分，使得連接的兩個關系之間滿足站點依賴，以根據站點依賴方法進行連接查詢?；谥苯舆B接查詢的優化方法由于傳輸代價太大，所以只適合于查詢處理慢，傳輸快的高速局域網場合。

3) 半連接優化策略:從上述基于直接連接查詢的優化方法的論述中，我們可以看到該方法的主要缺點就是在不同站點間傳輸的數據量太大，針對這一缺點，開發出了半連接優化策略。該方法的主要特點是通過投影和連接運算可以有效的減少操作關系的大小，從而減少站點之間的數據傳輸量，以盡可能只傳輸參與連接的數據，減少了數據傳輸時間，降低了CPU和磁盤I/O代價，提高了查詢效率;但半連接也會導致通信次數的增加和局部處理時間的增加，適用于傳輸代價高而局部處理時間短的場合。該方法的主要目標是能夠有效降低站點間的數據傳輸量，從而降低網絡傳輸代價，由于半連接不具有對稱性，連接順序的不同會導致中間結果大小的不同，因此基于半連接的多關系分布式查詢優化算法的目標就是找到一個最優的半連接執行順序，使得產生的中間結果最小，以降低網絡傳輸代價，縮短查詢響應時間。

為了進一步的提高半連接優化策略的效果，還設計了雙向半連接策略和全歸約技術。其中，雙向半連接策略通過兩次半連接將關系R和S完全歸約，減少了網絡間數據傳輸的代價，適用于明確要求將關系R和S傳送到第三站點進行連接的情況。其中，全歸約技術首先將所有關系的前導屬性傳送到一個站點進行連接操作，再將連接結果中的屬性分別傳回原節點，對原關系進行歸約以得到所有的有效元組，最后將有效元組傳送到目的節點進行連接。該方法是對半連接技術的加強，其最大限度的對分布式數據庫中的關系進行了歸約，在傳輸過程中只傳送查詢結果中要包含的元組，減少了傳輸代價。全歸約算法不依賴于關系的靜態特性，不需要對靜態特性的維護，提高了準確率;不需要搜索對比所有可能的半連接操作程序，并減少了通訊代價。但當一個關系中具有多個連接屬性時，多個連接屬性投影后得到的臨時關系可能會很大，與原關系記錄數相差不多，這時傳輸代價較大。

4) 索引優化:為提高查詢的速度，通常會采用索引技術，該技術能夠減少查詢搜索的時間，從而優化查詢效果。目前在數據庫查詢優化中主要采用3類索引技術，分別是:散列索引、基于樹的索引和位圖索引。其中，由于索引表需要占用內存空間，為減小系統開銷，一般采用散列索引。散列索引的主要優勢就是索引表占用的內存空間小。曾有學者提出“通過散列表保存關系中關鍵值的上下限記錄位置，以確定一個小于整個表的掃描范圍，以此減少掃描時間。”，還有學者對散列技術進行了改進，提出了雙層的查詢優化算法和雙項的查詢優化算法。其中雙層的查詢優化方法的主要原理是:通過建立雙層散列，在散列表之上再加一次散列，以適應散列表較大時的情況。而雙項的查詢優化算法中對散列表增加了一個記錄號次下限和次上限，以更精確的定位記錄所在的區域，并減少刪除、修改操作對散列表信息及查詢優化效率的影響。

索引技術的本質就是利用添加限制條件來減少掃描的數據量，該方法對局部數據庫查詢有利，但在分布式數據庫中由于建立索引較難，所以一般不采用。

5) 查詢優化搜索策略:上述4種方法是查詢優化中最常見的方法，它們能夠有效的降低查詢處理的時間。但是如何有效的應該這些技術來實現一個最優查詢方案是十分復雜的。目前查詢策略表示主要有兩類，一類是基于圖的查詢優化，另一類是基于樹的查詢優化。其中，基于圖的查詢優化是目前最常用的搜索策略，它的主要思想是通過關系的靜態屬性計算兩個關系的連接代價，依次將圖中代價最小的兩個站點進行連接合并，直到無法繼續合并為止。如果能將查詢臺與其它優化策略如半連接結合起來，就能實現更加有效的查詢。基于樹的查詢優化主要目的是生成一棵具有最小代價的查詢樹，并可通過樹中連接操作的并行執行來進一步縮短查詢響應時間。但由于在樹的搜索算法中沒有考慮到連接執行后其它邊上的代價會發生改變的情況，即沒有考慮到當前連接對之后連接的影響，而且所采用的貪婪搜索策略并不能保證最后的總代價一定是最小的。另外，基于樹的搜索算法不適于環查詢的情況，當查詢圖中存在環路時基于樹的搜索策略無法滿足所有的連接限制條件。

目前我們采用的搜索策略主要分為3類，分別是窮盡搜索策略、隨機搜索策略以及啟發式策略。其中，窮盡搜索策略是列出所有的組合順序，并進行比較，這樣就能找到最佳的查詢方案。但該策略的最大缺陷是由于實際運算的復雜度太大，導致該策略部具有實際應用價值。隨機搜索策略就是以一個隨機狀態作為出發點，并與隨機選擇的相鄰狀態進行比較，從而獲得更加的狀態，通過反復比較就能獲得近似的最佳情況。該策略的主要優點是算法的空間復雜度較低，滿足工程要求，但主要缺點是時間復雜度很難確定。常用的算法有代改進算法、模擬退火算法。其中，啟發式策略具有多項式級的時間和空間復雜度，但其生成的可能并不是最優的查詢計劃，而是一個近似的最優解。這類算法的典型代表有貪婪算法等，常見的有SDD-1算法。

1.2 常見并行數據庫查詢優化方法

并行數據庫的優化方法是目前研究較深入的部分，對整個數據庫查詢的優化具有重要的研究價值。從大的方面來看，可以分為4類，分別是基于查詢樹的傳統優化方法、多重加權樹優化方法、語義查詢優化方法以及基于遺傳的優化方法。其中，基于查詢樹的傳統優化方法主要包括基于左線性樹的查詢優化算法、基于右線性樹的查詢優化算法、基于片段式右線性樹的查詢優化方法、基于濃密樹的查詢優化算法和基于操作森林的查詢優化算法。多重加權樹優化方法夠處理最常用的選擇一投影一連接查詢，支持多種并行連接算法，包括流水線緩沖區的存儲器優化分配算法、數據操作的處理機與存儲器優化分配算法和連接操作實現算法的優選算法。語義查詢優化方法包括傳統語義查詢優化方法和基于Agent 技術的語義查詢優化方法。目前研究較多的是基于Agent 技術的語義查詢優化方法。該方法利用人工智能中的Agent 技術來實現并行數據庫查詢優化的優化。該方法采用Multi-Agent技術自動查找與給定查詢有關的完整性約束條件，然后，修改給定的查詢為更有效的等價查詢，使得多個關系間連接操作的效率得到很大的提高，從而達到查詢所期望達到的減少連接操作、縮短查詢時間的優化效果，實現了基于Agent 的語義查詢優化?；谶z傳的優化方法是目前發展較快的一種全局優化方法，它借助于生物學的遺傳觀點?？梢悦黠@的提高個體的實用性，從而實現更加的查詢優化效果。

曾有學者對上述幾類并行數據庫查詢優化方法進行了系統的比較研究，他得出的結論是基于遺傳的優化方法是效率最高的方法。當然，我們也應看到基于遺傳的優化方法方法目前還存在算法過程較復雜的缺點，但我們也必須意識到該方法是很有前途的一種方法。

2 結論

隨著信息技術，特別是網絡技術的快速發展，人們對數據庫的效率要求更高，實時數據庫領域尤為突出。查詢是數據庫操作最普通、最常用的操作之一。提高查詢的效率就能明顯的提高數據庫的效率，所以數據庫查詢優化技術就越發重要了。論文主要從分布式數據庫和并行數據庫兩個方面來論述數據庫查詢優化技術。在分布式數據庫部分，側重于方法和策略的研究，主要論述了5個方面。在并行數據庫部分，側重實際算法的介紹，主要介紹了4類算法，并指出基于遺傳的優化方法是目前效率最高，最有前途的方法之一。

當然，我們也要認識到查詢優化的核心就是減少操作的數據量，從而降低處理的代價。所以，我們在研究中，可以引入更多的人工智能、線性控制以及其其它方面的理論來提高優化的效率。同時，我們還有認識到每類優化策略或方法都有其特殊的應用場合，只有合理的應用優化策略才能實現高效的查詢效果。我們可以預測隨著相關學科的發展，查詢優化技術必將獲得更大的發展。

參考文獻:

[1] 邵佩英.分布式數據庫系統及其應用[M].北京:科學出版社，2005.

[2] .S.Pramanik，D.Vineyard.Optimizing Join Queries in Distributed Databases[J].IEEE，1988，l4(9):1319-1326.

[3] Chiping Wang，O.K.Li，L.P.Chen.Distributed Query Optimization by One-Shot Fixed-Precision Semi-Join Execution[J].Seventh International Conference 0n Data Engineering，1991:756-763.

[4] 王小平，曹立明.遺傳算法—理論、應用與軟件實現[M].西安:西安交通大學出版社，2002:123-140.

[5] 徐麗萍，金雄兵，趙小松.并行數據庫查詢優化技術研究[J].華中科技大學學報(自然科學版)，2006，34(3):11-13.

[6] 許新華，諶頏.并行數據庫的語義查詢優化研究:基于Agent[J].西南師范大學學報(自科版)，2007，32(4):128-132.