Performance of recursive stored procedures in MYSQL to get hierarchical data

Question

Hi,

I have table employee like,
employee ( emp_id int primary key, emp_name varchar(50), mngr_id int)

and here mngr_id would either null or contain valid emp_id. This way it form the hierarchy of employees in the organization.

In order to traverse the entire hierarchy I had to write the recursive stored procedure. (in Oracle it's easy by using CONNECT BY .. START WITH)

So the question is that what is the performance impact of such stored procedure given that the level of hierarchy would not go beyond 10 levels !

Is there any other way to achieve the same ?

Answer 1

Regarding the last question: There are a few nice options at "What is the most efficient/elegant way to parse a flat table into a tree?"

You should also consider caching the result of the recursion in an intermediate table. If you change that only on update to your hierarchy table, the recursion performance hit will be negligible.

EDIT: Personally I would do the recursion in the presentation layer of my app, for example on the web server. This provides greater flexibility compared to what can be achieved in SQL, and you can also use session or application level caching. (Using a pre-constructed DB table that is kept up to date with a trigger never leaves you with an outdated cache, though.)

Answer 2

Tomalak: " ... I would do the recursion in the presentation layer of my app ... "

This would mean every time the recursion happened another call is sent to the database server from the presentation layer. That would be incredibly slow.

Answer 3

a fairly simple iterative adjacency list db server side solution: http://pastie.org/1056977

delimiter ;

drop procedure if exists employee_hier;

delimiter #

create procedure employee_hier
(
in p_emp_id smallint unsigned
)
begin

declare p_done tinyint unsigned default(0);
declare p_depth smallint unsigned default(0);

create temporary table hier(
 boss_id smallint unsigned, 
 emp_id smallint unsigned, 
 depth smallint unsigned
)engine = memory;

insert into hier values (null, p_emp_id, p_depth);

/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

create temporary table emps engine=memory select * from hier;

while p_done <> 1 do

    if exists( select 1 from employee e inner join hier on e.boss_id = hier.emp_id and hier.depth = p_depth) then

        insert into hier select e.boss_id, e.emp_id, p_depth + 1 
            from employee e inner join emps on e.boss_id = emps.emp_id and emps.depth = p_depth;

        set p_depth = p_depth + 1;          

        truncate table emps;
        insert into emps select * from hier where depth = p_depth;

    else
        set p_done = 1;
    end if;

end while;

select 
 e.emp_id,
 e.name as emp_name,
 b.emp_id as boss_emp_id,
 b.name as boss_name,
 hier.depth
from 
 hier
inner join employee e on hier.emp_id = e.emp_id
inner join employee b on hier.boss_id = b.emp_id;

drop temporary table if exists hier;
drop temporary table if exists emps;

end #

delimiter ;


call employee_hier(1);
call employee_hier(3);