結(jié)合重寫(xiě)與數(shù)據(jù)并行的XQuery查詢優(yōu)化

陳榮鑫

(1.北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院， 北京 100124;2.集美大學(xué)計(jì)算機(jī)工程學(xué)院， 福建 廈門 361021)

0 引 言

XQuery作為W3C推薦的XML數(shù)據(jù)查詢語(yǔ)言[1]，在桌面系統(tǒng)、企業(yè)級(jí)Web服務(wù)和云計(jì)算平臺(tái)等各種開(kāi)發(fā)和應(yīng)用場(chǎng)景中得到逐步推廣.大量XML數(shù)據(jù)的操作要求高效的XQuery查詢支持.由于XQuery語(yǔ)言的編譯和執(zhí)行依靠XML查詢引擎完成，引擎的性能問(wèn)題成為研究重點(diǎn).目前發(fā)展出各種旨在提升引擎性能的XQuery查詢優(yōu)化方法，包括邏輯優(yōu)化和物理優(yōu)化等方面，通過(guò)查詢代數(shù)優(yōu)化設(shè)計(jì)、查詢重寫(xiě)等手段實(shí)現(xiàn)[2].

查詢優(yōu)化需要綜合考慮查詢語(yǔ)言本身特點(diǎn)和實(shí)際應(yīng)用條件等軟硬方面因素.一方面，查詢重寫(xiě)根據(jù)特定規(guī)則，為原查詢生成較為高效的查詢計(jì)劃，在查詢優(yōu)化過(guò)程中廣為應(yīng)用.Brantner M等人提出通過(guò)XQuery語(yǔ)言層的重寫(xiě)，獲得盡可能接近單一查詢塊的形式，以便進(jìn)一步生成優(yōu)化的查詢計(jì)劃[3].廖偉等人給出XQuery集成系統(tǒng)的查詢分解優(yōu)化方法，通過(guò)XQuery查詢重寫(xiě)實(shí)現(xiàn)，并且引入了新的語(yǔ)法元素以表達(dá)針對(duì)數(shù)據(jù)源的操作，該法用于提高多數(shù)據(jù)源分布式查詢的性能[4].另一方面，并行化措施是提升系統(tǒng)性能的重要途徑[5]，尤其是多核計(jì)算環(huán)境日益普及的今天.Li X給出一個(gè)XQuery并行化框架[6]，由編譯器完成并行化重寫(xiě)，由于缺乏對(duì)通用查詢的支持，適用性有限.Re C等人把XQuery語(yǔ)言擴(kuò)展成面向分布計(jì)算的XQueryD語(yǔ)言[7]；Fernàndez M等人則設(shè)計(jì)了用于分布式XML查詢的DXQ語(yǔ)言[8]；Yui等人在XBird查詢引擎上擴(kuò)展了并行功能，通過(guò)遠(yuǎn)程代理傳遞數(shù)據(jù)實(shí)現(xiàn)按需查詢[9]，這些工作主要面向分布式查詢應(yīng)用，面向單機(jī)多核并行計(jì)算的研究目前仍然很有限.

考慮既要獲取高效的查詢計(jì)劃，又要充分利用多核計(jì)算環(huán)境，本文分別在XQuery語(yǔ)言層和中間語(yǔ)言層開(kāi)展工作，給出使用查詢重寫(xiě)技術(shù)和數(shù)據(jù)并行技術(shù)進(jìn)行查詢優(yōu)化的方法，綜合這兩種技術(shù)以提高查詢引擎整體性能.

1 查詢重寫(xiě)優(yōu)化

1.1 XQuery查詢分析

XQuery作為XML查詢的專用語(yǔ)言，主要作用是從XML數(shù)據(jù)中查找和提取元素及屬性，并重新組織XML數(shù)據(jù)輸出.XQuery中最重要的語(yǔ)法結(jié)構(gòu)是FLWOR語(yǔ)句，其表達(dá)式語(yǔ)法[1]定義形如FLWORExpr ::= (ForClause | LetClause)+WhereClause? OrderByClause? "return" ExprSingle.對(duì)應(yīng)的語(yǔ)法組成包括ForClause | LetClause變量綁定子句(FL)，where謂詞過(guò)濾子句(W)，OrderByClause排序子句(O)，再加上return返回結(jié)果子句(R).FLWOR語(yǔ)句可以嵌套使用，以構(gòu)成功能強(qiáng)大的查詢程序，比如ExprSingle可能也是個(gè)FLWOR語(yǔ)句.以下XQuery程序來(lái)自W3C案例[10]，該程序是基于XML的在線拍賣系統(tǒng)中的1.4.4.3查詢實(shí)例，用于查找等級(jí)低于‘C’級(jí)的用戶，該用戶提供的拍賣品低價(jià)超過(guò)1 000，要求返回相關(guān)信息記錄.程序如下:

for $u in doc("c:/MR/users.xml")//user_tuple

for $i in doc("c:/MR/items.xml")//item_tuple

where $u/rating > "C" and $i/reserve_price > 1000 and $i/offered_by = $u/userid

return

該程序主體是FLWOR框架,帶有兩個(gè)for子句分別對(duì)兩個(gè)數(shù)據(jù)源的XPath軸操作結(jié)果序列進(jìn)行變量迭代綁定，這部分可視為數(shù)據(jù)獲取操作；where子句內(nèi)包含多個(gè)過(guò)濾條件，以及連接操作；return子句通過(guò)軸操作對(duì)變量進(jìn)行投影，并完成XML節(jié)點(diǎn)構(gòu)造并返回.where子句和return子句完成查詢的關(guān)鍵工作，往往是耗時(shí)最多的地方，其效率受前級(jí)數(shù)據(jù)獲取量的影響，因此有必要通過(guò)查詢重寫(xiě)進(jìn)行優(yōu)化.

1.2 查詢重寫(xiě)

關(guān)系代數(shù)中查詢優(yōu)化[11]的一般原則是盡早執(zhí)行選擇操作，以有效減少元組數(shù)量，涉及單個(gè)表的選擇條件盡可能轉(zhuǎn)移到數(shù)據(jù)源處完成；盡早執(zhí)行投影操作，以降低后續(xù)操作的數(shù)據(jù)量，對(duì)于后續(xù)沒(méi)有需求的屬性可以考慮提前去除.該優(yōu)化思路適用于XQuery查詢重寫(xiě)，通過(guò)重寫(xiě)來(lái)減少前級(jí)數(shù)據(jù)獲取量，降低了后續(xù)操作次數(shù)，有效提高查詢性能.

查詢重寫(xiě)的方法是遍歷表達(dá)式語(yǔ)法樹(shù)，分析依賴數(shù)據(jù)源的操作；判別數(shù)據(jù)獲取的投影操作來(lái)源，包括直接軸操作，where子句和返回子句中的軸操作；把來(lái)自不同數(shù)據(jù)源的投影操作分離出，組成對(duì)應(yīng)數(shù)據(jù)獲取表達(dá)式的for/let變量綁定子句；判別數(shù)據(jù)獲取的選擇操作來(lái)源，包括where子句和XPath表達(dá)式中的謂詞；把來(lái)自不同數(shù)據(jù)源的選擇操作分離出，組成對(duì)應(yīng)數(shù)據(jù)獲取表達(dá)式的where子句；用let綁定數(shù)據(jù)獲取表達(dá)式到返回變量$seq，該變量作為數(shù)據(jù)獲取序列提供后續(xù)操作使用；在提取后的主體表達(dá)式中，用$seq變量替換原有的數(shù)據(jù)獲取操作，框架剩余保持不變.一個(gè)重寫(xiě)前的典型查詢程序如下：

for $x in doc(1), $y in doc(2)

where fun($x,$y)

return {proj2($x), proj2($y)}

該程序包含了常見(jiàn)的涉及多個(gè)數(shù)據(jù)源操作的FLWOR表達(dá)式.doc表示數(shù)據(jù)源連接與獲取，包含了各種直接的軸操作，其中where條件表達(dá)式fun($x,$y)內(nèi)含有連接表達(dá)式j(luò)oin($x,$y)、選擇表達(dá)式filter($x,cond1)和filter($y,cond2)、投影表達(dá)式proj1($x)和proj1($y).連接表達(dá)式與兩個(gè)以上數(shù)據(jù)源相關(guān)，而選擇和投影表達(dá)式僅與單個(gè)數(shù)據(jù)源有關(guān).return返回結(jié)果構(gòu)造表達(dá)式，內(nèi)含有投影表達(dá)式proj2($x)與proj2($y).

用提取的選擇表達(dá)式構(gòu)成對(duì)應(yīng)數(shù)據(jù)獲取表達(dá)式的where條件部分；用原來(lái)where條件表達(dá)式中和返回結(jié)果中的投影表達(dá)式構(gòu)造對(duì)應(yīng)數(shù)據(jù)獲取表達(dá)式的返回結(jié)果表達(dá)式.用提取的連接表達(dá)式j(luò)oin($x,$y)構(gòu)成新的主體表達(dá)式中的where條件表達(dá)式，該主體表達(dá)式變成對(duì)數(shù)據(jù)源獲取結(jié)果序列的迭代處理.重寫(xiě)后的結(jié)果如下：

1: let $xseq:= for $x in doc(1)

2: where filter($x,cond)

3: return {proj1($x), proj2($x)}

4: let $yseq:=doc(2)

5: where filter($y,cond)

6: return {proj1($x), proj2($x)}

7: for $x in $xseq, $y in $yseq

8: where join($x,$y)

9: return { proj2($x), proj2($y)}

其中語(yǔ)句1～6為數(shù)據(jù)獲取表達(dá)式；語(yǔ)句7～9為包含連接操作的主體表達(dá)式.查詢重寫(xiě)結(jié)果仍然使用XQuery語(yǔ)法，并未增加新的語(yǔ)法元素，有利于本層次重寫(xiě)結(jié)果的可移植性.

對(duì)1.1節(jié)中的案例經(jīng)查詢重寫(xiě)后如下，

let $useq:=for $u in doc("c:/MR/users.xml")//user_tuple

where $u/rating > "C"

return

let $iseq:=for $i in doc("c:/MR/items.xml")//item_tuple where $i/reserve_price > 1000

return

for $u in $useq,

$i in $iseq

where $i/offered_by = $u/userid

return

重寫(xiě)前后的查詢計(jì)劃，用查詢代數(shù)算子表示分別為示意圖1(a)和1(b).為了簡(jiǎn)化表示，圖中的XML節(jié)點(diǎn)名稱僅用第一個(gè)字符；涉及的主要查詢代數(shù)算子包括連接，投影π，選擇σ和節(jié)點(diǎn)構(gòu)造χ.

圖1 查詢計(jì)劃組織示意

2 數(shù)據(jù)并行處理

2.1 pFL中間語(yǔ)言

由于XQuery語(yǔ)言面向開(kāi)發(fā)人員，語(yǔ)法形式豐富但較為復(fù)雜，在查詢引擎設(shè)計(jì)中，有必要引入更為簡(jiǎn)潔的中間語(yǔ)言表達(dá)查詢計(jì)劃，以利于優(yōu)化處理.本文引入的pFL中間語(yǔ)言，主要采用函數(shù)調(diào)用形式進(jìn)行表達(dá)式求值，易于通過(guò)函數(shù)原語(yǔ)并行化設(shè)計(jì)來(lái)實(shí)現(xiàn)并行.

pFL語(yǔ)法主要包括3類基本表達(dá)式：

(1) 常量 e::=c

(2) 帶局部變量 e::=e where (id=e)* (id(id*)=e)*

(3) 函數(shù)調(diào)用 e::=id(e*)

其中e∈Exp表達(dá)式；id∈ID變量或函數(shù)名；c∈Const常量.用id=e表示變量綁定，即變量id的定義；用id(id*)=e表示函數(shù)綁定，即函數(shù)id()的定義，該函數(shù)帶有數(shù)個(gè)變量.函數(shù)調(diào)用表達(dá)式中，當(dāng)id為并行原語(yǔ)時(shí)，支持并行化處理.

2.2 原語(yǔ)數(shù)據(jù)并行

FLWOR表達(dá)式在中間語(yǔ)言層翻譯成各種操作原語(yǔ)組合，其中常用的FOREACH、FOREACHAT、FILTER和FILTERAT等原語(yǔ)用于對(duì)序列的迭代操作，適合進(jìn)行數(shù)據(jù)并行化設(shè)計(jì).使用pmap描述用于數(shù)據(jù)并行操作，其功能簡(jiǎn)記為pmap(D,F,T)=join(map(D, fork(F), type(F))，其中變量D為數(shù)據(jù)對(duì)象，F(xiàn)為操作任務(wù)，T表示操作類型；用type獲取操作任務(wù)的類型；用fork指定線程執(zhí)行任務(wù)；map為描述數(shù)據(jù)迭代處理的基本原語(yǔ)；join進(jìn)行必要的結(jié)果排序和除重.

使用pmap組織數(shù)據(jù)并行的求值語(yǔ)義描述如下：

pmap::[Thread]→Exp→Exp→Int→Val

pmap((t:ts), (x:xs)┣[e1]ρ, e2, op)= switch(op):

case FOREACH: [e2]ρl{ ρl=ρ+x+t┣getThread(1)}: pmap(ts,xs,e2,op)

case FOREACHAT: ([e2]ρl{ ρl=ρ+x+t┣getThread(1)},index(x)): pmap(ts,xs,e2,op)

case FILTER: (if[e2]ρl{ ρl=ρ+x+t┣getThread(1)} =true) then x else ε): pmap(ts,xs,e2,op)

case FILTERAT: (if [e2]ρl{ ρl=ρ+x+t┣getThread(1)} =true) then (x,index(x)) else ε): pmap(ts,xs,e2,op)

其中ρ,ρl∈Env = (id┣Val)*+(t┣Thread)*，分別表示當(dāng)前求值環(huán)境、線程相關(guān)局部環(huán)境，這里用v┣E表示把變量綁定到表達(dá)式E的求值結(jié)果；id∈ID變量/函數(shù)名稱；t∈Thread邏輯工作線程；局部環(huán)境ρl由線程、函數(shù)閉包以及保存本地變量值及中間計(jì)算結(jié)果的局部堆空間等對(duì)象組成.內(nèi)部函數(shù)getThread(n)表示從線程池中獲取n個(gè)線程；index(x)表示獲取x在序列中的索引.

查詢重寫(xiě)優(yōu)化后，由于分離出了數(shù)據(jù)獲取表達(dá)式，中間語(yǔ)言層的函數(shù)調(diào)用關(guān)系更為清晰，有利于可并行性分析.對(duì)1.2節(jié)查詢重寫(xiě)后程序語(yǔ)句7的$x迭代操作部分并行化，語(yǔ)句7～9的對(duì)應(yīng)的pFL描述形式如：PMAP($x,FOREACH(FILTER($y, JoinFun($x,$y)), ReturnFun), FOREACH)，其中JoinFun表示用pFL表達(dá)的連接操作函數(shù)，ReturnFun表示用pFL表達(dá)的返回操作函數(shù).原來(lái)的for子句迭代操作轉(zhuǎn)換為FOREACH原語(yǔ)函數(shù)調(diào)用，而where條件子句轉(zhuǎn)換為FILTER原語(yǔ)函數(shù)調(diào)用.

2.3 代價(jià)優(yōu)化設(shè)計(jì)

由于FLWOR語(yǔ)句往往嵌套使用，翻譯后的查詢程序可能存在多個(gè)嵌套的迭代原語(yǔ)，如果都進(jìn)行并行化處理，可能造成任務(wù)粒度過(guò)細(xì)，線程管理和通信開(kāi)銷將抵消并行處理帶來(lái)的性能提升，因此可結(jié)合代價(jià)分析等手段，識(shí)別需要調(diào)用并行化原語(yǔ)的地方.

圖2 XQuery查詢引擎工作流程

影響代價(jià)的因素包括數(shù)據(jù)類型、數(shù)據(jù)量、操作頻度和操作類型.代價(jià)計(jì)算公式記為：C= kind(F, type(D))×size(D)，其中C為無(wú)量綱的代價(jià)值，F(xiàn)表示計(jì)算原語(yǔ)，D表示作為內(nèi)部對(duì)象類型的序列數(shù)據(jù)，kind用于判定并獲取不同操作類別在不同數(shù)據(jù)類型下的代價(jià)，type用于獲取數(shù)據(jù)類型，size用于獲得數(shù)據(jù)對(duì)象個(gè)數(shù)，對(duì)應(yīng)F的處理頻度.基本優(yōu)化策略是：在中間語(yǔ)言層估算有效計(jì)算的執(zhí)行時(shí)間代價(jià)，選擇代價(jià)高的迭代操作進(jìn)行數(shù)據(jù)并行；此外，為了控制并行任務(wù)的粒度，根據(jù)代價(jià)對(duì)數(shù)據(jù)迭代操作進(jìn)行分組，為每組計(jì)算任務(wù)分配一個(gè)工作線程.

3 原型系統(tǒng)構(gòu)建

開(kāi)發(fā)的XQuery查詢引擎原型系統(tǒng)包括了編譯模塊和執(zhí)行模塊.其中編譯模塊包括了詞語(yǔ)法分析、查詢重寫(xiě)、規(guī)范化、類型檢查、pFL翻譯等階段；執(zhí)行模塊整合了基本執(zhí)行原語(yǔ)，包括并行化的查詢?cè)Z(yǔ)，圖2顯示了引擎的工作流程.在詞語(yǔ)法分析階段完成XQuery源碼的詞法和語(yǔ)法分析，生成XQuery語(yǔ)法樹(shù)；查詢重寫(xiě)階段實(shí)現(xiàn)第1節(jié)介紹的重寫(xiě)優(yōu)化；在規(guī)范化階段實(shí)現(xiàn)向XQuery核心語(yǔ)言[12]轉(zhuǎn)換，降低中間語(yǔ)言描述的復(fù)雜性，完成語(yǔ)法樹(shù)的預(yù)處理；在類型檢查階段需要根據(jù)XQuery的語(yǔ)義規(guī)范進(jìn)行靜態(tài)類型檢查，完成早期程序錯(cuò)誤檢測(cè)；在pFL翻譯階段實(shí)現(xiàn)pFL查詢計(jì)劃重寫(xiě)，選擇適當(dāng)位置使用并行原語(yǔ).執(zhí)行模塊中引擎以函數(shù)調(diào)用形式完成表達(dá)式求值，其中調(diào)用并行原語(yǔ)函數(shù)以實(shí)現(xiàn)并行處理.

4 實(shí)例測(cè)試

為了驗(yàn)證優(yōu)化方法的實(shí)際效果，選取W3C測(cè)試案例[10]1.4.4節(jié)中9個(gè)實(shí)例作測(cè)試.Q1至Q9查詢分別對(duì)應(yīng)第2、3、4、6、11、15、16、17和18查詢實(shí)例，這些查詢的特點(diǎn)是涉及多個(gè)數(shù)據(jù)源的數(shù)據(jù)獲取和連接操作.查詢涉及3個(gè)XML文檔數(shù)據(jù)，鑒于原有的數(shù)據(jù)量較小，本文根據(jù)案例提供的DTD重新生成較大的XML數(shù)據(jù)，以模擬實(shí)際應(yīng)用情況.測(cè)試硬件平臺(tái)為AMD Athlon II X4 620 (2.60 Ghz) 多核PC，軟件環(huán)境是Windows XP系統(tǒng)運(yùn)行JDK1.6.0_18.圖3顯示了各實(shí)例在查詢重寫(xiě)優(yōu)化前后的執(zhí)行時(shí)間對(duì)比.比如Q2的主體是帶兩個(gè)for的FLWOR結(jié)構(gòu)，where子句包含過(guò)濾操作和連接操作，通過(guò)數(shù)據(jù)源過(guò)濾操作的提取獲得較小相關(guān)數(shù)據(jù)集，大大降低了連接操作強(qiáng)度，執(zhí)行時(shí)間大幅縮短為重寫(xiě)前的17%.Q8僅帶有一個(gè)for子句，where子句未帶過(guò)濾條件，僅進(jìn)行數(shù)據(jù)源投影操作提取獲得較少屬性的數(shù)據(jù)，執(zhí)行時(shí)間縮短為原來(lái)的58.1%.總體來(lái)看，各個(gè)實(shí)例重寫(xiě)后性能均有較大提升，案例平均執(zhí)行時(shí)間縮短為優(yōu)化前的27.3%.

圖3 查詢重寫(xiě)優(yōu)化前后執(zhí)行時(shí)間對(duì)比 圖4 并行化前后執(zhí)行時(shí)間對(duì)比

并行測(cè)試的配置采用Java Concurrent的線程池模式，未設(shè)置固定線程數(shù)目，由JDK管理線程分配.在已完成查詢重寫(xiě)優(yōu)化的前提下，對(duì)并行化前后執(zhí)行時(shí)間對(duì)比如圖4所示，在未進(jìn)行優(yōu)化的情況下，平均效率提升31.6%.并行粒度和負(fù)載均衡程度直接影響到并行化效果，通過(guò)優(yōu)化代價(jià)模型和任務(wù)調(diào)度設(shè)計(jì)，有望進(jìn)一步提高并行效率.

5 結(jié)束語(yǔ)

高效實(shí)用的XQuery查詢引擎的設(shè)計(jì)通常需要整合各種查詢優(yōu)化措施.針對(duì)XQuery多數(shù)據(jù)源查詢進(jìn)行重寫(xiě)優(yōu)化，由于未增加或修改任何語(yǔ)法元素，在XQuery語(yǔ)言層的重寫(xiě)結(jié)果同樣適用于其他查詢引擎，具備良好可移植性.為了充分利用多核計(jì)算環(huán)境以進(jìn)一步提升查詢性能，在中間語(yǔ)言層通過(guò)使用并行原語(yǔ)實(shí)現(xiàn)了數(shù)據(jù)并行處理.引入代價(jià)模型為合理識(shí)別可并行性與控制并行粒度提供了優(yōu)化手段.原型系統(tǒng)的測(cè)試實(shí)驗(yàn)結(jié)果驗(yàn)證了優(yōu)化方法的有效性.

參考文獻(xiàn)

[1] Boag S, Chamberlin D, Fernández M F,etal. XQuery 1.0: An XML query language[EB/OL]. http://www.w3.org/TR/xquery/.2011-03-29.

[2] 孟小峰,王 宇,王小鋒. XML查詢優(yōu)化研究[J]. 軟件學(xué)報(bào), 2006,17(10): 2 069-2 086.

[3] Brantner M, Kanne C C, Moerkotte G. Let a single FLWOR bloom[J]. Database and XMLTechnologies, 2007(2): 46-61.

[4] 廖 偉,廖湖聲,任 宇. 基于 XQuery 的數(shù)據(jù)集成系統(tǒng)中的查詢分解算法[J]. 通訊和計(jì)算機(jī), 2005,2(6): 24-30.

[5] Sutter H. The free lunch is over: A fundamental turn toward concurrency in software[EB/OL].http://www.gotw.ca/publications/concurrency-ddj.htm.2011-04-10.

[6] Li X. Efficient and parallel evaluation of XQuery[D]. Columbus: The Ohio State University, 2006.

[7] Re C, Brinkley J, Hinshaw K,etal. Distributed xquery[C]//Workshop on Information Integration on the Web. Citeseer, 2004:116-121.

[8] Fernández M, Jim T, Morton K,etal. DXQ: A distributed XQuery scripting language[C].Proceedings of the 4th International Workshop on XQuery Implementation, Experience and Perspectives. ACM, 2007:1-6.

[9] Yui M, Miyazaki J, Uemura S,etal. XBird/D: distributed and parallel XQuery processing using remote proxy[C].Proceedings of the 2008 ACM Symposium on Applied Computing. ACM, 2008:1 003-1 007.

[10] Chamberlin D, Fankhauser P, Florescu D,etal. XML Query Use Cases[EB/OL]. http://www.w3.org/TR/xquery-use-cases/.2011-03-29.

[11] Garcia-Molina H, Ullman J. D, Widom J. Database system implementation[M]. Prentice Hall Upper Saddle River, 2000.

[12] Draper D, Fankhauser P, Fernández M F,etal. XQuery 1.0 and XPath 2.0 Formal Semantics[EB/OL]. http://www.w3.org/TR/xquery-semantics/.2011-04-10.