文档首页 > > 开发指南> SQL参考> 数据类型> HLL数据类型

HLL数据类型

分享
更新时间: 2019/11/12 GMT+08:00

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

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

表1 HLL与其他算法比较

项目

Sort算法

Hash算法

HLL

时间复杂度

O(nlogn)

O(n)

O(n)

空间复杂度

O(n)

O(n)

1280 bytes

误差率

0

0

≈2%

所需存储空间

原始数据大小

原始数据大小

1280 bytes

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

当前默认规格下可计算最大distinct值的数量为1.6e+12个,误差率最大可达到2.3%。用户应注意如果计算结果超过当前规格下distinct最大值会导致计算结果误差率变大,或导致计算结果失败并报错。

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

表2 HyperLogLog中主要数据结构

数据类型

功能描述

hll

大小为确定的1280 bytes,可直接计算得到distinct值。

HLL的应用场景。

  • 场景1:“Hello World”

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

    -- 创建带有hll类型的表
    create table helloworld (id integer, set hll);
     
    -- 向表中插入空的hll
    insert into helloworld(id, set) values (1, hll_empty());
     
    -- 把整数经过哈希计算加入到hll中
    update helloworld set set = hll_add(set, hll_hash_integer(12345)) where id = 1;
    
    -- 把字符串经过哈希计算加入到hll中
    update helloworld set set = hll_add(set, hll_hash_text('hello world')) where id = 1;
     
    -- 得到hll中的distinct值
    select hll_cardinality(set) from helloworld where id = 1;
     hll_cardinality 
    -----------------
                   2
    (1 row)
  • 场景2:“网站访客数量统计”

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

    -- 创建原始数据表,表示某个用户在某个时间访问过网站。
    create table facts (
             date            date,
             user_id         integer
    );
     
    -- 构造数据,表示一天中有哪些用户访问过网站。
    insert into facts values ('2019-02-20', generate_series(1,100));
    insert into facts values ('2019-02-21', generate_series(1,200));
    insert into facts values ('2019-02-22', generate_series(1,300));
    insert into facts values ('2019-02-23', generate_series(1,400));
    insert into facts values ('2019-02-24', generate_series(1,500));
    insert into facts values ('2019-02-25', generate_series(1,600));
    insert into facts values ('2019-02-26', generate_series(1,700));
    insert into facts values ('2019-02-27', generate_series(1,800));
     
    -- 创建表并指定列为hll。
    create table daily_uniques (
        date            date UNIQUE,
        users           hll
    );
     
    -- 根据日期把数据分组,并把数据插入到hll中。
    insert into daily_uniques(date, users)
        select date, hll_add_agg(hll_hash_integer(user_id))
        from facts
        group by 1;
     
    -- 计算每一天访问网站不同用户数量
    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 | 203.813355588808
     2019-02-22 00:00:00 | 308.048239950384
     2019-02-23 00:00:00 | 410.529188080374
     2019-02-24 00:00:00 | 513.263875705319
     2019-02-25 00:00:00 | 609.271181107416
     2019-02-26 00:00:00 | 702.941844662509
     2019-02-27 00:00:00 | 792.249946595237
    (8 rows)
     
    -- 计算在2019.02.20到2019.02.26一周中有多少不同用户访问过网站
    select hll_cardinality(hll_union_agg(users)) from daily_uniques where date >= '2019-02-20'::date and date <= '2019-02-26'::date;
     hll_cardinality  
    ------------------
     702.941844662509
    (1 row)
     
    -- 计算昨天访问过网站而今天没访问网站的用户数量。
    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)
分享:

    相关文档

    相关产品

文档是否有解决您的问题?

提交成功!

非常感谢您的反馈,我们会继续努力做到更好!

反馈提交失败,请稍后再试!

*必选

请至少选择或填写一项反馈信息

字符长度不能超过200

提交反馈 取消

如您有其它疑问,您也可以通过华为云社区问答频道来与我们联系探讨

跳转到云社区