Infinite Loop in Cte When Parsing Self-Referencing Table

Infinite loop in CTE when parsing self-referencing table

The reason of an infinite loop is the first record where empid=mgrid. To handle this issue you should include a cumulative field (levels in this example) to store mgrid you have already processed and check if emid is already in this list to avoid a loop.

Here is a query:

with Tree as
        (
        SELECT  empid
        ,       mgrid
        ,       1 as lv
        ,       1 as level1
        ,       null as level2
        ,       null as level3
        ,       null as level4
        ,       null as level5
        ,       cast(mgrid as varchar(max)) levels  
        FROM    Employees
        WHERE   empid = 1 and mgrid = 1
        UNION ALL
        SELECT  E.empid
        ,       E.mgrid
        ,       T.lv + 1
        ,       T.level1
        ,       case when T.lv = 1 then E.empid else t.level2 end
        ,       case when T.lv = 2 then E.empid else t.level3 end
        ,       case when T.lv = 3 then E.empid else t.level4 end
        ,       case when T.lv = 4 then E.empid else t.level5 end
        ,       T.levels+','+cast(E.mgrid as varchar(max)) levels   

          FROM    Employees AS E
        JOIN    Tree T
        ON      E.mgrid = T.empid 
                and (','+T.levels+',' 
                      not like 
                     '%,'+cast(E.empid as varchar(max))+',%')
        )
select  *
from Tree
order by empid

And here is SQLFiddle demo

Infinite loop CTE with OPTION (maxrecursion 0)

If you are hitting the recursion limit, you either have considerable depth in sponsoring relationships or a loop in the data. A query like the following will detect loops and terminate the recursion:

declare @tblMember as Table ( MemberId Int, SponsorMemberId Int );
insert into @tblMember ( MemberId, SponsorMemberId ) values
  ( 1, 2 ), ( 2, 3 ), ( 3, 5 ), ( 4, 5 ), ( 5, 1 ), ( 3, 3 );
declare @MemberId as Int = 3;
declare @False as Bit = 0, @True as Bit = 1;

with Children as (
  select MemberId, SponsorMemberId,
    Convert( VarChar(4096), '>' + Convert( VarChar(10), MemberId ) + '>' ) as Path, @False as Loop
    from @tblMember
    where MemberId = @MemberId
  union all
  select Child.MemberId, Child.SponsorMemberId,
    Convert( VarChar(4096), Path + Convert( VarChar(10), Child.MemberId ) + '>' ),
    case when CharIndex( '>' + Convert( VarChar(10), Child.MemberId ) + '>', Path ) = 0 then @False else @True end
    from @tblMember as Child inner join
      Children as Parent on Parent.MemberId = Child.SponsorMemberId
    where Parent.Loop = 0 )
  select *
    from Children
    option ( MaxRecursion 0 );

To find infinite recursive loop in CTE

You haven't specified the dialect or your column names, so it is difficult to make the perfect example...

-- Some random data
IF OBJECT_ID('tempdb..#MyTable') IS NOT NULL
    DROP TABLE #MyTable

CREATE TABLE #MyTable (ID INT PRIMARY KEY, ParentID INT NULL, Description VARCHAR(100))
INSERT INTO #MyTable (ID, ParentID, Description) VALUES
(1, NULL, 'Parent'), -- Try changing the second value (NULL) to 1 or 2 or 3
(2, 1, 'Child'), -- Try changing the second value (1) to 2 
(3, 2, 'SubChild')
-- End random data

;WITH RecursiveCTE (StartingID, Level, Parents, Loop, ID, ParentID, Description) AS
(
    SELECT ID, 1, '|' + CAST(ID AS VARCHAR(MAX)) + '|', 0, * FROM #MyTable
    UNION ALL
    SELECT R.StartingID, R.Level + 1, 
        R.Parents + CAST(MT.ID AS VARCHAR(MAX)) + '|',
        CASE WHEN R.Parents LIKE '%|' + CAST(MT.ID AS VARCHAR(MAX)) + '|%' THEN 1 ELSE 0 END,
        MT.*
        FROM #MyTable MT
        INNER JOIN RecursiveCTE R ON R.ParentID = MT.ID AND R.Loop = 0
)

SELECT StartingID, Level, Parents, MAX(Loop) OVER (PARTITION BY StartingID) Loop, ID, ParentID, Description 
    FROM RecursiveCTE 
    ORDER BY StartingID, Level

Something like this will show if/where there are loops in the recursive cte. Look at the column Loop. With the data as is, there is no loops. In the comments there are examples on how to change the values to cause a loop.

In the end the recursive cte creates a VARCHAR(MAX) of ids in the form |id1|id2|id3| (called Parents) and then checks if the current ID is already in that "list". If yes, it sets the Loop column to 1. This column is checked in the recursive join (the ABD R.Loop = 0).

The ending query uses a MAX() OVER (PARTITION BY ...) to set to 1 the Loop column for a whole "block" of chains.

A little more complex, that generates a "better" report:

-- Some random data
IF OBJECT_ID('tempdb..#MyTable') IS NOT NULL
    DROP TABLE #MyTable

CREATE TABLE #MyTable (ID INT PRIMARY KEY, ParentID INT NULL, Description VARCHAR(100))
INSERT INTO #MyTable (ID, ParentID, Description) VALUES
(1, NULL, 'Parent'), -- Try changing the second value (NULL) to 1 or 2 or 3
(2, 1, 'Child'), -- Try changing the second value (1) to 2 
(3, 3, 'SubChild')
-- End random data

-- The "terminal" childrens (that are elements that don't have childrens
-- connected to them)
;WITH WithoutChildren AS
(
    SELECT MT1.* FROM #MyTable MT1
        WHERE NOT EXISTS (SELECT 1 FROM #MyTable MT2 WHERE MT1.ID != MT2.ID AND MT1.ID = MT2.ParentID)
)

, RecursiveCTE (StartingID, Level, Parents, Descriptions, Loop, ParentID) AS
(
    SELECT ID, -- StartingID 
        1, -- Level
        '|' + CAST(ID AS VARCHAR(MAX)) + '|', 
        '|' + CAST(Description AS VARCHAR(MAX)) + '|', 
        0, -- Loop
        ParentID
        FROM WithoutChildren
    UNION ALL
    SELECT R.StartingID, -- StartingID
        R.Level + 1, -- Level
        R.Parents + CAST(MT.ID AS VARCHAR(MAX)) + '|',
        R.Descriptions + CAST(MT.Description AS VARCHAR(MAX)) + '|', 
        CASE WHEN R.Parents LIKE '%|' + CAST(MT.ID AS VARCHAR(MAX)) + '|%' THEN 1 ELSE 0 END,
        MT.ParentID
        FROM #MyTable MT
        INNER JOIN RecursiveCTE R ON R.ParentID = MT.ID AND R.Loop = 0
)

SELECT * FROM RecursiveCTE 
    WHERE ParentID IS NULL OR Loop = 1

This query should return all the "last child" rows, with the full parent chain. The column Loop is 0 if there is no loop, 1 if there is a loop.

CTE for recursive querying

Looks like this will do it:

DECLARE @ProjectAccessories TABLE
(
    Id INT, ProjectComponentId INT, AccessorySetId INT 
)
DECLARE @ProjectAccessorySets TABLE
(
    Id INT, AccessoryId INT
)

INSERT @ProjectAccessories (Id, ProjectComponentId, AccessorySetId)
VALUES (4, 34, NULL)
,       (5, 145, NULL)
,       (6, 207, NULL)
,       (8, NULL, 3)

INSERT @ProjectAccessorySets (Id, AccessoryId)
VALUES (1, NULL)
,       (2, NULL)
,       (3, 6) 

;
WITH AccessoryIds AS
(
        SELECT      parent.Id
        ,           parent.AccessorySetId AS AccessoryId
        FROM        @ProjectAccessories AS parent
        INNER JOIN  @ProjectAccessorySets AS accessorySets
                ON  accessorySets.AccessoryId = parent.Id
        WHERE       parent.ProjectComponentId = 207

        UNION ALL

        SELECT      child.id
        ,           childAccessorySets.AccessoryId
        FROM        AccessoryIds AS asi 
        INNER JOIN  @ProjectAccessorySets AS childAccessorySets
                ON  childAccessorySets.AccessoryId = asi.Id
        INNER JOIN  @ProjectAccessories AS child
                ON  child.AccessorySetId = childAccessorySets.id
)

SELECT  * 
FROM    AccessoryIds

Results in:

+----+-------------+
| Id | AccessoryId |
+----+-------------+
|  6 | NULL        |
|  8 | 6           |
+----+-------------+

How to write a recursive query for a self referencing table and junction table (duh)

Assume you have a table sources with a column id.
The query to get the destinations for these particular sources would be as follows:

SELECT id_destination
FROM relation_entite
JOIN sources ON relation_entite.id_source = sources.id;

Then just plug this into a CTE, to get the basic recursive CTE for searching a subtree:

WITH RECURSIVE ids(id) AS (
  VALUES('m.06w4why')                -- start with this record
  UNION ALL
  SELECT id_destination              -- get destinations for any previous sources
  FROM relation_entite
  JOIN ids ON relation_entite.id_source = ids.id
)
SELECT id FROM ids;

(If it is possible that there are loops in the data, you must use UNION instead of UNION ALL.)

Recursive Query CTE Father - Son - Grandson error

The recursion didn't stop because your top row refers to itself endlessly.

If the top row has a null parent, that would have stopped the recursion.

Another approach is to use that case id = parentid as the termination logic.

The fiddle

WITH  LB (ID, IDFATHER, idstart) AS (
    SELECT ID,  IDFATHER, id
      FROM PROJECTS WHERE ID = 5
     UNION ALL 
    SELECT  I.ID,  I.IDFATHER, lbi.idstart
      FROM PROJECTS I 
      JOIN LB LBI
        ON  I.ID = lbi.IDFATHER 
       AND lbi.id <> lbi.idfather
      )

SELECT id AS idtop, idstart
  FROM LB
 WHERE LB.ID = LB.IDFATHER
;

The result:

Sample Image

With CTE why i am not able to print 1 to 1000 number or more but 1 to 100 i am able to print

The error is telling you the problemhere, by default a CTE has a maximum recursion of 100. This is intentional, as it's stops a poorly coded CTE taking out your server and grinding it to a halt.

You can increase that value by using OPTION MAXRECURSION. Thus, in simple terms:

WITH CTE AS (
    SELECT 1 AS I
    UNION ALL
    SELECT I + 1 AS I
    FROM CTE
    WHERE I + 1 <= 1000)
SELECT *
FROM CTE
OPTION (MAXRECURSION 1000);

This is all covered in the CTE documentation: Using MAXRECURSION to cancel a statement

Recursive CTE...dealing with nested parent/children records

I believe something like the following should work:

WITH RECURSIVE recCTE AS
(
    SELECT
        parent_payee_id as parent,
        payee_id as child,
        payee_pct
        1 as depth,
        parent_payee_id + '>' + payee_id as path
    FROM
        table
    WHERE
        --top most node
        parent_payee_id = 12043 
        AND payee_id <> parent_payee_id --prevent endless recursion

    UNION ALL

    SELECT
        table.parent_payee_id as parent,
        table.payee_id as child,
        table.payee_pct,
        recCTE.depth + 1 as Depth,
        recCTE.path + '>' + table.payee_id as path
    FROM
        recCTE
        INNER JOIN table ON
            recCTE.child = table.parent_payee_id AND
            recCTE.child <> table.payee_id --again prevent records where parent is child
    Where depth < 15 --prevent endless cycles
)

SELECT DISTINCT parent
FROM recCTE
GROUP BY parent
HAVING sum(payee_pct) <> 1;

This differs from yours mostly in the WHERE statements on both the Recursive Seed (query before UNION) and the recursive term (query after UNION). I believe yours is too restrictive, especially in the recursive term since you want to allow records that are children of 12067 through, but then you only allow 12067 as the parent id to pull in.

Here, though, we pull every descendant of 12043 (from your example table) and it's payee_pct. Then we analyze each parent in the final SELECT and the sum of all it's payee_pcts, which are essentially that parent's first childrens sum(payee_pct). If any of them are not a total of 1, then we display the parent in the output.

At any rate, between your query and mine, I would imagine this is pretty close to the requirements, so it should be tweaks to get you exactly where you need to be if this doesn't do the trick.

The maximum recursion 100 has been exhausted

This behavior is described in the documentation:

To prevent an infinite loop, you can limit the number of recursion levels allowed for a particular statement by using the MAXRECURSION hint and a value between 0 and 32,767 in the OPTION clause of the INSERT, UPDATE, DELETE, or SELECT statement. This lets you control the execution of the statement until you resolve the code problem that is creating the loop. The server-wide default is 100. When 0 is specified, no limit is applied.

You have hit the default limit of 100 iterations (which gives you a little more than 3 months of data).

The way your query is built, there is no risk of infinite loop. So, you can just allow an unlimited number of iterations by adding option (maxrecursion 0) at the end of your query.

Query to fetch all referenced entities recursively

So here is what I've learned and done so far. Thanks to the comment of habo which refers to the following question; Infinite loop in CTE when parsing self-referencing table

Firstly I decided to at least 'solve' my problem and wrote some manual recursion, this solves my problem but is not as 'pretty' as the CTE solution which I was hoping/thinking would be easier to read as well as out perform the manual recursion solution.

Manual Recursion

/****************************/
/* CLAIMS AND PAYMENT LOGIC */
/****************************/
DECLARE @rows as INT = 0
DECLARE @relevantClaimIds as Table(
Debtor_ID INT,
Claim_ID int
)
SET NOCOUNT ON

--Get anchor condition
INSERT INTO @relevantClaimIds (Debtor_ID, Claim_ID)
select Debtor_ID, ID
from Claim c
WHERE OpenAmount <> 0

--Do recursion
WHILE @rows <> (SELECT COUNT(*) FROM @relevantClaimIds)
BEGIN
set @rows = (SELECT COUNT(*) FROM @relevantClaimIds)

--Subtracted
INSERT @relevantClaimIds (Debtor_ID, Claim_ID)
SELECT DISTINCT c.Debtor_ID, c.id
FROM claim c
inner join claimcoupling cc on cc.SubstractedFromClaim_ID = c.ID
JOIN @relevantClaimIds rci on rci.Claim_ID = cc.AddedToClaim_ID
--might be multiple paths to this recursion so eliminate duplicates
left join @relevantClaimIds dup on dup.Claim_ID = c.id
WHERE dup.Claim_ID is null

--Added
INSERT @relevantClaimIds (Debtor_ID, Claim_ID)
SELECT DISTINCT c.Debtor_ID, c.id
FROM claim c
inner join claimcoupling cc on cc.AddedToClaim_ID = c.ID
JOIN @relevantClaimIds rci on rci.Claim_ID = cc.SubstractedFromClaim_ID
--might be multiple paths to this recursion so eliminate duplicates
left join @relevantClaimIds dup on dup.Claim_ID = c.id
WHERE dup.Claim_ID is null

--Payments
INSERT @relevantClaimIds (Debtor_ID, Claim_ID)
SELECT DISTINCT c.Debtor_ID, c.id
FROM @relevantClaimIds f
join ClaimEntryReference cer on f.Claim_ID = cer.Claim_ID
JOIN ClaimEntryReference cer_linked on cer.ClaimEntry_ID = cer_linked.ClaimEntry_ID AND cer.ID <> cer_linked.ID
JOIN Claim c on c.ID = cer_linked.Claim_ID
--might be multiple paths to this recursion so eliminate duplicates
left join @relevantClaimIds dup on dup.Claim_ID = c.id
WHERE dup.Claim_ID is null
END

Then after I received and read the comment I decided to try the CTE solution which looks like this;

CTE Recursion

with Tree as
        (
        select Debtor_ID, ID AS Claim_ID, CAST(ID AS VARCHAR(MAX)) AS levels
        from Claim c
        WHERE OpenAmount <> 0

        UNION ALL
        SELECT c.Debtor_ID, c.id, t.levels + ',' + CAST(c.ID AS VARCHAR(MAX)) AS levels
        FROM claim c
        inner join claimcoupling cc on cc.SubstractedFromClaim_ID = c.ID
        JOIN Tree t on t.Claim_ID = cc.AddedToClaim_ID
        WHERE (','+T.levels+',' not like '%,'+cast(c.ID as varchar(max))+',%')

        UNION ALL
        SELECT c.Debtor_ID, c.id, t.levels + ',' + CAST(c.ID AS VARCHAR(MAX)) AS levels
        FROM claim c
        inner join claimcoupling cc on cc.AddedToClaim_ID = c.ID
        JOIN Tree t on t.Claim_ID = cc.SubstractedFromClaim_ID
        WHERE (','+T.levels+',' not like '%,'+cast(c.ID as varchar(max))+',%')

        UNION ALL
        SELECT c.Debtor_ID, c.id, t.levels + ',' + CAST(c.ID AS VARCHAR(MAX)) AS levels
        FROM Tree t
        join ClaimEntryReference cer on t.Claim_ID = cer.Claim_ID
        JOIN ClaimEntryReference cer_linked on cer.ClaimEntry_ID = cer_linked.ClaimEntry_ID AND cer.ID <> cer_linked.ID
        JOIN Claim c on c.ID = cer_linked.Claim_ID
        WHERE (','+T.levels+',' not like '%,'+cast(c.ID as varchar(max))+',%')
        )
select  DISTINCT Tree.Debtor_ID, Tree.Claim_ID
from Tree

This solution is indeed a lot 'shorter' and easier on the eyes but does it actually perform better?

Performance differences

Manual; CPU 16, Reads 1793, Duration 13

CTE; CPU 47, Reads 4001, Duration 48

Conclusion

Not sure if it's due to the varchar cast that is required in the CTE solution or that it has to do one extra iteration before completing it's recursion but it actually requires more resources on all fronts than the manual recursion.

In the end it is possible with CTE however looks aren't everything (thank god ;-)) performance wise sticking with the manual recursion seems like a better route.

Infinite Loop in Cte When Parsing Self-Referencing Table