注意: 该页面中描述的功能为在Trafodion 1.1发行版本中技术预览(完成但未经测试)的功能。

介绍

Trafodion需要详细、准确的统计数据，以便能够执行基于成本的查询优化。这些统计数据以反映数据值的分布，唯一值数量以及高频(倾斜)率的直方图形式组成。产生这些统计数据的成本一直是Trafodion和其源系统的一个疑难问题。许多性能改进已被实现，但更新统计信息仍然是许多应用程序的瓶颈。统计数据收集的基本方法包括扫描表 (通常选择样本行)，排序、 分组和收集对每一列生成等高直方图的时间间隔。这些资源密集型操作受限于完成整个任务的速度快慢。此外，随着表的内容随着时间推移不断变化，必须重复整个过程以更新直方图，防止直方图变得陈旧而不再准确表示当前表内容。

这份蓝图描述了一种构建直方图，同时保留现有的直方图形式的替代方法。该方法不通过对数据进行排序和分组，而是使用Counting Bloom Filter（CBF）来记录不同值的出现频率，用于生成直方图的间隔，并推导出估算UECs（唯一条目计数）所需的频率值分布情况。

在这份蓝图中提出的首要工作便涉及最初由批量导入表时生成的统计信息的初始集合。它包括添加更新统计信息作为批量导入实用程序的可选任务 (最初由CQD控制，但可能在将来以通过修改批量导入语法的方式实现)，创建样本表，该样本表通过随机选择行写到Hive表中，并与新的“快速统计”算法和CBFs相结合，来创建基于批量导入结果的对于列的直方图。后续工作将使样例表持久，且当HBase刷新机制从MemStore创建新HFile时更新样例表(可能包括直方图)，但这项工作将会在发行版1.1完成后进行。

创建样本表

当先前为空的表通过Trafodion批量导入实用程序填充后时，将以默认采样率随机抽取行写入样本表。样本表将在一个固定的目录以外部Hive表的方式存储，该表包含了它所表示的HBase表的全称域名的命名约定。选择Hive表作为样本表是基于Hive表高扫描率的考量。

一个小的所选样本表 (样本表的样本)，将用于形成一个对每一列总体UEC的粗略估计。创建 CBF的参数之一是n，为筛选器代表的的键(不同的值)的预期数量。如果 n远低于实际唯一值的数量，由筛选器检测到的不同值的数量将会太少而频率过高。如果n远高于实际的键值数量，该筛选器所需的内存会过度，从而可能限制直方图在样本表单个传递中的产生数量，且需要额外的I/O。正如对于表列的最终UEC估算是对样本表中的数据使用线性加权组合(linear weighted combination，LWC)得到的，我们对于列给出的n值是根据子样本表的数据导出的。在子样本中每个不同值的发生频率被用来构建一个频率的频率数组，f'。此数组的元素值，例如f'[2] = 10，被解释为“有10个不同值在样品中出现两次”。对于子样本所需的频率信息，CBF将被使用(其自身的n值被设置为样本大小)，但如果涉及到的数据量较小，对频率的哈希表映射值可能会被使用。

用来计算每列CBF的n值，和以直方图存储的UECs值的是Jackknife and Schlosser线性加权组合（LWC）。这也是现阶段更新统计数据时使用的预估方法。

生成值/频率对

当批量加载已完成且样本表已就位,便可以开始对表列生成直方图的工作了。余下的步骤将会以生成一个直方图的形式来描述，但应指出,现行的内存压力，可以从示例表的单次扫描读取多个列来缓解。

样本表每列的值都会在列的CBF中被计算。值会被k种不同的哈希存储(通常情况下，k = 5)，每个哈希函数有从0到m-1的值范围，m值为CBF的计数器的数量。在这些k索引上的计数器会增加，频率的值是那些 k计数器值的最小值。使用多个哈希函数，以最低的计数器值为频率来减少碰撞的影响，避免了频率值的过度计数。一般而言，选择的CBF参数会使过度计数发生的情况低于1%。

除了在CBF中注册每个值的频率，我们也保持跟踪最小值和最大值，由此知道要由列的直方图表示的值的范围。每个不同值在第一次注册到CBF中时也会被添加到列表中。

完成对样品表列的所有值扫描后，我们将有以下信息:

  1. 列中包含不同的值的列表。
  2. 通过CBF可得知这些不同值的发生频率。
  3. 列中包含的最小值和最大值。

创建等高直方图

虽然最终的目标是等高直方图，创建等宽直方图的中间步骤生成了一个部分排序的数据而不用对所有数据进行排序。知道列中所包含的最小值和最大值，我们可以将值域分割成等宽间隔，通过一个简单的计算将每个不同值分配给合适的间隔。就我们的目的而言，将一个值分配给间隔需要执行下列操作:

  1. 增加间隔的UEC。
  2. 将发生频率值(从CBF中得到)添加进间隔的行计数中。
  3. 如果值过界，更新间隔的最小最大值。

宽度相等的概念需要域的任何两个值之间的直线距离的测量。要使这对于字符类型和其他非数字 (例如，日期时间，时间间隔) 的类型成为可能且更易于测量，值被分配给等宽直方图之前会编码成保留原始数据排序的双精度形式。最小和最大值也会编码成这种形式。对于值v而言目标间隔为(e(v) - min) / Iw，其中e为编码函数，Iw为等宽直方图中间隔的个数。

频率也被用来当做一个频率的频率数组的索引，该索引上的数组元素是递增的。这个频率的频率数据被用于LWC和样本表的UEC来估计全表的UEC。

计算等宽直方图的公式中含有部分排序的数据;对一个给定的区间，虽然所含的值并未排序，但每个值都大于前一个间隔中的任何值且小于后一个间隔中的任何值。现在等高直方图就能从等宽直方图中推导得出。

创建最终等高直方图

最终直方图展现了在Ih时间间隔内尽可能均匀的值频率（非不同值）。Iw应该比Ih大;Iw比Ih越大,则越少的不同值需要被排序。知道值发生频率次数和所需的间隔数，我们可以确定最终等高直方图中的目标频率次数。每个不同值必须由一个单一的间隔来完全代表，因此它通常是不可能确切地为每个间隔达到目标高度。一个单一的不同值的频率甚至可能会超过目标高度，并将赋予它自己的间隔。

宽度高度转换过程如下。从等宽直方图的第一个间隔开始，后续每个间隔的行计数会被累加，直到在某个间隔上累加的值会超过等高直方图的目标值。该间隔必须从等高直方图的第一和第二次间隔之间拆分。由于由间隔组成的非重复值是无序的，他们必须进行排序，最低值被添加到第一个等高间隔直到它填满(即，达到目标高度)。剩余的值分配给第二等高间隔，其中的最低的值被保存为第二间隔的边界值。我们重复该处理方式，直到等宽直方图的所有间隔已都分发给等高直方图。

最后一步，与原始的更新统计算法相结合，是将行计数和UEC扩大，使其代表全表，而不是样品表的估计数。虽然这是一个简单的基于采样率的行计数的缩放操作，UEC估算则更复杂，并由上述的LWC算法估计得出。

参考

Qifan Chen, Hans Zeller, Ram Kosuru, "Fast Construction of Histograms with Counting Bloom Filters", submitted to HP TechCon 2014, May 2014.

Li Fan, Pei Cao, Jussara Almeida, Andrei Broder, “Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol,” IEEE/ACM Transactions on Networking, Vol. 8, No. 3, June 2000.

Deolalikar Vinay, Choudur Lakshminarayan, "An Estimator of UEC in SQL/MX based on Skewness", HP Internal Presentation, 2006.

 

  • No labels