基于数据分组方法的数据仓库并行预计算和查询（四）

1、基于数据分组方法的数据仓库并行预计算和查询（四）        7.1   数据描述        在实验中，使用了一个来自不同气象站所收集的1985年9月的天气数据Hahn94。它包含了1,015,367个元组，一共20维。在这次实验中，所使用的是它前16维的数据，每个维度的依次如下表所示：维度维度名称维度的势1时间2402天空明亮度23纬度38094经度53595气象站编号70376气象站所处地点17当前天气情况1018云层覆盖总量

2、99低层云数量1010低层云高度1111低层云类型1312中层云类型1413高层云类型1114中层云数量×1002415高层云数量×1002416中层云数量10表7.1     天气数据集7.2   预计算实验 在本实验中，将讨论基于数据分组方法的并行预计算程序对于串行预计算程序在性能上的提高，以及这两种方法在不同规模数据集上进行运算的性能表现。讨论并行查询程序的加速比。在预计算实验中，在单节点环境下和三节点环境下分别对13个不同的数据进行了串行和并行预计算。这13个不同的数据的维度各不相同，从4维到16维，分别是

3、天气数据集20维数据中的前4维到前16维等，元组条数都是1,015,367条。三节点环境下的数据分割采用平均分割，每个节点上收到的元组条数基本上是相等的。在单节点环境下的实验使用串行的预计算程序。统计两个时间：(1)程序进行预计算写入文件的时间。(2)程序运行时间。在三节点环境下的实验使用并行的预计算程序。因为从机不需要等待主机完全读入数据文件便可得到一部分数据进行预计算，使得从机预计算时间和主机读取文件有交叉。因此在此实验中，每台机器都会统计三个时间：（1）主机从开始读取数据文件到数据完全载入内存并发送出去的时间。（2）每台机器进行预计算的时间。（3）每台机器总的运行时间。通过实验发现，刀片

4、服务器的网络效率非常高，在实验中，几乎所有的MPI点对点通信时间都可以在0.2秒之内完成，加上实验中的MPI通信次数比较少，所以MPI通信的时间可以忽略不计。图7.2所示是串行预计算时间和并行平均预计算时间的比值。在4到10维之间时，串行预计算时间一直维持在并行计算时间的2.9倍左右。但在11维或更多维数据时，串行预计算时间的增长率开始大幅超过并行预计算时间，使得并行计算的加速比在11维时达到了理想状态的3倍，并且呈线性增长的趋势。可见，随着数据量的增大，DFS算法性能会相应地下降，而减少元组条数可以继续使得DFS算法保持高性能。图7.1     预计算

5、时间图7.2     预计算加速比图7.3     数据读入时间图7.4     总运行时间图7.5     总运行时间加速比7.3   查询实验     本实验的主要内容是在预计算生成的商立方体基础上，对4至13维的商立方体进行单节点串行和三节点并行点查询实验。讨论并行查询程序相对于单机查询程序在性能上的提高，计算并行查询程序的加速比。首先各个维度都随机地生成了1000条点查询。生成的

6、点查询是从基表中随机抽取出1000条元组，并随机地将元组中的某些属性改为“*”。经观察，串行查询程序与并行查询程序所得到的查询结果是一致的，在本实验中，主要讨论并行查询程序对于串行程序的加速比，因此，查询的具体结果便不再讨论。串行查询与并行查询的程序运行时间如图7.6所示。图7.6     查询程序运行时间图7.7     商立方体单元数图7.8     程序加速比在基于数据分组方法的预计算中，经过预计算的商立方体数据是分布式地存放各台机器上的。对于一条查询语句q，当程序用q

7、在A机器的商立方体中进行查询时，q的覆盖集里面的所有元组在预计算时可能都没有分配到A机器上。在这种情况下，q在A上的查询便会产生巨大的额外开销：首先会从q所在层次h1里的单元中开始查找，在h1找不到的情况下，会继续查找h1的下一层h2。但是由于q在A上是无法命中的，查询程序会一层接着一层地往下扫描下去，直到扫描完最后一层。随机生成的1000条点查询语句是根据基表中的元组生成的，这样在串行查询中，较少会出现语句在某一层未能命中，需要扫描下一层的情况。然而在并行查询中，由于元组的分布性，产生了较多的查询不命中，使得程序必须进行额外的层次扫描，而且这种额外的层次扫描的代价十分巨大。在并行查询中，开销

8、巨大额外的层次扫描使得查询的时间急剧地增加，从而使得程序性能没能达到预期的效果。尽管如此，在三台机器上能够实现缩短一半的时间，并行查询程序的性能还是令人满意的。7.4   小结 由于硬件平台条件的限制，实验最多只能在三个节点上运行，无法进行更多的实验来验证本文提出的基于数据分组的并行预计算和并行查询方法的可扩展性。1         在三个节点上进行的预和查询实验的结果表明，基于数据分组方法的数据仓库并行预计算和查询方法是有效的，它能够有效地提高数据仓库预计算和查询的性能，并得到正确的结果。 第

9、八章  与展望 在数据仓库数据量急剧增长的今天，并行数据仓库技术成为了解决海量数据预计算和存储问题的一种重要的、有效的手段。本文主要研究了一种基于数据分组的并行数据仓库预计算和查询技术，并在串行程序基础上实现了并行预计算和查询的程序。然后通过实验数据来说明该方法的有效性和分析了这种方法的优点和存在的缺陷。8.1    结论 由于实验平台的限制，使得各项实验最多只能在三个节点的环境下运行，无法在更多节点的计算环境下进行实验，研究本文提出方法的可扩展性。通过实验的观察和分析，本文提出的基于数据分组的数据仓库并行预计算和并行查询方法有以下一些优点：(1)

10、60;  该实现方法的并行策略简单，该方法可以经过很少的修改，便可以将很多已经实现的串行程序改为并行程序。使用MPI和C+进行编程，使得程序具有良好的可移植性、面向对象性。(2)   可以更好地适用于大数据量场合。对于串行版本的预计算程序，在对于高维度数据集进行预计算时，随着数据量的增加，性能衰减得很厉害。并行预计算时的性能加速比十分可观，在数据量很大的情况下，甚至可以超过理想加速比。(3) 预计算后生成的商立方体数据以分布式方式存储，在查询时，各台机器都可以同时对立方体数据进行读取，充分利用了各台机器的磁盘I/O带宽。同时本文提出的并行预计算和并行查询方法存在的

11、一些不足：(1)   对于并行查询，查询的效率未能达到理想的加速比。这是由于数据元组的分布性与商立方体的特性所造成的，当查询语句覆盖集中的元组没被分配到某台机器上时，该查询语句在该台机器上的查询操作便无法命中。商立方体的特性使得查询在某一层上界中找不到所覆盖的上界的时候，必须到下一层进行查找，如果一直找不到，便会一直找下去，直到全部都扫描过。查询语句在某台机器上无法命中的后果是会产生很多额外的层次文件扫描操作，这样一层层的扫描操作代价是十分巨大的，但这种情况在数据元组分布式存储的情况下又是无法避免的，这样便使得并行查询程序的加速比未能达到理想状态。(2) 

12、0; 基表元组的映射可以提高预计算和查询的响应效率，但是对于映射这个步骤还不能完全地并行化处理。8.2   未来的改进 对于本文提出的并行预计算和并行查询方法存在的一些不足和缺点，可以存在这样一些补充和改进的地方：(1)   预计算算法还需要做出一些修改以适应立方体分布式存储环境，如聚集操作中的平均操作，除了对该维度量值做平均值计算之外，还应该同时加上计算总和的计算。这样才能保证元组条数的信息不至于丢失，在主进程最终做统计运算的时候才能得到正确的结果。(2)   对于基于顺序查询方法的并行查询，可以预先判断一下是否在该机上命中查询。如

13、果可以预先判断出查询不命中，则可以减少许多额外的层次扫描开销，提高效率。预先的判断应该可以通过扫描本地预计算输入基表里有没有查询语句覆盖集内的元组进行。(3)   改进查询程序的算法。顺序查询是最简单、易行的查询方法，但这种方法的效率确实不高。(4)   改进立方体数据结构，商立方体存在着查询效率不高的问题，对此人们提出了各种基于商立方体的改善型立方体数据结构，如QC-TreeLPZ03和Semi-Closed CubeLW05，基于此类型的立方体结构应该能够改善查询的响应速度。Beo07    B: T

14、he Beowulf Cluster SiteCCS93a     E. Codd, S. Codd, C. Salley. Beyond decision support. Computer World, 27(30): 87-89, 1993CCS93b   E. Codd, S. Codd, C. Salley. Providing OLAP to User-Analysts. PC World, (9), 1993Chen99     陈国良. 并行计算结构·算法·编

15、程. 北京, 高等出版社, 1999Du01       都志辉. 高性能计算并行编程技术MPI并行程序设计. 北京, 清华大学出版社, 2001Fly72      M. Flynn. Some Computer Organizations and Their Effectiveness. IEEE Transactions on Computers, C21(9), 1972GCB+97     J. Gray, S. Chaudhuri,

16、A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow and H. Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals. Journal of Data Mining and Knowledge Discovery, 1(1): 29-53, 1997GGKK03     A. Grama, A. Gupta, G. Karypis,

17、 V. Kumar. Introduction to Parallel Computing (Second Edition). Pearson Education, 2003. 张武, 毛国勇, 程海英 等译. 并行计算导论. 北京, 机械出版社, 2005HPF06    High Performance Fortran ForumInm02    W. H. Inmon. Building the Data Warehouse (Third Edition), John Wiley & Sons, Inc. 2002. 王志海, 林友芳等译. 数据仓库. 北京, 机械工业出版社, 2003LAM07     LAM-MPI Parallel ComputingLPH02     L. Lakshmanan, J. Pei and J.Han. Quotient Cube: How to Summarize the Semantics of a Data