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.