（计算机软件与理论专业论文）多维聚集查询的处理及优化.pdf

华中科技大学硕士学位论文 摘要 7 化天系掣联机分 ! j i 处理系统中，联机分丰j i 处理操作的实质就是多维聚集查嘲， 返j 含洵弛往足复杂费时的，这就对联机分析处理系统的查i 旬性能提出了很高的要 l 水。l 叫此，i + 分有必要对联机分析处理系统中的多维聚集查询处理进行优化。0 多维聚集查询的处理过程可概括为三个步骤，依次为：多维区间生成、数据立 力禽洵处删干fj 垡型硷潲处理。所以，对其的优化也主要针对这三个步骤分别进行。 o f 小枷交等价变抉是多维区间生成步骤中的一种台洵条件优化技术。当查询条 俐为析墩范z ，且其中各合取范式之问的交集非宅时，交集都分会在数据立方查询 处理的步骤- l 被重复畲询。互不相交等价变换把析取范式变换成互不相交的立方 块，这样小但r t ，以节省交集被重复查询的，f ：销，还可以宵省求各合取范式结果集并 鬃的jr 销。性能分析表明，当交集部分较大时，自4 i 柏交等价变换司以显著减小金 啪代价。 l 存数据莎方充分利用大容量内存，采用合适的数据小方袈入策略，有效组织 f 年管脞袈入内存的小方，实现了高效的数据立办查询。镁验结果表明，内存数据立 。川以快速响应点查渤和范围查询。一k 颅分组变换是一种星型查询优化技术，它利用层次代理键与维表层次属性之间 的映射关系，把部分分组聚集提到星型连接之前。由于分组聚集时尚未做连接操作， 所以参j 分组聚集的元组尺寸较小，另方面，提i j 分组聚集叉r q 减少参与星型连 接的，i 组数目。实验结果表明，预分组变换能同时加快星型连接和分组聚集计算。 关键词：联机分析处理；数据立方；多维聚集查询；查询处理；查询优化；星 型查询；互不相交等价变换；预分组变换 华中科技大学硕士学位论文 a b s t r a c t t ) n l i n e a n a l y t i c a lp r o c e s s i n go p e r a t i o n s a r em u l t i d i m e n s i o n a l a g g r e g a t eq u e r i e s i n e s s e n c ei nr e l a t i o n a lo n - l i n ea n a l y t i c a lp r o c e s s i n gs y s t e m m u l t i d i m e n s i o n a la g g r e g a t e q u e r i e sa r eu s u a l l yc o m p l i c a t e d ，a n do n - l i n ea n a l y t i c a lp r o c e s s i n gs y s t e mn e e d sh i g hq u e r y p c r l b r m a n c et oa n s w e rt h e s eq u e r i e sq u i c k l y t h e r e f o r e ，i ti sn e c e s s a r ya n di m p o r t a n tt o o p t i m i z e t h em u l t i d i m e n s i o n a l a g g r e g a t eq u e r yp r o c e s s i n g i no n - l i n e a n a l y t i c a l p r o c e s s i n gs y s t e m m u l t i d i m e n s i o n a l a g g r e g a t eq u e r yp r o c e s s i n g c a nb ed i v i d e di n t ot h r e em a i n p r o c e d u r e s ，m u l t i d i m e n s i o n a l r a n g e c r e a t i n g ，c u b e q u e r y p r o c e s s i n g ， a n d s t a r q u e r y p r o c e s s i n g i t s p e r f o r m a n c e c a nb e i m p r o v e d b yo p t i m i z i n g t h et h r e e p r o c e d u r e sr e s p e c t i v e l y e q u i v a l e n td i s j u n c t i o nt r a n s f o r m a t i o ni sa no p t i m i z a t i o nt e c h n i q u e t oq u e r y e x p r e s s i o n i nt h em u l t i d i m e n s i o n a l - r a n g e - c r e a t i n gs t e p w h e nt h ec o n s t r a i n te x p r e s s i o no faq u e r y i sd n f ( d i s j u n c t i v en o r m a lf o r m ) ，a n dt h ei n t e r s e c t i o n so fc n f s ( c o n j u n c t i v en o r m a l f o r m ) i nt h ed n fa r e n o t e m p t y ，t h e r e c o r d si nt h ei n t e r s e c t i o n sw i l lb er e t r i e v e d r e p e a t e d l y e q u i v a l e n td i s j u n c t i o nt r a n s f o r m a t i o nt r a n s f o r m st h ed n f i n t oau n i o no f d i s j u n c t i v e c u b ec h u n k s a sar e s u l t ，t h ec o s to fb o t h r e d u n d a n t l yq u e r y i n g t h e i n t e r s e c t i o n sa n dm e r g i n gt h ec n f s r e s u l t sc a nb es a v e d p e r f o r m a n c ea n a l y s i sh a s s h o w nt h a t e q u i v a l e n td i s j u n c t i o n t r a n s f o r m a t i o nc a n r e a l l y r e d u c et h e q u e r y c o s t r e m a r k a b l yw h e n t h ei n t e r s e c t i o n sa r el a r g e m e m o r y - c u b e m a k e sf u l lu s eo f l a r g er a m ，a p p l i e sas m a r tc u b o i d sl o a d i n ga l g o r i t h m ， a n do r g a n i z e sc u b o i d se f f e c t i v e l yi nm e m o r yt oi m p l e m e n t i n gc u b e q u e r y p r o c e s s i n g e f f i c i e n t l y t h ee x p e r i m e n tr e s u l th a ss h o w nt h a tm e m o r y - c u b ec a na n s w e rb o t hp o i n t q u e r i e sa n dr a n g eq u e r i e sq u i c k l y s t a r q u e r y p r o c e s s i n gc a nb eo p t i m i z e db yp r e g r o u p i n gt r a n s f o r m a t i o n p r e g r o u p i n g i l 华中科技大学硕士学位论文 = = ；= = # 目= ；= ；目目= ；目= ；_ _ _ _ _ _ _ _ _ _ - _ - - i l - l t r a n s l b r m a t i o n b r i n g sp a r t i a lg r o u p b y b e f o r e s t a r _ j o i nu s i n g t h ef u n c t i o n a lr e l a t i o n b e t w e e nt h e h i e r a r c h i c a l - s u r r o g a t e - k e y i n f a c tt a b l ea n dt h eh i e r a r c h i c a la t t r i b u t e si n d i m e n s i o nt a b l e a sar e s u l t ，t h es t a r - j o i ni sp e r f o r m e do nam u c hs m a l l e rn u m b e ro f t u p l e sw h i l et h eg r o u p b yi sp e r f o r m e do ns m a l l e rs i z et u p l e s t h ee x p e r i m e n tr e s u l th a s s h o w nt h a tp r e 。g r o u p i n gt r a n s f o r m a t i o nc a n s p e e du pb o t hg r o u p b ya n ds t a r _ j o i n k e yw o r d s ：o n l i n ea n a l y t i c a l p r o c e s s i n g ；d a t ac u b e ；m u l t i d i m e n s i o n a la g g r e g a t e q u e r y ；q u e r yp r o c e s s i n g ；q u e r yo p t i m i z a t i o n ；s t a r q u e r y ；e q u i v a l e n td i s j u n c t i o n t r a n s f o r m a t i o n ；p r e - g r o u p i n gt r a n s f o r m a t i o n 儿i 华中科技大学硕士学位论文 1 1 研究背景、目的和意义 1 绪论 任激烈的市场竞争中，管理者的正确决策对企业的生存和发展起着至关重要的 f 1 ：川。刈企业历史数据进行分析和挖掘，可以帮助管理者正确把握企业的整体形势 f 发展趋势，以便做出l 哪角的决策。所以众多企业对数据分析的需求越来越迫切， 也越来越复杂。为了满足企业数据分析市场迅猛扩大的需求，一些著名的数据库厂 商相继推出了它们的数据分析产品一一联机分析处理( 0 n l i n ea n a l y t i c a l h o c e s s i l l g ，o l a p ) 系统，例如m i c r o s o f ta n a l y s i ss e r v i c e 、l b h td b 20 l a ps e r v e r 7 2 和0 t d c l e e x p r e s ss e r v e r 等等。 侄o l a p 应用中，用户需要从多个不同角度观察和分析感兴趣的数据，这就要 求【) 1 a p 系统为用户提供数据的多维视图。于是，j i mg r a y 提出了一种多维概念模 鞋一数据立方。数据立方( d a t ac u b e ，简称c u b e ) 算子c u b eb y 是传统的g r o u p b y 算于的多维扩展，用于计算c u b eb y 子旬中各属性的所有可能组合所对应的 g r o u pb y 。一个g r o u pb y 也被称作一个数据小方( c u b o i d ) 1 2 1 。数据立方将数据 仓库中的数据组织成逻辑多维彤式，可以直观地支持通用的切片切块( 选择和投 影操作) 、i ：y 8 ( 增加聚集的粒度) 、下钻( 减小聚集粒度) 和旋转( 改变数据多维 视削的观察角度) 等o l a p 操作。 数据立方在不同类型的o l a p 系统中有不同的实现模式。o l a p 按照存储方式 f u 分为r o l a p 和m o l a p 。在m o l a p 中，数据以多维数组形式存储，可以直接支持数 w ：疗的多维概念模型。在r o l a p 中，数据以关系表的形式存储在r d b m s 中，一般 通过蛙型模式来支持数据立方的多维概念模型。星型模式中包含两类表：一类是事 典表，用来组织度量值以及各个维的码值，事实表往往很大，数据立方就是由此表 通过c u b eb y 算子计算得到；另一类是维表，分布在事实表的周围，用以组织在观 察，分析度量信息时所使用的维信息，相对于事实表来说，维表显得比较小。事实 华中科技大学硕士学位论文 表通过外键与维表中的主键联系在一起。为了加快o l a p 查询，一般预先部分或完 全汁算并实化数据立方，因此，r o l a p 中除了维表和事实表，还包含预先计算好的 较粗粒度的数据小方。 数据立方满足了o l a p 系统多维视图的需求。因此，数据立方概念一提出，就 引起r 学术界的广泛关注。学术界在数据立方的有关计算、索引存储、实化视图、 台询处理及优化等方面进行了大量的研究工作【3 - 5 l ，其研究成果很快在o l a p 系统中 使川，并与上钻( r o l l u p ) 算子1 6 】一起作为s q l 一9 2 标准在o l a p 方面的扩展，现在已 i i - 式被s q l 9 9 标准采用。所以现行的o l a p 系统无不把数据立方作为其构建的基础。 现在，国内企业对数据分析的需求也越来越大。科技信息分析系统是华中科技 人学数据库与多媒体技术研究所承担的科技部电子政务工程中的子项目，它要求建 ：在面向整个科技部的数据仓库之上，以数据立方为基本单元，面向分析，支持科 技郜管理中的决策制定过程。因此，厩对国内越来越大的数据分析市场，达梦联机 分析处理( d m 一0 l a p ) 系统将是一个重要的研发方向。d m o 【。a p 将是基于达梦关系数 据库管理系统( d m 3 ) 的r o l a p 系统，它以数据立方为核心，在d m 3 中利用星型模 式组织数据的存储，支持通常的o l a p 操作，可以作为一般o l a p 应用的支撑平台。 往r o t a p 中，o l a p 操作的实质就足多维聚集查询，这些查询往往需要对j - 亿条 汜录进行扛i 描、连接、聚集计算，而用户要求提交的查询能够在可接受的时间内得 到响应，这就对o l a t ，系统的查询性能提出了很高的要求1 7 j 。如果按照传统数据库系 统的查询处理及优化方案来处理这些查询，其响应速度很难满足用户要求。因此， 任我们的d m _ o l a p 系统中，必须针对多维聚集查询自身的特点，采用适当的查询处 理及优化技术，提高o l a p 性能，从而满足用户对响应速度的要求。本文的主要研 究目标是跟踪国内外多维聚集查询的处理及优化技术的发展动向，研发达梦联机分 机处理系统( d mo l a p ) 的多维聚集查询的处理及优化模块，提高科技信息分析系 统的分析效率。 1 2 国内外研究概况 蚓内外学术界关于多维聚集查询的处理及优化的研究重点主要在数据立方存 储组织及多维索引8 , 9 1 、实化视图技术【i o , t l l 、数据立方查询和星型查询f j 2 ，m 等方面。 华中科技大学硕士学位论文 本文主要围绕多维聚集查询处理、查询条件优化、数据立方查询的处理及优化和星 型查i 旬的处理及优化等四个方面进行了研究，因此重点介绍它们的研究情况。 1 2 1 多维聚集查询处理 刈于多维聚集查询处理的实现过程，现行的o l a p 系统一般分如下三个步骤。 1 多维区间生成：根据查询条件中指定的维表上的限制查询维表，生成维表 j 键值的多维区间。为了减小多维区间生成的代价，一般的做法是在维表上建立索 引，如b - t r e e 索引等。 2 数据立方查询处理：根据多维区间来查询数据立方，得到结果集【1 。其实 现过程可以描述为：首先确定查询所在的数据小方，如果该小方已经被预先计算， 则直接对该小方进行查询；否则在已被预先计算的小方( 包括最细粒度的小方) 中 找出能够响应该查询的较细粒度小方，然后重新生该小方上的多维区间，再根据这 一新的多维区间查询较细粒度小方，最后经过星型查询处理即时聚集计算得到结 粜。 3 星型查询处理：先是将结果集与各维表进行连接，然后进行分组聚集计算。 经过数据立方查询处理后，得到的结果集中只含各维的码值，用户并不知道这些码 值的含义。因此，数据立方查询处理后的结果集还要与各维表连接得到码值的描述 信息，如果是通过较细粒度小方间接查询的，与维表连接后还应按照用户要求进行 即时分组聚集计算，这个过程也称为星型查询处理。其中，结果集与各维表的连接 是中心表( 结果集) 与周边表( 维表) 之间的外键与主键的等值连接，也称为星型 连接i 】。 1 2 2 查询条件的优化 在现行r d b m s 中，对于查询条件为析取范式( d i s j u n c t i r en o r m a lf o r m ，d n f ) 的查询，即查询条件中含有0 r 逻辑运算符，一般采用以下3 种方案来处n t j 。 1 把原查询分解为不含0 r 的若干查询的并集。 2 先对每一个子条件生成位图索引，如对限制条件为s a l 3 0 的查 、咖则先生成s a l 3 0 两个位图索引，然后利用所有位图索引的逻辑加来找 华中科技大学硕士学位论文 剑符合任一条件的记录。 3 简单的把d n f 限制条件作为取得记录的过滤条件。 方案l 是最直观、最常用的方案，像m i c r o s o f ts q ls e r v e r 、s y b a s ea s e 、o r a c l e 8 等都吏持该方案。但是，当分解的子查询之问的交集非空时，则交集部分会被多次 重复查询，如果能减少或避免这种重复查询一定能大大提高查询性能。方案2 对于 较小数据集是一种非常有效的方案，支持方案的有m i c r o s o f ts o ls e r v e r 、o r a c l e 8 和s y b a s ea s i q 。但是当数据集较大时，生成位图索引的代价就会很大，会大大降 低整个查询性能。方案3 是最简单、最易实现的方案，它只是简单扫描整个表，然 后对每条记录用d n f 来过滤。显然，当数据集较大时，该方案是比较低效。o r a c l e 8 支持该方案。 对这个问题，现有的o l a p 系统一般还是采用上述的3 种方案，也没有很有效 的优化限制条件为析取范式的查询。 1 2 3 数据立方杳询的处理及优化 数据立方查询处理的具体实现与数据立方的存储组织有关。因此，近来对数据 0 ：方直询优化的研究主要集中于数据立方的存储组织。数据立方的存储组织要求既 要有利于快速响应查询，又要尽量节省存储空间，它包括数据立方索引和数据立方 小缩两个方向。 在数据立方索引方向，文献 1 8 ，1 9 总结了数据立方组织的主要途径，并且提 出1 r 尤其有利于对数据立方进行点查询( p o i n tq u e r i e s ) 的层次分裂立方森林 ( h i e r a r c h i c a ls p l i tc u b ef o r e s t s ) 。不过，它是一个高度冗余的数据结构，这使得它不 适合于大型数据库。d tn r o u s s o p o u l o s 等人提出了用c u b e t r e e l 2 0 1 作为数据立方的 存储抽象( s t o r a g ea b s t r a c t i o n ) ，并且用p a c k e dr t r e e s 来加以实现。c u b e t r e e 在存 储”销与查询性能之阃取得了较好的折衷，能够有效地减小存储开销，提高查询性 能，同时也利于快速更新。另外，针对数据立方的多维特性，建立各种多维索引， 如z k d b t r e e 【2 i l ，u b 1 h e 等。这些多维索引都是选取适当的多维填充曲线，如 z - o r d e r 、h i l b e r t 等1 2 3 1 ，把多维空间映射到一维空间，然后利用成熟的一维索引技 术，如b + t r e e 等，从而有效她对多维空间进行索引。 华中科技大学硕士学位论文 数据立方压缩的研究开始主要集中于对数据立方尺寸的压缩，主要是用来处理 数据稀疏问题1 2 4 _ 2 引。数据立方尺寸压缩的问题在于，响应查询的时候需要进行解压 缩运算，因而可能与聚集值的即时计算一样，带来用户无法忍受的响应延迟。后来 逐渐转向根据数据立方语义进行的数据立方浓缩，如c o n d e n s e d c u b e ， q u o t i e n t c u b e l 3 0 1 。c o n d e n s e dc u b e 利用基础单元组( b a s es i n g l et u p l e ) 构建一个完 全计算的、精确的( 可以提供精确的度量聚集值) 、精简的( 大大浓缩了数据立方 的尺、j ) 汇总立方，同时保持立方的语义( 可以无损地还原为原始数据立方) 和立 方格结构( 支持上卷下钻语义) ，支持一般的o l a p 应用。q u o t i e n t c u b e 实质跟 c o n d e n s e dc u b e 样，只是把c o n d e n s e d c u b e 支持的单调聚集函数扩展到非单调函 数，并给出有效的计算方法d e p t hf i r s ts e a r c h 。浓缩数据立方在响应查询的时候不 需要进行解压缩运算，因而大大加快了查询速度。 随着内存容量的飞速扩大，并且其价格迅速下降，出现了一些配备以g 计内存 的j ：作站，但现行的o l a p 系统都没有充分利用大容量内存。为了充分利用大容量 内存，k e n n e t ha r o s s 等人提出了基于内存的数据立方查询处理框架1 3 1 , 3 2 1 ，包括数 据j ) = 方的索引，数据立方的压缩和视阁选择等技术。他的总体内存结构是一个两层 框架结构：第一层组织结构为一个哈希表，所有装入内存的粗粒度的元组，通过统 。的哈希函数映射到该层；第二层存放最细粒度的小方的所有元组。 该框架对点查询的处理过程为：首先在第一层中查找( 利用组合哈希函数) 符 合查询条件的元组，如果该结果元组已被装入第一层，则直接返回该元组：否则， 转化为第二层的最细粒度数据小方上的范围查询，经过聚集计算得到结果。对于范 围查询，它首先都转化最细粒度数据小方上的范围查询，然后经过聚集计算得到结 粜。 出于该框架结构的第一层中统一存储来自不同数据小方的元组( 即含有不同 a j l 数目的元组) ，所以在该层上存在很多的a l l 占位空问浪费。另外，该框架选择 装入内存的粒度是元组级，这样不利于直接从第一层上快速响应范围查询，所有的 范围查询只能间接通过第二层响应。总体来说，该数据立方内存组织结构可以快速 响应点查询，但并没充分考虑到范围查询的性能，而范围查询又往往是比常见的， | i 比较费时的。 华中科技大学硕士学位论文 l2 4 星型查询的处理及优化 星型连接是星型查询的主要特征，它直是星型查询处理的瓶颈，也是近年来 鹫j 魁含嘲优化研究的热点。o n e i l 和g r a e f e 提出了一种的星型连接算法1 3 ”，它需要 每个维l ：都有索引，h 还要有从各维畦录i d 到事实表记录i d 的映射索引，因此该 辫法所需的额外索引代价较大。w i n i n g e r 针对星型模式的特点，提出一种适合于事 实表j ：没有任何多维索引的高效的选择和连接算法p u s h d o w n h a s hj o i n l j ”。 p u s h d o w nh a s hi o i n 的主要思想是：首先将各维上的限制条件的并集p u s h d o w n ，作 为jj 拙事实表的过滤器，一次性排除那些f i 会与任何个维连接的元组；然后对过 滤后的事实表与各维作选择和连接运算。对于火数据集的数掘立方来说，事实表上 般要建豇各种索引，否则扫描整个事实表的代价太大。对于纯粹的事实表与维表 之倒的外键与主键的等值连接操作，国内的蒋旭东利用星型模式中的维表较小的特 r _ 挺r 直舭的但很有效的矸i 需要任何索引的多表连接算法m h a s h j o i n 和 ms o t tj o i n l 3 5 j 。 分组聚集计算( g r o u pb y ) 也是星型查询处理中的一个重要环节。在传统的关 糸数拂i 库系统对g r o u pb y 的优化已有一套比较完善的数学理论和关系代数启发式 优化规则1 1 6 , 3 6 1 。另外，还一些具有针对性的优化算法，如y l e v y 等人提出了 m o v e a r o u n d 操作符，它主要针对含有多个查询块的查询，m o v e a r o u n d 可以移动 螽咖块1 3 7 1 。后米w e i p e n g 和l a r s o n 就决策支持应用中的聚集计算查询问题提出了优 化策略e a g e r a g g r e g a t i o na n d l a z y a g g r e g a t i o n i 3 8 ，它是在查洵树中上下移动g r o u p b y 操作符，它把g r o u pb y 操作放在某些j o i n 操作之i j i ，这样可以减少j o i n 操作中 的儿组数目。小过，e a g e r a g g r e g a t i o na n d l a z y a g g r e g a t i o n 仍然利用传统的关系代 数启发式优化规则来决定提前那些g r o u pb y 操作。 最近，k a r a y a n n i d i s 等对于基于层次聚簇p 9 j 的事实表的查询处理过程提出了 种坝分组变换( p r e g r o u p i n g ) 的优化方案【i ”。预分组变换利用层次代理键 ( t t i e r a r c h i c a ls u r r o g a t ek e y ，h s k ) 与维表层次属性的函数映射关系把部分g r o u p b y 提 i i f 到j o i n 之前，减少了j o i n 操作的元组数和g r o u pb y 操作的元组大小，并且 逊j 以避免小必要的j o i n 操作，从而同时减小g r o u pb y 和j o i n 的运算代价。它与 以附的利用关系代数等价变换的启发式优化规则的移动j o i n 操作符的算法有所不 6 华中科技大学项士学位论文 捌：后者在查询树中移动j o i n 操作符时不需要改变连接条件，而预分组变换需要改 变连接条件。但在有些情况下，额外增加的g r o u pb y 操作，会使预分组变换的代价 超过小进行预分组变换的代价。于是t s o i s 等人又提出基于代价的预分组变换优化 i i ，它使用一种代价模型来分别估算使用与不使用预分组变换的代价大小，让优化 器从中选择一个较好的方案。实施预分组变换的前提是星型模式中含有层次代理 键，所以需要对星型模式进行预处理：首先对维表进行h s k 编码且以该h s k 为 l + 键；然后在事实表中以各维的h s k 为外键。 1 3 课题主要研究工作 本课题名为：“多维聚集查询的处理及优化”，它是达梦联机分析处理( d m 一0 l a p ) 系统中的一个模块，并将应用于科技部电子政务工程中的科技信息分析系统。因此， 奉课题的主要目的是研究多维聚集查询的处理方案和优化技术，设计并实现 i j m 一0 l a p 系统的多维聚集查询的处理及优化模块，提高d m 一0 l a p 系统的查询效率， 改善科技信息分析系统性能。 本课题主要研究工作包括： 1 研究现有国内外多维聚集查询的处理及优化技术，提出或采用适合本系统 的查询处理及优化方案； 2 提出多维聚集查询条件优化策略，重点解决查询条件为析取范式的优化问 题； 3 设计并实现基于内存的数据立方存储组织方案，实现高效的数据立方查询： 4 采用合适的星型连接和分组聚集算法实现星型查询处理，并利用预分组变 换来技术来优化星型查询处理。 华中科技大学项士学位论文 2 1 引言 2 多维聚集查询的处理及优化 本课题“多维聚集查询的处理及优化”是d m _ o l a p 系统中的一个模块，并将 心h jj 二科技部电子政务工程中的科技信息分析系统。d m o l a p 系统是基于达梦数据 库管理系统的o i 。a p 应用的通用平台，它以数据立方为核心，支持通用的o l a p 操作， 如上卷、下钻、切片切块、旋转等。科技信息分析系统建立在面向整个科技部的 数据仓库之上，以d m _ o l a p 为支撑平台，支持科技部管理中的决策制定过程1 4 “4 “。 整个系统包括数据提取子系统、科技信息数据仓库子系统、d m o l a p 、i j 台分析工 具等。各子系统的相互关系如图2 1 所示。 i 鳘| 2 1 科技部信息分析系统体系结构l 笙| 往以数据立方为核心的r o l a p 中，o l a p 操作的实质就是对数据立方的多维聚集 垒询。由于数据立方的数据量都非常大，多维聚集查询是复杂费时的操作，往往需 要对上亿条记录的数据集进行扫描、连接和分组聚集计算。为了能够快速响应用户 查询需求，o l a p 系统必须针对多维聚集查询的特点，采用合适的查询处理方案及优 化技术。因此，多维聚集查询的处理及优化模块的好坏直接影响了d m o l a p 系统的 整体性能，将决定科技部信息分析系统的成功与否。 华中科技大学硕士学位论文 2 2 数据立方 2 2 1 基本概念 数据矗力也被称作多维数据集( m u l l id i m e n s i o n a ld a t as e t ) ，它强调提供用 户数捌的多维视图，即允许用户从各个角度观察和分析感兴趣的数据。在o l a p 分 杌环境卜- ，我们把观察数据特定的角度称作维( d i m e n s i o i l ) ，例如，企业常常关心 产订i i 的销售数据随时问推移而产生的变化情况，这时，他是从时l 、日j 的角度来观察产 。j 6 的销售情况，所以时问就是一个维( 时i t 日j 维) ，企业也常常关心自己的产品在不 川地区的销售情况，所以地理分布也是一个维( 地理维) 。把所观察的目标称作度 量l m e a s u r e ) ，一般情况下，度量总是一个数值量，例如：“销最”、“利润”、“成 套”等，凶此，用户可以对度景进行必要的计算，如平均、综合等等。通常，人们 观察艘量的维存往鲺i i 节程度刁i 同的多个描述方面，我们将维的多个描述方面称作维 的止：次( i t ie lu r c h y ) 关系，如时i 剐维的年、季度、月份和同期构成时问维上的一个 层次关系，l 司样，幽家，地区和城市构成了地理维上的一个层次关系。层次关系反 映j h j 户观察和分析数据时的一种习惯，即从大粒度级数据着手，逐步下钻到细粒 度线数据。以“0 问维为例，用户首先观察年度卜的销售数据，看看年度的销售数据 是 r 柯异常情况发生，如果某年的销售数据异常，那么卜钻到该年的季度销售数据， 看看足某个季度还是所有的季度出现了销售情况异常，如此等等。 墨毓 毒c m m t o o t h l m a o s o a p l23 s6 1 d a l e 7 1 81 中竹岫1 1 册 舢口t c r c a l e g y s t a l e i i i i o n t h p r 0 4 u c t c i t y i 卫甜 o l n 嘲d a ：h i 盯耐c h t c a l s u r m c i z a t i o np t t h i 茔| 2 2 超市数据立方s a l e 图2 2 是。个超市数据立方的示例。时间，产品和地理数据立方中的3 个维， 任t l 、m j 维l 面有4 个层次粒度：y e a r 一 q u a r t e r 一 m o n t h 一 d a t e = 在产品维上有3 个 层次粒度：i n d u s t r y 一 c a t e g o r y 一 p r o d u c t ；在地理维上有3 个层次粒度： l i u t i l t 【 y 一 s t a t e 一 c i t y 。在图2 1 所示的多维空l 、日j 中，每一个单元( c e l l ) 是由不 华中科技大学硕士学位论文 同的( p r o d u c t ，c i t y ，d a t e ) 取值所决定的度量s a l e s 。 2 2 2 实现方案 在逻辑上，数据立方以多维方式组织企业中的历史数据，并提供一套完备的多 维代数操作，用以操作数据立方。但是，在物理实现上，数据立方既可以基于多维 数据库技术，也可以建立在关系数据库技术之上。 多维型数据立方是近来应多维分析的要求而产生的，它以多维数据库为核心， 直接支持数据的多维视图，多维数据库在数据存储，检索以及综合上有着关系数据 库不可比拟的优势，但是，多维型数据立方在适应分析维数动态变化，适应数据变 化，适应大数据量和适应软硬件能力方面赶不上关系型数据立方。 关系型数据立方以广泛应用的关系数据库技术为基础，使用关系表存储数据立 方的数据，在技术成熟度以及各方面的适应性上较之多维型数据立方占有优势，是 l j 的常用的数据立方实现方案。但是，关系型数据立方也有它固有的缺点，即数据 方提供的多维模型和多维代数操作必须转换成相应的关系表和s q l 查询。 一种折衷的数据立方实现方案是综合上述两种数据立方实现方案的长处，采用 关系数据库存储海量的基表数据，采用多维数据库存储聚集数据，这就是混合数据 方。对于混合数据立方来说，如果钻敬到事实表，那么响应速度比较慢，但它可 以迅速从聚集中获取信息。许多公司把他们的历史数据分成两组，即现存历史数据 和存档历史数据。现存历史数据使用率高，覆盖期不超过2 年；存档期历史数据使 h j 较低，覆盖期为2 年以前。由于存档期历史数据一般要跨越许多年，甚至几十年， 数据量可以很多，由于这些数据不会被经常查询，因此，与使用关系数据立方存储 所具有的优势相比，关系数据立方较低的效率则显得无关重要。而现存历史数据的 分析频率较高，对效率的要求是第一位的，因此一般采用多维数据立方。 在日i i 的o l a p 分析服务器市场上，s y b a s ei q 、i n f o r m i xm e t a c u b e 中的数据 立方是关系型的，而o r a c l ee x p r e s ss e r v e r 、e s s b a s e 选择多维数据库实现数据 立方；丽 f i c r o s o f ta n a l y s i ss e r v i c e 支持3 种方式的数据立方实现技术，用户 可以根据实际的需要选择相应的数据立方实现技术。 所以说，关系型结构能够较好的适应多维数据的表示和存储。关系数据库将数 0 华中科技大学硕士学位论文 锯、：方 奉现的多维结构组织成两类表，一类是事实表( f ，a c tt a b l e ) ，用来组织度 量值以及各个维的码值，事实表往往很大，经常存储上十年的历史数据；另一类是 维丧( d h n e n s j o nt a b i e ) ，分稚在事实表的周围，用以组织在观察，分析度量信息 h 、j 所使用的维信息，相对于事实表来说，维表显得比较小。对于每一个维来说，有 个表用来保存该维的元数据，即维的描述信息，包括维的层次属性以及其它属性 等。事实表通过事实表中的外键和维表中的主键联系在一起，该结构被称之为星型 模式，采用这样的结构能够体现数据的多维特征，图2 3 所示的就是个星型模式 的例f 。 i 笙i23 星型模式 星型模式并没有对维的层次关系提供显式的支持，雪花模式对星型模式中的维 表进 jj ，绌化，维的层次关系清楚地展现在雪花模式中。从星型模式转到雪花模式 的，j 法就是规范化维表的过程，雪花模式的例子见图2 4 。 图24 雪花模式 户妒旧凰曲鲴 ， 篙囊一 瓢凰豳 华中科技大学硕士学位论文 采_ 】规范化的雪花模式使得维表占用较少的空问，同时，维表的维护变得更加 容易。但足，规范化的雪花模式并不适合于o i a p 分析环境的，它要求更多的连接 ( in ) 操作，| m 连接操作足关系数据库中最费时的操作之一，因此，雪花模式大 人降低了查询响应的速度。 根据以上分析，在d mo l a p 主要采用基于星型模式的关系型的数据立方实现 方案，所以本文所讨论的多维聚集查询的处理及优化是针对基于星型模式的关系型 数 】l t ：、 方。 2 3 多维聚集查询的处理及优化 2 3 1 多维聚集查询模板 丛f 数据矗方的多维聚集金询的般特征是：在多个维上加限制条件，根据这 螳维j ：的限制条件查询数据立方，然后把数据立方查询的结果集与多个维表进行外 键jl i 键的等值星型连接，最后进行分组聚集计算。一般的多维聚集查询可以用如 图25 所示的查询模板来表示。 s e l e c t s g a ，a g g r f r o mc u b e d w h e r ej ca n dl p a n dm p g r o u p b yg a s g ：选择的事实表的度量或维表的属性； a g g x ：事实表的度量上的聚集函数，如m l n 、m a x 、c o u n t 、s u m 、a v g 等； c u b e ：数据立方； d ：维表； j c ：事实表与多个维表之问的外键与主键的等值连接： l p ：维表上的限制条件； m p ；度量上的限制条件； ( ；a ：分组属性。 蹦2 5 多维聚集查询模扳 幽2 6 多维_ 聚集查询语句m d o 华中科技大学硕士学位论文 例如，针对图2 2 所示的数据立方，如图2 6 所示多维聚集查询语句m d q j 就表 小个对数据立方的切片操作。 2 3 2 多维聚集查询的处理及优化 今系统对多维聚集查询的处理采用典型的查询处理方案1 2 - t 4 ，主要包括3 个步 骤，它们依次为：多维区间生成、数据立方查询处理和星型查询处理。其流程如图 27 所_ i 。 f g r o n ps e l e c t 1 ll s t a r _o 。2j一 ( ) ic u b e 卜_ c u b e _ q u e r y p r o c e s s i n g 数据立方杏淘处理lj t 【m n i t i d i m e s i 。n _ i _ r a n g e _ c r e _ t i n g 】 ，土、，、 多维区间生成 亩自 卧从 | ! c | 27 多维聚集查询的处理流程 第l 步，多维区i 剞生成：根据查询条件中指定的维表上的限制条件( 图2 5 中 的jp ) 查询相应的维表，生成维表主键值的多维区浏，用逻辑运算符 m i j ll i 【】i m e n s i o n a 一r a n g e c r e a t i n g 来实现。 为了减小多维区间生成的代价，一般的做法是在维表上建立索引1 2 3 1 ，如w - t r e e 索t ；| 等。由于多维区间生成自身运算代价较小，单优化该运算符对多维聚集查询性 能的提高并不会很明显，所以本文从多维区间对后面步骤的影响的角度来进行优 化。j 数据立方查洵条件是析取范式( d n f 。d is j u n c t iv en o r m a lf o r m ) ，且d n f 1 备合取范式( c n f ，c o n j u n c t i v en o r m a lf o r m ) 之i 刈的交集非空时，如果直接根 华中科技大学项士学位论文 妣i ) n f 米进行多位区剧运算，则会生成多个相交的多维区间，且交集部分会被其后 的数扒矗一仓询处理多次重复查询。如果能减少或完全避免这种重复查询，则会大 人减小数据立方查询处理的代价，提高整个多维聚集查询的性能。 针对这一途径，本文将在第3 章提出一种多维聚集查询条件优化策略互不 榭交等价变换1 4 ”( e q u i v a l e n td i s j u n c t i o nt r u n s f o r m a t i u n ) 。互不相交等价变换是在 赳jj 多维l x m ，l 成之i i i 对查询条件作的一种等价变换，它把d n f 变换成等价的互不 斗史的矗，j 格，根捌这些直力+ 格生成的多维区也就n 不相交。这样优化后不但可 以棒省交集被重复