How to efficiently get an ordered hierarchical list from a large table (12k records) with a column that references the primary key column

Question

I'm struggling with a optimizing a SQL query and am looking for help. T-SQL for SQL Server 2008.

I have a set of Agents that have columns Id and ManagerId. A manager is just an agent, so ManagerId is like a foreign key back to the same table. I'm writing a query to bring back the agents in an ordered list based on a managerial hierarchy.

Given the set

Id  Name    ManagerId
-----------------------
1   Charlie 4
2   Alpha   NULL
3   Echo    5
4   Bravo   2
5   Delta   1
6   Foxtrot 3
7   Golf    6
8   Hotel   7
9   Juliet  8
10  India   8

I want to return the values in this order:

Id  Name    ManagerId
2   Alpha   NULL
4   Bravo   2
1   Charlie 4
5   Delta   1
3   Echo    5
6   Foxtrot 3
7   Golf    6
8   Hotel   7
9   Juliet  8
10  India   8

The strategy I am using now works great for 10 values. The real set I will use it on is about 12,000. When I use the below query on a test set of 10,000, it takes forever ~ 20 minutes on my laptop. I'm using a loop with sub-queries so I know there must be a better way.

CREATE TABLE #hierarchy (rowNumber INT, agentId INT);
CREATE TABLE #finishedManagers (id INT);

DECLARE @index INT = 1;
DECLARE @count INT = (SELECT COUNT(Id) FROM agents);
DECLARE @thisId INT;

WHILE (@index <= @count)

BEGIN
    SET @thisId = ( 
        SELECT TOP 1
            a.Id
        FROM    
            agents a
        WHERE
            a.Id NOT IN (SELECT * FROM #finishedManagers)
            AND
            (a.ManagerId IS NULL OR a.ManagerId IN (SELECT agentId FROM #heirarchy))
            );

    INSERT INTO #hierarchy (rowNumber, agentId)
        SELECT
            @index,
            @thisId

    SET @index = @index + 1;

    INSERT INTO #finishedManagers(id)
        SELECT
            @thisId 
END
GO

SELECT 
    a.*
FROM 
    #hierarchy h
LEFT JOIN
    agents a ON h.agentId = a.Id
ORDER BY
    h.rowNumber;

DROP TABLE #hierarchy;
DROP TABLE #finishedManagers;

How would you go about this?

Answer 1

First off, always try to avoid loops when possible.

The following is an example of using a Recursive CTE in concert with the HIERARCHY data type.

Recursive CTEs are great, and well worth your time to get comfortable with them. However, the performance can suffer a bit with larger/deeper hierarchies.

There are other techniques using TEMP tables which are more performant, but a little more involved.

Example

Declare @Top   int  = null  --<<  Sets top of Hier Just for FUN Try 3

;with cteP as (
      Select ID
            ,ManagerID 
            ,Name 
            ,HierID = convert(hierarchyid,'/'+convert(varchar(25),ID)+'/')
      From   YourTable 
      Where  IsNull(@Top,-1) = case when @Top is null then isnull(ManagerID ,-1) else ID end
      Union  All
      Select ID  = r.ID
            ,ManagerID  = r.ManagerID 
            ,Name   = r.Name
            ,HierID = convert(hierarchyid,p.HierID.ToString()+convert(varchar(25),r.ID)+'/')
      From   YourTable r
      Join   cteP p on r.ManagerID  = p.ID)
Select Lvl   = HierID.GetLevel()
      ,ID
      ,Name  
      ,ManagerID
 From cteP A
 Order By A.HierID

Returns

Lvl ID  Name    ManagerID
1   2   Alpha   NULL
2   4   Bravo   2
3   1   Charlie 4
4   5   Delta   1
5   3   Echo    5
6   6   Foxtrot 3
7   7   Golf    6
8   8   Hotel   7
9   9   Juliet  8
9   10  India   8

EDIT - Temp Table Approach 25,000 row in 2 seconds

Notice that I have max depth of 30 levels.

Declare @Top int =null 
Select *
      ,Lvl=1
      ,HierID = convert(hierarchyid,'/'+convert(varchar(25),ID)+'/')
 Into #TempBld 
 From YourTable
 Where  IsNull(@Top,-1) = case when @Top is null then isnull(ManagerID,-1) else ID end

Declare @Cnt int=1
While @Cnt<=30
    Begin
        Insert Into #TempBld 
        Select A.*
              ,Lvl=B.Lvl+1
              ,HierID = convert(hierarchyid,b.HierID.ToString()+convert(varchar(25),a.ID)+'/')
         From  YourTable A
         Join  #TempBld B on (B.Lvl=@Cnt and A.ManagerID=B.ID)
        Set @Cnt=@Cnt+1
    End

Select Lvl
      ,ID
      ,Name
      ,ManagerID
 From #TempBld
 Order by HierID