基于浓缩数据立方的内存实化数据立方的构建

联机分析处理应用需要对大量数据进行聚集计算，对系统的查询性能有较高要求，若预先计算并实化数据立方，就可缩短查询响应时间，但在外存存储实化数据，仍会带来大量的I／O操作。随着内存价格逐渐的降低，将数据立方的一个子集在内存实化，使其能够在不访问硬盘的情况下快速有效地回答所有查询，将特别适用于有时间约束的联机分析处理环境。另外，当有新的元组加入或更新元组时，不需要进行大量I／O来更新硬盘数据，而只需更新内存数据，降低了维护代价。研究内存实化数据立方，粒度是元组级的，但考虑的是一般立方元组，没有结合数据立方的浓缩特性，因此，本文利用数据立方的浓缩特性来进一步提高内存的使用效率。

1内存实化方案

由于没有足够的内存空间存储整个数据立方，因此采用浓缩数据立方，以提高内存空间的使用效率，这样原先完整的数据小方被拆分，分别放在对应的常规小方以及若干虚小方中。假设可供实化的内存空间至少能够容纳最细粒度数据小方，这个前提保证了在不进行内外存交换的情况下，完全利用内存数据响应所有的查询。并且在有多余空间的情况下，还可选择较粗粒度的小方元组在内存实化，从而直接响应一些查询，采用两级存储结构(如图1所示)，最细粒度数据小方的所有元组都存储在Level-1中(Level-1是一个含有若干槽孔的一维数组)，Level-2用于存储粗粒度的元组，是一个Hash表结构，利用选定元组的各个维值构造组合码K进行散列，V是元组的聚集度量值。

1.1Level-1存储的优化

假定一维槽孔数组大小为T，可以把一个一维的数组看作是d维的数组S，数组的各维下标是b1，b2，…，bd，满足的条件是b1b2…bd≤T。构造d维映射函数h1，h2，…，hd，其中函数hi将第i维上的维值映射到数组S第i维的下标范围1，2，…，bi中．一条元组(v1，v2，…，x)，其中vi和x分别是维值和度量值，将会映射到槽孔S[h1(v1)，h2(v2)，…，hd(vd)]。这条元组将会被存储在该槽孔中保存的链头所指示的一条链上，同样，所有最细粒度的元组都被这样存放，Level-1的一个主要作用就是支持范围查询。

a．选择bi的值

Level-1数据结构中的重要参数是每个维的下标的范围bi，若让bi的取值趋近于平衡，则有bi≈T1/d。．若某个维i的基数比bi还要小，则减小bi，让其他维的下标范围bj增大，平衡bi取值的目的是为了缩短平均响应时间。

b．优化槽孔数组的大小

希望得到时间性能较优的槽孔尺寸，含有较多ALL值的查询将是平均时间代价的主导因素。令k表示查询中ALL值的个数，假定bi之间均衡分布，并且每个槽孔对应链表中的元组数目也是均衡分布的。对于在Level-2没有得到响应的查询，需要访问的槽孑L的数目是Tk/d，整个查询的时间代价

式中：n是最细粒度元组的个数；s是访问一个槽孔的时间代价；l是存取链上一个元组需要的时间。当T＝nl(d－k)／(ks)时，式(1)的时间代价函数可以取得最小值。例如取k＝d／2，l＝s，槽孔的数目就等于最细粒度的元组的个数，当可用的内存空间受到限制时，由于没有足够的空间满足时间最优的选择，因此槽孔数组的大小将小于能够达到时间最优的数组。

c．hi函数的构造

Hash函数hi应尽可能均衡地分配元组到下标值1，2，…，bi中，避免槽孔结构中出现过长或者空的链。预先计算单个属性上的属性值的分布，据此调整hi，避免映像值过于集中。由于Level-1是进行范围查询(点查询在Level-1同样也是按照范围查询求解)的，因此若能够做到元组Hash之后的保序性，将是很好的选择。若某个维i的维值v1＜v2，经过Hash函数hi之后，hi(v1)＜hi(v2)，则称Hash函数hi具有保序性，范围查询通过嵌套的循环即可实现。

构造一个简单的Hash函数来实现这样的保序性。如果设定链长最大值为常量L，c[i]表示维i的基数，那么该维的下标范围bi＝c[i]/L。如果某一维i上的基数是1000，L＝100(也可以是其他的常数)，那么bi＝10。该维的Hash函数就是：维值1～100对应下标值0，101～200对应下标值1，…，其他维的Hash函数依此类推。

1.2Level-2中数据的选择存储

a．元组的选择模型

查询的概率模型主要有均衡概率分布模型和基于计数的分布模型。有两方面因素决定元组选择的优先权：一个因素是首先实化含有较多ALL值的元组，也即聚集度高的元组，从而提高空间利用率和减少计算代价；另一个因素是优先实化查询概率高的元组，这两个因素通常是相容的，聚集度高的元组往往查询的概率也较高。

使用在Level-1查找一条元组的时间代价作为该元组在Level-2存储的效益值。假定p是含有k个ALL值的小方i中的一条元组，其中pi,j是元组t被访问的概率，那么，在Level-2实化元组p的效益值

根据式(2)，一旦某个粒度的元组被选中在Level-2实化，紧接着就是相同粒度的其他元组。在空间允许的情况下，同一小方的元组可能接连被实化，因此，考虑按照小方来选择以简化实施，并使用1bit来标记那些已经完全实化的小方。为了按照小方进行选择，可以给出一个近似：每个小方内部所有的元组的查询概率相等，这也是将聚集度和查询概率统一起来的一种方式。

式中：Cj是含有k个ALL值的小方中第j个小方；Bcj是k的指数函数，与︱C︱是线性关系。优先选择聚集度高的小方中的元组；在聚集度相同的情况下，考虑尺寸小的小方中元组，而且虚小方和常规小方被放在一起进行选择。不同于一般小方级别的选择，其存储结构仍然是元组粒度，并按照元组单个存储，不会因为某个小方的整体尺寸太大而使小方中的所有元组都不能被实化。

b．Level-2结构的实现

Level-2采用Hash结构，关键问题是解决冲突，考虑各个小方的元组按照小方的不同分开存储，即首先按照小方编号进行散列。这样做只需要存储小方元组的有效数据，不需要保存它们的分组属性信息，从而避免小方之间元组Hash结果冲突的情况。例如(1，*，*)和(*，1，*)，即使采用最简单的Hash函数，由于它们存放在不同小方的桶中而不会发生冲突。对于同一小方中的冲突元组，采用冲突链的方式解决，并按照每个小方的元组数目适当分配桶的数目，避免出现很多空桶的情况。
2内存数据立方的查询

针对数据立方的查询分为范围查询和点查询两种。范围查询为若干个维限定了取值区间，若这个区间对每个维而言都只包含一个点值，则就是点查询。点查询的结果若存在，是单一的一条立方元组，则这样的查询可能在Level-2得到解。

2.1点查询处理

在浓缩数据立方中，由于基本单元组构成的虚小方的存在，通过新的查询分解方式，查询求解过程可能更简单直接。这里采用源表SALES(date，product，customer，amount)来说明点查询的查询分解和处理过程。

例1(查询Queryl)
SELECTdate，customer，amounts
FROMCube(date，product，customer，amounts)
WHEREdate：[3，3]，customer：[12，12]；

在未浓缩的数据立方中，Queryl需要向小方cuboid(date，customer)提交查询。在浓缩数据立方中，因为基本单元组归人相应的虚小方中，所以点查询仍然需要进行查询的分解。查询Queryl需要顺序访问V-cuboid(date)，V-cuboid(date，customer)和常规小方cuboid(date，customer)，若其中一个得到结果，则查询可以返回。若执行了等价查询的全部三个子查询，仍然没有得到结果，则需要根据不同的情况区别处理。若三个子查询中涉及的小方都已经在Level-2中完全实化，则说明数据立方中不存在合适的元组。若查询中涉及的小方没有实化或者没有完全实化，则要到Level-1按照范围查询进行求解。

2.2范围查询处理

由于Level-2是按照Hash方式进行存储的，不支持范围查询，因此对于范围查询必须到Level-1进行求解。同时在Level-2没有得到解的点查询，也需要在Level-1求解。对于一个限定若干维上下界(可能含有若干ALL值)的查询，首先按照各维的Hash函数，求得对应维的上下界的下标，对于取ALL值的维，按照立方中该维的最小值和最大值求上下界的下标，其实就是该维的下标边界范围。之后，按照各维的下标求得对应的槽孔，遍历这些槽孔，筛选并且聚集适当的元组，从而求得查询结果。

例2一个6维的数据集，一条查询前2维取ALL值，后面的4维被限定。假定被限定的维值v3，v4，…，v6通过h3，h4，…，h6分别被映射到y3，y4，…，y6，且假定前2维的下标范围分别是b1和b2。

算法1从Level-1计算聚集元组

输入：点查询的查询条件；
输出：查询结果total；

算法描述：
Initialize(total)；／*forsum，wouldbe“total=0”*7
For(xl＝1；zl≤b1；x1＋＋){
For(x2＝1；z2≤b2；．x2＋＋){
Foreachtupleintheliststartingats[x1][x2][y3][y4]…[y6]{
IfthetuplematchesthequeryAccumulate(total。aggregate_value)；

算法1给出了该查询在Level-1的求解过程,从中可以看到，仅需要遍历b1×b2条链，这对于完全扫描而言是一个很可观的改进。3实验结果分析

实验在赛扬1.8GHz，512Mbyte内存，40Gbyte硬盘的PC机上进行，采用的数据集是真实大气数据集，源表数据取4维，10000条元组，构造的查询是具有一定随机性的、数据分布比较均衡的点查询，每个小方lO条查询。

图2和图3是按照聚集度和小方尺寸相结合的选择方法，在数据集增大的情况下，分别基于浓缩数据立方和普通立方的查询性能的实验结果比较。结果显示，在数据集比较小时，例如源表数据取1000条元组，基于浓缩数据立方的内存实化方法效果没有基于普通立方的内存实化方法好。其原因在于：数据量比较小时，不能发挥浓缩数据立方的节省空间的优势，同时由于查询分解的存在，导致性能不如普通立方。随着数据量的增大，浓缩数据立方的内存实化方法效果比普通立方好。

在实验过程中，L的大小影响到了Level-1中Hash桶的多少以及Level-2中槽孔的多少。如果取太大会出现很多空桶，那么需要处理的槽孔数目也增多，时间性能不好；但是如果L取太小，每一条链上的数据过多，那么会造成很多不必要的数据的扫描，因此链长参数L的设定要适中。

转载：感谢您对网站平台的认可，以及对我们原创作品以及文章的青睐，非常欢迎各位朋友分享到个人站长或者朋友圈，但转载请说明文章出处。