郑雪梅1,2 ，陈梅1,2 ，李晖1,2

　　（1.贵州大学 计算机科学与技术学院，贵州 贵阳 550025;2.贵州大学 贵州省先进计算与医疗信息服务工程实验室，贵州 贵阳 550025)

　摘要：根据基于OLAP的what-if分析的查询特点，使用分布式并行处理技术解决whatif分析性能较低的问题。以星座模型为基础的whatif分析中，将多维聚集查询分布到不同计算节点进行聚集计算，然后将各个计算节点的聚集计算结果合并输出。该方法根据基于OLAP的whatif分析中其维表远远小于事实表的特性，将事实表中的记录进行水平分片，充分利用各节点计算和I/O处理能力，以解决OLAP查询中计算密集型及I/O消耗过大的难题。在该方法中，随着计算节点数目的增加，其查询时间随之减少，有效地提升了分析效率。

　关键词：OLAP; what-if分析;分布式并行处理

0引言

　　what-if分析是决策者对多种决策方案进行预测或评估时的常用手段，通常以多种形式应用于不同的应用场景，尤其在决策系统中发挥重要作用。简单地说，whatif分析就是以数据仓库中历史数据为基础数据的假设分析，决策者根据决策目标制定一系列假设场景，通过对已有数据的假设分析得到假设场景下的商业数据变化情况。

　　近年来，随着数据仓库中数据的不断膨胀，数据量从TB级增长到PB级甚至EB级别，决策者在海量的数据中挖掘价值，以便更快更准地捕获商机，在很大程度上还需要借助whatif分析工具的应用。因此，基于OLAP的whatif分析一直受到很多学者的关注，但由于whatif分析自身的复杂性，至今未得到广泛应用。在假设分析时通常需要更改Cube结构或修改Cube数据，这些操作均涉及到Cube重计算，花费时间较长，限制了whatif分析的能力。

　　随着大规模并行处理关系数据库的发展，如Vertica、微软的SQL Server并行数据仓库以及Greenplum数据仓库等的使用，使高效的并行查询处理及数据分析成为可能。因此，本文结合基于OLAP的whatif分析的特点，与分布式并行处理技术相结合，可以有效提高查询效率，解决决策者面临分析效率低的问题。

1相关研究工作

　　whatif分析的概念早已提出，由于其复杂性未得到广泛应用，但是对其研究一直在进行中。参考文献［1］中提出基于Delta表的whatif分析，通过预处理方法提高whatif分析效率，更改工作内容均是在内存数据库中实现，而不是在基于磁盘的关系型数据库中实现，其性能未得到明显提升。参考文献［2］在参考文献［1］的基础上，利用并行计算模型MapReduce实现whatif分析，其性能有一定的提升。随着whatif分析的研究，参考文献［34］分别将whatif分析应用于MapReduce的调优及复杂云数据中心的资源分配。参考文献［5］详细介绍了分布式并行处理整体方案。参考文献［6］提出了内存数据库中利用分布式并行处理技术实现OLAP并行操作的方案。本文中的whatif分析使用分布式并行处理技术，利用并行处理机制提升whatif分析性能。

2what-if分析

　　本节主要以OLAP模型中的星座模型为例，详细介绍whatif分析中的基础概念及实现方法，并分析其实现过程中存在的问题及拟解决方法。

　2.1基于OLAP的what-if分析

　　基于OLAP的whatif分析实质是基于假设场景的OLAP查询。在假设数据生成后，生成新的Cube，Cube通常有星型、星座和雪花等OLAP模型；基于新的Cube可以执行相应的OLAP操作，如Rollup。图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用于存储数据库中的历史数据，在whatif分析中称之为基表；sales_fact_virtual是与sales_fact结构相似的另一个事实表，叫delta表，用于存储假设数据，这类的假设分析是基于delta表的whatif分析。由事实表可知，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操作。下节将介绍使用分布式并行处理来提高whatif分析的整体效率。

3分布式并行执行

　　3.1分布式并行处理

　　基于Sharednothing结构的分布式并行数据库具有较好的可扩展性，图2为本文使用的分布式并行数据库集群架构，整个集群由多个数据节点（Segment Host）和控制节点（Master Host）组成。Master Host主要负责与客户端的通信、对SQL进行分析以及生成执行计划并分发到每个Segment上执行，最后将汇总结果反馈给客户端；数据节点负责数据的存储、存取以及执行Master分发的SQL语句，在每个数据节点上可以允许有多个数据库。同时，各个节点之间的信息交互通过节点互联网络来实现。

　　分布式并行处理数据库集群架构中，数据划分方法对其并行处理的性能影响很大，大多采用的是哈希划分法和范围划分法。文本中即采用了Hash划分方式将数据分布到各个节点上。其划分过程为：当数据存入数据库时进行数据划分处理，即根据表中的某一个或几个字段的哈希值分布到每个节点。

　　在涉及连接操作运算的查询中，利用分布式并行处理数据库对查询操作并行化，可以充分利用系统中所有的处理器和I/O处理能力，从而缩短查询响应时间。利用分布式并行处理数据库的优势，大大减少了whatif分析合并中由于多表连接产生的大量开销。

　3.2what-if分析的并行执行

　　what-if分析的OLAP查询中，涉及大量的聚集操作，针对可分布式执行的聚集函数，可将聚查询分布到不同计算节点进行聚集计算，并将各个节点的聚集计算结果进行合并输出。因此whatif分析的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查询效率，但与此同时，若将聚集函数转换为可分布式计算的聚集函数时，额外的通信代价相应地也会增加。因此，在利用各节点处理能力的同时需要考虑其网络开销，换句话说，随着节点在一定范围的增加，查询效率会有相应的提升，但当子节点过多时，随着网络开销的逐渐增加其查询效率将会受到一定的影响。

　　因此，本文一方面适当增加计算节点提高whatif分析的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节点与物理机的分配，分别测试whatif分析的3种实现算法的性能变化情况，图4和图5纵坐标均表示whatif分析中基表与delta表合并的时间。

　　图4为所有的Segments节点在同一物理机时3种连接算法的执行结果。可以看出，随着节点的增加，查询响应时间逐渐缩减。

　　图5为所有的Segments节点在不同的物理机上，与图4类似，其性能随节点增加而增加。比较图4与图5中的查询响应时间，Segments位于不同的物理机上时，whatif分析的响应时间略显优势。主要是因为在不同物理机上，其CPU和I/O处理能力更强，但同时也增加了更多的网络开销。

　　两种结果均表明，当数据节点为1时，其合并时间最高，约是数据节点为5时的5倍。

　　如图6为4种分布式聚集函数的并行化执行结果，图中的Segments放在相同配置的物理机上，当Segments节点数为5时，聚集函数所消耗的时间是单节点所消耗时间的1/4。由此可知，分布式并行执行能有效提高聚集运算的查询效率，有利于whatif分析中执行的OLAP查询性能的提高，使whatif分析效率进一步提升。

5结束语

　　分布式并行处理以其并行执行的优势，广泛应用于数据分析领域，可提升数据分析性能。文中详细介绍使用连接算法实现whatif分析，并分析算法中影响其性能的瓶颈，利用分布式并行执行策略，即在whatif分析的存储层使用分布式存储架构，通过并行查询处理机制，实现多连接查询的并行化，以达到快速查询的目的，从而提高whatif分析效率。最后，利用分布式并行执行策略对whatif分析中常用的SUM、COUNT、MAX、MIN等操作进行性能测试。

　　参考文献

　　［1］ 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.

　　［2］ 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.

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

　　［4］ 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.

　　［5］ 金树东，冯玉才. 并行数据库系统原型PARO［J］.计算机科学,1997,24(3):4145.

　　［6］ 张延松，张宇，黄伟,等.分布式聚集函数支持的内存OLAP并行查询处理技术［J］.软件学报，2009(20):165175.