Ordering results in SQL select query

Question

Suppose I have a table called Events with data similar to the following:

  ID |      Name      |    ParentEvent
 ----+----------------+-----------------
   0 |   Happy Event  |       NULL
   1 |    Sad Event   |       NULL
   2 |Very Happy Event|        0
   3 | Very Sad Event |        1
   4 | Happiest Event |        2
   5 |Unpleasant Event|        1

How can I query this table to get results returned in a way such that

• Events with that have a non-null ParentEvent appear directly after the event with the ID mathching the ParentEvent
• Events with a null ParentEvent have a depth of 0. If an event has a depth of n, any event that it is a parent to has a depth of n + 1.
• As long as the results satisfy the previous two conditions, the order the results appear in does not matter.

For the table given above, I would like to get a result set that looks like

  ID |      Name      |  ParentEvent |  Depth |
 ----+----------------+--------------+--------+
   0 |   Happy Event  |      NULL    |    0   |  
   2 |Very Happy Event|       0      |    1   |
   4 | Happiest Event |       2      |    2   |
   1 |    Sad Event   |      NULL    |    0   |
   3 | Very Sad Event |       1      |    1   |
   5 |Unpleasant Event|       1      |    1   |

How can I construct an SQL query to get this result set? I am using T-SQL, but if you can do this in any flavor of SQL please go ahead and answer.

Answer 1

The following queries all return the exact result set you asked for. All of these work by calculating the full path to the root nodes, and using some technique for making that path able to be ordered by.

SQL Server 2008 and up. Here, by converting to the hierarchyid data type, SQL Server handles the ordering properly.

WITH Data AS (
   SELECT
      ID,
      Name,
      ParentID,
      Depth = 0,
      Ancestry = '/' + Convert(varchar(max), ID) + '/'
   FROM
      hierarchy
   WHERE
      ParentID IS NULL
   UNION ALL
   SELECT
      H.ID,
      H.Name,
      H.ParentID,
      D.Depth + 1,
      Ancestry = D.Ancestry + Convert(varchar(max), H.ID) + '/'
   FROM
      Data D
      INNER JOIN hierarchy H
         ON H.ParentID = D.ID
)
SELECT
   ID,
   Name,
   ParentID,
   Depth
FROM Data
ORDER BY Convert(hierarchyid, Ancestry);

SQL Server 2005 and up. We can convert the ID values to string and pad them out so they sort.

WITH Data AS (
   SELECT
      ID,
      Name,
      ParentID,
      Depth = 0,
      Ancestry = Right('0000000000' + Convert(varchar(max), ID), 10)
   FROM
      hierarchy
   WHERE
      ParentID IS NULL
   UNION ALL
   SELECT
      H.ID,
      H.Name,
      H.ParentID,
      Depth + 1,
      Ancestry = D.Ancestry + Right('0000000000' + Convert(varchar(max), H.ID), 10)
   FROM
      Data D
      INNER JOIN hierarchy H
         ON H.ParentID = D.ID
)
SELECT
   ID,
   Name,
   ParentID,
   Depth
FROM Data
ORDER BY Ancestry;

Also we can use varbinary (otherwise, this is the same as the prior query):

WITH Data AS (
   SELECT
      ID,
      Name,
      ParentID,
      Depth = 0,
      Ancestry = Convert(varbinary(max), Convert(varbinary(4), ID))
   FROM
      hierarchy
   WHERE
      ParentID IS NULL
   UNION ALL
   SELECT
      H.ID,
      H.Name,
      H.ParentID,
      Depth + 1,
      Ancestry = D.Ancestry + Convert(varbinary(4), H.ID)
   FROM
      Data D
      INNER JOIN hierarchy H
         ON H.ParentID = D.ID
)
SELECT
   ID,
   Name,
   ParentID,
   Depth
FROM Data
ORDER BY Ancestry;

SQL Server 2000 and up, allowing a tree a maximum of 800 levels deep:

SELECT
   *,
   Ancestry = CASE WHEN ParentID IS NULL THEN Convert(varchar(8000), Right('0000000000' + Convert(varchar(10), ID), 10)) ELSE '' END,
   Depth = 0
INTO #hierarchy
FROM hierarchy;

WHILE @@RowCount > 0 BEGIN
   UPDATE H
   SET
      H.Ancestry = P.Ancestry + Right('0000000000' + Convert(varchar(8000), H.ID), 10),
      H.Depth = P.Depth + 1
   FROM
      #hierarchy H
      INNER JOIN #hierarchy P
         ON H.ParentID = P.ID
   WHERE
      H.Ancestry = ''
      AND P.Ancestry <> '';
END;

SELECT
   ID,
   Name,
   ParentID,
   Depth
FROM #hierarchy
ORDER BY Ancestry;

DROP TABLE #hierarchy;

The same varbinary conversion can be done, allowing up to 2000 levels deep.

Answer 2

This is just add to M.Ali's answer. I realize the OP said, "As long as the results satisfy the previous two conditions, the order the results appear in does not matter". However, by adding a column to the query that keeps track of the hierarchy path, it is possible to display the results the same as in the question.

;WITH CTE
AS
(
  SELECT 
    ID, 
    NAME,
    ParentID,
    0 as Depth,
    convert(varbinary(max), convert(varbinary(2), ID)) as ThePath
  FROM   hierarchy
  WHERE ParentID is null

  UNION ALL

  SELECT 
    h.ID, 
    h.NAME,
    h.ParentID, 
    cte.Depth + 1,
    cte.ThePath + convert(varbinary(max), convert(varbinary(2), h.ID)) as ThePath
  FROM   hierarchy AS h 
  INNER JOIN CTE as cte
  ON h.ParentID = cte.ID
)
SELECT 
  ID, 
  NAME, 
  ParentID, 
  Depth, 
  ThePath
FROM CTE 
ORDER BY ThePath

This displays the results like this.

ID          NAME                           ParentID    Depth       ThePath
----------- ------------------------------ ----------- ----------- ---------------
0           Happy Event                    NULL        0           0x0000
2           Very Happy Event               0           1           0x00000002
4           Happiest Event                 2           2           0x000000020004
1           Sad Event                      NULL        0           0x0001
3           Very Sad Event                 1           1           0x00010003
5           Unpleasant Event               1           1           0x00010005

Answer 3

Test Data

CREATE TABLE hierarchy (ID INT, NAME NVARCHAR(30), ParentID INT)
INSERT INTO hierarchy VALUES 
(0,'Happy Event'     ,NULL),
(1,'Sad Event'       ,NULL),
(2,'Very Happy Event',0),
(3,'Very Sad Event'  ,1),
(4,'Happiest Event'  ,2),
(5,'Unpleasant Event',1)

Query (Sql Server 2005+)

;WITH ClassHierarchy_CTE (CID, ClassID_Join, Level)
AS
(
SELECT ID, ID AS Join_Class, 0
FROM   hierarchy AS c

UNION ALL
SELECT cte.CID, h.ParentID, Level + 1
FROM   hierarchy AS h INNER JOIN ClassHierarchy_CTE as cte
ON     h.ID = cte.ClassID_Join
)
SELECT    CTE.CID      AS ID
        , Hic.NAME     AS NAME
        , Hic.ParentID AS ParentEvent 
        , COUNT(*)-1   AS Depth    
FROM    ClassHierarchy_CTE CTE INNER JOIN hierarchy Hic
ON      CTE.CID = Hic.ID
WHERE   ClassID_Join IS NOT NULL
GROUP BY CTE.CID, Hic.NAME, Hic.ParentID

Result Set

╔════╦══════════════════╦═════════════╦═══════╗
║ ID ║       NAME       ║ ParentEvent ║ Depth ║
╠════╬══════════════════╬═════════════╬═══════╣
║  0 ║ Happy Event      ║ NULL        ║     0 ║
║  1 ║ Sad Event        ║ NULL        ║     0 ║
║  2 ║ Very Happy Event ║ 0           ║     1 ║
║  3 ║ Very Sad Event   ║ 1           ║     1 ║
║  4 ║ Happiest Event   ║ 2           ║     2 ║
║  5 ║ Unpleasant Event ║ 1           ║     1 ║
╚════╩══════════════════╩═════════════╩═══════╝