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

陳榮鑫

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

隨著網絡的普及和網絡服務的發展，XML作為信息交換和存儲標準被日益廣泛應用［1－4］。XML是半結構化數據，用戶對其進行查詢和變換等操作需要通過特定的語言實現。XQuery語言［5］是W3C推薦的查詢XML數據的國際標準，被業界廣為接受。從桌面系統、企業級Web服務到云計算平臺，XQuery在各種應用場景中得到逐步推廣。XQuery語言的編譯和執行依靠XML查詢引擎完成，各種查詢的編譯設計和優化措施對引擎性能的提升起關鍵作用［6］。

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

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

1 XML查詢相關背景

1.1 XQuery查詢語言

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

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

1.2 XML 數據模型

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

1.3 查詢中間語言

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

2 pFL函數式中間語言

2.1 pFL 語法描述

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

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

表1 pFL基本語法

2.2 pFL 語義描述

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

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

1)數據并行規則

2)數據劃分規則

3)流水線的數據傳遞規則

2.3 執行層并行化設計

在共享求值環境中定義了多線程執行服務線程池 Executor exec←new Executor()，結合 Java Concurrent設計執行層的數據并行，簡要的框架算法如下:

輸入參數是各個數據集合信息。第1行新建一個以數據集內數據塊數目為參數的計數器，用于任務同步計數;第2行獲取共享環境中的多線程執行服務;第4行指派各個線程并行執行任務;第5行保證所有子任務的同步。完成所有任務后，系統將通過exec.shutdown();關閉線程服務。

3 原型系統設計

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

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

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

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

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

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

6)并行執行:在執行層執行查詢計劃。調用并行原語函數，以實現并行處理。

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

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

4 實例測試

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

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

表2 測試程序

圖2 加速比

5 結束語

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

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

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

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

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

［5］Boag S，Chamberlin D，Ferná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查詢優化研究［J］.軟件學報，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，Fankhauser P，Ferná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/.