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

Question

Étant donné une table d'auto-référencement

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

Avec une table associée de valeurs associées

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

Et des 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

J'ai besoin d'un sproc pour prendre Item.Id et renvoyer les enfants directs avec la somme de tous les ItemValue.Amounts pour eux, leurs enfants et leurs enfants en bas de l'arbre.

Par exemple, si 1 est passé, l’arborescence sera 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 type d’approches faut-il appliquer pour obtenir ce comportement?

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

Answer 1

Un CTE récursif comme celui-ci fonctionnerait si votre hiérarchie ne va pas trop loin:

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 sur le curseur ou autre. Comme il s'agit d'un processus stocké, c'est une possibilité, et s'il y a beaucoup de données à récupérer, il sera probablement mieux redimensionné, à condition que vous les découpiez de manière appropriée.

Si l'index en cluster est sur Id, ajoutez un index non en cluster sur ParentId. En tant qu'indice de couverture, il satisfera la recherche initiale sans recherche de signet. L'index clusterisé aidera ensuite à la jointure récursive.

Si l'index en cluster est déjà sur ParentId, ajoutez un index non en cluster sur Id. Ensemble, ils seront pratiquement é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 d'ensemble imbriqué (voici un fichier MySQL référence mais les idées sont génériques dans les bases de données)? Si tel est le cas, la recherche de la valeur que vous recherchez serait assez simple.

Answer 3

Cela doit-il être traité dans la base de données? Je suggère d’apporter les données nécessaires dans votre BLL et d’y effectuer la récursivité.