Hierarchical get all parents without using CTE query

Question

Introduction

There are a lot of answers out there which explains nicely how to read hierarchical data from parent-child relations. I am using mySQL and I have created a query which reads all parents (parent_id) (concatenated through comma) for a given id:

create table `menu` (
    `id` double ,
    `title` varchar (765),
    `controller` varchar (765),
    `method` varchar (765),
    `url` varchar (765),
    `parent_id` varchar (765),
    `added_date` datetime ,
    `updated_date` datetime 
);

Full example with table filled: http://sqlfiddle.com/#!9/48d276f/171 . The query should run without CTE and currently looks like:

SELECT GROUP_CONCAT(T2.id) AS parents
FROM (
    SELECT
        @r AS _id,
        (SELECT @r := parent_id FROM menu WHERE id = _id) AS parent_id,
        @l := @l + 1 AS lvl
    FROM (SELECT @r := 31, @l := 0) vars, menu m
    WHERE @r <> 0) T1
JOIN menu T2
ON T1._id = T2.id
ORDER BY T1.lvl DESC;

The result of the query is:

parents
-------------
3,17,31

Challenge:

I want to create the same query which allows me to read parents of multiple id's. I thought a subquery would help but I get an error (Unknown table 'T3' in field list) when passing the id to the subquery.

Expected result should be:

id      | parents
-----------------------
25      | 5,25
31      | 3,17,31
23      | 4,23

The used query (http://sqlfiddle.com/#!9/48d276f/180):

SELECT T3.id, T4.parents
FROM menu T3, (SELECT T3.id, GROUP_CONCAT(T2.id) AS parents
  FROM (
      SELECT
          @r AS _id,
          (SELECT @r := parent_id FROM menu WHERE id = _id) AS parent_id,
          @l := @l + 1 AS lvl
      FROM (SELECT @r := T3.id, @l := 0) vars, menu m
      WHERE @r <> 0) T1
  JOIN menu T2
  ON T1._id = T2.id
  ORDER BY T1.lvl DESC) T4
WHERE T3.id IN (25, 31, 23)

Sorry, I do not exactly understand what you mean. In this case every id can be a parent_id of another row. For example for the id 31 the parents are 31 (self) -> 17 (1 level up) -> 3 (2 level up) -> 0 (not visible in result because this is the "root"). — Matthias Günter, Sep 28 '17 at 08:35
He meant: the list of parents for id = 31 contains "31" itself (which is not a parent of 31). Your list is probably more like a "path", including the element itself. — Solarflare, Sep 28 '17 at 10:37

Solarflare · Accepted Answer · 2017-09-28T12:04:36.523

You can apply the same logic as with a single id by using another join, thus basically repeating that evaluation several times. Since you cannot use fixed start values anymore, I encoded the condition to reinitialize the variables in the cross join ("reset_r").

Try the following:

SELECT t1.id, GROUP_CONCAT(t1.r ORDER BY t1.lvl DESC) AS parents
FROM (
  SELECT
    t0.r_init AS id, 
    @r := IF(t0.reset_r = 1, t0.r_init, 
              (select parent_id from menu where id = @r)) AS r,
    @l := IF(t0.reset_r = 1, 1, @l + 1) AS lvl
  FROM 
    (SELECT m0.id as counter, m1.id AS r_init,
       ((SELECT min(id) FROM menu) = m0.id) AS reset_r 
     FROM menu m0, menu m1
     WHERE m1.id IN (25, 31, 23)
    ) t0 
  ORDER BY t0.r_init, t0.counter
) t1
WHERE t1.r <> 0
-- or instead of "where":
-- JOIN menu t2 ON t2.id = t1.r;
GROUP BY t1.id;

For large tables, you should either limit p to the maximum depth of your tree, or use a different data model. Also, although your table structure is probably due to being an example, you should obviously use a primary key (otherwise the parents and the reset condition are not well-defined) and the same datatype for parent_id and id.

Update: a version of that query for MySQL 5.6 (that should work on sql-fiddle too), using some more materialization:

SELECT t2.id, GROUP_CONCAT(t2.r ORDER BY t2.lvl DESC)
FROM (
  SELECT id, r, lvl
  FROM (
    SELECT
      t0.r_init AS id,
      @r := IF(t0.reset_r = 1, t0.r_init, 
                (select parent_id from menu where id = @r)) AS r,
      @l := IF(t0.reset_r = 1, 1, @l + 1) AS lvl
    FROM 
      (SELECT m0.id as counter, m1.id AS r_init,
         ((SELECT min(id) FROM menu) = m0.id) AS reset_r 
       FROM menu m0, menu m1
       WHERE m1.id IN (25, 31, 23)
       ORDER BY r_init, counter
      ) t0 
    ORDER BY t0.r_init, t0.counter
  ) t1
  WHERE r <> 0
) t2
GROUP BY t2.id;

As you can see from this fiddle: http://sqlfiddle.com/#!9/48d276f/206 it only returns one row instead of the expected result of three rows. Yes, the parents list is more like a path as you mentioned in the other comment. — Matthias Günter, Sep 28 '17 at 11:00
It works on 5.7., but you are right, I didn't check on fiddle. I'll add a version that should work on 5.6. (using some materialization). Generally, using variables is always a bit tricky and might (like in this case) depend on the mysql version and thus only a workaround for using standardized recursion. — Solarflare, Sep 28 '17 at 11:50

Hierarchical get all parents without using CTE query

Introduction

Challenge:

1 Answers1