如何用SQL高效获取有向图中指定节点到所有连通节点的路径？

问题背景 #

我们有一个大型SQLite表edge，表结构为：

CREATE TABLE edge(from TEXT, to TEXT);

该表存储有向图（可能含环）的所有边，图中每个节点拥有唯一TEXT类型ID。需求是高效查找指定节点到所有连通节点的路径，若两节点间存在多条路径，仅需返回任意一条。由于图规模极大，先获取所有可能路径再去重的方式效率过低。

示例 #

指定起始节点为A时，预期返回结果（非唯一）：

A->B
A->B->E
A->B->E->C
A->F

现有方案的问题 #

曾尝试递归CTE方案，但图规模大时速度极慢。原代码如下：

WITH RECURSIVE cte(to, chain) AS (
    SELECT edge.to, edge.to || '->' || edge.from FROM edge
        WHERE edge.from = 'A'
    UNION ALL
    SELECT edge.to, edge.to || '->' || cte.chain FROM edge
        JOIN cte
        ON cte.to = edge.from
)
SELECT MIN(chain) as selected_chain FROM cte
GROUP BY cte.to
ORDER BY selected_chain

核心问题：

• 使用UNION ALL会生成大量重复路径（包括环带来的无效路径），后续GROUP BY和MIN()的计算成本极高
• 每次递归拼接字符串生成路径，耗时且产生大量冗余数据
• 未跟踪已访问节点，导致递归过程中反复处理同一节点的多条路径

优化方案 #

1. 添加索引加速基础查询 #

首先给edge表的from字段创建索引，这是递归查询的核心关联条件，能大幅减少JOIN操作的时间：

CREATE INDEX idx_edge_from ON edge(`from`);

2. 跟踪已访问节点，避免无效递归 #

在递归CTE中加入visited字段，记录已访问的节点集合，从根源避免循环和重复访问同一节点：

WITH RECURSIVE cte(current_node, path, visited) AS (
    -- 起始节点初始化：路径为自身，已访问集合包含自身
    SELECT 'A', 'A', 'A'
    UNION ALL
    SELECT 
        e.to, 
        cte.path || '->' || e.to, 
        cte.visited || ',' || e.to
    FROM edge e
    JOIN cte ON e.from = cte.current_node
    -- 仅处理未访问过的节点，阻断环和重复路径
    WHERE NOT cte.visited LIKE '%,' || e.to || ',%'
)
-- 用DISTINCT ON确保每个目标节点只返回第一条找到的路径
SELECT DISTINCT ON (current_node) path
FROM cte
WHERE current_node != 'A' -- 排除起始节点自身
ORDER BY current_node, path;

DISTINCT ON (current_node)是SQLite支持的语法，比原方案的GROUP BY+MIN()效率更高，无需计算所有路径的最小值。

3. 路径存储优化（可选） #

如果节点ID较长，拼接字符串会占用大量内存，可改用JSON数组存储路径，内存占用更低，拼接效率更高：

WITH RECURSIVE cte(current_node, path_arr, visited) AS (
    SELECT 'A', json_array('A'), json('["A"]')
    UNION ALL
    SELECT 
        e.to, 
        json_insert(cte.path_arr, '$[#]', e.to),
        json_insert(cte.visited, '$[#]', e.to)
    FROM edge e
    JOIN cte ON e.from = cte.current_node
    -- 用JSON函数判断节点是否已访问
    WHERE NOT json_contains(cte.visited, json('"' || e.to || '"'))
)
-- 将JSON数组格式化为指定字符串格式
SELECT 
    json_group_array(value) ->> '$' AS path
FROM (
    SELECT DISTINCT ON (current_node) path_arr
    FROM cte
    WHERE current_node != 'A'
) t, json_each(t.path_arr)
GROUP BY t.path_arr;

4. 优先返回最短路径（可选） #

如果需要优先获取最短路径，可以在递归时记录路径长度，通过窗口函数筛选最短路径：

WITH RECURSIVE cte(current_node, path, length, visited) AS (
    SELECT 'A', 'A', 0, 'A'
    UNION ALL
    SELECT 
        e.to, 
        cte.path || '->' || e.to, 
        cte.length + 1,
        cte.visited || ',' || e.to
    FROM edge e
    JOIN cte ON e.from = cte.current_node
    WHERE NOT cte.visited LIKE '%,' || e.to || ',%'
)
SELECT path
FROM (
    SELECT 
        path,
        current_node,
        ROW_NUMBER() OVER (PARTITION BY current_node ORDER BY length) AS rn
    FROM cte
    WHERE current_node != 'A'
) t
WHERE rn = 1
ORDER BY path;

关键优化点总结 #

• 给edge.from加索引，大幅加速JOIN操作
• 跟踪已访问节点，从根源减少无效递归和环的产生
• 使用DISTINCT ON或窗口函数替代GROUP BY+MIN()，降低计算开销
• 按需选择路径存储格式（字符串/JSON数组），平衡可读性与性能

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