Optimización de la agregación de datos de la rama de árbol en SQL Server 2008 (recursión)

Question

Tengo una tabla que contiene etapas y subpares de ciertos proyectos, y una tabla con tareas específicas y costos estimados.
Necesito alguna forma de agregar cada nivel (etapas/subpares), para ver cuánto cuesta, pero hacerlo a un costo de rendimiento mínimo.

Para ilustrar esto, voy a utilizar la siguiente estructura de datos:

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 
) 

con los siguientes datos:

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

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

I desea obtener una tabla que contiene los costes totales de cada rama. Algo como esto:

Stage ID  Total Cost 
1    900 
2    300 
3    600 

Pero, también quiero que sea productivo. No quiero terminar con soluciones extremadamente malas como The worst algorithm in the world. Quiero decir que este es el caso. En caso de que solicite los datos para todos los artículos en la tabla stage, con los costos totales, cada costo total se evaluará D veces, donde D es la profundidad en el árbol (nivel) en el que se encuentra. Me temo que alcanzaré rendimientos extremadamente bajos con grandes cantidades de datos con muchos niveles.

SO,

que decidí hacer algo que me hizo esta pregunta aquí.
Decidí agregar 2 columnas más a la tabla stage, para el almacenamiento en caché.

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

Así que lo que quería hacer es pasar otra variable dentro del código, un valor datetime lo que equivale al tiempo en que este proceso se inició (casi única). De esta forma, si la fila stage ya tiene un date_calculated_cost que es igual a la que llevo, no me molesto en calcularlo nuevamente, y simplemente devuelvo el valor calculated_cost.

no podía hacerlo con las funciones (las actualizaciones son necesarias para la mesa stage, una vez que se calculan los costes)
no podía hacerlo con los Procedimientos (recursión dentro de los cursores en ejecución es un no-go)
I no estoy seguro de que las tablas temporales sean adecuadas porque no permitiría solicitudes simultáneas para el mismo procedimiento (que son las menos probables, pero de todos modos quiero hacerlo de la manera correcta)
No pude encontrar otras formas.

No estoy esperando una respuesta definitiva a la pregunta, pero voy a recompensar cualquier buena idea, y lo mejor será elegida como la respuesta.

Answer 1

1. Una forma de consultar las tablas para obtener el costo agregado.

1. Calcule el costo de cada etapa.
2. Use un CTE recursivo para obtener el nivel de cada etapa.
3. Almacena el resultado en una tabla temporal.
4. Agregue un par de índices a la tabla temporal.
5. actualizar el costo de la tabla temporal en un bucle para cada nivel

Los primeros tres pasos se combina con una declaración. Puede ser útil para el rendimiento hacer el primer cálculo, cteCost, en una tabla temporal propia y usar esa tabla temporal en el recursivo 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. Un disparador en la mesa task que mantiene un campo calculated_cost en 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