Avoiding duplicate recursion with Common Table Expressions

Question

Let's say I have a table with 2 columns ID and ParentID. My data looks like this:

ID           ParentID
1            Null
2            1
3            1
4            2
4            2

So to find all relationships based on a given ID my query simplified looks like this:

WITH links ([ID], [ParentID], Depth)
AS
(
    --Get the starting link
    SELECT 
        [ID],
        [ParentID],
        [Depth] = 1
    FROM
        [MyTable] 
    WHERE
        [ID] = @StartID

    UNION ALL

    --Recursively get links that are parented to links already in the CTE
    SELECT 
        mt.[ID],
        mt.[ParentID],
        [Depth] = l.[Depth] + 1
    FROM
        [MyTable] mt
    JOIN
        links l ON mt.ParentID = l.ID
    WHERE
        Depth < 99
)
SELECT 
    [Depth],
    [ID],
    [ParentID]
FROM
    [links]

Now let's say the data in my table creates a cyclical relationship (4 is parented to 2 and 2 is parented to 4. Forgetting for a moment that there should likely be constraints on the database to prevent this, the above recursive CTE query produce duplicate records (99 of them) because it will recursively evaluate that cyclical relationship between 2 and 4.

ID           ParentID
1            Null
2            1
3            1
4            2
2            4
2            4

How can I alter my query to prevent that, assuming that I have no control over preventing the actual data from representing that cyclical relationship. Normally I would put a distinct on the final select but I want the Depth value, which makes every record distinct. I'm also hoping to account for it within the CTE, as a distinct operates on the final select, and is probably not as efficient.

Steve Stedman Steve Stedman · Accepted Answer · 2015-03-19T22:29:37

You could create a tree path variable in the CTE which shows your entire path from the top of the recursive query, then check to see if the number in question is in the tree path, if it is then abort at that point.

USE Master;
GO
CREATE DATABASE [QueryTraining];
GO
USE [QueryTraining];
GO

CREATE TABLE [MyTable] (
    ID int,  --would normally be an INT IDENTITY
    ParentID int
    );

INSERT INTO [MyTable] (ID, ParentID) 
        VALUES (1, NULL),
               (2, 1),
               (3, 1),
               (4, 2),
               (2, 4),
               (2, 4);

DECLARE @StartID AS INTEGER;
SET @StartID = 1;

;WITH links (ID, ParentID, Depth, treePath)
AS
(
    --Get the starting link
    SELECT [ID],
           [ParentID],
           [Depth] = 1, 
           CAST(':' + CAST([ID] AS VARCHAR(MAX)) AS VARCHAR(MAX)) AS treePath
      FROM [MyTable] 
     WHERE [ID] = @StartID

    UNION ALL

    --Recursively get links that are parented to links already in the CTE
    SELECT mt.[ID],
           mt.[ParentID],
           [Depth] = l.[Depth] + 1,
           CAST(l.treePath + CAST(mt.[ID] AS VARCHAR(MAX)) + ':' AS VARCHAR(MAX)) AS treePath
      FROM [MyTable] mt
     INNER JOIN links l ON mt.ParentID = l.ID
       AND CHARINDEX(':' + CAST(mt.[ID] AS VARCHAR(MAX)) + ':', l.[treePath]) = 0
     WHERE Depth < 10
)
SELECT 
    [Depth],
    [ID],
    [ParentID],
    [treePath]
FROM
    [links];

The line on the INNER JOIN that says AND CHARINDEX(':' + CAST(mt.[ID] AS VARCHAR(MAX)) + ':', l.[treePath]) = 0 Is where the previous numbers in the path get filtered out.

Just copy and paste the example and give it a try.

One note, the way that I am using CHARINDEX on the CTE may not scale well, but it does accomplish what I think you are looking for.

Avoiding duplicate recursion with Common Table Expressions

1 Answers