HLL数据类型

HLL（HyperLoglog）是一种用于统计数据集中唯一值个数的高效近似算法。它有着计算速度快、节省空间的特点，不需要直接存储集合本身，而是存储一种名为HLL的数据结构。每当有新数据需要参与统计时，数据库会对数据进行哈希计算并插入到HLL中，最后就可以根据HLL得到结果。

HLL与其他算法的比较请参见表1。

HLL在计算速度和存储效率方面都具有优势。在时间复杂度上，Sort算法需要花费至少O(nlogn)的时间进行排序，而Hash算法和HLL均能通过O(n)的线性时间完成统计。但在存储效率方面，Sort算法和Hash算法都需要先存储原始数据再进行统计，会导致存储空间消耗巨大，而HLL不需要存储原始数据，只需要维护HLL数据结构，能节省很多存储空间，默认规格下HLL数据结构的最大空间约为16kB。

• 当前默认规格下可计算的最大唯一值个数约为1.1e+15个，误差率约为0.8%。用户应注意如果计算结果超过当前规格下最大唯一值个数会导致计算结果误差率变大，或导致计算失败并报错。
• 用户在首次使用该特性时，应该对业务的唯一值做评估，选取适当的配置参数并做验证，以确保精度符合要求：
  • 当前默认规格下，可以计算的最大唯一值个数为1.1e+15，如果计算得到的唯一值个数为NaN，需要调整log2m，或者采用其他算法计算唯一值个数。
  • 虽然hash算法存在极低的哈希冲突概率，但是建议用户在首次使用时选取2~3个不同的哈希种子进行验证，若各种子计算结果差异较小，则可以从中任选一个作为哈希种子。

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

创建HLL数据类型时，可支持0~4个参数入参，具体的参数含义与参数规格同函数hll_empty一致。第一个参数为log2m，表示分桶数的对数值，取值范围为10~16；第二个参数为log2explicit，表示Explicit模式的阈值大小，取值范围为0~12；第三个参数为log2sparse，表示Sparse模式的阈值大小，取值范围为0~14；第四个参数为duplicatecheck，表示是否启用duplicatecheck，取值范围为0~1。当入参输入值为-1时，会采用默认值设定HLL的参数。可通过“\d”或“\d+”查看HLL类型的参数。

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

• 创建HLL类型时对应入参不输入或输入-1时，采用默认值设定对应的HLL参数。
• 输入合法范围的入参时，对应HLL参数采用输入值。
• 输入不合法范围的入参时，创建HLL类型报错。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

-- 创建hll类型的表，不指定入参。
gaussdb=# CREATE TABLE t1 (id integer, set hll);
gaussdb=# \d t1
      Table "public.t1"
 Column |  Type   | Modifiers
--------+---------+-----------
 id     | integer |
 set    | hll     |

-- 创建hll类型的表，指定前两个入参，后两个采用默认值。
gaussdb=# CREATE TABLE t2 (id integer, set hll(12,4));
gaussdb=# \d t2
          Table "public.t2"
 Column |      Type      | Modifiers
--------+----------------+-----------
 id     | integer        |
 set    | hll(12,4,12,0) |

-- 创建hll类型的表，指定第三个入参，其余采用默认值。
gaussdb=# CREATE TABLE t3(id int, set hll(-1,-1,8,-1));
gaussdb=# \d t3
          Table "public.t3"
 Column |      Type      | Modifiers
--------+----------------+-----------
 id     | integer        |
 set    | hll(14,10,8,0) |

-- 创建hll类型的表，指定入参不合法报错。
gaussdb=# 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

-- 删除已创建的hll类型的表。
gaussdb=# DROP TABLE t1,t2,t3;
DROP TABLE

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

-- 创建带有hll类型的表。
gaussdb=# CREATE TABLE t1(id integer, set hll(14));

-- 向表中插入hll对象，参数一致，成功。
gaussdb=# INSERT INTO t1 VALUES (1, hll_empty(14,-1));

-- 向表中插入hll对象，参数不一致，失败。
gaussdb=# INSERT INTO t1(id, set) VALUES (1, hll_empty(14,5));
ERROR:  log2explicit does not match: source is 5 and dest is 10

-- 删除表。
gaussdb=# DROP TABLE t1;

HLL的应用场景。

• 场景1：“Hello World”

  通过以下示例说明如何使用hll数据类型：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  -- 创建带有hll类型的表。 gaussdb=# CREATE TABLE helloworld (id integer, set hll); -- 向表中插入空的hll。 gaussdb=# INSERT INTO helloworld(id, set) VALUES (1, hll_empty()); -- 把整数经过哈希计算加入到hll中。 gaussdb=# UPDATE helloworld SET set = hll_add(set, hll_hash_integer(12345)) WHERE id = 1; -- 把字符串经过哈希计算加入到hll中。 gaussdb=# UPDATE helloworld SET set = hll_add(set, hll_hash_text('hello world')) WHERE id = 1; -- 得到hll中的distinct值。 gaussdb=# SELECT hll_cardinality(set) FROM helloworld WHERE id = 1; hll_cardinality ----------------- 2 (1 row) -- 删除表。 gaussdb=# DROP TABLE helloworld;

• 场景2：“网站访客数量统计”

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

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

  -- 创建原始数据表，表示某个用户在某个时间访问过网站。 gaussdb=# CREATE TABLE facts ( date date, user_id integer ); -- 构造数据，表示一天中有哪些用户访问过网站。 gaussdb=# INSERT INTO facts VALUES ('2019-02-20', generate_series(1,100)); gaussdb=# INSERT INTO facts VALUES ('2019-02-21', generate_series(1,200)); gaussdb=# INSERT INTO facts VALUES ('2019-02-22', generate_series(1,300)); gaussdb=# INSERT INTO facts VALUES ('2019-02-23', generate_series(1,400)); gaussdb=# INSERT INTO facts VALUES ('2019-02-24', generate_series(1,500)); gaussdb=# INSERT INTO facts VALUES ('2019-02-25', generate_series(1,600)); gaussdb=# INSERT INTO facts VALUES ('2019-02-26', generate_series(1,700)); gaussdb=# INSERT INTO facts VALUES ('2019-02-27', generate_series(1,800)); -- 创建表并指定列为hll。 gaussdb=# CREATE TABLE daily_uniques ( date date UNIQUE, users hll ); -- 根据日期把数据分组，并把数据插入到hll中。 gaussdb=# INSERT INTO daily_uniques(date, users) SELECT date, hll_add_agg(hll_hash_integer(user_id)) FROM facts GROUP BY 1; -- 计算每一天访问网站不同用户数量。 gaussdb=# SELECT date, hll_cardinality(users) FROM daily_uniques ORDER BY date; date | hll_cardinality ------------+------------------ 2019-02-20 | 100 2019-02-21 | 200.217913059312 2019-02-22 | 301.76494508014 2019-02-23 | 400.862858326446 2019-02-24 | 502.626933349694 2019-02-25 | 601.922606454213 2019-02-26 | 696.602316769498 2019-02-27 | 798.111731634412 (8 rows) -- 计算在2019.02.20到2019.02.26一周中有多少不同用户访问过网站。 gaussdb=# 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) -- 计算昨天访问过网站而今天没访问网站的用户数量。 gaussdb=# 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); --默认兼容性（M兼容性）结果如下： date | lost_uniques ------------+-------------- 2019-02-20 | 0 2019-02-21 | 0 2019-02-22 | 0 2019-02-23 | 0 2019-02-24 | 0 2019-02-25 | 0 2019-02-26 | 0 2019-02-27 | 0 (8 rows) -- 删除表。 gaussdb=# DROP TABLE facts; gaussdb=# DROP TABLE daily_uniques;

• 场景3：“插入数据不满足hll数据结构要求”

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

  1 2 3 4

  gaussdb=# CREATE TABLE test(id integer, set hll); gaussdb=# INSERT INTO test VALUES(1, 'E\\1234'); ERROR: not a hll type, size=6 is not enough gaussdb=# DROP TABLE test;