Recursive query on same table MySQL

Question

I have the below data structure :

Order_id  |  Generated by | Order_type
X         |  NULL         | Subscription
Y         |  X            | Auto_renewal
Z         |  Y            | Auto_renewal
A         |  NULL         | Subscription
B         |  A            | Auto_renewal

How can I count the number of children sprung from a given father, e.g: In the above case, X is the father of Y (Y's generated by is X), and Y is the father of Z. Hence I kindly wish to have the following result table :

 Order_id  | Count_of_children
    X      | 2 
    A      | 1

Answer 1

The following recursive query will connect every root node with all their descendants:

with recursive rcte as (
  select Order_id as root, Order_id as node
  from mytable
  where Generated_by is null
  union all
  select r.root, t.Order_id
  from rcte r
  join mytable t on t.Generated_by = r.node
)
select * from rcte;

| root | node |
| ---- | ---- |
| X    | X    |
| A    | A    |
| X    | Y    |
| A    | B    |
| X    | Z    |

View on DB Fiddle

Now you just need to count the rows groupwise ignoring the root nodes:

with recursive rcte as (
  ...
)
select root as Order_id, count(*) as Count_of_children
from rcte
where node <> root
group by root;

| Order_id | Count_of_children |
| -------- | ----------------- |
| X        | 2                 |
| A        | 1                 |

View on DB Fiddle

Before MySQL 8.0 there was no way to write recursive queries. If the table is not too big, the simple way would be to fetch all rows and count the subtree nodes with a recursive function in application code. Unfortunately MySQL neither supports recursive functions. If you want to solve that within MySQL, you will need to find an iterative algorithm, which you can use in a function. Here is one way, which is using a JSON array as queue to return all descendants of a node as a JSON array. The pseudo code is like:

• Initialize the empty result array
• Initialize an empty queue
• Add the root node to queue
• While que is not empty
  • Get all children of the first queue element and apend them to the queue
  • Add the first queue element to to the result array
  • Remove the first element from the queue
• Remove the first element from the result array (since it's tzhe root node)
• Return the result array

Here is the implementation:

delimiter //

create function get_descendants(in_order_id varchar(50)) returns json
begin 
  declare descendants json;
  declare queue json;
  declare node varchar(50);

  set descendants = json_array();
  set queue = json_array(in_order_id);

  while json_length(queue) > 0 do
    set queue = json_merge(queue, coalesce((
      select json_arrayagg(Order_id)
      from mytable
      where Generated_by = queue->'$[0]'
    ), json_array()));    
    set descendants = json_array_append(descendants, '$', queue->'$[0]');
    set queue = json_remove(queue, '$[0]');
  end while;

  set descendants = json_remove(descendants, '$[0]');
  return descendants;
end //

delimiter ;

You can the use the function with:

select Order_id, get_descendants(Order_id) as descendants
from mytable
where Generated_by is null;

Result:

| Order_id | descendants |
| -------- | ----------- |
| A        | ["B"]       |
| X        | ["Y", "Z"]  |

View on DB Fiddle

To get the count, you can use the JSON_LENGTH() function:

select Order_id, json_length(get_descendants(Order_id)) as descendant_count
from mytable
where Generated_by is null;

Result:

| Order_id | descendant_count |
| -------- | ---------------- |
| A        | 1                |
| X        | 2                |

View on DB Fiddle