MySQL Multilevel Heirarchy List

Question

I'm making a list of users with their referred users, with unknown levels deep.

What I did for now is to take three levels deep using:

  SELECT 
  *
  FROM (
        SELECT 
            d1.id AS d1_id, d2.id AS d2_id, d3.id AS d3_id
        FROM users AS d1
        LEFT JOIN users AS d2 ON d2.referral_id = d1.id
        LEFT JOIN users AS d3 ON d3.referral_id = d2.id
        WHERE d1.agent_id = 12
    ) AS ut

Which results to:

+-------+-------+-------+
| d1_id | d2_id | d3_id |
+-------+-------+-------+
| 12    | 4     | NULL  |
+-------+-------+-------+
| 12    | 9     | NULL  |
+-------+-------+-------+
| 12    | 10    | NULL  |
+-------+-------+-------+
| 12    | 18    | 20    |
+-------+-------+-------+
| 12    | 18    | 21    |
+-------+-------+-------+
| 12    | 18    | 23    |
+-------+-------+-------+
| 12    | 18    | 26    |
+-------+-------+-------+
| 12    | 19    | 22    |
+-------+-------+-------+
| 16    | 13    | NULL  |
+-------+-------+-------+
| 16    | 17    | NULL  |
+-------+-------+-------+

Now I need to get all the subs of all D1 using JSON_OBJECT:

  SELECT 
  JSON_OBJECT('id', ut.d1_id, 'members', JSON_ARRAYAGG(JSON_OBJECT('id', ut.d2_id))) AS tree
  FROM (
        SELECT 
            d1.id AS d1_id, d2.id AS d2_id, d3.id AS d3_id
        FROM users AS d1
        LEFT JOIN users AS d2 ON d2.referral_id = d1.id
        LEFT JOIN users AS d3 ON d3.referral_id = d2.id
        WHERE d1.agent_id = 12
    ) AS ut
    GROUP BY ut.d1_id

Resulting to

+-----------------------------------------------------------------------------------------------------------------------+
| tree                                                                                                                  |
+-----------------------------------------------------------------------------------------------------------------------+
| {"id": 12, "members": [{"id": 4}, {"id": 9}, {"id": 10}, {"id": 18}, {"id": 18}, {"id": 18}, {"id": 18}, {"id": 19}]} |
+-----------------------------------------------------------------------------------------------------------------------+
| {"id": 16, "members": [{"id": 13}, {"id": 17}]}                                                                       |
+-----------------------------------------------------------------------------------------------------------------------+

But the problem with this is I cannot get the d3 users.

Expected output:

{"id": 16, "members" : [{"id": 13, members: {...}}, {"id": 17, members: {...}}]} }

My MySQL version is 8.0.21-0ubuntu0.20.04.4

PS. I've read about this but I can't/don't know how to apply it in my scenario.

Create a query which combines levels 1 and 2. Use it as subquery in a query which combines level 0 and combined level 1&2. — Akina, Sep 01 '20 at 17:38
@Akina that would be possible if only there 3 levels. But the OP was hoping to get a query that would do with unknown levels deep. — Karma Blackshaw, Sep 01 '20 at 17:41
@KarmaBlackshaw For multi-level tree with indefinite depth - build full tree from the root to the lives with level info in one recursive CTE, then move from leaves to root in another CTE combining current level node with the object combined in previous iterations. I.e. the same practically. — Akina, Sep 01 '20 at 18:55

score 0 · Answer 1 · answered Sep 02 '20 at 17:14

Maybe you might solve the issue using a CTE recursive query something like:

WITH RECURSIVE table_cte AS
(SELECT user_id , 1 as n FROM users 
UNION ALL
SELECT user_id , n + 1 FROM table_cte tc
INNER JOIN users u
ON ct.id = u.id
WHERE n <= max_depth) # Max deph allowed | optional
SELECT * FROM table_cte;

In the anchor member (query) you may place as many fields as necessary as far as you place them also in the recursive query part. It is also convinient to place a termination condition in the WHERE clause of the recursive query to avoid results to deep. You may achieve this effect by placing a counter in the anchor member. See https://www.mysqltutorial.org/mysql-recursive-cte/

score 0 · Answer 2 · answered Sep 04 '20 at 06:32

Currently you're using an Adjacency List pattern, where each row has a foreign key to its parent on the same table. This is an easy pattern to create and maintain however as you've found the as the query depth increases querying the data becomes more complex. When using an Adjacency List the only real solution as @Erick points out is recursive querying (or only supporting n levels of depth).

I'm going to suggest another pattern, adding a closure table. A closure table has 2 foreign keys to users.user_id, ancestor and descendant.

CREATE TABLE referrals(
    ancestor INT NOT NULL,
    descendant INT NOT NULL,
    PRIMARY KEY (ancestor, descendant),
    FOREIGN KEY (ancestor) REFERENCES users(id),
    FOREIGN KEY (descendant) REFERENCES users(id)
);

Each user will have a self referencing record, and a record with everyone above them as the ancestor and them as the descendant. In you case this might be a little cumbersome to populate initially (since you already have data). Adding new records is easy, you insert a self referencing record, then a insert all records where the referrer is the descendant and but with the new user as the descendant. having a structure like this makes queries like you're much easier to write.

SELECT descendant AS id
FROM referrals
WHERE ancestor = 12

Here is a fiddle I made that shows how to make and use a Closure table.

MySQL Multilevel Heirarchy List

2 Answers2