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

基于MapReduce的XML結(jié)構(gòu)連接處理*

李東+，鄧澤航，李祖立
華南理工大學(xué) 軟件學(xué)院，廣州 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.

摘要：可擴(kuò)展標(biāo)記語(yǔ)言（extensible markup language，XML）已經(jīng)成為Web上數(shù)據(jù)表達(dá)和數(shù)據(jù)交換的事實(shí)標(biāo)準(zhǔn)，Hadoop已成為云計(jì)算和大數(shù)據(jù)處理典型支撐框架之一，基于Hadoop MapReduce來(lái)實(shí)現(xiàn)XML查詢(xún)處理十分必要。為了實(shí)現(xiàn)基于MapReduce的XML查詢(xún)處理，首先實(shí)現(xiàn)了區(qū)間編碼、前綴編碼和層次編碼等3種不同的XML數(shù)據(jù)編碼方式，以此為基礎(chǔ)來(lái)研究和實(shí)現(xiàn)基于MapReduce的XML結(jié)構(gòu)連接處理。為查詢(xún)處理建立了代價(jià)模型，通過(guò)代價(jià)估算獲得優(yōu)化的查詢(xún)計(jì)劃樹(shù)。最后開(kāi)展了XML查詢(xún)處理實(shí)驗(yàn)評(píng)估，結(jié)果表明相對(duì)其他兩種XML編碼方式，區(qū)間編碼方式下實(shí)現(xiàn)的查詢(xún)處理速度較快，基于代價(jià)估算的優(yōu)化方法能進(jìn)一步有效地提高XML查詢(xún)處理性能。

關(guān)鍵詞：可擴(kuò)展標(biāo)記語(yǔ)言（XML）；結(jié)構(gòu)連接；MapReduce

1　引言

可擴(kuò)展標(biāo)記語(yǔ)言（extensible markup language，XML）已經(jīng)成為Web上數(shù)據(jù)表達(dá)和數(shù)據(jù)交換的事實(shí)標(biāo)準(zhǔn)，各種Web應(yīng)用促使XML數(shù)據(jù)量呈海量趨勢(shì)增長(zhǎng)。作為開(kāi)源的分布式計(jì)算框架，Hadoop[1]及其改進(jìn)系統(tǒng)以其可靠性、高效性、高容錯(cuò)性和低成本等特點(diǎn)，成為云計(jì)算和大數(shù)據(jù)處理典型支撐框架，基于Hadoop來(lái)研究XML查詢(xún)處理十分必要。

本文主要研究如何基于Hadoop MapReduce計(jì)算模型對(duì)XML數(shù)據(jù)進(jìn)行編碼，并利用MapReduce進(jìn)行查詢(xún)處理。XPath是XML查詢(xún)處理的核心，其中結(jié)構(gòu)連接又是最核心的操作之一，如何基于MapReduce來(lái)高效實(shí)現(xiàn)結(jié)構(gòu)連接對(duì)處理海量XML數(shù)據(jù)至關(guān)重要。本文基于3種不同的XML編碼，利用MapReduce實(shí)現(xiàn)XML海量數(shù)據(jù)的查詢(xún)，并為查詢(xún)處理建立了代價(jià)模型，通過(guò)代價(jià)估算方法對(duì)查詢(xún)計(jì)劃進(jìn)行優(yōu)化。

本文的主要貢獻(xiàn)如下：

（1）實(shí)現(xiàn)了MapReduce框架下3種不同的XML編碼。

（2）實(shí)現(xiàn)了MapReduce框架下不同編碼方式的結(jié)構(gòu)連接的XPath查詢(xún)處理算法。

（3）實(shí)現(xiàn)了MapReduce框架下基于代價(jià)估算的查詢(xún)優(yōu)化算法。

（4）實(shí)驗(yàn)結(jié)果驗(yàn)證了基于代價(jià)估算方法的有效性。

本文組織結(jié)構(gòu)如下：第2章介紹相關(guān)工作；第3和第4章分別介紹MapReduce框架下對(duì)XML進(jìn)行編碼和查詢(xún)處理的具體算法；第5章介紹查詢(xún)優(yōu)化算法；第6章進(jìn)行實(shí)驗(yàn)結(jié)果分析；最后總結(jié)全文。

2　相關(guān)工作

XML結(jié)構(gòu)連接是XML查詢(xún)處理的核心操作之一，現(xiàn)有的基于MapReduce的連接算法主要有相似性連接算法、等值連接算法和θ連接算法等。

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

基于MapReduce的XML數(shù)據(jù)查詢(xún)處理典型系統(tǒng)主要有ChuQL[9]和Xadoop。其中ChuQL主要是通過(guò)對(duì)XQuery語(yǔ)法進(jìn)行擴(kuò)展來(lái)實(shí)現(xiàn)在Hadoop上處理XML數(shù)據(jù)，對(duì)于XML數(shù)據(jù)處理則沒(méi)有經(jīng)過(guò)任何索引，每次使用擴(kuò)展的XQuery語(yǔ)句進(jìn)行查詢(xún)都要處理整個(gè)文檔來(lái)獲得結(jié)果。Xadoop將XQuery作為操作Hadoop的一種語(yǔ)言來(lái)處理半結(jié)構(gòu)化數(shù)據(jù)，主要研究XQuery代碼的自動(dòng)并行化，以及不同任務(wù)之間的數(shù)據(jù)傳輸和索引管理，僅支持以行為單位的分塊方法，且執(zhí)行效率較低。相較于ChuQL，只要編碼一次，便可以利用編碼文件進(jìn)行多次查詢(xún)，而不用每次查詢(xún)都處理整個(gè)XML文檔，相對(duì)于Xadoop而言，處理XML文檔也不需要一定以行為單位，可以跨行進(jìn)行數(shù)據(jù)讀取。

文獻(xiàn)[10]也提出了一種基于MapRedcue的XML結(jié)構(gòu)連接算法，它使用的是前綴編碼格式的數(shù)據(jù)進(jìn)行結(jié)構(gòu)連接。Map階段根據(jù)分區(qū)算法對(duì)數(shù)據(jù)進(jìn)行隨機(jī)分區(qū)，一個(gè)數(shù)據(jù)將產(chǎn)生多個(gè)副本分配到不同區(qū)，副本數(shù)由參數(shù)m和n決定，m是人為定義的（當(dāng)m為1 時(shí)Reduce只有1個(gè)區(qū)），n是XPath語(yǔ)句出現(xiàn)的標(biāo)簽名數(shù)目，每個(gè)數(shù)據(jù)都會(huì)產(chǎn)生m的n次冪個(gè)副本；Reduce階段讀取所有數(shù)據(jù)后排序再進(jìn)行結(jié)構(gòu)連接。此算法存在著Map階段輸出冗余度過(guò)大，Reduce階段內(nèi)存消耗過(guò)大，容易造成內(nèi)存溢出的缺點(diǎn)。而本文算法中分區(qū)根據(jù)不同編碼的特點(diǎn)進(jìn)行算法設(shè)計(jì)，Map階段輸出的冗余度遠(yuǎn)小于該算法，Shuffle階段又對(duì)數(shù)據(jù)進(jìn)行了二次排序，在Reduce階段數(shù)據(jù)已經(jīng)是有序的，不需要全部讀取后再排序，降低了Reduce階段內(nèi)存溢出的風(fēng)險(xiǎn)。

基于MapReduce的查詢(xún)優(yōu)化目前主要的研究都是針對(duì)SQL語(yǔ)句的查詢(xún)優(yōu)化。SQL語(yǔ)句中多表連接操作通常被分解成多個(gè)作業(yè)，每個(gè)作業(yè)執(zhí)行兩個(gè)表的連接操作。而優(yōu)化的方向主要有兩種：一種是多個(gè)SQL語(yǔ)句并行執(zhí)行時(shí)共享連接結(jié)果來(lái)加速處理[11]；另一種是針對(duì)一條語(yǔ)句通過(guò)代價(jià)估算來(lái)確定代價(jià)最低的多表連接次序[12]。本文提出的優(yōu)化算法也是在代價(jià)估算的基礎(chǔ)上針對(duì)一條XPath語(yǔ)句進(jìn)行連接次序的優(yōu)化，但是SQL確定的是作業(yè)的連接次序，本文確定的是兩個(gè)節(jié)點(diǎn)集是做Map端連接還是Reduce端連接，對(duì)于查詢(xún)計(jì)劃的生成都采用了啟發(fā)式方法。

3 基于MapReduce的XML編碼算法

為了對(duì)XML數(shù)據(jù)進(jìn)行索引和有效查詢(xún)，可以對(duì)XML樹(shù)進(jìn)行編碼，本研究中一共實(shí)現(xiàn)了3種不同編碼方案：區(qū)間編碼[13]、前綴編碼[13]和層次編碼[14]。圖1、圖2、圖3為3種編碼示例。

Fig.1　Interval encoding圖1區(qū)間編碼

Fig.2　Prefix encoding圖2前綴編碼

Fig.3　Hierarchy encoding圖3層次編碼

使用MapReduce進(jìn)行XML編碼首要解決問(wèn)題是對(duì)XML進(jìn)行讀取時(shí)文件劃分成多個(gè)分片，會(huì)造成分片的開(kāi)頭或結(jié)尾出現(xiàn)標(biāo)簽不全的問(wèn)題。如“”標(biāo)簽被分為“”被分到了分片2。解決策略是：每次讀取一個(gè)字節(jié)，讀到“<”符號(hào)就會(huì)一直往下讀到下一個(gè)“<”符號(hào)為止，即使超出了分片的范圍。

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

要對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行層次編碼，需要獲取到它的父節(jié)點(diǎn)的層次編碼和它的兄弟節(jié)點(diǎn)信息。層次編碼實(shí)現(xiàn)利用了前綴編碼的結(jié)果，先將深度相同的前綴編碼放在一個(gè)文件中，文件中節(jié)點(diǎn)按在XML文件中的順序排好序。

層次編碼對(duì)節(jié)點(diǎn)按深度從小到大進(jìn)行編碼，每一層使用一個(gè)作業(yè)完成。各層的編碼算法主要思路如下：

當(dāng)深度為1和2時(shí)，節(jié)點(diǎn)N(i,level)的編碼Hid按照層次編碼規(guī)則賦值。

當(dāng)深度大于2時(shí)，將啟動(dòng)MapReduce作業(yè)，使用算法1、算法2進(jìn)行編碼。

編碼階段將根據(jù)標(biāo)簽名把編碼后的節(jié)點(diǎn)信息按從小到大的順序存儲(chǔ)到HDFS上不同的文件中。

算法1 Map Encoding

輸入：未編碼數(shù)據(jù)集ENR，上一層已編碼數(shù)據(jù)集LR。

輸出：不完整編碼的數(shù)據(jù)集。

/*EN屬性分別為節(jié)點(diǎn)的前綴編碼、標(biāo)簽名*/

1.For（EN in ENR）do：

/*通過(guò)節(jié)點(diǎn)的前綴編碼可以獲知其父親編碼*/

2.parentEN←getParent（EN）；

/*獲取父親節(jié)點(diǎn)的層次編碼*/

3.parentHid←getHid（parentEN，LR）；

4.newEN←（，EN）；

5.output（newEN）；

6.Endfor；

算法2 Reduce Encoding

輸入：父節(jié)點(diǎn)相同的一組數(shù)據(jù)集ENR。

輸出：完整編碼的數(shù)據(jù)集。

1.初始化Set；

/*EN屬性分別為父節(jié)點(diǎn)層次編碼、節(jié)點(diǎn)本身的前綴編碼、標(biāo)簽名*/

2.For（EN in ENR）do：

3.add NAME（EN）into Set；

/*將EN名字在Set中的位置按規(guī)則轉(zhuǎn)為二進(jìn)制*/

4.S←Transform（EN，Set）；

/*S加上父節(jié)點(diǎn)的層次編碼形成子節(jié)點(diǎn)層次編碼*/

5.Hid←S+parentHid（EN）；

6.output（EN，Hid）；

7.Endfor

圖4、圖5為層次編碼過(guò)程示例。

4 基于MapReduce的XML查詢(xún)算法

4.1編碼大小比較規(guī)則

定義1“Ni

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

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

區(qū)間編碼的大小按start的值進(jìn)行判斷，如果Ni

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

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

（1）i

（2）?m

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

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

（1）i

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

4.2查詢(xún)算法總體思想

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

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

Fig.6　Query process圖6查詢(xún)過(guò)程

4.3Map端連接

當(dāng)查詢(xún)語(yǔ)句存在謂詞時(shí)，對(duì)于謂詞過(guò)濾都在Map階段進(jìn)行處理，讀取到一個(gè)節(jié)點(diǎn)后，如果需要進(jìn)行謂詞連接，則進(jìn)行相應(yīng)的條件過(guò)濾和連接判定，連接判定過(guò)程參考Map端連接算法。Map端進(jìn)行過(guò)濾可以減少M(fèi)ap的輸出節(jié)點(diǎn)數(shù)目，減少shuffle和reduce開(kāi)銷(xiāo)。Map結(jié)構(gòu)連接過(guò)程如圖7所示。

Map階段進(jìn)行組合的連接操作，每次讀到一個(gè)節(jié)點(diǎn)的編碼信息，就找出與其進(jìn)行連接的祖先節(jié)點(diǎn)，進(jìn)行連接判定，具體過(guò)程參算法3。

算法3 Map Join

輸入：節(jié)點(diǎn)數(shù)據(jù)集ENR，其祖先節(jié)點(diǎn)數(shù)據(jù)集AR。

輸出：節(jié)點(diǎn)對(duì)數(shù)據(jù)集。

1.parentEN←the first item inAR；

2.初始化List；

/*EN為一個(gè)節(jié)點(diǎn)的編碼信息（3種編碼中任意一種）*/

3.For（EN in ENR）do：

/*EN先與List里的節(jié)點(diǎn)做連接判定，并刪除不滿(mǎn)足連接條件的節(jié)點(diǎn)*/

4.JoinList（EN，List）；

/*parentEN

5.While parentEN

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

/*滿(mǎn)足連接條件，分區(qū)后輸出到reduce*/

7.partitionAndOutput（parentEN,EN）；

8.Add parentEN to List；

9.Endif

10.parentEN←the next item inAR；

11.Endwhile

12.Endfor

Map階段在輸出結(jié)果時(shí)需要根據(jù)節(jié)點(diǎn)的信息或節(jié)點(diǎn)對(duì)中子節(jié)點(diǎn)的信息進(jìn)行分區(qū)再輸出，各個(gè)編碼的分區(qū)規(guī)則如下。

（1）區(qū)間編碼分區(qū)規(guī)則

節(jié)點(diǎn)N的區(qū)間編碼為，分區(qū)長(zhǎng)度為B，則[0,B-1]為區(qū)域0，[B,2B-1]為區(qū)域1，以此類(lèi)推。

Fig.7　Map join process圖7Map結(jié)構(gòu)連接過(guò)程

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

（2）前綴編碼分區(qū)規(guī)則

節(jié)點(diǎn)N的前綴編碼為A1.A2.….Ai，分區(qū)長(zhǎng)度為B，那么當(dāng)i≥B時(shí)，N將分配到區(qū)域A1.A2.….AB，當(dāng)i

（3）層次編碼分區(qū)規(guī)則

節(jié)點(diǎn)N的層次編碼為 AiAi-1…A1，分區(qū)長(zhǎng)度為B，那么當(dāng)i≥B時(shí)，N將分配到AB…A2A1，當(dāng)i

通過(guò)分區(qū)，數(shù)據(jù)會(huì)產(chǎn)生一定的冗余，例如同個(gè)節(jié)點(diǎn)編碼輸出到了不同的區(qū)域里，但是保證了Reduce端連接時(shí)每一組包含連接所需要的所有節(jié)點(diǎn)信息。

4.4Reduce端連接

Reduce階段進(jìn)行連接操作。對(duì)于已經(jīng)完全排好序的中間結(jié)果集來(lái)說(shuō)連接是較直觀的，每讀到一個(gè)節(jié)點(diǎn)數(shù)據(jù)，找出對(duì)應(yīng)的祖先節(jié)點(diǎn)的棧；跟棧中節(jié)點(diǎn)進(jìn)行連接判定，判定成功的話(huà)，如果該數(shù)據(jù)不是最后要輸出的數(shù)據(jù)，則壓到對(duì)應(yīng)的棧里；如果是最后要輸出的數(shù)據(jù)，則先判斷分區(qū)id是否為節(jié)點(diǎn)Map輸出進(jìn)行分區(qū)時(shí)id最大的分區(qū)，是的話(huà)才輸出，不是則拋棄，這是為了避免不同分區(qū)輸出相同的結(jié)果。

4.5默認(rèn)查詢(xún)計(jì)劃

未優(yōu)化的查詢(xún)算法默認(rèn)采用的處理策略是對(duì)表達(dá)式以?xún)蓚€(gè)標(biāo)簽為一個(gè)組合進(jìn)行分解，分解后的組合將在Map階段進(jìn)行連接操作生成中間結(jié)果。因?yàn)榻M合中祖先節(jié)點(diǎn)的文件大小通常小于子孫節(jié)點(diǎn)的文件大小，所以祖先節(jié)點(diǎn)的文件不作為輸入文件，而將子孫節(jié)點(diǎn)的存儲(chǔ)文件作為MapReduce任務(wù)的輸入文件，如圖8所示。

Fig.8　Decomposition of XPath圖8XPath語(yǔ)句分解示例

從圖8可以看到，/site/regions//item/description/ parlist/listitem//parlist/listitem語(yǔ)句中有兩個(gè)組合是相同的，即{parlist/listitem}。當(dāng)讀到{parlist/listitem}的結(jié)果數(shù)據(jù)時(shí)，要與{parlist/listitem}的結(jié)果進(jìn)行Ancestor-Descendant關(guān)系判斷呢還是跟{item/description}的結(jié)果進(jìn)行Parent-Child關(guān)系判定呢？由于不能馬上判斷出讀到的數(shù)據(jù)是屬于哪個(gè){parlist/listitem}組合，采取的策略是按表達(dá)式從后向前進(jìn)行連接判定，先判斷{parlist/listitem}與{parlist/listitem}兩個(gè)是否是Ancestor-Descendant關(guān)系，不是的話(huà)再判斷{parlist/listitem} 與{item/description}的Parent-Child關(guān)系。

4.6數(shù)據(jù)重用

對(duì)一條查詢(xún)語(yǔ)句構(gòu)造其查詢(xún)計(jì)劃樹(shù)，可能出現(xiàn)Map階段輸出結(jié)果可以重用或者輸入文件可以重用的情況，這時(shí)可以利用重用數(shù)據(jù)以減少開(kāi)銷(xiāo)。

例如A/B/C/B，默認(rèn)查詢(xún)計(jì)劃樹(shù)中標(biāo)簽B在Map中需要做A/B和C/B連接判斷，都需要標(biāo)簽B的節(jié)點(diǎn)編碼文件要作為輸入文件，此時(shí)可以輸入一遍標(biāo)簽B的節(jié)點(diǎn)就行。又如A/B/A/B，查詢(xún)計(jì)劃中Map端需要做A/B的連接判定兩次，也可以合并為1次。

5　基于代價(jià)評(píng)估的查詢(xún)優(yōu)化

如圖6及圖8所示，對(duì)于一個(gè)查詢(xún)語(yǔ)句，不同的查詢(xún)計(jì)劃樹(shù)會(huì)使得模塊1和2的執(zhí)行代價(jià)不同。為了對(duì)代價(jià)進(jìn)行評(píng)估，需要對(duì)結(jié)構(gòu)連接操作結(jié)果集的數(shù)目進(jìn)行估算，對(duì)MapReduce作業(yè)建立代價(jià)模型。

5.1結(jié)構(gòu)連接操作結(jié)果集的估算

文獻(xiàn)[14]提出了一個(gè)在單節(jié)點(diǎn)環(huán)境下根據(jù)層次編碼統(tǒng)計(jì)信息對(duì)XPath查詢(xún)的CPU執(zhí)行代價(jià)估算的方法。本文結(jié)構(gòu)連接操作結(jié)果集的估算使用文獻(xiàn)[14]中的方法，來(lái)對(duì)兩個(gè)節(jié)點(diǎn)集連接結(jié)果進(jìn)行估算。

對(duì)于父子連接操作的結(jié)果集估算，如A/B，A表示一個(gè)標(biāo)簽名，A.result表示名字相同的節(jié)點(diǎn)層次編碼的集合。為了對(duì)A/B的結(jié)果集R進(jìn)行估算，需要對(duì)B集合的每一項(xiàng)b，遍歷A集合，查找A集合中是否存在節(jié)點(diǎn)a與節(jié)點(diǎn)b滿(mǎn)足父子關(guān)系，如果是則停止查找，并將b添加到R中。最后將R中的每個(gè)節(jié)點(diǎn)編碼信息中的nodeCount進(jìn)行相加，得到的和就是A/B的結(jié)果集數(shù)目的預(yù)估值。

對(duì)于祖孫連接操作的結(jié)果集估算，如A//B，需要對(duì)B集合的每一項(xiàng)b，遍歷A集合，查找A集合中是否存在節(jié)點(diǎn)a與節(jié)點(diǎn)b滿(mǎn)足祖孫關(guān)系，如果是則將b添加到R中，并繼續(xù)查找直到遍歷完。最后將R中的每個(gè)節(jié)點(diǎn)編碼信息中的nodeCount進(jìn)行相加，得到的和就是A//B的結(jié)果集數(shù)目的預(yù)估值。

對(duì)于數(shù)值型謂詞結(jié)果集的估算，如B>7，根據(jù)謂詞對(duì)應(yīng)的節(jié)點(diǎn)層次編碼、比較操作符以及參與比較的數(shù)值，使用直方圖進(jìn)行估算，詳細(xì)細(xì)節(jié)可看文獻(xiàn)[14]。

5.2MapReduce查詢(xún)代價(jià)模型

本文采用代價(jià)模型評(píng)估不同查詢(xún)計(jì)劃樹(shù)在Map-Reduce框架下執(zhí)行所消耗的代價(jià)。進(jìn)行代價(jià)估算需考慮3個(gè)因素：一是I/O開(kāi)銷(xiāo)；二是CPU的開(kāi)銷(xiāo)；三是網(wǎng)絡(luò)傳輸?shù)拈_(kāi)銷(xiāo)。表1是代價(jià)模型所使用的參數(shù)。

Table 1　Model parameters表1模型參數(shù)

查詢(xún)處理中Map過(guò)程有兩種不同操作，現(xiàn)在對(duì)兩種操作建立代價(jià)估算模型。首先定義Path(i,j)為路徑表達(dá)式，當(dāng)i=j時(shí)，代表Path(i,j)為一個(gè)節(jié)點(diǎn)名稱(chēng)，當(dāng)i

Path(i,i)對(duì)應(yīng)的節(jié)點(diǎn)數(shù)據(jù)集為Ii。按照式（1）～（3）可計(jì)算從HDFS上讀取輸入文件的代價(jià)RC（read cost），數(shù)據(jù)集進(jìn)行分區(qū)輸出的CPU代價(jià)PC（partition cost），Map數(shù)據(jù)輸出到本地文件的代價(jià)WC（write cost），三者構(gòu)成不進(jìn)行連接操作的Map階段代價(jià)。

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

按照式（5）～（7）可計(jì)算在HDFS讀取祖先節(jié)點(diǎn)數(shù)據(jù)集的代價(jià)RAC（read ancestor?s records cost），對(duì)連接結(jié)果數(shù)據(jù)集進(jìn)行分區(qū)輸出的CPU代價(jià)PPC（partition pair cost），結(jié)果數(shù)據(jù)集輸出節(jié)點(diǎn)到本地磁盤(pán)的代價(jià)WPC （write pair cost）。

式（7）與式（3）的主要區(qū)別是代價(jià)乘以2，這是因?yàn)榻Y(jié)果集中的每個(gè)數(shù)據(jù)都是由兩個(gè)節(jié)點(diǎn)編碼信息組成，所以大小也要多了一倍。

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

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

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

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

Job表示一個(gè)MapReduce作業(yè)，一個(gè)查詢(xún)的Map-Reduce作業(yè)的全部代價(jià)計(jì)算公式如下所示：

其中，∑CMi是查詢(xún)計(jì)劃樹(shù)中不做Map端連接的數(shù)據(jù)集Ii的Map階段代價(jià)總和；∑CM(j-1,j)是查詢(xún)計(jì)劃樹(shù)中進(jìn)行Map端連接的數(shù)據(jù)集Ij的Map階段代價(jià)。因?yàn)镸apReduce作業(yè)的Map任務(wù)數(shù)與輸入文件的大小相關(guān)，并行的Map任務(wù)數(shù)不同也會(huì)導(dǎo)致作業(yè)的效率不同，所以進(jìn)行代價(jià)評(píng)估時(shí)也需要考慮并行Map任務(wù)數(shù)的影響。而Reduce的組數(shù)一直大于集群中并行的Reduce任務(wù)數(shù)，因此這里不計(jì)入Reduce任務(wù)數(shù)的影響。假設(shè)查詢(xún)計(jì)劃的Map任務(wù)數(shù)為N，集群最大的并行Map任務(wù)數(shù)為M，則作業(yè)同時(shí)并行的Map任務(wù)數(shù)K=min(N,M)。

5.3啟發(fā)式優(yōu)化查詢(xún)算法

定義2J為一個(gè)狀態(tài)節(jié)點(diǎn)，保存了3個(gè)變量，第一個(gè)為路徑表達(dá)式Path，第二個(gè)為Path的執(zhí)行代價(jià)cost，第三個(gè)是Path中最后一個(gè)參與連接操作結(jié)構(gòu)的類(lèi)型type，type有兩種類(lèi)型EN和LP。EN表示元素節(jié)點(diǎn)名，LP表示一個(gè)二元連接結(jié)構(gòu)的長(zhǎng)路徑。

定義3 Path＋EN表示將連接節(jié)點(diǎn)EN添加到路徑表達(dá)式Path中，EN的數(shù)據(jù)集不進(jìn)行Map端連接操作。

定義4 Path-EN表示將路徑表達(dá)式Path中的最后一個(gè)連接節(jié)點(diǎn)EN除去。

定義5 EN1*EN2表示一個(gè)二元連接結(jié)構(gòu)，EN1與EN2兩個(gè)節(jié)點(diǎn)數(shù)據(jù)集在Map端進(jìn)行連接操作。

本文使用最佳優(yōu)先搜索算法[15]查找代價(jià)最小的查詢(xún)計(jì)劃。對(duì)一個(gè)查詢(xún)語(yǔ)句，從左往右逐個(gè)增加連接結(jié)構(gòu)生成查詢(xún)計(jì)劃樹(shù)，具體過(guò)程如下:

初始化優(yōu)先隊(duì)列Queue，用于保存狀態(tài)節(jié)點(diǎn)并每次返回執(zhí)行代價(jià)最低的狀態(tài)節(jié)點(diǎn)；minCost用于查詢(xún)語(yǔ)句的最低執(zhí)行代價(jià)，初始化為雙浮點(diǎn)最大值；minJ用于存儲(chǔ)執(zhí)行代價(jià)最低的完整查詢(xún)路徑。

初始化第一個(gè)狀態(tài)節(jié)點(diǎn)J，J.Path=Path(1,1)，根據(jù)表達(dá)式計(jì)算出各個(gè)變量的數(shù)據(jù)后存儲(chǔ)，添加到Queue中。

當(dāng)Queue不為空時(shí)，返回隊(duì)列中代價(jià)最低的狀態(tài)節(jié)點(diǎn)J，根據(jù)J的路徑表達(dá)式結(jié)構(gòu)添加新的連接節(jié)點(diǎn)EN1，添加規(guī)則如下所示。

當(dāng)J.type=EN時(shí)，可以生成兩個(gè)新的狀態(tài)節(jié)點(diǎn)進(jìn)行添加，假設(shè)J.Path的最后一個(gè)連接節(jié)點(diǎn)為EN′，則：

新的狀態(tài)節(jié)點(diǎn)：

J1.Path=J.Path+EN1

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

當(dāng)J.type=LP時(shí)，可以生成一個(gè)新的狀態(tài)節(jié)點(diǎn)：

J1.Path=J.Path+EN1

新的狀態(tài)節(jié)點(diǎn)根據(jù)路徑表達(dá)式更新作業(yè)的執(zhí)行代價(jià)，當(dāng)cost>minCost且type=LP時(shí)，該狀態(tài)節(jié)點(diǎn)則放棄掉。當(dāng)路徑表達(dá)式已經(jīng)是完整的查詢(xún)語(yǔ)句時(shí)，如果cost

算法4 Optimization

輸入：一個(gè)查詢(xún)語(yǔ)句XPath。

輸出：一個(gè)執(zhí)行計(jì)劃樹(shù)。

/*對(duì)語(yǔ)句進(jìn)行解析*/

1.Parse（XPath）；

2.初始化優(yōu)先隊(duì)列Queue，代價(jià)最小作業(yè)minJob；

3.minJob.cost←MAX；

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

5.Push J into Queue；

/*優(yōu)先隊(duì)列，每次返回代價(jià)最小節(jié)點(diǎn)*/

6.While Queue is not empty do

7.J←pop from Queue；

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

9.break；

/*對(duì)路徑根據(jù)類(lèi)型進(jìn)行擴(kuò)展，不是完整路徑則壓入Queue中，是的話(huà)根據(jù)代價(jià)更新minJob*/

10.ExpandAndUpdate(J，minJob，Queue)；

11.Endwhile；

12.return minJob.path；

對(duì)于查詢(xún)語(yǔ)句/A/B//C/D的優(yōu)化過(guò)程如圖9所示。圖中用|號(hào)表示分割，分割點(diǎn)所在的連接操作在Reduce端完成，其余連接操作都在Map端完成。

Fig.9　Query optimization process圖9 查詢(xún)優(yōu)化過(guò)程

6　實(shí)驗(yàn)測(cè)試

6.1實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)測(cè)試硬件環(huán)境是4臺(tái)IBM刀片服務(wù)器。安裝Openstack云計(jì)算平臺(tái)，創(chuàng)建了6臺(tái)CPU為2個(gè)虛擬內(nèi)核，內(nèi)存為4 GB的主機(jī)，其中1臺(tái)為namenode，5臺(tái)為datanode。

實(shí)驗(yàn)數(shù)據(jù)采用XMark[16]標(biāo)準(zhǔn)的數(shù)據(jù)集。實(shí)驗(yàn)測(cè)試采用的XML數(shù)據(jù)集如表2所示，所選取的主要查詢(xún)語(yǔ)句如表3所示。實(shí)驗(yàn)測(cè)試有3部分：（1）3種編碼方式下查詢(xún)速度的實(shí)驗(yàn)對(duì)比。（2）區(qū)間編碼方式下在不同數(shù)據(jù)集下的查詢(xún)速度對(duì)比。（3）計(jì)劃樹(shù)優(yōu)化前后的查詢(xún)速度對(duì)比。實(shí)驗(yàn)中將在分布式環(huán)境下，對(duì)不同查詢(xún)語(yǔ)句在不同數(shù)據(jù)集下進(jìn)行多次查詢(xún)（前兩部分實(shí)驗(yàn)采用的查詢(xún)計(jì)劃樹(shù)是未優(yōu)化的查詢(xún)計(jì)劃樹(shù)），記錄查詢(xún)時(shí)間并取得平均值。第三部分實(shí)驗(yàn)則選取查詢(xún)性能最優(yōu)的區(qū)間編碼方式進(jìn)行優(yōu)化方法的查詢(xún)性能測(cè)試。

Table 2　Dataset表2數(shù)據(jù)集

6.2實(shí)驗(yàn)結(jié)果與分析

（1）3種編碼方式查詢(xún)速度的實(shí)驗(yàn)對(duì)比

圖10～圖14為XP1到XP5在不同數(shù)據(jù)集下的查詢(xún)時(shí)間對(duì)比。從測(cè)試結(jié)果中可以看出，區(qū)間編碼的查詢(xún)性能在不同數(shù)據(jù)集和查詢(xún)語(yǔ)句下都是3種編碼中最優(yōu)的，且隨著數(shù)據(jù)量的增大，查詢(xún)性能的優(yōu)越性越來(lái)越明顯。前綴編碼和層次編碼兩者的查詢(xún)性能則比較接近，總體上層次編碼查詢(xún)速度更快。查詢(xún)性能上的差異主要來(lái)自分區(qū)和排序的執(zhí)行代價(jià)不同，區(qū)間編碼的分區(qū)和排序是直接對(duì)長(zhǎng)整數(shù)類(lèi)型數(shù)據(jù)進(jìn)行計(jì)算，而前綴編碼和層次編碼是先對(duì)字符串類(lèi)型數(shù)據(jù)進(jìn)行轉(zhuǎn)化后再計(jì)算，前者代價(jià)相對(duì)小于后者。

Fig.10　Query time of XP1圖10XP1查詢(xún)時(shí)間

Fig.11　Query time of XP2圖11XP2查詢(xún)時(shí)間

Fig.12　Query time of XP3圖12XP3查詢(xún)時(shí)間

Fig.13　Query time of XP4圖13XP4查詢(xún)時(shí)間

Fig.14　Query time of XP5圖14XP5查詢(xún)時(shí)間

（2）查詢(xún)速度隨數(shù)據(jù)集變化的情況

為了更準(zhǔn)確地觀察，這里采用的性能指標(biāo)為數(shù)據(jù)集節(jié)點(diǎn)數(shù)與查詢(xún)時(shí)間之比。經(jīng)過(guò)分析，XP1到XP5語(yǔ)句中查詢(xún)性能變化情況主要有兩種：第一種是如圖15中XP1的查詢(xún)性能變化情況，主要有XP1、XP2、XP3、XP5語(yǔ)句，隨著數(shù)據(jù)集的變大，查詢(xún)處理性能具有近線(xiàn)性特點(diǎn)。

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

第二種是如圖16中XP4的變化情況，查詢(xún)性能不斷提高，直到R5時(shí)性能下降。主要的原因是XP4的查詢(xún)數(shù)據(jù)處理量比其他幾個(gè)語(yǔ)句大，在R5數(shù)據(jù)集下超過(guò)了集群的同時(shí)并行能力最大數(shù)，導(dǎo)致需要多個(gè)周期的并行而使得性能下降。

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

（3）不同計(jì)劃樹(shù)的查詢(xún)速度對(duì)比

本實(shí)驗(yàn)中展示了只做Reduce連接的查詢(xún)計(jì)劃的執(zhí)行時(shí)間。圖17是XP1到XP5語(yǔ)句在R2（在其他數(shù)據(jù)集上也有相似結(jié)論）下的3種查詢(xún)計(jì)劃的執(zhí)行情況。其中，RJ（reduce join）表示只做Reduce連接的查詢(xún)計(jì)劃，DJ（default join）表示默認(rèn)的查詢(xún)計(jì)劃，OJ （optimized join）表示優(yōu)化后的查詢(xún)計(jì)劃。

Fig.17　Results of R2 comparison before and after optimization圖17　R2下優(yōu)化前后結(jié)果對(duì)比

從圖17可以看出，RJ在XP1、XP2、XP4中查詢(xún)性能略高于DJ，其他幾條語(yǔ)句則DJ的查詢(xún)性能更好。而OJ則在不同的查詢(xún)語(yǔ)句中都是查詢(xún)性能最好的，在本研究開(kāi)展過(guò)的實(shí)驗(yàn)中，OJ比DJ的查詢(xún)效率提高最高可達(dá)20%。

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

本文研究和實(shí)現(xiàn)了3種不同XML數(shù)據(jù)編碼算法，以此為基礎(chǔ)實(shí)現(xiàn)了基于MapReduce的XML結(jié)構(gòu)連接處理，最后還實(shí)現(xiàn)了基于MapReduce作業(yè)的XML查詢(xún)處理代價(jià)模型和查詢(xún)優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明，基于區(qū)間編碼方式的XML查詢(xún)處理性能在3者中最優(yōu)，提出的代價(jià)估算模型和優(yōu)化方法能有效地提高查詢(xún)處理性能。下一步將研究如何動(dòng)態(tài)調(diào)整分區(qū)長(zhǎng)度以進(jìn)一步提高XML查詢(xún)處理性能。

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年于華中科技大學(xué)獲得博士學(xué)位，現(xiàn)為華南理工大學(xué)教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)閄ML數(shù)據(jù)庫(kù)，移動(dòng)數(shù)據(jù)庫(kù)，商業(yè)流程管理等。

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—），男，廣東汕頭人，華南理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)榉植际接?jì)算。

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—），男，廣東惠州人，華南理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)榉植际接?jì)算。

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

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-13,http://www.cnki.net/kcms/detail/11.5602.TP.20151013.1624.004.html

文獻(xiàn)標(biāo)志碼：A

中圖分類(lèi)號(hào)：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