在递归 CTE 中使用 KEY

从片段组装 SQL 查询：CTE

随着 SQL 查询变得越来越复杂，管理其可读性、模块化和可重用性变得越来越具有挑战性。引入了 公用表表达式（CTE） 来解决这些问题，它允许开发人员在查询中定义临时的、命名的结果集。与编程中的函数类似，CTE 允许将大型查询分解为逻辑构建块，使其更易于理解、维护和调试。

CTE 特别适用于构建多步骤转换，否则可能需要深度嵌套的子查询或复杂的连接。通过提高 SQL 代码的清晰度和结构，CTE 已成为现代查询编写中不可或缺的工具——即使是最复杂的逻辑，也能通过它清晰、声明式地表达出来。

像 1999 年那样迭代：递归 CTE

为了增强 SQL 的表达能力，SQL:1999 标准引入了 递归 CTE。它们允许查询在同一表达式中引用前一次迭代的结果，从而使 SQL 能够解决更复杂的问题，例如图遍历和其他迭代计算。

这种能力将 SQL 推向了基本数据检索之外，允许直接在 SQL 中制定复杂的迭代逻辑。事实上，递归 CTE 使 SQL 成为图灵完备的，这意味着它理论上可以表达任何计算（在有足够时间和内存的情况下）。

但是，递归 CTE 在 DuckDB 中是如何工作的呢？

让我们看一个简单的例子来剖析其机制。假设我们要计算小于 100 的最大 2 的幂。我们可以使用递归 CTE power 迭代生成 2 的幂，直到达到该限制。对于 power 中的任何行 (a, b, c)，我们会有 a^b = c。

WITH RECURSIVE power(a, b, c) AS (
    SELECT 2, 0, 1       -- 2^0 = 1
        UNION
    SELECT a, b+1, a * c -- a^(b+1) = a * a^b
    FROM power           -- reads the working table (contains a single row)
    WHERE a * c < 100
)
FROM power;         -- reads the union table (contains all intermediate results)

我们可以将递归 CTE 分为两部分，由 UNION 关键字分隔。UNION 上方的部分是非递归部分（在我们的示例中是 SELECT 2, 0, 1），下方部分是递归部分。

在递归部分中，CTE power 引用自身。这种自引用指向我们所称的工作表。工作表始终包含紧接前一次迭代中生成的行。并且仅包含这些行。

其工作原理如下（分步说明）

• 首先，执行非递归部分，生成初始行——在我们的示例中，就是行 (2, 0, 1)。这些行存储在工作表中。
• 然后，使用工作表中的行执行递归部分。递归部分生成的每一新行都存储在中间表中，该表保存当前迭代的结果。
• 如果中间表为空，则迭代结束。
• 否则，我们清空工作表，并用中间表的内容替换它——为下一次迭代做准备。
• 我们还将中间表的内容添加到联合表中，该表累积所有迭代的中间结果。

在这里，您可以看到 CTE 每次迭代中涉及的三个表的条目

当递归 CTE 完成时，联合表将包含整个结果集，包括每次迭代中的所有中间行

┌───────┬───────┬───────┐
│   a   │   b   │   c   │ -- a^b = c
│ int32 │ int32 │ int32 │
├───────┼───────┼───────┤
│     2 │     0 │     1 │
│     2 │     1 │     2 │
│     2 │     2 │     4 │
│     2 │     3 │     8 │
│     2 │     4 │    16 │
│     2 │     5 │    32 │
│     2 │     6 │    64 │
└───────┴───────┴───────┘

联合表提供了幂计算历史的完整记录。这可能导致不必要的开销，特别是如果我们需要的是最后一行——递归的最终结果。存储每个中间值可能效率低下，特别是当不需要中间结果时，或者在处理大型数据集（涉及多行或宽行，例如存在数组类型列时）时。

递归 CTE 患有“失忆症”

虽然联合表在计算完成后保存了刚才提到的历史记录，但递归 CTE 在迭代进行时却患有“失忆症”：递归部分只能看到紧接前一次迭代的中间结果。这可能是一个限制，我们中的许多人都会看到查询作者如何通过手动维护数组（或类似的容器结构）来保存关于先前迭代的信息，从而规避此限制。这可能会代价高昂。然而，如果允许递归部分访问联合表及其所有累积的——可能相当大的——中间结果，那么在迭代过程中很容易产生性能问题。这是一个真正的难题。

使用 KEY 治愈失忆症

我们能否承受让递归部分访问联合表的代价？可以，但我们需要一种方法来控制其大小。因此，以仅追加模式操作联合表是行不通的。相反，让递归部分可选择性地用当前迭代中计算出的新信息覆盖联合表中的现有行。这可以显著减小联合表的大小（参见下面的实验）。

从版本 1.3 开始，DuckDB 推出了一种 带有 USING KEY 的递归 CTE 变体，它正是基于这个想法。

如果您想了解更多关于其起源的信息，请查阅 CIDR 2023。有关实现详情，请参阅 SIGMOD 2025。

与普通递归 CTE 相比，此变体引入了两个主要区别

1. 它不仅提供对工作表（一如既往）的访问，还提供对联合表的访问——我们现在称之为循环表。
2. 循环表不再仅仅将新行简单追加到自身，而是更像一个字典（类似于 Python 的 dict），允许基于键的更新。

要使用此新功能，请在递归 CTE 中添加 USING KEY (...) 子句

WITH RECURSIVE power(a, b, c) USING KEY (a)
    -- key: a, payload: b, c
AS (
    ...
);

使用 USING KEY，递归 CTE 的模式被分为键列和负载列。键列通过 USING KEY (列名) 子句指定，而其余列则被视为负载。

这种划分影响了循环表的行为方式。它不再在每次迭代中固执地追加新行，而是更像一个字典：如果递归部分返回一个以前未见的行，它会像往常一样被添加到循环表中。但是，如果一行与循环表中现有条目共享一个键，则负载会被更新——替换循环表中该键的先前值。

如果在单次迭代中生成了多个具有相同键的行，则只保留最后一个。因此，您可能希望在递归部分中使用 ORDER BY 子句来控制保留哪一行。

这种方法允许递归查询更有效地维护和更新状态，特别是对于保留给定键的最新（或“最佳”）值至关重要的算法。

覆盖旧的中间结果

让我们再次使用上面的递归示例查询。现在我们计算底数为 2 和 3 的幂，只要它们小于 100。

WITH RECURSIVE power(a, b, c) USING KEY (a) AS (
    FROM (VALUES (2, 0, 1), (3, 0, 1))   -- 2^0 = 1, 3^0 = 1
        UNION
    SELECT a, b+1, a * c                 -- a^(b+1) = a * a^b
    FROM power                           -- reads the working table (contains two rows)
    WHERE a * c < 100
)
FROM power;                              -- reads the recurring table (contains two rows)

我们从非递归部分的两行开始：一行键（底数）为 2，另一行键为 3。在递归部分，我们将中间的幂乘以底数。这会生成两行，键仍然是 2 和 3。

与普通递归 CTE 不同，我们不将这两新行追加到循环表中。相反，我们更新循环表中键为 2 和 3 的现有行，覆盖其负载值。因此，在整个计算过程中我们只保留两行，每行都在列 a 中存储其键（或底数）的当前幂值。

正如我们所看到的，循环表的大小保持不变。无关的计算历史被覆盖，从而导致内存使用量减少。最终的循环表内容为

┌───────┬───────┬───────┐
│   a   │   b   │   c   │ -- a^b = c
│ int32 │ int32 │ int32 │
├───────┼───────┼───────┤
│     2 │     6 │    64 │
│     3 │     4 │    81 │
└───────┴───────┴───────┘

这种行为对于我们关注给定键的最新、最佳或最小值的算法特别有用。循环表中的最大行数现在受唯一键数量的限制。由于使用的不同键的数量由递归部分控制，这在处理大型数据集时可以是一个强大的优势。

键的改变

现在，如果您碰巧对计算历史感兴趣，并且愿意投入内存空间，那么所需要的只是改变键。通过

WITH RECURSIVE power(a, b, c)
    USING KEY (a, b)
AS (  -- formerly: USING KEY (a)
    ...
)
FROM power
ORDER BY a, b;

列 b 中的迭代计数器（或指数）也被视为键的一部分。因此，循环表将跟踪唯一的 (a, b) 组合（即底数、指数），我们能够追踪迭代过程中发生的一切。

┌───────┬───────┬───────┐
│   a   │   b   │   c   │
│ int32 │ int32 │ int32 │
├───────┼───────┼───────┤
│     2 │     0 │     1 │
│     2 │     1 │     2 │
│     2 │     2 │     4 │
│     2 │     3 │     8 │
│     2 │     4 │    16 │
│     2 │     5 │    32 │
│     2 │     6 │    64 │
│     3 │     0 │     1 │
│     3 │     1 │     3 │
│     3 │     2 │     9 │
│     3 │     3 │    27 │
│     3 │     4 │    81 │
└───────┴───────┴───────┘

访问相关历史记录

与普通递归 CTE 的另一个主要区别是：现在循环表的大小受到控制，我们可以直接在 CTE 的递归部分中引用它。这使我们能够访问尚未被覆盖的任何中间结果——无论这些结果是由哪次迭代计算的。不再有失忆症！要访问循环表，只需在 CTE 名称前加上伪模式名称 recurring。

WITH RECURSIVE t(...) USING KEY (...) AS (
    ...
    FROM recurring.t  -- reads the recurring table while we iterate
)
...;

USING KEY 可释放性能优势

为了进一步强调普通 CTE 和基于键的 CTE 之间的差异，让我们考虑一个使用图数据集的更复杂示例——社交网络图。

这些图表源自 LDBC 社交网络基准（SNB），该基准提供了一个合成社交网络数据的生成器。为了使图表更易于与 WITH RECURSIVE 查询一起使用，我们根据人名对其进行了进一步筛选，从而降低了它们的密度。

在这个数据集中，节点代表人，而边则表示他们之间的关系。我们正在使用的表是 Person(id)，它包含网络中所有现有的 ID，以及 knows(person1id, person2id)，其中每行包含一对相互认识的人。

如果您想亲自尝试，请首先将数据库附加到任何 DuckDB 会话中。

ATTACH 'https://blobs.duckdb.org/data/using-key-graph.duckdb';
USE 'using-key-graph';

我们的目标是计算社交网络中所有人对之间的最短路径。由于这是一个固有的二次复杂度问题，我们需要密切关注运行时和内存需求。对于每对，我们首先添加一行，其中一个人作为起始节点，另一个人作为目标节点。然后我们迭代地探索起始节点认识的所有个体，继续遍历直到到达目标人物。网络中的路径由 via 节点编码：要从起始节点到达目标，首先前往 via 节点（起始节点的直接邻居）——到达那里后，使用该节点的 via 条目继续您的遍历。

实现此方法的递归 CTE 如下所示

WITH RECURSIVE paths(here, current, via, len, there, completed, found) AS (
  SELECT n1.id AS here, n1.id AS current, NULL::BIGINT AS via,
         0 AS len, n2.id AS there, false AS completed, false AS found
    FROM Person AS n1 JOIN Person AS n2 ON (n2.id <> n1.id)
    UNION ALL
  SELECT paths.here,
         person2id AS current,
         coalesce(paths.via, knows.person2id) AS via,
         paths.len+1 AS len,
         paths.there,
         bool_or(knows.person2id = paths.there)
                 OVER (PARTITION BY paths.here, paths.there
                       ROWS BETWEEN UNBOUNDED PRECEDING
                                AND UNBOUNDED FOLLOWING) AS completed,
         knows.person2id = paths.there AS found
      FROM paths
      JOIN knows ON (paths.current = knows.person1id AND NOT paths.completed)
 )
 SELECT here, there, via, len
 FROM paths WHERE found
 ORDER BY len, here, there;

递归 CTE paths 的工作表有七列

• here 指的是遍历开始的人，
• there 指的是我们旨在达到的目标人，
• via 表示当前路径起始节点的直接邻居，
• len 是当前路径的长度，遍历中每走一步都会加一。

其余三列控制遍历逻辑并优化计算。

• current 指的是遍历过程中当前正在探索的节点，
• found 表示当前路径是否已成功到达目标人物，
• completed 跟踪是否已有任何具有相同 here 和 there 的路径已到达目标。一旦找到最短路径，这会阻止该对的进一步遍历，从而避免探索更长的路径。

如果我们在一个包含许多边的大型图中进行搜索，普通递归 CTE 中的联合表可能会变得非常大，可能超出内存限制。这不仅会导致严重的性能问题，在极端情况下甚至可能导致 查询崩溃。

新的基于键的 CTE 通过改变搜索状态的维护方式来避免此问题。这使得一系列新算法能够在 SQL 中高效表达，包括在大型图中寻找最短路径的算法。

其中一种算法是 距离向量路由（DVR），这是一种基于指示“下一步跳到哪里”的节点本地路由表来计算网络中最短路径的方法。

• 在 DVR 中，每个节点都维护一个路由表，记录到达其他节点的路径长度。
• 我们使用循环表来存储网络中所有节点的这些路由表：一行 (here, there, via, len) 表示从节点 here 到节点 there 的路径上的第一个跳点是节点 via。总路径的长度是 len。
• 当找到到达目标节点的更短路径时，相应的路由表条目会更新。
• 在上次迭代中找到的路由更新通过工作表分发到相邻节点。

为了检查新传入的路由更新是否改善了当前已知路径，我们在循环表中执行查找。如果新长度小于已知路径的长度，我们更新该条目并将更新传播到我们的直接邻居。这种机制即使在非常大的图中也能实现高效的路径查找——请参见下文 DVR 如何胜过上述基于普通递归 CTE 的方法。

WITH RECURSIVE dvr(here, there, via, len) USING KEY (here, there) AS (
  -- initialize routing tables for all nodes, only the routes to
  -- immediate neighbors are known at this time
  SELECT n.person1id AS here, n.person2id AS there, n.person2id AS via, 1::DOUBLE AS len
  FROM   knows AS n
    UNION
  (SELECT n.person1id AS here, dvr.there, dvr.here AS via, 1 + dvr.len AS len
    FROM dvr -- working table - routing updates shared by neighbors
    JOIN knows AS n ON
        (n.person2id =  dvr.here AND    -- send update only to immediate neighbors
        n.person1id <> dvr.there)       -- no need to store a route to myself
    LEFT JOIN recurring.dvr AS rec ON   -- recurring table (current routing tables)
        (rec.here = n.person1id AND rec.there = dvr.there) -- identify affected routing table entry
    WHERE 1 + dvr.len < coalesce(rec.len, 'Infinity'::DOUBLE) --  does the routing update improve the entry in the routing table?
    ORDER BY len -- shortest path first
  )
)
FROM dvr
ORDER BY len, here, there;

社交网络图（A 到 G）越大，普通递归 CTE（REC）与新的 USING KEY 变体（KEY）之间的性能差距就越明显。下表报告了每次迭代中处理的行数

即使对于最小的图（图 A），差异也很大：REC CTE 产生大约 350,000 行，而 KEY 只生成 744 行。随着图规模的增加，差距变得更加显著。在图 C 中，包含 424 个节点和 1,446 条边，REC 方法处理了近 10 亿行，而 KEY 方法处理的行数不到 20,000 行。尽管这并非我们基准测试中最大的图，但 REC 方法已接近内存不足（OOM，❌）的情况。

内存使用量的巨大差异只是故事的一部分。REC 方法的性能也迅速下降。虽然两种 CTE 在小图上表现相似，但随着图的增长，REC 的速度显著变慢——最终导致崩溃——而 KEY 则继续平稳扩展。

这就是新 USING KEY CTE 的美妙之处。它通过提供对每次迭代之间传递的中间结果大小的基于键的控制，实现了更高效的复杂迭代算法表达——内存压力减轻，运行时性能可以显著提升。如果您正在 DuckDB 中使用递归 CTE，请务必利用这一强大功能——它可能会对您的查询产生显著影响。