Optimizing removal of duplicate rows from recursive CTE query

Question

I need to write a recursive SQL query to fetch multiple projects together with their lineage from the following table:

CREATE TABLE #Project
(
Name VARCHAR(10),
ParentName VARCHAR(10)
)

INSERT INTO #Project(Name, ParentName) VALUES ('P', NULL);
INSERT INTO #Project(Name, ParentName) VALUES ('C1', 'P');
INSERT INTO #Project(Name, ParentName) VALUES ('C2', 'P');
SELECT Name, ParentName FROM #Project

(this is just a toy example, so please ignore table design issues and the lack of indexing)

So, given multiple project names, I need to fetch a table that contains the projects as well as all their ancestors, because the result table will have to support lineage queries for a given Project name

In order to do this, I came up with the following recursive CTE query:

WITH Lineage (Name, ParentName)
AS
(
SELECT        Name, ParentName
FROM            #Project WHERE Name = 'C1' OR Name = 'C2'
UNION ALL
SELECT        #Project.Name, #Project.ParentName
FROM            #Project INNER JOIN Lineage ON #Project.Name = Lineage.ParentName
)
SELECT Name, ParentName FROM Lineage

And, here is the result of the query:

Name | ParentName
C1   | P
C2   | P
P    | NULL
P    | NULL

As expected, this returns projects C1 and C2, as well as their parents, which will be duplicated for each child, unfortunately.

In order to get rid of the duplicated parents, I added DISTINCT to the final SELECT:

SELECT DISTINCT Name, ParentName FROM Lineage

Which returns:

Name | ParentName
P    | NULL
C1   | P
C2   | P

Even though this produces the desired result, I am concerned about the performance of this query. The Lineage CTE will surely contain a lot of extra rows if I let it return these duplicates, which I remove at a later step in the query.

Is there any way to rewrite the CTE such that it removes these duplicates directly?

UPDATE: Just in case my example wasn't clear enough, I need to somehow specify the project names for which to fetch the lineages.

Answer 1

How about this? Kind of a hack - but row_number should be quicker than distinct.

;WITH Lineage AS
(
SELECT
    Name
   ,CASE WHEN ROW_NUMBER() OVER (PARTITION BY ParentName ORDER BY ParentName) > 1 
         THEN NULL 
         ELSE ParentName END AS ParentNameToJoin
   ,ParentName AS ParentNameToDisplay 
FROM
    #Project
WHERE
    Name in ('C1','C2')
UNION ALL
SELECT
    p.Name
   ,CASE WHEN ROW_NUMBER() OVER (PARTITION BY p.ParentName ORDER BY p.ParentName) > 1 
         THEN NULL 
         ELSE ParentName END AS ParentNameToJoin
   ,p.ParentName 
FROM
    #Project as p
INNER JOIN
    Lineage ON p.Name = Lineage.ParentNameToJoin
)
SELECT
    Name
   ,ParentNameToDisplay
FROM
    lineage

Answer 2

Instead of using a recursive CTE, you could consider using the built-in hierarchyid SQL Server type to store the hierarchy.

I've put together a short MCVE to illustrate how this works.

I'm doing this in tempdb:

USE tempdb;

IF OBJECT_ID(N'dbo.Projects', N'U') IS NOT NULL
DROP TABLE dbo.Projects;

CREATE TABLE dbo.Projects
(
    ProjectID int NOT NULL
        CONSTRAINT PK_Projects
        PRIMARY KEY
        CLUSTERED
        IDENTITY(1,1)
    , ProjectName varchar(30) NOT NULL
    , Hierarchy hierarchyid NOT NULL
);

Here I'm inserting some sample data. Note Top Project 2 is not referenced by any other project.

INSERT INTO dbo.Projects (ProjectName, Hierarchy)
VALUES ('Top Project', '/1/')
    , ('Top Project 2', '/2/')
    , ('Child Project 1', '/1/3/')
    , ('Child Project 2', '/1/3/4/');

SELECT p.ProjectID
    , p.ProjectName
    , Hierarchy = p.Hierarchy.ToString()
FROM dbo.Projects p

Results:

╔═══════════╦═════════════════╦═══════════╗
║ ProjectID ║   ProjectName   ║ Hierarchy ║
╠═══════════╬═════════════════╬═══════════╣
║         1 ║ Top Project     ║ /1/       ║
║         2 ║ Top Project 2   ║ /2/       ║
║         3 ║ Child Project 1 ║ /1/3/     ║
║         4 ║ Child Project 2 ║ /1/3/4/   ║
╚═══════════╩═════════════════╩═══════════╝

This query gets all the ancestor projects of Child Project 2:

SELECT p.ProjectID
    , p.ProjectName
    , Hierarchy = p.Hierarchy.ToString()
    , Parents = STUFF((SELECT ', ' + p1.ProjectName
    FROM dbo.Projects p1
    WHERE p.Hierarchy.IsDescendantOf(p1.Hierarchy) = 1
        AND p.Hierarchy <> p1.Hierarchy
    FOR XML PATH('')), 1, 2, '')
FROM dbo.Projects p
WHERE p.ProjectName = 'Child Project 2';

The results:

╔═══════════╦═════════════════╦═══════════╦══════════════════════════════╗
║ ProjectID ║   ProjectName   ║ Hierarchy ║           Parents            ║
╠═══════════╬═════════════════╬═══════════╬══════════════════════════════╣
║         4 ║ Child Project 2 ║ /1/3/4/   ║ Top Project, Child Project 1 ║
╚═══════════╩═════════════════╩═══════════╩══════════════════════════════╝