树形结构中的递归求和

Question

我有一张单表格的树形结构。该表格是一个类别树，可以无限嵌套。每个类别都有一个ProductCount列，用于显示直接在该类别中拥有多少个产品（不包括子类别）。

Id  | ParentId | Name      | ProductCount
------------------------------------
1   | -1       | Cars      | 0
2   | -1       | Bikes     | 1
3   | 1        | Ford      | 10
4   | 3        | Mustang   | 7
5   | 3        | Focus     | 4

我想创建一个 SQL 查询，对于每行/类别，它可以给出包括子类别中的产品数量。

上表的输出应为：

Id  | ParentId | Name      | ProductCount | ProductCountIncludingChildren
--------------------------------------------------------------------------
1   | -1       | Cars      | 0            | 21
2   | -1       | Bikes     | 1            | 1
3   | 1        | Ford      | 10           | 21
4   | 3        | Mustang   | 7            | 7
5   | 3        | Focus     | 4            | 4

我知道我可能应该使用CTE，但却不能使它像应该的那样正常工作。

非常感谢任何帮助！

- Rasmus

---

你目前尝试了什么？发表你的问题... - Jesuraja

尝试使用CTE，但无法正确求和。 - Rasmus

Answer 1

您可以使用递归CTE，其中在锚定部分获取所有行，在递归部分加入以获取子行。请记住来自锚定部分的原始Id别名为RootID，并在主查询中按RootID进行分组的总和聚合。

SQL Fiddle

MS SQL Server 2012 Schema Setup:

create table T
(
  Id int primary key,
  ParentId int,
  Name varchar(10),
  ProductCount int
);

insert into T values
(1, -1, 'Cars',    0),
(2, -1, 'Bikes',   1),
(3,  1, 'Ford',    10),
(4,  3, 'Mustang', 7),
(5,  3, 'Focus',   4);

create index IX_T_ParentID on T(ParentID) include(ProductCount, Id);

查询1:

with C as
(
  select T.Id,
         T.ProductCount,
         T.Id as RootID
  from T
  union all
  select T.Id,
         T.ProductCount,
         C.RootID
  from T
    inner join C 
      on T.ParentId = C.Id
)
select T.Id,
       T.ParentId,
       T.Name,
       T.ProductCount,
       S.ProductCountIncludingChildren
from T
  inner join (
             select RootID,
                    sum(ProductCount) as ProductCountIncludingChildren
             from C
             group by RootID
             ) as S
    on T.Id = S.RootID
order by T.Id
option (maxrecursion 0)

Results:

| ID | PARENTID |    NAME | PRODUCTCOUNT | PRODUCTCOUNTINCLUDINGCHILDREN |
|----|----------|---------|--------------|-------------------------------|
|  1 |       -1 |    Cars |            0 |                            21 |
|  2 |       -1 |   Bikes |            1 |                             1 |
|  3 |        1 |    Ford |           10 |                            21 |
|  4 |        3 | Mustang |            7 |                             7 |
|  5 |        3 |   Focus |            4 |                             4 |

- Mikael Eriksson

---

这个递归CTE的可扩展性非常差，因为它实际上将叶值复制到所有父级、直接和更高层次的树中（例如，将Mustang的ProductCount复制到Ford和Cars中的每一个）。我在大约200个数据集上尝试了一下，CTE结果集膨胀到了大约10万行，需要大约半分钟的时间。 - Elaskanator

@Elaskanator 谢谢你的尝试，我想做类似的事情，大约有三百万个集合。一想到我的CTE结果集就会起鸡皮疙瘩。 - Moons

Answer 2

这与Tom的回答是相同的概念，但代码更少（而且速度更快）。

with cte as
(
  select v.Id, v.ParentId, v.Name, v.ProductCount, 
  cast('/' + cast(v.Id as varchar) + '/' as varchar) Node
  from Vehicle v
  where ParentId = -1
  union all
  select v.Id, v.ParentId, v.Name, v.ProductCount,  
  cast(c.Node + CAST(v.Id as varchar) + '/' as varchar)
  from Vehicle v
  join cte c on v.ParentId = c.Id
)

select c1.Id, c1.ParentId, c1.Name, c1.ProductCount, 
c1.ProductCount + SUM(isnull(c2.ProductCount, 0)) ProductCountIncludingChildren
from cte c1
left outer join cte c2 on c1.Node <> c2.Node and left(c2.Node, LEN(c1.Node)) = c1.Node
group by c1.Id, c1.ParentId, c1.Name, c1.ProductCount
order by c1.Id

SQL Fiddle是一个用于测试的在线工具，这里添加了一些额外的数据行进行测试。

- Jerrad

---

当转换为 varchar 时，如果没有指定字符串长度，则会得到默认的30个字符。这可能足够了，但我认为最好明确指定要使用的字符串长度。 - Mikael Eriksson

没错。我不知道他的实际数据长什么样，所以我没有关注那些细节。 - Jerrad

他确实说过：“表格是一个可以无限嵌套的类别树。”当然，这并不是字面上的真相，但它可能会使树变得非常深。 - Mikael Eriksson

我承认这不是一个理想的解决方案。你的答案到目前为止是最好的。 - Jerrad

Answer 3

实际上，这可以是 SQL Server 中 HIERARCHYID 的一个很好的用法。

CREATE TABLE [dbo].[CategoryTree]
(
    [Id] INT,
    [ParentId] INT,
    [Name] VARCHAR(100),
    [ProductCount] INT
)
GO

INSERT [dbo].[CategoryTree]
VALUES
    (1, -1, 'Cars', 0),
    (2, -1, 'Bikes', 1),
    (3, 1, 'Ford', 10),
    (4, 3, 'Mustang', 7),
    (5, 3, 'Focus', 4)
    --,(6, 1, 'BMW', 100)
GO

查询。

WITH [cteRN] AS (
    SELECT *,
        ROW_NUMBER() OVER (
            PARTITION BY [ParentId] ORDER BY [ParentId]) AS [ROW_NUMBER]
    FROM  [dbo].[CategoryTree]
),
[cteHierarchy] AS (
    SELECT CAST(
            CAST(hierarchyid::GetRoot() AS VARCHAR(100))
            + CAST([ROW_NUMBER] AS VARCHAR(100))
            + '/' AS HIERARCHYID
        ) AS [Node],
        *
    FROM [cteRN]
    WHERE [ParentId] = -1
    UNION ALL
    SELECT CAST(
            hierarchy.Node.ToString()
            + CAST(RN.[ROW_NUMBER] AS VARCHAR(100)
        ) + '/' AS HIERARCHYID),
        rn.*
    FROM [cteRN] rn
    INNER JOIN [cteHierarchy] hierarchy
        ON rn.[ParentId] = hierarchy.[Id]
)
SELECT x.[Node].ToString() AS [Node],
    x.[Id], x.[ParentId], x.[Name], x.[ProductCount],
    x.[ProductCount] + SUM(ISNULL(child.[ProductCount],0))
        AS [ProductCountIncludingChildren]
FROM [cteHierarchy] x
LEFT JOIN [cteHierarchy] child
    ON child.[Node].IsDescendantOf(x.[Node]) = 1
    AND child.[Node] <> x.[Node]
GROUP BY x.[Node], x.[Id], x.[ParentId], x.[Name], x.[ProductCount]
ORDER BY x.[Id]

结果。

- Tom Hunter

---

请注意，大部分查询只是关于设置HierarchyId“Node”列。如果您可以使用HierarchyId列存储数据，则最终查询应该非常快速。 - Tom Hunter

对于这篇文章中的实际问题，上面的解决方案同样有效且更简单，但使用HierarchyId允许您按级别求和，我认为这更好。 - Seb

Answer 4

这不是最优解，但它可以工作，但需要使用两个CTE。一个主要的CTE和一个在表值函数中的CTE来汇总每个子树的值。

第一个CTE

;WITH cte 
AS 
(
SELECT 
   anchor.Id,
   anchor.ParentId,
   anchor.Name,
   anchor.ProductCount,
   s.Total AS ProductCountIncludingChildren
FROM
testTable anchor 
    CROSS APPLY SumChild(anchor.id) s
WHERE anchor.parentid = -1
UNION ALL
SELECT 
   child.Id,
   child.ParentId,
   child.Name,
   child.ProductCount,
   s.Total AS ProductCountIncludingChildren
  FROM
cte 
  INNER JOIN testTable child on child.parentid = cte.id
  CROSS APPLY SumChild(child.id) s
 )
 SELECT * from cte 

而且这个函数

CREATE FUNCTION SumChild 
(
@id int

)
RETURNS TABLE
AS
 RETURN  
 (
 WITH cte 
 AS 
 (
   SELECT 
     anchor.Id,
     anchor.ParentId,
     anchor.ProductCount
   FROM
      testTable anchor 
   WHERE anchor.id = @id 
   UNION ALL
SELECT 
      child.Id,
      child.ParentId,
      child.ProductCount
    FROM
   cte 
     INNER JOIN testTable child on child.parentid = cte.id
)
SELECT SUM(ProductCount) AS Total from CTE
 )
GO

这将导致：

从源表中

对于格式问题，我们深表歉意。

- brumScouse

Answer 5

我想不出一个好的基于T-SQL的集合答案，但我想出了一个答案：临时表模拟了您的表结构。表变量是一个工作表。

--Initial table
CREATE TABLE #products (Id INT, ParentId INT, NAME VARCHAR(255), ProductCount INT)
INSERT INTO #products
        ( ID,ParentId, NAME, ProductCount )
VALUES  ( 1,-1,'Cars',0),(2,-1,'Bikes',1),(3,1,'Ford',10),(4,3,'Mustang',7),(5,3,'Focus',4)

--Work table
DECLARE @products TABLE (ID INT, ParentId INT, NAME VARCHAR(255), ProductCount INT, ProductCountIncludingChildren INT)
INSERT INTO @products
        ( ID ,
          ParentId ,
          NAME ,
          ProductCount ,
          ProductCountIncludingChildren
        )
SELECT  Id ,
        ParentId ,
        NAME ,
        ProductCount,
        0
FROM #products

DECLARE @i INT
SELECT @i = MAX(id) FROM @products

--Stupid loop - loops suck
WHILE @i > 0
    BEGIN
        WITH cte AS (SELECT ParentId, SUM(ProductCountIncludingChildren) AS ProductCountIncludingChildren FROM @products GROUP BY ParentId)
        UPDATE p1
        SET p1.ProductCountIncludingChildren = p1.ProductCount + isnull(p2.ProductCountIncludingChildren,0)
        FROM @products p1
        LEFT OUTER JOIN cte p2 ON p1.ID = p2.ParentId
        WHERE p1.ID = @i

        SELECT @i = @i - 1
    END

SELECT *
FROM @products

DROP TABLE #products

我非常希望看到更好的基于集合的方法。我遇到的问题是，当您使用递归CTE时，您从父级开始并朝向子级工作 - 这对于在父级别获取总和并不起作用。您必须执行某种向后递归CTE。

- Dave.Gugg

---

你可以从树的底部开始，通过使用像 SELECT leafNodes.* FROM [dbo].[CategoryTree] leafNodes LEFT JOIN [dbo].[CategoryTree] children ON children.[ParentId] = leafNodes.[Id] WHERE children.[Id] IS NULL 这样的锚点，在递归CTE中向上工作。 - Tom Hunter

问题在于你不能在CTE的递归成员中使用GROUP BY和聚合。我能想到的唯一办法是在标量函数中使用递归CTE，这本质上与使用循环相同。 - Tom Hunter

我认为我和你有相同的想法，但是我使用了一个表格值函数（这是不必要的，请参见上文 - 我也指出它不是最优的）。我也考虑过从底部向上遍历，一边求和一边走，但是无法快速解决如何实现。 - brumScouse