快速移动的整体聚合

Richard Wesley

2021-11-12 · 12 分钟

在上一篇文章中，我们描述了 DuckDB 的窗口函数架构并提到了对一些高级移动聚合的支持。在这篇文章中，我们将比较这些函数各种可能的移动实现方式的性能，并解释 DuckDB 的高性能实现原理。

什么是聚合函数？

当人们想到聚合函数时，通常会想到像 SUM 或 AVG 这样简单的东西。但更一般地讲，聚合函数的作用是把一组值汇总成一个单一值。这种汇总可以任意复杂，并且涉及任何数据类型。例如，DuckDB 提供了用于连接字符串（STRING_AGG）和构建列表（LIST）的聚合。在 SQL 中，聚合集来自 GROUP BY 子句或 OVER 窗口规范。

整体聚合

所有基本的 SQL 聚合函数，如 SUM 和 MAX，都可以通过一次读取一个值并丢弃它们来计算。但是有些函数可能需要跟踪所有值才能产生结果。这些被称为整体聚合，它们在实现时需要更小心。

对于某些聚合（例如 STRING_AGG），值的顺序可以改变结果。这对于窗口函数不是问题，因为 OVER 子句可以指定排序，但在 GROUP BY 子句中，值是无序的。为了处理这种情况，对顺序敏感的聚合可以包含一个 WITHIN GROUP(ORDER BY <expr>) 子句来指定值的顺序。因为所有值都必须被收集和排序，所以使用 WITHIN GROUP 子句的聚合是整体的。

统计整体聚合

由于窗口聚合的参数排序可以通过 OVER 子句指定，您可能想知道是否存在不使用排序或使用与 OVER 子句中不同排序方式的其他类型的整体聚合。事实证明，有许多重要的统计函数在 SQL 中会变成整体聚合。特别地，DuckDB 目前支持的统计整体聚合如下：

真正有趣的是当我们尝试计算这些聚合的移动版本时。例如，计算移动 AVG 相当简单：你可以减去离开帧的值，并添加新进入的值，或者使用上一篇关于窗口函数的文章中的线段树方法。

Python 示例

计算移动中位数并非易事。让我们看一个简单的例子，说明如何为以下字符串数据在 Python 中实现移动 median，使用一个包含两侧各一个元素的帧：

在这个例子中，我们使用字符串，这样就不必担心插值问题。

data = ('a', 'b', 'c', 'd', 'c', 'b',)
w = len(data)
for row in range(w):
    l = max(row - 1, 0)       # First index of the frame
    r = min(row + 1, w-1)     # Last index of the frame
    frame = list(data[l:r+1]) # Copy the frame values
    frame.sort()              # Sort the frame values
    n = (r - l) // 2          # Middle index of the frame
    median = frame[n]         # The median is the middle value
    print(row, data[row], median)

每个帧都有不同的值集需要聚合，我们无法改变表中值的顺序，因此每次排序前都必须复制它们。排序很慢，并且存在很多重复。

如果仅仅重用简单的实现来处理移动版本，所有这些整体聚合都存在类似的问题。幸运的是，对于所有这些问题都有快得多的方法。

移动整体聚合

在上一篇关于窗口函数的文章中，我们解释了用于实现通用聚合函数（初始化、更新、最终化、组合和窗口）的组件操作。在本文的其余部分，我们将深入探讨如何为这些复杂聚合实现它们。

分位数

quantile 聚合变体都从集合中有序值的给定分数（或分数列表）处提取值。最简单的变体是我们在引言中遇到的 median 函数，它使用 0.5 的分数。还有其他变体取决于值是定量（即它们有距离且可以插值）还是仅仅是序数（即它们可以排序，但平局必须打破）。还有其他变体取决于分数是单个值还是值的列表，但它们都可以以类似的方式实现。

在 Python 示例中我们看到的一种实现 quantile 的常用方法是将所有值收集到状态中，对其进行排序，然后读取所需位置的值。（这可能就是 SQL 标准将其称为“有序集聚合”的原因。）状态可以通过连接来组合，这使我们能够并行分组并为窗口函数构建段树。

这种方法非常耗时，因为排序是 O(N log N)，但幸运的是，对于 quantile，我们可以使用一种相关的算法，称为 QuickSelect，它可以通过部分排序数组，在仅 O(N) 时间内找到一个位置值。如果您曾经在 C++ 标准库中使用过 std::nth_element 算法，您可能遇到过此算法。这对于分组分位数非常有效，但对于移动分位数，段树方法最终会比每次从头开始计算慢约 5%。

为了真正提高移动分位数的性能，我们注意到部分顺序在帧之间可能变化不大。如果我们维护一个窗口内间接索引列表，并在这些索引上调用 nth_element，我们可以重新排列部分有序的索引，而不是值本身。在帧大小相同的一般情况下，我们甚至可以检查新值是否会扰乱部分排序，并跳过重新排序！通过这种方法，我们可以获得 1.5 到 10 倍的显著性能提升。

在这个例子中，有一个 3 元素的帧（绿色），每个值向右移动一个位置

橙色的中位数必须从头计算。请注意，在示例中，这只发生在窗口的开始。白色的中位数是使用现有的部分排序计算的。在示例中，这发生在帧大小改变时。最后，蓝色的中位数不需要重新排序，因为新值与旧值相同。通过这种算法，我们可以创建一个不经过排序的单分数 quantile 的更快实现。

四分位距 (IQR)

我们可以利用每次调用 nth_element 都会部分排序值的这一事实，将此实现扩展到分数列表，从而进一步提高性能。“重用”技巧可以推广，以区分未受干扰的分数和需要重新计算的分数。

多个分数的一个常见应用是使用分数列表 [0.25, 0.5, 0.75] 计算四分位距。这是我们用于多个分数基准测试的分数列表。结合移动的 MIN 和 MAX，这种移动聚合可以用于生成移动箱线图的数据。

中位数绝对偏差 (MAD)

保持部分排序也可用于提升中位数绝对偏差（或 mad）聚合的性能。不幸的是，如果数据中位数发生变化，第二个部分排序不能使用单值技巧，因为用于部分排序值的“函数”会随之改变。尽管如此，这些值可能仍然相差不远，这再次提高了 nth_element 的性能。

众数

mode 聚合返回集合中最常见的值。一种常见的实现方法是将所有值累积到状态中，对它们进行排序，然后扫描最长的连续序列。这些状态可以通过合并来组合，这使得我们能够并行计算众数并为窗口函数构建段树。

同样，这种方法非常耗时，因为排序是 O(N log N)。它还可能比必要地使用更多内存，因为它保留了所有值，而不是只保留唯一值。如果列表中存在高频项（这通常是使用 mode 的目的），这可能会非常显著。

另一种实现 mode 的方法是使用哈希映射来存储值到计数的状态。哈希表在累积时通常是 O(N)，这比排序有所改进，并且它们只需要存储唯一值。如果状态还跟踪迄今为止见过的最大值和计数，我们可以在聚合结束时直接返回该值。状态可以通过合并来组合，这使得我们能够并行分组并为窗口函数构建段树。

不幸的是，正如下面的基准测试所显示，这种用于窗口函数的段树方法相当慢！事实证明，合并哈希表用于段树的开销比为窗口中的每一行构建一个新的哈希表慢约 5%。但对于移动的 mode 计算，我们可以改为创建一个单一的哈希表，并在帧每次移动时更新它，移除旧值，添加新值，并更新值/计数对。有时当前众数的值的计数可能会减少，但当这种情况发生时，我们可以重新扫描表以找到新的众数。

在这个例子中，4 元素的帧（绿色）每个值向右移动一个位置

当众数不变（蓝色）时，可以直接使用。当众数变得模糊（橙色）时，我们必须重新扫描表。这种方法要快得多，在基准测试中，它比另外两种方法快 15 到 55 倍。

微基准测试

为了对各种实现进行基准测试，我们对一个包含 10M 整数的表运行移动窗口查询：

CREATE TABLE rank100 AS
    SELECT b % 100 AS a, b FROM range(10000000) tbl(b);

然后将结果重新聚合到一行，以消除流式传输结果的影响。帧宽度为 100 元素，并使用固定的尾部帧重复测试：

SELECT quantile_cont(a, [0.25, 0.5, 0.75]) OVER (
    ORDER BY b ASC
    ROWS BETWEEN 100 PRECEDING AND CURRENT ROW) AS iqr
FROM rank100;

以及一个围绕当前值伪随机移动的可变帧：

SELECT quantile_cont(a, [0.25, 0.5, 0.75]) OVER (
    ORDER BY b ASC
    ROWS BETWEEN mod(b * 47, 521) PRECEDING AND 100 - mod(b * 47, 521) FOLLOWING) AS iqr
FROM rank100;

这里的两个例子是四分位距查询；其他查询使用单参数聚合函数 median、mad 和 mode。

最后一步，我们运行了与 count(*) 相同的查询，它与其他基准测试具有相同的开销，但计算起来微不足道（它只返回帧大小）。我们将该开销从运行时间中减去，以获得算法计时：

可以看出，为所有这些聚合实现窗口操作带来了显著的益处，通常性能提升达十倍左右。

一个意想不到的发现是，对于这些复杂状态的段树方法总是比简单地为每个输出行创建状态慢（约 5%）。这表明，在编写可组合的复杂聚合时，对聚合进行基准测试，然后考虑提供一个窗口操作而不是依赖于段树机制，是非常值得的。

结论

DuckDB 的聚合 API 允许聚合函数定义一个窗口操作，可以显著提高复杂聚合的移动窗口计算性能。此功能已用于显著加速众数、四分位距和中位数绝对偏差等多种统计聚合的窗口计算。

DuckDB 是一个免费开源的数据库管理系统（MIT 许可）。它旨在成为分析领域的 SQLite，并提供一个快速高效、零外部依赖的数据库系统。它不仅适用于 Python，还适用于 C/C++、R、Java 等。