Page History

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

介绍

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

...

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

创建样本表

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

...

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

生成值/频率对

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

...

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

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

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

创建等高直方图

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

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

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

...

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

创建最终等高直方图

最终直方图展现了在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.

...