SelectDB中HyperLogLog去重_云数据库 SelectDB 版(SelectDB)-阿里云帮助中心

本文介绍云数据库SelectDB提供的HyperLogLog（简称 HLL）功能，帮助您进行数据去重，加速查询。

概述

在实际的业务场景中，随着业务数据量的不断增加，数据去重的压力也随之增大。当数据规模达到一定程度时，采用精准去重的成本也随之增加。在业务可接受的情况下，通过近似算法来快速去重，降低计算压力，是一种非常有效的方式。

针对这种场景，SelectDB提供了近似去重算法HyperLogLog（简称 HLL）。HLL的特点是具有非常优异的空间复杂度O(log(logn))和时间复杂度O(n)，并且计算结果的误差可控制在1%~2%左右（误差与数据集大小以及所采用的哈希函数有关）。

HyperLogLog原理

近似去重算法HyperLogLog是LogLog算法的升级版，作用是能够提供不精确的去重计数，其数学基础为伯努利试验。

数学基础

在伯努利试验中，假设硬币拥有正反两面，一次抛硬币中最终出现正反面的概率都是50%。若将“一直抛硬币，直到它出现正面为止”记录为一次完整的试验，那么对于n次伯努利试验，就意味着出现了n次的正面。

假设每次伯努利试验所经历了的抛掷次数为k，第一次伯努利试验的次数设为k1，第n次对应的是kn，以此类推。那么在这之中，对于这n次伯努利试验，必然会有一个最大的抛掷次数k，意味着抛了k次才出现正面，称这个次数为k_max，代表抛了最多的次数。那么，伯努利试验容易得出有以下结论：

n次伯努利过程的投掷次数都不大于k_max。
n次伯努利过程，至少有一次投掷次数等于k_max。

结合极大似然估算的方法，发现在n和k_max中存在估算关联：n = 2 ^ k_max。当我们只记录了k_max时，即可估算总共有多少条数据，也就是基数。

估算误差

假设试验结果如下：

第1次试验：抛了3次才出现正面，此时 k=3，n=1。
第2次试验：抛了2次才出现正面，此时 k=2，n=2。
第3次试验：抛了6次才出现正面，此时 k=6，n=3。
...
第n次试验：抛了12次才出现正面，此时我们估算n = 2^12。

取上面例子中前三组试验，那么k_max = 6，最终n=3。我们放进估算公式中去，明显3 ≠ 2^6 。也即是说，当试验次数很小的时候，这种估算方法的误差是很大的。

这三组试验，称为一轮的估算。如果只是进行一轮的话，当n足够大的时候，估算的误差率会相对减少，但仍然不够小。

SelectDB HLL函数

HLL是基于HyperLogLog算法的工程实现，用于保存HyperLogLog计算过程的中间结果，它只能作为表的Value列类型、通过聚合来不断的减少数据量，以此来实现加快查询的目的。基于它得到的是一个估算结果，误差大概在1%左右。HLL列是通过其它列或者导入数据里面的数据生成的，导入的时候通过hll_hash函数来指定数据中哪一列用于生成HLL列。它常用于替代count distinct，与ROLLUP结合在业务上用于快速计算独立访客UV（Unique Visitor）等。

HLL函数有以下几个。

HLL_UNION_AGG(hll)
此函数为聚合函数，用于计算满足条件的所有数据的基数估算。
HLL_CARDINALITY(hll)
此函数用于计算单条HLL列的基数估算。
HLL_HASH(column_name)
生成HLL列类型，用于Insert或导入数据时，导入的使用请参见使用示例。

使用示例

创建一张含有HLL列的表
```
CREATE TABLE test_hll(
    dt date,
    id int,
    name char(10),
    province char(10),
    os char(10),
    pv hll hll_union
)
Aggregate KEY (dt,id,name,province,os)
distributed by hash(id) buckets 10
PROPERTIES(
    "replication_num" = "1",
    "in_memory"="false"
);
```
重要
使用HLL需要注意以下问题。
- 使用HLL去重的时候，需要在建表语句中将目标列类型设置成HLL，聚合函数设置成HLL_UNION。
- HLL类型的列不能作为Key列使用。
- 不需要指定长度及默认值，长度根据数据聚合程度在系统内控制。

导入数据

示例数据如下（test_hll.csv）。

2022-05-05,10001,测试01,北京,windows
2022-05-05,10002,测试01,北京,linux
2022-05-05,10003,测试01,北京,macos
2022-05-05,10004,测试01,河北,windows
2022-05-06,10001,测试01,上海,windows
2022-05-06,10002,测试01,上海,linux
2022-05-06,10003,测试01,江苏,macos
2022-05-06,10004,测试01,陕西,windows

使用不同的导入方式如下。

使用Stream Load导入，示例如下。

# curl --location-trusted -u root: -H "label:label_test_hll_load" -H "column_separator:," -H "columns:dt,id,name,province,os,pv=hll_hash(id)" -T test_hll.csv http://127.0.0.1:8030/api/demo/test_hll/_stream_load

{
    "TxnId": 693,
    "Label": "label_test_hll_load",
    "TwoPhaseCommit": "false",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 8,
    "NumberLoadedRows": 8,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 320,
    "LoadTimeMs": 23,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 9,
    "CommitAndPublishTimeMs": 11
}

使用Broker Load导入，示例如下。

LOAD LABEL demo.test_hlllabel
 (
    DATA INFILE("hdfs://hdfs_host:hdfs_port/user/doris_test_hll/data/input/file")
    INTO TABLE `test_hll`
    COLUMNS TERMINATED BY ","
    (dt,id,name,province,os)
    SET (
      pv = HLL_HASH(id)
    )
 );

查询数据

HLL列不允许直接查询原始值，只能通过HLL的聚合函数进行查询。

求总的PV，示例如下。

SELECT HLL_UNION_AGG(pv) FROM test_hll;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

等价于使用(DISTINCT pv)查询。

SELECT COUNT(DISTINCT pv) FROM test_hll;
+----------------------+
| count(DISTINCT `pv`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

求每一天的PV，示例如下。

SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)