基于MapReduce的Skyline-join查詢算法

孫大烈，李建中

(哈爾濱工業(yè)大學 計算機科學與技術學院，150001哈爾濱，sdl@hit.edu.cn)

給定一個感興趣的屬性集合，Skyline查詢返回這樣的元組，這些元組在任何一個屬性上都不受其他元組制約[1].例如，一名學生想要尋找一個合適的住處，他可能提交這樣的查詢:“返回價格便宜并且離學校距離近的公寓”.Skyline查詢在決策系統(tǒng)中很有價值(用處).由于它的重要性，研究人員已經(jīng)開始在商用數(shù)據(jù)庫管理系統(tǒng)(DBMS)中實現(xiàn) Skyline 查詢[2－3].

現(xiàn)有的研究工作大多假設Skyline查詢只局限于一個數(shù)據(jù)表，也就是說，所有待查的屬性都來自于同一張數(shù)據(jù)表.然而，這種假設在互聯(lián)網(wǎng)環(huán)境中不再成立，因為此時查詢處理需要來自多源的數(shù)據(jù).例如，數(shù)據(jù)庫cheapoair.com提供機票預訂服務，BookInHotels.com提供酒店預訂服務.假設用戶提交這樣的查詢“請列出所有在5月11日起飛的最廉價的航班，以及距離機場最近的四星級酒店”.這種查詢與Skyline查詢有共同的特點，但是它需要從多張數(shù)據(jù)表提取數(shù)據(jù)信息.在本文中，稱這種類型的查詢?yōu)镾kyline-join.

處理Skyline-join查詢的一個簡單而原始的方法是，先連接所有相關的數(shù)據(jù)表，然后再應用現(xiàn)有的Skyline算法.然而，這種簡單的算法往往效率低下，不能提供及時的結果.因此，本文提出一種新的基于 MapReduce框架[4－5]的分布式并行算法.該算法可以應用在計算機集群環(huán)境中，通過將計算分布在不同的節(jié)點上來提高處理速度.

1 Skyline-join查詢

如前所述，不同于現(xiàn)有的操作，Skyline-join操作會涉及多張數(shù)據(jù)表.對于某單一數(shù)據(jù)表，如果當0≤i≤d時，vi?v'i并且 ?j(0≤ j≤d)∧(vj?v'j)，這里定義?和?為偏序關系，則元組ti=(v0，v1，…，vd)制 約 元 組 tj=(v'0，v'1，…，v'd).Skyline查詢返回那些不受其他元組制約的元組.若Q= ＜ {A1，A2，B1，B2}，?，{A3，B3}＞ 取自多張數(shù)據(jù)表，則引發(fā)了新問題——多數(shù)據(jù)表Skyline查詢.為處理這種查詢，本文引入一種新的查詢操作，稱為 Skyline-join.最近，Skyline-join查詢引起了其他研究者的興趣[6].

設有數(shù)據(jù)庫D，其中數(shù)據(jù)表集合為T，Skylinejoin表示為 ＜S，C，J＞，其中S為Skyline查詢中的屬性集合，C為用戶提交的查詢條件集合，J為連接屬性集合.S(T)，C(T)和J(T)分別為對于某數(shù)據(jù)表T的Skyline查詢屬性集、條件屬性集以及連接屬性集.為討論簡便起見，這里假設J∩S=?.事實上，J∩S≠?只是算法的一種特殊情況.對于某查詢 ＜S，C，J＞，Skyline-join檢索空間定義為:

定義1 Skyline-join檢索空間.

Ttotal是查詢 ＜S，C，J＞ 的Skyline-join檢索空間，當且僅當

c)不存在T'total滿足上述兩條性質，且其中數(shù)據(jù)表的個數(shù)少于Ttotal.

Skyline-join查詢在其相應檢索空間里進行處理，檢索空間中不同元組之間的制約關系定義為:

定義2 Skyline-join Domination.

給定Skyline-join查詢 ＜S，C，J＞及其檢索空間 Ttotal，對于 Ttotal中的兩元組 t1=(v0，v1，v2，…，vd)和 t2=(v0，v1，v2，…，vd)，t1制約 t2當且僅當

為表述方便，本文用ti?domtj表示元組tiSkyline-join制約元組tj，并用ti?Atj來表示元組ti在屬性集合A上Skyline-join制約元組tj.

定義3 Skyline-join結果集.

對于Skyline-join查詢Q=＜S，C，J＞，檢索空間為Ttotal，其結果集R有以下性質:

性質1 ?ti(ti∈R)→??tj(tj∈Ttotal)∧(tj?domtj).

性質2 對于元組ti∈R，ti=(v0，v1，…，vd)，若存在atti∈C，則vi必須滿足相應查詢屬性條件.

為方便討論簡單，假設查詢條件C=?并只考慮數(shù)值型屬性，域值范圍[0，100]，并用“MAX”作為Skyline條件.

2 MapReduce框架

MapReduce是由Google提出的處理海量數(shù)據(jù)的并行處理平臺.它可以應用在計算機集群之上，通過將數(shù)據(jù)和計算分布在不同的節(jié)點來取得高性能.MapReduce也是一個靈活的編程框架，它提供了兩個接口函數(shù):Map和Reduce.用戶可以實現(xiàn)自己的Map和Reduce函數(shù)來完成相關的處理任務.

Map和Reduce函數(shù)的輸入必須是一對(key，value).其中key用來表示數(shù)據(jù)的鍵值，而value則代表實際的數(shù)據(jù).Map函數(shù)可以抽象為

對每一個輸入的(key，value)對，Map函數(shù)進行相應的處理，并輸出一串新的(key，value)對.這些新的(key，value)對被傳送到不同的Reduce函數(shù)進行進一步的處理.而Reduce函數(shù)可以抽象為

Reduce函數(shù)收到來自不同Map函數(shù)的(key，value)對.在進行處理之前，它先對這些(key，value)對按照它們的key值進行排序，具有相同key值的對被集成為(key，list(v))，即一個key值對應一個value數(shù)組.(key，list(v))作為輸入被傳入Reduce函數(shù)，然后按照用戶的處理邏輯生成結果.通常結果是一串值 (表示為list(v))，并被寫為分布式文件系統(tǒng)，如 GFS[7]和 BigTable[8].

圖1列出了基于MapReduce的統(tǒng)計詞頻的偽代碼.在Map函數(shù)中，每次對一行的文本進行分析，將單詞切分出來.對每一個單詞w產(chǎn)生一個(key，value)對，即 (w，1)，表示該單詞已經(jīng)出現(xiàn)了一次.在Reduce函數(shù)，對同一個函數(shù)的統(tǒng)計被集成在一個(key，list(value))中.因此，只要遍歷該數(shù)組，就可以知道這個單詞出現(xiàn)的次數(shù).

圖1 MapReduce詞頻統(tǒng)計算法

3 基于MapReduce的查詢方法

本文用表1，表2作為例子來闡述相關的算法.

表1 表R

表2 表S

其中表R和表S使用ID屬性進行連接，而對于其他屬性 (A1…Am以及 B1…Bn)，Skyline-join查詢使用Max作為條件，要求返回在這些屬性上不被其他記錄支配的記錄.

使用MapReduce來處理Skyline-join查詢可分為:1)一個MapReduce任務被用來產(chǎn)生表的連接結果;2)連接的結果被用來作為另一個MapReduce任務的輸入，而該任務產(chǎn)生多個表的Skyline-join結果.

3.1 產(chǎn)生連接結果

在第1個MapReduce任務中，Map函數(shù)從分布式文件系統(tǒng)讀取兩個表的數(shù)據(jù)，對于每一個記錄，Map函數(shù)產(chǎn)生一個(key，value)對，其中該記錄的ID值被用作為key，而其他值被作為value.這樣一來，能夠在ID上連接的表R和表S的記錄將被發(fā)送到同一個Reduce函數(shù).該Reduce函數(shù)將含有相同ID的記錄集合在一起，采用基于內存的連接算法產(chǎn)生相應的表連接結果.在表連接結果產(chǎn)生之后，Reduce函數(shù)再調用基于內存的Skyline算法，比如BNL算法.被其他記錄支配的記錄被舍去，因為它們不可能成為最終的Skyline-join結果.其他記錄被寫入分布式文件系統(tǒng).圖2給出了相關偽碼.

圖2 MapReduce的Skyline-join算法

圖2是針對兩個表的Skyline-join.對于更多表的Skyline-join查詢，該算法依舊適用.唯一的區(qū)別就是當處理有n個表的Skyline-join查詢時，需要有n種Map函數(shù)，每種函數(shù)讀取一個表的數(shù)據(jù).同時在Reduce函數(shù)，需要對n個表進行連接操作.

3.2 產(chǎn)生Skyline-Join結果

第2個MapReduce任務讀取上一個任務產(chǎn)生的結果，然后采用空間劃分的方式來計算Skyline結果.假設Skyline-join查詢要求在x和y屬性上得到不能被支配的元組，圖3給出了一種可能的空間劃分方法.該方法將x和y平均劃為4個區(qū)域，從而整個空間被劃為4×4=16的子空間.如果一個記錄位于子空間S(a，b)，那么它的x屬性的值位于x的第a個區(qū)間，而它的y屬性位于y的第b個區(qū)間.

圖3 空間劃分

在第2個MapReduce任務中，Map讀取上一個任務的結果，然后為每一個記錄判斷其所在的子空間.假設下一個記錄t在空間S(a，b)，那么Map為它生成的(key，value)對為(h(a，b)，t).其中h為一個哈希函數(shù)，給定兩個值a和b，h(a，b)返回一個Reduce函數(shù)的ID.根據(jù)該ID，Map函數(shù)知道該(key，value)對應該傳遞給哪一個Reduce函數(shù).采用這種方法，同一個子空間的記錄都會發(fā)送給同一個Reduce函數(shù).該Reduce函數(shù)調用基于內存的Skyline算法，可以計算得出該子空間的Skyline結果.

當?shù)?個MapReduce任務完成后，分布式文件系統(tǒng)存儲著每個子空間的Skyline-join結果.然而這并不是最終的結果.為了得到全局的Skyline-join結果，第3個MapReduce任務被提交，用來合并子空間的Skyline-join結果.在合并之前，本文采用一個預處理過程來刪減掉不可能產(chǎn)生結果的子區(qū)間.

在圖 3 中，假設子空間 S(3，2)，S(2，2)，S(3，3)和S(2，3)產(chǎn)生了一些Skyline-join結果.那么子空間S(1，1)可以被排除，因為即使它產(chǎn)生了一些結果，其結果也必然被上述4個子空間中的結果支配，從而不可能出現(xiàn)在最終結果中.相反，子空間S(3，1)，S(2，1)，S(1，2)和 S(1，3)不能被排除，因為它們的結果并不能被前面的子空間支配.

預處理之后，剩下的結果被Map函數(shù)讀取，Map函數(shù)為所有的記錄產(chǎn)生同一個key，使得它們都被發(fā)送到同一個Reduce函數(shù).該 Reduce函數(shù)調用傳統(tǒng)的Skyline算法，如文獻[9－10]，來產(chǎn)生最終的結果.

4 實驗結果

為了驗證分布式算法的有效性，本文采用Amazon的EC2[11]平臺搭建了一個集群環(huán)境，并根據(jù)文獻[6]的描述生成了實驗數(shù)據(jù).實驗數(shù)據(jù)包括兩個數(shù)據(jù)表R和S.表R包含3個屬性:員工編號、年齡和工資.表S包含3個屬性:員工編號、經(jīng)理編號和公司編號.所有屬性均為整形，并符合均勻數(shù)據(jù)分布，其中表R和表S使用員工編號進行連接操作.在一個n節(jié)點構成的集群中，每個表的元組數(shù)為1 500 000 n.每個節(jié)點運行4個Map進程和2個Reduce進程.

圖4展示了隨著節(jié)點個數(shù)的增加，查詢處理時間的變化.可以看到，本文的分布式算法基本不受節(jié)點個數(shù)以及數(shù)據(jù)量的影響(節(jié)點越多數(shù)據(jù)量越大).因此，該算法具有很好的可擴展性.如果要獲得更好的查詢性能或者能夠處理更多的數(shù)據(jù)，只需要增加更多的節(jié)點即可.

圖4 節(jié)點數(shù)目的影響

作為比較，圖5顯示了當節(jié)點增加數(shù)據(jù)量不變的情況下，查詢的效率變化.可以看出，本文提出的Skyline-join算法非常適合應用在并發(fā)處理平臺如MapReduce之上.當節(jié)點數(shù)量增加，查詢的速度也隨之變快，幾乎達到線性遞減的趨勢.

圖5 節(jié)點數(shù)目的影響

5 結論

1)通過將數(shù)據(jù)以及計算分布在不同的節(jié)點上，使用并行化的處理機制來提高性能.

2)在Map階段采用分片剪枝的方法來降低復雜度.

3)通過在真實的云計算平臺實驗表明，該算法具有高可擴展性的特點.

[1]BORZSONYI S，STOCKER K，KOSSMANN D.The Skyline operator[C]//Proceedings of the 17th International Conference on Data Engineering.Washington，DC:IEEE Computer Society，2001:421－430.

[2]CHAUDHURI S，DALVI N，KAUSHIK R.Robust cardinality and cost estimation for skyline operator[C]//Proceedings of the 22nd International Conference on Data Engineering.Washington，DC:IEEE Computer Society，2006:64.

[3]EDER H，WEI Fang.Evaluation of skyline algorithms in PostgreSQL[C]//Proceedings of the 13th International Database Engineering＆Applications Symposium.New York，NY:ACM，2009:334－337.

[4]DEAN J，GHEMAWAT S.MapReduce:Simplified data processing on large clusters[J].Communication of ACM，2008，51(1):107－113.

[5]YANG Hung-Chih，DASDAN A，HSIAO Ruey-Lung，et al.Map-reduce-merge:simplified relational data processing on large clusters[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data.New York，NY:ACM，2007:1029－1040.

[6]JIN W，ESTER M，HU Z J，et al.The multi-relational skyline operator[C]//Proceedings of the IEEE 23rd International Conference on Data Engineering.Washington，DC:IEEE，2007，1376 －1380.

[7]GHEMAWAT S，GOBIOFF H，LEUNG Shun-`Tak.The Google file system[J].ACM SIGOPS Operating Systems Review，2003，37(5):29－43.

[8]CHANG F，DEAN J，GHEMAWAT S，et al.Bigtable:A distributed storage system for structured data[C]//Proceedings of the 7th Usenix Symposium on Operating Systems Design and Implementation.Berkeley CA:USENIX Association，2006:205－218.

[9]BARTOLINI I，CIACCIA P，PATELLA M.Salsa:Computing the skyline without scanning the whole sky[C]//Proceedings of the 15th ACM International Conference on Information and Knowledge Management.Arlington，Virginia，2006:405 －414.

[10]CHAN C Y，ENG P K，TAN K L.Stratified computation of skylines with partially-ordered domains[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data.New York，NY:ACM，2005:203－214.

[11]Amazon.Amazon Elastic Compute Cloud(Amazon EC2)[EB/OL].http://aws.amazon.com/ec2//192－5518875－2032964.