PostgreSQL中从黄边出发遍历关联蓝边的多路径图遍历实现咨询

我有一张存储图边的SQL表，包含fromNodes、toNodes，以及edgeType、edgeLength两个边属性。我的目标是先查询所有黄色边，再以每条黄色边为起点，构建由所有连通蓝色边组成的图路径。

已完成实现步骤 #

步骤1：查询所有黄色边 #

实现逻辑简单，代码如下：

WITH 
  YellowEdges AS
  (SELECT EdgeId, FromNodeID, ToNodeID,EdgeType,EdgeLength,array_append(GraphNetwork.EDGES,GraphNetwork.EdgeId) AS EdgePathArray
     FROM GraphNetwork
  WHERE EdgeType = 3
  )
  
SELECT * 
FROM YellowEdge

执行后得到所有黄色边：1、4、6、9、15

步骤2：查询所有蓝色边 #

代码如下：

WITH
  YellowEdges AS
  (SELECT EdgeId, FromNodeID, ToNodeID,EdgeType,EdgeLength,array_append(GraphNetwork.EDGES,GraphNetwork.EdgeId) AS EdgePathArray
     FROM GraphNetwork
  WHERE EdgeType = 3
  ),
  BlueEdges AS 
  (SELECT *
  FROM GraphNetwork
  WHERE EdgeType = 2
  )

SELECT *
FROM BlueEdges

步骤3：查找所有指向黄色边的蓝色边 #

执行左连接，将黄色边和蓝色边都添加到名为EdgePathArray的数组列中：

WITH
  YellowEdges AS
  (SELECT EdgeId, FromNodeID, ToNodeID,EdgeType,EdgeLength,array_append(GraphNetwork.EDGES,GraphNetwork.EdgeId) AS EdgePathArray
     FROM GraphNetwork
  WHERE EdgeType = 3
  ),
  BlueEdges AS 
  (SELECT *
  FROM GraphNetwork
  WHERE EdgeType = 2
  ),
  EdgePathTable AS
  (SELECT *
  FROM (
    SELECT BlueEdges.EdgeId, BlueEdges.FromNodeID, BlueEdges.ToNodeID,BlueEdges.EdgeType,BlueEdges.EdgeLength,array_append(YellowEdges.EdgePathArray,BlueEdges.EdgeId) AS EdgePathArray
    FROM YellowEdges
    LEFT JOIN BlueEdges
    ON YellowEdges.EdgeId <> BlueEdges.EdgeId 
    AND YellowEdges.FromNodeID = BlueEdges.ToNodeID 
       ) AS unnamedTable
  )
  
SELECT * 
FROM EdgePathTable

步骤4：查找所有与上一步识别的蓝色边相连的蓝色边 #

将其添加到路径中（确保新边未被当前路径遍历过，避免生成环）：

WITH
  YellowEdges AS
  (SELECT EdgeId, FromNodeID, ToNodeID,EdgeType,EdgeLength,array_append(GraphNetwork.EDGES,GraphNetwork.EdgeId) AS EdgePathArray
     FROM GraphNetwork
  WHERE EdgeType = 3
  ),
  BlueEdges AS 
  (SELECT *
  FROM GraphNetwork
  WHERE EdgeType = 2
  ),
  EdgePathTable AS
  (SELECT *
  FROM (
    SELECT BlueEdges.EdgeId, BlueEdges.FromNodeID, BlueEdges.ToNodeID,BlueEdges.EdgeType,BlueEdges.EdgeLength,array_append(YellowEdges.EdgePathArray,BlueEdges.EdgeId) AS EdgePathArray
    FROM YellowEdges
    LEFT JOIN BlueEdges
    ON YellowEdges.EdgeId <> BlueEdges.EdgeId 
    AND YellowEdges.FromNodeID = BlueEdges.ToNodeID 
       ) AS unnamedTable
  )

SELECT *
FROM (SELECT EdgePathTable_iteration2.EdgeId, EdgePathTable_iteration2.FromNodeID, EdgePathTable_iteration2.ToNodeID,EdgePathTable_iteration2.EdgeType,EdgePathTable_iteration2.EdgeLength,array_append(EdgePathTable.EdgePathArray,EdgePathTable_iteration2.EdgeId) AS EdgePathArray
FROM EdgePathTable
LEFT JOIN BlueEdges AS EdgePathTable_iteration2
ON EdgePathTable_iteration2.EdgeId <> any(EdgePathTable.EdgePathArray) 
AND EdgePathTable.FromNodeID = EdgePathTable_iteration2.ToNodeID) AS EdgePathTable

步骤5：重复迭代 #

需要重复步骤4直到满足终止条件，例如完成指定迭代次数，或者所有路径都到达终点。

当前卡点 #

• 对递归CTE可行性存疑：递归CTE依赖union，似乎无法结合左连接实现，现有树遍历示例多仅支持单条边作为起点，不确定是否支持多路径遍历，且需要适配10万到100万条边的生产库。
• 函数调用方案复杂度高：无法直接将表作为参数传递给函数，类表结构参数的实现方式不明确。
• while循环方案缺少参考资料：没有找到PostgreSQL查询中实现while循环的易懂文档，基础while逻辑无法在SQL fiddle中运行。

测试表结构与示例代码 #

CREATE TABLE GraphNetwork 
(
    EdgeId INT primary key,
    FromNodeID INT,  
    ToNodeID INT,
    EdgeType INT,
    EdgeLength INT,
    EDGES INT[]
);

INSERT INTO GraphNetwork (EdgeId, FromNodeID, ToNodeID, EdgeType, EdgeLength)
VALUES
    (1,2,1,3,10),
    (2,3,2,2,50),
    (3,4,3,2,40),
    (4,5,4,3,15),
    (5,5,16,2,60),
    (6,4,5,3,20),
    (7,3,4,2,80),
    (8,2,3,2,25),
    (9,7,6,3,5),
    (10,8,7,2,20),
    (11,9,8,2,35),
    (12,7,9,2,10),
    (13,10,9,2,10),
    (14,11,10,1,15),
    (15,13,12,3,25),
    (16,14,13,2,25),
    (17,15,14,1,30)
;

WITH YellowEdges AS
(
    SELECT 
        EdgeId, FromNodeID, ToNodeID, EdgeType, EdgeLength,
        array_append(GraphNetwork.EDGES, GraphNetwork.EdgeId) AS EdgePathArray
    FROM 
        GraphNetwork
    WHERE 
        EdgeType = 3
),
BlueEdges AS 
(
    SELECT *
    FROM GraphNetwork
    WHERE EdgeType = 2
),
EdgePathTable AS
( 
    SELECT *
    FROM 
        (SELECT 
             BlueEdges.EdgeId, BlueEdges.FromNodeID, BlueEdges.ToNodeID,
             BlueEdges.EdgeType, BlueEdges.EdgeLength,
             array_append(YellowEdges.EdgePathArray, BlueEdges.EdgeId) AS EdgePathArray
         FROM 
             YellowEdges
         LEFT JOIN 
             BlueEdges ON YellowEdges.EdgeId <> BlueEdges.EdgeId 
                       AND YellowEdges.FromNodeID = BlueEdges.ToNodeID 
        ) AS unnamedTable
)
SELECT *
FROM 
    (SELECT 
         EdgePathTable_iteration2.EdgeId, 
         EdgePathTable_iteration2.FromNodeID, 
         EdgePathTable_iteration2.ToNodeID,
         EdgePathTable_iteration2.EdgeType,
         EdgePathTable_iteration2.EdgeLength,
         array_append(EdgePathTable.EdgePathArray, EdgePathTable_iteration2.EdgeId) AS EdgePathArray
     FROM 
         EdgePathTable
     LEFT JOIN 
         BlueEdges AS EdgePathTable_iteration2 ON EdgePathTable_iteration2.EdgeId <> ANY(EdgePathTable.EdgePathArray) 

                                               AND EdgePathTable.FromNodeID = EdgePathTable_iteration2.ToNodeID) AS EdgePathTable

递归CTE完全可以满足多起点路径遍历的需求，不需要额外使用while循环或者自定义函数，性能在百万级边的场景下加对应索引即可支撑，实现代码如下：

WITH RECURSIVE graph_traversal AS (
    -- 递归锚点：所有黄色边作为初始路径
    SELECT 
        EdgeId,
        FromNodeID,
        ToNodeID,
        EdgeType,
        EdgeLength,
        ARRAY[EdgeId] AS EdgePathArray,
        FromNodeID AS current_start_node
    FROM GraphNetwork
    WHERE EdgeType = 3

    UNION ALL

    -- 递归部分：每次迭代关联相连的蓝色边
    SELECT 
        b.EdgeId,
        b.FromNodeID,
        b.ToNodeID,
        b.EdgeType,
        b.EdgeLength,
        array_append(g.EdgePathArray, b.EdgeId) AS EdgePathArray,
        b.FromNodeID AS current_start_node
    FROM graph_traversal g
    JOIN GraphNetwork b
        ON b.EdgeType = 2
        AND b.ToNodeID = g.current_start_node
        AND b.EdgeId <> ALL(g.EdgePathArray) -- 过滤已遍历边避免环
)
SELECT * FROM graph_traversal
ORDER BY EdgePathArray;

生产环境优化建议 #

1. 为EdgeType、FromNodeID、ToNodeID添加联合索引，可大幅提升关联查询效率。
2. 若业务场景对路径深度有要求，可在递归条件中添加深度限制，例如array_length(g.EdgePathArray,1) < 20，避免过长路径占用过多计算资源。
3. 若仅需输出无法继续延伸的完整路径，可在最终查询时添加过滤条件，排除仍有可关联蓝色边的中间路径。

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