Christoffer Kjølbæk I have a blog, therefore I am…

Making “backtrace” in MySQL with “recursive” call

Having items mapped in a tree structure is often used in database design, using "child" and "parent" ids or "nodes" and "leaf nodes". Often when presenting data, it is nice to make a "backtrace" by showing all nodes from the leaf to the root of the tree.

In this case I have a system with a lot of users, each of which is mapped to a group. The groups are defined as a tree structure, but because of the roles of the system, the leaf node can never be more than three nodes away from the root. I need to show a list of, say all users not logged in the last 2 months, and the list should show in which groups the users is located.

I could find all users, get the group id from each users and with a recursive function in the application, find the parent group id of the group, get this group from the database, find the parent group id of the group, get this group from the database..... This would require a lot of database activity. It is also possible to make nested sets or stored procedures, but if the depth of the three is relative low (and known), I believe the below is simpler.

The table of groups is defined as:

CREATE TABLE `groups` (
	`gid` INT NOT NULL AUTO_INCREMENT PRIMARY KEY ,
	`pgid` INT NOT NULL ,
	`title` VARCHAR( 100 ) NOT NULL 
) ENGINE = MYISAM ;

With these groups:

mysql> select * from groups;
+-----+------+---------+
| gid | pgid | title   |
+-----+------+---------+
|   1 |    0 | Level 1 |
|   2 |    1 | Level 2 |
|   3 |    2 | Level 3 |
|   4 |    3 | Level 4 |
|   5 |    4 | Level 5 |
+-----+------+---------+
5 rows in set (0.00 sec)

With the below query, it is possible to make the backtrace using joins. Line 6 will find the record holding the parent group of the selected group as the temporary record bt1. Line 7 will then use the parent group id from bt1 to find this group as bt2, and so on.

1
2
3
4
5
6
7
8
9

SELECT groups.gid, groups.title, 
	bt1.gid AS 'gid-1', bt1.title AS 'title-1', 
	bt2.gid AS 'gid-2', bt2.title AS 'title-2', 
	bt3.gid AS 'gid-3', bt3.title AS 'title-3'
FROM groups
	LEFT JOIN groups AS bt1 ON bt1.gid = groups.pgid
	LEFT JOIN groups AS bt2 ON bt2.gid = bt1.pgid
	LEFT JOIN groups AS bt3 ON bt3.gid = bt2.pgid
WHERE groups.gid IN (1,2,3,4,5);

The result is

+-----+---------+-------+---------+-------+---------+-------+---------+
| gid | title   | gid-1 | title-1 | gid-2 | title-2 | gid-3 | title-3 |
+-----+---------+-------+---------+-------+---------+-------+---------+
|   1 | Level 1 |  NULL | NULL    |  NULL | NULL    |  NULL | NULL    |
|   2 | Level 2 |     1 | Level 1 |  NULL | NULL    |  NULL | NULL    |
|   3 | Level 3 |     2 | Level 2 |     1 | Level 1 |  NULL | NULL    |
|   4 | Level 4 |     3 | Level 3 |     2 | Level 2 |     1 | Level 1 |
|   5 | Level 5 |     4 | Level 4 |     3 | Level 3 |     2 | Level 2 |
+-----+---------+-------+---------+-------+---------+-------+---------+
5 rows in set (0.00 sec)

This is not really a recursive call as the title says, but the result is the same, though much faster :)