Artful Common Queries

Edge node path

from the Artful Common Queries page

Given a table infotree( id int, name varchar(64), parentid int ) holding an edge list tree, how to find the path of parent rows leading to a given tree node id? Since MySQL 8.0, this is done most efficiently with a query using a Common Table Expression (see that topic on our Tips page) ...

create procedure parentwalk( pid int )
begin
  with recursive cte as (
    -- SEED ROW
    select @level:=0 as level, id, name, parentid 
    from infotree
    where id=pid
    -- RECURSE UP THE TREE FOR ALL PARENTS EXCEPT ROOT
    union all
    select @level:=@level+1 as level, t.id, t.name, t.parentid 
    from infotree t
    join cte on cte.parentid = t.id  
    where t.parentid is not null  
  )
  select id, name, parentid 
  from cte
  order by level desc;
end;

To always include the root node, omit where t.parentid is not null.

This site runs on such a tree; here's the parent path to the article you're reading ...

+------+------------------------+----------+
| id   | Tree down to ID 2106   | parentid |
+------+------------------------+----------+
|  993 | Computing              |        1 |
|  371 | SQL                    |      993 |
|  128 | MySQL                  |      371 |
|    5 | Common queries         |      128 |
|   31 | Graphs and Hierarchies |        5 |
| 2111 | Edge node path         |       31 |
+------+------------------------+----------+

Before version 8.0 of MySQL or 10.2 of MariaDB, you need to hand-code the recursive logic in a stored procedure ...

create procedure parentwalk( pid int )
begin
  set @id=pid, @n=0, @r=0;
  drop temporary table if exists temp;
  create temporary table temp( 
    ord smallint unsigned, id int, name varchar(64), parentid int 
  );
  select name, parentid into @name, @parentid from infotree where id=@id;
  repeat
    insert into temp 
      set ord=@n, id=@id, name=@name, parentid=@parentid;
    if @parentid is not null then
      set @n:=@n+1, @id=@parentid;
      select name, parentid into @name, @parentid 
      from infotree where id=@id;
      set @r = found_rows();
    end if;
  until @r=0 or @parentid is null end repeat;
  set @sql = concat( "select id, name as 'Tree down to ID ", pid, 
                     "', parentid from temp order by ord desc" 
                   );
  prepare stmt from @sql;
  execute stmt;
  drop prepare stmt;
end;

Last updated 29 Jul 2024