在SQL Server 2008中优化树分支数据聚合(递归)

Question

我有一个表格,其中包含某些项目的阶段和子阶段,以及一个包含特定任务和估计成本的表格.
我需要一些方法来聚合每个级别(阶段/子阶段),以查看它的成本,但是以最低的性能成本来完成.

为了说明这一点,我将使用以下数据结构:

CREATE TABLE stage
(
    id int not null,
    fk_parent int
)

CREATE TABLE task
(
    id int not null,
    fk_stage int not null,
    cost decimal(18,2) not null default 0
)

以下数据:

==stage==
id  fk_parent
1   null
2   1
3   1

==task==
id  fk_stage  cost
1   2         100
1   2         200
1   3         600

我想获得一个包含每个分支的总成本的表.像这样的东西:

Stage ID      Total Cost
1             900
2             300
3             600

但是,我也希望它富有成效.我不想最终得到像世界上最糟糕的算法这样的非常糟糕的解决方案.我的意思是这样的.如果我要求stage表格中所有项目的数据,总成本,每个总成本将被评估D时间,其中D树木(水平)的深度位于何处.恐怕我会在很多级别的大量数据中达到极低的性能.

所以,

我决定做点什么让我在这里问这个问题.
我决定在stage表中添加2个列,用于缓存.

...
calculated_cost decimal(18,2),
date_calculated_cost datetime
...

所以我想要做的是在代码中传递另一个变量,该datetime值等于此过程开始的时间(非常独特).那样的话,如果stage行已经有一个date_calculated_cost等于我所携带的那一行,我就不再费心计算它,只返回calculated_cost值.

我无法使用函数(stage一旦计算成本就需要对表进行更新)
我无法使用Procedures(在运行游标中递归是不行的)
我不确定临时表是否合适,因为它不会允许并发请求到同一个程序(这是最不可能的,但无论如何我想以正确的方式做)
我无法弄清楚其他方法.

我不期待我的问题有一个明确的答案,但我会奖励任何好主意,最佳选择将作为答案.

Answer 1

1. 一种查询表以获得聚合成本的方法。

1. 计算每个阶段的成本。
2. 使用递归 CTE 来获取每个阶段的级别。
3. 将结果存储在临时表中。
4. 向临时表添加几个索引。
5. 在每个级别的循环中更新临时表中的成本

前三个步骤合并为一个语句。cteCost对它自己的临时表进行第一次计算并在递归中使用该临时表可能对性能有好处cteLevel。

;with cteCost as
(
  select s.id,
         s.fk_parent,
         isnull(sum(t.cost), 0) as cost
  from stage as s
    left outer join task as t
      on s.id = t.fk_stage
  group by s.id, s.fk_parent
),
cteLevel as
(
  select cc.id,
         cc.fk_parent,
         cc.cost,
         1 as lvl
  from cteCost as cc
  where cc.fk_parent is null
  union all
  select cc.id,
         cc.fk_parent,
         cc.cost,
         lvl+1
  from cteCost as cc
    inner join cteLevel as cl
      on cc.fk_parent = cl.id       
)
select *
into #task
from cteLevel

create clustered index IX_id on #task (id)
create index IX_lvl on #task (lvl, fk_parent)

declare @lvl  int
select @lvl = max(lvl)
from #task

while @lvl > 0
begin

  update T1 set
    T1.cost = T1.cost + T2.cost
  from #task as T1
    inner join (select fk_parent, sum(cost) as cost
                from #task
                where lvl = @lvl
                group by fk_parent) as T2
      on T1.id = T2.fk_parent

  set @lvl = @lvl - 1
end

select id as [Stage ID],
       cost as [Total Cost] 
from #task

drop table #task

2. 表上的触发器task，维护calculated_cost中的字段stage。

create trigger tr_task 
on task 
after insert, update, delete
as
  -- Table to hold the updates
  declare @T table
  (
    id int not null, 
    cost decimal(18,2) not null default 0
  )

  -- Get the updates from inserted and deleted tables
  insert into @T (id, cost)
  select fk_stage, sum(cost)
  from (
          select fk_stage, cost
          from inserted
          union all
          select fk_stage, -cost
          from deleted
       ) as T   
  group by fk_stage

  declare @id int
  select @id = min(id)
  from @T

  -- For each updated row
  while @id is not null
  begin

    -- Recursive update of stage
    with cte as 
    (
      select s.id,
             s.fk_parent
      from stage as s
      where id = @id
      union all
      select s.id,
             s.fk_parent
      from stage as s
        inner join cte as c
          on s.id = c.fk_parent    
    )
    update s set
      calculated_cost = s.calculated_cost + t.cost 
    from stage as s
      inner join cte as c
        on s.id = c.id
      cross apply (select cost
                   from @T
                   where id = @id) as t   

    -- Get the next id
    select @id = min(id)
    from @T
    where id > @id
  end