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

1、基于数据分组方法的数据仓库并行预计算和查询一论文关键词：数据仓库并行计算消息传递接口商立方体论文摘要：目前很多数据仓库的原始数据量已经超过了t字节级，在单处理机机器上运行数据量如此庞大的数据仓库是非常困难。因此，并行计算技术对于数据仓库技术的介入是无法防止的，并行计算技术为进步运算才能和存储才能这影响数据仓库性能的两大重要因素提供了技术基矗本文详细介绍了基于数据分组方法的数据仓库并行预计算和查询的方法，其主要思想是将数据仓库基表中的数据进展分割，分发到各台计算机上后，并行地对数据进展预计算，并根据预计算完成后，立方体数据存储的分布性，并行地进展查询。本文首先介绍了数据仓库和并行计算的根本概念，

2、并根据商立方体的特点提出了基于数据分组方法的数据仓库并行预计算和查询的方法。本文对该方法的详细实现进展了描绘，并分析了在刀片效劳器上运行后得到的各项结果。基于数据分组方法的数据仓库预计算和查询方法的并行策略相对较简单，但在现实应用中，通过实验观察和对实验数据的分析，证明了这种方法是可行的，数据仓库的预计算性能于查询性能都得到了令人满意的进步。第一章绪论随着计算机应用的普及，人们的社会活动已经越来越多地依赖于计算机的使用。人类的各种社会活动，例如商品交易、科学实验都产生了宏大的数据量。这些常年累月积累下来的数据量极为宏大，虽然看似杂乱无章，但是里面却隐含着社会科学和自然科学的各种规律。如何更好地

3、去利用这些数据，从数据中寻找出这些规律来造福社会，是人们面临的另一个重要问题。传统的信息处理方式，如数据库，是以单一的数据为中心的事务处理，它可以让人们在可以承受的时间范围内完成对数据的各种事务操作，但是对于开掘数据中的规律却是无能为力。为此人们创造了很多新的计算机技术从这些数据中寻找出其隐含的规律，数据仓库便是其中的一种。为了更好、更快速地执行用户对数据仓库的查询，需要对原始数据集进展预计算。预计算就是将人们会在查询中希望得到的，将很多记录按照其某项属性进展某种聚集操作和、最大、最小等等后的结果，进展预先的计算处理。这样便可以进步查询的响应速度，减少响应时间，进步人们数据仓库的利用效率。由于

4、预计算所产生的数据集合必须考虑到每条记录的聚合，所以产生的数据量是原始数据集的数百倍甚至千倍。人们对于预计算的计算量要求也是宏大的。目前很多数据仓库的原始数据量已经超过了tb级，在单台机器上是根本支持不了数据量如此庞大的数据仓库，因此，并行计算技术的介入是无法防止的，它为进步运算才能和存储才能这两大重要因素提供了技术基矗并行计算是唯一可以处理这么大量信息的计算技术。本文将研究如何把并行计算技术引入到数据仓库的预计算和查询中，并通过实验来支持这种做法的有效性。希望可以为数据仓库的并行处理技术提供一种新的思路。1.1目的本文的研究目的是提出一种数据仓库并行处理技术，它使用pi实现，可以在多种平台上

5、运行，能有效地实现立方体预计算加速以及查询加速。1.2本文安排本文的余下部分将如下安排：第二章是介绍本文研究的相关背景，将描绘本文中涉及的关于数据仓库和并行计算的概念。第三章概括性地介绍了pi，包括pi标准开展史，pi编程中经常使用到的点对点通信原语和通信形式以及pi程序的根本构造。第四章将介绍商立方体提出的目的，商立方体的特性，预计算算法以及查询算法。第五章描绘了基于数据分组方法的数据仓库并行预计算和查询方法的根本思路与实现步骤，并对该方法的正确性做了初步的证明。第六章详细描绘了并行预计算程序和并行查询程序的详细实现与工作流程。第七章通过实验测量的数据来说明本文提出方法的有效性和对于预计算和

6、查询性能的进步。第八章对本文的工作进展了总结，说明了本文的主要成果和存在的缺乏，并为进一步的工作进展了展望。第二章背景自计算机创造后，人类文明进入了一个前所未有的高速开展阶段。计算机技术的应用缩短了许多新技术的研发周期，新技术往往意味着更高的消费力、更好的产品和更低的本钱。计算机自身也得益于这些新技术，越来越多的商业公司和个人可以负担得起计算机的使用费用，计算机逐渐普及。随着计算机技术应用的广泛性日益增加、性能不断地进步，加上互联网等革命性技术的出现，人们开场进入信息化社会，信息已经成为人类社会不可或缺的重要资源。社会信息化使得社会活动如：商业交易，科学实验，数据统计等所产生的数据急剧地增长，

7、而在这些数量宏大，看似杂乱无章的数据中，隐藏着社会活动和自然科学的规律。例如人们的购置习惯、dna的作用。分析数据，学习其中的规律成了人们迫切的目的。但是，数据的数量级已经远远地超过了人脑所能处理的范围，因此，人们只能将希望寄托在计算机上。2.1数据仓库面对爆炸性膨胀的数据和不断提升的应用要求，数据库技术也在不断地进步着数据库应用的作用和价值。传统的数据库技术主要擅长于提供以数据为中心，通过数据库对一个或一组数据记录进展查询和修改等的面向详细、特定应用的效劳，它可以满足响应时间、数据可靠性和完好性等方面的要求。这些传统的事务处理系统已经比拟成熟，在企业和组织中应用也非常普遍，随着各种组织的日常

8、事务处理的信息化，数据分析和决策支持应用成了必然的趋势。如何有效地利用历史数据为决策分析做支持，是近年来数据处理研究领域的热点。对数据进展分析处理的要求使得传统的数据库技术不能满足要求，为理解决这个问题，innin02提出了数据仓库的概念。他对于数据仓库是这样定义的：数据仓库就是一个用以更好地支持企业或组织的决策分析处理、面向主题的、集成的、不可更新的、随时间不断变化的数据集合。数据仓库有以下特点：面向主题subjet-riented：数据仓库中的数据是面向主题进展组织的。集成integrated：数据仓库中通常集成了多个异质数据源的数据。在集成过程中，需要对数据进展清洗、转换以保证数据的一致

9、性。稳定nnvlatile：数据仓库中的数据是反映一段相对长时间内历史数据的内容，是不同时间数据库快照的集合，以及基于这种快照进展统计、综合和重组的导出数据。所设计的操作主要是数据查询，一般不会进展修改操作。随时间变化tie-variant：数据仓库随时间变化不断增加新的内容，删去旧的内容。数据仓库技术在过去的一段时间内开展迅速，已经成功地应用到电信、银行、保险等行业。随着企业信息化的不断深化，这种开展还会持续。2.1.1联机分析处理与数据立方体为了让决策支持人员更好地去分析处理数据仓库中的海量数据，e.dd于1993年提出了联机分析处理lap:n-lineanalytialpressing的

10、概念s93a,s93b。lap工具通过对信息的多个角度维进展快速、一致、稳定的交互访问，决策支持人员可以深化地进展观察。lap工具是为了满足更高效地进展多维分析的需求而产生的，其主要功能是根据用户所选择的分析角度，事先计算好一些辅助构造，以便在查询对可以抽取到所需要的记录。lap系统中的数据通常会以一个多维的构造模型表现出来。表2.1是一个简单的销售数据仓库的基表basetable，基表中的一条记录称为元组tuple，该基表中一条元组有三个属性：时间、产品名称和地点，在这里被称为维度diensin，这些维用来表示和区分开不同的数据。销量属性是一个数值类型的度量值easure，是人们想要去分析的

11、数据。维度通常也会分层次hierarhy，例如时间维度可能会分为年、月、日、季度等层次。地点产品名称时间销量广州(gz)篮球(b)2022.5(1)20广州(gz)足球(f)2022.6(2)15深圳(sz)篮球(b)2022.5(1)25表2.1销售数据仓库的基表数据立方体dataube是由gray等人提出gb+97。它是对所有维度的所有可能结合，根据不同聚集粒度进展grup-by操作而产生的一个概括化数据集合。每一个grup-by操作都与一个单元ells的集合相关联，数据立方体关于表2.1的所有单元都在表2.2中列出，在表中，“*表示在这一维度中，它可以匹配到这个维度值域中的任何一个值。上

12、卷rll-up和下钻drill-dn是数据立方体中的两种根本语义关系。一个较高聚集层次的单元可以下钻到一个较低聚集层次的单元，如：gz,*,1下钻到(gz,b,1)。一个较低聚集层次的单元可以上卷到一个较高聚集层次的单元，如：sz,b,1上卷到*,b,*。一个立方体中的所有单元间的上卷/下钻关系构成了一个网格构造。图2.1中表现出了表2.2中的立方体网格。地点产品名称时间总和销量gzb120gzf215szb125gzb*20gz*120*b145sz*25*f*15*145*60表2.2数据立方体中的单元shape*ergefrat图2.1数据立方体网格2.2并行计算大规模科学与工程计算应用

13、使得人们对计算机性能要求不断进步。例如天气预报、空间模拟、石油勘探等科学计算对计算机的性能要求可以说是无穷无尽的。单台作业的计算机是根本无法满足这种计算需求的，因此人们便开场尝试应用新技术使得多台单独作业的计算机可以协调地共同进展工作，并行计算机便开场逐步走入人们的视野。并行计算是伴随着并行计算机的出现，在近三十年来迅速开展的一门穿插学科，是指在并行计算机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间互相协同，并行地执行子任务，从而到达加快求解速度，或者进步求解应用问题规模的目的zl06。并行计算必须具备三个根本条件：1并行计算机。并行计算机至少浩瀚两台或两台以上处理机，这

14、些处理机通过互联网络互相连接，互相通信。2应用问题必须具有并行度。应用可以分解为多个子任务，并且这些子任务可以并行地执行。3并行编程。在并行计算机提供的并行编程环境上，详细实现并行算法。2.2.1并行编程形式编程形式是程序员和计算机之间的界面，它是建立在计算机体系构造之上的程序的抽象，它定义了程序的设计与其实现之间的接口。在并行计算机开展的历史过程中，人们提出过许多合适不同并行体系构造的编程形式st98，经过时间的淘汰，目前比拟流行的并行编程形式根本上趋向于以下三种hen99,du01,zl06：消息传递形式：程序的执行分为多个进程，用户需要显式地为每个进程分配数据和指令。进程都在自己的私有空

15、间中运行，显式地通过发送和接收消息进展交互。有同步通信和异步通信两种方式。消息传递形式为程序员提供了更灵敏的控制手段和表达并行的方法，因此消息传递并行程序往往能到达高的执行效率。但由于程序员需要显式地指定进程间的信息交换、协调和控制，编写基于消息传递形式的并行计算程序对于程序员的才能要求比拟高。尽管如此，消息传递仍然是目前最常用的并行编程形式。pipi03a,pi03b和并行虚拟机pv07是其中两种广泛使用的消息传递编程标准库。共享存储形式：程序是由运行在一个公共地址空间的一组进程所组成。用户无需进展数据分配，每个进程相对独立地运行，进程间的通信通过存放在公共存储器中的共享变量进展。所以保持变

16、量操作的一致性和同步性是使用这种编程形式时必须考虑的关键问题。基于该形式通过手工或编译器将串行程序并行化，相比照基于消息传递形式更容易，对程序员要求也相对较低。目前使用较多的共享存储形式的实现有ieee标准委员会的多线程接口ptp06和penp标准委员会的penpp07。数据并行形式：程序所处理的数据被划分为多个小块，分配到系统中的各个处理单元上，每个处理单元执行一样的程序，不需要显示同步。数据并行形式的实现层次较高，一般由编译器实现，程序员只需指明怎样的并行操作和操作的对象即可。高性能frtranhpf06是一种使用较多的数据并行语言。2.2.2并行计算机体系构造并行计算机的分类是随着并行计

17、算机的开展而开展的。在并行计算技术开展的不同阶段，各个计算机消费厂商创造了各种各样把多个处理器处理单元整合在一起的方法，从而使得系统的整体计算才能有所进步。这些技术经过不断地开展，逐渐成熟并衍生出技术分支，同时也产生出许多不同的并行计算机体系构造。描绘这些体系构造特征的最常用的方法是flynn分类法fly72。它根据指令流数目和数据流数目来分类，将计算机分成了4类：sisd、sid、isd和id。其中，属于并行计算机的有：(1)单指令多数据流sid：同一指令被复制成多份，并发地发送给多个处理器，形成多个独立的进程，每个进程都具有自己的数据流如图2.2所示，具有同步性和确定性。shape*erg

18、efratshape*ergefrat图2.2sid体系构造(2)多指令多数据流id：在id系统中，每个处理器都具有自己的指令来操作自己的数据，与其他处理器无关。指令流可以同步或异步地执行，指令流的执行具有确定性和不确定性。如图2.3所示。shape*ergefrat图2.3id体系构造随着技术的开展，曾经风行的sid并行计算机已经退出了历史舞台，id体系的并行机已经占据了统治性的地位。目前世界上流行的并行计算机系统根本上都是属于id计算机。在id的分类中，按照内存访问模型、微处理器和互联网络的不同，并行计算机可分为以下5类zl06：(1)对称多处理共享存储并行计算机syetriulti-pr

19、essing,sp:sp系统中任何处理器都可以直接访问任何存储模块中的存储单元和i/模块，且各自间的访问延迟、带宽都一样。整个系统只有一个操作系统驻留在共享存储器中，可以动态地分配进程到各个处理器，而且每个进程都是使用共享的数据存储区来完成通信，通信的延迟较低。但是由于各个处理单元之间的耦合程度较高，所以只要总线、存储器或操作系统其中一个出错，便会导致整个系统的崩溃，而且系统的可扩张性较差。支持消息传递、共享存储并行程序设计。(2)分布式共享存储并行计算机distributedsharedery,ds：系统以节点为单位，每个节点包含一个或多个pu，每个pu有部分的ahe。存储在物理上分布，但在

20、逻辑上是统一的内存地址空间。各个节点既可以直接访问本地的部分存储单元，也进展访问其他节点的部分存储单元，但远端访问必须通过高性能互联网络，性能远不如本地访问。ds系统的可扩展性强，可扩展至数百个节点。支持消息传递、共享存储并行程序设计。(3)集群系统luster：系统由节点构成，每个节点包含24个商用途理器，节点内部共享存储。各节点通过交换机连接。当计算机是运行linux操作系统的p机时，这类集群那么成为beulfbe07集群。集群系统只支持消息传递并行程序设计。目前集群系统占据着主流地位，在世界超级计算机500强中，占据了大多数的席位。(4)星群系统nstellatin：系统由节点构成，每个

21、节点是一台sp或ds子系统，包含的处理器数量宏大，计算功能非常强大。节点间通过集群交换机连接，节点间分布存储。各个节点运行专用的操作系统、编译系统和作业管理系统。与集群系统所不同的是，星群系统可以支持消息传递和共享存储两种并行编程形式：在节点间使用消息传递，节点内部那么可以使用共享存储形式，这种混合形式充分利用了两种编程形式的特点，因此被认为是最有效率的编程形式。(5)大规模并行计算机系统(assivelyparallelpressing,pp)：由数百个乃至数千个结算节点和i/节点组成，每个节点相对独立，并拥有一个或多个微处理器。这些节点的部分ahe通过部分总线或互联网络与部分内存模块和i/

22、设备相连接。互联网络与集群互联网络不同，一般采用由多种静态拓扑构造耦合而成的混合拓扑构造，通信延迟和通信带宽明显优于集群系统。每个节点均拥有不同的操作系统，允许用户在某个特定节点上作业。各节点间内存模块互相独立且没有全局内存统一编址。假如要直接访问其他节点的内存那么需要有操作系统的支持。pp支持消息传递或高性能frtran并行程序设计，但不支持共享存储形式。各种并行计算机对于消息传递、共享存储、数据并行三种编程形式的支持在表2.3中列出。spds集群星群pp消息传递共享存储xx数据并行xx表2.3各种并行计算机对与编程形式的支持2.3小结数据仓库的应用日渐广泛，但是数据量的增长使得lap系统的

23、效率逐渐低下和数据立方体的容量呈指数上升。数据立方体的预计算需要大量的计算才能和存储空间，随着并行计算技术的开展，数据仓库将会更多地使用到并行计算技术。并行计算技术带来的不仅仅是计算才能和存储空间上的扩展，并行计算技术对于计算机性能的扩展使得更多更复杂的应用技术得以实现，扩展数据仓库的功能。第三章pi消息传递是一个广泛应用在并行计算机特别是分布存储并行机：ds、集群、星群和pp上的形式。自从20世纪80年代以来，经过10余年的开展，很多基于消息传递的应用系统有了长足的进步。由于基于消息传递形式的系统很多都具有效率高、适用性强等优点，所以人们认为通过定义一个核心库程序的语法与语义，将有益于广阔用户，将可以在更大范围的机器上有效实现消息传递形式。本章的主要内容是介绍目前最为流行的基于消息传递形式的编程环境：pi。在以下的章节中会介绍pi的产生、pi的实现和关于pi编程的根本概念。3.1pi的产生早期的商用并行计算机很多是基于