穿窗飞行

Author Avatar
Richard Wesley
2025-02-14 · 11 分钟

概要：深入了解 DuckDB 近期窗口函数性能改进的细节。

介绍

在上一篇文章中，我介绍了 DuckDB 中通过 SQL 提供的一些新窗口函数功能。但还有一些其他改进，它们在不增加新功能的情况下，优化了我们对资源（例如内存）的使用。那么，让我们“深入内部”，看看这些变化。

我们之前对窗口函数密集型工作负载进行了基准测试，结果显示性能随时间推移显著提升。本篇博客中介绍的优化进一步提升了 DuckDB 窗口操作符的性能。

线段树向量化

2023 年夏季做出的一项重要改进是将线段树评估代码从单值评估转换为向量化评估。你可能想知道，在一个“向量化关系型数据库”中，为什么一开始就不是这样（！），但答案已无从考证。我最好的猜测是，要么是已发布的算法是为单值设计的，要么是聚合 API 尚未最终确定（或两者兼有）。

在旧版本中，我们使用聚合的 update 或 combine API，但仅限于单行的数据和树状态。为了向量化线段树聚合，我们累积叶值和树状态的*向量*，并在达到 2048 行的向量容量时将其刷新到每个输出行的状态中。需要注意的是，要通过按正确顺序累积值来处理顺序敏感型聚合。FILTER 和 EXCLUDE 子句也带来了一些挑战，但现在线段树已完全向量化。这里的性能提升大约是四倍（从“基线”到“扇出”）。

下方图表显示了向量化改进带来的加速效果

一旦线段树向量化，我们就可以在用归并排序树实现 DISTINCT 聚合时采用相同的方法。未来某个时候，可能值得更新自定义窗口 API 以处理向量化，因为尽管大多数自定义窗口聚合（例如 quantile、mad 和 mode）都相当慢，但 count(*) 也作为自定义聚合实现，并很可能受益于向量化实现。

常量聚合

许多窗口计算都是针对帧的聚合，而使用这些结果的常见分析任务是将部分聚合与*整个分区*上的相同聚合进行比较。重复计算此值既昂贵又可能浪费内存（例如，旧实现即使只需要一个值，也会构建一个线段树）。

之前的性能解决方案是在子查询中计算聚合，并根据分区键进行连接，但这很不友好。现在，我们添加了一个优化，用于检查*分区范围内的聚合*，并为每个分区只计算该值一次。这不仅减少了聚合本身的内存和计算时间，而且我们通常可以返回一个常量向量，该向量在块中所有行之间共享值，从而减少复制成本，甚至可能减少下游评估成本。

返回常量向量可以带来惊人的内存和性能优势。在促成此改进的问题中，用户正在构建一个包含 10 万个元素的常量列表（！），然后使用列表聚合 lambda 计算中位数。通过返回单个常量列表，我们只需构建和精简该列表一次，而不是每行一次！

流式窗口

计算窗口函数通常非常耗时！整个关系必须具体化，分成多个分区，并且每个分区都需要排序。

但是如果没有分区或排序呢？这意味着窗口函数将在“自然顺序”下，对整个关系进行计算，使用一个从第一行开始并延伸到当前行的帧。例如，分配行号或计算运行总和。这足够简单，我们可以在单个线程上*流式*评估函数。

首先，让我们退一步谈谈窗口*操作符*。在查询的解析和优化过程中，所有窗口函数都关联到一个单一的*逻辑*窗口操作符。在规划查询时，我们将具有共同分区和“兼容”排序的函数进行分组（更多信息请参阅曹等人，分析窗口函数的优化），并将每组移交给一个单独的*物理*窗口操作符来处理该分区和排序。为了使用“自然顺序”，我们必须将那些可以流式处理的函数进行分组并首先执行它们（否则顺序会被破坏！），然后将它们移交给*流式*物理窗口操作符。

那么，哪些窗口函数可以进行流式处理呢？结果发现有很多

  • 聚合函数 BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW（我们只需更新聚合）
  • first_value – 它始终是相同的
  • percent rank – 它始终是 0
  • rank – 它始终是 0
  • dense_rank – 它始终是 0
  • row_number – 我们只需计数行
  • lead 和 lag – 我们只需维护一个缓冲区

还有一些限制

  • 不允许使用 IGNORE NULLS、EXCLUDE 和 ORDER BY 参数
  • lead 和 lag 的距离限制在 ±2048（一个向量）的常量范围内。这并不是什么大问题，因为距离通常是 1。

流式 LEAD 的改进相当显著

SELECT setseed(0.8675309);
CREATE OR REPLACE TABLE df AS
    SELECT 
        random() AS a,
        random() AS b,
        random() AS c,
    FROM range(10_000_000);

SELECT sum(a_1 + a_2 + b_1 + b_2)
FROM (
    SELECT
        lead(a, 1) OVER () AS a_1,
        lead(a, 2) OVER () AS a_2,
        lead(b, 1) OVER () AS b_1,
        lead(b, 2) OVER () AS b_2
    FROM df
) t;

下方图表显示了性能改进。

  • 基线 – 我们开始的地方
  • 移位 – 在非流式实现内部复制行块，而不是逐个复制
  • 流式 – 流式 LEAD 的首次实现
  • 部分 – 当整个块可以被直接引用时，避免复制

请注意，*x* 轴显示了相对于基线（1 倍）的加速效果，绝对运行时长（秒）则显示为标签。

未来，我们或许能够将帧的结束位置放宽到与当前行保持恒定距离，且该距离符合缓冲区长度（例如 BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING），但这尚未进行调查。

分区优先评估

窗口分区是完全独立的，因此单独评估它们很有吸引力。我们首次实现时利用了这一点，并在单独的线程上评估每个分区。如果分区数量多于线程数量且它们大小大致相同，则效果很好，但如果分区大小不均或只有一个分区（常见情况），那么大多数核心将处于空闲状态，从而降低吞吐量。

为了提高 CPU 利用率，我们在 v1.1 中改变了执行模型，以并行评估分区。分区从最大到最小进行评估，然后我们将每个分区尽可能多地分配给多个核心，同时同步对共享数据结构的访问。这比独立单线程分区评估更具挑战性，并且我们遇到了一些同步问题（希望现在都已解决！），这些问题在 v1.1.x 版本中得到了处理。但现在我们的核心利用率大大提高，尤其是对于未分区数据。作为附带好处，由于一次性加载到内存中的分区数量更少，我们能够减少内存占用。

仍然存在的一个问题是子分区的粗粒度。目前，为了避免复制，它们使用排序代码生成的块，这些块通常比我们希望的要大。减小这些块的大小是未来的工作，但希望我们能在对排序代码进行一些提议的更改时解决它。

内存不足时的操作

由于窗口操作会具体化整个关系，因此很容易超出查询的内存预算。对于 v1.2，我们已从在内存中具体化活跃分区切换到使用可分页集合。所以现在我们不仅活跃分区数量更少（得益于上述的分区优先评估），而且那些分区本身现在可以溢出到磁盘。这进一步减少了评估大型分区时的内存压力。

然而，窗口操作非常复杂，因此仍然存在一些大型数据结构。用于加速聚合的线段树和归并排序树仍在内存中，尤其是树中间的中间聚合状态。要完全解决这个问题，需要一种将聚合状态序列化到磁盘的通用方法，我们目前还没有。不过，大多数聚合可以作为二进制数据序列化，无需特殊处理，因此短期内，我们很可能可以用当前的聚合基础设施覆盖许多情况，就像我们处理 GROUP BY 一样。

共享表达式

窗口表达式是独立评估的，但它们经常共享表达式。其中一些表达式评估成本高昂，而另一些则需要在整个分区上具体化。作为后者的一个例子，聚合函数可以引用分区中的任何位置的值。这可能导致重复计算和具体化相同的值

-- Compute the moving average and range of x over a large window
SELECT
    x,
    min(x) OVER w AS min_x,
    avg(x) OVER w AS avg_x,
    max(x) OVER w AS max_x,
FROM data
WINDOW w AS (
    PARTITION BY p
    ORDER BY s
    ROWS BETWEEN 1_000_000 PRECEDING and 1_000_000 FOLLOWING
);

对 x 的数据进行分页可以减少内存占用，但用于评估这三个聚合的线段树将包含 x 的重复副本——以及 with 操作符本身（它必须返回 x）。在 v1.2 中，我们添加了一种机制，用于在函数之间共享此类表达式的评估。这不仅减少了内存，而且在此示例中，由于所有三个函数都将访问相同的值，还将减少磁盘分页。

我们在多个地方共享表达式，包括 ORDER BY 参数、range 表达式以及像 lead、lag 和 nth_value 这样的“值”函数，并且我们一直在寻找更多可以共享的地方（例如帧边界——甚至线段树）。

未来工作

虽然我提到了未来希望实现的一些事情，但其中一个目前尚未很好地融入任何主题的是查询重写。结果表明，某些窗口函数可以使用其他技术进行评估，例如自连接以及我们一些更智能的聚合（如 arg_max）。生成这些备用查询计划可以带来巨大的性能优势，我们计划对此进行调查。

结论

如您所见，窗口操作是一个庞大而复杂的难题！关于有效算法的已发表研究也不多（我基本上已经链接了所有这些研究），因此我们常常不得不自己摸索，或者退回到极其简单而缓慢的方法。但我希望，您中的许多人能从我们过去 2-3 年的工作中发现一些新颖和令人兴奋的东西——我将努力更及时地撰写关于未来窗口改进的博客文章。

本文中