8

Given a hierarchical table like this:

CREATE TABLE [dbo].[btree]
(
  id INT PRIMARY KEY
, parent_id INT REFERENCES [dbo].[btree] ([id])
, name NVARCHAR(20)
);

I would like to obtain the whole tree structure.

For instance, using this data:

INSERT INTO [btree] VALUES (1, null, '1 Root');
INSERT INTO [btree] VALUES (2,    1, '1.1 Group');
INSERT INTO [btree] VALUES (3,    1, '1.2 Group');
INSERT INTO [btree] VALUES (4,    2, '1.1.1 Group');
INSERT INTO [btree] VALUES (5,    2, '1.1.2 Group');
INSERT INTO [btree] VALUES (6,    3, '1.2.1 Group');
INSERT INTO [btree] VALUES (7,    3, '1.2.2 Group');
INSERT INTO [btree] VALUES (8,    4, '1.1.1.1 Items');
INSERT INTO [btree] VALUES (9,    4, '1.1.1.2 Items');
INSERT INTO [btree] VALUES (10,   5, '1.1.2.1 Items');
INSERT INTO [btree] VALUES (11,   5, '1.1.1.2 Items');
INSERT INTO [btree] VALUES (12,   6, '1.2.1.1 Items');
INSERT INTO [btree] VALUES (13,   6, '1.2.1.2 Items');
INSERT INTO [btree] VALUES (14,   7, '1.2.2.1 Items');

I would like to obtain:

+----+-----------+---------------------+
| id | parent_id | description         |
+----+-----------+---------------------+
|  1 |    NULL   | 1 Root              |
|  2 |     1     |   1.1 Group         |
|  4 |     2     |     1.1.1 Group     |
|  8 |     4     |       1.1.1.1 Items |
|  9 |     4     |       1.1.1.2 Items |
|  5 |     2     |     1.1.2 Group     |
| 10 |     5     |       1.1.2.1 Items |
| 11 |     5     |       1.1.2.2 Items |
|  3 |     1     |   1.2 Group         |
|  6 |     3     |     1.2.1 Group     |
| 12 |     6     |       1.2.1.1 Items |
| 13 |     6     |       1.2.1.2 Items |
|  7 |     3     |     1.2.2 Group     |
| 14 |     7     |       1.2.2.1 Items |
+----+-----------+---------------------+

I'm fetching records using a recursive query like this:

;WITH tree AS
(
    SELECT c1.id, c1.parent_id, c1.name, [level] = 1
    FROM dbo.[btree] c1
    WHERE c1.parent_id IS NULL
    UNION ALL
    SELECT c2.id, c2.parent_id, c2.name, [level] = tree.[level] + 1
    FROM dbo.[btree] c2 INNER JOIN tree ON tree.id = c2.parent_id
)
SELECT tree.level, tree.id, parent_id, REPLICATE('  ', tree.level - 1) + tree.name AS description
FROM tree
OPTION (MAXRECURSION 0)
;

And this is the current result:

+----+-----------+---------------------+
| id | parent_id | description         |
|  1 |    NULL   | 1 Root              |
|  2 |     1     |   1.1 Group         |
|  3 |     1     |   1.2 Group         |
|  6 |     3     |     1.2.1 Group     |
|  7 |     3     |     1.2.2 Group     |
| 14 |     7     |       1.2.2.1 Items |
| 12 |     6     |       1.2.1.1 Items |
| 13 |     6     |       1.2.1.2 Items |
|  4 |     2     |     1.1.1 Group     |
|  5 |     2     |     1.1.2 Group     |
| 10 |     5     |       1.1.2.1 Items |
| 11 |     5     |       1.1.1.2 Items |
|  8 |     4     |       1.1.1.1 Items |
|  9 |     4     |       1.1.1.2 Items |
+----+-----------+---------------------+

I can't figure out how to order it by levels.

Is there a way to set a rank for each sub-level?

I've set up a Rextester

7

Add a "path" field and sort by that similar to a file path. As ypercube mentioned, the sorting is overly simplistic in this example and just happens to work but for simplicity's sake I'll leave as is. Most of the time when I use this pattern I sort by name rather than ID anyway.

IF OBJECT_ID('[dbo].[btree]', 'U') IS NOT NULL 
    DROP TABLE [dbo].[btree];
GO

CREATE TABLE [dbo].[btree]
(
  id INT PRIMARY KEY
, parent_id INT REFERENCES [dbo].[btree] ([id])
, name NVARCHAR(20)
);
GO

INSERT INTO [btree] VALUES (1, null, '1 Root');
INSERT INTO [btree] VALUES (2,    1, '1.1 Group');
INSERT INTO [btree] VALUES (3,    1, '1.2 Group');
INSERT INTO [btree] VALUES (4,    2, '1.1.1 Group');
INSERT INTO [btree] VALUES (5,    2, '1.1.2 Group');
INSERT INTO [btree] VALUES (6,    3, '1.2.1 Group');
INSERT INTO [btree] VALUES (7,    3, '1.2.2 Group');
INSERT INTO [btree] VALUES (8,    4, '1.1.1.1 Items');
INSERT INTO [btree] VALUES (9,    4, '1.1.1.2 Items');
INSERT INTO [btree] VALUES (10,   5, '1.1.2.1 Items');
INSERT INTO [btree] VALUES (11,   5, '1.1.2.2 Items');
INSERT INTO [btree] VALUES (12,   6, '1.2.1.1 Items');
INSERT INTO [btree] VALUES (13,   6, '1.2.1.2 Items');
INSERT INTO [btree] VALUES (14,   7, '1.2.2.1 Items');

;WITH tree AS
(
    SELECT c1.id, c1.parent_id, c1.name, [level] = 1, path = cast('root' as varchar(100))
    FROM dbo.[btree] c1
    WHERE c1.parent_id IS NULL
    UNION ALL
    SELECT c2.id, c2.parent_id, c2.name, [level] = tree.[level] + 1, 
           Path = Cast(tree.path+'/'+right('000000000' + cast(c2.id as varchar(10)),10) as varchar(100))
    FROM dbo.[btree] c2 INNER JOIN tree ON tree.id = c2.parent_id
)
SELECT tree.path, tree.id, parent_id, REPLICATE('  ', tree.level - 1) + tree.name AS description
FROM tree
Order by path
OPTION (MAXRECURSION 0)
;

Here a rextester

| improve this answer | |
  • It's the right idea but in the path expression should have c2.id replaced with a row_number and padded on the left so all the parts have equal length. Otherwise, it won't work for all data. Just replace 2 with 55 in the data and the order changes – ypercubeᵀᴹ Jan 12 '17 at 23:34
  • Totally agree. I'm on mobile and wanted to win the race to the answer :) Actually I'd use the "name" field in the path generally. That's usually my use case. – Ben Campbell Jan 12 '17 at 23:35
  • I'm probably wrong about the row number (not needed) but the padding is. +1 (If we do use row_number, the path will reconstruct the first part of name!) – ypercubeᵀᴹ Jan 12 '17 at 23:40
  • I've edited the Path with a small correction, to add padding. – ypercubeᵀᴹ Jan 12 '17 at 23:47
  • 1
    I usually use double my expected path length if there's any doubt as to max depth. Also you can reduce the zero padding if you know the maximum order of magnitude of the ID/row_number. – Ben Campbell Jan 13 '17 at 0:14
4

Cheating, just a bit ;) Look ma, no recursion!

Tested at rextester.com

SELECT btree.*        -- , a,b,c,d     -- uncomment to see the parts
FROM btree 
  OUTER APPLY
    ( SELECT rlc = REVERSE(LEFT(name, CHARINDEX(' ', name)-1))) AS r
  OUTER APPLY
    ( SELECT a = CAST(REVERSE(PARSENAME(r.rlc, 1)) AS int),
             b = CAST(REVERSE(PARSENAME(r.rlc, 2)) AS int),
             c = CAST(REVERSE(PARSENAME(r.rlc, 3)) AS int),
             d = CAST(REVERSE(PARSENAME(r.rlc, 4)) AS int)
    ) AS p 
ORDER BY a, b, c, d ;

Of course the above is rather limited. It works only under the assumptions:

  • the name column has stored (in the first part) the actual "path".
  • the depth of the tree is maximum 4 (so the path has up to 4 parts).
  • the CAST .. AS int is needed only if the parts are numbers.

Explanation: The code works by using the function PARSENAME() which has the main purpose of splitting an object name into its 4 parts:

Server.Database.Schema.Object
  |        |       |      |
 4th      3rd     2nd    1st

Note that the order is reverse. As an example, PARSENAME('dbo.btree', 2) will give us 'dbo' as a result.With 3, we'll get NULL (that's why the REVERSE() is used twice in the code. Otherwise we'd get the nulls in the beginning. The '1.2' would be parsed into null, null, 1, 2 while we want 1, 2, null, null.)


Conclusion: after all that, I should add that the answer by Bob Campbel is the way to go as it is more general and produces (in the "path" column in the result) the path hierarchy, which can then be used for the ORDER BY.

Other options you may consider - if the size of the table grows big and the recursive solution becomes slow - is to actually store the path in a separate column (in a format that is good for ordering, i.e. with padding) or to use the provided HierarchyID type which is exactly for this use case, hierarchical data.

| improve this answer | |
  • :) It's really awesome! Unfortunately name cannot be used in this case. It will take me all night long to decipher it, could I have some explanation? – McNets Jan 12 '17 at 23:47
  • So, the "name" column does not have the data you provided in the example? Pity. – ypercubeᵀᴹ Jan 12 '17 at 23:49
  • No, I've used it as example, just to remark there are some levels. – McNets Jan 12 '17 at 23:52
  • 1
    @Mcnets in the (unlikely) case that the name does store a path (with text), like 'order173.palletA27.box9'.bag3A, you could still use the code (just remove the casts to int). In any case, the query by BenCambell is the way to go in general. – ypercubeᵀᴹ Jan 13 '17 at 0:04
  • 1
    @EvanCarroll yes, the hierarchyid type. I was just adding a last paragraph about other options with link. – ypercubeᵀᴹ Jan 13 '17 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.