HyperLogLog函数

数据结构

HyperLogLog（hll）是一种统计基数的算法。它实际上不会存储每个元素出现的次数，它使用的是概率算法，通过存储元素的32位hash值的第一个1的位置，来计算元素数量。通常分为稀疏存储结构和密集存储结构两种。hll创建时是稀疏存储结构，当需要更高效处理时会转为密集型数据结构。P4HyperLogLog则在其整改生命周期都是密集型数据结构。如有必要，可以显式地转换cast(hll as P4HyperLogLog)。在当前数据引擎的实现中，hll的数据草图是通过一组32位的桶来存储对应的最大hash。

序列化

数据草图可以通过varbinary进行序列化和反序列化。这使得可以被方便地存储，以备后用。通过合并多个草图，可以在查询分区中所有元素的approx_distinct()，即每个元素出现的近似次数，进而通过很小的开销去完成整个查询。

例如，只要计算每日每个用户浏览了多少次网页，就可以通过累加的方式，去计算每周、每年对应的数据，类似于通过汇总每日收入来计算每周收入。

可以将approx_distinct()与GROUPING SETS一起使用转换为HyperLogLog。如下所示：

CREATE TABLE visit_summaries(visit_date date,hll varbinary);

INSERT INTO visit_summaries 
SELECT visit_date,cast(approx_set(user_id) AS varbinary) 
FROM user_visits 
GROUP BY visit_date; 

SELECT cardinality(merge(cast(hll AS HyperLogLog)))AS weekly_unique_users 
FROM visit_summaries
WHERE visit_date>=current_date-interval'7'day;

函数

• approx_set(x) → HyperLogLog

  描述：返回HyperLogLog。这个数据草图是approx distinct()的基础，可以通过调用cardinality()来存储和使用。

  select approx_set(cookieid) from cookies_log;--02 0c 02 00 c0 77 15 40 c1 2f 1b c2 

• cardinality(hll) → bigint

  描述：计算hll汇总的数据。

  select cardinality(approx_set(cookieid)) from cookies_log; --2

• empty_approx_set()→ HyperLogLog

  描述：返回一个空的hyperloglog。

  select empty_approx_set();--02 0c 00 00

• merge(HyperLogLog) → HyperLogLog

  描述：对每个独立的hll数据草图进行汇总求并集的操作。

  CREATE TABLE visit_summaries (  visit_date date,  hll varbinary);
  
  insert into visit_summaries select createtime,cast(approx_set(cookieid) as varbinary) from cookies_log group by createtime;
  
  SELECT cardinality(merge(cast(hll AS HyperLogLog))) AS weekly_unique_users FROM visit_summaries WHERE visit_date >=date '2020-07-11';
   weekly_unique_users 
  ---------------------
                     2 
  (1 row)