鄭雪梅1,2 ，陳梅1,2 ，李暉1,2

　?。?.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025;2.貴州大學(xué) 貴州省先進(jìn)計(jì)算與醫(yī)療信息服務(wù)工程實(shí)驗(yàn)室，貴州 貴陽(yáng) 550025)

　　摘要：根據(jù)基于OLAP的what-if分析的查詢特點(diǎn)，使用分布式并行處理技術(shù)解決whatif分析性能較低的問(wèn)題。以星座模型為基礎(chǔ)的whatif分析中，將多維聚集查詢分布到不同計(jì)算節(jié)點(diǎn)進(jìn)行聚集計(jì)算，然后將各個(gè)計(jì)算節(jié)點(diǎn)的聚集計(jì)算結(jié)果合并輸出。該方法根據(jù)基于OLAP的whatif分析中其維表遠(yuǎn)遠(yuǎn)小于事實(shí)表的特性，將事實(shí)表中的記錄進(jìn)行水平分片，充分利用各節(jié)點(diǎn)計(jì)算和I/O處理能力，以解決OLAP查詢中計(jì)算密集型及I/O消耗過(guò)大的難題。在該方法中，隨著計(jì)算節(jié)點(diǎn)數(shù)目的增加，其查詢時(shí)間隨之減少，有效地提升了分析效率。

　　關(guān)鍵詞：OLAP; what-if分析;分布式并行處理

0引言

　　what-if分析是決策者對(duì)多種決策方案進(jìn)行預(yù)測(cè)或評(píng)估時(shí)的常用手段，通常以多種形式應(yīng)用于不同的應(yīng)用場(chǎng)景，尤其在決策系統(tǒng)中發(fā)揮重要作用。簡(jiǎn)單地說(shuō)，whatif分析就是以數(shù)據(jù)倉(cāng)庫(kù)中歷史數(shù)據(jù)為基礎(chǔ)數(shù)據(jù)的假設(shè)分析，決策者根據(jù)決策目標(biāo)制定一系列假設(shè)場(chǎng)景，通過(guò)對(duì)已有數(shù)據(jù)的假設(shè)分析得到假設(shè)場(chǎng)景下的商業(yè)數(shù)據(jù)變化情況。

　　近年來(lái)，隨著數(shù)據(jù)倉(cāng)庫(kù)中數(shù)據(jù)的不斷膨脹，數(shù)據(jù)量從TB級(jí)增長(zhǎng)到PB級(jí)甚至EB級(jí)別，決策者在海量的數(shù)據(jù)中挖掘價(jià)值，以便更快更準(zhǔn)地捕獲商機(jī)，在很大程度上還需要借助whatif分析工具的應(yīng)用。因此，基于OLAP的whatif分析一直受到很多學(xué)者的關(guān)注，但由于whatif分析自身的復(fù)雜性，至今未得到廣泛應(yīng)用。在假設(shè)分析時(shí)通常需要更改Cube結(jié)構(gòu)或修改Cube數(shù)據(jù)，這些操作均涉及到Cube重計(jì)算，花費(fèi)時(shí)間較長(zhǎng)，限制了whatif分析的能力。

　　隨著大規(guī)模并行處理關(guān)系數(shù)據(jù)庫(kù)的發(fā)展，如Vertica、微軟的SQL Server并行數(shù)據(jù)倉(cāng)庫(kù)以及Greenplum數(shù)據(jù)倉(cāng)庫(kù)等的使用，使高效的并行查詢處理及數(shù)據(jù)分析成為可能。因此，本文結(jié)合基于OLAP的whatif分析的特點(diǎn)，與分布式并行處理技術(shù)相結(jié)合，可以有效提高查詢效率，解決決策者面臨分析效率低的問(wèn)題。

1相關(guān)研究工作

　　whatif分析的概念早已提出，由于其復(fù)雜性未得到廣泛應(yīng)用，但是對(duì)其研究一直在進(jìn)行中。參考文獻(xiàn)［1］中提出基于Delta表的whatif分析，通過(guò)預(yù)處理方法提高whatif分析效率，更改工作內(nèi)容均是在內(nèi)存數(shù)據(jù)庫(kù)中實(shí)現(xiàn)，而不是在基于磁盤(pán)的關(guān)系型數(shù)據(jù)庫(kù)中實(shí)現(xiàn)，其性能未得到明顯提升。參考文獻(xiàn)［2］在參考文獻(xiàn)［1］的基礎(chǔ)上，利用并行計(jì)算模型MapReduce實(shí)現(xiàn)whatif分析，其性能有一定的提升。隨著whatif分析的研究，參考文獻(xiàn)［34］分別將whatif分析應(yīng)用于MapReduce的調(diào)優(yōu)及復(fù)雜云數(shù)據(jù)中心的資源分配。參考文獻(xiàn)［5］詳細(xì)介紹了分布式并行處理整體方案。參考文獻(xiàn)［6］提出了內(nèi)存數(shù)據(jù)庫(kù)中利用分布式并行處理技術(shù)實(shí)現(xiàn)OLAP并行操作的方案。本文中的whatif分析使用分布式并行處理技術(shù)，利用并行處理機(jī)制提升whatif分析性能。

2what-if分析

　　本節(jié)主要以O(shè)LAP模型中的星座模型為例，詳細(xì)介紹whatif分析中的基礎(chǔ)概念及實(shí)現(xiàn)方法，并分析其實(shí)現(xiàn)過(guò)程中存在的問(wèn)題及擬解決方法。

　　2.1基于OLAP的what-if分析

　　基于OLAP的whatif分析實(shí)質(zhì)是基于假設(shè)場(chǎng)景的OLAP查詢。在假設(shè)數(shù)據(jù)生成后，生成新的Cube，Cube通常有星型、星座和雪花等OLAP模型；基于新的Cube可以執(zhí)行相應(yīng)的OLAP操作，如Rollup。圖1為本文使用Foodmart數(shù)據(jù)的OLAP模型。

　　圖1中有2個(gè)事實(shí)表和6個(gè)維表。其中，sales_fact(product_id, time_id, customer_id, promotion_id, store_id, store_sales)、sales_fact_virtual(product_id, time_id, customer_id, promotion_id, store_id, store_sales, wbversion, sign)為兩個(gè)事實(shí)表。

　　sales_fact用于存儲(chǔ)數(shù)據(jù)庫(kù)中的歷史數(shù)據(jù)，在whatif分析中稱之為基表；sales_fact_virtual是與sales_fact結(jié)構(gòu)相似的另一個(gè)事實(shí)表，叫delta表，用于存儲(chǔ)假設(shè)數(shù)據(jù)，這類的假設(shè)分析是基于delta表的whatif分析。由事實(shí)表可知，delta表是在基表的基礎(chǔ)上增加了多個(gè)字段，如wbversion和sign，wbversion表示版本號(hào)，sign為更新類型，其更新類型主要有插入(I)、更新(U)和刪除(D)三類，分別用1、0、-1值來(lái)表示。store_sales為度量值，其余均為維度值。

　　2.2what-if分析實(shí)現(xiàn)

　　本節(jié)主要介紹基于delta表的what-if分析的實(shí)現(xiàn)過(guò)程。首先，根據(jù)假設(shè)場(chǎng)景將假設(shè)數(shù)據(jù)存儲(chǔ)到delta表中；其次，將delta表與基表合并生成新的Cube，此步驟稱之為假設(shè)更新，也叫what-if更新；最后，基于新生成的Cube執(zhí)行OLAP查詢操作。

　　對(duì)于基表與delta表的合并，常用的方法是通過(guò)等值連接、左連接和全連接等操作來(lái)實(shí)現(xiàn)。下面是依據(jù)2.1節(jié)中的OLAP模型通過(guò)使用連接操作來(lái)實(shí)現(xiàn)what-if分析。

　　在連接算法中，首先排除基表中受delta表D和U類更新影響的記錄，然后再與delta表中U類型和I類型的記錄合并。三種算法具體實(shí)現(xiàn)如下：

　　算法1等值連接算法

　　tmptable = sales_fact left(sf) join sales_fact_virtual(sfv)

　　for each tuple t in sf

　　output(t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales)->what-if_view_0

　　for each tuple t in tmptable

　　output(t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales)->what-if_view_1

　　for each tuple t in sfv

　　if sign=1 or 0 then output(t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales)->what-if_view_2

　　return what-if_view_0 EXCEPT what-if_view_1 union all what-if_view_2

　　算法2左連接算法

　　tmptable = sales_fact left(sf) join sales_fact_virtual(sfv)

　　for each tuple t in tmptable

　　if t.sign is null then output(t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales)->what-if_view;

　　if t.sign=-1 then skip t;

　　for each tuple t in sfv

　　if sign=1 or 0 then output(t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales)->what-if_view_1

　　return what-if_view union all what-if_view_1

　　算法3全連接算法

　　tmptable = sales_fact left(sf) join sales_fact_virtual(sfv)

　　for each tuple t in tmptable

　　if t.product_id is not null and t.sign is null then output (t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales) ->what-if_view

　　if t.product_id is not null and t.sign = 1 or 0 then output (t.product_id(sfv), t.time_id(sfv), t.customer_id(sfv), t.promotion_id(sfv), t.store_id(sfv), t.store_sales(sfv)) ->what-if_view

　　return what-if_view；

　　通過(guò)連接操作執(zhí)行假設(shè)更新后得到新的Cube，在基于Cube的OLAP查詢中，其OLAP查詢結(jié)果通常為group by 和order by所得的聚集結(jié)果值，涉及操作有MAX、MIN、SUM、COUNT等分布式聚集運(yùn)算等。

　　綜上所述，在what-if分析的實(shí)現(xiàn)過(guò)程中，關(guān)鍵問(wèn)題是如何高效地合并基表和delta表并執(zhí)行OLAP操作。下節(jié)將介紹使用分布式并行處理來(lái)提高whatif分析的整體效率。

3分布式并行執(zhí)行

　　3.1分布式并行處理

　　基于Sharednothing結(jié)構(gòu)的分布式并行數(shù)據(jù)庫(kù)具有較好的可擴(kuò)展性，圖2為本文使用的分布式并行數(shù)據(jù)庫(kù)集群架構(gòu)，整個(gè)集群由多個(gè)數(shù)據(jù)節(jié)點(diǎn)（Segment Host）和控制節(jié)點(diǎn)（Master Host）組成。Master Host主要負(fù)責(zé)與客戶端的通信、對(duì)SQL進(jìn)行分析以及生成執(zhí)行計(jì)劃并分發(fā)到每個(gè)Segment上執(zhí)行，最后將匯總結(jié)果反饋給客戶端；數(shù)據(jù)節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的存儲(chǔ)、存取以及執(zhí)行Master分發(fā)的SQL語(yǔ)句，在每個(gè)數(shù)據(jù)節(jié)點(diǎn)上可以允許有多個(gè)數(shù)據(jù)庫(kù)。同時(shí)，各個(gè)節(jié)點(diǎn)之間的信息交互通過(guò)節(jié)點(diǎn)互聯(lián)網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)。

　　分布式并行處理數(shù)據(jù)庫(kù)集群架構(gòu)中，數(shù)據(jù)劃分方法對(duì)其并行處理的性能影響很大，大多采用的是哈希劃分法和范圍劃分法。文本中即采用了Hash劃分方式將數(shù)據(jù)分布到各個(gè)節(jié)點(diǎn)上。其劃分過(guò)程為：當(dāng)數(shù)據(jù)存入數(shù)據(jù)庫(kù)時(shí)進(jìn)行數(shù)據(jù)劃分處理，即根據(jù)表中的某一個(gè)或幾個(gè)字段的哈希值分布到每個(gè)節(jié)點(diǎn)。

　　在涉及連接操作運(yùn)算的查詢中，利用分布式并行處理數(shù)據(jù)庫(kù)對(duì)查詢操作并行化，可以充分利用系統(tǒng)中所有的處理器和I/O處理能力，從而縮短查詢響應(yīng)時(shí)間。利用分布式并行處理數(shù)據(jù)庫(kù)的優(yōu)勢(shì)，大大減少了whatif分析合并中由于多表連接產(chǎn)生的大量開(kāi)銷。

　　3.2what-if分析的并行執(zhí)行

　　what-if分析的OLAP查詢中，涉及大量的聚集操作，針對(duì)可分布式執(zhí)行的聚集函數(shù)，可將聚查詢分布到不同計(jì)算節(jié)點(diǎn)進(jìn)行聚集計(jì)算，并將各個(gè)節(jié)點(diǎn)的聚集計(jì)算結(jié)果進(jìn)行合并輸出。因此whatif分析的OLAP并行查詢可分為兩階段：一是提交查詢到多個(gè)子查詢節(jié)點(diǎn)上進(jìn)行并行執(zhí)行；二是合并查詢結(jié)果，然后輸出合并后的最終結(jié)果。

　　圖3為what-if分析中并行執(zhí)行OLAP查詢的計(jì)算過(guò)程。在此并行查詢處理中，各處理節(jié)點(diǎn)均將查詢結(jié)果返給OLAP中間服務(wù)器，并計(jì)算出最終結(jié)果。

　　根據(jù)3.1節(jié)中數(shù)據(jù)劃分方法，每個(gè)屬性將被分布在不同的節(jié)點(diǎn)上。例如，當(dāng)有n個(gè)節(jié)點(diǎn)時(shí)，針對(duì)屬性A，則有A=A1∪A2…∪An，在圖3的分布式聚集函數(shù)計(jì)算過(guò)程中，最終的計(jì)算結(jié)果是1~n個(gè)節(jié)點(diǎn)的計(jì)算結(jié)果的總和。在本文中，實(shí)現(xiàn)了常用的分布式聚集函數(shù)如SUM、COUNT、MAX以及MIN等的分布式聚集運(yùn)算，其計(jì)算公式分別表示如下：

　　SUM(A)=SUM(SUM(A1) ,…,SUM(An))

　　COUNT(A)=COUNT(COUNT(A1),…,COUNT(An))

　　MAX(A)= MAX(MAX(A1) ,…,MAX(An))

　　MIN(A)= MIN(MIN(A1) ,…,MIN(An))

　　在分布式并行執(zhí)行中，可以利用各計(jì)算節(jié)點(diǎn)的計(jì)算能力及I/O處理能力提高what-if分析的OLAP查詢效率，但與此同時(shí)，若將聚集函數(shù)轉(zhuǎn)換為可分布式計(jì)算的聚集函數(shù)時(shí)，額外的通信代價(jià)相應(yīng)地也會(huì)增加。因此，在利用各節(jié)點(diǎn)處理能力的同時(shí)需要考慮其網(wǎng)絡(luò)開(kāi)銷，換句話說(shuō)，隨著節(jié)點(diǎn)在一定范圍的增加，查詢效率會(huì)有相應(yīng)的提升，但當(dāng)子節(jié)點(diǎn)過(guò)多時(shí)，隨著網(wǎng)絡(luò)開(kāi)銷的逐漸增加其查詢效率將會(huì)受到一定的影響。

　　因此，本文一方面適當(dāng)增加計(jì)算節(jié)點(diǎn)提高whatif分析的OLAP查詢效率，另一方面為防止網(wǎng)絡(luò)開(kāi)銷的過(guò)度增加而控制計(jì)算節(jié)點(diǎn)數(shù)量。通過(guò)此方法，可以有效提高OLAP中所涉及分布式聚集操作。

4實(shí)驗(yàn)及結(jié)果

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

　　本文實(shí)驗(yàn)包括兩部分，一是對(duì)2.2節(jié)中的三種連接算法實(shí)現(xiàn)what-if分析中基表與delta表合并的性能測(cè)試；二是對(duì)what-if分析中4種常用的分布式聚集函數(shù)的測(cè)試。

　　測(cè)試實(shí)驗(yàn)為分布式并行處理，分配一個(gè)主節(jié)點(diǎn)，數(shù)據(jù)節(jié)點(diǎn)數(shù)分別為1、2、3、4、5，節(jié)點(diǎn)與物理機(jī)的分配方式分為兩種：一是主節(jié)點(diǎn)為單獨(dú)的物理機(jī)，將所有的數(shù)據(jù)節(jié)點(diǎn)放在同一物理機(jī)上；二是主節(jié)點(diǎn)和每個(gè)數(shù)據(jù)節(jié)點(diǎn)均放在不同的物理機(jī)上。所有物理機(jī)的配置相同，均為Centos6.4 64 bit的操作系統(tǒng)，16 GB內(nèi)存，100 GB硬盤(pán)，Greenplum 4.3.5.2為底層數(shù)據(jù)庫(kù)。

　　在測(cè)試中，F(xiàn)oodmart數(shù)據(jù)集作為測(cè)試數(shù)據(jù)，事實(shí)表sales_fact的記錄數(shù)為80millions，sales_fact_virtual的記錄數(shù)占sales_fact的4%，并設(shè)置sales_fact_virtual中I類型、U類型、D類型占sales_fact_virtual總記錄數(shù)的30%、40%和30%。

　　4.2實(shí)驗(yàn)結(jié)果

　　根據(jù)Segments節(jié)點(diǎn)與物理機(jī)的分配，分別測(cè)試whatif分析的3種實(shí)現(xiàn)算法的性能變化情況，圖4和圖5縱坐標(biāo)均表示whatif分析中基表與delta表合并的時(shí)間。

　　圖4為所有的Segments節(jié)點(diǎn)在同一物理機(jī)時(shí)3種連接算法的執(zhí)行結(jié)果?？梢钥闯?，隨著節(jié)點(diǎn)的增加，查詢響應(yīng)時(shí)間逐漸縮減。

　　圖5為所有的Segments節(jié)點(diǎn)在不同的物理機(jī)上，與圖4類似，其性能隨節(jié)點(diǎn)增加而增加。比較圖4與圖5中的查詢響應(yīng)時(shí)間，Segments位于不同的物理機(jī)上時(shí)，whatif分析的響應(yīng)時(shí)間略顯優(yōu)勢(shì)。主要是因?yàn)樵诓煌锢頇C(jī)上，其CPU和I/O處理能力更強(qiáng)，但同時(shí)也增加了更多的網(wǎng)絡(luò)開(kāi)銷。

　　兩種結(jié)果均表明，當(dāng)數(shù)據(jù)節(jié)點(diǎn)為1時(shí)，其合并時(shí)間最高，約是數(shù)據(jù)節(jié)點(diǎn)為5時(shí)的5倍。

　　如圖6為4種分布式聚集函數(shù)的并行化執(zhí)行結(jié)果，圖中的Segments放在相同配置的物理機(jī)上，當(dāng)Segments節(jié)點(diǎn)數(shù)為5時(shí)，聚集函數(shù)所消耗的時(shí)間是單節(jié)點(diǎn)所消耗時(shí)間的1/4。由此可知，分布式并行執(zhí)行能有效提高聚集運(yùn)算的查詢效率，有利于whatif分析中執(zhí)行的OLAP查詢性能的提高，使whatif分析效率進(jìn)一步提升。

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

　　分布式并行處理以其并行執(zhí)行的優(yōu)勢(shì)，廣泛應(yīng)用于數(shù)據(jù)分析領(lǐng)域，可提升數(shù)據(jù)分析性能。文中詳細(xì)介紹使用連接算法實(shí)現(xiàn)whatif分析，并分析算法中影響其性能的瓶頸，利用分布式并行執(zhí)行策略，即在whatif分析的存儲(chǔ)層使用分布式存儲(chǔ)架構(gòu)，通過(guò)并行查詢處理機(jī)制，實(shí)現(xiàn)多連接查詢的并行化，以達(dá)到快速查詢的目的，從而提高whatif分析效率。最后，利用分布式并行執(zhí)行策略對(duì)whatif分析中常用的SUM、COUNT、MAX、MIN等操作進(jìn)行性能測(cè)試。

　　參考文獻(xiàn)

　?。?］ Zhang Yansong, Zhang Yu, Xiao Yanqin， et al. The tradeoff of delta table merging and rewriting algorithms in whatif analysis application［C］. In Proc. APWeb/WAIM ′09, 2009:260272.

　?。?］ Xu Huan, Luo Hao, He Jieyue. Whatif query processing policy for big data in OLAP system［C］. In Proc. CBD ′13, 2013:110116.

　?。?］ HERODOTOU H, BABU S. Profiling, whatif analysis, and cost based optimization of MapReduce programs［C］.Proc. of the VLDB Endowment, 2011:11111122.

　?。?］ SINGH R, SHENOY P, NATU M, et al. Analytical modeling for whatif analysis in complex cloud computing applications［C］. SIGMETRICS Perform, 2013:5362.

　?。?］ 金樹(shù)東，馮玉才. 并行數(shù)據(jù)庫(kù)系統(tǒng)原型PARO［J］.計(jì)算機(jī)科學(xué),1997,24(3):4145.

　　［6］ 張延松，張宇，黃偉,等.分布式聚集函數(shù)支持的內(nèi)存OLAP并行查詢處理技術(shù)［J］.軟件學(xué)報(bào)，2009(20):165175.