HLL数据类型

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

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

表 1 HLL与其他算法比较

项目

Sort算法

Hash算法

HLL

时间复杂度

O(nlogn)

O(n)

O(n)

空间复杂度

O(n)

O(n)

1280字节

误差率

0

0

≈2%

所需存储空间

原始数据大小

原始数据大小

1280字节

HLL在计算速度和所占存储空间上都占优势。在时间复杂度上，Sort算法需要排序至少O(nlogn)的时间，虽说Hash算法和HLL一样扫描一次全表O(n)的时间就可以得出结果，但是存储空间上，Sort算法和Hash算法都需要先把原始数据存起来再进行统计，会导致存储空间消耗巨大，而对HLL来说不需要存原始数据，只需要维护HLL数据结构，故占用空间始终是1280字节常数级别。

HLL数据类型 - 图1 须知：

  • 当前默认规格下可计算最大distinct值的数量为1.6e+12个，误差率最大可达到2.3%。用户应注意如果计算结果超过当前规格下distinct最大值会导致计算结果误差率变大，或导致计算结果失败并报错。
  • 用户在首次使用该特性时，应该对业务的distinct value做评估，选取适当的配置参数并做验证，以确保精度符合要求：
  • 当前默认参数下，可以计算的distinct value值为1.6e+12，如果计算得到的distinct value值为NaN，需要调整log2m和regwidth来容纳更多的distinct value。
  • 虽然hash算法存在极低的hash collision概率，但是建议用户在首次使用时，选取2-3个hash seed验证，如果得到的distinct value相差不大，则可以从该组seed中任选一个作为hash seed。

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

表 2 HyperLogLog中主要数据结构

数据类型

功能描述

hll

大小为确定的1280字节，可直接计算得到distinct值。

HLL的应用场景。

  • 场景1：“Hello World”

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

    1. -- 创建带有hll类型的表
    2. postgres=# create table helloworld (id integer, set hll);
    4. -- 向表中插入空的hll
    5. postgres=# insert into helloworld(id, set) values (1, hll_empty());
    7. -- 把整数经过哈希计算加入到hll中
    8. postgres=# update helloworld set set = hll_add(set, hll_hash_integer(12345)) where id = 1;
    10. -- 把字符串经过哈希计算加入到hll中
    11. postgres=# update helloworld set set = hll_add(set, hll_hash_text('hello world')) where id = 1;
    13. -- 得到hll中的distinct值
    14. postgres=# select hll_cardinality(set) from helloworld where id = 1;
    15.  hll_cardinality 
    16. -----------------
    17.                2
    18. (1 row)
    20. -- 删除表
    21. postgres=# drop table helloworld;

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

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

    1. -- 创建原始数据表，表示某个用户在某个时间访问过网站。
    2. postgres=# create table facts (
    3.          date            date,
    4.          user_id         integer
    5. );
    7. -- 构造数据，表示一天中有哪些用户访问过网站。
    8. postgres=# insert into facts values ('2019-02-20', generate_series(1,100));
    9. postgres=# insert into facts values ('2019-02-21', generate_series(1,200));
    10. postgres=# insert into facts values ('2019-02-22', generate_series(1,300));
    11. postgres=# insert into facts values ('2019-02-23', generate_series(1,400));
    12. postgres=# insert into facts values ('2019-02-24', generate_series(1,500));
    13. postgres=# insert into facts values ('2019-02-25', generate_series(1,600));
    14. postgres=# insert into facts values ('2019-02-26', generate_series(1,700));
    15. postgres=# insert into facts values ('2019-02-27', generate_series(1,800));
    17. -- 创建表并指定列为hll。
    18. postgres=# create table daily_uniques (
    19.     date            date UNIQUE,
    20.     users           hll
    21. );
    23. -- 根据日期把数据分组，并把数据插入到hll中。
    24. postgres=# insert into daily_uniques(date, users)
    25.     select date, hll_add_agg(hll_hash_integer(user_id))
    26.     from facts
    27.     group by 1;
    29. -- 计算每一天访问网站不同用户数量
    30. postgres=# select date, hll_cardinality(users) from daily_uniques order by date;
    31.         date         | hll_cardinality  
    32. ---------------------+------------------
    33.  2019-02-20 00:00:00 |              100
    34.  2019-02-21 00:00:00 | 203.813355588808
    35.  2019-02-22 00:00:00 | 308.048239950384
    36.  2019-02-23 00:00:00 | 410.529188080374
    37.  2019-02-24 00:00:00 | 513.263875705319
    38.  2019-02-25 00:00:00 | 609.271181107416
    39.  2019-02-26 00:00:00 | 702.941844662509
    40.  2019-02-27 00:00:00 | 792.249946595237
    41. (8 rows)
    43. -- 计算在2019.02.20到2019.02.26一周中有多少不同用户访问过网站
    44. postgres=# select hll_cardinality(hll_union_agg(users)) from daily_uniques where date >= '2019-02-20'::date and date <= '2019-02-26'::date;
    45.  hll_cardinality  
    46. ------------------
    47.  702.941844662509
    48. (1 row)
    50. -- 计算昨天访问过网站而今天没访问网站的用户数量。
    51. postgres=# 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);                                                                                                             
    52.         date         | lost_uniques 
    53. ---------------------+--------------
    54.  2019-02-20 00:00:00 |            0
    55.  2019-02-21 00:00:00 |            0
    56.  2019-02-22 00:00:00 |            0
    57.  2019-02-23 00:00:00 |            0
    58.  2019-02-24 00:00:00 |            0
    59.  2019-02-25 00:00:00 |            0
    60.  2019-02-26 00:00:00 |            0
    61.  2019-02-27 00:00:00 |            0
    62. (8 rows)
    64. -- 删除表
    65. postgres=# drop table facts;
    66. postgres=# drop table daily_uniques;

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

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

    1. postgres=# create table test(id integer, set hll);
    2. postgres=# insert into test values(1, 'E\\1234');
    3. ERROR:  unknown schema version 4
    4. postgres=# drop table test;