MYSQL query to return all descendants of a specific parent

Question

I have this parent table. my goal is to find out given an id all of its decendents. For example for the following table:

+----------+-----+
| parentId |  id |
+----------+-----+
|  0       |   1 |
|  0       |   2 |
|  0       |   3 |
|  0       |   4 |
|  1       |   5 |
|  1       |  11 |
|  5       |  12 |
| 12       |  13 |
| 14       |  15 |
| 19       |  20 |
| 20       |  24 |
+----------+-----+

given the parent 0 i would like to get:

+----+
| Id |
+----+
|  1 |
|  2 |
|  3 |
|  4 |
|  5 |
| 11 |
| 12 |
| 13 |
+----+

My Restircions/Notes: 1. I can have 4 levels of hierarchy at the worst case. 2. my DB is MYSQL ( that means i cannot write recursive query ) . 3. the table id_to_id is pretty small.. 100 rows tops.

the solution i was thinking about was something like this sql query :

SELECT DISTINCT(T.Id)
FROM(
SELECT t1.Id
FROM id_to_id AS t1
LEFT JOIN id_to_id AS t2 ON t2.parentId = t1.Id
LEFT JOIN id_to_id AS t3 ON t3.parentId = t2.Id
LEFT JOIN id_to_id AS t4 ON t4.parentId = t3.Id
WHERE t1.parentId = 0

UNION ALL

SELECT t2.Id as lev2
FROM id_to_id AS t1
LEFT JOIN id_to_id AS t2 ON t2.parentId = t1.Id
LEFT JOIN id_to_id AS t3 ON t3.parentId = t2.Id
LEFT JOIN id_to_id AS t4 ON t4.parentId = t3.Id
WHERE t1.parentId = 0

UNION ALL

SELECT t3.Id as lev3
FROM id_to_id AS t1
LEFT JOIN id_to_id AS t2 ON t2.parentId = t1.Id
LEFT JOIN id_to_id AS t3 ON t3.parentId = t2.Id
LEFT JOIN id_to_id AS t4 ON t4.parentId = t3.Id
WHERE t1.parentId = 0

UNION ALL

SELECT t4.Id as lev4
FROM id_to_id AS t1
LEFT JOIN id_to_id AS t2 ON t2.parentId = t1.Id
LEFT JOIN id_to_id AS t3 ON t3.parentId = t2.Id
LEFT JOIN id_to_id AS t4 ON t4.parentId = t3.Id
WHERE t1.parentId = 0) as T

WHERE T.Id IS NOT NULL;

BUT then that inner query will be performed 4 times ( am i wrong here? ) :

FROM id_to_id AS t1
LEFT JOIN id_to_id AS t2 ON t2.parentId = t1.Id
LEFT JOIN id_to_id AS t3 ON t3.parentId = t2.Id
LEFT JOIN id_to_id AS t4 ON t4.parentId = t3.Id
WHERE t1.parentId = 0) as T

So my questions are:

any ideas for making it work without joining 4 times? Or another smart solution for that query?
How to write query that can perform the same on each id on the table ( can i do that?) without a given parameter - something like :

+----+------------+
| Id |  decedents |
+----+------------+
|  0 | 1,2,3,4,...|
|  1 | 5,11,...   |
+----+------------+

Thanks, Ido

This post seems to do right for you: http://stackoverflow.com/questions/10646833/using-mysql-query-to-traverse-rows-to-make-a-recursive-tree Good work! ;) — Zio Panzu, Apr 09 '14 at 14:58
Are you insistent on accomplishing this using only SQL? I had a similar issue with an infinite hierarchy of items and found it to be very clean in procedural code in the language I was ultimately using for the front-end. I will post that solution if interested. — ATP_JD, Jul 10 '15 at 03:43

drunken_monkey · Answer 1 · 2015-07-22T13:37:45.603

There is no way to do this easier with that table in MySQL. In Oracle you could perorm a query with a CONNECT BY ... START WITH clause.

But in MySQL you either have a mapping table with each combination of parents (in you example for id 11 you would have two entries: [0, 11] and [1, 11]. One for each hierachical level above it. But that would probably defeat the purpose of the table.

The other option is to do as you have already and join 4 times.

A third possibility would be to write a procedure that loops recursively over the table and outputs the result. This would also be very flexible as it does not matter how deep your hierarchie is.

create function f_recursive_id_to_id_lookup(in parent_id int)
returns varchar(255)
begin
  -- declare a variable that we use later to break the while loop
  declare l_done tinyint default 0;
  -- the result variable
  declare l_result varchar(255) default '';

  -- table to hold parent ids and insert first id from parameter
  drop table if exists tmp_ids;
  create temporary table tmp_ids(id int, unique key (id));
  insert into tmp_ids(id)
  values (parent_id);

  -- table to hold result
  drop table if exists tmp_result;
  create temporary table tmp_result(id int, unique key (id));

  while l_done = 0 do
    -- insert new ids from previous loop (or none)
    insert ignore into tmp_ids(id)
    select id from tmp_result;

    -- insert new children
    insert ignore into tmp_result(id)
    select id
    from id_to_id i2i
      join tmp_ids tid
        on i2i.parentId = tid.id;

    -- if no rows were inserted, break the loop
    -- rows already present in the table are not counted
    if row_count() = 0 then
      set l_done = 1;
    end if;
  end while;

  -- select the result from the temp table to output to console
  select ifnull(group_concat(id),'') into l_result from tmp_results;
  return l_result;
end

This function you can now use in a query:

select parentId, f_recursive_id_to_id_lookup(parentId)
from id_to_id;

This will give you the expected result. It can be slow though, as it will do the recursive lookup 100 times for 100 parentIds. What is also not covered is that only toplevel ids are listed. This lists all ids.

MYSQL query to return all descendants of a specific parent

1 Answers1