如何优化PostgreSQL递归SQL查询以寻找最低成本路径

我在PostgreSQL中编写递归SQL查询，用于计算从蒙特利尔出发前往各城市的最低成本。数据采用有向无环图（DAG）结构，航班连接存储在Flights表中，包含src（出发城市）、dst（到达城市）和cost（航班成本）字段。

示例：
Route 1: Montreal → Toronto → LA, total cost: $2000
Route 2: Montreal → Chicago → LA, total cost: $1800

这种场景下，查询应仅返回前往LA的最低成本航线，总成本为1800美元。现有查询已能找到最低成本路径，但需要进一步优化，核心需求是：

• 递归过程中筛选路径，仅保留每个目的地的最低总成本
• 避免重复访问路径中已包含的城市或连接

现有查询代码 #

WITH RECURSIVE CheapestFlight AS 
(
    SELECT src, dst, cost AS total_price
    FROM Flights
    WHERE src = 'Montreal'
    UNION
    SELECT cf.src, f.dst, cf.total_price + f.cost AS total_price
    FROM CheapestFlight cf
    INNER JOIN Flights f ON f.src = cf.dst
)
SELECT dst as destination, total_price
FROM CheapestFlight cf
WHERE total_price = (SELECT MIN(total_price)
                     FROM CheapestFlight
                     WHERE dst = cf.dst)

优化建议 #

1. 递归阶段实时过滤最低成本与重复城市

原查询会生成所有可能路径，最后再计算最小值，对于大规模DAG效率极低。可以在递归过程中就过滤掉无效路径，只保留每个目的地的最低成本记录：

WITH RECURSIVE CheapestFlight AS (
    -- 初始节点：蒙特利尔出发的所有直飞航班，同时记录路径
    SELECT 
        src, 
        dst, 
        cost AS total_price,
        ARRAY[src, dst] AS path
    FROM Flights
    WHERE src = 'Montreal'
    
    UNION ALL
    
    -- 递归阶段：仅保留更优路径
    SELECT 
        cf.src, 
        f.dst, 
        cf.total_price + f.cost AS total_price,
        cf.path || f.dst AS path
    FROM CheapestFlight cf
    INNER JOIN Flights f ON f.src = cf.dst
    -- 避免路径中重复访问城市（即使DAG无环，也能过滤绕路的无效路径）
    WHERE NOT f.dst = ANY(cf.path)
    -- 只保留比当前已知该目的地成本更低的路径
    AND (cf.total_price + f.cost) < COALESCE(
        (SELECT MIN(total_price) FROM CheapestFlight WHERE dst = f.dst),
        infinity
    )
)
-- 按目的地分组取最低成本
SELECT 
    dst AS destination, 
    MIN(total_price) AS lowest_cost
    -- 如需返回具体路径，可添加：ARRAY_AGG(path ORDER BY total_price LIMIT 1) AS cheapest_path
FROM CheapestFlight
GROUP BY dst;

优化点说明：

• 用path数组记录已访问城市，通过NOT f.dst = ANY(cf.path)过滤重复访问的路径
• 递归时直接校验新路径成本是否优于已有记录，减少CTE中的数据量，大幅提升性能
• 用UNION ALL替代UNION，避免不必要的去重操作

2. 利用DAG拓扑排序特性优化

由于数据是DAG结构，可以先对节点做拓扑排序，再按顺序计算各节点的最低成本，这种方式比无约束递归更高效：

WITH RECURSIVE TopologicalPath AS (
    SELECT 
        src,
        dst,
        cost AS total_price,
        ARRAY[src, dst] AS path
    FROM Flights
    WHERE src = 'Montreal'
    UNION ALL
    SELECT 
        tp.src,
        f.dst,
        tp.total_price + f.cost AS total_price,
        tp.path || f.dst AS path
    FROM TopologicalPath tp
    JOIN Flights f ON tp.dst = f.src
    WHERE NOT f.dst = ANY(tp.path)
),
FinalCosts AS (
    SELECT 
        dst AS destination,
        MIN(total_price) AS lowest_cost
    FROM TopologicalPath
    GROUP BY dst
)
SELECT * FROM FinalCosts;

优化点说明：

• 拓扑排序保证了节点的处理顺序符合DAG的依赖关系，避免反向递归
• 结合路径过滤，进一步减少无效计算

3. 添加索引加速查询

为Flights表创建针对性索引，提升递归中的JOIN和查询效率：

-- 加速src字段的JOIN操作
CREATE INDEX idx_flights_src ON Flights(src);

-- 覆盖查询所需字段，避免回表
CREATE INDEX idx_flights_src_dst_cost ON Flights(src, dst, cost);

4. 替换子查询为GROUP BY简化最终计算

原查询末尾用子查询求每个目的地的最小值，换成GROUP BY更高效，避免逐行子查询的开销：

-- 替换原最终查询部分
SELECT dst AS destination, MIN(total_price) AS lowest_cost
FROM CheapestFlight
GROUP BY dst;

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