Parent-Child Tree Hierarchical ORDER

Question

I have to following data in SQL Server 2008 R2. SQLFiddle

Schema:

CREATE TABLE [dbo].[ICFilters](
   [ICFilterID] [int] IDENTITY(1,1) NOT NULL,
   [ParentID] [int] NOT NULL DEFAULT 0,
   [FilterDesc] [varchar](50) NOT NULL,
   [Active] [tinyint] NOT NULL DEFAULT 1,
 CONSTRAINT [PK_ICFilters] PRIMARY KEY CLUSTERED 
 ( [ICFilterID] ASC ) WITH 
    PAD_INDEX  = OFF,
    STATISTICS_NORECOMPUTE = OFF,
    IGNORE_DUP_KEY = OFF,
    ALLOW_ROW_LOCKS  = ON,
    ALLOW_PAGE_LOCKS  = ON
 ) ON [PRIMARY]
) ON [PRIMARY]

INSERT INTO [dbo].[ICFilters] (ParentID,FilterDesc,Active)
Values 
(0,'Product Type',1),
(1,'ProdSubType_1',1),
(1,'ProdSubType_2',1),
(1,'ProdSubType_3',1),
(1,'ProdSubType_4',1),
(2,'PST_1.1',1),
(2,'PST_1.2',1),
(2,'PST_1.3',1),
(2,'PST_1.4',1),
(2,'PST_1.5',1),
(2,'PST_1.6',1),
(2,'PST_1.7',0),
(3,'PST_2.1',1),
(3,'PST_2.2',0),
(3,'PST_2.3',1),
(3,'PST_2.4',1),
(14,'PST_2.2.1',1),
(14,'PST_2.2.2',1),
(14,'PST_2.2.3',1),
(3,'PST_2.8',1)

Table:

| ICFILTERID | PARENTID |    FILTERDESC | ACTIVE |
--------------------------------------------------
|          1 |        0 |  Product Type |      1 |
|          2 |        1 | ProdSubType_1 |      1 |
|          3 |        1 | ProdSubType_2 |      1 |
|          4 |        1 | ProdSubType_3 |      1 |
|          5 |        1 | ProdSubType_4 |      1 |
|          6 |        2 |       PST_1.1 |      1 |
|          7 |        2 |       PST_1.2 |      1 |
|          8 |        2 |       PST_1.3 |      1 |
|          9 |        2 |       PST_1.4 |      1 |
|         10 |        2 |       PST_1.5 |      1 |
|         11 |        2 |       PST_1.6 |      1 |
|         12 |        2 |       PST_1.7 |      0 |
|         13 |        3 |       PST_2.1 |      1 |
|         14 |        3 |       PST_2.2 |      0 |
|         15 |        3 |       PST_2.3 |      1 |
|         16 |        3 |       PST_2.4 |      1 |
|         17 |       14 |     PST_2.2.1 |      1 |
|         18 |       14 |     PST_2.2.2 |      1 |
|         19 |       14 |     PST_2.2.3 |      1 |
|         20 |        3 |       PST_2.8 |      1 |

Every row has the ID of its parent and the root's parentid = 0. The FilterDescs are just sample descriptions so I can't try to parse those for ordering.

The Question

Is it possible to select all the rows in a tree-like manner? If so, how? When I say 'tree-like', I mean recursively select the parent followed by all of its children, then all the children of each one of those and so on. A Depth first tree traversal.

My Friends and I have tried but we have fallen short of working solutions but will keep trying. I am fairly new to sql so maybe this can be done easily and i'm just making things harder than necessary.

Example(desired) output:

| ICFILTERID | PARENTID |    FILTERDESC | ACTIVE |
--------------------------------------------------
|          1 |        0 |  Product Type |      1 |
|          2 |        1 | ProdSubType_1 |      1 |
|          6 |        2 |       PST_1.1 |      1 |
|          7 |        2 |       PST_1.2 |      1 |
|          8 |        2 |       PST_1.3 |      1 |
|          9 |        2 |       PST_1.4 |      1 |
|         10 |        2 |       PST_1.5 |      1 |
|         11 |        2 |       PST_1.6 |      1 |
|         12 |        2 |       PST_1.7 |      0 |
|          3 |        1 | ProdSubType_2 |      1 |
|         13 |        3 |       PST_2.1 |      1 |
|         14 |        3 |       PST_2.2 |      0 |
|         17 |       14 |     PST_2.2.1 |      1 |
|         18 |       14 |     PST_2.2.2 |      1 |
|         19 |       14 |     PST_2.2.3 |      1 |
|         15 |        3 |       PST_2.3 |      1 |
|         16 |        3 |       PST_2.4 |      1 |
|         20 |        3 |       PST_2.8 |      1 |
|          4 |        1 | ProdSubType_3 |      1 |
|          5 |        1 | ProdSubType_4 |      1 |

Answer 1

OK, enough brain cells are dead.

SQL Fiddle

WITH cte AS
(
  SELECT 
    [ICFilterID], 
    [ParentID],
    [FilterDesc],
    [Active],
    CAST(0 AS varbinary(max)) AS Level
  FROM [dbo].[ICFilters]
  WHERE [ParentID] = 0
  UNION ALL
  SELECT 
    i.[ICFilterID], 
    i.[ParentID],
    i.[FilterDesc],
    i.[Active],  
    Level + CAST(i.[ICFilterID] AS varbinary(max)) AS Level
  FROM [dbo].[ICFilters] i
  INNER JOIN cte c
    ON c.[ICFilterID] = i.[ParentID]
)

SELECT 
  [ICFilterID], 
  [ParentID],
  [FilterDesc],
  [Active]
FROM cte
ORDER BY [Level];

Answer 2

create table pc ( parent varchar(10), child varchar(10) )

insert into pc values('a','b');
insert into pc values('a','c');
insert into pc values('b','e');
insert into pc values('b','f');
insert into pc values('a','d');
Insert into pc values('b','g');
insert into pc values('c','h');
insert into pc values('c','i');
insert into pc values('d','j');
insert into pc values('f','k');
insert into pc values('x','y');
insert into pc values('y','z');
insert into pc values('m','n');

 DECLARE @parent varchar(10) = 'a';
 WITH cte AS
 (
  select null parent, @parent child, 0 as level
   union
  SELECT  a.parent, a.child , 1 as level
    FROM pc a
   WHERE a.parent = @parent
   UNION ALL
  SELECT a.parent, a.child , c.level +    1
  FROM pc a JOIN cte c ON a.parent = c.child
  )
  SELECT distinct parent, child , level
  FROM cte
  order by level, parent

This will give you all descendants and the level.
Hope this helps :)

Answer 3

The above does not seem to work correctly for me. Imagine a 2 table setup with facebook type of data. Table 1, has PostId + you other fields. PostId is auto increment and obviously in your interface, you will sort DESC to have the latest post at the top.

Now for the comments table. Table 2 This table CommentId is the primary key, auto number. In your gui, you want to display it ASC, so that when reading the thread, it makes sense. (oldest (smaller number) at the top) Other important keys in table 2 are: PostId (FK back to posts), and ParentId (FK to CommentId) where ParentId will be NULL if this is the "root" comment on a Post. If someone REPLY on a comment, then the parentId will be populated with the commentid.
Hope you guys get the drift. The CTE will look like this:

WITH  Comments
        AS ( SELECT  CommentId , ParentId, CAST(CommentId AS VARBINARY(MAX)) AS Sortkey, 0 AS Indent
             FROM    dbo.Comments
             WHERE   ParentId IS NULL AND PostId = 105
             UNION ALL
             SELECT  b.CommentId , b.ParentId,  c.Sortkey + CAST(b.CommentId AS varbinary(max))  AS Sortkey, c.Indent + 1 AS Indent
             FROM    dbo.Comments b
             INNER JOIN Comments c ON c.CommentId = b.ParentId
           )
   SELECT   *
   FROM     Comments
   ORDER BY Sortkey

Sample output

1   NULL    0x0000000000000001  0
5   1   0x00000000000000010000000000000001  1
6   5   0x000000000000000100000000000000010000000000000005  2
2   NULL    0x0000000000000002  0

On F/B post 105, there was a two comment (CommentIds 1 and 2) Someone then replied on Comment1 (CommentId 5, ParentId 1), and then someone else commented on that reply, so on Comment5 (CommentId 6, ParentId 6)

And viola, the sequence is correct, under the post, you can now show the comments in the right sequence. To indent the posts so that it forms and outline like in facebook (the deeper the level goes, the more it must be margined from the left), I also have a column called Indent. The roots are 0 and then in the union, we have c.Indent + 1 AS Indent In code, yo can now multiply the indent with lets assume 32px, and show the comments in a nice hierarchy and outline.

I see no problem using the auto increment primary key CommentId as the driving force for building my SortKey, as there is a better change of you messing up dates (commentdate) than messing up an database managed key that seeds with +1