一種基于XQuery的運行專門化處理算法

□□ 陳俊祺

(武警山西總隊參謀部，山西 太原 030012)

引言

隨著越來越多的信息被存儲、交換和使用XML呈現，查詢XML數據源的能力變得越來越重要。為解決這一能力需求，W3C XML查詢工作組設計了XQuery程序語言。它是一種函數式語言，查詢簡便，易于理解，應用靈活，可以查詢廣泛的XML信息源，包括數據庫和文檔。XML近年來已經成為Web上數據表示和交換的事實標準，對XQuery處理效率的要求也越來越高。在XQuery的研究領域中，已經開發出一些新技術，用于提高處理效率，但在這一領域中很少用到“部分評估”的優化技術。為了找到一種提高XQuery處理效率的新方法，擴展了“部分評估”技術的應用范圍，進一步研究了XQuery語言的部分評價技術。

部分評估，也稱為“程序專門化”，是一種專門的程序轉換技術。給定一個源程序和一個稱為“靜態輸入”的輸入數據一部分，部分評估根據在使用靜態輸入分析程序后提取程序中的不變量，生成一個剩余程序。當應用到剩余輸入數據時稱為“動態輸入”，剩余程序產生的結果與源程序在應用于所有輸入時所產生的結果相同，通常情況下，剩余程序運行比原始程序快。第一個關于程序專業化的應用出現在1980年代早期，在隨后的幾年里，大多數研究人員在編譯時和源代碼中探索了該技術，但是編譯時專門化技術并不適合于應用程序領域，而用于專門化程序的不變量只能在運行時處理。因此，一些研究人員在運行時開發了一些專門的程序。在XQuery的應用程序領域中，動態生成的查詢被廣泛采用，如使用XQuery與Java API(XQJ)的應用程序。在XQJ中，xqpreparedex抑制的執行過程被分為兩個階段：準備階段和執行階段。準備階段相當于XQuery中的靜態分析階段，在該階段中，靜態類型檢查或其他靜態分析可以為已完成的XQuery程序完成；與動態階段相對應的執行階段，在這種情況下，當“executeQuery()”方法被調用時，查詢的值會被多次評估，而不需要再次靜態地重新分析表達式。在運行XQJ時，數據源通常在準備階段被知道，這可以被看作是查詢的不變量。因此，可以使用運行時專門化(RTS)來提高查詢的執行效率。

為此，本文設計了一種名為XQPE的XQuery編程語言的離線部分評估系統。XQPE在編程語言上擴大了部分評估技術的應用范圍，使用XQuery及其應用程序，其中包括基于RTS的XQJ應用程序框架。

1 技術背景

Hornof L等[1]已經為C程序開發了一個部分評估器，名為Tempo，一個離線的部分評估器。它也不會在運行時只在編譯時崩潰時專門化程序。在C程序中，有些值不能被編碼到剩余程序中，應該作為非liftable(如C程序中的指針)進行注釋。為了確保正確的專門化，Tempo使用評估時間分析來查找那些非liftable值。

DyC是基于特定運行時間的基于注釋的C系統。其執行動態編譯，在用戶控制關鍵決策的情況下，對程序轉換的靈活和系統的部分評估模型進行了動態編譯。他們的注釋設計是通過搜索一組靈活的原始指令來管理動態編譯的，這適用于人類程序員和工具。與Tempo相比，DyC分析處理的是標量局部變量，但全局變量、指針或數據結構，DyC使用特殊編譯器的專用變體，而不是像Tempo那樣在現有的標準編譯器上使用。

Lee P等[2]建議對法比尤斯的研究比DyC和Tempo更有限。在運行時，將在XML中編寫的普通程序轉換為本機代碼。但與DyC和Tempo不同的是，FABIUS自動執行所有動態編譯優化，沒有附加注解；動態編譯過程中涉及的權衡不是用戶控制的。

Hidelhiko H等[3]提出了一種字節碼專門化(BCS)技術，該技術可以在運行時對Java虛擬機(JVM)語言程序進行專門化。其二進制時間分析算法直接處理字節碼程序，使BCS獨立于源代碼級語言和編譯器的內部。

在部分評價技術中，特別是在運行時專門化研究的基礎上，研究了XQuery編程語言離線部分評價的編譯時間和運行時專門化。

2 知識準備

作為一種新的函數語言，XQuery有一些不適合程序專門化的特性。為了解決這些問題，引用敏感性分析(RSA)和兩相結合時間分析(BTA)，以確保精度和提高專門化的正確性。RSA和兩相BTA的詳細描述在文獻[4]和文獻[5]中都有表示。

2.1 敏感性分析

在XQuery表達式的基本構建塊,和其值都是存儲為XML數據模型(一棵樹)實例[5]，由無約束的節點和/或原子值序列,如XML片段由節點值,表示數字“5”是由原子值5。在程序專門化中，通常對靜態表達式的值進行常量折疊以生成剩余程序，這意味著這些值應該在剩余程序中進行編碼。這就很容易對一個原子值進行編碼，比如使用數字“5”來表示原子值5，但是沒有適合的形式來編碼XML節點。其原因是一個節點不僅包含XML片段的字符串值，還包含一些有用的語義信息，如節點標識和文檔順序。為了在剩余程序中對節點進行編碼，除了使用構造函數操作將節點重構為XML片段之外，沒有其他選擇。然而，新的重構XML片段僅復制了字符串值，并且丟失了原始節點的一些語義信息，但很少有表達式通過使用XQuery中的信息計算出它們的值。如節點比較操作(“《”、“》”或“is”)需要兩個參數的文檔命令來完成，計算示例見表1和表2。

表1 生成錯誤的表達式(示例1)

表2 生成正確的剩余表達式(示例2)

表1顯示了不能為節點進行專門化的情況。在表1的A示例中，“S|m”的節點比較“是”將專門用于剩余程序。“S|m”的文檔順序已經丟失(實際上，“S|m”的新構造段將被視為一個新文檔，并被分配給一個新的文檔順序)，因此，比較不同文檔的節點是沒有意義的，對應的剩余程序結果，見表1。B示例一定是一個錯誤的結果。這意味著即使它們的綁定時間是靜態的，一些表達式也不能專門化。相反，表2顯示了“S|m”的值可以按傳統方式進行專門化。

從表1和表2中可以發現，如果任意地對所有節點進行特殊化，可能會出現一些操作需要丟失信息錯誤的專門化；如果只是簡單地禁止節點的所有專門化，那么XQuery專門化的精度將會非常糟糕，因為大多數表達式的結果都是XQuery中的節點。

參考敏感性分析(RSA)發現并注釋了計算將滿足重建后語義信息丟失問題的表達式。在RSA之后，specializer將會得到表1中“S|m”的信息，不能專門化，但是表2中的“S|m”可以專門化，這意味著專門化的正確性和精確性可以在一定程度上得到保證。RSA的詳細信息幫助專家實現了高效專業化[4]。

2.2 兩個階段綁定時間分析

RSA給出了信息，這些狀態對每個被稱為“引用-敏感狀態(RSA)”的表達式進行了注釋，以指出當它的綁定時間為靜態時，表達式是否可以專門化。這意味著傳統的BTA需要擴展。因此，設計了兩個階段的綁定時間分析，前一個階段是BTA1，在這個階段中，表達式被識別并標注了綁定時間分析狀態(BTAS)，它只依賴于配置中可用的靜態參數值，以及程序中可用的靜態信息(如常量)；后一階段是BTA2，用于根據BTA1給出的RSA和BTAS對表達式進行修改。

在表1中，在做了RSA之后，“S|m”被標注為RSA—FALSE，這意味著這個變量不能專門化。在執行BTA1之后，“$m”被注釋到BTAS(靜態的)，然后在執行BTA2之后，BTAS“S|m”將會修改到最后的BTAS，即根據注釋的RSA和BTAS保留。相反，表2中的“S|m”將被注釋到最終的BTAS-STATIC，在完成RSA之后，它給出了RSA—TURE、BTA1、BTAS-STATIC。因此，表1中的變量“S|m”不能專門化，但它的對等物可以專門用于表2。

示例1和示例2的正確結果見表3。

表3 示例1和示例2的正確結果

3 運行時專門化

特定編譯(compile-time specialization)目前已經被成功應用。試驗結果表明，XQuery程序的效率可以顯著提高。在特定編譯中，不變量或靜態配置被接受用于專門化；但在運行時應用程序可以在執行過程中給出信息。如在XQJ應用程序中，數據源和XQuery程序都是在準備階段實現的，可以提取這些信息進行專門化處理。因此，為了在此場景中擴展XQuery專門化，將相應地研究運行時專門化技術。

3.1 運行時專門化

在預處理之后，解析的抽象語法樹(AST)中的每個表達式都帶有一個綁定時間。在特定運行時間中，對靜態狀態的表達式進行了評估，并在AST中完成了相應的結果，最后將AST轉換為剩余代碼，即Java字節碼級別。設計以下步驟來實現特定運行時間：

(1)解析XQuery源代碼到AST。

(2)評價AST中靜態表達式的值。

(3)在全局環境中存儲這些值。

(4)使用特殊的數據攣縮，稱為孔洞，代替AST中評估的表達式。

(5)在全局環境中添加對孔的綁定和相應的值。

(6)用Java字節碼來編譯AST，Java字節碼可以直接在Java虛擬機(JVM)上運行。

完成這些任務后，即完成了專門化并生成字節碼級別的剩余程序。在JVM上運行剩余程序時，需要從全局環境中加載所需的孔值。

表4顯示了運行時專門化和編譯時專門化的比較。為了簡單地表示，將使用PSEUDO代碼來表示運行時專門化的結果。在表4的A中，“OP:CON”是AST中的一個表達式。參數“S|m”被一個洞取代，這里是孔(2)。孔中的參數“2”表示綁定值的索引。當執行剩余表達式時，JVM將從這個孔獲取索引值。在表4的B中，編譯時專門化顯示了“OP:CON”與“S|m”的值應該編碼到XQuery代碼。

表4 運行時專門化和編譯時專門化

XQuery運行時特殊化原型系統如圖1所示，其包括三個部分：

圖1 XQuery RTS模型系統

(1)XQuery解析器，其輸入是XQuery源代碼，并輸出相應的AST。

(2)XQuery部分評估核心，其輸入是由配置和AST提供的不變量，其輸出是具有漏洞的AST和存儲索引值的全局環境。

(3)字節碼編譯器將AST編譯成Java字節碼，它使用全局環境在JVM上運行時獲得索引。

3.2 代碼爆炸控制

在專門化過程中，展開循環可能導致代碼爆炸，這是部分評估中的一個關鍵問題，至今還沒有一個簡單有效的方法來解決該問題。在運行時專門化中，值將不會被編碼到XQuery代碼中，并且只保留它們的內存實例，因此在執行遞歸函數調用和多級“FLWOR”表達式時，會發生代碼爆炸。擬使用保守的策略在一定程度上控制代碼爆炸。該策略包括兩個主要方面：

(1)遞歸函數調用的控制。使用一個動態分支狀態(DBS)來標記遞歸函數調用，如果它屬于一個“if”表達式的一個分支(也包含“typeswitch”表達式)，并且它的條件綁定時間不是靜態的，那么將這個函數標記為一個真實的狀態，否則標記為FALSE。這意味著當為遞歸函數調用進行專門化時，專門化器首先檢測DBS，如果DBS為真，那么它生成一個專門的函數，但不會在剩余程序中展開這個遞歸函數。

(2)多級“FLWOR”表達式的控制。使用閾值來控制“FLWOR”表達式是否應該展開。當專門化一個多級別的“FLWOR”時，首先檢查“FLWOR”中的每個“for”子句的值，如果該值的長度大于閾值，則該“for”子句的專門化將被取消；擴展了該子句來進行專門化處理。

4 應用示例

4.1 XQJ應用程序框架

Java的XQuery API目前在Java Community Process的開發中作為JSR 225，提供了應用程序開發人員使用XQuery進行XML處理和數據集成應用程序的機會，并充分支持Java SE和Java EE平臺。XQJ允許Java程序連接到XML數據源，準備和執行XQuery程序，并將查詢結果作為XML文檔進行處理。這個功能類似于SQL的JDBC Java API，但是XQJ的查詢語言是XQuery。

用Java語言描述的程序代碼見表5。此代碼段僅限于表述XQJ API的使用方法，不是詳盡或完整的程序段。如假設“xqds”表示一個給定數據源的“XQDataSource”對象。它說明了Java應用程序執行XQuery表達式的基本步驟(第12和17行)，并在給定的XQuery實現中執行第8和第13行調用的綁定變量。

表5 一個XQL示例

這是一個典型的應用場景，在只有一些輸入值改變的情況下，該應用程序可以多次執行一個查詢。XQJ給出了準備表達式的概念，只有一次靜態分析時可以多次執行，而不需要每次都靜態分析一遍(見代碼形式4～10行)。所以，XQPreparedExpression的準備階段可以用于做專業化。而XQuery中的外部變量，通過使用接口bindXXX()綁定到動態值，可以看作是專門化的動態輸入。比較第11～14行和第16～18行的代碼段，只有bindInt()中的值是不同的，其他代碼是相同的。在XQPrapredExpression中，“fn:doc('catalog.xml')”、“/prince”和“/name”的表達式在運行時不會再次發生變化，這些都被視為專門化的不變量。顯然“XQPreparedExpression”的處理非常適合做部分評估。此外，在Java應用程序中，查詢可能是動態接受的(如來自網絡、I/Os，甚至是程序創建的)。

運行時專門化非常適合為XQJ應用程序進行優化。為此開發了一個XQJ應用程序框架如圖2所示，其中XQuery處理是通過運行時XQuery專門化來優化的。

圖2 基于RTS的XQJ應用程序框架

圖2描述了基于RTS的XQJ應用程序框架。該框架有三個主要部分：

(1)XQJ接口。它接受java對象實例，其中存儲了XQuery源代碼。它的輸出包括凈化XQuery程序和外部變量，這些變量的值將被視為動態輸入。所有這些對于用戶都是透明和自動處理的。它還接受由JVM返回的Java對象實例的最終結果，并將結果輸出。

(2)RTS專業化系統。它接受自動凈化的XQuery程序進行專門化。在專門化之后，它會輸出剩余程序(Java字節碼)和相應的全局環境。

(3)JVM。它使用被接受的剩余程序和全局環境來完成計算和返回查詢結果。

4.2 結果驗證

測試條件：分節的標題應該是新羅馬12點的粗體，只有首字母大寫(注：對于子分段和次子分段，像the或者a等單詞不大寫，除非是分段頭的第一個單詞才大寫。)

基于運行時專門化的XQJ已經實現，并進行了一系列的驗證，以測試該工作是否能夠真正提高XQJ的執行效率。下面使用14個案例在三個不同的XQJ實現中運行：

A組：在XQJ實現中，當執行exectueQuery()方法時，XQuery程序由一個解釋器執行；

B組：在XQJ實現中，XQuery程序是在準備階段編譯的，然后在調用executeQuery()方法時執行它；

C組：在XQJ實現中，XQuery程序在準備階段通過RTS進行優化，然后在調用exectueQuery()方法時執行。

所有的案例都運行在一個具有1 GB物理內存的Inter Pentium PIV-1.6處理器上。執行時間如圖3所示，C組大多數病例的執行時間均小于其他兩組。C組的平均執行時間為23.9%，B組為40.5%。這意味著RTS可以顯著提高XQJ的處理效率。

圖3 三組執行時間比較

5 結語

全面介紹了一種用于XQuery編程語言的運行時專門化技術。在運行時專門化的預處理階段，使用引用敏感性分析來發現和注釋值將參與計算的表達式，這些表達式需要語義，并且這些表達式不應該在剩余程序中專門化和編碼，即使它是一個靜態表達式。相應地，綁定時間分析不僅根據配置參數和其他靜態信息對表達式進行注釋，而且根據引用敏感性分析狀態對表達式進行重新注釋。在專門化階段，首先在AST中添加了一個帶有索引的漏洞，以專門化靜態表達式，生成一個全局環境，該環境存儲被索引的專門化值，然后將此AST編譯成Java字節碼。一個保守策略用于防止遞歸函數的無限特殊化，并使用閾值來控制“for”子句的展開。開發了一個XQuery運行時專門化原型系統。

在應用領域，基于運行時專門化設計并實現了XQJ應用程序框架。測試結果表明，RTS可以顯著提高XQJ應用的執行效率。XQuery程序的運行時專門化的研究并成功地將其應用于XQJ接口，從而擴大了部分評估的應用范圍。為大多數應用程序需求提供了XQuery程序的編譯時和運行時專門化。但是也有一些重要的后續工作要做，如利用XQuery表達式的類型信息來提高綁定時分析的精度，這可以從XML文檔的XML模式中推斷出來。