數據庫查詢優化中的智能預取技術

摘要：提出了一種新的用于關系數據庫查詢緩沖和預取的方法。首先將數據查詢語句抽象成由四元組組成的查詢模板，同時保存了查詢語句的實際參數。基于這些模板和參數，提出了兩種智能預取算法以適應兩類不同的數據查詢需求。第一個算法基于蟻群規則，該算法能夠用于預測將來具有最高可能性的查詢。經過監控某個特定應用對于數據庫所發生的大量查詢，實際的模板數要遠遠小于發生的查詢數。當通過考慮查詢模板和跟蹤歷史查詢記錄來預測未來可能發生的查詢時，提出了第二類算法。該算法基于慣性規則，它使用BP網絡來跟蹤用戶的查詢歷史。相對于前面的算法，該算法更適合多應用共存的場合。在模擬實驗中發現對于單個應用而言，查詢具有很高的模板依賴性，而對于多應用場合，慣性規則具有更好的適應性。

關鍵詞：數據預取；蟻群規則；慣性規則

中圖分類號：TP391．7文獻標志碼：A

文章編號：1001－3695(2007)05－0035－03



0引言

對于海量數據的檢索往往耗時巨大，因此有必要設計特定的查詢優化系統。通常的優化系統采用的策略可以分為兩類：①通用的優化策略。該策略與應用本身無關，適應面廣，可以應用在所有的優化系統中，但往往優化的效果并不是十分明顯，尤其是對于海量隨機檢索，查詢效率很難有所提高。②與應用密切相關的優化策略。該策略在設計過程中需要考慮應用的細節，有可能對查詢效率有所提高，但如果應用比較復雜，其設計的難度也很大，而且由于僅適用于特定應用，其開發成本也很高。人工智能技術具有自適應的特性，能夠針對不同情況自動調整系統的各項參數，因此十分適合構造一種既與應用相關，又可以通過自動調整以適應不同應用的查詢優化策略。

通過構建一個采用預取策略的查詢優化系統來對數據檢索進行優化。其中預取哪些數據是查詢優化系統能否發揮作用的一個重要因素。因此在預取數據的選擇上采用了蟻群規則和慣性規則相結合的方式來實現。通過使用該算法，預取數據既可以與應用緊密相關，同時又具有自動調整的特性，能夠適應不同的應用需求。通過實驗驗證，該方案不僅在特定應用中能夠發揮優化作用，而且具有較強的通用性。

1相關工作

Seppi[1]提出了一種基于Bayesian方法的數據查詢優化算法。該算法試圖利用人工智能的方法解決查詢的不確定性，在學習算法和查詢處理之間獲得較好的平衡。但是這種方法需要大量的實例進行訓練，從而獲得相應的Bayesian網絡。然而即使得到了該網絡，仍然不能處理其他類型應用所產生的查詢，因此在應用面上受到了很大的限制。基于Seppi的工作，Cole等人[2]提出了一種基于成本的決策模型來生成動態執行計劃。與Seppi進行預測的優化思想不同，Cole的工作是基于執行成本進行優化，而相應的執行成本需要建立在預先數據分析的基礎上，這對負載較重的數據庫系統來說會帶來較大的性能問題。Wang Dazhi提出了采用分析查詢語句，并提取出相應模板的做法來實現數據預取[3]。這種思想與本文所提出的預取思想有類似之處，但是其應用場合僅限于包含大量相同查詢模式的場合。例如通過Web頁面訪問數據庫，在該場合下，訪問數據庫的模式往往是預先定義好的，因此比較適合簡單的統計預測。Zhou Jingren等人[4]則從內存訪問的局部化方面入手，設計了一種新的預測算法，可以通過提高在查詢過程中內存訪問的局部性來提高Cache的命中率。

隨著對數據查詢需求的日益提高，查詢優化系統已經從單純的性能提高發展為具有體系結構、可擴展的系統。針對這種發展趨勢，已有研究機構對于查詢優化的可擴展性提出了以下幾個顯著特征[5]：①具有嚴格的數學推導和理論算法;②具有一套數據變換規則；③基于統計學或成本的模型;④算法的物理屬性；⑤新的狀態空間搜索策略;⑥執行計劃的質量（如是否需要全局搜索）。

與此同時，由于現代數據查詢都具有海量的特性，優化器本身的查詢和匹配效率也是十分重要的指標。目前國外已經開發出了一些具有可擴展特性的查詢優化系統[6～8]，但是這些系統并沒有完全滿足完整的查詢優化需求。本文提出的方法滿足了特征②～④。雖然并沒有提出嚴格的數學推導，但由于采用了以統計學為基礎的蟻群假設和以BP網絡為基礎的慣性假設，仍然具有比較堅實的理論基礎。

2預取算法描述

本文討論的目標數據集合為符合關系數據模型的數據源，面向的查詢語句為標準的SQL查詢語句。定義1標引屬性（LP）。能夠對海量數據查詢進行分解處理的前提是該海量數據具有可分性，即存在某個屬性值，通過對該屬性值進行分類，可以較為平均地對數據進行分割。這個值稱為標引屬性，記為LP（Labled Property）。

標引屬性對于特定的目標數據集合來說是唯一的。

定義2索引屬性（IP）。可能產生數據查詢條件的屬性稱為索引屬性，記為IP（Indexed Property）。

目標數據集合除了包括標引屬性LP和索引屬性IP外，還可能包括其他屬性值。

定義3歷史查詢（HQ）。用戶曾經發出的查詢請求。其中條件字段中必須包括LP，有可能包括IP。

根據LP將目標查詢數據分解為固定大小的子區域，在每個子區域上重新構建用戶的查詢命令，生成的任務稱為子查詢任務。每個子查詢任務的結果可以形成一個數據塊存放到高速緩沖區中；當下次執行相同的子查詢任務時可以直接從高速緩沖區中獲取結果，而不需要重新執行數據庫查詢操作，這樣的數據塊稱為緩沖塊。

定義4用戶（U）。每個發出查詢請求的客戶被稱為一個用戶，用U（User）標記。

預取算法的基本思想就是將根據所收集到的HQ來計算未來可能產生的查詢請求，并通過在空閑時段預取這些查詢請求，將得到的結果存放在高速緩存中，以加速對下次查詢請求的響應速度。

本文所涉及的預取技術是在滿足以下兩個前提的基礎上設計的。

2．1蟻群算法

蟻群規則的算法思想如圖1所示。圖中橫坐標為LP，通過LP將目標數據空間進行等分；縱坐標為SPs，表示查詢語句所返回的數據屬性項，每種屬性項占一格。圖中深色部分表示用戶請求（hq）所覆蓋的區域。除了LP條件外，其他IP條件相同的hq可以標注在同一張圖上。在積累了若干條hq后，就可以得到圖中的淺色區域，該區域代表了所需要預取的數據。

在實際的實現過程中，將hq表示為以下格式的四元組：

表名，選取字段列表，LP條件，IP條件

針對該四元組進行的算法描述如下：

(1)用相同表名和IP條件的四元組構成一個集合；

(2)從集合中得到LP條件的最大和最小值；

(3)根據集合中所有的選取字段列表生成一個字段列表，該列表包含所有在集合中出現過的字段；

(4)根據表名、IP條件、LP條件的最大/最小值以及包含所有字段的列表構成一個新的四元組，并從該四元組生成預取指令；

(5)執行預取指令，并緩存結果。

2．2群體算法

群體算法是基于慣性規則思想實現的。與蟻群算法一樣，該算法也把hq表示為相同格式的四元組進行處理；與蟻群算法不同的是，群體算法并不是一個確定性的算法。該算法利用具有前向反饋功能的BP網絡來記錄歷史hq，同時其輸出的內容將取決于用于訓練的樣本空間。該算法的具體流程如下：

(1)用相同表名的四元組構成一個集合，并按照接收hq的次序為每個hq編號。

(2)得到該表的所有字段，并分別編號；之后的所有處理都使用編號來代替相應的字段。

(3)構造一個BP網絡，其輸入為hq編號、選取字段列表和IP條件；其輸出為選取字段列表和IP條件。

(4)訓練時，若選取字段列表中包含某字段，則該字段對應的輸入為1；否則為0，IP條件字段也作同樣處理。

(5)BP網絡的評價函數通過將輸出結果與訓練集合中的下一條hq對比得到。若某字段在選取字段列表的輸出為1，而且在下一條hq的選取字段中也存在，則認為輸出正確；否則錯誤。

(6)通過反復訓練，直到訓練結果收斂或達到指定的正確率為止。

(7)當有新的hq到達時，將該hq分解為四元組，并將對應的字段映射到指定的編號上，然后作為BP網絡的輸入，用得到的輸出重新構建四元組及查詢指令。

(8)將得到的查詢指令作為預取指令并執行，緩存結果。

3預取性能分析

預取算法的主要目標就是利用歷史知識來預測未來，從而可以有效地提高未來查詢的響應速度。其性能考查的指標主要包括預取率和命中率。

預取率體現了預取算法占用系統資源的程度。其中系統資源包括計算資源和存儲資源，考慮到預取一般都發生在計算資源相對空閑的時候，因此可以不考慮計算資源對預取率的影響，而僅考慮存儲資源對預取率的影響。預取率計算公式為

其中，hitf表示命中率；hits表示每個hq在緩沖中的命中次數；totals表示每個hq分解的任務數。

一般來說，預取率比較低的算法其命中率也比較低。這是因為緩沖范圍減小的原因，可以通過計算不同預取率情況下的命中率變化來找到一個最佳預取率，使得小于該預取率時，命中率變化曲線比較快速；當大于該預取率之后，命中率變化曲線比較平緩，則此預取率具有較高的性價比。



對于蟻群算法，由于其具有明確的預取范圍，預取率一般是可以預測的；對于群體算法，由于其不是一個確定性的算法，預取率變化范圍比較大。但由于可以通過對網絡參數的調整來得到不同的預取率，可以根據上面提出的方法，通過實際測試獲取一個比較合理的預取率。

4實驗結果分析

為了驗證兩種算法的效果，分別設計了兩種實驗方法。

（1）采用與Wang Dazhi類似的方法，即監控一個時段某個應用訪問數據庫的所有查詢語句，并記錄查詢模版數量隨時間變化的曲線。在本實驗中，選擇某科學網格計算系統作為參考應用，其結果如圖2所示。

由圖2可以看出，隨著查詢數據的增長，查詢模板的數量變化很小。因此在此假設基礎上實現的優化算法具有良好的預測能力。

（2）模擬多應用場合下，在查詢條件相對隨機的情況下，驗證優化算法的預測效果。實驗方法如下：

①查詢條件均為關鍵詞＋時間段。

②隨機生成較小時間段，并在預先生成的規模為1 000詞的關鍵詞表中隨機選擇三個以下的關鍵詞作為檢索條件進行檢索。

③逐漸加大時間段，關鍵詞仍然是隨機選取。

④每個時間段為一個測試單元，隨機選取五組關鍵詞執行此查詢，記錄下平均返回記錄條數及返回速度。

⑤每個測試單元之間執行清除Oracle數據庫自身Cache的操作，避免Oracle的Cache干擾實驗結果。圖3是在記錄規模為5.76億條的Oracle 10g數據庫上執行全文查詢的實驗結果。從實驗結果可以看出，在查詢返回記錄增加到萬條以上后，查詢速度有了明顯提高。由于排除了Oracle本身Cache的干擾，可以認為查詢效率的提高主要得益于預取算法發揮了效果。

當然，由于在測試過程中關鍵詞是隨機選取的，并不能完全體現出預取算法的智能性。可以預測，在實際應用中，關鍵詞的選取是具有一定規律性和時效性的，因此預取的性能將會更加顯著。

5結束語

對海量數據進行檢索是一項非常耗時的操作，通常采用預取算法來對其進行優化以達到滿足響應速度的要求，但在預取算法的選擇上非常困難。本文提出了一種具有自適應特性的智能預取算法，采用蟻群規則和慣性規則相結合的方式來實現。該算法既可以實現與應用的緊密相關，同時又具有自動調整的特性，能夠適應不同的應用需求。通過實驗驗證，該方案不僅在特定應用中能夠發揮優化作用，而且具有較強的通用性。未來的數據查詢需求將對預取算法提出更高的要求，如何進一步將智能化引入預取算法中將是一個非常有實際應用價值的研究課題。

參考文獻：

［1］

SEPPI K，BARNES J，MORRIS C. A bayesian approach to query optimization in large scale databases[J].ORSA J. of Computing，1993，5(4): 410－419.

[2]COLE R L. A decision theoretic cost model for dynamic plans[J].IEEE Data Engineering Bulletin，2000，23(2): 34－41.

[3]TENG Weiguang， CHANG Chengyue， CHEN Mingsyan. Integrating web caching and web prefetching in client－side proxies[J].IEEE Transactions on Parallel and Distributed Systems，2005，16(5):444－455.[4]ZHOU Jingren，ROSS K A. Buffering database operations for enhanced instruction cache performance:SIGMOD [C].Paris:[s.n.]，2004:191－202.

[5]MCKENNA W J.Efficient search in extensible database query optimization the volcano optimizer generator[D].Boulder:Colorado University，1993.

[6]ZHOU Jingren，ROSS K A.Buering accesses to memory－resident index structures:VLDB[C].Berlin:[s.n.]，2003:405－416.

[7]CHEN Shimin，GIBBONS P B，MOWRY T C，et al.Fractal prefetching B+－trees:optimizing both cache and disk performance:SIGMOD[C].Madison:[s.n.]，2002:157－168.

[8]ZHOU Jingren. Architecture－sensitive database query processing[D].New York:Columbia University，2004.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”