分布式數據庫的查詢優化算法概論

程鵬 周小琳

沈陽理工大學 遼寧 沈陽 110000

1 數據庫概述

分布式數據庫系統是以集中式數據庫作為基礎的一種計算機網絡技術，不同的是能夠分散存儲在網絡不同場所，存儲場所不同對數據處理能力也存在一定的差異。在目前有兩種分布式數據庫系統：一是在邏輯上結構完整而物理上應用網絡技術使其分散的多個數據庫集群連接，并通過使用數據庫管理軟件管理分布式系統。該系統用途比較單一，適合比較小的部門;另一種形式是在邏輯和物理上都是分散開的，該系統可容納相比差異較大的多個數據庫，適合較大數據庫集成[1]。

2 分布式數據庫查詢優化的目的

有兩個實現分布式數據庫的查詢優化的主要目的：一是縮短查詢數據所需的時間；二是降低查詢資料所需的費用。因為在分布式數據庫的數據查詢中數據量大且復雜，所以需要的時間、費用相比集中式來說是更多。因此優化分布式數據庫查詢以時間、費用為出發點，盡可能在縮短時間、降低費用的基礎上實現優化。

3 優化分布式數據庫查詢的基本方法

3.1 基于半連接操作的優化算法

數據庫中的連接操作會產生冗余數據，基于半連接操作優化算法是通過使用半連接操作減少不必要的數據傳輸，避免產生數據冗余。代表算法有：①二次劈開縮減算法[2]：通過使用二分劈開條件（二分條件選擇將決定數據在兩個站點是否等分），將完全半連接中的縮減關系分成兩半。后將相同條件的數據傳輸到相同站點進行對應的連接操作，利用系統的并行性得到兩個站點的連接結果，最終提高了整體查詢效率。②SDD-1 算法[3]：基本算法是通過估計縮減程序的因素，使用迭代得到的有益半連接計算，得出半連接縮減程序集合，由合集給出最收益策略，后優化算法是對基本算法求得的解進行修正，最終查詢結果將由所有站點的數據整合而成。

3.2 基于直連接操作的優化算法

對于半連接操作而言，在直接連接操作中局部處理代價更受重視,但比較少考慮數據傳輸的代價。該策略的代表算法有：①分片復制算法：首先選擇數據庫系統的一組站點，將查詢中的某一個關系進行分片并將分片片段都傳送到預定站點中，最終結果將是每個預定站點返回結果的集合。②Hash劃分算法：首先選取合適的Hash 函數，后對關系的某一個屬性或幾個屬性集合的元組值進行Hash 計算，把相同計算結果的關系元組存放在相同的站點上，關系元組因此都被分散放在不同的站點上，進而得到相應關系的水平片段。

3.3 基于查詢圖的優化算法

利用貪心算法構造出代價模型的查詢圖，并實現數據庫查詢是該類算法的基本思想。Kruskal 算法對非鏈接型查詢圖的優化效果較好，該算法對不同查詢圖中都需要構造最小生成樹即在圖中找到代價最小的序列。該算法對不同查詢都可以找到最小代價序列，可以實現最大程度優化。

3.4 基于粒子群算法

在多表連接的查詢特征基礎上,將粒子樹形編碼的分布式數據查詢方式。使用粒子群算法優化后的查詢策略比原始的查詢策略的執行代價低，有效地增加了系統的查詢效率。為了進一步提升效率，又提出了多連接粒子群優化算法，該算法能夠在更復雜多連接查詢優化問題中得到應用。

3.5 遺傳算法

分布式數據查詢時不僅要考慮數據的分布與冗余，而且要考慮站點間的通信代價以及計算機的并行執行能力、時間成本等。近年來，學者們把粒子群算法、人工免疫算法、人工魚群算法等應用于分布式數據庫查詢中。這些啟發式算法在一定程度上提高了分布式數據庫查詢優化效果。遺傳算法是一種并行、高效、全局搜索算法，在數據庫查詢優化過程中能夠獲取與積累經驗，并能夠在查詢過程中自適應地對搜索過程進行控制，獲得最優解。查詢時遺傳算法個體在求解，不斷根據問題域中的適應度值，進行選擇、交叉、變異等遺傳操作，找到最優查詢方案。步驟如下：①隨機初始化n個個體作為初始種群，設置w、μ、α等參數的值，對初始種群進行評價，記錄最佳個體的適應度值。②設置初始樣本群為空。③判斷是否需要重新取樣，若需要，轉到步驟4，不需要，轉到步驟6。④根據條件采樣方法進行取樣，評價樣本中的所有種群，標記所有比當前種群好的種群組成種群集合J。⑤得出當前最優的變異率。⑥交叉、變異操作。⑦更新當前種群，并對其進行評價，記錄最佳個體的適應度值。⑧判斷是否滿足結束條件，若滿足，結束，不滿足，則轉步驟3。按照步驟3～8進行3次迭代，在進化結束后，當前種群中的最佳個體即為要找的最優查詢執行計劃，按照該查詢執行計劃查詢，整個查詢過程得到優化。

4 結束語

本文主要敘述了分布式數據庫的概念、查詢優化的目的和優化查詢的方法等內容，并且對查詢優化中的方法策略進行了簡單的介紹。查詢優化算法不是通用的，影響查詢算法效率的主要因素包括：是否可以滿足大數據量的需求；是否可以為全局或局部優化；是否可以滿足復雜性的需求等。在不同的查詢問題中，選擇方案使查詢優化算法可以達到最優為目的。