计算同一 table 中的后代数

Question

我有 table 个带有 ID 的 object 个，其中一些是基于其他 object 个。
为此，我使用了一个名为路径的字段，其中列出了 parents' ID

的字符串

ObjectD(path="A,B,C")是基于objectC是基于B是基于A.

现在我想 select * 来自所有 objects，加上一个额外的列：count(descendants)
(A 有 3 个 (B,C 和 D) B 有 2 个 (C 和 D) 而 C 只有一个 (D) - D 有 0

"my"个后代是路径=myPath+myID(+more?)
的object个数 - 这是否仅在 SQL 中可行（不在 PHP 中循环）？

O id=a .... path="" ....... a 有 5 个后代
O id=b .... path="a" ....... b 有3
O id=c .... path="a,b" ..... c 有 1
O id=d .... path="a,b,c" .. d 有 0
O id=n .... path="a,b" ..... n有0
O id=x .... path="a" ....... x 有 0

Answer 1

这个table结构如果需要经常查询的话很可能会出问题。很少建议在单个列中存储多个值，尽管 MySQL 有一种基本的读取方法。

不过鉴于您现有的要求，查询结果并不难产生您想要的结果。使用 LEFT JOIN 将 table 与自身加入不同的别名，您可以使用 MySQL 的 FIND_IN_SET() string function 来定位object里面的path作为加入条件。

加入后，您可以 COUNT() 来自 FIND_IN_SET() 的匹配项，并且由于您使用了 LEFT JOIN，它将 return 0没有后代。

SELECT
  o.*,
  -- Count matches from the joined table
  COUNT(odesc.object) AS num_descendants
FROM
  paths o
  -- Self join with FIND_IN_SET()
  LEFT JOIN paths odesc ON FIND_IN_SET(o.object, odesc.path)
GROUP BY o.object

给定您的样本行，这里有一个演示，如果它工作并产生您预期的结果。 http://sqlfiddle.com/#!9/1fae7/1

现在，如果您的数据不像您的样本那样规则，那可能仍然允许不完全遵循的路径，而只是将对象作为成员。添加额外的 LIKE 条件可以强制 LEFT JOIN 两侧的路径以相同的方式开始，这意味着一条路径延伸另一条路径。

 LEFT JOIN paths odesc ON
   FIND_IN_SET(o.object, odesc.path)
   -- Additional condition to ensure paths start the same
   AND odesc.path LIKE CONCAT(COALESCE(o.path, ''), '%')

为了验证结果是否相同，http://sqlfiddle.com/#!9/1fae7/15

请注意，使用 FIND_IN_SET() 永远不会很快。这就是困难所在——MySQL 没有很好的拆分字符串的本机功能，并且不能很好地利用索引。

附录：

I 运行 EXPLAIN 针对 FIND_IN_SET() 查询，两列各有一个索引：

+------+-------------+-------+-------+---------------+------+---------+------+------+--------------------------------------------------------------+
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                                        |
+------+-------------+-------+-------+---------------+------+---------+------+------+--------------------------------------------------------------+
|    1 | SIMPLE      | o     | index | NULL          | path | 20      | NULL |    6 | Using index; Using temporary; Using filesort                 |
|    1 | SIMPLE      | ox    | index | NULL          | path | 20      | NULL |    6 | Using where; Using index; Using join buffer (flat, BNL join) |
+------+-------------+-------+-------+---------------+------+---------+------+------+--------------------------------------------------------------+

这是在更正源数据以使用尾随逗号和空字符串而不是 NULL:

之后，来自评论的依赖子查询的解释

EXPLAIN select    paths.*,   (select count(object)     from paths ox    where LEFT(ox.path,char_length( concat( paths.path, paths.object))) = concat(paths.path, paths.object ) )as descendants from paths;
+------+--------------------+-------+-------+---------------+------+---------+------+------+--------------------------+
| id   | select_type        | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                    |
+------+--------------------+-------+-------+---------------+------+---------+------+------+--------------------------+
|    1 | PRIMARY            | paths | index | NULL          | path | 20      | NULL |    6 | Using index              |
|    2 | DEPENDENT SUBQUERY | ox    | index | NULL          | path | 20      | NULL |    6 | Using where; Using index |
+------+--------------------+-------+-------+---------------+------+---------+------+------+--------------------------+

最后，用subselect修改后的数据表示为LEFT JOIN，MySQL可能更能优化：

EXPLAIN SELECT
   paths.*,
   COUNT(ox.object)
FROM
  paths
  LEFT JOIN paths ox
     ON LEFT(ox.path,char_length(concat(paths.path, paths.object))) = concat(paths.path, paths.object)
GROUP BY paths.object;

+------+-------------+-------+-------+---------------+------+---------+------+------+--------------------------------------------------------------+
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                                        |
+------+-------------+-------+-------+---------------+------+---------+------+------+--------------------------------------------------------------+
|    1 | SIMPLE      | paths | index | NULL          | path | 20      | NULL |    6 | Using index; Using temporary; Using filesort                 |
|    1 | SIMPLE      | ox    | index | NULL          | path | 20      | NULL |    6 | Using where; Using index; Using join buffer (flat, BNL join) |
+------+-------------+-------+-------+---------------+------+---------+------+------+--------------------------------------------------------------+

这三个似乎都可以使用索引，但您需要将它们与真实的行集进行对比，以找出最有效的索引。重要的是，这些是运行针对最近的 MariaDB 版本。如果您的年龄较大 MySQL，您的结果可能会有很大差异。

我发现修改原始数据以满足尾随逗号的要求有点令人反感。

Answer 2

我假设您有一个 table，id 列为 keyy，parents 为 parents。我还假设 parents 列中的每个 parent 都以“,”结尾。那么：

select t.*, 
      (select count(*) 
       from t tt 
       where tt.parents between concat( t.parents , t.keyy ,',' )
         and  concat(t.parents , t.keyy ,',zzzzzzzzzz' ) )as descendants
    from t

如果您在 parents 列上有索引，则可以使用它。也许你应该把 zz 换成更合理的东西。

参见： http://sqlfiddle.com/#!9/a2d5e/1

计算同一 table 中的后代数

Count number of descendants in the same table

php

mysql

sql

inner-join

附录：