DuckDB 中的窗口函数

Richard Wesley

2021-10-13 · 15 分钟

窗口函数（使用 OVER 子句的函数）是分析数据序列的重要工具，但如果实现不当，它们可能会很慢。在这篇文章中，我们将探讨 DuckDB 如何实现窗口功能。我们还将了解 DuckDB 如何利用其聚合函数架构来计算有用的移动聚合，例如移动四分位距 (IQR)。

超越集合

Codd 在 20 世纪 70 年代开发的原始关系模型将关系视为元组的无序集合。虽然这对于理论计算机科学工作来说很不错，但它忽略了人类使用物理类比（神经科学中的“具身大脑”模型）进行思考的方式。特别是，人类自然地对数据进行排序以帮助他们理解和处理数据。为了实现这一点，SQL 使用 SELECT 子句进行水平布局，使用 ORDER BY 子句进行垂直布局。

尽管如此，人类对数据施加的排序往往不仅仅是神经学的辅助。例如，时间对测量数据施加了自然的顺序，这些测量数据中的大幅波动本身可能是重要数据，或者它们可能表明数据需要通过平滑来清洗。趋势可能存在，或者相对变化对于分析来说可能比原始值更重要。为了帮助回答这些问题，SQL 在 2003 年引入了分析（或窗口）函数。

窗口函数

窗口操作通过将一个关系分解为独立的分区，对这些分区进行排序，然后定义各种函数，这些函数可以使用附近值对每行进行计算。这些函数包括所有聚合函数（例如 sum 和 avg），以及一些窗口专用函数（例如 rank() 和 nth_value(<expression>, <N>)）。

一些窗口函数仅依赖于分区边界和排序，但少数（包括所有聚合函数）也使用帧。帧被指定为当前行两侧（前导或后随）的行数。距离可以指定为行数，也可以使用分区的排序值和距离来指定一个值范围。

帧是窗口环境中最为混乱的部分，所以让我们来看一个非常简单的例子，暂时忽略分区和排序。

SELECT points,
    sum(points) OVER (
        ROWS BETWEEN 1 PRECEDING
                 AND 1 FOLLOWING) AS we
FROM results;

此查询计算每个点及其两侧点的总和

请注意，在分区边缘，只有两个值相加。

发电量示例

现在我们来看一个具体的窗口函数查询示例。假设我们有一些发电厂的发电数据

数据存在噪音，因此我们希望为每个电厂计算一个 7 天移动平均值。为此，我们可以使用此窗口查询

SELECT "Plant", "Date",
    avg("MWh") OVER (
        PARTITION BY "Plant"
        ORDER BY "Date" ASC
        RANGE BETWEEN INTERVAL 3 DAYS PRECEDING
                  AND INTERVAL 3 DAYS FOLLOWING)
        AS "MWh 7-day Moving Average"
FROM "Generation History"
ORDER BY 1, 2;

此查询计算每个电厂每天发电量的 7 天移动平均值。OVER 子句是 SQL 指定函数在窗口中计算的方式。它根据 Plant 对数据进行分区（以使不同电厂的数据分开），根据 Date 对每个电厂的分区进行排序（以使能源测量值相邻），并为 avg 使用每个日期两侧各三天的一个 RANGE 帧（以处理任何缺失日期）。结果如下：

您可以在同一个 SELECT 语句中请求多个不同的 OVER 子句，并且每个子句都会单独计算。然而，通常您希望对多个函数使用相同的窗口，这可以通过使用 WINDOW 子句来定义一个命名窗口来完成

SELECT "Plant", "Date",
    avg("MWh") OVER seven AS "MWh 7-day Moving Average"
FROM "Generation History"
WINDOW seven AS (
    PARTITION BY "Plant"
    ORDER BY "Date" ASC
    RANGE BETWEEN INTERVAL 3 DAYS PRECEDING
              AND INTERVAL 3 DAYS FOLLOWING)
ORDER BY 1, 2;

例如，如果也想通过 7 天移动 min 和 max 来显示数据的边界，这将非常有用。

幕后实现

这是一个很长的复杂功能列表！要使其全部相对快速地运行需要许多部分，所以让我们来看看它们在 DuckDB 中是如何实现的。

管道中断

首先要注意的是，窗口操作是一个“管道中断器”。也就是说，Window 运算符必须读取其所有输入才能开始计算函数。这意味着，如果存在其他计算方法，使用不同技术可能会更快。

一个常见的分析任务是找到某个组中的最后一个值。例如，假设我们想找到每个电厂最后记录的功率输出。诱人的是使用 rank() 窗口函数并进行反向排序来完成此任务

SELECT "Plant", "MWh"
FROM (
    SELECT "Plant", "MWh",
        rank() OVER (
            PARTITION BY "Plant"
            ORDER BY "Date" DESC) AS r
    FROM table) t
WHERE r = 1;

但这需要物化整个表、对其进行分区、对分区进行排序，然后从这些分区中提取单行。一种更快的方法是使用自连接来过滤表，使其只包含 DATE 字段的最后一个（max）值

SELECT table."Plant", "MWh"
FROM table,
    (SELECT "Plant", max("Date") AS "Date"
     FROM table GROUP BY 1) lasts
WHERE table."Plant" = lasts."Plant"
  AND table."Date" = lasts."Date";

此连接查询需要两次表扫描，但唯一物化的数据是过滤表（可能比原始表小得多），并且根本没有排序。

这种类型的查询出现在用户博客中，我们发现连接查询在他们的数据集上快了 20 多倍

当然，大多数使用窗口功能的分析任务确实需要使用 Window 运算符，DuckDB 使用一系列技术来尽可能提高性能。

分区和排序

曾几何时，窗口操作是通过对分区和排序字段进行排序，然后找到分区边界来实现的。这是一种资源密集型操作，因为整个关系都必须进行排序，并且排序的时间复杂度为关系大小的 O(N log N)。幸运的是，有更快的方法来实现这一步。

为了减少资源消耗，DuckDB 使用了 Leis 等人论文《分析型 SQL 查询中窗口函数的有效处理》中的分区方案，并使用 O(N) 哈希将分区拆分为 1024 个块。这些块仍然需要在所有字段上进行排序，因为可能存在哈希冲突，但现在每个分区可以小 1024 倍，这显著减少了运行时间。此外，这些分区可以轻松地并行提取和处理。

DuckDB 中的排序最近获得了显著的性能提升，同时还具备了处理大于内存的分区的能力。此功能也已添加到 Window 运算符中，使得“组中最后一个”示例的性能提高了 33%。

作为最终优化，即使您可以请求多个窗口函数，DuckDB 也会收集使用相同分区和排序的函数，并在这些函数之间共享数据布局。

聚合

大多数通用窗口函数都易于计算，但窗口聚合函数可能成本高昂，因为它们需要查看每行的多个值。它们通常需要多次查看相同的值，或者重复查看大量值，因此多年来已采取多种方法来提高性能。

朴素窗口聚合

在解释 DuckDB 如何实现窗口聚合之前，我们需要简要了解一下普通聚合函数的实现方式。聚合“函数”通过三个必需操作和一个可选操作来实现

• 初始化 – 创建一个将被更新的状态。对于 sum，这是运行总计，从 NULL 开始（因为零项的总和是 NULL，而不是零）。
• 更新 – 使用新值更新状态。对于 sum，这将值添加到状态中。
• 完成 – 从状态生成最终聚合值。对于 sum，这只是复制运行总计。
• 组合 – 将两个状态组合成一个状态。组合是可选的，但如果存在，它允许聚合并行计算。对于 sum，这将生成一个新状态，其中包含两个输入值的总和。

计算单个窗口聚合值的最简单方法是：初始化一个状态，用窗口帧中的所有值更新该状态，然后使用完成操作生成窗口聚合值。这种朴素算法始终有效，但效率很低。例如，每次运行总计都会重新添加分区开头的所有值，其运行时间为 O(N^2)。

为了改进这一点，一些数据库添加了额外的“移动状态”操作，可以增量地添加或删除单个值。这在某些常见情况下减少了计算量，但它只能用于某些聚合函数。例如，它不适用于 min）因为您不知道是否存在多个重复的最小值。此外，如果帧边界移动很多，它仍然可能退化为 O(N^2) 的运行时间。

线段树聚合

DuckDB 没有添加更多函数，而是使用了 Leis 等人提出的线段树方法。这种方法通过在整个分区之上构建一棵树来实现，聚合值位于树的底部。值在树中向上组合成节点状态，直到只剩一个根节点

为了计算一个值，该算法会为帧的不规则边缘生成状态，组合帧中值上方树中的状态，并从最后一个剩余状态完成结果。因此，在上面的示例（来自 Leis 等人的图 5）中，只需要添加三个值而不是 7 个。此技术可用于所有可组合聚合。

通用窗口聚合

线段树最大的缺点是需要管理大量潜在的中间状态。对于标准分布式聚合（如 sum）所使用的简单状态，这不是问题，因为状态很小，树将状态数量保持在对数级别，并且用于计算每个值的状态也很廉价。

然而，对于某些聚合函数，状态并不小。通常这些是所谓的整体聚合，其值取决于帧中的所有值。此类聚合的示例包括 mode 和 quantile，其中每个状态可能需要包含迄今为止所有值的副本。虽然线段树可以用于实现任何可组合聚合的移动版本，但这对于大型、复杂的状态来说可能相当昂贵——而这并非该算法的最初目标。

为了解决这个问题，我们使用了 Wesley 和 Xu 论文《常见窗口整体聚合的增量计算》中的方法，该方法将线段树推广到特定于聚合的数据结构。聚合函数可以定义第五个可选的窗口操作，该操作将接收树的底部以及当前帧和前一帧的边界。然后，聚合函数可以为其实现创建适当的数据结构。

例如，mode 函数维护一个可以高效更新的计数哈希表，而 quantile 函数维护一个部分排序的帧索引列表。此外，quantile 函数可以接受一个分位数值数组，通过在不同分位数值之间共享部分有序结果来进一步提高性能。

由于这些聚合函数可以在窗口上下文中使用，因此上述移动平均示例可以很容易地修改以生成移动四分位距

SELECT "Plant", "Date",
    quantile_cont("MWh", [0.25, 0.5, 0.75]) OVER seven
        AS "MWh 7-day Moving IQR"
FROM "Generation History"
WINDOW seven AS (
    PARTITION BY "Plant"
    ORDER BY "Date" ASC
    RANGE BETWEEN INTERVAL 3 DAYS PRECEDING
              AND INTERVAL 3 DAYS FOLLOWING)
ORDER BY 1, 2;

像这样的移动分位数对异常值更具鲁棒性，这使其成为数据序列分析的宝贵工具，但它们通常并未在大多数数据库系统中实现。虽然有些查询引擎中可以使用一些方法，但缺乏通用的移动聚合架构意味着这些解决方案可能不自然或复杂。DuckDB 的实现使用标准窗口表示法，这意味着您无需学习新语法或将数据提取到另一个工具中。

有序集合聚合

窗口函数通常与 SQL 标准定义的一些特殊“有序集合聚合”密切相关。一些数据库使用 Window 运算符来实现这些函数，但这效率相当低下，因为不需要对数据进行排序（一个 O(N log N) 操作）——只需使用 Hoare 的 O(N) FIND 算法，就像 STL 的std::nth_element 中使用的一样。DuckDB 将这些有序集合聚合转换为使用更快的 quantile_cont、quantile_disc 和 mode 常规聚合函数，从而完全避免使用窗口功能。

扩展

这种架构还意味着我们添加的任何新聚合函数都可以受益于现有的窗口基础设施。DuckDB 是一个开源项目，我们欢迎提交有用的聚合函数——或者您可以在自己的分支中创建自己的领域特定函数。我们希望在某个时候拥有一个 UDF 架构，允许插件聚合，并且界面的简洁性和强大功能将使这些插件能够利用内部函数所享有的符号简洁性和运行时性能。

结论

DuckDB 的窗口实现使用了多种技术来加速分析查询中可能最慢的部分。它与排序子系统和聚合函数架构良好集成，这使得表达高级移动聚合既自然又高效。

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