鄭雪梅1,2 ，陳梅1,2 ，李暉1,2
（1.貴州大學 計算機科學與技術學院，貴州 貴陽 550025;2.貴州大學 貴州省先進計算與醫療信息服務工程實驗室，貴州 貴陽 550025)
摘要：根據基于OLAP的what-if分析的查詢特點，使用分布式并行處理技術解決whatif分析性能較低的問題。以星座模型為基礎的whatif分析中，將多維聚集查詢分布到不同計算節點進行聚集計算，然后將各個計算節點的聚集計算結果合并輸出。該方法根據基于OLAP的whatif分析中其維表遠遠小于事實表的特性，將事實表中的記錄進行水平分片，充分利用各節點計算和I/O處理能力，以解決OLAP查詢中計算密集型及I/O消耗過大的難題。在該方法中，隨著計算節點數目的增加，其查詢時間隨之減少，有效地提升了分析效率。
關鍵詞：OLAP; what-if分析;分布式并行處理
0引言
what-if分析是決策者對多種決策方案進行預測或評估時的常用手段，通常以多種形式應用于不同的應用場景，尤其在決策系統中發揮重要作用。簡單地說，whatif分析就是以數據倉庫中歷史數據為基礎數據的假設分析，決策者根據決策目標制定一系列假設場景，通過對已有數據的假設分析得到假設場景下的商業數據變化情況。
近年來，隨著數據倉庫中數據的不斷膨脹，數據量從TB級增長到PB級甚至EB級別，決策者在海量的數據中挖掘價值，以便更快更準地捕獲商機，在很大程度上還需要借助whatif分析工具的應用。因此，基于OLAP的whatif分析一直受到很多學者的關注，但由于whatif分析自身的復雜性，至今未得到廣泛應用。在假設分析時通常需要更改Cube結構或修改Cube數據，這些操作均涉及到Cube重計算，花費時間較長，限制了whatif分析的能力。
隨著大規模并行處理關系數據庫的發展，如Vertica、微軟的SQL Server并行數據倉庫以及Greenplum數據倉庫等的使用，使高效的并行查詢處理及數據分析成為可能。因此，本文結合基于OLAP的whatif分析的特點，與分布式并行處理技術相結合，可以有效提高查詢效率，解決決策者面臨分析效率低的問題。
1相關研究工作
whatif分析的概念早已提出，由于其復雜性未得到廣泛應用，但是對其研究一直在進行中。參考文獻［1］中提出基于Delta表的whatif分析，通過預處理方法提高whatif分析效率，更改工作內容均是在內存數據庫中實現，而不是在基于磁盤的關系型數據庫中實現，其性能未得到明顯提升。參考文獻［2］在參考文獻［1］的基礎上，利用并行計算模型MapReduce實現whatif分析，其性能有一定的提升。隨著whatif分析的研究，參考文獻［34］分別將whatif分析應用于MapReduce的調優及復雜云數據中心的資源分配。參考文獻［5］詳細介紹了分布式并行處理整體方案。參考文獻［6］提出了內存數據庫中利用分布式并行處理技術實現OLAP并行操作的方案。本文中的whatif分析使用分布式并行處理技術，利用并行處理機制提升whatif分析性能。
2what-if分析
本節主要以OLAP模型中的星座模型為例，詳細介紹whatif分析中的基礎概念及實現方法，并分析其實現過程中存在的問題及擬解決方法。
2.1基于OLAP的what-if分析
基于OLAP的whatif分析實質是基于假設場景的OLAP查詢。在假設數據生成后，生成新的Cube，Cube通常有星型、星座和雪花等OLAP模型；基于新的Cube可以執行相應的OLAP操作，如Rollup。圖1為本文使用Foodmart數據的OLAP模型。
圖1中有2個事實表和6個維表。其中，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)為兩個事實表。
sales_fact用于存儲數據庫中的歷史數據，在whatif分析中稱之為基表；sales_fact_virtual是與sales_fact結構相似的另一個事實表，叫delta表，用于存儲假設數據，這類的假設分析是基于delta表的whatif分析。由事實表可知，delta表是在基表的基礎上增加了多個字段，如wbversion和sign，wbversion表示版本號，sign為更新類型，其更新類型主要有插入(I)、更新(U)和刪除(D)三類，分別用1、0、-1值來表示。store_sales為度量值，其余均為維度值。
2.2what-if分析實現
本節主要介紹基于delta表的what-if分析的實現過程。首先，根據假設場景將假設數據存儲到delta表中；其次，將delta表與基表合并生成新的Cube，此步驟稱之為假設更新，也叫what-if更新；最后，基于新生成的Cube執行OLAP查詢操作。
對于基表與delta表的合并，常用的方法是通過等值連接、左連接和全連接等操作來實現。下面是依據2.1節中的OLAP模型通過使用連接操作來實現what-if分析。
在連接算法中，首先排除基表中受delta表D和U類更新影響的記錄，然后再與delta表中U類型和I類型的記錄合并。三種算法具體實現如下：
算法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；
通過連接操作執行假設更新后得到新的Cube，在基于Cube的OLAP查詢中，其OLAP查詢結果通常為group by 和order by所得的聚集結果值，涉及操作有MAX、MIN、SUM、COUNT等分布式聚集運算等。
綜上所述，在what-if分析的實現過程中，關鍵問題是如何高效地合并基表和delta表并執行OLAP操作。下節將介紹使用分布式并行處理來提高whatif分析的整體效率。
3分布式并行執行
3.1分布式并行處理
基于Sharednothing結構的分布式并行數據庫具有較好的可擴展性，圖2為本文使用的分布式并行數據庫集群架構，整個集群由多個數據節點（Segment Host）和控制節點（Master Host）組成。Master Host主要負責與客戶端的通信、對SQL進行分析以及生成執行計劃并分發到每個Segment上執行，最后將匯總結果反饋給客戶端；數據節點負責數據的存儲、存取以及執行Master分發的SQL語句，在每個數據節點上可以允許有多個數據庫。同時，各個節點之間的信息交互通過節點互聯網絡來實現。
分布式并行處理數據庫集群架構中，數據劃分方法對其并行處理的性能影響很大，大多采用的是哈希劃分法和范圍劃分法。文本中即采用了Hash劃分方式將數據分布到各個節點上。其劃分過程為：當數據存入數據庫時進行數據劃分處理，即根據表中的某一個或幾個字段的哈希值分布到每個節點。
在涉及連接操作運算的查詢中，利用分布式并行處理數據庫對查詢操作并行化，可以充分利用系統中所有的處理器和I/O處理能力，從而縮短查詢響應時間。利用分布式并行處理數據庫的優勢，大大減少了whatif分析合并中由于多表連接產生的大量開銷。
3.2what-if分析的并行執行
what-if分析的OLAP查詢中，涉及大量的聚集操作，針對可分布式執行的聚集函數，可將聚查詢分布到不同計算節點進行聚集計算，并將各個節點的聚集計算結果進行合并輸出。因此whatif分析的OLAP并行查詢可分為兩階段：一是提交查詢到多個子查詢節點上進行并行執行；二是合并查詢結果，然后輸出合并后的最終結果。
圖3為what-if分析中并行執行OLAP查詢的計算過程。在此并行查詢處理中，各處理節點均將查詢結果返給OLAP中間服務器，并計算出最終結果。
根據3.1節中數據劃分方法，每個屬性將被分布在不同的節點上。例如，當有n個節點時，針對屬性A，則有A=A1∪A2…∪An，在圖3的分布式聚集函數計算過程中，最終的計算結果是1~n個節點的計算結果的總和。在本文中，實現了常用的分布式聚集函數如SUM、COUNT、MAX以及MIN等的分布式聚集運算，其計算公式分別表示如下：
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))
在分布式并行執行中，可以利用各計算節點的計算能力及I/O處理能力提高what-if分析的OLAP查詢效率，但與此同時，若將聚集函數轉換為可分布式計算的聚集函數時，額外的通信代價相應地也會增加。因此，在利用各節點處理能力的同時需要考慮其網絡開銷，換句話說，隨著節點在一定范圍的增加，查詢效率會有相應的提升，但當子節點過多時，隨著網絡開銷的逐漸增加其查詢效率將會受到一定的影響。
因此，本文一方面適當增加計算節點提高whatif分析的OLAP查詢效率，另一方面為防止網絡開銷的過度增加而控制計算節點數量。通過此方法，可以有效提高OLAP中所涉及分布式聚集操作。
4實驗及結果
4.1實驗環境
本文實驗包括兩部分，一是對2.2節中的三種連接算法實現what-if分析中基表與delta表合并的性能測試；二是對what-if分析中4種常用的分布式聚集函數的測試。
測試實驗為分布式并行處理，分配一個主節點，數據節點數分別為1、2、3、4、5，節點與物理機的分配方式分為兩種：一是主節點為單獨的物理機，將所有的數據節點放在同一物理機上；二是主節點和每個數據節點均放在不同的物理機上。所有物理機的配置相同，均為Centos6.4 64 bit的操作系統，16 GB內存，100 GB硬盤，Greenplum 4.3.5.2為底層數據庫。
在測試中，Foodmart數據集作為測試數據，事實表sales_fact的記錄數為80millions，sales_fact_virtual的記錄數占sales_fact的4%，并設置sales_fact_virtual中I類型、U類型、D類型占sales_fact_virtual總記錄數的30%、40%和30%。
4.2實驗結果
根據Segments節點與物理機的分配，分別測試whatif分析的3種實現算法的性能變化情況，圖4和圖5縱坐標均表示whatif分析中基表與delta表合并的時間。
圖4為所有的Segments節點在同一物理機時3種連接算法的執行結果。可以看出，隨著節點的增加，查詢響應時間逐漸縮減。
圖5為所有的Segments節點在不同的物理機上，與圖4類似，其性能隨節點增加而增加。比較圖4與圖5中的查詢響應時間，Segments位于不同的物理機上時，whatif分析的響應時間略顯優勢。主要是因為在不同物理機上，其CPU和I/O處理能力更強，但同時也增加了更多的網絡開銷。
兩種結果均表明，當數據節點為1時，其合并時間最高，約是數據節點為5時的5倍。
如圖6為4種分布式聚集函數的并行化執行結果，圖中的Segments放在相同配置的物理機上，當Segments節點數為5時，聚集函數所消耗的時間是單節點所消耗時間的1/4。由此可知，分布式并行執行能有效提高聚集運算的查詢效率，有利于whatif分析中執行的OLAP查詢性能的提高，使whatif分析效率進一步提升。
5結束語
分布式并行處理以其并行執行的優勢，廣泛應用于數據分析領域，可提升數據分析性能。文中詳細介紹使用連接算法實現whatif分析，并分析算法中影響其性能的瓶頸，利用分布式并行執行策略，即在whatif分析的存儲層使用分布式存儲架構，通過并行查詢處理機制，實現多連接查詢的并行化，以達到快速查詢的目的，從而提高whatif分析效率。最后，利用分布式并行執行策略對whatif分析中常用的SUM、COUNT、MAX、MIN等操作進行性能測試。
參考文獻
［1］ Zhang Yansong, Zhang Yu, Xiao Yanqin， et al. The tradeoff of delta table merging and rewriting algorithms in whatif analysis application［C］. In Proc. APWeb/WAIM ′09, 2009:260272.
［2］ Xu Huan, Luo Hao, He Jieyue. Whatif query processing policy for big data in OLAP system［C］. In Proc. CBD ′13, 2013:110116.
［3］ HERODOTOU H, BABU S. Profiling, whatif analysis, and cost based optimization of MapReduce programs［C］.Proc. of the VLDB Endowment, 2011:11111122.
［4］ SINGH R, SHENOY P, NATU M, et al. Analytical modeling for whatif analysis in complex cloud computing applications［C］. SIGMETRICS Perform, 2013:5362.
［5］ 金樹東，馮玉才. 并行數據庫系統原型PARO［J］.計算機科學,1997,24(3):4145.
［6］ 張延松，張宇，黃偉,等.分布式聚集函數支持的內存OLAP并行查詢處理技術［J］.軟件學報，2009(20):165175.