Recursive SQL CTE's and Custom Sort Ordering

Image you are creating a DB schema for a threaded discussion board. Is there an efficient way to select a properly sorted list for a given thread? The code I have written works but does not sort the way I would like it too.

Let's say you have this data:

ID   |  ParentID
-----------------
1    |   null
2    |   1
3    |   2
4    |   1
5    |   3

So the structure is supposed to look like this:

1
|- 2
|  |- 3
|  |  |- 5
|- 4

Ideally, in the code, we want the result set to appear in the following order: 1, 2, 3, 5, 4
PROBLEM: With the CTE I wrote it is actually being returned as: 1, 2, 4, 3, 5

I know this would be easy to group/order by using LINQ but I am reluctant to do this in memory. It seems like the best solution at this point though...

Here is the CTE I am currently using:

with Replies as ( 
 select c.CommentID, c.ParentCommentID 1 as Level
     from Comment c
  where ParentCommentID is null and CommentID = @ParentCommentID

 union all

 select c.CommentID, c.ParentCommentID, r.Level + 1 as Level
    from Comment c
    inner join Replies r on c.ParentCommentID = r.CommentID
)

select * from Replies

Any help would be appreciated; Thanks!

---

I'm new to SQL and had not heard about hierarchyid datatype before. After reading about it from this comment I decided I may want to incorporate this into my design. I will experiment with this tonight and post more information if I have success.

---

Update
Returned result from my sample data, using dance2die's suggestion:

ID  |  ParentID  | Level  | DenseRank
-------------------------------------
15     NULL          1         1
20     15            2         1
21     20            3         1
17     22            3         1
22     15            2         2
31     15            2         3
32     15            2         4
33     15            2         5
34     15            2         6
35     15            2         7
36     15            2         8

From stackoverflow

• Hmmmm - I am not sure if your structure is the best suited for this problem. Off the top of my head I cannot think of anyway to sort the data as you want it within the above query.

  The best I can think of is if you have a parent table that ties your comments together (eg. a topic table). If you do you should be able to simply join your replies onto that (you will need to include the correct column obviously), and then you can sort by the topicID, Level to get the sort order you are after (or whatever other info on the topic table represents a good value for sorting).

• Consider storing the entire hierarchy (with triggers to update it if it changes ) in a field.

  This field in your example would have: 1 1.2 1.2.3 1.2.5 1.4

  then you just have to sort on that field, try this and see:

  create table #temp (test varchar (10))
  insert into #temp (test)
  select '1'
  union select '1.2'
  union select '1.2.3'
  union select '1.2.5'
  union select '1.4'
  select * from #temp order by test asc
  

  AlexKuznetsov : yes - this is called materialized path

• I am sure that you will love this. I recently find out about Dense_Rank() function, which is for "ranking within the partition of a result set" according to MSDN

  Check out the code below and how "CommentID" is sorted.

  As far as I understand, you are trying to partition your result set by ParentCommentID.

  Pay attention to "denserank" column.

  with Replies (CommentID, ParentCommentID, Level) as 
  (
       select c.CommentID, c.ParentCommentID, 1 as Level
       from Comment c
       where ParentCommentID is null and CommentID = 1
  
          union all
  
       select c.CommentID, c.ParentCommentID, r.Level + 1 as Level
       from Comment c
         inner join Replies r on c.ParentCommentID = r.CommentID
  )
  select  *,
       denserank = dense_rank() over (partition by ParentCommentID order by CommentID)
  from    Replies
  order by denserank
  

  

  Result below

  Bill Gates : Thanks for the suggestion, I was trying to get dense_rank() to work at first with no luck. I queried your code on my sample data and it worked...almost. One row was out of order. I will post the data above.

• You have to use hierarchyid (sql2008 only) or a bunch of string (or byte) concatenation.