Query to get parent records with child record, followed by next parent-child records in mysql

Question

I have data in the following format in the Names table in database:

ID  | Name                     | ParentID
1   | Parent 1                 | 0
2   | Parent 2                 | 0
3   | Parent 1 Child 1         | 1
4   | Parent 2 Child 1         | 2
5   | Parent 1 Child 1 Child   | 3
6   | Parent 2 Child 1 Child 1 | 4
7   | Parent 2 Child 1 Child 2 | 4

The ParentID column is having data from ID column as parent record. ParentID with 0 value indicates root items. I need to write a query to get data in the following order:

ID  | Name                     | ParentID
1   | Parent 1                 | 0
3   | Parent 1 Child 1         | 1
5   | Parent 1 Child 1 Child   | 3
2   | Parent 2                 | 0
4   | Parent 2 Child 1         | 2    
6   | Parent 2 Child 1 Child 1 | 4
7   | Parent 2 Child 1 Child 2 | 4

I need to get the root record(record with ParentID as 0) followed by all the child and sub-children of this root record and then get the next root record followed by child and sub-children of the this root record and so on.

Answer 1

The solution I propose here uses the concept of materialized path. The following is an example of materialized paths using your sample data. I hope it helps you to understand materialized path concept:

+----+--------------------------+----------+------------------+
| ID |           Name           | ParentID | MaterializedPath |
+----+--------------------------+----------+------------------+
|  1 | Parent 1                 |        0 | 1                |
|  2 | Parent 2                 |        0 | 2                |
|  4 | Parent 2 Child 1         |        2 | 2.4              |
|  6 | Parent 2 Child 1 Child 1 |        4 | 2.4.6            |
|  7 | Parent 2 Child 1 Child 2 |        4 | 2.4.7            |
|  3 | Parent 1 Child 1         |        1 | 1.3              |
|  5 | Parent 1 Child 1 Child   |        3 | 1.3.5            |
+----+--------------------------+----------+------------------+

Each node N has a materialized path, this path tells you the way to go from the root node to the node N. It can be build concatenating the node id's. For example, to reach node 5 starting from its root node, you visit node 1, node 3, and node 5, so node 5 materialized path is 1.3.5

Coincidentally, the order you are looking for can be achieved ordering by the materialized path.

On the previous example, materialized paths are buit concatenating strings, but I prefer binary concatenation for a number of reasons.

To build the materialized paths you need the following recursive CTE:

CREATE TABLE Tree
(
    ID int NOT NULL CONSTRAINT PK_Tree PRIMARY KEY, 
    Name nvarchar(250) NOT NULL,
    ParentID int NOT NULL,
)

INSERT INTO Tree(ID, Name, ParentID) VALUES
(1, 'Parent 1', 0),
(2, 'Parent 2', 0),
(3, 'Parent 1 Child 1', 1),
(4, 'Parent 2 Child 1', 2),
(5, 'Parent 1 Child 1 Child', 3),
(6, 'Parent 2 Child 1 Child 1', 4),
(7, 'Parent 2 Child 1 Child 2', 4)

GO
WITH T AS
(
    SELECT
        N.ID, N.Name, N.ParentID, CAST(N.ID AS varbinary(512)) AS MaterializedPath
    FROM
        Tree N
    WHERE
        N.ParentID = 0

    UNION ALL

    SELECT
        N.ID, N.Name, N.ParentID, CAST( T.MaterializedPath + CAST(N.ID AS binary(4)) AS varbinary(512) ) AS MaterializedPath
    FROM
        Tree N INNER JOIN T
            ON N.ParentID = T.ID

)
SELECT *
FROM T
ORDER BY T.MaterializedPath

Result:

+----+--------------------------+----------+----------------------------+
| ID |           Name           | ParentID |      MaterializedPath      |
+----+--------------------------+----------+----------------------------+
|  1 | Parent 1                 |        0 | 0x00000001                 |
|  3 | Parent 1 Child 1         |        1 | 0x0000000100000003         |
|  5 | Parent 1 Child 1 Child   |        3 | 0x000000010000000300000005 |
|  2 | Parent 2                 |        0 | 0x00000002                 |
|  4 | Parent 2 Child 1         |        2 | 0x0000000200000004         |
|  6 | Parent 2 Child 1 Child 1 |        4 | 0x000000020000000400000006 |
|  7 | Parent 2 Child 1 Child 2 |        4 | 0x000000020000000400000007 |
+----+--------------------------+----------+----------------------------+

The above recursive CTE starts with the root nodes. Calculating the materialized path for a root node is trivially straightforward, it's the ID of the node itself. On the next iteration the CTE joins root nodes with its child nodes. The materialized path for a child node CN is the concatenation of the materialized path of its parent node PN and the id of node CN. Subsequent iterations advance one level down on the tree until the leaf nodes are reached.