如何用SQL递归查询计算人物间的关联步数？

现有数据表 #

假设数据库表（假设表名为person_pairs）结构及示例数据如下：

该表包含约6万行人物配对数据，配对可重复且无固定方向（比如人物1也可直接与人物3配对）。

需求 #

计算任意两人之间的最短关联步数，例如人物1到人物4的关联路径为1->2->3->4，步数为3。期望输出格式如下：

已知可通过递归查询实现，但不清楚具体思路。

实现思路与代码 #

递归查询分为锚点成员和递归成员两部分，核心是逐层遍历关联关系，记录已访问的节点避免循环，直到找到目标节点或遍历完所有可达节点。

单人物对查询示例 #

假设要查询person1_id = 1到person2_id = 4的步数：

WITH RECURSIVE path AS (
    -- 锚点：起始节点的直接配对，步数初始为1
    SELECT 
        person1_id AS start_id, 
        person2_id AS end_id, 
        1 AS steps,
        -- 用数组记录已访问节点，防止循环
        ARRAY[person1_id, person2_id] AS visited
    FROM person_pairs
    WHERE person1_id = 1

    UNION ALL

    -- 递归：基于已找到的路径，扩展下一层关联
    SELECT 
        p.start_id, 
        pp.person2_id AS end_id, 
        p.steps + 1 AS steps,
        p.visited || pp.person2_id AS visited
    FROM path p
    JOIN person_pairs pp ON p.end_id = pp.person1_id
    -- 避免重复访问同一节点，防止无限递归
    WHERE NOT pp.person2_id = ANY(p.visited)
)
-- 取到目标节点的最短步数
SELECT start_id AS person1_id, end_id AS person2_id, MIN(steps) AS steps
FROM path
WHERE end_id = 4
GROUP BY start_id, end_id;

关键说明 #

• 锚点成员：从目标起始人物的直接配对数据开始，初始化步数为1，同时用数组记录已访问的人物ID。
• 递归成员：将上一层路径的终点作为新起点，关联配对表获取下一层关联人物，步数加1并更新已访问数组。
• 防循环处理：通过NOT pp.person2_id = ANY(p.visited)确保不会重复访问同一人物，避免因循环配对导致的无限递归。
• 最短步数获取：同一人物对可能存在多条关联路径，用MIN(steps)筛选出最短的步数。

批量查询所有人物对的步数 #

如果需要计算所有人物对之间的最短步数，可以修改锚点为所有人物的直接配对，最后过滤掉同一人物的无效数据：

WITH RECURSIVE path AS (
    SELECT 
        person1_id AS start_id, 
        person2_id AS end_id, 
        1 AS steps,
        ARRAY[person1_id, person2_id] AS visited
    FROM person_pairs

    UNION ALL

    SELECT 
        p.start_id, 
        pp.person2_id AS end_id, 
        p.steps + 1 AS steps,
        p.visited || pp.person2_id AS visited
    FROM path p
    JOIN person_pairs pp ON p.end_id = pp.person1_id
    WHERE NOT pp.person2_id = ANY(p.visited)
)
SELECT start_id AS person1_id, end_id AS person2_id, MIN(steps) AS steps
FROM path
WHERE start_id != end_id
GROUP BY start_id, end_id
ORDER BY start_id, end_id;

注意：6万行数据量较大，批量查询时建议先添加person1_id和person2_id的索引优化性能，也可根据需求限制查询范围，避免全量遍历导致的性能问题。

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