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

论文关键词：数据仓库　并行计算　消息传递接口　商立方体

论文摘要：目前很多数据仓库的原始数据量已经超过了T字节级，在单处理机机器上运行数据量如此庞大的数据仓库是十分困难。因此，并行计算技术对于数据仓库技术的介入是无法避免的，并行计算技术为提高运算能力和存储能力这影响数据仓库性能的两大重要因素提供了技术基础。本文详细介绍了基于数据分组方法的数据仓库并行预计算和查询的方法，其主要思想是将数据仓库基表中的数据进行分割，分发到各台计算机上后，并行地对数据进行预计算，并根据预计算完成后，立方体数据存储的分布性，并行地进行查询。本文首先介绍了数据仓库和并行计算的基本概念，并根据商立方体的特点提出了基于数据分组方法的数据仓库并行预计算和查询的方法。本文对该方法的具体实现进行了描述，并分析了在刀片服务器上运行后得到的各项结果。基于数据分组方法的数据仓库预计算和查询方法的并行策略相对较简单，但在现实应用中，通过实验观察和对实验数据的分析，证明了这种方法是可行的，数据仓库的预计算性能于查询性能都得到了令人满意的提高。

第一章 绪论

随着计算机应用的普及，人们的社会活动已经越来越多地依赖于计算机的使用。人类的各种社会活动，例如商品交易、科学实验都产生了巨大的数据量。这些长年累月积累下来的数据量极为巨大，虽然看似杂乱无章，但是里面却隐含着社会科学和自然科学的各种规律。如何更好地去利用这些数据，从数据中寻找出这些规律来造福社会，是人们面临的另一个重要问题。传统的信息处理方式，如数据库，是以单一的数据为中心的事务处理，它可以让人们在可以接受的时间范围内完成对数据的各种事务操作，但是对于发掘数据中的规律却是无能为力。为此人们发明了很多新的计算机技术从这些数据中寻找出其隐含的规律，数据仓库便是其中的一种。

为了更好、更快速地执行用户对数据仓库的查询，需要对原始数据集进行预计算。预计算就是将人们会在查询中希望得到的，将很多记录依照其某项属性进行某种聚集操作（和、最大、最小等等）后的结果，进行预先的计算处理。这样便可以提高查询的响应速度，减少响应时间，提高人们数据仓库的利用效率。由于预计算所产生的数据集合必须考虑到每条记录的聚合，所以产生的数据量是原始数据集的数百倍甚至千倍。人们对于预计算的计算量要求也是巨大的。

目前很多数据仓库的原始数据量已经超过了TB级，在单台机器上是根本支持不了数据量如此庞大的数据仓库，因此，并行计算技术的介入是无法避免的，它为提高运算能力和存储能力这两大重要因素提供了技术基础。并行计算是唯一能够处理这么大量信息的计算技术。

本文将研究如何把并行计算技术引入到数据仓库的预计算和查询中，并通过实验来支持这种做法的有效性。希望可以为数据仓库的并行处理技术提供一种新的思路。

1.1　目标

本文的研究目标是提出一种数据仓库并行处理技术，它使用MPI实现，能够在多种平台上运行，能有效地实现立方体预计算加速以及查询加速。

1.2　本文安排

本文的余下部分将如下安排：

第二章是介绍本文研究的相关背景，将描述本文中涉及的关于数据仓库和并行计算的概念。

第三章概括性地介绍了MPI，包括MPI标准发展史，MPI编程中经常使用到的点对点通信原语和通信模式以及MPI程序的基本结构。

第四章将介绍商立方体提出的目的，商立方体的特性，预计算算法以及查询算法。

第五章描述了基于数据分组方法的数据仓库并行预计算和查询方法的基本思路与实现步骤，并对该方法的正确性做了初步的证明。

第六章详细描述了并行预计算程序和并行查询程序的具体实现与工作流程。

第七章通过实验测量的数据来说明本文提出方法的有效性和对于预计算和查询性能的提高。

第八章对本文的工作进行了总结，说明了本文的主要成果和存在的不足，并为进一步的工作进行了展望。

第二章 背景

自计算机发明后，人类文明进入了一个前所未有的高速发展阶段。计算机技术的应用缩短了许多新技术的研发周期，新技术往往意味着更高的生产力、更好的产品和更低的成本。计算机自身也得益于这些新技术，越来越多的商业公司和个人可以负担得起计算机的使用费用，计算机逐渐普及。

随着计算机技术应用的广泛性日益增加、性能不断地提高，加上互联网等革命性技术的出现，人们开始进入信息化社会，信息已经成为人类社会不可或缺的重要资源。社会信息化使得社会活动如：商业交易，科学实验，数据统计等所产生的数据急剧地增长，而在这些数量巨大，看似杂乱无章的数据中，隐藏着社会活动和自然科学的规律。例如人们的购买习惯、DNA的作用。分析数据，学习其中的规律成了人们迫切的目标。但是，数据的数量级已经远远地超过了人脑所能处理的范围，因此，人们只能将希望寄托在计算机上。

2.1 数据仓库

面对爆炸性膨胀的数据和不断提升的应用要求，数据库技术也在不断地提高着数据库应用的作用和价值。传统的数据库技术主要擅长于提供以数据为中心，通过数据库对一个或一组数据记录进行查询和修改等的面向具体、特定应用的服务，它可以满足响应时间、数据可靠性和完整性等方面的要求。这些传统的事务处理系统已经比较成熟，在企业和组织中应用也十分普遍，随着各种组织的日常事务处理的信息化，数据分析和决策支持应用成了必然的趋势。如何有效地利用历史数据为决策分析做支持，是近年来数据处理研究领域的热点。

对数据进行分析处理的要求使得传统的数据库技术不能满足要求，为了解决这个问题，Inmon[Inm02]提出了数据仓库的概念。他对于数据仓库是这样定义的：数据仓库就是一个用以更好地支持企业或组织的决策分析处理、面向主题的、集成的、不可更新的、随时间不断变化的数据集合。数据仓库有以下特点：

面向主题（Subject-oriented）：数据仓库中的数据是面向主题进行组织的。

集成（Integrated）：数据仓库中通常集成了多个异质数据源的数据。在集成过程中，需要对数据进行清洗、转换以保证数据的一致性。

稳定（Nonvolatile）：数据仓库中的数据是反映一段相对长时间内历史数据的内容，是不同时间数据库快照的集合，以及基于这种快照进行统计、综合和重组的导出数据。所设计的操作主要是数据查询，一般不会进行修改操作。

随时间变化（Time-variant）：数据仓库随时间变化不断增加新的内容，删去旧的内容。

数据仓库技术在过去的一段时间内发展迅速，已经成功地应用到电信、银行、保险等行业。随着企业信息化的不断深入，这种发展还会持续。

2.1.1 联机分析处理与数据立方体

为了让决策支持人员更好地去分析处理数据仓库中的海量数据，E. Codd于1993年提出了联机分析处理（OLAP: On-Line Analytical Processing）的概念[CCS93a, CCS93b]。OLAP工具通过对信息的多个角度（维）进行快速、一致、稳定的交互访问，决策支持人员可以深入地进行观察。OLAP工具是为了满足更高效地进行多维分析的需求而产生的，其主要功能是根据用户所选择的分析角度，事先计算好一些辅助结构，以便在查询对能够抽取到所需要的记录。

OLAP系统中的数据通常会以一个多维的结构模型表现出来。表2.1是一个简单的销售数据仓库的基表（base table），基表中的一条记录称为元组（tuple），该基表中一条元组有三个属性：时间、产品名称和地点，在这里被称为维度（dimension），这些维用来表示和区分开不同的数据。销量属性是一个数值类型的度量值（measure），是人们想要去分析的数据。维度通常也会分层次（hierarchy），例如时间维度可能会分为年、月、日、季度等层次。

地点

产品名称

时间

销量

广州(GZ)

篮球(B)

2007.5(M1)

20

广州(GZ)

足球(F)

2007.6(M2)

15

深圳(SZ)

篮球(B)

2007.5(M1)

25

表2.1销售数据仓库的基表

数据立方体（Data Cube）是由Gray等人提出[GCB+97]。它是对所有维度的所有可能结合，根据不同聚集粒度进行group-by操作而产生的一个概括化数据集合。每一个group-by操作都与一个单元（cells）的集合相关联，数据立方体关于表2.1的所有单元都在表2.2中列出，在表中，“*”表示在这一维度中，它可以匹配到这个维度值域中的任何一个值。

上卷（roll-up）和下钻（drill-down）是数据立方体中的两种基本语义关系。一个较高聚集层次的单元可以下钻到一个较低聚集层次的单元，如：（GZ, *, M1）下钻到(GZ, B, M1)。一个较低聚集层次的单元可以上卷到一个较高聚集层次的单元，如：（SZ, B, M1）上卷到（*, B, *）。一个立方体中的所有单元间的上卷/下钻关系构成了一个网格结构。图2.1中表现出了表2.2中的立方体网格。

地点

产品名称

时间

总和（销量）

GZ

B

M1

20

GZ

F

M2

15

SZ

B

M1

25

GZ

B

*

20

GZ

*

M1

20

*

B

M1

45

…

…

…

…

SZ

*

*

25

*

F

*

15

*

*

M1

45

*

*

*

60

表2.2 数据立方体中的单元

SHAPE \* MERGEFORMAT

图2.1 数据立方体网格

2.2 并行计算

大规模科学与工程计算应用使得人们对计算机性能要求不断提高。例如天气预报、空间模拟、石油勘探等科学计算对计算机的性能要求可以说是无穷无尽的。单台作业的计算机是根本无法满足这种计算需求的，因此人们便开始尝试应用新技术使得多台单独作业的计算机可以协调地共同进行工作，并行计算机便开始逐步走入人们的视野。

并行计算是伴随着并行计算机的出现，在近三十年来迅速发展的一门交叉学科，是指在并行计算机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加快求解速度，或者提高求解应用问题规模的目的[ZCML06]。并行计算必须具备三个基本条件：

（1）并行计算机。并行计算机至少浩瀚两台或两台以上处理机，这些处理机通过互联网络相互连接，互相通信。

（2）应用问题必须具有并行度。应用可以分解为多个子任务，并且这些子任务可以并行地执行。

（3）并行编程。在并行计算机提供的并行编程环境上，具体实现并行算法。

2.2.1 并行编程模式

编程模式是程序员和计算机之间的界面，它是建立在计算机体系结构之上的程序的抽象，它定义了程序的设计与其实现之间的接口。在并行计算机发展的历史过程中，人们提出过许多适合不同并行体系结构的编程模式[ST98]，经过时间的淘汰，目前比较流行的并行编程模式基本上趋向于以下三种[Chen99, Du01, ZCML06]：

消息传递模式：程序的执行分为多个进程，用户需要显式地为每个进程分配数据和指令。进程都在自己的私有空间中运行，显式地通过发送和接收消息进行交互。有同步通信和异步通信两种方式。消息传递模式为程序员提供了更灵活的控制手段和表达并行的方法，因此消息传递并行程序往往能达到高的执行效率。但由于程序员需要显式地指定进程间的信息交换、协调和控制，编写基于消息传递模式的并行计算程序对于程序员的能力要求比较高。尽管如此，消息传递仍然是目前最常用的并行编程模式。MPI[MPI03a, MPI03b]和并行虚拟机[PVM07]是其中两种广泛使用的消息传递编程标准库。

共享存储模式：程序是由运行在一个公共地址空间的一组进程所组成。用户无需进行数据分配，每个进程相对独立地运行，进程间的通信通过存放在公共存储器中的共享变量进行。所以保持变量操作的一致性和同步性是使用这种编程模式时必须考虑的关键问题。基于该模式通过手工或编译器将串行程序并行化，相对比基于消息传递模式更容易，对程序员要求也相对较低。目前使用较多的共享存储模式的实现有IEEE标准委员会的多线程接口[PTP06]和OpenMP标准委员会的OpenMP[OMP07]。

数据并行模式：程序所处理的数据被划分为多个小块，分配到系统中的各个处理单元上，每个处理单元执行相同的程序，不需要显示同步。数据并行模式的实现层次较高，一般由编译器实现，程序员只需指明怎样的并行操作和操作的对象即可。高性能Fortran[HPF06]是一种使用较多的数据并行语言。

2.2.2 并行计算机体系结构 并行计算机的分类是随着并行计算机的发展而发展的。在并行计算技术发展的不同阶段，各个计算机生产厂商发明了各种各样把多个处理器（处理单元）整合在一起的方法，从而使得系统的整体计算能力有所提高。这些技术经过不断地发展，逐渐成熟并衍生出技术分支，同时也产生出许多不同的并行计算机体系结构。

描述这些体系结构特征的最常用的方法是Flynn分类法[Fly72]。它根据指令流数目和数据流数目来分类，将计算机分成了4类：SISD、SIMD、MISD和MIMD。其中，属于并行计算机的有：

(1) 单指令多数据流（SIMD）：同一指令被复制成多份，并发地发送给多个处理器，形成多个独立的进程，每个进程都具有自己的数据流（如图2.2所示），具有同步性和确定性。

SHAPE \* MERGEFORMAT SHAPE \* MERGEFORMAT

图2.2 SIMD体系结构

(2) 多指令多数据流（MIMD）：在MIMD系统中，每个处理器都具有自己的指令来操作自己的数据，与其他处理器无关。指令流可以同步或异步地执行，指令流的执行具有确定性和不确定性。如图2.3所示。

SHAPE \* MERGEFORMAT

图2.3 MIMD体系结构

随着技术的发展，曾经风行的SIMD并行计算机已经退出了历史舞台，MIMD体系的并行机已经占据了统治性的地位。目前世界上流行的并行计算机系统基本上都是属于MIMD计算机。

在MIMD的分类中，按照内存访问模型、微处理器和互联网络的不同，并行计算机可分为以下5类[ZCML06]：

(1) 对称多处理共享存储并行计算机（Symmetric Multi-Processing, SMP）:SMP系统中任何处理器都可以直接访问任何存储模块中的存储单元和I/O模块，且各自间的访问延迟、带宽都一样。整个系统只有一个操作系统驻留在共享存储器中，可以动态地分配进程到各个处理器，而且每个进程都是使用共享的数据存储区来完成通信，通信的延迟较低。但是由于各个处理单元之间的耦合程度较高，所以只要总线、存储器或操作系统其中一个出错，便会导致整个系统的崩溃，而且系统的可扩张性较差。支持消息传递、共享存储并行程序设计。

(2) 分布式共享存储并行计算机（Distributed Shared Memory, DSM）：系统以节点为单位，每个节点包含一个或多个CPU，每个CPU有局部的cache。存储在物理上分布，但在逻辑上是统一的内存地址空间。各个节点既可以直接访问本地的局部存储单元，也进行访问其他节点的局部存储单元，但远端访问必须通过高性能互联网络，性能远不如本地访问。DSM系统的可扩展性强，可扩展至数百个节点。支持消息传递、共享存储并行程序设计。

(3) 集群系统（Cluster）：系统由节点构成，每个节点包含2－4个商用处理器，节点内部共享存储。各节点通过交换机连接。当计算机是运行Linux操作系统的PC机时，这类集群则成为Beowulf[Beo07]集群。集群系统只支持消息传递并行程序设计。目前集群系统占据着主流地位，在世界超级计算机500强中，占据了大多数的席位。

(4) 星群系统（Constellation）：系统由节点构成，每个节点是一台SMP或DSM子系统，包含的处理器数量巨大，计算功能十分强大。节点间通过集换机连接，节点间分布存储。各个节点运行专用的操作系统、编译系统和作业管理系统。与集群系统所不同的是，星群系统可以支持消息传递和共享存储两种并行编程模式：在节点间使用消息传递，节点内部则可以使用共享存储模式，这种混合模式充分利用了两种编程模式的特点，因此被认为是最有效率的编程模式。

(5) 大规模并行计算机系统(Massively Parallel Processing, MPP)：由数百个乃至数千个结算节点和I/O节点组成，每个节点相对独立，并拥有一个或多个微处理器。这些节点的局部cache通过局部总线或互联网络与局部内存模块和I/O设备相连接。互联网络与集群互联网络不同，一般采用由多种静态拓扑结构耦合而成的混合拓扑结构，通信延迟和通信带宽明显优于集群系统。每个节点均拥有不同的操作系统，允许用户在某个特定节点上作业。各节点间内存模块相互独立且没有全局内存统一编址。如果要直接访问其他节点的内存则需要有操作系统的支持。MPP支持消息传递或高性能Fortran并行程序设计，但不支持共享存储模式。

各种并行计算机对于消息传递、共享存储、数据并行三种编程模式的支持在表2.3中列出。

SMP

DSM

集群

星群

MPP

消息传递

√

√

√

√

√

共享存储

√

√

X

√

X

数据并行

√

√

X

X

√

表2.3 各种并行计算机对与编程模式的支持

2.3 小结

数据仓库的应用日渐广泛，但是数据量的增长使得OLAP系统的效率逐渐低下和数据立方体的容量呈指数上升。数据立方体的预计算需要大量的计算能力和存储空间，随着并行计算技术的发展，数据仓库将会更多地使用到并行计算技术。并行计算技术带来的不仅仅是计算能力和存储空间上的扩展，并行计算技术对于计算机性能的扩展使得更多更复杂的应用技术得以实现，扩展数据仓库的功能。

第三章 MPI

消息传递是一个广泛应用在并行计算机（特别是分布存储并行机：DSM、集群、星群和MPP）上的模式。自从20世纪80年代以来，经过10余年的发展，很多基于消息传递的应用系统有了长足的进步。由于基于消息传递模式的系统很多都具有效率高、适用性强等优点，所以人们认为通过定义一个核心库程序的语法与语义，将有益于广大用户，将可以在更大范围的机器上有效实现消息传递模式。本章的主要内容是介绍目前最为流行的基于消息传递模式的编程环境：MPI。在以下的章节中会介绍MPI的产生、MPI的实现和关于MPI编程的基本概念。

3.1 MPI的产生 早期的商用并行计算机很多是基于消息传递的，因为它的成本相对于共享存储的机器更低。人们开发了基于消息传递模式的多种不同实现的消息传递程序库，但是这些程序库就像汇编语言一样，每个硬件制造商提供的程序库都与其他的不兼容。这些不同的程序库之间的实质上的差别其实很小，有的只是语法上的不同而已，但是要想将消息传递程序从一个库移植到另一个库中时，程序往往要作出很大程度的修改。由此人们便意识到需要指定一个消息传递程序设计的接口标准，以便并行计算科学的进一步发展，消息传递接口（MPI：Message Passing Interface）便是这个标准的产物。

MPI的标准化开始于1992年4月底，在美国弗吉尼亚州的Williamsburg召开的“分布式存储环境中消息传递标准”的讨论会上[MPI03a]。MPI1.0标准由Dongarra, Hempel, Hey以及Walker在1992年11月提出的初始草案和于1993年2月完成的修订版本所规定。为了促进MPI的发展，MPI论坛（MPI Forum）因此而诞生，负责MPI的完善和维护工作。

MPI-2[MPI03b]是在对原来MPI作了重大扩充基础上，于1997年7月推出的MPI扩展部分，原来的MPI各种版本改称为MPI-1。MPI-2的扩充很多，但最主要的是以下三部分：并行I/O，远程存储访问和动态进程管理。

MPI的标准化是多个组织和个人的努力成果，他们主要是来自美国和欧洲，大约60名来自40个不同组织的工作人员为此付出了辛勤的劳动。这其中包括了并行计算机大多数的并行计算机生产商、大学、政府实验室和工厂的研究人员。他们有Venus (IBM) 、NX/2 (Intel) Express (Parasoft)、 Vertex(nCUBE)、 P4 (ANL)、 PARMACS (ANL)， 还包括Zipcode (MSU)、 Chimp (Edinburgh University)、 PVM (ORNL, UTK, Emory U.) 、Chameleon (ANL)、 PICL (ANL)等。

MPI建立了一套有效的、可移植的、灵活的标准，并已经成为国际上应用最为广泛的并行程序设计平台。MPI可以使用于几乎所有的并行计算环境（共享存储和分布式存储、MPP、Cluster）和多个操作系统（UNIX、WindowsNT、Linux）。

3.2 MPI的特点与实现 如上一小节所述，MPI是一个消息传递模式下并行程序设计的标准规范。在标准的程序设计语言的基础上，加入实现进程间通信的MPI消息传递函数以及其他并行计算环境设置函数，就构成了MPI并行程序设计所依赖的并行编程环境。对于MPI的定义，需要理解以下三个方面[Du01]：

(1) MPI是一个库而不是一门语言。MPI库可以被FORTRAN77/C/Fortran90/C++调用从语法上说它遵守所有对库函数/过程的调用规则和一般的函数/过程没有什么区别。

(2) MPI是一种标准或规范的代表,而不特指某一个对它的具体实现。迄今为止所有的并行计算机制造商都提供对MPI的支持，一个正确的MPI程序，可以不加修改地在所有并行机上运行。

(3) MPI是一种消息传递编程模式并成为这种编程模式的代表和事实上的标准。MPI虽然很庞大，但是它的最终目的是服务于进程间通信这一目标的。

由此可见，MPI是一个标准。就如同世界上其他标准一样，都会出现很多基于同一标准的不同产品，MPI也不例外。很多研究机构或者公司根据MPI的标准和自己的实际情况，编写出了不同的支持MPI程序的编程环境，而这些编程环境在MPI的世界里就被称为MPI实现。目前比较重要的MPI实现有以下两种：

MPICH[MPI07]。MPICH是一种最重要的MPI实现，是目前使用最广泛的免费MPI系统，大部分集群系统上的并行环境是MPICH。它由美国Argonne国家实验室和MSU共同进行维护。支持几乎所有Linux/UNIX以及Windows9x，NT，2000和XP系统。而且每当MPI推出新的版本时，就会有相应的MPICH实现版本。

LAM[LAM07]。由美国Ohio State University开发，主要用于异构的计算机网络计算系统。

3.3 MPI编程的基本概念

一个MPI并行程序由一组进程或线程所组成。这些进程或线程可以运行在相同的机器上，也可以运行在不同的机器上。在MPI中，一个独立参与通信的个体被定义为一个进程。每个进程所运行的代码并不需要是同样的，进程间的通信是通过调用MPI通信原语来完成。在典型情况下，每个进程都是在自己特有的地址空间中运行，尽管有时在SMP上的MPI程序并不如此。MPI程序中的每个进程都有一个序号，用于在进程组（由MPI程序中部分或全部进程所构成的一个集合）中标识该进程，这个序号被称为进程号，取值范围由0开始。

MPI程序中进程间通信是通过通信器（communicator）进行的，通信器提供了进程间通信的基本环境。MPI程序在启动时会自动创建两个通信器：MPI_COMM_WORLD和MPI_COMM_SELF。前者包含程序运行时的所有进程，后者则是由每个进程独自构成、仅包含自己的通信器。在MPI程序中，一个MPI进程由通信器和进程在该通信器中的进程号唯一标识，同一进程可以在不同通信器中有不同的进程号。进程可以通过调用MPI_Comm_rank函数来获得本进程在某指定通信器中的进程号。

3.3.1 MPI的点对点通信

通信器使得进程间可以通过消息或同步操作来完成通信。消息指在进程间进行的一次数据交换，在MPI中，消息一般包含以下一些内容：通信器、源进程、目的进程、消息标签和数据。MPI进程中使用得最频繁，最基本的一种通信模式就是一对进程相互之间进行通信，也就是一个进程发送消息，另一个进程接收消息，这种通信方式在MPI中被称作点对点通信（point to point communication）。MPI有两大类型的点对点通信函数，一种称为阻塞式（blocking），另一种则是非阻塞式（unblocking）。

阻塞式通信：阻塞式函数会等到通信操作实际完成，或者至少通信所涉及的数据已经被MPI环境处理好之后才会返回。如MPI_Send和MPI_Recv，分别是阻塞式的发送和接收函数。MPI_Send函数返回之后，表明消息已经发送完毕或者已经被MPI环境处理完毕，随后对于发送缓冲区的修改不会对已经发出的消息有所影响。而MPI_Recv函数返回后，表明消息已经接收完毕并且可以立即使用。

非阻塞式通信：非阻塞式函数在调用后会立即返回，而实际的消息传递工作由MPI环境在后台执行。非阻塞式函数的命名是在阻塞式函数名的MPI_前缀之后加上一个“I”，如MPI_Isend和MPI_Irecv则是MPI_Send和MPI_Recv的对应非阻塞式通信版本。在调用非阻塞式函数之后，进程可以调用MPI_Wait函数来等待通信操作的完成，或者可以进行其他的计算工作，而不必将CPU时间浪费在通信上，但这时不能对相关的数据缓冲区进行操作。因为当前操作可能会与正在后台进行的通信发生冲突，产生错误使得程序出问题。要检测通信操作是否实际完成，应该调用MPI_Test函数来查询通信操作的完成情况。

在MPI中，对于点对点通信，也存在着4种发送模式。这4种模式的对应函数名称不同，但参数表是一样的，它们之间的差异，存在于它们发送消息的方式和对接收方的状态要求的不同。这4种模式分别是：标准模式、缓冲模式、同步模式和就绪模式。

标准模式：当消息长度小于或等于MPI环境预留的数据缓冲区大小时，MPI环境会将消息复制到缓冲区，然后立即返回。否则会当部分或全部消息发送完成后才返回。标准模式下，发送操作的完成需要与接收方联络。

缓冲模式：MPI环境将消息复制到一个用户提供的缓冲区中，然后就立即返回，消息由MPI环境在后台执行。用户必须确保所提供的缓冲区能够容下将要发送的消息。缓冲模式下的发送操作不需要与接收方联络便可立即完成。

同步模式：同步模式是基于标准模式上，增加了一个要求。它要求确认接收方已经开始接收数据后函数调用才返回。

就绪模式：调用就绪模式发送时必须确保接收方已经正在等待接收该消息，不然就会产生错误。

3.3.2 MPI程序结构 下面是C/C++语言MPI程序的典型结构：

#include "mpi.h"

........

int main(int argc, char *argv[])

{

int myrank, numprocs;

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

MPI_Comm_rank(MPI_COMM_WORLD, &myrank);

......

MPI_Finalize();

......

return 0;

}

表3.1 MPI程序基本结构

C/C++语言的MPI程序必须包含MPI的头文件mpi.h，以获得MPI函数的原型说明和MPI的预定义数据类型和常量。在使用C++作为MPI程序编程语言的时候，在编译程序时可能会遇到以下的出错信息：

“SEEK_SET is #defined but must not be for the C++ binding of MPI”

这个问题是由于stdio.h和MPI C++接口同时都使用了SEEK_SET，SEEK_CUR，SEEK_END这些全局变量，这是MPI-2标准中的一个bug。要解决这个问题，一般会在#include “mpi.h”这句代码前加上以下三句：

#undef SEEK_SET

#undef SEEK_END

#undef SEEK_CUR

MPI_Init函数用于初始化MPI系统环境。该函数应该在调用其他所有MPI函数之前（除了MPI_Initialized）调用，不然MPI环境还没建立，其他函数也无法运行。命令行参数argc和argv可以传递给MPI_Init，因为有时可以通过这些参数将运行进程的相关信息传递给MPI程序。一般来说，调用MPI_Init(0, 0)也是足够的了。

函数MPI_Comm_size和MPI_Comm_rank分别返回指定通信器中的进程数目和本进程的进程号。在这个例子中，使用的通信器是MPI_COMM_WORLD，它包含了所有进程。

MPI_Finalize函数是用来退出MPI系统环境的。调用它之后便不能再调用任何其他的MPI函数了。程序的主体运行部分一般是在MPI_Finalize之前。进程可以通过myrank变量判断自己是哪个进程来执行不同进程所应该做的工作。

3.3.3 MPI编程的主从模式

构成并行程序的进程中有一个主进程（通常是进程0）其余为从进程。主进程与从进程的分工是不同的。主进程的工作一般负责整个并行程序的控制，分配数据和任务给从进程，从进程负责数据的处理和计算工作，同时主进程也可以参与数据的处理和计算工作。

3.4 小结

MPI的一个最重要的特点就是免费和源代码开放，MPI可以被迅速接受和它为自己定下的高效率、方便移植和功能强大三个主要目标密不可分。它采用广为使用的语言FORTRAN和C/C++进行绑定也是它成功的一个重要因素，当然MPI的成功还因为它总结和吸收了前期大量消息传递系统的经验。一个成功的标准是需要大量的实践和艰苦的努力的，MPI就是这种实践和努力的结果。

第四章 商立方体

联机分析处理（OLAP）由于要计算复杂的聚集函数，有很多的查询要从磁盘读取大量的数据，而OLAP的交互特性要求系统能快速地响应查询。为了解决这对矛盾，Gray等人提出了数据立方体（Data Cube）[GCB+97]。数据立方体概括了可能提出的所有的查询类型，并且将查询结果预先计算出来保存到磁盘。在响应查询时，通过查询重写把用户的查询转换为对某一个实例化视图的查询，极大地提高了查询响应速度。

近年来，随着数据仓库应用的广泛，数据仓库的数据量也越来越大，使得数据立方体的数据量也相应地急剧增加。数据立方体存在一个明显的缺陷：由于需要计算多个聚集函数对于所有可聚合属性的集合，数据立方体需要大量的计算和巨大的磁盘存储空间，不能很好地适用于多维度的场合。因此，减少数据立方体所占用的空间成为了一个关键问题。对此，人们纷纷提出了多种数据立方体的数据压缩技术。其中一类是基于数据立方体单元间关系的压缩技术，它们利用这些关系，如上卷、下钻等，通过分析发现单元间能够去除掉的冗余信息。这样，在将这些冗余信息去除掉之后，数据立方体的存储空间得到压缩并且数据立方体元组之间的关系得以保留，这类技术是目前数据立方体压缩存储技术的主流，代表着未来数据立方体压缩存储技术的发展趋势。

Wang等人提出了精简立方体（Condensed Cube）的概念[WLFY02]，它其中有一个关键概念叫“Base Single Tuple（BST）”。它将具有相同BST的数据立方体单元归为同一类，仅仅存储BST和对应的单元集，其他不符合这些条件的元组则按原来的方式存储。通过去除相同BST的数据立方体单元间的冗余信息，精简立方体能够有效地减少数据立方体的数据量。

Y. Sismanis等人提出了一种称为Dwarf的，基于语义压缩方法的立方体结构[SRD02]。它通过识别出立方体结构中具有相同前缀和后缀的语义信息，并去除这两种类型的冗余信息，可以十分显著地缩减数据立方体的存储空间。Dwarf在最好的情况下可以达到1/6000的压缩率。

商立方体（Quotient Cube）的概念由Laks Lakshmanan等提出[LPH02]，主要是为了解决立方体压缩过程中立方体单元间上卷和下钻逻辑关系的丢失问题。在商立方体中，所有的单元被划分为若干类，在同一类中的单元具有相同的聚集值。类的划分不仅仅是满足聚集值相同这个条件，同时也满足一些额外的条件。这些条件的限制，使得商立方体可以保留下数据立方体的语义结构。因此，每个类只需保存下某些能够代表本类中所有单元属性的单元，即可实现数据量的压缩。

4.1 商立方体的分类 商立方体的主要思想是分类，它采用了一种单元分类方法，称为“覆盖”分类法[LPH02]。该方法与聚集函数类型无关，也就是说，数据立方体上的任一单元，无论它的度量值的聚集函数是哪种操作，这个单元都会被商立方体算法划分到同一类中。

假设基表中的一条元组t，在数据立方体网格中，t能够通过某一存在的路径，上卷到单元c，则称c覆盖（cover）t。c的覆盖集（cover set）定义为：c所覆盖的所有基表中的元组。例如，在图2.1中，单元（*, B, M1）的覆盖集是{(GZ, B, M1), (SZ, B, M1)}。

对于单元c和单元d，当c和d的覆盖集是相等的时候，它们被称为覆盖相等。例如，图2.1中的（*, B, M1）和（*, *, M1），它们的覆盖集都是{(GZ, B, M1), (SZ, B, M1)}，因此这两个单元是覆盖相等的。

商立方体的分类方法就是将覆盖相等的单元分为同一类。在同一类单元中，有个上界（upper bound）的概念。上界就是在该类中最小的元素，也就是说，上界是无法下钻到同类单元中其他任何一个单元的。使用覆盖相等方法产生的商立方体分类，每个类有且只有一个上界，且同类的单元具有相同的聚集值[LPZ03]。

表4.1所示是对于图2.1中的数据立方体进行商立方体分类和各类的上界。

类别

类中单元

上界

1

(*,*,*):60

(*,*,*):60

2

(GZ,*,*):35

(GZ,*,*):35

3

(*,*,M1):45, (*,B,*):45, (*,B,M1):45

(*,B,M1):45

4

(*,F,*):15, (*,*,M2):15, (GZ,F,*):15

(GZ,*,M2):15, (*,F,M2):15, (GZ,F,M2):15

(GZ,F,M2);15

5

(GZ,B,*):20, (GZ,*,M1):20, (GZ,B,M1):20

(GZ,B,M1):20

6

(SZ,*,*):25, (SZ,*,M1):25, (SZ,B,*):25, (SZ,B,M1):25

(SZ,B,M1):25

表4.1 商立方体分类和上界集

4.2 商立方体的预计算算法

商立方体的预计算算法的主要目的就是将单元分类和找出这些类的上界。为了加快预计算的速度，本文中的预计算程序使用到了映射处理。也就是将在原始数据某一维上不相等的数值，根据它们出现的顺序，映射成正整数。例如表2.1中的第2维{B, F, B}，通过映射，B将映射成1，F将映射成2，第3个B因为之前已经出现，所以不必重新映射。映射后，对于数值为“*”的维度，则把它看作是0。

在将基表完成映射并完全载入内存的时候，便开始进入商立方体预计算算法的主体部分，一个深度优先算法（DFS）。在DFS中，完成了以下一些工作：找出覆盖相等的单元、找出类的上界并跳转到这些上界、根据基表分区来进行立方体计算。

对于某单元c，DFS是按照以下步骤来找出c所在类的上界ubc的：根据上界的定义，可以知道ubc与c比较的话，在c中不是“*”的维度的值与ubc相应维度的值是相同的。对于c在基表上的覆盖集Bc，任意一个维度i，且c在i维上的值为“*”，假设一个固定值xi出现在所有Bc中的所有元组的第i维中，则ubc的第i维元素就是xi。如果不存在这样xi，则第i维上的元素就是“*”。DFS的大体流程如下表所示：

DFS (cl, bPos, ePos, d)

(1) 计算cl的上界集ucl；

(2) 如果存在j<d使得cl[j]=*而ucl[j]!=*,返回(已经存在ucl，不用再次计算)；

(3) 否则，计算元组cl的聚合值，写进内存变量；

(4) 用临时元组tmpucl存储上界集ucl；

(5) 对所有d<j<n使得ucl[j]=*进行以下操作：对从bPos到ePos元组在维度j上排序，对j维度上的每一个值x，让ucl[j]=x；Posb为j维度值为x的第一个元组，Pose为j维度值为x的最后一个元组，递归调用DFS(ucl,Posb,Pose,j)；每次j值改变之后，ulc=tmpucl；

(6) 返回；

表4.2 DFS算法

预计算算法最终的输出结果所有类的上界和类的度量值，它们存放在（维度数+1）×2个文件中。假设原始数据的维度是d，则会产生d+1个存放上界的文件，另外d+1个文件则存放相应的度量值。具有同样多个“*”的上界被归为同一层，它们都存放在同一个文件中，且该文件只存放同一层的上界，它们相应的度量值也存在相应层次的度量值文件中。例如：全部都是“*”的单元是第0层，没有“*”的单元则是第d层，依此类推。

4.3 商立方体的查询算法 商立方体的查询其实就是查找出与查询语句划分在同一类中的上界。本文中所使用的商立方体查询算法是最直观的顺序查询。对于某条查询q，顺序查询是按照以下步骤进行的：

(1) 根据预计算产生的映射文件，对q进行映射。

(2) 扫描映射后的q，确定q所在的层次。

(3) 打开q所在层次的对应上界文件。

(4) 从目前打开文件的第一条上界开始扫描，判断该上界是否被q所覆盖。如覆盖，则记下该上界的位置，在相应的度量值文件中找到该上界的度量值，返回度量值。如不覆盖，则继续扫描下一条上界，判断是否被q覆盖。

(5) 假如在当前打开的层次文件中扫描不到被q所覆盖的上界，且当前层次已经是第d层，则返回查询不命中。如果当前层次还不是第d层，则打开当前层次的下一层次文件。然后跳转到(4)。

文献[LW05]对于商立方体的查询性能进行了分析。对于查询算法的第(5)步，假如在q所在层次文件扫描不到上界，便需要扫描下一个层次，当每个层次的数据量都很大的时候，这种查询不命中就会产生额外的开销，使得查询程序性能下降得很厉害，而对于数据立方体类似的顺序查询则不会造这种额外层次扫描的开销。

4.4 小结 目前基于数据立方体元组间关系的压缩技术分成了两类，一类是以原有立方体存储结构为基础，如精简立方体；另一类则是通过分析立方体元组间的逻辑关系，构造出新的立方体存储结构，如Dwarf和商立方体。

商立方体的主要思想是把数据立方体中覆盖相等的单元全部分成一类，使得只需保存这个类的上界便可保留数据立方体的信息，这样便达到了压缩数据立方体的目的。

第五章 并行化算法的设计

本章将描述本文提出的基于数据分组方法的并行预计算，以及在该预计算方法产生的商立方体数据上，并行地进行查询的方法，并对这种做法的正确性进行初步的分析。

5.1 基于数据分组的预计算

基于数据分组的预计算方法的主要思想是数据的分布性。并行预计算程序使用主从模式进行编程。主要的处理步骤如下所示：

(1) 基表由主进程读入，主进程一边读入基表元组，一边完成对各维数据的映射处理，映射关系文件存储在主进程所运行的机器上。

(2) 当主进程载入内存的数据元组条数到达一定数量时（由用户决定），主进程将这部分数据发送给相应的从进程，从进程在接收数据完毕之后，立即开始对所接收到数据进行商立方体预计算。主进程在将分配给某个从进程的数据发送完毕后，继续将基表中的数据载入内存，直到所有元组都被载入和所有的从进程都接收好数据以后，主进程开始对留在本地内存中，没有分派给任何从进程的元组数据进行预计算。

(3) 每个进程都独立地进行预计算工作，它们预计算所产生的商立方体上界分层地存储在进程运行机器的本地磁盘中。

(4) 所有进程都完成预计算后，并行程序退出。

主进程数据分发示意图如图5.1所示。

SHAPE \* MERGEFORMAT

图5.1 数据分发示意图

5.2 在立方体分布式存储情况下的并行查询

上一小节所描述的预计算算法，在完成预计算之后，将会把商立方体数据分布式地存储在各台机器的本地磁盘中。对于这种情况，应该要并行地对各个独立存储的立方体进行查询，并且最终各个查询结果要经过汇总处理后才能得到与串行查询程序一样的查询结果。本文提出的在立方体分布式存储情况下的并行查询也是基于MPI，以主从模式为实现方式，基本步骤如下：

(1) 主进程读入多条查询语句，并根据主进程本地存储的映射关系文件对查询语句进行映射，映射后的查询语句都存放在主进程的内存中。

(2) 主进程将所有的查询语句广播给各个从进程后，主进程开始进行查询。从进程在接受完查询语句后，也开始对本地的立方体数据进行查询。

(3) 每条查询语句都会返回一个结果，各个进程将这些查询结果存放在一个大小为查询语句条数的数组中。在所有查询都完成查询后，主进程开始接收来自各从进程的查询结果，从进程则开始向主进程发回它们的查询结果。

(4) 主进程在接收完各从进程的查询结果后，将所有查询结果整合在一起，便得到最终的查询结果。

5.3 正确性分析

本节将用来说明在5.1和5.2节中所提出的基于数据分组的并行预计算和查询方法的正确性。主要说明在立方体数据分布式存储情况下，并行查询程序得到的结果，与在立方体数据集中式存储情况下的串行查询程序所得到的结果是相等价的。

对于查询语句q，它的查询结果R(q)是决定于q的覆盖集Cov(q)的。假设基表为B，有m条元组，q在B上的覆盖集为Cov(q)。

随机地将B中的元组分为2部分，分别为B′和B′′。由于是以元组为单位划分，同一条元组不可能同时出现在两部分中，q在B′、B′′上的覆盖集分别为Cov′(q)、Cov′′(q)。可知：

设a机的输入基表是B′，b机的输入是B′′。在预计算完成后，分别生成立方体QC(B′)和QC(B′′)。在并行查询中，分别使用q对QC(B′)和QC(B′′)进行查询。假设查询命中的上界分别是u′和u′′。根据本文4.3节中提到的查询算法的原理，可知：

在QC(B′)中，u′与q被划分到同一类中，且u′是该类的上界，则u′和q是覆盖相等的，有：

同理：在QC(B′′)中，

则有：

串行查询结果R(q)决定于Cov(q)所包含的元组信息。在并行查询中，程序可以分别得到Cov(u′)和Cov(u′′)的信息，而Cov(u′)与Cov(u′′)包含了Cov(q)中包含的所有的元组信息，因此，并行查询是可以得到与串行查询相等价的查询结果的。

5.4 小结

本章概括性地描述了基于数据分组的并行预计算和并行查询方法的实现过程，并对于这种方法的正确性进行了初步的分析。在接下来的章节中，将会详细地描述基于这种方法的并行程序的实现和使用实验数据来更进一步地表明该方法的正确性和有效性。

第六章 并行化算法的实现 6.1 串行预计算程序结构

在串行预计算程序中，一共有Cubing、DFHandle、QuotientCube和TupleHandle4个类，其中DFHandle和TupleHandle两个类是辅助功能类。它们的类图如图6.1所示。DFHandle的主要功能是打开关闭数据文件，将数据文件中的元组一条一条地读进来，然后将该条元组交给TupleHandle处理，TupleHandle将元组的各维数据分割开来，每次处理一维，并将该维数据存在程序指定的一个内存区域中。关于Cubing类和QuotientCube类的详细介绍，将在以下的章节中给出。

图6.1 DFHandle类和TupleHandle类

6.1.1 Cubing类

Cubing类的类图如图6.2所示，其中loadData()的作用是使用DFHandle类，打开指定的数据文件，将元组读出之后，使用TupleHandle来将各个维度和度量值的数据拆分开来，然后对所有的维度做映射操作，写入映射文件，同时将映射后的维度数据存在data这个二维数组里，度量值存在msrdata中，直到把所有数据文件都读入data和msrdata中。在读数据之前，loadData还会先统计基表中有多少条元组，元组有多少维和多少个度量值，某度量值上的聚集操作分别是哪种，这些数据分别存在tuplesNum，dimsNum，msrsNum和aggFunOrder中。

avgFun()、maxFun()、minFun()、sumFun()和countFun()里面分别是平均、最大值、最小值、和、计数等聚集操作的实现。

图6.2 Cubing类

Cubing类的工作主要是完成预计算真正开始之前的准备工作，把所有数据都读入内存之后，QuotientCube类便可以使用这些数据来进行预计算工作。Cubing类的preCompute()函数是一个虚函数，它的具体实现在QuotientCube中。QuotientCube类是Cubing类的一个子类。

6.1.2 QuotientCube类

QuotientCube类public继承于Cubing。它的类图如图6.3所示。通过调用preCompute()开始预计算工作。

图6.3 QuotientCube类

程序首先会创建dimsNum+1个aggDimDataX文件，用来存放不同层次的上界，同时也创建同样多个的aggMsrDataX文件，用来存放相对应的度量值。data[0]中存放Cubing从数据文件读出的data内容，同样msrData[0]中存放相应的度量值，data[1]和msrdata[1]中将存放的是将data[0]、msrdata[0]里数据排序后的结果，用来排序的算法在Partition()中实现。

preCompute()接下来便会调用DFS()开始计算上界并将上界与其所对应的度量值写入相应层次的文件中。DFS()的具体算法详见本文4.2节。

预计算程序的数据流图如图6.4所示。

图6.4 串行预计算程序中的数据流

6.2 预计算并行化

并行预计算程序中，在串行程序的基础上增加了两个类：分别是DispatchManager类和DispatchWorker类。顾名思义，DispatchManager类中的方法是为主从模式中的主进程所调用，DispatchWorker类中的方法是在从进程中调用。根据本文5.1节中的描述，DispatchManger类主要的工作是完成数据读入、映射和数据分发工作。DispatchWorker的工作是接收主进程发送过来的数据。

6.2.1 DispatchManager类和DispatchWorker类

DispatchManager类和DispatchWorker类的类图如图6.5所示。数据的读入工作将由Cubing类转移到DispatchManager类中，但由于从进程无法接触到文件信息，因此，主进程必须将与数据文件相关的数据预先得出并发送给每个从进程。DispatchManager在初始化时便会调用getDataFileNum()和getConfig()。

getDataFileNum函数使用DFHandle和TupleHandle来完成工作。首先打开数据文件，将第一行读出。数据文件的第一行是用来写明基表有多少个维度和度量值，每个维度和度量值的名称分别是什么。getDataFileNum里会根据里面的信息分辨出哪些是维度数据，哪些是度量值，分别有多少个，度量值以何种方式进行聚集操作等，然后把这些数据保存下来。最后是统计整个数据文件有多少条元组。这些操作基本和Cubing::loadData中前面部分的操作相同。

图6.5 DispatchManager和DispatchWorker类图

getConfig函数的作用是将保存着各个进程数据分配比例的配置文件内容读出，并根据getDataFileNum中得到的元组条数，计算出每个进程应当接收的元组条数。计算完之后，将这些信息保存在pConfig中。

接下来，DispatchManager便会将pConfig里的数据连同度量值操作方式和文件夹名称发送到每个相应的进程中，如图6.6所示。同时，在从进程中运行的DispatchWorker也调用了recvConfig()。主从进程间通过MPI的点对点通信，完成配置数据的发送和接收。DispatchWorker接收完配置数据之后，将配置数据存如pConfig里。

在完成配置数据的交互之后，DispatchWorker将会利用收到的数据，如元组条数、维度数和度量值数来决定该分配多大的内存空间以存下将要收到的数据，并开始等待接收数据。而DispatchManager则会调用loadData()来将数据文件载入内存。

DispatchManager在loadData()时是将数据存入两个长度分别为iDimNum*iTupleNum和iMsrNum*iTupleNum的一维数组中，它们分别是pDimData和pMsrData。与串行预计算程序中的Cubing作用类似，DispatchManager会在载入数据的同时完成映射的工作。但当DispatchManager准备好要发送到其中一个从进程的数据之后，它便会调用sendData()，指明将要发送的进程号，将数据发送出去。如图6.7所示。

图6.6 发送和接收配置数据示意图

图6.7 发送和接收数据示意图

在每个从进程都接收完数据和主进程完成loadData之后，每个进程都会有装着维度数据和度量值的两个一维数组。在并行程序的Cubing中，由于不再需要与文件打交道，所以将Cubing::loadData()重载，将它的输入参数由数据文件名改为文件夹名称、pDimData、pMsrData和pAggFun。在这个函数中，Cubing将会把pDimData和pMsrData这两个一维数组的数据读出，存成二维数组。这样，数据发送过程已经完结，预计算开始之前的数据准备工作已经完成，接下来便是各个进程调用QuotientCube里的preCompute()函数，开始预计算工作。接下来在每个进程中的工作情况，和串行环境下的情况一致。

6.3 串行查询程序结构

在串行查询程序中，同样也有DFHandle和TupleHandle这两个辅助类。实现查询功能主要由以下三个类完成：AggStorage、CloseCubeQuery、QueryComputation。它们的类图如图6.8所示。

图6.8 查询程序类

AggStorage类的主要功能是面向立方体数据的操作。它封装了读入预计算所产生文件的方法，如loadMapData是将map文件读入，用来映射查询语句。loadAggData用来将某一层立方体文件内容读进内存。

串行查询程序首先会通过QueryComputation::getQueryRecord()将查询语句批量地读入，存在QueryRecords里，然后调用CloseCubeQuery::Query()。在CloseCubeQuery::Query()中，程序通过aggStorage所实例化的AggStorage对象将映射关系文件读入，并调用MapStoI()将查询语句映射为整型数组。映射后的查询语句存在tqryobj中，然后将tqryobj中的内容，一次一条地递交给pointQuery()进行查询。大致的流程如图6.9所示。

图6.9 串行查询流程

pointQuery首先会确定该条查询语句的层次，然后判断该层次的数据是否已经载入内存，如果没，则调用AggStorage::loadAggData()将其载到内存中。然后开始顺序扫描各条上界，使用isCovered来判断该上界是否被查询语句所覆盖。如果扫描完一层还找不到所覆盖的上界，则继续扫描下一层文件。具体流程在本文4.3节。

6.4 并行查询

在并行查询程序中，增加了两个类，分别是QueryManager类和QueryWorker类。串行程序中的QueryComputation类被取消，它的功能将在QueryManager类中实现，CloseCubeQuery中的MapStoI()函数也放在QueryManager类中实现。图6.10中所示为QueryManager类和QueryWorker类的类图。

6.4.1 QueryManager类和QueryWorker类

并行查询程序首先会在主进程中调用QueryManager::loadQuery()来将查询语句全部存入内存queryRecords二维数组中。接着就是调用QueryManager::mapQuery()将查询语句映射成整型数组，存入QueryManager::pQuery中。与并行预计算程序类似，并行查询程序中，主进程也会预先将一些配置数据发送给从进程，其中包括了查询语句的条数、数据的维度和度量值数。从进程在接收完这些数据之后，做一些初始化工作，为即将发送过来的查询数据做准备。实现这个功能的是QueryManager::broadcastConfig()和QueryWorker::receiveConfig()。

在配置数据发送完毕之后，便是开始发送查询数据，主进程调用QueryManager::broadcastQuery()将查询数据分发到各个从进程上，从进程接收完之后，将查询语句存入QueryWorker::pQuery中。

结果的指针。主进程与从进程分别调用CloseCubeQuery::Query(QueryManager::pQuery, QueryManager::pQueryResults[0])和CloseCubeQuery::Query(QueryWorker::pQuery, QueryWorker::pQueryResult)开始进行查询工作。

图6.10 QueryManager类和QueryWorker类

查询的流程如图6.11所示，在Query()中的实现过程基本与串行程序过程一致。在查询完毕之后，各个从进程将会把存放着查询结果的数组，pQueryResult发送回主进程。主进程调用QueryManager::collectResults()将所有信息收集起来，并将其存在pQueryResults二维数组中。最后，QueryManager将会调用statistics()来统计并得到最终的查询结果，并行查询程序返回。

图6.11 并行查询示意图

6.5 小结

本章通过类图和数据流图说明了并行预计算程序和并行查询程序的具体实现。程序使用了C++和MPI为编程语言和编程环境，使得程序具有良好的封装性和可移植性。

第七章 实验

在本章中通过实验说明算法的有效性和可扩展性。实验的平台是一台有三个计算节点的刀片服务器，每个节点上的处理器主频为1.8GHz，内存容量为1GB，操作系统是Linux，内核版本2.6.9，节点间采用千兆网络连接。MPI运行环境为MPICH2.0，C++编译器g++版本为3.4.3，MPI环境下C++编译器MPICXX的版本为1.0.3。

7.1 数据描述 在实验中，使用了一个来自不同气象站所收集的1985年9月的天气数据[Hahn94]。它包含了1,015,367个元组，一共20维。在这次实验中，所使用的是它前16维的数据，每个维度的依次如下表所示：

维度

维度名称

维度的势

1

时间

240

2

天空明亮度

2

3

纬度

3809

4

经度

5359

5

气象站编号

7037

6

气象站所处地点

1

7

当前天气情况

101

8

云层覆盖总量

9

9

低层云数量

10

10

低层云高度

11

11

低层云类型

13

12

中层云类型

14

13

高层云类型

11

14

中层云数量×100

24

15

高层云数量×100

24

16

中层云数量

10

表7.1 天气数据集

7.2 预计算实验

在本实验中，将讨论基于数据分组方法的并行预计算程序对于串行预计算程序在性能上的提高，以及这两种方法在不同规模数据集上进行运算的性能表现。讨论并行查询程序的加速比。

在预计算实验中，在单节点环境下和三节点环境下分别对13个不同的数据进行了串行和并行预计算。这13个不同的数据的维度各不相同，从4维到16维，分别是天气数据集20维数据中的前4维到前16维等，元组条数都是1,015,367条。三节点环境下的数据分割采用平均分割，每个节点上收到的元组条数基本上是相等的。

在单节点环境下的实验使用串行的预计算程序。统计两个时间：(1)程序进行预计算写入文件的时间。(2)程序运行时间。

在三节点环境下的实验使用并行的预计算程序。因为从机不需要等待主机完全读入数据文件便可得到一部分数据进行预计算，使得从机预计算时间和主机读取文件有交叉。因此在此实验中，每台机器都会统计三个时间：（1）主机从开始读取数据文件到数据完全载入内存并发送出去的时间。（2）每台机器进行预计算的时间。（3）每台机器总的运行时间。

通过实验发现，刀片服务器的网络效率非常高，在实验中，几乎所有的MPI点对点通信时间都可以在0.2秒之内完成，加上实验中的MPI通信次数比较少，所以MPI通信的时间可以忽略不计。

7.2.1 预计算实验结果分析 图7.1所示是分别在两种环境下的预计算时间，也就是程序生成立方体的计算时间。并行环境下的预计算时间是取三个节点预计算时间的平均值。如图中所示，基于数据分组的并行预计算方法能够有效地缩短预计算的时间。在数据维度少于或等于9维时，预计算的时间增长显得比较缓慢，在这个维度区间内，预计算程序的性能始终保持着较高水平。但随着数据维度的增多，预计算性能开始出现衰减。从11维数据开始，每增加一维数据，串行预计算时间便会增加约33%，而并行的预计算时间增长率为29%左右。

图7.2所示是串行预计算时间和并行平均预计算时间的比值。在4到10维之间时，串行预计算时间一直维持在并行计算时间的2.9倍左右。但在11维或更多维数据时，串行预计算时间的增长率开始大幅超过并行预计算时间，使得并行计算的加速比在11维时达到了理想状态的3倍，并且呈线性增长的趋势。可见，随着数据量的增大，DFS算法性能会相应地下降，而减少元组条数可以继续使得DFS算法保持高性能。

图7.1 预计算时间

图7.2 预计算加速比

图7.3、7.4和7.5分别是预计算程序读入数据文件时间、程序总运行时间和总运行时间的加速比。并行环境下程序总运行时间是指程序开始运行直到最后一个进程完成计算退出为止。并行程序中数据读入与数据发送是结合在一起的，数据读入一部分之后即可将该部分数据发送给相应的进程进行计算，但读入数据文件这一部分不能达到完全的并行化，所以程序总运行时间的加速比性能并没有已经完全并行化的预计算加速比那么可观。但随着维度的增多，预计算时间的增长，数据读入时间所占的总运行时间比例也相应地减少。在高维度的预计算中，并行的预计算程序最终还是可以达到3倍这个理想性能加速比。

图7.3 数据读入时间

图7.4 总运行时间

图7.5 总运行时间加速比

7.3 查询实验 本实验的主要内容是在预计算生成的商立方体基础上，对4至13维的商立方体进行单节点串行和三节点并行点查询实验。讨论并行查询程序相对于单机查询程序在性能上的提高，计算并行查询程序的加速比。

首先各个维度都随机地生成了1000条点查询。生成的点查询是从基表中随机抽取出1000条元组，并随机地将元组中的某些属性改为“*”。经观察，串行查询程序与并行查询程序所得到的查询结果是一致的，在本实验中，主要讨论并行查询程序对于串行程序的加速比，因此，查询的具体结果便不再讨论。串行查询与并行查询的程序运行时间如图7.6所示。

图7.6 查询程序运行时间

7.3.1 查询实验结果分析

尽管在并行查询中，每台机器所查询的立方体单元数目基本上只相当于串行查询中立方体单元数目的三分之一，如图7.7所示，但通过实验发现，并行查询程序的性能加速比并未能够达到理想的加速比，如图7.8，只能达到2倍左右的性能加速。对其原因进行分析，发现这是由于查询语句未能直接命中，会造成额外开销的问题（本文4.3节中提到）所造成的。

图7.7 商立方体单元数

图7.8 程序加速比

在基于数据分组方法的预计算中，经过预计算的商立方体数据是分布式地存放各台机器上的。对于一条查询语句q，当程序用q在A机器的商立方体中进行查询时，q的覆盖集里面的所有元组在预计算时可能都没有分配到A机器上。在这种情况下，q在A上的查询便会产生巨大的额外开销：首先会从q所在层次h1里的单元中开始查找，在h1找不到的情况下，会继续查找h1的下一层h2。但是由于q在A上是无法命中的，查询程序会一层接着一层地往下扫描下去，直到扫描完最后一层。

随机生成的1000条点查询语句是根据基表中的元组生成的，这样在串行查询中，较少会出现语句在某一层未能命中，需要扫描下一层的情况。然而在并行查询中，由于元组的分布性，产生了较多的查询不命中，使得程序必须进行额外的层次扫描，而且这种额外的层次扫描的代价十分巨大。在并行查询中，开销巨大额外的层次扫描使得查询的时间急剧地增加，从而使得程序性能没能达到预期的效果。

尽管如此，在三台机器上能够实现缩短一半的时间，并行查询程序的性能还是令人满意的。

7.4 小结

由于硬件平台条件的限制，实验最多只能在三个节点上运行，无法进行更多的实验来验证本文提出的基于数据分组的并行预计算和并行查询方法的可扩展性。

在三个节点上进行的预计算和查询实验的结果表明，基于数据分组方法的数据仓库并行预计算和查询方法是有效的，它能够有效地提高数据仓库预计算和查询的性能，并得到正确的结果。

第八章 总结与展望

在数据仓库数据量急剧增长的今天，并行数据仓库技术成为了解决海量数据预计算和存储问题的一种重要的、有效的手段。本文主要研究了一种基于数据分组的并行数据仓库预计算和查询技术，并在串行程序基础上实现了并行预计算和查询的程序。然后通过实验数据来说明该方法的有效性和分析了这种方法的优点和存在的缺陷。

8.1 结论

由于实验平台的限制，使得各项实验最多只能在三个节点的环境下运行，无法在更多节点的计算环境下进行实验，研究本文提出方法的可扩展性。通过实验的观察和分析，本文提出的基于数据分组的数据仓库并行预计算和并行查询方法有以下一些优点：

(1) 该实现方法的并行策略简单，该方法可以经过很少的修改，便可以将很多已经实现的串行程序改为并行程序。使用MPI和C++进行编程，使得程序具有良好的可移植性、面向对象性。

(2) 可以更好地适用于大数据量场合。对于串行版本的预计算程序，在对于高维度数据集进行预计算时，随着数据量的增加，性能衰减得很厉害。并行预计算时的性能加速比十分可观，在数据量很大的情况下，甚至可以超过理想加速比。

(3) 预计算后生成的商立方体数据以分布式方式存储，在查询时，各台机器都可以同时对立方体数据进行读取，充分利用了各台机器的磁盘I/O带宽。

同时本文提出的并行预计算和并行查询方法存在的一些不足：

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

(2) 基表元组的映射可以提高预计算和查询的响应效率，但是对于映射这个步骤还不能完全地并行化处理。

8.2 未来的改进

对于本文提出的并行预计算和并行查询方法存在的一些不足和缺点，可以存在这样一些补充和改进的地方：

(1) 预计算算法还需要做出一些修改以适应立方体分布式存储环境，如聚集操作中的平均操作，除了对该维度量值做平均值计算之外，还应该同时加上计算总和的计算。这样才能保证元组条数的信息不至于丢失，在主进程最终做统计运算的时候才能得到正确的结果。

(2) 对于基于顺序查询方法的并行查询，可以预先判断一下是否在该机上命中查询。如果可以预先判断出查询不命中，则可以减少许多额外的层次扫描开销，提高效率。预先的判断应该可以通过扫描本地预计算输入基表里有没有查询语句覆盖集内的元组进行。

(3) 改进查询程序的算法。顺序查询是最简单、易行的查询方法，但这种方法的效率确实不高。

(4) 改进立方体数据结构，商立方体存在着查询效率不高的问题，对此人们提出了各种基于商立方体的改善型立方体数据结构，如QC-Tree[LPZ03]和Semi-Closed Cube[LW05]，基于此类型的立方体结构应该能够改善查询的响应速度。

参考文献 [Beo07] 　: The Beowulf Cluster Site:

[CCS93a] E. Codd, S. Codd, C. Salley. Beyond decision support. Computer World, 27(30): 87-89, 1993

[CCS93b] 　E. Codd, S. Codd, C. Salley. Providing OLAP to User-Analysts. PC World, (9), 1993

[Chen99] 陈国良. 《并行计算——结构·算法·编程》. 北京, 高等教育出版社, 1999

[Du01] 都志辉. 《高性能计算并行编程技术——MPI并行程序设计》. 北京, 清华大学出版社, 2001

[Fly72] M. Flynn. Some Computer Organizations and Their Effectiveness. IEEE Transactions on Computers, C21(9), 1972

[GCB+97] J. Gray, S. Chaudhuri, 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, 1997

[GGKK03] A. Grama, A. Gupta, G. Karypis, V. Kumar. Introduction to Parallel Computing (Second Edition). Pearson Education, 2003. 张武, 毛国勇, 程海英 等译. 《并行计算导论》. 北京, 机械工业出版社, 2005

[Hahn94] C. Hahn et. al. Edited synoptic cloud reports from ships and land stations over the globe, 1982-1991. cdiac.est.ornl.gov/ftp/ndp026b/SEP85L.Z, 1994.

[HPF06] High Performance Fortran Forum: hpff.rice.edu/

[Inm02] W. H. Inmon. Building the Data Warehouse (Third Edition), John Wiley & Sons, Inc. 2002. 王志海, 林友芳等译. 《数据仓库》. 北京, 机械工业出版社, 2003

[LAM07] LAM-MPI Parallel Computing:

[LPH02] L. Lakshmanan, J. Pei and J.Han. Quotient Cube: How to Summarize the Semantics of a Data Cube. In VLDB’02

[LPZ03] 　L. Lakshmanan, J. Pei and Y. Zhao. QC-Trees: An Efficient Summary Structure for Semantic OLAP. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, ACM, 2003

[LW05] S. Li and S. Wang. Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time. Journal of Computer Science and Technology, Vol.20, No.3, pp.367-372, 2005

[MPI03a] MPI: A Message-Passing Interface Standard. /docs/mpi1-report.pdf

[MPI03b] MPI-2: Extensions to the Message-Passing Interface. /docs/mpi2-report.pdf

[MPI07] MPICH2 home page: www-unix.mcs.anl.gov/mpi/mpich/

[OMP07] OpenMP: Simple, Portable, Scalable SMP Programming:

[PTP06] POSIX Thread Programming: www.llnl.gov/computing/tutorials/pthreads/

[PVM07] Parallel Virtual Machine Web Site: www.epm.ornl.gov/pvm/

[SRD02] Y. Sismanis, N. Roussopoulos, A. Deligiannakis and Y. Kotidis. Dwarf: Shrinking the Petacube. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, ACM, 2002

[ST98] D. Skillicorn and D. Talia. Models and Languages for Parallel Computation. ACM Computing Surveys, 30(2): 123-169, 1998

[WLFY02] W. Wang, H. Lu, J. Feng and J. Yu. Condensed Cube: An Effective Approach to Reducing Data Cube Size. In Proceedings of the 18th International Conference on Data Engineering, IEEE Computer Society, 2002.

[ZCML06] 张林波, 迟学斌, 莫则尧, 李若. 《并行计算导论》. 北京, 清华大学出版社, 2006

附 录

时间(秒)

维度

, , 串行

并行

4

5.18

4.98

5

6.94

6.68

6

7.50

7.36

7

8.55

8.28

8

9.08

8.98

9

9.83

9.76

10

10.58

10.54

11

11.29

11.32

12

12.02

12.08

13

12.75

12.78

14

13.47

13.70

15

14.26

14.49

16

14.96

15.31

表1 数据文件读取时间

时间(秒)

维度

串行

并行进程0

并行进程1

并行进程2

并行平均

4

28.92

9.95

10.29

9.58

9.94

5

84.40

29.04

30.09

28.24

29.12

6

84.70

29.13

30.10

28.42

29.22

7

87.78

30.23

31.23

29.40

30.29

8

92.41

31.81

32.91

31.07

31.93

9

100.98

34.69

35.74

33.84

34.76

10

114.48

39.24

40.19

38.11

39.18

11

139.92

45.93

49.33

44.88

46.67

12

180.65

57.77

61.94

56.26

58.73

13

244.26

78.17

78.25

74.78

77.07

14

332.70

104.71

103.72

98.87

102.43

15

431.87

132.03

130.22

126.22

129.49

16

576.41

173.32

170.31

164.59

169.41

表2 预计算时间

时间(秒)

维度

串行

并行进程0

并行进程1

并行进程2

并行完成

4

34.10

16.10

14.74

15.72

16.10

5

91.34

36.84

35.58

36.02

36.84

6

92.20

38.58

37.05

37.86

38.58

7

96.33

40.69

38.86

39.86

40.69

8

107.49

42.15

40.2

41.41

42.15

9

110.81

46.01

43.74

45.15

46.01

10

125.06

51.26

48.65

50.13

51.26

11

151.21

60.09

56.86

58.37

60.09

12

192.67

73.34

69.57

70.45

73.34

13

257.01

92.72

88.46

89.32

92.72

14

346.17

120.28

114.66

114.43

120.28

15

446.13

148.56

141.81

142.74

148.56

16

591.37

190.8

182.58

182.07

190.80

表3 预计算程序运行时间

单元数(条)

维度

串行

并行进程0

并行进程1

并行进程2

并行总和

4

1476016

508194

513514

503833

1525541

5

1480006

509514

514914

505273

1529701

6

1480006

509514

514914

505273

1529701

7

1702776

610851

618488

596856

1826195

8

2211668

847229

861503

817868

2526600

9

3147573

1190299

1208486

1136715

3535500

10

4747893

1738919

1756447

1634975

5130341

11

7140853

2532913

2551943

2321907

7406763

12

11034333

3818969

3832601

3458299

11109869

13

16386342

5595663

5598401

5077096

16271160

14

18964307

6469585

6464190

5824463

18758238

15

20850282

7091770

7071021

6369647

20532438

16

23480070

7979451

7945029

7131160

23055640

表4 预计算生成的单元数

时间(秒)

维度

串行

并行进程0

并行进程1

并行进程2

并行完成

4

8.13

5.67

5.67

5.28

5.73

5

10.44

6.03

6.30

5.62

6.30

6

12.22

6.95

7.18

7.30

7.30

7

13.96

8.47

8.20

8.53

8.56

8

18.16

11.18

10.94

9.67

11.26

9

28.79

14.34

14.03

13.84

14.38

10

42.97

23.50

22.44

19.30

23.54

11

67.36

35.46

33.46

31.67

35.58

12

106.22

49.84

48.09

47.26

49.94

13

173.07

74.75

73.73

74.32

74.83

表5 查询时间