Quel est le meilleur moyen de regrouper, d'agréger et de sommer des données d'arbre?

Question

donné une table de référence auto

Item 
------------- 
Id (pk) 
ParentId (fk) 

Avec une table connexe de valeurs associées

ItemValue 
------------- 
ItemId (fk) 
Amount 

Et quelques exemples de données

Item      ItemValues 
Id  ParentId   ItemId  Amount 
--------------------  ---------------------- 
1  null    1   10 
2  1     3   40 
3  1     3   20 
4  2     4   10 
5  2     5   30 
6  null 
7  6 
8  7 

je besoin d'un sproc prendre Item.Id et retourner le directe les enfants avec une somme de ItemValue.Amounts pour eux, leurs enfants et leurs enfants tout le long ee.

Par exemple, si 1 est passé dans, l'arbre serait 2, 3, 4, 5 les enfants directs sont 2, 3 la sortie serait

ItemId Amount 
------------------ 
2   40  (values from ItemIds 4 & 5) 
3   60  (values from ItemId 3) 

Quel genre d'approches à appliquer pour faire parvenir à ce comportement?

J'envisage d'utiliser un CTE, mais je me demande s'il y a une approche meilleure/plus rapide.

Answer 1

Un CTE récursive comme cela fonctionnerait, en supposant que votre hiérarchie ne va pas trop profonde:

declare @ParentId int; 
set @ParentId = 1; 

;with 
    Recurse as (
    select 
     a.Id as DirectChildId 
    , a.Id 
    from Item a 
    where ParentId = @ParentId 
    union all 
    select 
     b.DirectChildId 
    , a.Id 
    from Item a 
    join Recurse b on b.Id = a.ParentId 
    ) 
select 
    a.DirectChildId, sum(b.Amount) as Amount 
from Recurse a 
left join ItemValues b on a.Id = b.ItemId 
group by 
    DirectChildId; 

Une méthode non-CTE nécessiterait une forme d'itération, basée curseur ou autrement. Comme il s'agit d'un proc stocké, c'est une possibilité, et s'il y a beaucoup de données à recopier, il serait probablement plus efficace, à condition de bien découper les données.

Si l'index cluster est sur Id, ajoutez un index non cluster sur ParentId. En tant qu'indice de couverture, il satisfera la recherche initiale sans recherche de marque-page. L'index clusterisé aidera alors avec la jointure récursive.

Si l'index cluster est déjà sur ParentId à la place, ajoutez un index non cluster sur Id. Ensemble, ils seront virtuellement équivalents à ce qui précède. Pour ItemValues, vous pouvez vouloir un index sur (ItemId) INCLUDE (Amount), si la table réelle est plus large que cela.

Answer 2

Pourriez-vous stocker vos données comme dans le modèle de jeu imbriqué (voici un MySQL reference mais les idées sont génériques dans les bases de données)? Si oui, les opérations pour trouver la valeur que vous recherchez seraient assez simples.

Answer 3

Est-ce que cela doit être géré dans la base de données? Je suggère d'apporter les données nécessaires dans votre BLL et d'effectuer la récursion là-bas.