Mysql – Loop through Self JOIN on table until the operand column is NULL completely

MySQLtree

For the problem I have a single table which store a Member's ID and His Referee's ID. This is something like a Multi-Level-Marketing plan where you join a company for some tasks and then someone join from your reference and appear under your downline and so on and so forth. The scheme I am using is not necessarily a binary tree, there can be many users under a single user.

I want to retrieve the entire tree under a specific user, I am using below query to retrieve the records but this is not the solution I want.

SELECT t1.user AS lvl1, t2.user AS lvl2, t3.user AS lvl3,
       t4.user AS lvl4, t5.user AS lvl5
FROM reference t1  
LEFT JOIN reference t2 ON t2.referee = t1.user  
LEFT JOIN reference t3 ON t3.referee = t2.user  
LEFT JOIN reference t4 ON t4.referee = t3.user  
LEFT JOIN reference t5 ON t5.referee = t4.user  
WHERE t1.referee = 1

This query will get me the tree structure under user 1 but only 5 level deep.

Now I want to retrieve the entire tree upto last level but cant figure out a way for same. Tree depth can be anything depending on the users referrals so I cannot even guess the depth (That wont make sense anyway).

All I want right now is to perform the JOIN and keep watching the selected column (in our case user) from last JOIN to check if all the values in it are NULL. If the column from last JOIN is NULL then it means the tree is completed and query should return the result.

Can anyone suggest a workaround?
I can make changes in the table structure if necessary but that should not effect the behavior of other operations.

Best Answer

Although MySQL has no CTE functionality, there are two major ways to create CTE expressions:

TECHNIQUE #1 : Write Stored Procedures to Traverse Recursively

Rather than Reinventing the Wheel, please see my past posts on how to make stored procedures

Oct 24, 2011 : Find highest level of a hierarchical field: with vs without CTEs
Oct 26, 2012 : Hierarchical queries without CTEs

TECHNIQUE #2 : Iterate Based on the Tree's Maximum Depth

First, here is some sample data

DROP DATABASE IF EXISTS dufran;
CREATE DATABASE dufran;
USE dufran;
CREATE TABLE reference 
(
    user INT NOT NULL AUTO_INCREMENT,
    referee INT NOT NULL DEFAULT 0,
    name VARCHAR(20) NOT NULL,
    PRIMARY KEY (user)
);
INSERT INTO reference (name,referee) VALUES ('Rolando',0);
INSERT INTO reference (name,referee) VALUES ('Pamela',1);
INSERT INTO reference (name,referee) VALUES ('Carlik',2);
INSERT INTO reference (name,referee) VALUES ('Javonne',2);
INSERT INTO reference (name,referee) VALUES ('Dominique',2);
INSERT INTO reference (name,referee) VALUES ('Diamond',2);
INSERT INTO reference (name,referee) VALUES ('Azalia',3);

When loaded, this is the data

mysql> SELECT * FROM reference;
+------+---------+-----------+
| user | referee | name      |
+------+---------+-----------+
|    1 |       0 | Rolando   |
|    2 |       1 | Pamela    |
|    3 |       2 | Carlik    |
|    4 |       2 | Javonne   |
|    5 |       2 | Dominique |
|    6 |       2 | Diamond   |
|    7 |       3 | Azalia    |
+------+---------+-----------+
7 rows in set (0.00 sec)

mysql>

Here is how you compute the maximum depth

SET @depth = 0;
SELECT MAX(@depth:=@depth+1) max_depth FROM
(SELECT DISTINCT referee FROM reference) A;

Here is the maximum depth for the sample data

mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT MAX(@depth:=@depth+1) max_depth FROM
    -> (SELECT DISTINCT referee FROM reference) A;
+-----------+
| max_depth |
+-----------+
|         4 |
+-----------+
1 row in set (0.00 sec)

mysql>

Using this principle, iterate for the SELECT columns and the LEFT JOIN clauses

SET @depth = 0;
SELECT GROUP_CONCAT(CONCAT('t',dep,'.user AS lvl',dep))
INTO @sqllist FROM
(SELECT @depth:=@depth+1 dep FROM
(SELECT DISTINCT referee FROM reference) AA) A;
SET @depth1 = 0;
SET @depth2 = 1;
SELECT GROUP_CONCAT(sqljoin SEPARATOR ' ') INTO @sqljoins
FROM (SELECT CONCAT('LEFT JOIN reference t',@depth2:=@depth2+1,
' ON t',@depth2,'.referee = t',@depth1:=@depth1+1,'.user') sqljoin
FROM (SELECT DISTINCT referee FROM reference) AA) A;
SELECT @sqljoins;
SET @sqlstmt = CONCAT('SELECT ',@sqllist,
' FROM reference t1 ',@sqljoins);
SELECT @sqllist\G
SELECT @sqljoins\G
SELECT @sqlstmt\G

Here is the SQL generated

mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT GROUP_CONCAT(CONCAT('t',dep,'.user AS lvl',dep))
    -> INTO @sqllist FROM
    -> (SELECT @depth:=@depth+1 dep FROM
    -> (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)

mysql> SET @depth1 = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @depth2 = 1;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT GROUP_CONCAT(sqljoin SEPARATOR ' ') INTO @sqljoins
    -> FROM (SELECT CONCAT('LEFT JOIN reference t',@depth2:=@depth2+1,
    -> ' ON t',@depth2,'.referee = t',@depth1:=@depth1+1,'.user') sqljoin
    -> FROM (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)

mysql>     SELECT @sqllist\G
*************************** 1. row ***************************
@sqllist: t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4
1 row in set (0.00 sec)

mysql>     SELECT @sqljoins\G
*************************** 1. row ***************************
@sqljoins: LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user
1 row in set (0.00 sec)

mysql>     SELECT @sqlstmt\G
*************************** 1. row ***************************
@sqlstmt: SELECT t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4 FROM reference t1 LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user
1 row in set (0.00 sec)

mysql>

Here is the big question, does the SQL work ??? Take the SQL and run it dynamically:

PREPARE s FROM @sqlstmt;
EXECUTE s;
DEALLOCATE PREPARE s;

Here is the result:

mysql> PREPARE s FROM @sqlstmt;
Query OK, 0 rows affected (0.00 sec)
Statement prepared

mysql> EXECUTE s;
+------+------+------+------+
| lvl1 | lvl2 | lvl3 | lvl4 |
+------+------+------+------+
|    1 |    2 |    3 |    7 |
|    1 |    2 |    4 | NULL |
|    1 |    2 |    5 | NULL |
|    1 |    2 |    6 | NULL |
|    2 |    3 |    7 | NULL |
|    2 |    4 | NULL | NULL |
|    2 |    5 | NULL | NULL |
|    2 |    6 | NULL | NULL |
|    3 |    7 | NULL | NULL |
|    4 | NULL | NULL | NULL |
|    5 | NULL | NULL | NULL |
|    6 | NULL | NULL | NULL |
|    7 | NULL | NULL | NULL |
+------+------+------+------+
13 rows in set (0.03 sec)

mysql> DEALLOCATE PREPARE s;
Query OK, 0 rows affected (0.00 sec)

mysql>

I scripted this to give you a starting point and some homework. Here is what I mean: You probably don't want to see NULL columns. You could do one of two things:

Convert each NULL to IFNULL(lvl1,''), GROUP_CONCAT all columns.
Compute the depth of a particular id and gather columns for it only.

Give it a Try !!!

UPDATE 2016-06-14 16:36 EDT

Someone just commented

Your max depth calculation is wrong. Proof: Add to your sample data: INSERT INTO reference (name,referee) VALUES ('Maria',4);

Let's try it out

mysql> INSERT INTO reference (name,referee) VALUES ('Maria',4);
Query OK, 1 row affected (0.00 sec)

mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT MAX(@depth:=@depth+1) max_depth FROM
    -> (SELECT DISTINCT referee FROM reference) A;
+-----------+
| max_depth |
+-----------+
|         5 |
+-----------+
1 row in set (0.00 sec)

OK, it says the depth is 5. Is there visible proof of this ?

mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT GROUP_CONCAT(CONCAT('t',dep,'.user AS lvl',dep))
    -> INTO @sqllist FROM
    -> (SELECT @depth:=@depth+1 dep FROM
    -> (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)

mysql> SET @depth1 = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @depth2 = 1;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT GROUP_CONCAT(sqljoin SEPARATOR ' ') INTO @sqljoins
    -> FROM (SELECT CONCAT('LEFT JOIN reference t',@depth2:=@depth2+1,
    -> ' ON t',@depth2,'.referee = t',@depth1:=@depth1+1,'.user') sqljoin
    -> FROM (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)

mysql> SELECT @sqljoins;
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| @sqljoins                                                                                                                                                                                                                                  |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user LEFT JOIN reference t6 ON t6.referee = t5.user |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> SET @sqlstmt = CONCAT('SELECT ',@sqllist,
    -> ' FROM reference t1 ',@sqljoins);
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT @sqllist\G
*************************** 1. row ***************************
@sqllist: t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4,t5.user AS lvl5
1 row in set (0.00 sec)

mysql> SELECT @sqljoins\G
*************************** 1. row ***************************
@sqljoins: LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user LEFT JOIN reference t6 ON t6.referee = t5.user
1 row in set (0.00 sec)

mysql> SELECT @sqlstmt\G
*************************** 1. row ***************************
@sqlstmt: SELECT t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4,t5.user AS lvl5 FROM reference t1 LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user LEFT JOIN reference t6 ON t6.referee = t5.user
1 row in set (0.00 sec)

mysql> PREPARE s FROM @sqlstmt;
Query OK, 0 rows affected (0.00 sec)
Statement prepared

Guess what the output says ?

mysql> EXECUTE s;
+------+------+------+------+------+
| lvl1 | lvl2 | lvl3 | lvl4 | lvl5 |
+------+------+------+------+------+
|    1 |    2 |    3 |    7 | NULL |
|    1 |    2 |    4 |    8 | NULL |
|    1 |    2 |    5 | NULL | NULL |
|    1 |    2 |    6 | NULL | NULL |
|    2 |    3 |    7 | NULL | NULL |
|    2 |    4 |    8 | NULL | NULL |
|    2 |    5 | NULL | NULL | NULL |
|    2 |    6 | NULL | NULL | NULL |
|    3 |    7 | NULL | NULL | NULL |
|    4 |    8 | NULL | NULL | NULL |
|    5 | NULL | NULL | NULL | NULL |
|    6 | NULL | NULL | NULL | NULL |
|    7 | NULL | NULL | NULL | NULL |
|    8 | NULL | NULL | NULL | NULL |
+------+------+------+------+------+
14 rows in set (0.00 sec)

mysql> DEALLOCATE PREPARE s;
Query OK, 0 rows affected (0.00 sec)

mysql>

Just as my code predicted. The depth is 5 and the Dynamic SQL just proved it.

Related Solutions

Mysql – get column from too many tables in thesql

If all the tables use the MyISAM Storage Engine and have the same table structure, I have some good news for you.

You can create a single table that consumes no additional space except a .frm file and some mapping info. The key is to take advantage of the MERGE (MRG_MyISAM) Storage Engine.

Here is how you can do this:

CREATE TABLE XMerge LIKE X1;
ALTER TABLE XMerge ENGINE=MRG_MYISAM
UNION=(X1,X2,X3,X4) INSERT_METHOD=LAST;

Using this method, you can query the 4 tables at the same time like this:

SELECT ReqF FROM XMerge WHERE EmpName='John';

Was that simple, or what ???

In your case, you have 75 tables. You would do this:

CREATE TABLE XMerge LIKE X1;
ALTER TABLE XMerge ENGINE=MRG_MYISAM
UNION=(X1,X2,X3,X4,X5,X6,X7,X8,X9,
X10,X11,X12,X13,X14,X15,X16,X17,X18,X19,
X20,X21,X22,X23,X24,X25,X26,X27,X28,X29,
X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,
X40,X41,X42,X43,X44,X45,X46,X47,X48,X49,
X50,X51,X52,X53,X54,X55,X56,X57,X58,X59,
X60,X61,X62,X63,X64,X65,X66,X67,X68,X69,
X70,X71,X72,X73,X74,X75) INSERT_METHOD=LAST;
SELECT ReqF FROM XMerge WHERE EmpName='John';

The beauty of this is that creating a MERGE table takes milliseconds. Just make sure every table has an index on EmpName. Better to do 75 indexed lookups that 75 full table scans. If there is no index on EmpName, you need to do this:

ALTER TABLE X1 ADD UNIQUE KEY (EmpName);
ALTER TABLE X2 ADD UNIQUE KEY (EmpName);
.
.
.
ALTER TABLE X75 ADD UNIQUE KEY (EmpName);
CREATE TABLE XMerge LIKE X1;
ALTER TABLE XMerge ENGINE=MRG_MYISAM
UNION=(X1,X2,X3,X4,X5,X6,X7,X8,X9,
X10,X11,X12,X13,X14,X15,X16,X17,X18,X19,
X20,X21,X22,X23,X24,X25,X26,X27,X28,X29,
X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,
X40,X41,X42,X43,X44,X45,X46,X47,X48,X49,
X50,X51,X52,X53,X54,X55,X56,X57,X58,X59,
X60,X61,X62,X63,X64,X65,X66,X67,X68,X69,
X70,X71,X72,X73,X74,X75) INSERT_METHOD=LAST;
SELECT ReqF FROM XMerge WHERE EmpName='John';

Give it a Try !!!

PostgreSQL tree structure and recursive CTE optimization

If you really have to modify these data rarely, then you can simply store the result of the CTE in a table, and run queries against this table. You can define indexes based on your typical queries.
Then TRUNCATE and repopulate (and ANALYZE) as necessary.

On the other hand, if you can put the CTE in separate stored procedures rather than a view, you can easily put your conditions in the CTE part rather then the final SELECT (which is basically what you do querying against tree_view_1), so that much less rows will be involved in the recursion. From the query plan it looks like that PostgreSQL estimates row numbers based on some far-from-true assumptions, probably producing suboptimal plans - this effect can be reduced somewhat with the SP solution.

EDIT I may miss something, but just noticed that in the non-recursive term you don't filter the rows. Possibly you want to include only root nodes there (WHERE parent_id IS NULL) - I'd expect much less rows and recursions this way.

EDIT 2 AS it slowly became clear for me from the comments, I misthought the recursion in the original question going the other way. Here I mean starting from the root nodes and going deeper in the recursion.