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

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

1 内存实化方案

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

图1 两级存储结构示意图

    1.1 Level-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.2 Level-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函数，由于它们存放在不同小方的桶中而不会发生冲突。对于同一小方中的冲突元组，采用冲突链的方式解决，并按照每个小方的元组数目适当分配桶的数目，避免出现很多空桶的情况。