估计频次值¶

概述¶

Snowflake 提供了节省空间算法的实现，该算法由 Metwally、Agrawal 和 Abbadi 在 `《数据流中频繁和 Top-k 元素的有效计算》<https://www.cs.ucsb.edu/research/tech-reports/2005-23>`_ 中提出。它是通过 APPROX_TOP_K 函数系列实现的。

此外，APPROX_TOP_K_COMBINE 函数利用了 Cafaro、Pulimeno 和 Tempesta 概述的 并行节省空间算法 (https://arxiv.org/abs/1401.0702)。

算法的错误百分比很大程度上取决于数据的偏斜程度以及算法中使用的计数器数量。随着数据变得更加偏斜，或者使用更多的计数器，输出将更加准确。

SQL 函数¶

下列 聚合函数 使用节省空间算法来估计频次值：

• APPROX_TOP_K：返回输入中频次值的近似值。

• APPROX_TOP_K_ACCUMULATE：跳过最后的估算步骤，并在聚合结束时返回节省空间的状态。

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

• APPROX_TOP_K_ESTIMATE：计算由 APPROX_TOP_K_ACCUMULATE 和 APPROX_TOP_K_COMBINE 生成的节省空间状态的基数估计值。

实施细节¶

实施中的每个计数器都会跟踪一个项目及其频率。值得注意的是，我们的实施不跟踪计数器的 epsilon 值，因为它们仅用于保证算法的输出，不用于算法本身。

计数器的最大数量设置为 10 万。在这种情况下，内存中存储了 10 万个计数器，但其中只有一小部分以导出状态存储。

k 最大数量为 10 万。如果所有值都无法放入输出中，则会自动减小此值。

在大多数情况下，实施的运行时不依赖于计数器的数量。实施确保计数器的数量不会对算法的运行时产生明显影响。

每个聚合状态中的每个计数器都使用大约 100 字节的恒定内存开销。因此，如果聚合使用 c 个计数器并且存在 g 个聚合组，则聚合将使用 c * g * 100B 内存，加上用于存储值的内存。如果此内存超过总内存预算，则内存将溢出到磁盘。这比确切版本使用的内存要少得多，尤其是当存在大量唯一值时。