有向图全关联节点遍历优化：支持双向边适配千万级数据查询场景

原递归CTE性能劣化根因与优化方案 #

原写法性能差的核心原因是LEAST/GREATEST函数作用于索引列后，无法命中a、b列的单列索引，导致每次关联都要全表扫描。可以把双向匹配拆成两个独立的关联分支，完全规避函数调用，即可用到现有索引：

WITH RECURSIVE traverse(id, path, cycle) AS (
    SELECT a, ARRAY[a], false
    FROM foo WHERE a = 1
    UNION ALL
    -- 匹配正向边 a->b
    SELECT b, traverse.path || b, b = ANY(traverse.path)
    FROM traverse
    INNER JOIN foo ON foo.a = traverse.id
    WHERE NOT cycle AND b <> ALL(traverse.path)
    UNION ALL
    -- 匹配反向边 b->a
    SELECT a, traverse.path || a, a = ANY(traverse.path)
    FROM traverse
    INNER JOIN foo ON foo.b = traverse.id
    WHERE NOT cycle AND a <> ALL(traverse.path)
)
SELECT DISTINCT id FROM traverse;

该写法可以完全命中a、b列的单列索引，性能和去掉函数的单方向遍历版本基本一致。

现有迭代方案的优化空间 #

你当前的迭代实现已经适配了小连通子图的场景，还可以从以下几个维度进一步优化：

• 索引优化：将现有单列索引替换为覆盖索引，避免回表查询：

CREATE INDEX idx_edges_from_to ON edges("from", "to");
CREATE INDEX idx_edges_to_from ON edges("to", "from");

• 去重逻辑优化：由于两个方向的查询已经通过NOT("to" = ANY(var_node_ids))过滤了已访问节点，可将UNION替换为UNION ALL + DISTINCT，减少全局排序开销：

var_iteration_node_ids := ARRAY(
    SELECT DISTINCT node FROM (
        SELECT "to" AS node FROM edges
          WHERE "from" = ANY(var_iteration_node_ids)
          AND NOT("to" = ANY(var_node_ids))
        UNION ALL
        SELECT "from" AS node FROM edges
          WHERE "to" = ANY(var_iteration_node_ids)
          AND NOT("from" = ANY(var_node_ids))
    ) t
);

• 访问集合判断优化：如果后续连通子图规模变大，数组ANY判断性能会下降，可改用临时表存储已访问节点，通过主键索引的EXISTS判断代替数组匹配，性能更稳定。

千万级数据量场景适配思路 #

针对你提到的5000万+边、单连通子图节点数不超过100的业务特征，最高效的方案是预计算连通分量：

• 离线跑批计算每个节点所属的连通分量ID，单独存储一张表node_component，结构为node_id INT PRIMARY KEY, component_id INT
• 查询时仅需通过起始节点ID查到对应的component_id，再取出该分量下的所有节点即可，耗时稳定在1ms级别
• 如果图有增量更新，可每次新增边时判断两个端点所属的分量，若分量不同则合并两个分量的所有节点的component_id，增量更新成本极低。

如果图是高频实时更新、无法接受预计算延迟，也可以选择将边存为双向冗余格式：每条有向边存储为(a,b)和(b,a)两条记录，查询时仅需单方向遍历，无需每次union两个方向的查询，性能可提升50%以上。

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