SQL多分支树最长路径深度计算的性能优化请求

问题描述 #

需要在SQL中确定树结构里每个节点在最长路径上的层级或深度，尽管仅包含159个节点，但由于分支路径变体过多，当前遍历代码耗时无法控制在5分钟以内，恳请提供合理时间内完成遍历的优化建议。

原遍历代码 #

DECLARE @treeToTraverse TABLE (
     nodeId INT
     ,NextNodeId INT
     ,UNIQUE (
         nodeId
         ,NextNodeId
         ) -- enforce unique consitraint
     )

/*
apply distinct here otherwise the joins explode the dataset making it
untraversable, behaving similarly to circular references (infinite, or near
enough in this case)
*/

INSERT INTO @treeToTraverse (
    nodeId
    ,NextNodeId
    )
SELECT DISTINCT a.nodeId
    ,a.NextNodeId
FROM a AS a
INNER JOIN q AS q ON q.Id = a.nodeId

WITH treeCte (
    nodeId
    ,NextNodeId
    ,depth
    ,pathTaken
    )
AS (
    SELECT a.nodeId
        ,a.NextNodeId
        ,1
        ,'|' + convert(VARCHAR(max), a.nodeId) + '|'
    FROM @treeToTraverse AS a
    WHERE a.nodeId = 1
    
    UNION ALL
    
    SELECT a.nodeId
        ,a.NextNodeId
        ,qtc.depth + 1
        ,qtc.pathTaken + convert(VARCHAR(10), a.nodeId) + '|'
    FROM @treeToTraverse AS a
    INNER JOIN treeCte AS qtc ON qtc.NextNodeId = a.nodeId
    WHERE qtc.pathTaken NOT LIKE '%|' + convert(VARCHAR(10), a.nodeId) + '|%'
    )
SELECT *
INTO #r
FROM treeCte AS qtc
ORDER BY nodeId
OPTION (MAXRECURSION 1000)

select nodeId, max(depth) from #r 
group by nodeId

优化建议 #

1. 移除字符串路径跟踪，消除性能瓶颈 #

原代码中pathTaken字符串拼接和LIKE模糊匹配是核心性能问题——每次递归都要操作长字符串，且模糊匹配的时间复杂度随路径长度线性增长。

• 如果树结构无循环引用：直接删除pathTaken字段和对应的WHERE条件，递归只会沿有向边前进，不会重复访问节点，可大幅减少计算量。
• 如果存在循环：提前清理环结构（业务允许的话），或改用二进制数组存储已访问节点（替代字符串），用EXISTS检测替代模糊匹配，提升查询速度。

2. 反向遍历（从叶子到根）减少冗余路径 #

原代码从根节点出发遍历所有路径，会生成大量冗余记录。改为从叶子节点反向遍历到根节点，仅计算每个节点到根的最长路径：

-- 构建反向树结构（子节点指向父节点）
DECLARE @reverseTree TABLE (
    nodeId INT,
    parentNodeId INT,
    UNIQUE(nodeId, parentNodeId)
);

INSERT INTO @reverseTree (nodeId, parentNodeId)
SELECT DISTINCT a.NextNodeId, a.nodeId
FROM a AS a
INNER JOIN q AS q ON q.Id = a.nodeId;

-- 递归计算最长路径深度
WITH reverseCte AS (
    -- 初始化叶子节点（无后续节点的节点）
    SELECT rt.nodeId, rt.parentNodeId, 1 AS depth
    FROM @reverseTree rt
    LEFT JOIN a ON a.nodeId = rt.nodeId
    WHERE a.nodeId IS NULL
    -- 单独加入根节点（若根节点无父节点）
    UNION ALL
    SELECT 1, NULL, 1 WHERE NOT EXISTS (SELECT 1 FROM @reverseTree WHERE nodeId = 1)

    UNION ALL

    SELECT rt.nodeId, rt.parentNodeId, rc.depth + 1
    FROM @reverseTree rt
    INNER JOIN reverseCte rc ON rc.parentNodeId = rt.nodeId
)

-- 取每个节点的最大深度
SELECT nodeId, MAX(depth) AS max_depth
FROM reverseCte
GROUP BY nodeId
ORDER BY nodeId;

3. 提前优化基础数据 #

• 给原表创建索引，加速DISTINCT查询：

  CREATE NONCLUSTERED INDEX IX_a_nodeId_NextNodeId ON a(nodeId, NextNodeId);
  CREATE NONCLUSTERED INDEX IX_q_Id ON q(Id);
  

• 提前清理a表中的重复(nodeId, NextNodeId)记录，避免后续递归的数据膨胀。

4. 改用迭代遍历替代递归CTE #

递归CTE在路径数量极多时会有内存和性能限制，用WHILE循环+临时表手动控制遍历逻辑，减少冗余计算：

DECLARE @temp TABLE (
    nodeId INT,
    depth INT,
    PRIMARY KEY(nodeId, depth) -- 避免重复记录
);

-- 初始化根节点
INSERT INTO @temp (nodeId, depth)
SELECT 1, 1;

-- 循环遍历，直到没有新节点可扩展
WHILE EXISTS (
    SELECT 1 FROM @temp t
    INNER JOIN @treeToTraverse tt ON t.nodeId = tt.nodeId
    LEFT JOIN @temp t2 ON tt.NextNodeId = t2.nodeId AND t.depth + 1 = t2.depth
    WHERE t2.nodeId IS NULL
)
BEGIN
    INSERT INTO @temp (nodeId, depth)
    SELECT tt.NextNodeId, t.depth + 1
    FROM @temp t
    INNER JOIN @treeToTraverse tt ON t.nodeId = tt.nodeId
    LEFT JOIN @temp t2 ON tt.NextNodeId = t2.nodeId AND t.depth + 1 = t2.depth
    WHERE t2.nodeId IS NULL;
END

-- 输出每个节点的最大深度
SELECT nodeId, MAX(depth) AS max_depth
FROM @temp
GROUP BY nodeId;

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