如何用带节点可见性条件的递归CTE压缩SQL Server路径？

我在SQL Server中处理节点间路径的数据集，每个节点带有可见性标识（IsVisible）。目标是跳过不可见节点（IsVisible=0），直接连接可见节点来压缩路径，例如将A->B(不可见)->C(不可见)->D转换为A->D。

表结构及示例数据 #

路径以起始、结束节点对存储，包含两者的可见性标识：

CREATE TABLE Paths (
    StartNode CHAR(1),
    EndNode CHAR(1),
    StartNodeIsVisible BIT,
    EndNodeIsVisible BIT
);

INSERT INTO Paths (StartNode, EndNode, StartNodeIsVisible, EndNodeIsVisible) VALUES
('A', 'B', 1, 0),
('B', 'C', 0, 0),
('C', 'D', 0, 1),
('D', 'E', 1, 1);

期望结果 #

尝试的递归CTE代码 #

我尝试用递归CTE实现，但无法正确跳过不可见节点，且在大数据集下性能极差：

WITH RecursivePaths AS (
    SELECT StartNode, EndNode, StartNodeIsVisible, EndNodeIsVisible, 1 AS Depth
    FROM Paths
    WHERE StartNodeIsVisible = 1

    UNION ALL

    SELECT rp.StartNode, p.EndNode, rp.StartNodeIsVisible, p.EndNodeIsVisible, Depth + 1
    FROM RecursivePaths rp
    JOIN Paths p ON rp.EndNode = p.StartNode
    WHERE p.EndNodeIsVisible = 1 OR (p.EndNodeIsVisible = 0 AND Depth < 50)
)
SELECT *
FROM RecursivePaths
WHERE EndNodeIsVisible = 1
OPTION (MAXRECURSION 200);

该代码在小数据集上能运行，但处理1500万行的表时，读取量达到6亿次，不得不终止执行，还曾出现「递归深度100耗尽」的错误，因此添加了OPTION (MAXRECURSION 200)。

待解决问题 #

1. 如何调整递归CTE，仅保留可见节点间的路径，有效跳过中间不可见节点？
2. 有没有更高效的写法来处理大数据集的大量路径？（接受任何可行方案）

一、优化递归CTE逻辑 #

核心思路：仅追踪起始可见节点，递归过程中跳过所有中间不可见节点的分支记录，直到遇到下一个可见节点才输出结果。

优化后的递归CTE代码：

WITH RecursivePaths AS (
    -- 锚点成员：从所有可见起始节点出发，记录起始可见节点和当前路径终点
    SELECT 
        StartNode AS VisibleStart,
        EndNode AS CurrentNode,
        EndNodeIsVisible,
        1 AS Depth
    FROM Paths
    WHERE StartNodeIsVisible = 1

    UNION ALL

    -- 递归成员：仅在当前路径终点不可见时继续延伸路径
    SELECT 
        rp.VisibleStart,
        p.EndNode AS CurrentNode,
        p.EndNodeIsVisible,
        rp.Depth + 1 AS Depth
    FROM RecursivePaths rp
    JOIN Paths p ON rp.CurrentNode = p.StartNode
    WHERE rp.EndNodeIsVisible = 0
)
-- 只筛选终点为可见节点的结果，即压缩后的路径
SELECT 
    VisibleStart AS StartNode,
    CurrentNode AS EndNode,
    Depth
FROM RecursivePaths
WHERE EndNodeIsVisible = 1
OPTION (MAXRECURSION 0); -- 0表示无递归深度限制，可根据实际场景调整

优化点说明 #

• 锚点成员明确标记VisibleStart，避免递归过程中生成无效分支
• 递归条件改为rp.EndNodeIsVisible = 0，仅在当前路径终点不可见时继续迭代，大幅减少不必要的计算
• 最终直接输出终点为可见节点的记录，无需额外过滤无效数据

二、大数据集下的高效方案 #

对于1500万行的大规模数据，递归CTE的迭代次数过多会导致性能瓶颈，推荐以下两种方案：

方案1：循环+临时表（兼容所有SQL Server版本） #

通过循环逐步合并不可见节点的路径，直到没有可合并的记录为止：

-- 创建临时表存储最终压缩路径
DROP TABLE IF EXISTS #CompressedPaths;
CREATE TABLE #CompressedPaths (
    StartNode CHAR(1),
    EndNode CHAR(1),
    Depth INT,
    PRIMARY KEY (StartNode, EndNode) -- 添加主键提升查询性能
);

-- 初始化：插入可见节点直接相连的路径
INSERT INTO #CompressedPaths
SELECT StartNode, EndNode, 1 AS Depth
FROM Paths
WHERE StartNodeIsVisible = 1 AND EndNodeIsVisible = 1;

-- 创建临时表存储待合并的中间路径（起始可见、终点不可见）
DROP TABLE IF EXISTS #TempPaths;
CREATE TABLE #TempPaths (
    StartNode CHAR(1),
    EndNode CHAR(1),
    Depth INT,
    PRIMARY KEY (StartNode, EndNode)
);

INSERT INTO #TempPaths
SELECT StartNode, EndNode, 1 AS Depth
FROM Paths
WHERE StartNodeIsVisible = 1 AND EndNodeIsVisible = 0;

-- 循环合并路径，直到没有新的合并记录
WHILE @@ROWCOUNT > 0
BEGIN
    -- 合并中间路径与原路径，生成终点为可见节点的压缩路径
    INSERT INTO #CompressedPaths
    SELECT tp.StartNode, p.EndNode, tp.Depth + 1
    FROM #TempPaths tp
    JOIN Paths p ON tp.EndNode = p.StartNode
    WHERE p.EndNodeIsVisible = 1
    EXCEPT
    SELECT StartNode, EndNode, Depth FROM #CompressedPaths;

    -- 更新临时表：保留合并后终点仍不可见的路径，继续迭代
    DELETE FROM #TempPaths;
    INSERT INTO #TempPaths
    SELECT tp.StartNode, p.EndNode, tp.Depth + 1
    FROM #TempPaths tp
    JOIN Paths p ON tp.EndNode = p.StartNode
    WHERE p.EndNodeIsVisible = 0
    EXCEPT
    SELECT StartNode, EndNode, Depth FROM #TempPaths;
END

-- 查询最终结果
SELECT * FROM #CompressedPaths;

-- 清理临时表
DROP TABLE IF EXISTS #CompressedPaths;
DROP TABLE IF EXISTS #TempPaths;

方案2：SQL Server图形功能（2017+版本） #

SQL Server 2017及以上支持图形表，可高效处理路径遍历：

-- 创建节点表和边表
DROP TABLE IF EXISTS Nodes;
DROP TABLE IF EXISTS Edges;

CREATE TABLE Nodes (
    NodeId CHAR(1) PRIMARY KEY,
    IsVisible BIT
);

CREATE TABLE Edges (
    EdgeId INT IDENTITY PRIMARY KEY,
    StartNodeId CHAR(1) REFERENCES Nodes(NodeId),
    EndNodeId CHAR(1) REFERENCES Nodes(NodeId),
    $from_id INT, -- 图形表必需列
    $to_id INT    -- 图形表必需列
) AS EDGE;

-- 插入节点数据
INSERT INTO Nodes (NodeId, IsVisible)
SELECT DISTINCT StartNode, StartNodeIsVisible FROM Paths
UNION
SELECT DISTINCT EndNode, EndNodeIsVisible FROM Paths;

-- 插入边数据
INSERT INTO Edges (StartNodeId, EndNodeId, $from_id, $to_id)
SELECT 
    p.StartNode,
    p.EndNode,
    n1.$node_id,
    n2.$node_id
FROM Paths p
JOIN Nodes n1 ON p.StartNode = n1.NodeId
JOIN Nodes n2 ON p.EndNode = n2.NodeId;

-- 使用SHORTEST_PATH遍历可见节点间的路径，跳过中间不可见节点
SELECT
    n1.NodeId AS StartNode,
    n2.NodeId AS EndNode,
    LEN(STRING_AGG(n.NodeId, '') WITHIN GROUP (GRAPH PATH)) + 1 AS Depth
FROM Nodes n1,
     Nodes n2,
     Edges FOR PATH e,
     Nodes FOR PATH n
WHERE MATCH(SHORTEST_PATH(n1(-(e)->n)+->n2))
  AND n1.IsVisible = 1
  AND n2.IsVisible = 1
  AND ALL(n.IsVisible = 0 FOR PATH) -- 确保中间节点都不可见
GROUP BY n1.NodeId, n2.NodeId;

通用性能优化建议 #

• 为Paths表的StartNode、EndNode列添加非聚集索引：

  CREATE NONCLUSTERED INDEX IX_Paths_StartNode ON Paths(StartNode);
  CREATE NONCLUSTERED INDEX IX_Paths_EndNode ON Paths(EndNode);
  

• 循环方案优先使用临时表而非表变量，临时表支持索引，性能更优
• 图形方案适合复杂多跳路径场景，尤其是需要处理大量分支的情况

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