版本: 最新版本-3.5

使用 HLL 进行近似去重计数

背景

在实际场景中，随着数据量的增加，对数据进行去重的压力也随之增加。当数据量达到一定规模时，精确去重的成本相对较高。在这种情况下，用户通常使用近似算法来降低计算压力。HyperLogLog (HLL) 是本节将介绍的一种近似去重算法，它具有出色的空间复杂度 O(mloglogn) 和时间复杂度 O(n)。更重要的是，计算结果的误差率可以控制在 1%-10% 左右，具体取决于数据集的大小和使用的哈希函数。

什么是 HyperLogLog

HyperLogLog 是一种消耗极少存储空间的近似去重算法。**HLL 类型**用于实现 HyperLogLog 算法。它保存 HyperLogLog 计算的中间结果，并且只能用作数据表的指标列类型。

由于 HLL 算法涉及大量的数学知识，我们将使用一个实际的例子来说明它。假设我们设计一个随机实验 A，即独立重复抛硬币直到第一次出现正面；将第一次出现正面的抛硬币次数记录为随机变量 X，那么

X=1, P(X=1)=1/2
X=2, P(X=2)=1/4
...
X=n, P(X=n)=(1/2)ⁿ

我们使用测试 A 来构建随机测试 B，即对测试 A 进行 N 次独立重复，生成 N 个独立同分布的随机变量 X₁, X₂, X₃, ..., X_N。将随机变量的最大值作为 X_max。利用大似然估计，N 的估计值为 2^X_max。

现在，我们使用给定数据集上的哈希函数来模拟上述实验

测试 A：计算数据集元素的哈希值，并将哈希值转换为二进制表示。记录 bit=1 的出现，从二进制的最低位开始。
测试 B：对测试 B 的数据集元素重复测试 A 过程。更新每次测试中第一个位 1 出现的最大位置 "m"；
估计数据集中的非重复元素数量为 m²。

实际上，HLL 算法根据元素哈希值的低 k 位将元素分成 K=2^k 个桶。从第 k+1 位开始计算第一个位 1 出现的最大值 m₁, m₂,..., m_k，并估计桶中非重复元素的数量为 2^m₁, 2^m₂,..., 2^m_k。数据集中的非重复元素数量是桶的数量乘以桶中非重复元素数量的总和平均值：N = K(K/(2^-m₁+2^-m₂,..., 2^-m_K))。

HLL 将校正因子与估计结果相乘，以使结果更准确。

参考文章 https://gist.github.com/avibryant/8275649 关于使用 StarRocks SQL 语句实现 HLL 去重算法

SELECT floor((0.721 * 1024 * 1024) / (sum(pow(2, m * -1)) + 1024 - count(*))) AS estimate
FROM(select(murmur_hash3_32(c2) & 1023) AS bucket,
     max((31 - CAST(log2(murmur_hash3_32(c2) & 2147483647) AS INT))) AS m
     FROM db0.table0
     GROUP BY bucket) bucket_values

该算法对 db0.table0 的 col2 进行去重。

使用哈希函数 murmur_hash3_32 计算 col2 的哈希值作为 32 位有符号整数。
使用 1024 个桶，校正因子为 0.721，并将哈希值的低 10 位作为桶的下标。
忽略哈希值的符号位，从次高位到低位开始，确定第一个位 1 出现的位置。
按桶对计算出的哈希值进行分组，并使用 MAX 聚合来查找桶中第一个位 1 出现的最大位置。
聚合结果用作子查询，所有桶估计值的总和平均值乘以桶的数量和校正因子。
请注意，空桶计数为 1。

当数据量大时，上述算法的错误率非常低。

这是 HLL 算法的核心思想。如果您有兴趣，请参考 HyperLogLog 论文。

如何使用 HyperLogLog

要使用 HyperLogLog 去重，需要在表创建语句中将目标指标列类型设置为 HLL，并将聚合函数设置为 HLL_UNION。
目前，只有 Aggregate 表支持 HLL 作为指标列类型。
当在 HLL 类型的列上使用 count distinct 时，StarRocks 会自动将其转换为 HLL_UNION_AGG 计算。

示例

首先，创建一个具有 **HLL** 列的表，其中 uv 是聚合列，列类型是 HLL，聚合函数是 HLL_UNION。

CREATE TABLE test(
        dt DATE,
        id INT,
        uv HLL HLL_UNION
)
DISTRIBUTED BY HASH(ID);

注意：当数据量很大时，最好为高频 HLL 查询创建相应的 rollup 表

使用 Stream Load 加载数据

curl --location-trusted -u <username>:<password> -H "label:label_1600997542287" \
    -H "column_separator:," \
    -H "columns:dt,id,user_id, uv=hll_hash(user_id)" -T /root/test.csv http://starrocks_be0:8040/api/db0/test/_stream_load
{
    "TxnId": 2504748,
    "Label": "label_1600997542287",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 5,
    "NumberLoadedRows": 5,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 120,
    "LoadTimeMs": 46,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 29,
    "CommitAndPublishTimeMs": 14
}

Broker Load 模式

LOAD LABEL test_db.label
 (
    DATA INFILE("hdfs://<hdfs_host>:<hdfs_port>/user/starrocks/data/input/file")
    INTO TABLE `test`
    COLUMNS TERMINATED BY ","
    (dt, id, user_id)
    SET (
      uv = HLL_HASH(user_id)
    )
 );

查询数据

HLL 列不允许直接查询其原始值，使用函数 HLL_UNION_AGG 进行查询。
要查找总 uv，

SELECT HLL_UNION_AGG(uv) FROM test;

此语句等效于

SELECT COUNT(DISTINCT uv) FROM test;

查询每天的 uv

SELECT COUNT(DISTINCT uv) FROM test GROUP BY ID;

注意事项

我应该如何在 Bitmap 和 HLL 之间进行选择？如果数据集的基础数据在数百万或数千万级别，并且您有几十台机器，请使用 count distinct。如果基础数据在数亿级别，并且需要精确去重，请使用 Bitmap；如果可以接受近似去重，请使用 HLL 类型。

Bitmap 仅支持 TINYINT、SMALLINT、INT 和 BIGINT。请注意，不支持 LARGEINT。对于要进行去重的其他类型的数据集，需要构建字典以将原始类型映射到整数类型。构建字典很复杂，需要在数据量、更新频率、查询效率、存储和其他问题之间进行权衡。HLL 不需要字典，但它需要相应的数据类型来支持哈希函数。即使在内部不支持 HLL 的分析系统中，仍然可以使用哈希函数和 SQL 来实现 HLL 去重。

对于常用列，用户可以使用 NDV 函数进行近似去重。此函数返回 COUNT(DISTINCT col) 结果的近似聚合，底层实现将数据存储类型转换为 HyperLogLog 类型进行计算。NDV 函数在计算时消耗大量资源，因此不太适合高并发场景。

如果要执行用户行为分析，可以考虑 IntersectCount 或自定义 UDAF。

背景​

什么是 HyperLogLog​

如何使用 HyperLogLog​

示例​

注意事项​

您觉得这篇文档怎么样？

背景

什么是 HyperLogLog

如何使用 HyperLogLog

示例

注意事项