基于MapReduce的XML結構連接處理*

李　東，鄧澤航，李祖立華南理工大學 軟件學院，廣州 510006

基于MapReduce的XML結構連接處理*

李東+，鄧澤航，李祖立
華南理工大學 軟件學院，廣州 510006

LI Dong,DENG Zehang,LI Zuli.Structural join processing for XML based on MapReduce.Journal of Frontiers of Computer Science and Technology,2016,10(8)：1080-1091.

摘要：可擴展標記語言（extensible markup language，XML）已經成為Web上數據表達和數據交換的事實標準，Hadoop已成為云計算和大數據處理典型支撐框架之一，基于Hadoop MapReduce來實現XML查詢處理十分必要。為了實現基于MapReduce的XML查詢處理，首先實現了區間編碼、前綴編碼和層次編碼等3種不同的XML數據編碼方式，以此為基礎來研究和實現基于MapReduce的XML結構連接處理。為查詢處理建立了代價模型，通過代價估算獲得優化的查詢計劃樹。最后開展了XML查詢處理實驗評估，結果表明相對其他兩種XML編碼方式，區間編碼方式下實現的查詢處理速度較快，基于代價估算的優化方法能進一步有效地提高XML查詢處理性能。

關鍵詞：可擴展標記語言（XML）；結構連接；MapReduce

1　引言

可擴展標記語言（extensible markup language，XML）已經成為Web上數據表達和數據交換的事實標準，各種Web應用促使XML數據量呈海量趨勢增長。作為開源的分布式計算框架，Hadoop[1]及其改進系統以其可靠性、高效性、高容錯性和低成本等特點，成為云計算和大數據處理典型支撐框架，基于Hadoop來研究XML查詢處理十分必要。

本文主要研究如何基于Hadoop MapReduce計算模型對XML數據進行編碼，并利用MapReduce進行查詢處理。XPath是XML查詢處理的核心，其中結構連接又是最核心的操作之一，如何基于MapReduce來高效實現結構連接對處理海量XML數據至關重要。本文基于3種不同的XML編碼，利用MapReduce實現XML海量數據的查詢，并為查詢處理建立了代價模型，通過代價估算方法對查詢計劃進行優化。

本文的主要貢獻如下：

（1）實現了MapReduce框架下3種不同的XML編碼。

（2）實現了MapReduce框架下不同編碼方式的結構連接的XPath查詢處理算法。

（3）實現了MapReduce框架下基于代價估算的查詢優化算法。

（4）實驗結果驗證了基于代價估算方法的有效性。

本文組織結構如下：第2章介紹相關工作；第3和第4章分別介紹MapReduce框架下對XML進行編碼和查詢處理的具體算法；第5章介紹查詢優化算法；第6章進行實驗結果分析；最后總結全文。

2　相關工作

XML結構連接是XML查詢處理的核心操作之一，現有的基于MapReduce的連接算法主要有相似性連接算法、等值連接算法和θ連接算法等。

相似性連接算法大體上可分為水平劃分方法和垂直劃分方法。水平劃分方法首先劃分所有的數據對，之后獨立地針對每個劃分執行連接，最后將所有劃分的執行結果進行合并。為了只對有效對進行劃分，可以采用相應的裁剪技術對候選對進行過濾[2-3]。而垂直劃分方法首先建立反轉表索引，然后在每個索引的劃分中枚舉數值對檢查其相似性[4-5]。當合并結果集時，要消去重復項完成最終的相似性連接。有些論文研究了等值連接[6]的MapReduce算法以及θ連接[7-8]的MapReduce算法，與以上不同的是，本文研究XML結構連接的MapReduce算法。

基于MapReduce的XML數據查詢處理典型系統主要有ChuQL[9]和Xadoop。其中ChuQL主要是通過對XQuery語法進行擴展來實現在Hadoop上處理XML數據，對于XML數據處理則沒有經過任何索引，每次使用擴展的XQuery語句進行查詢都要處理整個文檔來獲得結果。Xadoop將XQuery作為操作Hadoop的一種語言來處理半結構化數據，主要研究XQuery代碼的自動并行化，以及不同任務之間的數據傳輸和索引管理，僅支持以行為單位的分塊方法，且執行效率較低。相較于ChuQL，只要編碼一次，便可以利用編碼文件進行多次查詢，而不用每次查詢都處理整個XML文檔，相對于Xadoop而言，處理XML文檔也不需要一定以行為單位，可以跨行進行數據讀取。

文獻[10]也提出了一種基于MapRedcue的XML結構連接算法，它使用的是前綴編碼格式的數據進行結構連接。Map階段根據分區算法對數據進行隨機分區，一個數據將產生多個副本分配到不同區，副本數由參數m和n決定，m是人為定義的（當m為1 時Reduce只有1個區），n是XPath語句出現的標簽名數目，每個數據都會產生m的n次冪個副本；Reduce階段讀取所有數據后排序再進行結構連接。此算法存在著Map階段輸出冗余度過大，Reduce階段內存消耗過大，容易造成內存溢出的缺點。而本文算法中分區根據不同編碼的特點進行算法設計，Map階段輸出的冗余度遠小于該算法，Shuffle階段又對數據進行了二次排序，在Reduce階段數據已經是有序的，不需要全部讀取后再排序，降低了Reduce階段內存溢出的風險。

基于MapReduce的查詢優化目前主要的研究都是針對SQL語句的查詢優化。SQL語句中多表連接操作通常被分解成多個作業，每個作業執行兩個表的連接操作。而優化的方向主要有兩種：一種是多個SQL語句并行執行時共享連接結果來加速處理[11]；另一種是針對一條語句通過代價估算來確定代價最低的多表連接次序[12]。本文提出的優化算法也是在代價估算的基礎上針對一條XPath語句進行連接次序的優化，但是SQL確定的是作業的連接次序，本文確定的是兩個節點集是做Map端連接還是Reduce端連接，對于查詢計劃的生成都采用了啟發式方法。

3 基于MapReduce的XML編碼算法

為了對XML數據進行索引和有效查詢，可以對XML樹進行編碼，本研究中一共實現了3種不同編碼方案：區間編碼[13]、前綴編碼[13]和層次編碼[14]。圖1、圖2、圖3為3種編碼示例。

Fig.1　Interval encoding圖1區間編碼

Fig.2　Prefix encoding圖2前綴編碼

Fig.3　Hierarchy encoding圖3層次編碼

使用MapReduce進行XML編碼首要解決問題是對XML進行讀取時文件劃分成多個分片，會造成分片的開頭或結尾出現標簽不全的問題。如“”標簽被分為“”被分到了分片2。解決策略是：每次讀取一個字節，讀到“<”符號就會一直往下讀到下一個“<”符號為止，即使超出了分片的范圍。

區間編碼算法和前綴編碼算法都是在Map階段對節點進行不完整的編碼并輸出，每處理完一個分片將分片的偏移信息記錄下來，保存到HDFS上。Reduce階段讀取所有分片信息建立偏移表，對編碼進行矯正并輸出。具體實現可以參照文獻[13]，本文研究借鑒了其實現思想，做的改進主要是在Map輸出key值時，還額外輸出了節點編碼用于二次排序，使得最后Reduce的輸出是有序的。

要對一個節點進行層次編碼，需要獲取到它的父節點的層次編碼和它的兄弟節點信息。層次編碼實現利用了前綴編碼的結果，先將深度相同的前綴編碼放在一個文件中，文件中節點按在XML文件中的順序排好序。

層次編碼對節點按深度從小到大進行編碼，每一層使用一個作業完成。各層的編碼算法主要思路如下：

當深度為1和2時，節點N(i,level)的編碼Hid按照層次編碼規則賦值。

當深度大于2時，將啟動MapReduce作業，使用算法1、算法2進行編碼。

編碼階段將根據標簽名把編碼后的節點信息按從小到大的順序存儲到HDFS上不同的文件中。

算法1 Map Encoding

輸入：未編碼數據集ENR，上一層已編碼數據集LR。

輸出：不完整編碼的數據集。

/*EN屬性分別為節點的前綴編碼、標簽名*/

1.For（EN in ENR）do：

/*通過節點的前綴編碼可以獲知其父親編碼*/

2.parentEN←getParent（EN）；

/*獲取父親節點的層次編碼*/

3.parentHid←getHid（parentEN，LR）；

4.newEN←（，EN）；

5.output（newEN）；

6.Endfor；

算法2 Reduce Encoding

輸入：父節點相同的一組數據集ENR。

輸出：完整編碼的數據集。

1.初始化Set；

/*EN屬性分別為父節點層次編碼、節點本身的前綴編碼、標簽名*/

2.For（EN in ENR）do：

3.add NAME（EN）into Set；

/*將EN名字在Set中的位置按規則轉為二進制*/

4.S←Transform（EN，Set）；

/*S加上父節點的層次編碼形成子節點層次編碼*/

5.Hid←S+parentHid（EN）；

6.output（EN，Hid）；

7.Endfor

圖4、圖5為層次編碼過程示例。

4 基于MapReduce的XML查詢算法

4.1編碼大小比較規則

定義1“Ni

Fig.4　Map process of hierarchy encoding圖4 層次編碼Map過程示例

Fig.5　Reduce process of hierarchy encoding圖5　層次編碼Reduce過程示例

區間編碼的大小按start的值進行判斷，如果Ni

前綴編碼的大小判斷規則如下，示例1.1<1.1.1< 1.1.2<1.2。

設Ni的前綴編碼為A1.A2.….Ai，設Nj的前綴編碼為B1.B2.….Bj，如果Ni

（1）i

（2）?m

層次編碼的大小判斷規則如下，示例0<0010< 0110<10110。

設Ni的層次編碼為AiAi-1…A1，設Nj的前綴編碼為BjBj-1…B1，如果Ni

（1）i

（2）?m≤min(i,j),Am

4.2查詢算法總體思想

本文查詢算法主要包括Map端連接和Reduce端連接兩部分。

在Map階段，查詢算法采取的策略是首先對讀取的節點進行謂詞過濾。根據查詢計劃樹的不同有兩種不同操作：第一種是進行兩兩元素之間的連接操作，對連接產生的中間結果進行區域劃分；第二種是直接對讀取的節點進行區域劃分，再利用shuffle過程按key排序的特性對節點信息進行排序。在Reduce階段，對已經排好序的中間結果進行連接。各階段詳細討論將在后續幾節介紹。圖6為總體查詢處理過程。

Fig.6　Query process圖6查詢過程

4.3Map端連接

當查詢語句存在謂詞時，對于謂詞過濾都在Map階段進行處理，讀取到一個節點后，如果需要進行謂詞連接，則進行相應的條件過濾和連接判定，連接判定過程參考Map端連接算法。Map端進行過濾可以減少Map的輸出節點數目，減少shuffle和reduce開銷。Map結構連接過程如圖7所示。

Map階段進行組合的連接操作，每次讀到一個節點的編碼信息，就找出與其進行連接的祖先節點，進行連接判定，具體過程參算法3。

算法3 Map Join

輸入：節點數據集ENR，其祖先節點數據集AR。

輸出：節點對數據集。

1.parentEN←the first item inAR；

2.初始化List；

/*EN為一個節點的編碼信息（3種編碼中任意一種）*/

3.For（EN in ENR）do：

/*EN先與List里的節點做連接判定，并刪除不滿足連接條件的節點*/

4.JoinList（EN，List）；

/*parentEN

5.While parentEN

6.If join（parentEN，EN）=true then

/*滿足連接條件，分區后輸出到reduce*/

7.partitionAndOutput（parentEN,EN）；

8.Add parentEN to List；

9.Endif

10.parentEN←the next item inAR；

11.Endwhile

12.Endfor

Map階段在輸出結果時需要根據節點的信息或節點對中子節點的信息進行分區再輸出，各個編碼的分區規則如下。

（1）區間編碼分區規則

節點N的區間編碼為，分區長度為B，則[0,B-1]為區域0，[B,2B-1]為區域1，以此類推。

Fig.7　Map join process圖7Map結構連接過程

令 first=start/B，last=end/B，則節點N將輸出到區域first至區域last。例如N編碼為<20,30,3>, B=5，分配到區域4、5、6。

（2）前綴編碼分區規則

節點N的前綴編碼為A1.A2.….Ai，分區長度為B，那么當i≥B時，N將分配到區域A1.A2.….AB，當i

（3）層次編碼分區規則

節點N的層次編碼為 AiAi-1…A1，分區長度為B，那么當i≥B時，N將分配到AB…A2A1，當i

通過分區，數據會產生一定的冗余，例如同個節點編碼輸出到了不同的區域里，但是保證了Reduce端連接時每一組包含連接所需要的所有節點信息。

4.4Reduce端連接

Reduce階段進行連接操作。對于已經完全排好序的中間結果集來說連接是較直觀的，每讀到一個節點數據，找出對應的祖先節點的棧；跟棧中節點進行連接判定，判定成功的話，如果該數據不是最后要輸出的數據，則壓到對應的棧里；如果是最后要輸出的數據，則先判斷分區id是否為節點Map輸出進行分區時id最大的分區，是的話才輸出，不是則拋棄，這是為了避免不同分區輸出相同的結果。

4.5默認查詢計劃

未優化的查詢算法默認采用的處理策略是對表達式以兩個標簽為一個組合進行分解，分解后的組合將在Map階段進行連接操作生成中間結果。因為組合中祖先節點的文件大小通常小于子孫節點的文件大小，所以祖先節點的文件不作為輸入文件，而將子孫節點的存儲文件作為MapReduce任務的輸入文件，如圖8所示。

Fig.8　Decomposition of XPath圖8XPath語句分解示例

從圖8可以看到，/site/regions//item/description/ parlist/listitem//parlist/listitem語句中有兩個組合是相同的，即{parlist/listitem}。當讀到{parlist/listitem}的結果數據時，要與{parlist/listitem}的結果進行Ancestor-Descendant關系判斷呢還是跟{item/description}的結果進行Parent-Child關系判定呢？由于不能馬上判斷出讀到的數據是屬于哪個{parlist/listitem}組合，采取的策略是按表達式從后向前進行連接判定，先判斷{parlist/listitem}與{parlist/listitem}兩個是否是Ancestor-Descendant關系，不是的話再判斷{parlist/listitem} 與{item/description}的Parent-Child關系。

4.6數據重用

對一條查詢語句構造其查詢計劃樹，可能出現Map階段輸出結果可以重用或者輸入文件可以重用的情況，這時可以利用重用數據以減少開銷。

例如A/B/C/B，默認查詢計劃樹中標簽B在Map中需要做A/B和C/B連接判斷，都需要標簽B的節點編碼文件要作為輸入文件，此時可以輸入一遍標簽B的節點就行。又如A/B/A/B，查詢計劃中Map端需要做A/B的連接判定兩次，也可以合并為1次。

5　基于代價評估的查詢優化

如圖6及圖8所示，對于一個查詢語句，不同的查詢計劃樹會使得模塊1和2的執行代價不同。為了對代價進行評估，需要對結構連接操作結果集的數目進行估算，對MapReduce作業建立代價模型。

5.1結構連接操作結果集的估算

文獻[14]提出了一個在單節點環境下根據層次編碼統計信息對XPath查詢的CPU執行代價估算的方法。本文結構連接操作結果集的估算使用文獻[14]中的方法，來對兩個節點集連接結果進行估算。

對于父子連接操作的結果集估算，如A/B，A表示一個標簽名，A.result表示名字相同的節點層次編碼的集合。為了對A/B的結果集R進行估算，需要對B集合的每一項b，遍歷A集合，查找A集合中是否存在節點a與節點b滿足父子關系，如果是則停止查找，并將b添加到R中。最后將R中的每個節點編碼信息中的nodeCount進行相加，得到的和就是A/B的結果集數目的預估值。

對于祖孫連接操作的結果集估算，如A//B，需要對B集合的每一項b，遍歷A集合，查找A集合中是否存在節點a與節點b滿足祖孫關系，如果是則將b添加到R中，并繼續查找直到遍歷完。最后將R中的每個節點編碼信息中的nodeCount進行相加，得到的和就是A//B的結果集數目的預估值。

對于數值型謂詞結果集的估算，如B>7，根據謂詞對應的節點層次編碼、比較操作符以及參與比較的數值，使用直方圖進行估算，詳細細節可看文獻[14]。

5.2MapReduce查詢代價模型

本文采用代價模型評估不同查詢計劃樹在Map-Reduce框架下執行所消耗的代價。進行代價估算需考慮3個因素：一是I/O開銷；二是CPU的開銷；三是網絡傳輸的開銷。表1是代價模型所使用的參數。

Table 1　Model parameters表1模型參數

查詢處理中Map過程有兩種不同操作，現在對兩種操作建立代價估算模型。首先定義Path(i,j)為路徑表達式，當i=j時，代表Path(i,j)為一個節點名稱，當i

Path(i,i)對應的節點數據集為Ii。按照式（1）～（3）可計算從HDFS上讀取輸入文件的代價RC（read cost），數據集進行分區輸出的CPU代價PC（partition cost），Map數據輸出到本地文件的代價WC（write cost），三者構成不進行連接操作的Map階段代價。

Path(i,i)的Map階段的代價計算公式如下所示：

按照式（5）～（7）可計算在HDFS讀取祖先節點數據集的代價RAC（read ancestor?s records cost），對連接結果數據集進行分區輸出的CPU代價PPC（partition pair cost），結果數據集輸出節點到本地磁盤的代價WPC （write pair cost）。

式（7）與式（3）的主要區別是代價乘以2，這是因為結果集中的每個數據都是由兩個節點編碼信息組成，所以大小也要多了一倍。

Path(i-1,i)的Map階段代價計算公式如下所示：

Shuffle和Reduce階段的代價估算主要考慮影響因素是Map輸出的節點數據集（在本文算法中，Map的輸出數據集總和與Reduce的輸入數據集是相同的），假設RI為Reduce的輸入數據集，則Reduce階段的代價計算公式如下所示：

CR=Cshuffle(RI)+Crjoin(RI)+NUM(RO)×Cwh（9）

其中，Cshuffle(RI)代表從Map獲取輸出文件到Reduce輸入的整個shuffle過程的全部代價；Crjoin(RI)代表在Reduce端對集合RI進行連接的CPU代價；NUM(RO)×Cwh代表的是Reduce的輸出代價。

Job表示一個MapReduce作業，一個查詢的Map-Reduce作業的全部代價計算公式如下所示：

其中，∑CMi是查詢計劃樹中不做Map端連接的數據集Ii的Map階段代價總和；∑CM(j-1,j)是查詢計劃樹中進行Map端連接的數據集Ij的Map階段代價。因為MapReduce作業的Map任務數與輸入文件的大小相關，并行的Map任務數不同也會導致作業的效率不同，所以進行代價評估時也需要考慮并行Map任務數的影響。而Reduce的組數一直大于集群中并行的Reduce任務數，因此這里不計入Reduce任務數的影響。假設查詢計劃的Map任務數為N，集群最大的并行Map任務數為M，則作業同時并行的Map任務數K=min(N,M)。

5.3啟發式優化查詢算法

定義2J為一個狀態節點，保存了3個變量，第一個為路徑表達式Path，第二個為Path的執行代價cost，第三個是Path中最后一個參與連接操作結構的類型type，type有兩種類型EN和LP。EN表示元素節點名，LP表示一個二元連接結構的長路徑。

定義3 Path＋EN表示將連接節點EN添加到路徑表達式Path中，EN的數據集不進行Map端連接操作。

定義4 Path-EN表示將路徑表達式Path中的最后一個連接節點EN除去。

定義5 EN1*EN2表示一個二元連接結構，EN1與EN2兩個節點數據集在Map端進行連接操作。

本文使用最佳優先搜索算法[15]查找代價最小的查詢計劃。對一個查詢語句，從左往右逐個增加連接結構生成查詢計劃樹，具體過程如下:

初始化優先隊列Queue，用于保存狀態節點并每次返回執行代價最低的狀態節點；minCost用于查詢語句的最低執行代價，初始化為雙浮點最大值；minJ用于存儲執行代價最低的完整查詢路徑。

初始化第一個狀態節點J，J.Path=Path(1,1)，根據表達式計算出各個變量的數據后存儲，添加到Queue中。

當Queue不為空時，返回隊列中代價最低的狀態節點J，根據J的路徑表達式結構添加新的連接節點EN1，添加規則如下所示。

當J.type=EN時，可以生成兩個新的狀態節點進行添加，假設J.Path的最后一個連接節點為EN′，則：

新的狀態節點：

J1.Path=J.Path+EN1

J2.Path=J.Path-EN′+(EN′*EN1)

當J.type=LP時，可以生成一個新的狀態節點：

J1.Path=J.Path+EN1

新的狀態節點根據路徑表達式更新作業的執行代價，當cost>minCost且type=LP時，該狀態節點則放棄掉。當路徑表達式已經是完整的查詢語句時，如果cost

算法4 Optimization

輸入：一個查詢語句XPath。

輸出：一個執行計劃樹。

/*對語句進行解析*/

1.Parse（XPath）；

2.初始化優先隊列Queue，代價最小作業minJob；

3.minJob.cost←MAX；

4.J.Path←Xpath(1，1)；

5.Push J into Queue；

/*優先隊列，每次返回代價最小節點*/

6.While Queue is not empty do

7.J←pop from Queue；

8.If(minJob.cost>J.cost)

9.break；

/*對路徑根據類型進行擴展，不是完整路徑則壓入Queue中，是的話根據代價更新minJob*/

10.ExpandAndUpdate(J，minJob，Queue)；

11.Endwhile；

12.return minJob.path；

對于查詢語句/A/B//C/D的優化過程如圖9所示。圖中用|號表示分割，分割點所在的連接操作在Reduce端完成，其余連接操作都在Map端完成。

Fig.9　Query optimization process圖9 查詢優化過程

6　實驗測試

6.1實驗環境

實驗測試硬件環境是4臺IBM刀片服務器。安裝Openstack云計算平臺，創建了6臺CPU為2個虛擬內核，內存為4 GB的主機，其中1臺為namenode，5臺為datanode。

實驗數據采用XMark[16]標準的數據集。實驗測試采用的XML數據集如表2所示，所選取的主要查詢語句如表3所示。實驗測試有3部分：（1）3種編碼方式下查詢速度的實驗對比。（2）區間編碼方式下在不同數據集下的查詢速度對比。（3）計劃樹優化前后的查詢速度對比。實驗中將在分布式環境下，對不同查詢語句在不同數據集下進行多次查詢（前兩部分實驗采用的查詢計劃樹是未優化的查詢計劃樹），記錄查詢時間并取得平均值。第三部分實驗則選取查詢性能最優的區間編碼方式進行優化方法的查詢性能測試。

Table 2　Dataset表2數據集

6.2實驗結果與分析

（1）3種編碼方式查詢速度的實驗對比

圖10～圖14為XP1到XP5在不同數據集下的查詢時間對比。從測試結果中可以看出，區間編碼的查詢性能在不同數據集和查詢語句下都是3種編碼中最優的，且隨著數據量的增大，查詢性能的優越性越來越明顯。前綴編碼和層次編碼兩者的查詢性能則比較接近，總體上層次編碼查詢速度更快。查詢性能上的差異主要來自分區和排序的執行代價不同，區間編碼的分區和排序是直接對長整數類型數據進行計算，而前綴編碼和層次編碼是先對字符串類型數據進行轉化后再計算，前者代價相對小于后者。

Fig.10　Query time of XP1圖10XP1查詢時間

Fig.11　Query time of XP2圖11XP2查詢時間

Fig.12　Query time of XP3圖12XP3查詢時間

Fig.13　Query time of XP4圖13XP4查詢時間

Fig.14　Query time of XP5圖14XP5查詢時間

（2）查詢速度隨數據集變化的情況

為了更準確地觀察，這里采用的性能指標為數據集節點數與查詢時間之比。經過分析，XP1到XP5語句中查詢性能變化情況主要有兩種：第一種是如圖15中XP1的查詢性能變化情況，主要有XP1、XP2、XP3、XP5語句，隨著數據集的變大，查詢處理性能具有近線性特點。

Fig.15　XP1?s query speed changing with record set圖15　XP1查詢速度隨記錄集變化圖

第二種是如圖16中XP4的變化情況，查詢性能不斷提高，直到R5時性能下降。主要的原因是XP4的查詢數據處理量比其他幾個語句大，在R5數據集下超過了集群的同時并行能力最大數，導致需要多個周期的并行而使得性能下降。

Fig.16　XP4?s query speed changing with record set圖16XP4查詢速度隨記錄集變化

（3）不同計劃樹的查詢速度對比

本實驗中展示了只做Reduce連接的查詢計劃的執行時間。圖17是XP1到XP5語句在R2（在其他數據集上也有相似結論）下的3種查詢計劃的執行情況。其中，RJ（reduce join）表示只做Reduce連接的查詢計劃，DJ（default join）表示默認的查詢計劃，OJ （optimized join）表示優化后的查詢計劃。

Fig.17　Results of R2 comparison before and after optimization圖17　R2下優化前后結果對比

從圖17可以看出，RJ在XP1、XP2、XP4中查詢性能略高于DJ，其他幾條語句則DJ的查詢性能更好。而OJ則在不同的查詢語句中都是查詢性能最好的，在本研究開展過的實驗中，OJ比DJ的查詢效率提高最高可達20%。

7　結束語

本文研究和實現了3種不同XML數據編碼算法，以此為基礎實現了基于MapReduce的XML結構連接處理，最后還實現了基于MapReduce作業的XML查詢處理代價模型和查詢優化算法。實驗結果表明，基于區間編碼方式的XML查詢處理性能在3者中最優，提出的代價估算模型和優化方法能有效地提高查詢處理性能。下一步將研究如何動態調整分區長度以進一步提高XML查詢處理性能。

References:

[1]Dai Wei,Bassiouni.M An improved task assignment scheme for Hadoop running in the clouds[J].Journal of Cloud Computing,2013,2(1):1-16.

[2]Kim Y,Shim K.Parallel top-k similarity join algorithms using MapReduce[C]//Proceedings of the 2012 IEEE 28th International Conference on Data Engineering,Washington, USA,Apr 1-5,2012.Piscataway,USA:IEEE,2012:510-521.

[3]Yu Jiang,Deng Dong,Wang Jiannan,et al.Efficient parallel partition-based algorithms for similarity search and join with edit distance constraints[C]//Proceedings of the Joint EDBT/ICDT 2013 Workshops,Genoa,Italy,Mar 22,2013. New York,USA:ACM,2013:341-348.

[4]Metwally A,Faloutsos C.V-SMART-Join:a scalable Map-Reduce framework for all-pair similarity joins of multisets and vectors[J].Proceedings of the VLDB Endowment,2012, 5(8):704-715.

[5]Vernica R,Carey M J,Li Chen.Efficient parallel set-similarity joins using MapReduce[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis,USA,Jun 6-10,2010.New York,USA:ACM, 2010:495-506.

[6]Zhang Xiaofei,Chen Lei,Wang Min.Efficient multi-way theta-join processing using MapReduce[J].Proceedings of the VLDB Endowment,2012,5(11):1184-1195.

[7]Okcan A,Riedewald M.Processing theta-joins using Map-Reduce[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,Athens, Greece,Jun 12-16,2011.New York,USA:ACM,2011:949-960.

[8]Blanas S,Patel J M,Ercegovac V.A comparison of join algorithms for log processing in MapReduce[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,Indianapolis,USA,Jun 6-10,2010. New York,USA:ACM,2010:975-986.

[9]Khatchadourian S,Consens M,Siméon J.ChuQL:processing XML with XQuery using Hadoop[C]//Proceedings of the 2011 Conference of the Center for Advanced Studies on Collaborative Research.Riverton,USA:IBM Corp,2011:74-83.

[10]Wu Huayu.Parallelizing structural joins to process queries over big XML data using MapReduce[C]//LNCS 8645:Proceedings of the 25th International Conference on Database and Expert Systems Applications,Munich,Germany,Sep 1-4,2014.Berlin:Springer International Publishing,2014: 183-190.

[11]Wang Guoping,Chan C Y.Multi-query optimization in Map-Reduce framework[J].Proceedings of the VLDB Endowment,2013,7(3):145-156.

[12]Wu Sai,Li Feng,Mehrotra S,et al.Query optimization for massively parallel data processing[C]//Proceedings of the 2nd ACM Symposium on Cloud Computing,Cascais,Portugal,Oct 26-28,2011.New York,USA:ACM,2011:12.

[13]Choi H,Lee K H,Lee Y J.Parallel labeling of massive XML data with MapReduce[J].The Journal of Supercomputing,2014,67(2):408-437.

[14]Li Dong,Chen Wenhao,Liang Xiaochong,et al.Cost-based query optimization for XPath[J].Applied Mathematics& Information Sciences,2014,8(4):1935-1948.

[15]Dechter R,Pearl J.Generalized best-first search strategies and the optimality of A?[J].Journal of the ACM,1985,32 (3):505-536.

[16]Schmidt A,Waas F,Kersten M,et al.XMark:a benchmark for XML data management[C]//Proceedings of the 28th International Conference on Very Large Data Bases,Hong Kong,China,Aug 20-23,2002:974-985.

LI Dong was born in 1970.He received the Ph.D.degree in computer science from Huazhong University of Science and Technology in 2001.Now he is a professor at South China University of Technology,and the member of CCF.His research interests include XML databases,mobile database and business process management,etc.

李東（1970—），男，湖南邵東人，2001年于華中科技大學獲得博士學位，現為華南理工大學教授，CCF會員，主要研究領域為XML數據庫，移動數據庫，商業流程管理等。

DENG Zehang was born in 1991.He is an M.S.candidate at South China University of Technology.His research interest is distributed computation.

鄧澤航（1991—），男，廣東汕頭人，華南理工大學碩士研究生，主要研究領域為分布式計算。

LI Zuli was born in 1992.He is an M.S.candidate at South China University of Technology.His research interest is distributed computation.

李祖立（1992—），男，廣東惠州人，華南理工大學碩士研究生，主要研究領域為分布式計算。

*The Integration Project of Industry,Education and Research of Guangdong Province under Grant No.2013C001(廣東省部產學研結合項目);the Project of Technology Bureau in Duanzhou District of Zhaoqing under Grant No.2014-5(肇慶市端州區科技局項目). Received 2015-07,Accepted 2015-09.

CNKI網絡優先出版:2015-10-13,http://www.cnki.net/kcms/detail/11.5602.TP.20151013.1624.004.html

文獻標志碼：A

中圖分類號：TP391

doi:10.3778/j.issn.1673-9418.1509011

Structural Join Processing for XMLBased on MapReduce?

LI Dong+,DENG Zehang,LI Zuli
School of Software Engineering,South China University of Technology,Guangzhou 510006,China +Corresponding author:E-mail:cslidong@scut.edu.cn

Abstract:Extensible markup language(XML)has become the defacto standard of data representation and data exchange on Web.Hadoop is a typical framework for cloud computing and big data processing,thus making a study on XML query processing based on MapReduce is necessary.In order to implement the XML query processing based on MapReduce,this paper proposes three different encoding algorithms such as interval encoding,prefix encoding and hierarchy encoding,and designs the corresponding structural join algorithms based on MapReduce to support XML queries.This paper sets up a cost model for the query processing,and proposes a cost-based approach to determine the optimal execution tree.In the end,the XML query processing experiments are made,the experimental results show that relative to other two XML encoding schemes,the query processing based on interval encoding has a higher query performance.And the cost-based optimal approach is effective and further improves the performance of XML query processing.

Key words:extensible markup language(XML);structural join;MapReduce