"SQL Spackle" is a collection of short articles written based on multiple requests for similar code. These short articles are NOT meant to be complete solutions. Rather, they are meant to "fill in the cracks".

--Phil McCracken

Update

This "SQL Spackle" article is just the tip of the proverbial iceberg when it comes to hierarchies.  If your hierarchies contain more than just a couple of hundred rows, you might be interested in the following reading list. These articles weren't available when this article was first published.

For some very high performance methods for building/maintaining (54 seconds for a million node hierarchy) from an Adjacency List and using Nested Sets in conjunction with both an Adjacency List and a Hierarchical Path all in one table, please see the following article.

Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets

For information on how to build a pre-aggregated hierarchical table that contains answers for most of the things you'd ever query a hierarchical table for (MLM'ers will love this one), please see the following article.

Hierarchies on Steroids #2: A Replacement for Nested Sets Calculations

Thanks for the "read", folks.  I hope these articles are of some help to you.  As "Red Green" would say, "We're all in this together and I'm pullin' for ya." 😉

Introduction

One common T-SQL code request is "How do I sort a hierarchical list for display"? What folks typically mean when they ask that question is how to display an "Adjacency List" (ie: a typical Child/Parent list) in a sorted order similar to a "drill down" control without all the fancy lines. Without delving into the requirements, advantages, pitfalls, or other comparisons of the different structures of hierarchical data, let's see how we can easily sort the output of a query on hierarchical data stored as an "Adjacency List".

There are a whole lot more things you can do with hierarchies so, just as a reminder, this is a very "incomplete" solution compared to a whole hierarchical system. The only thing this short bit of "SQL Spackle" is meant to do is to show you one quick method for displaying hierarchical data in an expected order. Watch for a much more complete article in the next month or two.

"Adjacency List" Test Data

As always, one of the easiest methods to describe a problem is to simply build some data that represents the problem. In this bit of "SQL Spackle", we want to build data that represents the following small hierarchical organizational chart:

Figure 1 - A Typical Hierarchy

Here's the code to create the table and data as an "Adjacency List" which represents the above hierarchy:

/***********************************************************
 Create an "Adjacency List" Hierarchical Model
***********************************************************/--===== Since we're going to drop and create tables, 
     -- do this in a nice safe place that everyone has.
    USE TempDB
;
--===== Conditionally drop Temp tables to make reruns easy
     IF OBJECT_ID('dbo.Employee','U') IS NOT NULL
        DROP TABLE dbo.Employee
;
--===== Create the test table with a clustered PK 
 CREATE TABLE dbo.Employee
        (
        EmployeeID   INT         NOT NULL,
        ManagerID    INT         NULL,
        EmployeeName VARCHAR(10) NOT NULL,
        Sales        INT         NOT NULL,
        CONSTRAINT PK_Employee          
            PRIMARY KEY CLUSTERED (EmployeeID ASC),
        CONSTRAINT FK_Employee_Employee 
            FOREIGN KEY (ManagerID) 
            REFERENCES dbo.Employee (EmployeeID)
        )
;
--===== Populate the test table with test data.
     -- Since each row forms a parent/child relationship, 
     -- it's an "Adjacency Model.
 INSERT INTO dbo.Employee
        (EmployeeID, ManagerID, EmployeeName, Sales)
 SELECT  1,NULL,'Jim'    ,200000 UNION ALL
 SELECT  2,   1,'Lynne'  , 90000 UNION ALL
 SELECT  3,   1,'Bob'    ,100000 UNION ALL
 SELECT  6,  17,'Eric'   , 75000 UNION ALL
 SELECT  8,   3,'Bill'   , 80000 UNION ALL
 SELECT  7,   3,'Vivian' , 60000 UNION ALL
 SELECT 12,   8,'Megan'  , 50000 UNION ALL
 SELECT 13,   8,'Kim'    , 55000 UNION ALL
 SELECT 17,   2,'Butch'  , 70000 UNION ALL
 SELECT 18,  39,'Lisa'   , 40000 UNION ALL
 SELECT 20,   3,'Natalie', 40000 UNION ALL
 SELECT 21,  39,'Homer'  , 30000 UNION ALL
 SELECT 39,   1,'Ken'    , 90000 UNION ALL
 SELECT 40,   1,'Marge'  ,120000
;
--===== Add an index to speed things up a bit
     -- for the code that follows.
 CREATE INDEX IX_Employee_Composite01
     ON dbo.Employee (ManagerID, EmployeeID, EmployeeName)
;
--===== Display the data in the Employee table
 SELECT * 
   FROM dbo.Employee
  ORDER BY EmployeeID
;

As you can see from the output of the final SELECT from the code above (which will be in the same order as the data listed above), there's no hint of a hierarchical order based on the order of the rows themselves. What we must do is build a "Hierarchical Path" (some call it a "Hierarchical Sort") column so that we can display the data in a sort of "drill down" fashion.

Selecting a "Down-line"

Books Online suggests using a recursive CTE much like the following code to select everyone in the "down-line" (i.e.: create a list of subordinates regardless of level):

--===== Recursive CTE similar to that found in Books Online.
     -- Nodes are returned in no particular order.
WITH 
cteDirectReports AS 
(--==== Get the "Root" row
 SELECT EmployeeID, ManagerID, EmployeeLevel = 1
   FROM dbo.Employee
  WHERE EmployeeID = 1 --CHANGE THIS VALUE FOR THE DOWNLINE OF OTHERS
  UNION ALL
 --==== Recurse through each level of the hierarchy
 SELECT e.EmployeeID, e.ManagerID, EmployeeLevel = EmployeeLevel + 1
   FROM dbo.Employee e
  INNER JOIN cteDirectReports d ON e.ManagerID = d.EmployeeID 
)--==== Display the output from the CTE above
 SELECT EmployeeID, ManagerID, EmployeeLevel 
   FROM cteDirectReports;
;

Notice that the "Root" node referred to in the code above could be any EmployeeID but "1" was used in this example because, if you look back at the org chart in Figure 1, "Jim" is at the top level and we want to display everyone in his "down-line". Keep in mind that we could have used any EmployeeID to find just their down-line.

The way the code works is the first SELECT in the CTE finds the "Root" (the single Yellow box in Figure 1) of the down-line we want to examine. This section of the code is usually referred to as the "Anchor Section" of the CTE.

The second SELECT in the CTE is known as the "Recursive Section". It processes one level of the hierarchy at a time on right after the other. For example, in the org chart diagram in Figure 1, it will process Level 2 (the Green boxes) and then process Level 3 (the Blue boxes), and finally process Level 4 (the Purple boxes). As a side bar, this sounds like "RBAR" but it's not because more than one row is processed for all but the "Anchor Section" of the code. Joe Celko refers to this a "Lasagna Code" because it processes entire "layers" or levels of the hierarchy.

The problem is, even though we successfully selected everyone in the down-line for Jim, the output still doesn't represent anything that could be thought of as a "drill down order" and certainly doesn't reflect the expected order of a hierarchy.

Building the "Hierarchical Path" Column

We need something to sort on which will return the data in more of a "drill down order". In order to do that, all we need to do is include everyone in the "up-line" for every node. It sounds rather complicated but it's not. Using the recursive CTE that we used to find everyone in the "down-line", we can simply concatenate the EmployeeID of each node to all the previous nodes. It's simple. Take a look at the "HierarchicalPath" column in the following code:

--===== Recursive CTE similar to that found in Books Online with
     -- an added human readable "HierarchicalPath" column to sort on
     -- Nodes are returned in expected hierarchical order order
WITH 
cteDirectReports AS 
(
 SELECT EmployeeID, ManagerID, EmployeeLevel = 1,
        HierarchicalPath = CAST('\'+CAST(EmployeeID AS VARCHAR(10)) AS VARCHAR(4000))
   FROM dbo.Employee
  WHERE ManagerID IS NULL
  UNION ALL
 SELECT e.EmployeeID, e.ManagerID, EmployeeLevel = d.EmployeeLevel + 1,
        HierarchicalPath = CAST(d.HierarchicalPath + '\'+CAST(e.EmployeeID AS VARCHAR(10)) AS VARCHAR(4000))
   FROM dbo.Employee e
  INNER JOIN cteDirectReports d ON e.ManagerID = d.EmployeeID 
)
 SELECT EmployeeID, ManagerID, EmployeeLevel, HierarchicalPath 
   FROM cteDirectReports
  ORDER BY HierarchicalPath
;

Let's see how that works for just one node: Take a look at "Kim" on the org chart below...

Figure 2 - Kim's Up-Line

Starting from the top, we can see that "Jim" is EmployeeID "1". As we move towards "Kim", each EmployeeID is concatenated to the Hierarchical Path (see the Red lettering on the left side of Figure 2). When we finally get to "Kim", the entire "up-line" for "Kim" is contained in the Hierarchical Path and, guess what? THAT's what we sort on to get a sort similar to what we'd expect for a "drill down order" and the output can look like this.

Figure 3 - A Human Readable Hierarchical Path

Notice in the above (Figure 3) that "Kim" (EmployeeID 13) has an "up-line" of \1\3\8\13 just like what was depicted in the Figure 2.

Formatting the Output

Yeah, I know. I'll be the first to say that formatting should be done in the GUI. Still, sometimes you've got to appease the Boss or some BA or other customer.

Formatting the output of hierarchical queries usually isn't anything more than simple indention. We happen to have a very handy column to control such indenting call "EmployeeLevel". If we subtract 1 from that level and multiply the result by 4 spaces, we get what looks like a "drill down" menu. Here's the code. Notice the SPACE function and the formula it contains:

WITH 
cteDirectReports AS 
(
 SELECT EmployeeID, ManagerID, EmployeeName, EmployeeLevel = 1,
        HierarchicalPath = CAST('\'+CAST(EmployeeID AS VARCHAR(10)) AS VARCHAR(4000))
   FROM dbo.Employee
  WHERE ManagerID IS NULL
  UNION ALL
 SELECT e.EmployeeID, e.ManagerID, e.EmployeeName, EmployeeLevel = d.EmployeeLevel + 1,
        HierarchicalPath = CAST(d.HierarchicalPath + '\'+CAST(e.EmployeeID AS VARCHAR(10)) AS VARCHAR(4000))
   FROM dbo.Employee e
  INNER JOIN cteDirectReports d ON e.ManagerID = d.EmployeeID 
)
 SELECT EmployeeID,
        ManagerID,
        EmployeeName = SPACE((EmployeeLevel-1)*4) + EmployeeName,
        EmployeeLevel,
        HierarchicalPath 
   FROM cteDirectReports
  ORDER BY HierarchicalPath
;

Here's what the output from the above code looks like. Notice how each name is indented according to the level in the hierarchy.

Figure 4 - Nodes Indented According to Level in Order by EmployeeID

Sorting By Name

If you REALLY need nodes on each level to be sorted by name, just substitute EmployeeName for EmployeeID in the HierarchicalPath column. Like this...

WITH 
cteDirectReports AS 
(
 SELECT EmployeeID, ManagerID, EmployeeName, EmployeeLevel = 1,
        HierarchicalPath = CAST('\'+CAST(EmployeeName AS VARCHAR(10)) AS VARCHAR(4000))
   FROM dbo.Employee
  WHERE ManagerID IS NULL
  UNION ALL
 SELECT e.EmployeeID, e.ManagerID, e.EmployeeName, EmployeeLevel = d.EmployeeLevel + 1,
        HierarchicalPath = CAST(d.HierarchicalPath + '\'+CAST(e.EmployeeName AS VARCHAR(10)) AS VARCHAR(4000))
   FROM dbo.Employee e
  INNER JOIN cteDirectReports d ON e.ManagerID = d.EmployeeID 
)
 SELECT EmployeeID,
        ManagerID,
        EmployeeName = SPACE((EmployeeLevel-1)*4) + EmployeeName,
        EmployeeLevel,
        HierarchicalPath 
   FROM cteDirectReports
  ORDER BY HierarchicalPath
;
 

Here's what the output from the above code looks like:

As a bit of a side bar, the methods used in this article are similar to the methods used to build the new HierarchyID datatype from an "Adjacency List" in SQL Server 2008 and above.

Crack filled!

Thanks for listening, folks.

--Jeff Moden

"RBAR" is pronounced "ree-bar" and is a "Modenism" for "Row By Agonizing Row"