GBase 8c 数据类型-HLL数据类型

HLL（Hyper Loglog）是一种用于统计数据集中唯一值个数的高效近似算法，具有计算速度快、节省空间的特点，不需要直接存储集合本身，而是存储HLL数据结构。每当有新数据合入统计时，只需要把数据经过哈希计算，并插入到HLL中，最后根据HLL就可以得到统计结果。
 

HLL与其他算法的比较，参见下表。

由上表可知，HLL在计算速度和所占存储空间上都占优势。在时间复杂度上，Sort算法至少需要O(nlogn)的时间，Hash算法、HLL需要O(n)的时间就可以得出结果；在存储空间上，Sort算法和Hash算法都需要先把原始数据存起来再进行统计，会导致存储空间消耗巨大，而对HLL来说，不需要存原始数据，只需要维护HLL数据结构，故占用空间有很大的压缩。默认规格下HLL数据结构的最大空间约为16KB。

l 当前默认规格下，可计算最大distinct值的数量约为1.1e+15个，误差率为0.8%。需要注意的是，如果计算结果超过当前规格下distinct最大值，会导致计算结果误差率变大，或导致计算结果失败并报错。

l 用户在首次使用该特性时，应该对业务的distinct value做评估，选取适当的配置参数并做验证，以确保精度符合要求：

n 当前默认参数下，可以计算的distinct值为1.1e+15，如果计算得到的distinct值为NaN，需要调整log2m，或者采用其他算法计算distinct值。

n 虽然hash算法存在极低的hash collision概率，但是建议用户在首次使用时，选取2-3个hash seed验证，如果得到的distinct value相差不大，则可以从该组seed中任选一个作为hash seed。

HLL中主要的数据结构，请参见下表。

创建HLL数据类型时，可以支持0~4个参数入参。当入参输入值为-1 时，会采用默认值设定HLL的参数。可以通过\d或\d+查看HLL类型的参数。具体的参数含义与参数规格同函数hll_empty一致：

l 第一个参数为log2m，表示分桶数的对数值，取值范围10~16；

l 第二个参数为log2explicit，表示Explicit模式的阈值大小，取值范围0~12；

l 第三个参数为log2sparse，表示Sparse模式的阈值大小，取值范围0~14；

l 第四个参数为duplicatecheck，表示是否启用duplicatecheck，取值范围为0~1。

创建HLL数据类型时，根据入参的行为不同，结果不同：

l 创建HLL类型时对应入参不输入或输入-1，采用默认值设定对应的HLL参数。

l 输入合法范围的入参，对应HLL参数采用输入值。

l 输入不合法范围的入参，创建HLL类型报错。

-- 创建hll类型的表，不指定入参

gbase=# CREATE TABLE t1(id integer, set hll);

CREATE TABLE

gbase=# \d t1

      Table "public.t1"

 Column |  Type   | Modifiers

--------+---------+-----------

 id     | integer |

 set    | hll     |

-- 创建hll类型的表，指定前两个入参，后两个采用默认值

gbase=# CREATE TABLE t2 (id integer, set hll(12,4));

CREATE TABLE

gbase=# \d t2

          Table "public.t2"

 Column |      Type      | Modifiers

--------+----------------+-----------

 id     | integer        |

 set    | hll(12,4,12,0) |

--创建hll类型的表，指定第三个入参，其余采用默认值

gbase=# CREATE TABLE t3(id int, set hll(-1,-1,8,-1));

CREATE TABLE

gbase=# \d t3

          Table "public.t3"

 Column |      Type      | Modifiers

--------+----------------+-----------

 id     | integer        |

 set    | hll(14,10,8,0) |

--创建hll类型的表，指定入参不合法报错

gbase=# CREATE TABLE t4(id int, set hll(5,-1));

ERROR:  log2m = 5 is out of range, it should be in range 10 to 16, or set -1 as default

LINE 1: CREATE TABLE t4(id int, set hll(5,-1));

gbase=# DROP TABLE t1,t2,t3;

DROP TABLE

对含有HLL类型的表插入HLL对象时，HLL类型的设定参数须同插入对象的设定参数一致，否则报错。

-- 创建带有hll类型的表

gbase=# CREATE TABLE t1(id integer, set hll(14));

CREATE TABLE

-- 向表中插入hll对象,参数一致，成功

gbase=# insert into t1 values (1, hll_empty(14,-1));

INSERT 0 1

-- 向表中插入hll对象，参数不一致，失败

gbase=# insert into t1(id, set) values (1, hll_empty(14,5));

ERROR:  log2explicit does not match: source is 5 and dest is 10

CONTEXT:  referenced column: set

gbase=# DROP TABLE t1;

DROP TABLE

HLL的应用场景

场景1：通过下面的示例说明如何使用HLL数据类型：

-- 创建带有hll类型的表

gbase=# create table helloworld (id integer, set hll);

CREATE TABLE

-- 向表中插入空的hll

gbase=# insert into helloworld(id, set) values (1, hll_empty());

INSERT 0 1

-- 把整数经过哈希计算加入到hll中

gbase=# update helloworld set set = hll_add(set, hll_hash_integer(12345)) where id = 1;

UPDATE 1

-- 把字符串经过哈希计算加入到hll中

gbase=# update helloworld set set = hll_add(set, hll_hash_text('hello world')) where id = 1;

UPDATE 1

-- 得到hll中的distinct值

gbase=# select hll_cardinality(set) from helloworld where id = 1;

hll_cardinality

-----------------

               2

(1 row)

-- 删除表

gbase=# drop table helloworld;

DROP TABLE

场景2：网站访客数量统计。通过下面的示例说明hll如何统计在一段时间内访问网站的不同用户数量：

-- 创建原始数据表，表示某个用户在某个时间访问过网站。

gbase=# create table facts ( date date, user_id integer);

CREATE TABLE

-- 构造数据，表示一天中有哪些用户访问过网站。

gbase=# insert into facts values ('2019-02-20', generate_series(1,100));

INSERT 0 100

gbase=# insert into facts values ('2019-02-21', generate_series(1,200));

INSERT 0 100

gbase=# insert into facts values ('2019-02-22', generate_series(1,300));

INSERT 0 100

gbase=# insert into facts values ('2019-02-23', generate_series(1,400));

INSERT 0 100

gbase=# insert into facts values ('2019-02-24', generate_series(1,500));

INSERT 0 100

gbase=# insert into facts values ('2019-02-25', generate_series(1,600));

INSERT 0 100

gbase=# insert into facts values ('2019-02-26', generate_series(1,700));

INSERT 0 100

gbase=# insert into facts values ('2019-02-27', generate_series(1,800));

INSERT 0 100

-- 创建表并指定列为hll。

gbase=# create table daily_uniques ( date date UNIQUE,users hll);

NOTICE:  CREATE TABLE / UNIQUE will create implicit index "daily_uniques_date_key" for table "daily_uniques"

CREATE TABLE

-- 根据日期把数据分组，并把数据插入到hll中。

gbase=# insert into daily_uniques(date, users) select date, hll_add_agg(hll_hash_integer(user_id)) from facts group by 1;

INSERT 0 8

-- 计算每一天访问网站不同用户数量

gbase=# select date, hll_cardinality(users) from daily_uniques order by date; 

        date         | hll_cardinality

---------------------+------------------

 2019-02-20 00:00:00 |              100

 2019-02-21 00:00:00 | 200.217913059312

 2019-02-22 00:00:00 |  301.76494508014

 2019-02-23 00:00:00 | 400.862858326446

 2019-02-24 00:00:00 | 502.626933349694

 2019-02-25 00:00:00 | 601.922606454213

 2019-02-26 00:00:00 | 696.602316769498

 2019-02-27 00:00:00 | 798.111731634412

(8 rows)

-- 计算在2019.02.20到2019.02.26一周中有多少不同用户访问过网站

gbase=# select hll_cardinality(hll_union_agg(users)) from daily_uniques where date >= '2019-02-20'::date and date <= '2019-02-26'::date;

hll_cardinality

------------------

 696.602316769498

(1 row)

-- 计算昨天访问过网站而今天没访问网站的用户数量。

gbase=# SELECT date, (#hll_union_agg(users) OVER two_days) - #users AS lost_uniques FROM daily_uniques WINDOW two_days AS (ORDER BY date ASC ROWS 1 PRECEDING);

        date         | lost_uniques

---------------------+--------------

 2019-02-20 00:00:00 |            0

 2019-02-21 00:00:00 |            0

 2019-02-22 00:00:00 |            0

 2019-02-23 00:00:00 |            0

 2019-02-24 00:00:00 |            0

 2019-02-25 00:00:00 |            0

 2019-02-26 00:00:00 |            0

 2019-02-27 00:00:00 |            0

(8 rows)

-- 删除表

gbase=# drop table facts;

DROP TABLE

gbase=# drop table daily_uniques;

DROP TABLE

场景3：当用户给hll类型的字段插入数据的时候，必须保证插入的数据满足hll数据结构要求，如果解析后不满足就会报错。示例：插入数据'E\\1234'时，该数据不满足hll数据结构，不能解析成功因此失败报错。

gbase=# create table test(id integer, set hll);

CREATE TABLE

gbase=# insert into test values(1, 'E\\1234');

ERROR:  not a hll type, size=6 is not enough

LINE 1: insert into test values(1, 'E\\1234');

                                   ^

CONTEXT:  referenced column: set

gbase=# drop table test;

DROP TABLE