PostgreSQL插件之hll

背景

在现实生活中，我们通常需要统计一个集合中不重复的元素个数。在数据库中通过使用如下的SQL语句进行精确统计：

CREATE TABLE tbl(id INT, a INT);
INSERT INTO tbl VALUES(1, 1), (2, 1), (3, 2), (4, 2), (5, 2), (6, 3);
SELECT COUNT(DISTINCT a) FROM tbl;
 count 
-------
     3
(1 row)

为了计算 count-distinct 通常使用哈希或者排序的方式计算不重复元素个数。但是，如果数据量比较大，哈希或者排序消耗的内存较大。HyperLogLog 是处理这个问题的一个概率算法，但是其消耗资源较少。

postgresql-hll插件引入了一个新的数据类型hll，它是一个HyperLogLog数据结构。下面对其使用进行详细介绍。

支持版本

1. PostgreSQL 12
   
2. PostgreSQL 11
   
3. PostgreSQL 10
   
4. PostgreSQL 9.6
   
5. PostgreSQL 9.5

安装

在华为云使用postgresql-hll，请参考：https://support.huaweicloud.com/usermanual-rds/rds_09_0043.html 进行安装和卸载。

使用

CREATE TABLE hll_tbl (
    id      integer,
    set     hll
);

--- 插入空的HLL
INSERT INTO hll_tbl(id, set) VALUES (1, hll_empty());

--- 增加一个被散列的整数值到HLL中
UPDATE hll_tbl SET set = hll_add(set, hll_hash_integer(12345)) WHERE id = 1;

--- 增加一个被散列的字符串到HLL中
UPDATE hll_tbl SET set = hll_add(set, hll_hash_text('hello world')) WHERE id = 1;

--- 计算HLL的基数
SELECT hll_cardinality(set) FROM hll_tbl WHERE id = 1;

数据仓库示例

我们假设有一个事实表，记录了用户对我的站点的访问、他们做了什么以及他们来自哪里。表中有上亿行数据，表扫描需要几分钟（或者至少需要很多秒）。

CREATE TABLE facts (
    date            date,
    user_id         integer,
    activity_type   smallint,
    referrer        varchar(255)
);

insert into facts select timestamp '2014-01-10 10:00:00' +
       random() * (timestamp '2021-01-20 20:00:00' - timestamp '2014-01-10 10:00:00'),
       generate_series(1, 10000000), 1, 'no use';

insert into facts select timestamp '2014-01-10 10:00:00' +
       random() * (timestamp '2021-01-20 20:00:00' - timestamp '2014-01-10 10:00:00'),
       generate_series(1, 10000000), 1, 'no use';

如果想快速（毫秒级别）知道每天有多少独立用户访问了站点，可以建立一个聚合表：

CREATE TABLE daily_uniques (
    date            date UNIQUE,
    users           hll
);

INSERT INTO daily_uniques(date, users)
    SELECT date, hll_add_agg(hll_hash_integer(user_id))
    FROM facts
    GROUP BY 1;

我们首先对user_id进行散列，然后按天将这些散列后的值聚合为一个hll。现在我们可以计算每天的hll基数：

SELECT date, hll_cardinality(users) FROM daily_uniques;

如果想要得到这周独立的用户访问数呢？

SELECT hll_cardinality(hll_union_agg(users)) 
	FROM daily_uniques 
	WHERE date >= '2012-01-02'::date AND date <= '2012-01-08'::date;

操作符

插件中已经添加了一些操作符，使用hll变得不那么冗长。它们是最常用函数的简单别名。

散列函数

• hll_hash_boolean(boolean)
  
• hll_hash_smallint(smallint)
  
• hll_hash_integer(integer)
  
• hll_hash_bigint(bigint)
  
• hll_hash_bytea(bytea)
  
• hll_hash_text(text)
  
• hll_hash_any(any)

示例如下：

SELECT hll_hash_boolean(TRUE);
SELECT hll_hash_boolean(TRUE, 123/*hash seed*/);
SELECT hll_hash_smallint(4::smallint);
SELECT hll_hash_smallint(4::smallint, 123/*hash seed*/);
SELECT hll_hash_integer(21474836);
SELECT hll_hash_integer(21474836, 123/*hash seed*/);
SELECT hll_hash_bigint(223372036854775808);
SELECT hll_hash_bigint(223372036854775808, 123/*hash seed*/);
SELECT hll_hash_bytea(E'\\xDEADBEEF');
SELECT hll_hash_bytea(E'\\xDEADBEEF', 123/*hash seed*/);
SELECT hll_hash_text('foobar');
SELECT hll_hash_text('foobar', 123/*hash seed*/);

SELECT hll_hash_any(123);
SELECT hll_hash_any(123, 123/*hash seed*/);

注意：hll_hash_any会动态地分派给适当的特定类型的函数，这使得它比它包装的特定类型的函数要慢。只有在不知道输入类型时才使用它。

聚集函数

如果要从表或结果集中创建一个hll，请使用hll_add_agg。这里的命名并不是特别有创意：它是一个聚合函数，将值添加到空的hll中。

SELECT date, hll_add_agg(hll_hash_integer(user_id))
    FROM facts
    GROUP BY 1;

上面的示例将为每个包含每天用户的日期提供一个hll。如果您想汇总已经存储到单个hll中的一个hll列表，请使用hll_union_agg。再次说明：它是一个聚合函数，将值合并到一个空的hll中。

SELECT EXTRACT(MONTH FROM date), hll_cardinality(hll_union_agg(users))
    FROM daily_uniques
    GROUP BY 1;

窗口是hll功能的另一个主要例子。执行滑动窗口惟一计数通常涉及一些generate_series技巧，对于已经计算过的滑动窗口则非常简单。

SELECT date, #hll_union_agg(users) OVER seven_days
    FROM daily_uniques
    WINDOW seven_days AS (ORDER BY date ASC ROWS 6 PRECEDING);