更多精彩内容：请登录：ke.sandata.com.cn
前言
HLL是 HyperLogLog数据结构的简称。PostgresSQL通过插件的方式引入了这种新的数据类型hll。HyperLogLog是一个具有固定大小，类似于集合结构，用于可调精度的不同值计数。例如，在1280字节的hll数据结构中，它可以在很小的误差范围内估算出数百亿的不同值计数。
算法
hll可以被视为层次结构的不同集合/不同值计数算法的组合，并向上移动该层次结构的规则。为了区分上述描述算法，将其命名为以下:
♠ EMPTY
表示空集的常量值
♠ EXPLICIT
集合中确定的，唯一的，排序完整的整数列表，该列表保持一个固定的基数
♠ SPARSE
HyperLogLog是基于映射的“惰性”实现，是一种基于概率集合的数据结构。仅将非零寄存器的索引和值存储在 map中，直到非零寄存器的数量超过固定的基数。
♠ FULL
HyperLogLog是一个完全物化，基于列表的实现。它将每个寄存器的值显式存储在按寄存器索引排序的列表中。
基本概念
- 基数计数
用来统计一个集合中不重复的元素的个数。
- 基数计数实现
假设一个集合为Su,用列举法表示{2,3,1,4,5,9},如果此时有一个新的元素Xi=3要加入到集合Su中。如果Su中包含该元素,那么该元素将不会被加入到集合Su中，否则，加入该元素到集合中，计数值为Su，即基数值为元素的中非相同值的个数。如集合中{1,2,3,5,2}，基数为4，因为2是 DV（Distinct Value），不被计算到基数中。
该实现有两个问题：
- 当集合无限增加，元素增多时，相应的存储内存也会无限增长
- 当集合无线增加，元素增多，判断是否包含待加入元素的成本也将增加。
实现动机
最初扩充原始HLL算法如下：
- 一般情况下，一个HLL占用 regwidth * 2^log2m 位存储。
- 典型使用中，log2m = 11 和 regwidth = 5时，将请求需要10240位或者1280个字节。即 5 * 2^11 = 5* 2048 = 10240
- 还有一种就是有很多的字节
最初的HLL算法的第一个补充来自于实现1280个字节需要160个64位整数的大小。因此，如果希望在低基数下获得更高的准确性，则可以将一组明确的输入保留为64位整数的排序列表，直到达到第161个不同的值为止。这将为提供流中不同值的真实表示，同时需要相同数量的内存。 （这是EXPLICIT算法）。
第二个是不需要存储值为零的寄存器。可以简单地将一组具有非零值的寄存器表示为从索引到值的映射。该映射存储为索引值对的列表，这些索引值对是长度为log2m + regwidth的bit-packed的“short words”。 （这是SPARSE算法。）
结合这两种增强，得到了一个“promotion hierarchy”，可以对算法进行调整以提高准确性，内存或性能。
初始化和存储新的hll对象将仅分配一个小的小标记值，该值表示空集（EMPTY）。当添加前几个值时，唯一整数的排序列表存储在EXPLICIT集中。当希望停止权衡内存的准确性时，已排序列表中的值将“promoted”为基于SPARSE映射的HyperLogLog结构。最后，当有足够的寄存器时，基于映射的HLL将转换为位打包的FULL HLL结构。
自然地，EMPTY和EXPLICIT表示的基数估计是准确的，而SPARSE和FULL表示的准确性受原始HLL算法提供的保证的约束。
安装和使用HLL
解压安装包
[postgres@pgserver plugin]$ ls
postgresql-hll-2.15.1 postgresql-hll-2.15.1.tar.gz
[postgres@pgserver plugin]$ cd postgresql-hll-2.15.1
[postgres@pgserver postgresql-hll-2.15.1]$ ls
CHANGELOG.md expected include Makefile REFERENCE.md src
DEVELOPER.md hll.control LICENSE README.md sql</
