基于函數(shù)式中間語言的XML查詢并行化

陳榮鑫

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

隨著網(wǎng)絡(luò)的普及和網(wǎng)絡(luò)服務(wù)的發(fā)展，XML作為信息交換和存儲標(biāo)準(zhǔn)被日益廣泛應(yīng)用［1－4］。XML是半結(jié)構(gòu)化數(shù)據(jù)，用戶對其進行查詢和變換等操作需要通過特定的語言實現(xiàn)。XQuery語言［5］是W3C推薦的查詢XML數(shù)據(jù)的國際標(biāo)準(zhǔn)，被業(yè)界廣為接受。從桌面系統(tǒng)、企業(yè)級Web服務(wù)到云計算平臺，XQuery在各種應(yīng)用場景中得到逐步推廣。XQuery語言的編譯和執(zhí)行依靠XML查詢引擎完成，各種查詢的編譯設(shè)計和優(yōu)化措施對引擎性能的提升起關(guān)鍵作用［6］。

由于單機系統(tǒng)日益難以滿足服務(wù)級的查詢需求，不少研究轉(zhuǎn)向多機群集系統(tǒng)，試圖利用分布式技術(shù)來提高查詢性能。S.Abiteboul等［7］開展的ActiveXML(AXML)項目把 Web服務(wù)函數(shù)嵌入XML文檔中，函數(shù)調(diào)用后將把執(zhí)行結(jié)果更新到XML文檔中，支持各種優(yōu)化和延遲求值。C.Re等［8］把 XQuery語言擴展成面向分布計算的XQueryD語言，給出分布式查詢方案，支持查詢遷移，以避免高代價的數(shù)據(jù)遷移。M.F.Fernàndez等［9］設(shè)計了用于分布式XML查詢的DXQ語言，支持更新語義和遠(yuǎn)程異步執(zhí)行。Y.Zhang等［10］結(jié)合XQuery函數(shù)和RPC規(guī)范提出XRPC，按消息傳遞機制實現(xiàn)遠(yuǎn)程調(diào)用。這些研究為用戶提供分布計算的語言描述和執(zhí)行環(huán)境支持，而XQuery查詢并行化研究目前開展得還很有限。X.Li［11］給出一個XQuery并行化框架，由編譯器完成并行化重寫，但未結(jié)合XQuery語義分析典型查詢條件下的情況，適用性有限。

由于多核計算環(huán)境的日益普及，并行化成為進一步提高應(yīng)用程序性能的重要途徑，也是軟件設(shè)計和開發(fā)的趨勢［12］，但面向多核計算的XML并行化的有效方法還有待發(fā)展。本文關(guān)注XML查詢在多核計算環(huán)境中的并行化問題，介紹XML查詢相關(guān)背景，指出中間語言的作用，給出函數(shù)式中間語言pFL的語法和語義以及執(zhí)行層的并行化設(shè)計，構(gòu)建一個基于pFL的查詢引擎，并進行實例測試，最后展望了未來的研究方向。

1 XML查詢相關(guān)背景

1.1 XQuery查詢語言

XQuery語言作為 XML專用查詢語言，于2007年1月成為W3C正式推薦標(biāo)準(zhǔn)。由于XQuery是聲明式語言，語法簡潔，易學(xué)易用，而且表達能力強，適合描述各種復(fù)雜的XML數(shù)據(jù)查詢，正成為主流的XML查詢語言而被廣為接受。XQuery的主要作用是從XML數(shù)據(jù)中查找和提取元素及屬性，并重新組織XML數(shù)據(jù)輸出。XQuery也支持各種算術(shù)/邏輯運算和字符串處理等其他通用數(shù)據(jù)操作。XQuery中最重要的語法結(jié)構(gòu)是FLWOR語句，對應(yīng)的語法元素包括for/let綁定(FL)、where謂詞過濾(W)、order by排序(O)和return返回結(jié)果(R)。FLWOR語句可以嵌套使用，以構(gòu)成功能強大的查詢程序。

由于XQuery是一種函數(shù)式語言，程序各個部分的計算順序無關(guān)性適合并行化處理［13］，且函數(shù)式求值無副作用，正確性容易保證，因此可考慮通過重寫變換實現(xiàn)并行化。

1.2 XML 數(shù)據(jù)模型

XML查詢基本操作依賴特定的數(shù)據(jù)模型。由于處理的數(shù)據(jù)對象是半結(jié)構(gòu)化的XML數(shù)據(jù)，因此XQuery使用的數(shù)據(jù)模型XDM(XQuery/XPath Data Model)［14］與傳統(tǒng)的關(guān)系數(shù)據(jù)模型有很大差別。XDM是一種層次化、節(jié)點順序敏感且具備唯一性的結(jié)構(gòu)。XQuery的查詢輸入和輸出均為XDM的實例，具備封閉性計算特點。XDM中包含有文檔、元素、屬性、文本、名字空間、指令和注釋等類型的節(jié)點，同時還包含原子值節(jié)點，對應(yīng) XML Schema中定義的各種簡單類型。XML查詢引擎內(nèi)部通過各種accessors方法存取XDM的節(jié)點序列來訪問XML數(shù)據(jù)，而用戶則可以通過XQuery定義的軸操作函數(shù)來訪問XML數(shù)據(jù)。某些查詢引擎使用了自定義的內(nèi)部數(shù)據(jù)模型，以支持特定的操作，比如為了提高XQuery的處理效率，有必要支持高效的Twig查詢［15］，可通過為 XDM擴展內(nèi)部數(shù)據(jù)表示，增加特定的XML編碼描述，以支持Twig查詢。

1.3 查詢中間語言

XQuery語言面向開發(fā)人員，語法形式豐富且復(fù)雜，在查詢引擎設(shè)計中，需要引入更為簡潔的中間語言作為變法表達形式，以降低復(fù)雜性。此外，采用特定中間語言以描述查詢計劃，便于執(zhí)行層的設(shè)計和優(yōu)化實現(xiàn)。W3C給出的XQuery核心語法［16］可作為中間語言，不少查詢引擎設(shè)計據(jù)此作為描述查詢計劃的方法，而某些查詢引擎為了支持樹查詢模式［15］，引入了特定的中間語言，通過中間語言的分析和重寫，較易實現(xiàn)查詢并行化處理。本文為了便于并行化處理，引入了pFL函數(shù)式中間語言。

2 pFL函數(shù)式中間語言

2.1 pFL 語法描述

pFL中間語言語法如表1所示。表中e∈Exp為表達式;id∈ID為變量或函數(shù)名;c∈Const為常量。帶局部變量表達式中id=e表示變量綁定，即變量id的定義;id(id*)=e表示函數(shù)綁定，即函數(shù)id()的定義，該函數(shù)本身帶有數(shù)個變量。函數(shù)調(diào)用表達式中，當(dāng)id為并行原語標(biāo)記時(比如PMAP、PIPELINE、PARA、PFUTURE 和 PCOND)，用于描述對應(yīng)的并行行為。

pFL使用PMAP描述用于數(shù)據(jù)并行操作，其功能簡單表示為 PMAP(D，f)=join(map(D，fork(f))，其中:D為數(shù)據(jù)對象;f為操作任務(wù)，用fork指定線程執(zhí)行任務(wù);map用于描述數(shù)據(jù)迭代處理的基本原語，包括核心語法中 for循環(huán)綁定和where謂詞過濾等對應(yīng)的執(zhí)行原語;join進行必要的結(jié)果排序和除重。pFL還包含流水線并行原語PIPELINE，以及2種類型的任務(wù)并行原語PARA和PFUTURE，分別用于預(yù)測(speculative)任務(wù)并行和保守任務(wù)并行。用PCOND表示pcond(e1，e2，e3)，該函數(shù)支持條件表達式的預(yù)測并行化求值，對應(yīng)XQuery核心語法中的if e1 then e2 else e3表達式。pFL語言是函數(shù)式的，和XQuery語言特性完全兼容。此外，該語言進一步簡化了XQuery核心語法的表達方式，便于底層執(zhí)行機制的實現(xiàn)。

表1 pFL基本語法

2.2 pFL 語義描述

中間語言通過并行原語組織，表達并行化語義;并行原語執(zhí)行，實現(xiàn)了查詢的并行處理。語義方程中的變量定義如:ρl，ρs∈Env=(id┣Val)*+(t┣Thread)*局部環(huán)境與共享環(huán)境，這里:┣表示綁定關(guān)系;id∈ID為變量/函數(shù)名稱;t∈Thread為邏輯工作線程;局部環(huán)境ρl由線程、函數(shù)閉包、局部堆空間(例如本地變量、中間計算結(jié)果等)等對象組成，可帶數(shù)字以區(qū)別不同局部環(huán)境;共享環(huán)境ρs包括線程池、共享堆空間(如XML-dom信息等)等。由并行原語實現(xiàn)并行處理，只需考慮id(e*)中出現(xiàn)調(diào)用并行原語的求值語義。有以下的求值語義描述，其中用［］表示表達式求值計算，用{}表示環(huán)境的內(nèi)容。

原語函數(shù)pmap、partition、getone、touch等定義了幾個主要的求值規(guī)則，如下所示:

1)數(shù)據(jù)并行規(guī)則

2)數(shù)據(jù)劃分規(guī)則

3)流水線的數(shù)據(jù)傳遞規(guī)則

2.3 執(zhí)行層并行化設(shè)計

在共享求值環(huán)境中定義了多線程執(zhí)行服務(wù)線程池 Executor exec←new Executor()，結(jié)合 Java Concurrent設(shè)計執(zhí)行層的數(shù)據(jù)并行，簡要的框架算法如下:

輸入?yún)?shù)是各個數(shù)據(jù)集合信息。第1行新建一個以數(shù)據(jù)集內(nèi)數(shù)據(jù)塊數(shù)目為參數(shù)的計數(shù)器，用于任務(wù)同步計數(shù);第2行獲取共享環(huán)境中的多線程執(zhí)行服務(wù);第4行指派各個線程并行執(zhí)行任務(wù);第5行保證所有子任務(wù)的同步。完成所有任務(wù)后，系統(tǒng)將通過exec.shutdown();關(guān)閉線程服務(wù)。

3 原型系統(tǒng)設(shè)計

XML查詢引擎通過整合并行化中間語言pFL，實現(xiàn)對并行查詢的支持，其工作示意圖如圖1所示，具體包括以下工作模塊。

1)詞語法分析:完成XQuery源碼的詞法和語法分析，生成XQuery語法樹。

2)規(guī)范化:實現(xiàn)向XQuery核心語言轉(zhuǎn)換。為了降低中間語言描述的復(fù)雜性，該步驟根據(jù)XQuery語義規(guī)范［12］生成核心代碼，完成語法樹的預(yù)處理。

3)靜態(tài)類型檢查:根據(jù)XQuery的語義規(guī)范，完成靜態(tài)類型檢查。XQuery是強類型語言，該步驟進行類型合法性驗證，完成早期程序錯誤檢測，以提高程序健壯性。

4)依賴分析:完成基本計算的依賴分析，提供并行化的判別條件。通過分析核心語法樹，找出各計算之間的相互依賴關(guān)系和數(shù)據(jù)在各計算之間的傳遞方式。

5)pFL重寫:實現(xiàn)pFL查詢計劃重寫，在適當(dāng)位置使用并行原語。根據(jù)依賴分析結(jié)果，對存在相互獨立的計算考慮采用任務(wù)并行;對存在數(shù)據(jù)平行迭代計算的情況考慮采用數(shù)據(jù)并行;對存在數(shù)據(jù)傳遞的計算考慮采用流水線。各種并行方法按重寫規(guī)則進行合理組織。

6)并行執(zhí)行:在執(zhí)行層執(zhí)行查詢計劃。調(diào)用并行原語函數(shù)，以實現(xiàn)并行處理。

7)XML解析:進行XML解析，獲取DOM信息，通過包裝提供查詢可用的數(shù)據(jù)模型。該部分是相對獨立的工作模塊。

圖1 XML查詢引擎整合工作示意圖

4 實例測試

為了測試基于pFL的原型系統(tǒng)在多核計算環(huán)境下的工作效果，采用典型案例，獲取不同數(shù)量工作線程下的執(zhí)行時間，并計算各案例的加速比。查詢案例如表2所示。編寫一個具有較高時間復(fù)雜度的自定義函數(shù)local:bigfun，用以模擬關(guān)鍵執(zhí)行步。Loop程序是簡單的循環(huán)綁定操作，適合進行數(shù)據(jù)并行，驗證FOREACH原語的并行工作效果;Flwor程序是個典型的FLWOR語句，可以驗證FILTER原語并行工作;XmarkQ是來自XMark測試平臺的一個查詢實例，用于測試一般的XQuery查詢程序的并行化執(zhí)行效果。

本文的測試硬件平臺是AMD Athlon II X4 620(2.60 Ghz)4核PC，軟件環(huán)境是Windows XP系統(tǒng)，運行JDK1.6.0_18。通過獲取測試程序在各線程條件下的平均執(zhí)行時間計算加速比。以程序原有的串行執(zhí)行時間T1作基準(zhǔn)，在n個線程下的解析時間為Tn，則此時的加速比Sn=Tn/T1。實驗獲得的加速比結(jié)果如圖2所示。由于Loop是簡單的循環(huán)綁定，各循環(huán)項負(fù)載容易均衡，獲得了接近理想線性的加速比。XmarkQ是實際應(yīng)用中的一般查詢程序，在4個工作線程條件下，獲得的平均加速比為3.1，效果良好。

表2 測試程序

圖2 加速比

5 結(jié)束語

XML查詢性能的提升是現(xiàn)實應(yīng)用中的重要需求。目前存在多種查詢編譯優(yōu)化方法，并發(fā)展了各種適應(yīng)多機系統(tǒng)的分布式查詢方式。隨著多核環(huán)境的普及，并行化作為重要優(yōu)化途徑值得深入研究。本文給出基于函數(shù)式中間語言pFL進行并行化的方法，通過原型系統(tǒng)的初步測試實驗，獲得較好加速比。未來的研究主要考慮引入代價模型，以便更有效地進行任務(wù)劃分。通過逐步完善自動并行化的機制，實現(xiàn)面向多核并行計算的XML查詢并行化，以滿足日益增長的查詢性能提升需求。

［1］朱慶生，戴剛.基于XML的安全數(shù)據(jù)交換模型［J］.重慶工學(xué)院學(xué)報:自然科學(xué)版，2009，23(6):36－39.

［2］汪維華，汪維清，李靈.基于XML的Web模型研究［J］.重慶文理學(xué)院學(xué)報:自然科學(xué)版，2006，(5)4:16－19.

［3］羅凌.XML數(shù)字簽名在電子公文交換中的應(yīng)用［J］.重慶師范大學(xué)學(xué)報:自然科學(xué)版，2008，25(2):46－49.

［4］劉長勇，寧正元.基于XML的高性能數(shù)據(jù)庫連接池設(shè)計方案［J］.重慶工學(xué)院學(xué)報:自然科學(xué)版，2009，23(2):176－180.

［5］Boag S，Chamberlin D，F(xiàn)ernández M F，et al.XQuery 1.0:An XML query language［EB/OL］.［2011 －04 －10］.http://www.w3.org/TR/xquery/.

［6］孟小峰，王宇，王小鋒.XML查詢優(yōu)化研究［J］.軟件學(xué)報，2006，17(10):2069 －2086.

［7］Abiteboul S，Benjelloun O，Milo T.The Active XML project:an overview［J］.The VLDB Journal，2008，17:1019－1040.

［8］Re C，Brinkley J，Hinshaw K，et al.Distributed xquery［C］//Workshop on Information Integration on the Web.Citeseer:［s.n.］，2004:116 －121.

［9］Fernández M F，Jim T，Morton K，et al.DXQ:A distributed XQuery scripting language［C］//Proceedings of the 4th international workshop on XQuery implementation，experience and perspectives.［S.l.］:ACM，2007:1 －6.

［10］Zhang Y，Boncz P.XRPC:interoperable and efficient distributed XQuery［C］//Proceedings of the 33rd international conference on Very large data bases.［S.l.］:VLDB Endowment，2007:99 －110.

［11］Li X.Efficient and parallel evaluation of XQuery［D］.Columbus:The Ohio State University，2006.

［12］Sutter H.The free lunch is over:A fundamental turn toward concurrency in software［EB/OL］.［2011 －04 －10］.http://www.gotw.ca/publications/concurrencyddj.htm.

［13］Hammond K.Parallel functional programming:An introduction［C］//International Symposium on Parallel Symbolic Computation.Citeseer:［s.n.］，1994.

［14］Fernández M F，Malhotra A，Marsh J，et al.XQuery 1.0 and XPath 2.0 Data Model(XDM)［EB/OL］.［2011 －04 －10］.http://www.w3.org/TR/xpath-datamodel/.

［15］Bruno N，Koudas N，Srivastava D.Holistic twig joins:optimal XML pattern matching［C］//Proceedings of the SIGMOD Conference.［S.l.］:［s.n.］，2002:310 －321.

［16］Draper D，F(xiàn)ankhauser P，F(xiàn)ernández M F，et al.XQuery 1.0 and XPath 2.0 Formal Semantics［EB/OL］.［2011－04 － 10］.http://www.w3.org/TR/xquery-semantics/.