數(shù)據(jù)庫查詢優(yōu)化中的智能預(yù)取技術(shù)

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

關(guān)鍵詞：數(shù)據(jù)預(yù)取；蟻群規(guī)則；慣性規(guī)則

中圖分類號(hào)：TP391．7文獻(xiàn)標(biāo)志碼：A

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



0引言

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

通過構(gòu)建一個(gè)采用預(yù)取策略的查詢優(yōu)化系統(tǒng)來對(duì)數(shù)據(jù)檢索進(jìn)行優(yōu)化。其中預(yù)取哪些數(shù)據(jù)是查詢優(yōu)化系統(tǒng)能否發(fā)揮作用的一個(gè)重要因素。因此在預(yù)取數(shù)據(jù)的選擇上采用了蟻群規(guī)則和慣性規(guī)則相結(jié)合的方式來實(shí)現(xiàn)。通過使用該算法，預(yù)取數(shù)據(jù)既可以與應(yīng)用緊密相關(guān)，同時(shí)又具有自動(dòng)調(diào)整的特性，能夠適應(yīng)不同的應(yīng)用需求。通過實(shí)驗(yàn)驗(yàn)證，該方案不僅在特定應(yīng)用中能夠發(fā)揮優(yōu)化作用，而且具有較強(qiáng)的通用性。

1相關(guān)工作

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

隨著對(duì)數(shù)據(jù)查詢需求的日益提高，查詢優(yōu)化系統(tǒng)已經(jīng)從單純的性能提高發(fā)展為具有體系結(jié)構(gòu)、可擴(kuò)展的系統(tǒng)。針對(duì)這種發(fā)展趨勢(shì)，已有研究機(jī)構(gòu)對(duì)于查詢優(yōu)化的可擴(kuò)展性提出了以下幾個(gè)顯著特征[5]：①具有嚴(yán)格的數(shù)學(xué)推導(dǎo)和理論算法;②具有一套數(shù)據(jù)變換規(guī)則；③基于統(tǒng)計(jì)學(xué)或成本的模型;④算法的物理屬性；⑤新的狀態(tài)空間搜索策略;⑥執(zhí)行計(jì)劃的質(zhì)量（如是否需要全局搜索）。

與此同時(shí)，由于現(xiàn)代數(shù)據(jù)查詢都具有海量的特性，優(yōu)化器本身的查詢和匹配效率也是十分重要的指標(biāo)。目前國外已經(jīng)開發(fā)出了一些具有可擴(kuò)展特性的查詢優(yōu)化系統(tǒng)[6～8]，但是這些系統(tǒng)并沒有完全滿足完整的查詢優(yōu)化需求。本文提出的方法滿足了特征②～④。雖然并沒有提出嚴(yán)格的數(shù)學(xué)推導(dǎo)，但由于采用了以統(tǒng)計(jì)學(xué)為基礎(chǔ)的蟻群假設(shè)和以BP網(wǎng)絡(luò)為基礎(chǔ)的慣性假設(shè)，仍然具有比較堅(jiān)實(shí)的理論基礎(chǔ)。

2預(yù)取算法描述

本文討論的目標(biāo)數(shù)據(jù)集合為符合關(guān)系數(shù)據(jù)模型的數(shù)據(jù)源，面向的查詢語句為標(biāo)準(zhǔn)的SQL查詢語句。定義1標(biāo)引屬性（LP）。能夠?qū)Ａ繑?shù)據(jù)查詢進(jìn)行分解處理的前提是該海量數(shù)據(jù)具有可分性，即存在某個(gè)屬性值，通過對(duì)該屬性值進(jìn)行分類，可以較為平均地對(duì)數(shù)據(jù)進(jìn)行分割。這個(gè)值稱為標(biāo)引屬性，記為LP（Labled Property）。

標(biāo)引屬性對(duì)于特定的目標(biāo)數(shù)據(jù)集合來說是唯一的。

定義2索引屬性（IP）。可能產(chǎn)生數(shù)據(jù)查詢條件的屬性稱為索引屬性，記為IP（Indexed Property）。

目標(biāo)數(shù)據(jù)集合除了包括標(biāo)引屬性LP和索引屬性IP外，還可能包括其他屬性值。

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

根據(jù)LP將目標(biāo)查詢數(shù)據(jù)分解為固定大小的子區(qū)域，在每個(gè)子區(qū)域上重新構(gòu)建用戶的查詢命令，生成的任務(wù)稱為子查詢?nèi)蝿?wù)。每個(gè)子查詢?nèi)蝿?wù)的結(jié)果可以形成一個(gè)數(shù)據(jù)塊存放到高速緩沖區(qū)中；當(dāng)下次執(zhí)行相同的子查詢?nèi)蝿?wù)時(shí)可以直接從高速緩沖區(qū)中獲取結(jié)果，而不需要重新執(zhí)行數(shù)據(jù)庫查詢操作，這樣的數(shù)據(jù)塊稱為緩沖塊。

定義4用戶（U）。每個(gè)發(fā)出查詢請(qǐng)求的客戶被稱為一個(gè)用戶，用U（User）標(biāo)記。

預(yù)取算法的基本思想就是將根據(jù)所收集到的HQ來計(jì)算未來可能產(chǎn)生的查詢請(qǐng)求，并通過在空閑時(shí)段預(yù)取這些查詢請(qǐng)求，將得到的結(jié)果存放在高速緩存中，以加速對(duì)下次查詢請(qǐng)求的響應(yīng)速度。

本文所涉及的預(yù)取技術(shù)是在滿足以下兩個(gè)前提的基礎(chǔ)上設(shè)計(jì)的。

2．1蟻群算法

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

在實(shí)際的實(shí)現(xiàn)過程中，將hq表示為以下格式的四元組：

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

針對(duì)該四元組進(jìn)行的算法描述如下：

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

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

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

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

(5)執(zhí)行預(yù)取指令，并緩存結(jié)果。

2．2群體算法

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

(1)用相同表名的四元組構(gòu)成一個(gè)集合，并按照接收hq的次序?yàn)槊總€(gè)hq編號(hào)。

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

(3)構(gòu)造一個(gè)BP網(wǎng)絡(luò)，其輸入為hq編號(hào)、選取字段列表和IP條件；其輸出為選取字段列表和IP條件。

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

(5)BP網(wǎng)絡(luò)的評(píng)價(jià)函數(shù)通過將輸出結(jié)果與訓(xùn)練集合中的下一條hq對(duì)比得到。若某字段在選取字段列表的輸出為1，而且在下一條hq的選取字段中也存在，則認(rèn)為輸出正確；否則錯(cuò)誤。

(6)通過反復(fù)訓(xùn)練，直到訓(xùn)練結(jié)果收斂或達(dá)到指定的正確率為止。

(7)當(dāng)有新的hq到達(dá)時(shí)，將該hq分解為四元組，并將對(duì)應(yīng)的字段映射到指定的編號(hào)上，然后作為BP網(wǎng)絡(luò)的輸入，用得到的輸出重新構(gòu)建四元組及查詢指令。

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

3預(yù)取性能分析

預(yù)取算法的主要目標(biāo)就是利用歷史知識(shí)來預(yù)測(cè)未來，從而可以有效地提高未來查詢的響應(yīng)速度。其性能考查的指標(biāo)主要包括預(yù)取率和命中率。

預(yù)取率體現(xiàn)了預(yù)取算法占用系統(tǒng)資源的程度。其中系統(tǒng)資源包括計(jì)算資源和存儲(chǔ)資源，考慮到預(yù)取一般都發(fā)生在計(jì)算資源相對(duì)空閑的時(shí)候，因此可以不考慮計(jì)算資源對(duì)預(yù)取率的影響，而僅考慮存儲(chǔ)資源對(duì)預(yù)取率的影響。預(yù)取率計(jì)算公式為

其中，hitf表示命中率；hits表示每個(gè)hq在緩沖中的命中次數(shù)；totals表示每個(gè)hq分解的任務(wù)數(shù)。

一般來說，預(yù)取率比較低的算法其命中率也比較低。這是因?yàn)榫彌_范圍減小的原因，可以通過計(jì)算不同預(yù)取率情況下的命中率變化來找到一個(gè)最佳預(yù)取率，使得小于該預(yù)取率時(shí)，命中率變化曲線比較快速；當(dāng)大于該預(yù)取率之后，命中率變化曲線比較平緩，則此預(yù)取率具有較高的性價(jià)比。



對(duì)于蟻群算法，由于其具有明確的預(yù)取范圍，預(yù)取率一般是可以預(yù)測(cè)的；對(duì)于群體算法，由于其不是一個(gè)確定性的算法，預(yù)取率變化范圍比較大。但由于可以通過對(duì)網(wǎng)絡(luò)參數(shù)的調(diào)整來得到不同的預(yù)取率，可以根據(jù)上面提出的方法，通過實(shí)際測(cè)試獲取一個(gè)比較合理的預(yù)取率。

4實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證兩種算法的效果，分別設(shè)計(jì)了兩種實(shí)驗(yàn)方法。

（1）采用與Wang Dazhi類似的方法，即監(jiān)控一個(gè)時(shí)段某個(gè)應(yīng)用訪問數(shù)據(jù)庫的所有查詢語句，并記錄查詢模版數(shù)量隨時(shí)間變化的曲線。在本實(shí)驗(yàn)中，選擇某科學(xué)網(wǎng)格計(jì)算系統(tǒng)作為參考應(yīng)用，其結(jié)果如圖2所示。

由圖2可以看出，隨著查詢數(shù)據(jù)的增長，查詢模板的數(shù)量變化很小。因此在此假設(shè)基礎(chǔ)上實(shí)現(xiàn)的優(yōu)化算法具有良好的預(yù)測(cè)能力。

（2）模擬多應(yīng)用場(chǎng)合下，在查詢條件相對(duì)隨機(jī)的情況下，驗(yàn)證優(yōu)化算法的預(yù)測(cè)效果。實(shí)驗(yàn)方法如下：

①查詢條件均為關(guān)鍵詞＋時(shí)間段。

②隨機(jī)生成較小時(shí)間段，并在預(yù)先生成的規(guī)模為1 000詞的關(guān)鍵詞表中隨機(jī)選擇三個(gè)以下的關(guān)鍵詞作為檢索條件進(jìn)行檢索。

③逐漸加大時(shí)間段，關(guān)鍵詞仍然是隨機(jī)選取。

④每個(gè)時(shí)間段為一個(gè)測(cè)試單元，隨機(jī)選取五組關(guān)鍵詞執(zhí)行此查詢，記錄下平均返回記錄條數(shù)及返回速度。

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

當(dāng)然，由于在測(cè)試過程中關(guān)鍵詞是隨機(jī)選取的，并不能完全體現(xiàn)出預(yù)取算法的智能性。可以預(yù)測(cè)，在實(shí)際應(yīng)用中，關(guān)鍵詞的選取是具有一定規(guī)律性和時(shí)效性的，因此預(yù)取的性能將會(huì)更加顯著。

5結(jié)束語

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

參考文獻(xiàn)：

［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.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”