mysql - MySQL同表递归查询

Question

我有以下数据结构:

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

如何计算从给定父亲生出的 child 的数量，例如:在上面的情况下，X是Y的父亲(Y的生成者是X)，而Y是Z的父亲。因此我恳请得到以下结果表:

 Order_id  | Count_of_children
    X      | 2 
    A      | 1

Answer 1

以下递归查询将连接每个根节点及其所有后代:

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

现在您只需要按组计算行数，忽略根节点:

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

在 MySQL 8.0 之前，无法编写递归查询。如果表不是太大，简单的方法是获取所有行并在应用程序代码中使用递归函数对子树节点进行计数。不幸的是 MySQL 也不支持递归函数。如果你想在 MySQL 中解决这个问题，你需要找到一种迭代算法，你可以在函数中使用它。这是一种方法，使用 JSON 数组作为队列，以 JSON 数组的形式返回节点的所有后代。伪代码如下:

• 初始化空结果数组
• 初始化一个空队列
• 将根节点添加到队列
• 虽然 que 不为空
  • 获取第一个队列元素的所有子元素并将它们附加到队列
  • 将第一个队列元素添加到结果数组
  • 从队列中删除第一个元素
• 从结果数组中删除第一个元素(因为它是根节点)
• 返回结果数组

这里是实现:

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 ;

您可以使用该函数:

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

结果:

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

View on DB Fiddle

要获取计数，您可以使用 JSON_LENGTH() 函数:

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

结果:

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

View on DB Fiddle