SQL Server：如何将 CTE 递归限制为刚刚递归添加的行？

Question

更简单的示例

让我们尝试一个更简单的示例，这样人们就可以理解这些概念，并有一个可以复制并粘贴到 SQL 查询分析器中的实际示例：

想象一个具有层次结构的 Nodes 表：

A
 - B
    - C

我们可以开始在查询分析器中进行测试：

CREATE TABLE ##Nodes
(
 NodeID varchar(50) PRIMARY KEY NOT NULL,
 ParentNodeID varchar(50) NULL
)

INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('A', null)
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('B', 'A')
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('C', 'B')

所需输出：

ParentNodeID    NodeID    GenerationsRemoved
============    ======    ==================
NULL            A         1
NULL            B         2
NULL            C         3
A               B         1
A               C         2
B               C         1

现在是建议的 CTE 表达式，其输出不正确：

WITH NodeChildren AS
(
   --initialization
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
   FROM ##Nodes
   WHERE ParentNodeID IS NULL

   UNION ALL

   --recursive execution
   SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1
   FROM NodeChildren AS P
      INNER JOIN ##Nodes AS N
      ON P.NodeID = N.ParentNodeID
)
SELECT ParentNodeID, NodeID, GenerationsRemoved
FROM NodeChildren

实际输出：

ParentNodeID    NodeID    GenerationsRemoved
============    ======    ==================
NULL            A         1
NULL            B         2
NULL            C         3

注意： 如果 SQL Server 2005† CTE 无法完成我在 2000 年之前所做的事情‡，没关系，这就是答案。 谁给出“不可能”作为答案，谁就将赢得赏金。 但我会等几天，以确保每个人都同意，在我因无法解决我的问题而无可挽回地给予 250 声望之前，这是不可能的。

Nitpickers Corner

†不是 2008 年

‡不诉诸 UDF*，这是已有的解决方案

*除非您可以在原始问题中找到提高 UDF 性能的方法

---

原始问题

我有一个表格节点，每个节点都有一个指向另一个节点（或 null）的父节点。

举例来说：

1 My Computer
    2 Drive C
         4 Users
         5 Program Files
         7 Windows
             8 System32
    3 Drive D
         6 mp3

我想要一个返回所有父子关系以及它们之间的代数的表

对于所有直接父母关系：

ParentNodeID  ChildNodeID  GenerationsRemoved
============  ===========  ===================
(null)        1            1
1             2            1
2             4            1
2             5            1
2             7            1
1             3            1
3             6            1
7             8            1

但是还有祖父母关系：

ParentNodeID  ChildNodeID  GenerationsRemoved
============  ===========  ===================
(null)        2            2
(null)        3            2
1             4            2
1             5            2
1             7            2
1             6            2
2             8            2

还有曾祖祖父母关系：

ParentNodeID  ChildNodeID  GenerationsRemoved
============  ===========  ===================
(null)        4            3
(null)        5            3
(null)        7            3
(null)        6            3
1             8            3

所以我可以弄清楚基本的CTE初始化：

WITH (NodeChildren) AS
{
   --initialization
   SELECT ParentNodeID, NodeID AS ChildNodeID, 1 AS GenerationsRemoved
   FROM Nodes
} 

现在的问题是递归部分。 当然，显而易见的答案是行不通的：

WITH (NodeChildren) AS
{
   --initialization
   SELECT ParentNodeID, ChildNodeID, 1 AS GenerationsRemoved
   FROM Nodes

   UNION ALL

   --recursive execution
   SELECT parents.ParentNodeID, children.NodeID, parents.Generations+1
   FROM NodeChildren parents
    INNER JOIN NodeParents children
    ON parents.NodeID = children.ParentNodeID
} 

Msg 253, Level 16, State 1, Line 1
Recursive member of a common table expression 'NodeChildren' has multiple recursive references.

生成整个递归列表所需的所有信息都存在于初始 CTE 表中。 但如果不允许，我会尝试：

WITH (NodeChildren) AS
{
   --initialization
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
   FROM Nodes

   UNION ALL

   --recursive execution
   SELECT parents.ParentNodeID, Nodes.NodeID, parents.Generations+1
   FROM NodeChildren parents
    INNER JOIN Nodes
    ON parents.NodeID = nodes.ParentNodeID
} 

但这会失败，因为它不仅加入递归元素，而且不断递归地一遍又一遍地添加相同的行：

Msg 530, Level 16, State 1, Line 1
The statement terminated. The maximum recursion 100 has been exhausted before statement completion.

在 SQL Server 2000 中，我通过使用用户定义函数（UDF）模拟了 CTE ):

CREATE FUNCTION [dbo].[fn_NodeChildren] ()
RETURNS @Result TABLE (
    ParentNodeID int NULL,
    ChildNodeID int NULL,
    Generations int NOT NULL) 
AS  
/*This UDF returns all "ParentNode" - "Child Node" combinations
    ...even multiple levels separated
BEGIN 
    DECLARE @Generations int
    SET @Generations = 1

    --Insert into the Return table all "Self" entries
    INSERT INTO @Result
    SELECT ParentNodeID, NodeID, @Generations
    FROM Nodes
    WHILE @@rowcount > 0 
    BEGIN
        SET @Generations = @Generations + 1
        --Add to the Children table: 
        --  children of all nodes just added 
        -- (i.e. Where @Result.Generation = CurrentGeneration-1)
        INSERT @Result
        SELECT CurrentParents.ParentNodeID, Nodes.NodeID, @Generations
        FROM Nodes
            INNER JOIN @Result CurrentParents
            ON Nodes.ParentNodeID = CurrentParents.ChildNodeID
        WHERE CurrentParents.Generations = @Generations - 1
    END
    RETURN
END

防止它爆炸的神奇之处在于限制 where 子句： WHERE CurrentParents.Generations - @Generations-1

如何防止递归 CTE 永远递归？

Answer 1

试试这个：

WITH Nodes AS
(
   --initialization
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
   FROM ##Nodes

   UNION ALL

   ----recursive execution
   SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1
   FROM Nodes AS P
      INNER JOIN ##Nodes AS N
      ON P.NodeID = N.ParentNodeID
   WHERE P.GenerationsRemoved <= 10

)
SELECT ParentNodeID, NodeID, GenerationsRemoved
FROM Nodes
ORDER BY ParentNodeID, NodeID, GenerationsRemoved

基本上从初始化查询中删除“只显示绝对父母”； 这样，它会生成从每个结果开始并从那里递减的结果。 我还在“WHERE P.GenerationsRemoved <= 10”中添加了无限递归捕获（将 10 替换为 100 以内的任何数字以满足您的需要）。 然后添加排序，使其看起来像您想要的结果。

Answer 2

旁白：你有 SQL Server 2008 吗？ 这可能适合 hierarchyid 数据类型。

Answer 3

如果我理解您的意图，您可以通过执行以下操作来获得结果：

DECLARE @StartID INT;
SET @StartID = 1;
WITH CTE (ChildNodeID, ParentNodeID, [Level]) AS
(
  SELECT  t1.ChildNodeID, 
          t1.ParentNodeID, 
          0
  FROM tblNodes AS t1
  WHERE ChildNodeID = @StartID
  UNION ALL
  SELECT  t1.ChildNodeID, 
          t1.ParentNodeID, 
          t2.[Level]+1
  FROM tblNodes AS t1
    INNER JOIN CTE AS t2 ON t1.ParentNodeID = t2.ChildNodeID    
)
SELECT t1.ChildNodeID, t2.ChildNodeID, t1.[Level]- t2.[Level] AS GenerationsDiff
FROM CTE AS t1
  CROSS APPLY CTE t2

这将返回所有节点之间的代差，您可以根据您的确切需要对其进行修改。

Answer 4

好吧，你的答案不是那么明显:-)

WITH (NodeChildren) AS
{
   --initialization
   SELECT ParentNodeID, ChildNodeID, 1 AS GenerationsRemoved
   FROM Nodes

这部分被称为递归 CTE 的“锚”部分 - 但它实际上应该只从表中选择一行或选定的几行 - 这会选择所有内容！

我想你在这里缺少的只是一个合适的 WHERE 子句：

WITH (NodeChildren) AS
{
   --initialization
   SELECT ParentNodeID, ChildNodeID, 1 AS GenerationsRemoved
   FROM Nodes
   **WHERE ParentNodeID IS NULL**

但是，恐怕你的要求不仅要有“直接”层次结构，而且要有祖父母-孩子行，可能不太容易满足......通常，递归 CTE 只会显示一级及其直接下级（当然，还有层次结构中的下一级）——它通常不会跳过一级、二级甚至更多级。

希望这个对你有帮助。

马克

Answer 5

问题在于 Sql Server 默认递归限制 (100)。 如果您在顶部尝试删除锚点限制（还添加了排序依据）的示例：

WITH NodeChildren AS
(
   --initialization
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
   FROM Nodes

   UNION ALL

   --recursive execution
   SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1
   FROM NodeChildren AS P
      inner JOIN Nodes AS N
      ON P.NodeID = N.ParentNodeID
)
SELECT ParentNodeID, NodeID, GenerationsRemoved
FROM NodeChildren
ORDER BY ParentNodeID ASC

这会产生所需的结果。 您面临的问题是，如果行数较多，您将重复 100 次以上，这是默认限制。 这可以通过在查询后添加选项（最大递归 x） 来更改，其中 x 是 1 到 32767 之间的数字。x 也可以设置为 0，这不会设置任何限制，但很快就会有一个对您的服务器性能产生非常不利的影响。 显然，随着节点中行数的增加，递归次数会很快增加，除非表中的行数有已知的上限，否则我会避免这种方法。 为了完整起见，最终查询应如下所示：

 WITH NodeChildren AS
    (
       --initialization
       SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
       FROM Nodes

       UNION ALL

       --recursive execution
       SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1
       FROM NodeChildren AS P
          inner JOIN Nodes AS N
          ON P.NodeID = N.ParentNodeID
    )
    SELECT * 
    FROM NodeChildren
    ORDER BY ParentNodeID
    OPTION (MAXRECURSION 32767)

其中 32767 可以向下调整以适合您的场景

Answer 6

您是否尝试过在 CTE 中构建一条路径并使用它来识别祖先？

然后，您可以从祖先节点深度中减去后代节点深度来计算 GenerationsRemoved 列，如下所示...

DECLARE @Nodes TABLE
(
    NodeId varchar(50) PRIMARY KEY NOT NULL,
    ParentNodeId varchar(50) NULL
)

INSERT INTO @Nodes (NodeId, ParentNodeId) VALUES ('A', NULL)
INSERT INTO @Nodes (NodeId, ParentNodeId) VALUES ('B', 'A')
INSERT INTO @Nodes (NodeId, ParentNodeId) VALUES ('C', 'B')

DECLARE @Hierarchy TABLE
(
    NodeId varchar(50) PRIMARY KEY NOT NULL,
    ParentNodeId varchar(50) NULL,
    Depth int NOT NULL,
    [Path] varchar(2000) NOT NULL
)

WITH Hierarchy AS
(
    --initialization
    SELECT NodeId, ParentNodeId, 0 AS Depth, CONVERT(varchar(2000), NodeId) AS [Path]
    FROM @Nodes
    WHERE ParentNodeId IS NULL

    UNION ALL

    --recursive execution
    SELECT n.NodeId, n.ParentNodeId, p.Depth + 1, CONVERT(varchar(2000), p.[Path] + '/' + n.NodeId)
    FROM Hierarchy AS p
    INNER JOIN @Nodes AS n
    ON p.NodeId = n.ParentNodeId
)
INSERT INTO @Hierarchy
SELECT *
FROM Hierarchy

SELECT parent.NodeId AS AncestorNodeId, child.NodeId AS DescendantNodeId, child.Depth - parent.Depth AS GenerationsRemoved
FROM @Hierarchy AS parent
INNER JOIN @Hierarchy AS child
ON child.[Path] LIKE parent.[Path] + '/%'

Answer 7

这打破了克里斯·谢弗的答案所施加的递归限制。

我创建一个带有循环的表：

CREATE TABLE ##Nodes
(
   NodeID varchar(50) PRIMARY KEY NOT NULL,
   ParentNodeID varchar(50) NULL
)

INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('A', 'C');
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('B', 'A');
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('C', 'B');

在存在潜在循环的情况下（即 ParentNodeId IS NOT NULL），删除的生成从 2 开始。然后我们可以通过检查 (P.ParentNodeID == N.NodeID) 来标识循环，我们根本不添加它。 然后，我们添加省略的代remove = 1。

WITH ParentNodes AS
(
   --initialization
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
   FROM ##Nodes
   WHERE ParentNodeID IS NULL

   UNION ALL

   SELECT P.ParentNodeID, N.NodeID, 2 AS GenerationsRemoved
   FROM ##Nodes N
   JOIN ##Nodes P ON N.ParentNodeID=P.NodeID
   WHERE P.ParentNodeID IS NOT NULL

   UNION ALL

   ----recursive execution
   SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1
   FROM ParentNodes AS P
     INNER JOIN ##Nodes AS N
     ON P.NodeID = N.ParentNodeID
   WHERE P.ParentNodeID IS NULL OR P.ParentNodeID <> N.NodeID

),
Nodes AS (
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved 
   FROM ##Nodes 
   WHERE ParentNodeID IS NOT NULL

   UNION ALL

   SELECT ParentNodeID, NodeID, GenerationsRemoved FROM ParentNodes
)
SELECT ParentNodeID, NodeID, GenerationsRemoved
FROM Nodes
ORDER BY ParentNodeID, NodeID, GenerationsRemoved

Answer 8

with cte as
(
    select a=65, L=1
    union all
    select a+1, L=L+1
    from cte
    where L<=100
)
select 
IsRecursion=Case When L>1 then 'Recursion' else 'Not Recursion' end,
AsciiValue=a,
AsciiCharacter=char(a)
from cte

1. 创建一个包含当前级别的列。
2. 检查级别是否 >1

我的示例显示了一个递归 CTE，它在 100 个级别（最大值）后停止递归。 作为奖励，它会显示一堆 ASCII 字符和相应的数值。