估计非重复值的数量

Snowflake 使用 HyperLogLog 估计数据集中非重复值的大致数量。HyperLogLog 是一种更先进的基数估计算法，能够估计数万亿行的不同基数，平均相对误差为百分之几。

在可以接受估计基数的情况下，可以使用 HyperLogLog 代替 COUNT(DISTINCT ...)。

本主题内容：

概述

Snowflake 提供了 Flajolet 等人在“HyperLogLog：近似最优基数估计算法的分析 (http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)”中介绍的 HyperLogLog 算法的偏差校正实现。

建议在输入可能很大且可以接受近似结果时使用 HyperLogLog。HyperLogLog 实现的平均相对误差为 1.62338%（即与相应 COUNT(DISTINCT ...) 结果的平均相对差）。

SQL 函数

提供以下:doc:`/sql-reference/functions-aggregation`来使用 HyperLogLog 估计基数：

  • HLL：返回输入的非重复基数的近似值。

  • HLL_ACCUMULATE：跳过最后的估算步骤，并在聚合结束时返回 HyperLogLog 状态。

  • HLL_COMBINE：将输入状态合并（即合并）为单个输出状态。

  • HLL_ESTIMATE：计算由 HLL_ACCUMULATE 和 HLL_COMBINE 生成的 HyperLogLog 状态的基数估计值。

  • HLL_EXPORT：将 HyperLogLog 状态从 BINARY 格式转换为 OBJECT （然后可以打印并导出为 JSON）。

  • HLL_IMPORT：将 HyperLogLog 状态从 OBJECT 格式转换为 BINARY 格式。

实施细节

我们的实现将输入行哈希为 64 位值，其中上 12 位或“精度”（如 HyperLogLog 算法论文中所述；有关详细信息，请参阅上面的文档链接）用于将输入值划分为所谓的子流。这会产生以下平均相对误差：

sqrt(3*ln(2)-1)/sqrt(2^precision) = 0.0162338 = 1.62338%

换言之，对于 COUNT(DISTINCT ...) 将返回 1,000,000 结果的查询，HyperLogLog 通常返回 983,767 到 1,016,234 范围内的结果。

对于每个子流，HyperLogLog 保持最大前导零计数（对于精度 = 12 时的 64 位值，介于 0 和 52 之间）。这种状态最直接的表示形式是一个简单的字节数组，每个 2^12 = 4096 子流一个字节。我们的实现确实需要每个聚合组最多 4096 字节 (2^precision = 2^12 = 4096) 的内存。从技术上讲，每个子流只需要 6 位（而不是 8 位），但我们用一些空间效率来换取计算效率。

对于较小的输入基数，大多数子流永远不会被命中。因此，我们的实现不是预先为每个聚合组分配整个 4096 字节块，而是在有利的情况下使用此状态的空间优化“稀疏”表示。因此，HyperLogLog 的内存成本可以大大低于每个聚合组 4096 字节（每个聚合组低至约 32 字节）。这样可以对许多聚合组（数百万甚至数十亿，由查询的 GROUP BY 或 OVER 子句确定）进行基数估计，使用的内存和 CPU 时间比相应的 COUNT(DISTINCT ...) 查询少几个数量级。

在（罕见）情况下，如果一个非常大的输入表和许多聚合组导致 HyperLogLog 超出其总内存预算，Snowflake 仍然能够溢出到临时空间并执行递归聚合，就像任何其他聚合函数一样。

导出的状态格式

可以分别使用 HLL_EXPORT 和 HLL_IMPORT 函数导出和导入（或重新导入）HyperLogLog 算法的状态。导出的状态是 OBJECT 类型，包含以下字段。

密集格式

version:

HyperLogLog 实现的版本号。

precision:

用于选择子流的哈希值位数。目前固定为 12。

dense:

整数数组，每个整数包含相应子流的最大前导零计数 + 1。0 表示尚未命中相应的子流。合法值在 0 到 53 的范围内。相应的子流索引由数组中的元素位置给出。

例如：

{
  "version" : 3,
  "precision" : 12,
  "dense" : [3,3,3,3,5,3,4,3,5,6,2,4,4,7,5,6,6,3,2,2,3,2,4,5,5,5,2,5,5,3,6,1,4,2,2,4,4,5,2,5,...,4,6,3]
}
Copy

稀疏格式

version:

HyperLogLog 实现的版本号。

precision:

用于选择子流的哈希值位数。目前固定为 12。

sparse:

indices：整数数组，每个整数包含一个子流索引（以 0 为基数）。合法值在 0 到 4095 的范围内。

maxLzCounts：整数数组，每个整数包含相应子流的最大前导零计数 + 1。0 表示尚未命中相应的子流。

合法值在 0 到 53 的范围内。给定前导零计数的子流由 indices 数组中的相应元素给出。

indices 和 maxLzCounts 数组必须具有相同的长度。HLL_IMPORT 函数还会检查子流索引是否在有效范围内，以及有没有重复的子流索引。indices 数组不需要排序。前导零计数未经过验证。无效值不会导致查询失败，但会导致 HLL_ESTIMATE 出现未定义的结果。

例如：

{
  "version" : 3,
  "precision" : 12,
  "sparse" : {
    "indices": [1131,1241,1256,1864,2579,2699,3730],
    "maxLzCounts":[2,4,2,1,3,2,1]
  }
}
Copy

示例

环境设置：

USE WAREHOUSE dontdrop;
USE DATABASE stressdb;
USE SCHEMA bdb_5nodes;

SELECT COUNT(*) FROM uservisits;

-----------+
 COUNT(*)  |
-----------+
 751754869 |
-----------+
Copy

第 1 步：

创建一个包含日历日期（年/月/日）和 HLL 结构的表。我们使用 HLL_EXPORT 将二进制结构存储为文本对象：

CREATE OR REPLACE TABLE daily_uniques
AS
SELECT
 visitdate,
 hll_export(hll_accumulate(sourceip)) AS hll_sourceip
FROM uservisits
GROUP BY visitdate;
Copy

第 2 步：

我们可以通过聚合第 1 步中每天的 HLL 结构来按月计算唯一 IPs 值。我们使用 HLL_IMPORT 将文本转换为二进制结构，然后使用 HLL_COMBINE 将多个 HLL 结构组合成一个结构，然后使用 HLL_ESTIMATE 计算非重复值的数量：

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll_estimate(hll_combine(hll_import(hll_sourceip))) AS distinct_ips
FROM daily_uniques
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 1.3s
Copy

比较：

我们将运用 HLL 函数的聚合使用情况与详细级别数据上的 HLL 使用情况进行了比较。在本例中，HLL() 相当于第 2 步中的 HLL_ESTIMATE(HLL_COMBINE(HLL_IMPORT()))：

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll(sourceip) AS distinct_ips
FROM uservisits
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 2m 29s
Copy

正如您所看到的，HLL 结构的聚合明显快于基础数据的聚合，例如，在这个小示例中，1.3 秒对 149 秒，这意味着查询时间减少了 100 倍。

语言: 中文