如何规避递归CTE中的禁用外连接？实现依赖对象修剪排序

问题描述 #

给定存储无环对象依赖关系的临时表：

CREATE TEMPORARY TABLE dependencies
(
    obj_id        bigint,
    depended_upon bigint NULL
);
INSERT INTO dependencies
VALUES
    (1, NULL), -- 1 不依赖任何对象
    (2, 1),    -- 2 依赖 1
    (3, 4),    -- 3 依赖 4
    (3, 2),    -- 3 同时依赖 2
    (4, NULL); -- 4 不依赖任何对象

需要计算从叶子节点（无依赖对象）开始的修剪顺序，确保修剪时不违反依赖关系：每个对象在所有依赖对象都已被修剪的首个步骤中处理。预期结果如下：

原尝试代码及报错 #

使用递归CTE时触发PostgreSQL语法错误：

WITH RECURSIVE deletion_order(obj_id, step) AS (
    SELECT obj_id, 0
    FROM dependencies
    GROUP BY obj_id
    HAVING COUNT(depended_upon) = 0
    UNION ALL
    SELECT dependencies.obj_id, step + 1
    FROM dependencies
             LEFT JOIN deletion_order ON dependencies.depended_upon = deletion_order.obj_id
    WHERE deletion_order.obj_id IS NULL
)
SELECT *
FROM deletion_order
ORDER BY step;

报错：

[42P19] ERROR: recursive reference to query "deletion_order" must not appear within an outer join

解决方案 #

方法1：基于依赖深度计算 #

每个对象的修剪步骤等于其所有依赖对象的最大步骤值加1，叶子节点步骤为0。该方法利用递归CTE计算每个节点的最长依赖路径长度：

WITH RECURSIVE obj_steps AS (
    -- 基础情况：无依赖的叶子节点，步骤0
    SELECT DISTINCT obj_id, 0 AS step
    FROM dependencies
    WHERE depended_upon IS NULL

    UNION ALL

    -- 递归计算：获取当前对象所有依赖的最大步骤，加1作为当前对象的步骤
    SELECT d.obj_id, MAX(os.step) + 1 AS step
    FROM dependencies d
    JOIN obj_steps os ON d.depended_upon = os.obj_id
    -- 跳过已计算过步骤的对象
    WHERE NOT EXISTS (SELECT 1 FROM obj_steps os2 WHERE os2.obj_id = d.obj_id)
    GROUP BY d.obj_id
)
SELECT obj_id, step
FROM obj_steps
ORDER BY step, obj_id;

方法2：模拟逐步修剪过程 #

每次找出所有依赖对象都已被修剪的对象，分配当前步骤，直到处理完所有对象：

WITH RECURSIVE pruning_process AS (
    -- 初始步骤：所有无依赖的叶子节点
    SELECT DISTINCT obj_id, 0 AS step
    FROM dependencies
    WHERE depended_upon IS NULL

    UNION ALL

    -- 后续步骤：筛选出所有依赖对象都已处理的未修剪对象
    SELECT DISTINCT d.obj_id, pp.step + 1 AS step
    FROM dependencies d
    CROSS JOIN pruning_process pp
    -- 确保当前对象的所有依赖都已被修剪
    WHERE NOT EXISTS (
        SELECT 1
        FROM dependencies d2
        WHERE d2.obj_id = d.obj_id
        AND d2.depended_upon NOT IN (SELECT obj_id FROM pruning_process)
    )
    -- 排除已处理的对象
    AND d.obj_id NOT IN (SELECT obj_id FROM pruning_process)
    GROUP BY d.obj_id, pp.step + 1
)
SELECT obj_id, step
FROM pruning_process
ORDER BY step, obj_id;

结果验证 #

两种方法均会输出符合预期的结果：

内容的提问来源于stack exchange，提问作者ravron