规划 AsOf 连接

Richard Wesley

2025-02-19 · 10 分钟

“我喜欢计划成功的感觉。”
— 汉尼拔·史密斯，《天龙特攻队》

介绍

AsOf 连接是一种对于时间序列分析非常有用的操作。顾名思义，当您有一个随时间变化的数值表，并希望查找另一组时间点上最新的值时，它们是一种查找方式。换句话说，它们让您可以询问：“截至此时，该属性的值是多少？”

DuckDB 在大约 18 个月前添加了 AsOf 连接，您可以阅读该帖子了解其语义。

计划是什么？

在之前的帖子中，我解释了为什么当您可以在传统 SQL 中实现 AsOf 连接时，我们仍为其提供了自定义运算符和语法。SQL 的超能力在于它是声明性的：您告诉我们您想要什么，我们来找出高效的如何实现。通过允许您声明想要 AsOf 连接，我们可以思考如何更快地为您获取结果！

然而，AsOf 运算符需要做大量工作。具体来说，包括：

• 读取右侧（查找）表中的所有数据
• 根据任何相等条件进行分区
• 根据不相等条件进行排序
• 对左侧（探测）表重复此过程
• 对两表执行合并连接，只返回“最新”值

这涉及到大量数据移动！此外，如果任何表很大，我们可能会超出内存并溢出到磁盘，从而进一步减慢操作速度。尽管如此，正如我们将看到的，它比普通的 SQL 实现要快得多。

这造成了很大的负担，许多支持 AsOf 连接的数据库都要求右侧表根据您可能想要连接的任何键进行分区和排序。这与 DuckDB 的“友好 SQL”方法不太吻合，因此（目前）我们每次都必须这样做。

化繁为简

事实证明，AsOf 连接有一个非常常见的情况，即左表很小。假设您有一年的价格数据，以高粒度（例如，秒的分数）记录，但您只想查找少量（比如 20 个）您实际买入或卖出的时间值？

价格表可能包含数亿甚至数十亿行，仅仅对其进行排序就需要大量时间和内存。鉴于其开销如此之大，人们可能会想是否有办法避免所有这些排序？令人高兴的是，答案是有！

简单连接

假设我们交换连接的两侧，将旧的左侧构建为一个小的右侧表，并通过连接的左侧流式传输巨大的表。我们可以使用 AsOf 条件进行连接，并希望能找到一种方法来丢弃较旧的匹配项（我们只希望保留最新的匹配项）。这将使用非常少的内存，并且流式传输可以高度并行化。

为此，我们可以使用两种流式物理连接运算符：

• 嵌套循环连接（Nested Loop Join）——顾名思义：遍历每个左侧块和右侧表，检查匹配项；
• 分段合并连接（Piecewise Merge Join）——一种针对单个不相等条件的巧妙连接，它在合并查找匹配项之前对右侧和每个左侧块进行排序；

一旦我们有了消除重复项的方法，就可以尝试这两种方法。不过，需要注意的是，它们都是 N^2 算法，因此“小”的规模会有上限。

分组

如果您使用数据库足够久，您就会知道“消除重复项”意味着 GROUP BY！因此，为了消除重复项，我们希望在输出中添加一个聚合运算符。棘手的部分在于，我们只想保留具有“最大”时间的匹配值。幸运的是，DuckDB 有一对恰好能实现这一点的聚合函数：arg_max 和 arg_min（也称为 max_by 和 min_by）。

这解决了查找表中的字段问题，但小表中的字段呢？嗯，这些值都将是相同的，所以我们只需对它们使用 first 聚合函数。

流式窗口

但我们应该按什么分组呢？人们可能会倾向于按查找时间进行分组，但这可能会有问题，因为如果存在重复的查找时间（只会返回其中一行！）。相反，我们需要为每个被查找的行提供一个唯一标识符。最简单的方法是使用 流式窗口运算符 和 row_number() 窗口函数。然后我们按此行号分组。

汇总结果

这一切听起来都不错，但它在实践中如何运作呢？“小”可以有多大？为了回答这个问题，我运行了一些基准测试，将小表与大表连接。这些表名为 prices 和 times

CREATE OR REPLACE TABLE prices_{prices_size} AS
    SELECT
        r AS id,
        '2021-01-01T00:00:00'::TIMESTAMP +
            INTERVAL (random() * 365 * 24 * 60 * 60) SECOND
            AS time,
        (random() * 100000)::INTEGER AS price,
    FROM range({prices_size}) tbl(r);

CREATE OR REPLACE TABLE times_{times_size} AS
    SELECT
        r AS id,
        '2021-01-01'::TIMESTAMP +
            INTERVAL ((random() * 365 * 24 * 60 * 60)::INTEGER) SECONDS
            AS probe
    FROM range({times_size}) tbl(r);

然后我运行了一个基准查询

SELECT count(*)
FROM (
    SELECT
        t.probe,
        p.price
    FROM times_{times_size} t
        ASOF JOIN prices_{prices_size} p
        ON t.probe >= p.time
    ) t;

针对以下数值矩阵：

• 价格表 – 10万到10亿行，按10倍步长递增；
• 时间表 – 1到2048行，按2倍步长递增（直到速度变得过慢）；
• 线程数 – 36、18和9；

结果如下

正如您所看到的，连接的二次方特性意味着“小”指的是“<= 64”。这相当小，但原始用户问题中的表只有 21 个值。

我们还可以看到，分段合并连接提供的排序似乎没有太大帮助，因此普通的嵌套循环连接是最佳选择。

很明显，标准运算符的性能在每个大小下都稳定，但随着线程数的增加而缓慢下降。这是有道理的，因为排序是计算密集型的，我们能分配的核心越少，所需的时间就越长。

如果您想进一步探究数据，可以在我们的 Tableau Public 网站上找到交互式可视化图表。

内存

循环连接计划在小数据量时明显更快，但这两种计划使用了多少内存呢？以下是发生过度分页或分配失败之前所需的大致内存量：

换句话说，循环连接计划只需要足够的内存来分页查找表！因此，如果表很大而您的内存有限，循环连接计划是最佳选择，即使它可能非常慢。请记住，循环连接计划必须与标准运算符在分页情况下的速度竞争，并且在达到某个临界点后，后者可能仍然更快。

备用方案

作为实验的一部分，我还测量了旧的 SQL 实现的性能，结果不尽如人意。在 10 亿行的级别，我不得不运行一次后就将其中止，以避免浪费时间。

请注意，这里的 Y 轴是对数刻度！

设置

虽然我们为进行此类计划选择提供了默认值是件好事，但正如他们所说，您的实际情况可能有所不同。如果您的时间比内存更充裕，那么提高循环连接阈值可能对您来说是值得的。该阈值是一个名为 asof_loop_join_threshold 的新设置，默认值为 64，您可以使用 PRAGMA 语句对其进行更改：

PRAGMA asof_loop_join_threshold = 128;

但请记住，这是一个二次方运算，将其设置得过高可能会花费很长很长的时间（尤其是如果您用古老的树人语来表达！）。

如果您希望禁用此功能，只需将其设置为零即可：

PRAGMA asof_loop_join_threshold = 0;

自行实现

此循环连接计划优化要到 v1.3 版本才会发布，但如果您今天遇到问题，可以随时编写自己的版本，如下所示：

SELECT
    first(t.probe) AS probe,
    arg_max(p.price, p.time) AS price
FROM prices p
INNER JOIN (
    SELECT
        *,
        row_number() OVER () AS pk
    FROM times
) t
ON t.probe >= p.time
GROUP BY pk
ORDER BY 1;

如果您知道探测时间是唯一的，您可以将其简化为：

SELECT
    t.probe,
    arg_max(p.price, p.time) AS price
FROM prices p
INNER JOIN times t
ON t.probe >= p.time
GROUP BY 1
ORDER BY 1;

未来工作

新的 AsOf 循环连接计划功能仅涵盖了一种常见但非常具体的情况，如果标准运算符知道数据已经排序，它的效率会大大提高。这种情况经常发生，但我们目前还没有能力跟踪运算符之间的分区和排序。跟踪这类元数据对于加速大量操作将非常有用，包括排序（！）、分区聚合、窗口化、AsOf 连接和合并连接。这是我们非常感兴趣的工作，敬请期待！

结论

向吉多·范罗苏姆致歉，通常做某件事不止一种方法，但每种方法可能具有截然不同的性能特征。作为一种拥有声明性查询语言（如 SQL）的关系型数据库，其职责之一就是在各种选项之间做出智能选择，以便用户可以专注于结果。在 DuckDB，我们期待找到更多规划查询的方法，让您可以专注于自己最擅长的事情！

备注

• 所有测试均在配备 2.3 GHz 18 核 Intel Xeon W CPU 和 128 GB 内存的 iMac Pro 上运行。
• 原始测试数据和可视化图表可在我们的 Tableau Public 存储库中获取。
• 生成数据的脚本位于我的公共 DuckDB 工具存储库中。