TSQL CTE: 如何避免循环遍历？

Question

我编写了一个非常简单的CTE表达式，用于检索用户是成员的所有组的列表。

规则如下：用户可以在多个组中，组可以嵌套，因此一个组可以是另一个组的成员，而且，组也可以相互成为成员，所以组A是组B的成员，组B也是组A的成员。

我的CTE表达式如下，显然会产生无限递归：

            ;WITH GetMembershipInfo(entityId) AS( -- entity can be a user or group
                SELECT k.ID as entityId FROM entities k WHERE k.id = @userId
                UNION ALL
                SELECT k.id FROM entities k 
                JOIN Xrelationships kc on kc.entityId = k.entityId
                JOIN GetMembershipInfo m on m.entityId = kc.ChildID
            )

我找不到一个简单的解决方案来回溯那些我已经记录过的组。

我考虑在CTE中使用一个额外的varchar参数来记录我已访问的所有组的列表，但是使用varchar太粗糙了，不是吗？

有更好的方法吗？

- Haoest

---

你确定它一直在递归吗？服务器默认是100次迭代。尝试阅读有关MSDN上“MAXRECURSION”提示的内容。 - Bridge

先关注效率，然后再考虑粗糙度，如果时间允许的话 :) - AakashM

它不会无限递归，因为在100次递归调用后会抛出错误。请原谅我的措辞。 - Haoest

Answer 1

在递归过程中需要积累一个哨兵字符串。在以下示例中，我从A、B、C、D循环回到A，使用哨兵字符串避免了循环：

DECLARE @MyTable TABLE(Parent CHAR(1), Child CHAR(1));

INSERT @MyTable VALUES('A', 'B');
INSERT @MyTable VALUES('B', 'C');
INSERT @MyTable VALUES('C', 'D');
INSERT @MyTable VALUES('D', 'A');

; WITH CTE (Parent, Child, Sentinel) AS (
    SELECT  Parent, Child, Sentinel = CAST(Parent AS VARCHAR(MAX))
    FROM    @MyTable
    WHERE   Parent = 'A'
    UNION ALL
    SELECT  CTE.Child, t.Child, Sentinel + '|' + CTE.Child
    FROM    CTE
    JOIN    @MyTable t ON t.Parent = CTE.Child
    WHERE   CHARINDEX(CTE.Child,Sentinel)=0
)
SELECT * FROM CTE;

结果：

Parent Child Sentinel
------ ----- --------
A      B     A
B      C     A|B
C      D     A|B|C
D      A     A|B|C|D

- John Dewey

---

我喜欢你的解决方案，因为它有效。但是有没有一种方法可以不使用哨兵字符串来完成这个任务？我觉得在每个哨兵条目周围添加某种分隔符很笨重且重复，比如Sentinel = '<' + CAST(Parent AS VARCHAR(MAX)) + '>'然后我们必须在CharIndex()函数中执行相同的操作，因为如果没有分隔符，就可能会出现误报。如果哨兵字符串变得太大而超过varchar(max)的长度，会发生什么？ - Haoest

很高兴听到这个方法可行。这是有点取巧，而且我实在想不出更“干净”的方法了。但请记住，哨兵在每个递归分支中独立增长，因此只会增长到最大深度乘以每个字符串的长度加上分隔符。VARCHAR(MAX)的限制为2GB，而最大深度可以根据需要扩大到最大32767。因此，你很可能永远不会溢出VARCHAR(MAX)。大多数递归作业可能会有几千棵树，但它们的深度很少超过5。因此，你的哨兵字符串通常会保持相当小。 - John Dewey

我认为您需要以不同的方式构建哨兵字符串，以避免在一般情况下出现误判（当没有使用CHAR(1)时）。CHARINDEX可能会在"AB|C"中找到"A"，但无法在"<AB><C>"中找到"<A>"。此外，如果ID允许包含<或>，您也需要正确编码。当然，如果您继续使用CHAR(1)，这些都不是问题，但那不是一个现实的情况。无论如何，这是一个很好的想法，我给你点赞！ - Branko Dimitrijevic

关于@BrankoDimitrijevic所说的，请参见此解决方案。它确保了哨兵中的标识符始终被分隔，并通过在哨兵中查找delimiter + identifier + delimiter来验证循环引用。 - TT.

Answer 2

不要使用哨兵字符串，而是使用哨兵表变量。无论圈子有多少个跳跃，函数都能捕获循环引用，不会出现nvarchar(max)的最大长度问题，可以轻松修改以适应不同的数据类型甚至是多部分键，并且可以将该函数分配给检查约束。

CREATE FUNCTION [dbo].[AccountsCircular] (
    @AccountID UNIQUEIDENTIFIER
)
RETURNS BIT 
AS
BEGIN
    DECLARE @NextAccountID UNIQUEIDENTIFIER = NULL;
    DECLARE @Sentinel TABLE (
        ID UNIQUEIDENTIFIER
    );

    INSERT INTO @Sentinel ([ID])
    VALUES (@AccountID);

    SET @NextAccountID = @AccountID;

    WHILE @NextAccountID IS NOT NULL BEGIN
        SELECT @NextAccountID = [ParentAccountID]
        FROM [dbo].[Accounts]
        WHERE [AccountID] = @NextAccountID;

        IF EXISTS (SELECT 1 FROM @Sentinel WHERE ID = @NextAccountID) BEGIN
            RETURN 1;
        END;

        INSERT INTO @Sentinel ([ID])
        VALUES (@NextAccountID)
    END;

    RETURN 0;
END;

- Aging Hippie