高效優(yōu)化的XML索引推薦系統(tǒng)

徐 謙

(黑龍江工程學(xué)院)

?

高效優(yōu)化的XML索引推薦系統(tǒng)

徐 謙

(黑龍江工程學(xué)院)

XML數(shù)據(jù)庫日益龐大，日益高度結(jié)構(gòu)化，查詢也越來越復(fù)雜.提出一種XML索引推薦系統(tǒng)，它緊密聯(lián)結(jié)查詢優(yōu)化器，能夠解決XML索引推薦問題.

XML索引；查詢優(yōu)化器；候選索引集；評估配置

0 引言

XML語言的豐富性和優(yōu)化配置潛在的復(fù)雜性，為XML索引推薦帶來巨大難度，使搜索算法作用顯著.提高優(yōu)化器效率，減少其評估命令數(shù)量也同樣重要.

該文提出一種XML索引推薦器，它在考慮數(shù)據(jù)更改而產(chǎn)生的索引更新成本的前提下，可以為指定的數(shù)據(jù)庫和查詢工作量自動推薦最佳索引集模式.

這個XML索引推薦器的關(guān)鍵特征就是與XML數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化器緊密聯(lián)結(jié).依靠查詢優(yōu)化器列舉候選索引模式，評估特定索引配置的查詢效益；運(yùn)用優(yōu)化器的索引選擇和成本估算能力，確保推薦的索引確實(shí)應(yīng)用并有效.

該文其余部分結(jié)構(gòu)如下：

運(yùn)用一個算法列舉候選XML索引.

運(yùn)用一個泛化算法擴(kuò)展候選索引集.

采用兩種新穎算法，搜索索引配置空間，以找到適合于硬盤預(yù)算的最佳配置.

一種技術(shù)，提高優(yōu)化器效率，減少評估索引配置的命令數(shù)量.

采用DB2原型版本執(zhí)行XML索引推薦器，以TPoX基準(zhǔn)進(jìn)行實(shí)驗(yàn)研究.

1 XML索引推薦系統(tǒng)的框架結(jié)構(gòu)

圖1 XML索引推薦框架

圖1表示了XML索引推薦器的結(jié)構(gòu).索引推薦過程框架如下：首先，依靠查詢優(yōu)化器列舉一個特定的候選索引集.然后，將它擴(kuò)展成為能夠滿足現(xiàn)在和將來工作負(fù)荷復(fù)雜查詢的泛化索引集.通過兩種新的優(yōu)化模式運(yùn)用查詢優(yōu)化器.第一種，稱作列舉索引模式，優(yōu)化器接受查詢并且列舉相關(guān)索引.第二種，稱為評估索引模式，優(yōu)化器評估索引配置的查詢成本.優(yōu)化模式將索引推薦過程與查詢優(yōu)化器緊密聯(lián)結(jié)，無須復(fù)制優(yōu)化器已有的功能.新模式中，需要修改查詢優(yōu)化器，創(chuàng)建一個虛擬索引集.這個虛擬索引集不能用于查詢，只創(chuàng)建在特定的查詢模式中，目的是泛化查詢.

當(dāng)虛擬索引集創(chuàng)建完成，啟動優(yōu)化器，以評估模式估算成本.

使用數(shù)據(jù)庫系統(tǒng)工程中的統(tǒng)計(jì)收集命令，為XML數(shù)據(jù)收集統(tǒng)計(jì)數(shù)據(jù)，供虛擬索引使用.

XML索引推薦系統(tǒng)考慮到因更新、刪除和插入等操作而產(chǎn)生的索引更新成本，會從計(jì)算效益減去配置中所有索引的維護(hù)成本[1]. 該文運(yùn)行一個例子，包含下面兩種TPoX基準(zhǔn)的查詢的工作負(fù)荷[2].

Q1: Return a security having the specified Symbol

for $sec in SECURITY(’SDOC’)/Security

where $sec/Symbol= "BCIIPRC"

return $sec

Q2: List securities in a particular sector given a yield range

for $sec in SECURITY(’SDOC’)/Security[Yield>4.5]

where $sec/SecInfo/*/Sector= "Energy"

return

2 以優(yōu)化模式產(chǎn)生基本索引集

為得到查詢必需的基本候選索引集，XML索引推薦系統(tǒng)必須與優(yōu)化器的索引匹配過程緊密聯(lián)結(jié)，利用其詳盡的查詢解析、索引匹配、類型檢驗(yàn)和查詢改寫功能而無需復(fù)制.

利用查詢優(yōu)化器的索引匹配能力列舉候選XML索引集，必須修改優(yōu)化器以創(chuàng)建一個特定的列舉索引查詢優(yōu)化器模式.首先，在XML數(shù)據(jù)上創(chuàng)建一個虛擬的、廣泛的索引，模式是//*.這個 //*虛擬索引，虛擬地索引XML數(shù)據(jù)中的所有元素，由此匹配查詢中的任何可以回應(yīng)索引的XPath模式.然后，查詢優(yōu)化器進(jìn)行優(yōu)化查詢.在索引匹配后，收集查詢到所有與這個//*匹配的索引模式，優(yōu)化過程終止.

這個列舉模式包括了只出現(xiàn)在查詢重寫中的索引.例如，表1中的C1, C2和C3，是被DB2優(yōu)化器為查詢例子Q1和 Q2.列舉的模式，C1和C2只各自出現(xiàn)在Q1and Q2查詢重寫中.所有這三個候選考慮到?jīng)Q定索引模式的目標(biāo)節(jié)點(diǎn)的條件.

表1 基本和泛化索引

通過這個優(yōu)化模式，XML索引推薦系統(tǒng)產(chǎn)生了一個基礎(chǔ)的候選集.

3 擴(kuò)展出更加廣泛的泛化索引集

為識別具有相似模式的、對現(xiàn)有和將來查詢都有用途的復(fù)雜查詢模式，必須從基礎(chǔ)索引集擴(kuò)展出更廣泛的泛化索引集.

例如，在Q1and Q2查詢中，下面的兩種XPath路徑表達(dá)式，被查詢優(yōu)化器識別為索引/Security/Symbol和/Security/SecInfo/*/Sector的候選.以兩種路徑表達(dá)為基礎(chǔ)，擴(kuò)展候選集到包括更多概括性模式/Security//*. 這個新的路徑表達(dá)覆蓋了兩種初始路徑表達(dá)以及數(shù)據(jù)中潛在的其他路徑表達(dá)，例如 /Security//Industry.

為找到更多泛化索引模式，泛化算法交替地對每一組基本候選索引集和產(chǎn)生的泛化索引集用進(jìn)行泛化.這個過程持續(xù)到找不到新的泛化XML索引模式為止.泛化原則要兼顧兩個XPath路徑表達(dá)式，找到兩種路徑間的普遍結(jié)點(diǎn).一種新結(jié)構(gòu)的、泛化的XML表達(dá)模式符合這種兼容性考慮，于是這個新表達(dá)被加入到候選集中.泛化前，要檢驗(yàn)兩個模式的兼容性，例如數(shù)據(jù)類型和命名空間.每組泛化過程都分兩個步驟，代表要索引的結(jié)點(diǎn)最終步驟和導(dǎo)向這一結(jié)點(diǎn)的步驟.

表2 算法Ⅰ

路徑表達(dá)模式是一個鏈接的列表，其中每個結(jié)點(diǎn)就是一個路徑步驟.組泛化過程有兩個功能：generalizeStep (算法Ⅰ見表2)和advanceStep.每個函數(shù)返回一個或者更多泛化列表.將這個泛化模式提交為genXPath .發(fā)起一個generalizeStep(null , pi, pj)的起始命令，pi和 pj指向頭結(jié)點(diǎn).泛化中pi和 pj指向newNode，并將newNode加入genXPath.檢驗(yàn)是否pi和 pj具有同樣的命名.如果有，這個新泛化的結(jié)點(diǎn)和原來結(jié)點(diǎn)保留同樣的命名.如果沒有，使用通配符標(biāo)簽*.newNode的導(dǎo)航軸由genAxis (pi.axis , pj.axis )決定，如果至少有一個輸入是派生軸則返回派生軸 (//) ，否則返回子軸.運(yùn)用isLast (p)測試是否 p指向最后步驟.

另一個函數(shù)，advanceStep，根據(jù)表3中總結(jié)的泛化候選集合規(guī)則，前移指針pi 和pj，逐一巡查表達(dá)式列表.

根據(jù)第一條規(guī)則，最后一步泛化完成以后，兩種表達(dá)式的巡查結(jié)束.

在最后步驟上的節(jié)點(diǎn)，只能用另一個最后步驟上的節(jié)點(diǎn)泛化，所以，第二條規(guī)則和第三條規(guī)則，測試這樣的情況：一條表達(dá)式已經(jīng)到達(dá)了它的最后步驟，而另一條表達(dá)式還沒有.第四條規(guī)則處理中間兩步的泛化.可以得到生成三種泛化：(1)把兩種表達(dá)式的指針，前移一步，并泛化它們.(2)和(3)，試圖找到第一種(第二種)表達(dá)式的第一個節(jié)點(diǎn)，出現(xiàn)在第二個(第一個)表達(dá)式中的情形，并一起泛化它們.

表3 推進(jìn)函數(shù)原則

在(2)、(3)中，如果找不到這樣的節(jié)點(diǎn)，就不用執(zhí)行泛化了.(2)和(3)是針對同一節(jié)點(diǎn)重復(fù)出現(xiàn)的情形，進(jìn)行泛化.比如，/a/b/d 和/a/d/b/d ，會生成 /a//d和 /a//b/d.表格2中的規(guī)則0，是生成Xpath之前的最后重寫步驟.在這個步驟中，出現(xiàn)在表達(dá)式中間的一個或多個相鄰的/*，被下一個步驟中的子軸取代.

4 搜索優(yōu)化配置適應(yīng)空間預(yù)算

候選集列舉和泛化之后，XML索引推薦系統(tǒng)掌握了一個擴(kuò)展的候選索引集.下一步就要搜索包含候選索引集的索引配置的空間，以尋找到效益最大，且適應(yīng)用戶空間大小的索引配置.

這個組合的搜索問題可以建模為一個0/1背包問題，并且是NP完全問題[3].背包的大小是用戶特定的硬盤空間預(yù)算.候選索引集是放到背包加密系統(tǒng)中的細(xì)目，具有成本.

采用兩種搜索方法，探索法貪婪搜索能夠確保查詢中使用盡可能多的索引.上下搜索能夠找到一種盡可能泛化的配置.

4.1 探索法貪婪搜索

貪婪搜索可以選擇到的泛化性索引，但它總是做出在當(dāng)前看來是最好的選擇，并不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解[4]，因此有可能與其他索引指向重復(fù)，而優(yōu)化器計(jì)劃只能執(zhí)行一次索引.解決辦法是先選擇索引，再匯集查詢，然后去除從未使用過的索引.同時，盡可能立刻刪除冗余的索引，并馬上回收他們占用的空間.

探索法貪婪搜索最大化地保留了搜索最初目標(biāo)的效益，并且保留了一個查詢的XPath模式點(diǎn)位圖.這個點(diǎn)位圖用來確認(rèn)，新加入配置中的泛化索引，并非已有索引的復(fù)制.

當(dāng)一個概括性的索引，xgeneral ,被加到推薦的索引配置中，它必須比他所概括的其他索引x1,x2, …,xn“更好”.定義 IB (X)，索引集X的改進(jìn)效益為現(xiàn)有配置效益.一個概括性索引要加到配置中，必須滿足以下兩種探索條件：

IB(xgeneral) ≥ IB(x1,x2,…,xn)

大多數(shù)時候，泛化索引比他們泛化的具體索引大，盡量選擇對現(xiàn)在工作負(fù)荷最佳的最小配置.價值 β是個門檻，指定多大的增加可以接受.在實(shí)驗(yàn)中得到，當(dāng) β = 10%時，工作優(yōu)良.

4.2 上下搜索

探索法貪婪搜索的弊端是當(dāng)工作負(fù)荷即使微小變化，推薦配置就可能失效[5].而XML豐富的結(jié)構(gòu)允許用戶提出查詢，要求讀取輕微變化的數(shù)據(jù)元素.于是，XML索引推薦系統(tǒng)用上下搜索以達(dá)到這一目標(biāo).

在上下搜索中，構(gòu)建一個候選索引集的直接線形圖表(DAG) ，并且泛化他們.每個在DAG中的結(jié)點(diǎn)代表一種XML模式，基于我們的候選泛化算法，結(jié)點(diǎn)具有這種模式的概括性.例如，當(dāng)泛化兩個候選集 /Security/Symbol and /Security/SecInfo/*/Sector，去得到/Security//*，在DAG中將為 /Security//*創(chuàng)建一個結(jié)點(diǎn)，并且這個結(jié)點(diǎn)將是兩個候選集的根.

最后，擁有一個了DAG，將這個DAG的根源作為現(xiàn)行配置.因?yàn)榉夯饕己艽?，這個配置容易超過硬盤空間預(yù)算，但是它也更容易獲得最大化效益.

然而，泛化索引集可能零或負(fù)效益，因?yàn)閮蓚€原因：(1)因?yàn)樵诠ぷ髫?fù)荷中更新、刪除和插入操作而導(dǎo)致的高維護(hù)成本.(2)不能被優(yōu)化器計(jì)劃執(zhí)行使用.為此，加了一個預(yù)處理解析過程，從搜索空間去除沒有效益的索引.然后，用具體的(更小的)子索引集交替取代一個泛化性索引，重復(fù)這個步驟直到現(xiàn)行配置適應(yīng)硬盤空間預(yù)算.

有兩個版本的上下搜索算法.第一種版本，上下搜索簡版，忽略索引相互影響，索引集效益的總和被計(jì)算成配置的效益.第二種版本，上下搜索全版，可以更技術(shù)，更合理地評估配置的效益.

4.3 有效率的效益評估

效益評估由于索引相互間作用而更加復(fù)雜.一個索引查詢的效益會產(chǎn)生變化，取決于是否存在其他索引[6].評估時要考慮到索引間相互影響，所以，將配置中所有索引創(chuàng)建為虛擬索引集.

追蹤每個索引，x，它的查詢操作產(chǎn)生基本候選索引模式.從x中受益的操作被稱之為受影響的集.評估配置的效益，只需對這個受影響的集進(jìn)行總體優(yōu)化.

分出更小的子配置，每一個子配置中都包括相互影響的索引，這些索引與受影響的集重疊.保留一個以前評估過的子配置的緩存，評估某個子配置是否可以在緩存中找到.交替地合并受影響的集的子配置，直到不能再合并.

例如，評估包括 表格1中C1, C2和 C3的索引配置的效益，我們最初分別放置他們到子配置中.因?yàn)?C2和 C3是列舉自相同的查詢Q2中，我們合并他們的子配置，生成兩個子配置{C1} and {C2, C3}.考慮到與其他索引相互作用，估算 C2的效益，就只需評估{C2, C3}的效益，而不包括{C1}.因此，只需發(fā)起對受影響集C2和C3的優(yōu)化命令，不用優(yōu)化整個工作負(fù)荷.

5 用實(shí)驗(yàn)證明XML索引推薦系統(tǒng)高效

5.1 實(shí)驗(yàn)設(shè)置

修改DB2 9 查詢優(yōu)化器，創(chuàng)建支持XML索引推薦系統(tǒng)的兩種新優(yōu)化模式的原形文本.這些新模式在優(yōu)化器中作為實(shí)驗(yàn)?zāi)Ｊ?客戶端側(cè)XML索引推薦系統(tǒng)用JavaTM 1.5執(zhí)行，與原形服務(wù)器經(jīng)由JDBC交流.在有兩個 Intel R Xeon R 2.8GHz CPUs 和 4GB 運(yùn)行內(nèi)存的SUSE Linux R 10 Dell PowerEdge 2850服務(wù)器上進(jìn)行實(shí)驗(yàn).這些數(shù)據(jù)庫存在一個146GB 10K RPM SCSI 驅(qū)動中.

實(shí)驗(yàn)運(yùn)用XML基準(zhǔn)：TPoX.

5.2 推薦效率

索引推薦系統(tǒng)執(zhí)行五種組合的搜索算法：(1)沒有探索法的貪婪搜索.(2)探索法貪婪搜索，(3)上下搜索簡版(4)上下搜索全版.圖2顯示了不同硬盤空間預(yù)算下，不同搜索算法的加速估算.

圖2 評估加速

當(dāng)硬盤空間預(yù)算增加，加速也增強(qiáng).貪婪搜索甚至比全索引需要更大的硬盤空間.探索法搜索和上下搜索簡版都得比貪婪搜索加速好，加速效果接近動力程序搜索.上下搜索全版考慮到了索引間相互影響，加速表現(xiàn)最好.

圖3顯示，上下搜索全版的優(yōu)異表現(xiàn)來之不易.圖表顯示，索引推薦時間伴隨硬盤空間預(yù)算的變化而變化.上下搜索全版運(yùn)行時間超過探索法貪婪搜索7倍還多.但是，隨硬盤空間增加，上下搜索全版運(yùn)行時間明顯改進(jìn).

圖3 推薦系統(tǒng)運(yùn)行時間

5.3 推薦泛化索引

為證明XML索引推薦器能夠推薦更多泛化的、對未來復(fù)雜查詢更加有益的索引，首先闡釋在工作負(fù)荷中可能找到多少泛化索引.

表4顯示列舉索引集模式下，工作負(fù)荷查詢中優(yōu)化器泛化的索引集數(shù)量，當(dāng)工作負(fù)荷的查詢數(shù)量增加，泛化的候選索引集的總數(shù)量也增加.數(shù)量顯示即使這些隨機(jī)的、只有很少、或者沒有普遍性的工作負(fù)荷，也能夠通過加入泛化索引而擴(kuò)展候選索引集的數(shù)量高達(dá)50%.

表4 估算候選索引集

表5 推薦泛化(G)和具體(S)索引數(shù)

闡釋的第二個問題是多少泛化索引集能夠被上下搜索的算法推薦及其效益.

表5顯示不同的硬盤空間預(yù)算下，運(yùn)用探索法貪婪搜索，上下搜索簡版和上下搜索全版的泛化和具體索引集數(shù)量.探索法貪婪搜索推薦表現(xiàn)保守.上下搜索，則相反，硬盤空間越多，它推薦的泛化索引越多.

為顯示加速效果，執(zhí)行一個實(shí)驗(yàn)，其中用來評估推薦配置的測試工作負(fù)荷與訓(xùn)練工作負(fù)荷并不相同.圖4顯示在硬盤空間2GB的預(yù)算下，變化訓(xùn)練工作負(fù)荷大小，測試工作負(fù)荷的估算加速.數(shù)字顯示是在一定硬盤空間下，上下搜索非常高效，可以泛化從訓(xùn)練工作負(fù)荷到測試工作負(fù)荷、從可見到未可見的查詢.而探索法貪婪搜索沒有這個能力.

圖4 泛化未可見查詢

圖5 泛化未可見查詢一實(shí)際加速

6 結(jié)束語

該文提出了一個索引推薦系統(tǒng)，能夠?yàn)橹付ǖ腦ML數(shù)據(jù)庫和查詢工作負(fù)荷推薦最佳索引集.這個推薦系統(tǒng)列舉和評估索引時，緊密地聯(lián)結(jié)查詢優(yōu)化器.它運(yùn)用搜索算法，超越訓(xùn)練工作負(fù)荷推薦有用途的索引集，并且最小化優(yōu)化器命令數(shù)量，操作極為高效.在DB2原形文本中執(zhí)行XML索引推薦系統(tǒng)，顯示它所推薦的索引，極大地加速了工作負(fù)荷查詢.

[1] Elghandour, Aboulnaga A, Zilio D C,et al.與優(yōu)化器高度匹配的索引推薦,發(fā)表滑鐵盧大學(xué)技術(shù)學(xué)刊2013-22,2013.

[2] Nicola M，Kogan I，Schiefer B.“XML 操作過程基準(zhǔn)”，數(shù)據(jù)管理國際會議，2007.https:/sourceforge.net/projects/tpox.

[3] Valentin G，Narasaya V R.有效的Microsoft SQL Server成本驅(qū)動索引選擇工具.國際海量數(shù)據(jù)大會,1997.

[4][5] Kleinberg J，Tardos E.算法設(shè)計(jì).北京：清華大學(xué)，2006.

[6] 季玉梅.一種基于XML模式的XML索引技術(shù).北京工業(yè)大學(xué)學(xué)刊,2013.

(責(zé)任編輯：季春陽)

Highly Optimal XML Index Recommendation

Xu Qian

(Heilongjiang Institute of Technology)

XML database systems are increasingly large, highly structured and increasingly complex to be queried. In this paper, an XML Index Advisor coupled with the query optimizer tightly `` is proposed which make it efficiently easy to recommend the best set of XML indexes and expand more useful generalized set of indexes candidates.

XML index；Query optimizer；Indexes candidates；Estimate configurations

2016-01-19

TP274

A

1000-5617(2016)02-0079-05