用于OLAP的视图大小估算算法比较与分析

OLAP系统中的视图物化操作，要求快速、可靠而精确。许多视图大小估算技术利用特定的统计假设，其误差可能较大。基于概率的估算方法在速度方面可能较慢，但是在估算大视图时精确度和可靠度较高，而且使用内存较少。论文中介绍了几种基于散列的视图大小估算方法，并进行了实验加以分析对比。实验结果表明，修正算法(Adaptive Counting)不管视图大小如何均提供精确的估算，而且当增大存储预算时仍可保持较快的估算速度。

OLAP 系统中，频繁需要在大规模数据仓库上进行复杂的查询，为了提高查询速度，往往需要事先物化一些视图。视图物化是提高数据仓库性能的最有效技术之一。物化了的视图是一种通过预计算中间结果来提高数据访问的物理结构。进行视图物化首先要解决视图大小的估算问题。

近年来对于视图大小的估算研究很多。典型的OLAP 查询由选择和聚合数据(通过GROUP BY 语句实现)构成[1]。通过预计算，许多似是而非的组集可以避免由于大数据表上的聚合引起的响应速度减慢。

许多查询，如那些包含条件(HAVING clause)可以利用预先聚合加快计算速度。然而物化视图需要额外的存储空间。而导致在数据仓库刷新时产生维护开销。此外，视图的数据量很大：在一个d 维的数据立方体中，视图的数量是2d[1]。因此，在数据仓库的物理设计中物化视图的选择是非常重要的，是一个NP困难问题[2]。一些视图大小估算技术假设数据的分布是“谦虚”的，通常假设是均匀的分布[3]，但是任何数据分布的偏差均将导致过高的估计结果。

一般的， 当统计假设估计量较快完成计算那么代价最大的步骤可能是随机抽样。

其误差可能比较大， 且不能成为被束缚的先验。这里将讨论基于概率的估算(Probabilistic Counting) [4]、重对数概率估算(LOGLOG Probabilistic Counting) [5]、修正算法(Adaptive Counting) [6]。代价相对大、相对平易的估计量倾向于提供较高的精确度和可靠性[7]。

为了使用这些技术，需要将列进行快速散列(Hashing)，理论边界需要至少两两独立的散列值。幸运的是，当在数据立方体中具有较多维数(d > 10)每一维值相对可用内存来说通常是小的。因此可以对每一维分别进行散列。将结果存储于主存之中，将这些完全独立的一维的散列值合并为独立的d 型多维散列值。

当分配较多单元时，算法更为精确，但速度减慢。文章中设计了两种使用场合，一种情况是期望粗略估计，误差可达10%，尽可能的快速估算，这时可使用较小的存储预算(少于1 MB)；另一种情况是期望精确计算，误差小于1%，甚至0.1%，这时使用数MB 的内存。

2. 多重分型模型的估算 这里在多重分型模型之上实现了各种算法[8]。给定一个样例，对于多重分型模型所有需要研究的是每个样例F0 中相异的元素数量，样例N’中的元素数量，所有元素的总数N，以及样例mmax 中最频繁出现项的数量。因此，一种简单的实现是可能的(见Algorithm 1)。算法内存的使用由取样上的GROUP BY查询决定(line 6)：通常，一个较大的样例将导致更为重要的内存使用。

3. 随机散列 散列以随机的方式进行。

从元组)0 2L， 的散列函数中。L 是定值(32L =或64L =)在( )()1 2LP h xy==