Optimiser une hiérarchie CTE

15

Mettre à jour ci-dessous

J'ai un tableau de comptes avec une architecture de compte acct / parent typique pour représenter une hiérarchie de comptes (SQL Server 2012). J'ai créé une VUE en utilisant un CTE pour hacher la hiérarchie, et dans l'ensemble cela fonctionne à merveille et comme prévu. Je peux interroger la hiérarchie à n'importe quel niveau et voir facilement les branches.

Il existe un champ de logique métier qui doit être renvoyé en fonction de la hiérarchie. Un champ dans chaque enregistrement de compte décrit la taille de l'entreprise (nous l'appellerons CustomerCount). La logique dont j'ai besoin pour rendre compte doit remonter le compte client de toute la succursale. En d'autres termes, compte tenu d'un compte, j'ai besoin de résumer les valeurs de compte personnalisé pour ce compte avec chaque enfant dans chaque branche sous le compte le long de la hiérarchie.

J'ai réussi à calculer le champ à l'aide d'un champ de hiérarchie construit dans le CTE, qui ressemble à acct4.acct3.acct2.acct1. Le problème que je rencontre est simplement de le faire fonctionner rapidement. Sans ce seul champ calculé, la requête s'exécute en ~ 3 secondes. Lorsque j'ajoute dans le champ calculé, cela se transforme en une requête de 4 minutes.

Voici la meilleure version que j'ai pu trouver qui renvoie les bons résultats. Je cherche des idées sur la façon de restructurer cela COMME UNE VUE sans sacrifices énormes à la performance.

Je comprends la raison pour laquelle celui-ci va lentement (nécessite le calcul d'un prédicat dans la clause where), mais je ne peux pas penser à une autre façon de le structurer et d'obtenir toujours les mêmes résultats.

Voici un exemple de code pour construire une table et faire le CTE à peu près exactement comme cela fonctionne dans mon environnement.

Use Tempdb
go
CREATE TABLE dbo.Account
(
   Acctid varchar(1) NOT NULL
    , Name varchar(30) NULL
    , ParentId varchar(1) NULL
    , CustomerCount int NULL
);

INSERT Account
SELECT 'A','Best Bet',NULL,21  UNION ALL
SELECT 'B','eStore','A',30 UNION ALL
SELECT 'C','Big Bens','B',75 UNION ALL
SELECT 'D','Mr. Jimbo','B',50 UNION ALL
SELECT 'E','Dr. John','C',100 UNION ALL
SELECT 'F','Brick','A',222 UNION ALL
SELECT 'G','Mortar','C',153 ;


With AccountHierarchy AS

(                                                                           --Root values have no parent
    SELECT
        Root.AcctId                                         AccountId
        , Root.Name                                         AccountName
        , Root.ParentId                                     ParentId
        , 1                                                 HierarchyLevel  
        , cast(Root.Acctid as varchar(4000))                IdHierarchy     --highest parent reads right to left as in id3.Acctid2.Acctid1
        , cast(replace(Root.Name,'.','') as varchar(4000))  NameHierarchy   --highest parent reads right to left as in name3.name2.name1 (replace '.' so name parse is easy in last step)
        , cast(Root.Acctid as varchar(4000))                HierarchySort   --reverse of above, read left to right name1.name2.name3 for sorting on reporting only
        , cast(Root.Name as varchar(4000))                  HierarchyLabel  --use for labels on reporting only, indents names under sorted hierarchy
        , Root.CustomerCount                                CustomerCount   

    FROM 
        tempdb.dbo.account Root

    WHERE
        Root.ParentID is null

    UNION ALL

    SELECT
        Recurse.Acctid                                      AccountId
        , Recurse.Name                                      AccountName
        , Recurse.ParentId                                  ParentId
        , Root.HierarchyLevel + 1                           HierarchyLevel  --next level in hierarchy
        , cast(cast(recurse.Acctid as varchar(40)) + '.' + Root.IdHierarchy as varchar(4000))   IdHierarchy --cast because in real system this is a uniqueidentifier type needs converting
        , cast(replace(recurse.Name,'.','') + '.' + Root.NameHierarchy as varchar(4000)) NameHierarchy  --replace '.' for parsing in last step, cast to make room for lots of sub levels down the hierarchy
        , cast(Root.AccountName + '.' + Recurse.Name as varchar(4000)) HierarchySort    
        , cast(space(root.HierarchyLevel * 4) + Recurse.Name as varchar(4000)) HierarchyLabel
        , Recurse.CustomerCount                             CustomerCount

    FROM
        tempdb.dbo.account Recurse INNER JOIN
        AccountHierarchy Root on Root.AccountId = Recurse.ParentId
)


SELECT
    hier.AccountId
    , Hier.AccountName
    , hier.ParentId
    , hier.HierarchyLevel
    , hier.IdHierarchy
    , hier.NameHierarchy
    , hier.HierarchyLabel
    , parsename(hier.IdHierarchy,1) Acct1Id
    , parsename(hier.NameHierarchy,1) Acct1Name     --This is why we stripped out '.' during recursion
    , parsename(hier.IdHierarchy,2) Acct2Id
    , parsename(hier.NameHierarchy,2) Acct2Name
    , parsename(hier.IdHierarchy,3) Acct3Id
    , parsename(hier.NameHierarchy,3) Acct3Name
    , parsename(hier.IdHierarchy,4) Acct4Id
    , parsename(hier.NameHierarchy,4) Acct4Name
    , hier.CustomerCount

    /* fantastic up to this point. Next block of code is what causes problem. 
        Logic of code is "sum of CustomerCount for this location and all branches below in this branch of hierarchy"
        In live environment, goes from taking 3 seconds to 4 minutes by adding this one calc */

    , (
        SELECT  
            sum(children.CustomerCount)
        FROM
            AccountHierarchy Children
        WHERE
            hier.IdHierarchy = right(children.IdHierarchy, (1 /*length of id field*/ * hier.HierarchyLevel) + hier.HierarchyLevel - 1 /*for periods inbetween ids*/)
            --"where this location's idhierarchy is within child idhierarchy"
            --previously tried a charindex(hier.IdHierarchy,children.IdHierarchy)>0, but that performed even worse
        ) TotalCustomerCount
FROM
    AccountHierarchy hier

ORDER BY
    hier.HierarchySort


drop table tempdb.dbo.Account

20/11/2013 MISE À JOUR

Certaines des solutions suggérées ont fait couler mon jus et j'ai essayé une nouvelle approche qui se rapproche, mais introduit un obstacle nouveau / différent. Honnêtement, je ne sais pas si cela justifie un poste séparé ou non, mais c'est lié à la solution de ce problème.

Ce que j'ai décidé, c'est que ce qui rendait la somme (compte personnalisé) difficile, c'est l'identification des enfants dans le contexte d'une hiérarchie qui commence en haut et se construit progressivement. J'ai donc commencé par créer une hiérarchie qui se construit de bas en haut, en utilisant la racine définie par "les comptes qui ne sont parents d'aucun autre compte" et en faisant la jointure récursive à l'envers (root.parentacctid = recurse.acctid)

De cette façon, je pourrais simplement ajouter le nombre de clients enfants au parent lorsque la récursivité se produit. En raison de la façon dont j'ai besoin de rapports et de niveaux, je fais ce cte de bas en haut en plus de haut en bas, puis je les rejoins simplement via l'ID de compte. Cette approche s'avère beaucoup plus rapide que le compte personnalisé de la requête externe d'origine, mais j'ai rencontré quelques obstacles.

Tout d'abord, je capturais par inadvertance le nombre de clients en double pour les comptes parents de plusieurs enfants. J'ai compté deux ou trois fois le nombre de clients pour certains acctid, par le nombre d'enfants. Ma solution était de créer un autre cte qui compte le nombre de nœuds d'un acct et de diviser le acct.customercount pendant la récursivité, donc quand j'additionne la branche entière, l'acct n'est pas compté deux fois.

Donc, à ce stade, les résultats de cette nouvelle version ne sont pas corrects, mais je sais pourquoi. Le cte bottomup crée des doublons. Lorsque la récursivité réussit, elle recherche tout élément de la racine (enfants de niveau inférieur) qui est enfant d'un compte dans la table des comptes. Lors de la troisième récursivité, il récupère les mêmes comptes que dans le second et les réinsère.

Des idées sur la façon de faire un cte de bas en haut, ou cela fait-il couler d'autres idées?

Use Tempdb
go


CREATE TABLE dbo.Account
(
    Acctid varchar(1) NOT NULL
    , Name varchar(30) NULL
    , ParentId varchar(1) NULL
    , CustomerCount int NULL
);

INSERT Account
SELECT 'A','Best Bet',NULL,1  UNION ALL
SELECT 'B','eStore','A',2 UNION ALL
SELECT 'C','Big Bens','B',3 UNION ALL
SELECT 'D','Mr. Jimbo','B',4 UNION ALL
SELECT 'E','Dr. John','C',5 UNION ALL
SELECT 'F','Brick','A',6 UNION ALL
SELECT 'G','Mortar','C',7 ;



With AccountHierarchy AS

(                                                                           --Root values have no parent
    SELECT
        Root.AcctId                                         AccountId
        , Root.Name                                         AccountName
        , Root.ParentId                                     ParentId
        , 1                                                 HierarchyLevel  
        , cast(Root.Acctid as varchar(4000))                IdHierarchy     --highest parent reads right to left as in id3.Acctid2.Acctid1
        , cast(replace(Root.Name,'.','') as varchar(4000))  NameHierarchy   --highest parent reads right to left as in name3.name2.name1 (replace '.' so name parse is easy in last step)
        , cast(Root.Acctid as varchar(4000))                HierarchySort   --reverse of above, read left to right name1.name2.name3 for sorting on reporting only
        , cast(Root.Acctid as varchar(4000))                HierarchyMatch 
        , cast(Root.Name as varchar(4000))                  HierarchyLabel  --use for labels on reporting only, indents names under sorted hierarchy
        , Root.CustomerCount                                CustomerCount   

    FROM 
        tempdb.dbo.account Root

    WHERE
        Root.ParentID is null

    UNION ALL

    SELECT
        Recurse.Acctid                                      AccountId
        , Recurse.Name                                      AccountName
        , Recurse.ParentId                                  ParentId
        , Root.HierarchyLevel + 1                           HierarchyLevel  --next level in hierarchy
        , cast(cast(recurse.Acctid as varchar(40)) + '.' + Root.IdHierarchy as varchar(4000))   IdHierarchy --cast because in real system this is a uniqueidentifier type needs converting
        , cast(replace(recurse.Name,'.','') + '.' + Root.NameHierarchy as varchar(4000)) NameHierarchy  --replace '.' for parsing in last step, cast to make room for lots of sub levels down the hierarchy
        , cast(Root.AccountName + '.' + Recurse.Name as varchar(4000)) HierarchySort    
        , CAST(CAST(Root.HierarchyMatch as varchar(40)) + '.' 
            + cast(recurse.Acctid as varchar(40))   as varchar(4000))   HierarchyMatch
        , cast(space(root.HierarchyLevel * 4) + Recurse.Name as varchar(4000)) HierarchyLabel
        , Recurse.CustomerCount                             CustomerCount

    FROM
        tempdb.dbo.account Recurse INNER JOIN
        AccountHierarchy Root on Root.AccountId = Recurse.ParentId
)

, Nodes as
(   --counts how many branches are below for any account that is parent to another
    select
        node.ParentId Acctid
        , cast(count(1) as float) Nodes
    from AccountHierarchy  node
    group by ParentId
)

, BottomUp as
(   --creates the hierarchy starting at accounts that are not parent to any other
    select
        Root.Acctid
        , root.ParentId
        , cast(isnull(root.customercount,0) as float) CustomerCount
    from
        tempdb.dbo.Account Root
    where
        not exists ( select 1 from tempdb.dbo.Account OtherAccts where root.Acctid = OtherAccts.ParentId)

    union all

    select
        Recurse.Acctid
        , Recurse.ParentId
        , root.CustomerCount + cast ((isnull(recurse.customercount,0) / nodes.nodes) as float) CustomerCount
        -- divide the recurse customercount by number of nodes to prevent duplicate customer count on accts that are parent to multiple children, see customercount cte next
    from
        tempdb.dbo.Account Recurse inner join 
        BottomUp Root on root.ParentId = recurse.acctid inner join
        Nodes on nodes.Acctid = recurse.Acctid
)

, CustomerCount as
(
    select
        sum(CustomerCount) TotalCustomerCount
        , hier.acctid
    from
        BottomUp hier
    group by 
        hier.Acctid
)


SELECT
    hier.AccountId
    , Hier.AccountName
    , hier.ParentId
    , hier.HierarchyLevel
    , hier.IdHierarchy
    , hier.NameHierarchy
    , hier.HierarchyLabel
    , hier.hierarchymatch
    , parsename(hier.IdHierarchy,1) Acct1Id
    , parsename(hier.NameHierarchy,1) Acct1Name     --This is why we stripped out '.' during recursion
    , parsename(hier.IdHierarchy,2) Acct2Id
    , parsename(hier.NameHierarchy,2) Acct2Name
    , parsename(hier.IdHierarchy,3) Acct3Id
    , parsename(hier.NameHierarchy,3) Acct3Name
    , parsename(hier.IdHierarchy,4) Acct4Id
    , parsename(hier.NameHierarchy,4) Acct4Name
    , hier.CustomerCount

    , customercount.TotalCustomerCount

FROM
    AccountHierarchy hier inner join
    CustomerCount on customercount.acctid = hier.accountid

ORDER BY
    hier.HierarchySort 



drop table tempdb.dbo.Account
liver.larson
la source
1
Avez-vous essayé de mettre les résultats du AccountHierarchy CTE dans une table temporaire (indexée sur IdHierarchy) ALORS faire le calcul en interrogeant à partir de la table temporaire? Vous pourriez être en cours d'exécution dans la façon dont les CTE sont mis en œuvre; il est possible que vous exécutiez l'intégralité du CTE une fois pour CHAQUE ligne du CTE.
Jon Boulineau
1
Quels sont les index sur la table sous-jacente?
Mike Walsh
1
Et combien de lignes dans le vrai tableau?
Mike Walsh
2
@MaxVernon Merci. N'ont pas beaucoup posté, mais voient certainement la différence de qualité des réponses pour les questions vagues.
liver.larson
@JonBoulineau J'avais envisagé d'essayer quelque chose avec des tables temporaires, mais j'essaie spécifiquement de l'exécuter en tant que vue, ce qui exclut les tables temporaires. Avez-vous des idées sur la façon de vous déplacer ou de tester votre dernière affirmation?
liver.larson

Réponses:

6

Edit: c'est la deuxième tentative

Sur la base de la réponse de @Max Vernon, voici un moyen de contourner l'utilisation de CTE dans une sous-requête en ligne, ce qui revient à rejoindre le CTE et je suppose que c'est la raison de la faible efficacité. Il utilise des fonctions analytiques disponibles uniquement dans la version 2012 de SQL-Server. Testé à SQL-Fiddle

Cette partie peut être sautée de la lecture, c'est un copier-coller de la réponse de Max:

;With AccountHierarchy AS
(                                                                           
    SELECT
        Root.AcctId                                         AccountId
        , Root.Name                                         AccountName
        , Root.ParentId                                     ParentId
        , 1                                                 HierarchyLevel  
        , cast(Root.Acctid as varchar(4000))                IdHierarchyMatch        
        , cast(Root.Acctid as varchar(4000))                IdHierarchy
        , cast(replace(Root.Name,'.','') as varchar(4000))  NameHierarchy   
        , cast(Root.Acctid as varchar(4000))                HierarchySort
        , cast(Root.Name as varchar(4000))                  HierarchyLabel          ,
        Root.CustomerCount                                  CustomerCount   

    FROM 
        account Root

    WHERE
        Root.ParentID is null

    UNION ALL

    SELECT
        Recurse.Acctid                                      AccountId
        , Recurse.Name                                      AccountName
        , Recurse.ParentId                                  ParentId
        , Root.HierarchyLevel + 1                           HierarchyLevel
        , CAST(CAST(Root.IdHierarchyMatch as varchar(40)) + '.' 
            + cast(recurse.Acctid as varchar(40))   as varchar(4000))   IdHierarchyMatch
        , cast(cast(recurse.Acctid as varchar(40)) + '.' 
            + Root.IdHierarchy  as varchar(4000))           IdHierarchy
        , cast(replace(recurse.Name,'.','') + '.' 
            + Root.NameHierarchy as varchar(4000))          NameHierarchy
        , cast(Root.AccountName + '.' 
            + Recurse.Name as varchar(4000))                HierarchySort   
        , cast(space(root.HierarchyLevel * 4) 
            + Recurse.Name as varchar(4000))                HierarchyLabel
        , Recurse.CustomerCount                             CustomerCount
    FROM
        account Recurse INNER JOIN
        AccountHierarchy Root on Root.AccountId = Recurse.ParentId
)

Ici, nous ordonnons les lignes du CTE en utilisant le IdHierarchyMatch et nous calculons les numéros de ligne et un total cumulé (de la ligne suivante jusqu'à la fin).

, cte1 AS 
(
SELECT
    h.AccountId
    , h.AccountName
    , h.ParentId
    , h.HierarchyLevel
    , h.IdHierarchy
    , h.NameHierarchy
    , h.HierarchyLabel
    , parsename(h.IdHierarchy,1) Acct1Id
    , parsename(h.NameHierarchy,1) Acct1Name
    , parsename(h.IdHierarchy,2) Acct2Id
    , parsename(h.NameHierarchy,2) Acct2Name
    , parsename(h.IdHierarchy,3) Acct3Id
    , parsename(h.NameHierarchy,3) Acct3Name
    , parsename(h.IdHierarchy,4) Acct4Id
    , parsename(h.NameHierarchy,4) Acct4Name
    , h.CustomerCount
    , h.HierarchySort
    , h.IdHierarchyMatch
        , Rn = ROW_NUMBER() OVER 
                  (ORDER BY h.IdHierarchyMatch)
        , RunningCustomerCount = COALESCE(
            SUM(h.CustomerCount)
            OVER
              (ORDER BY h.IdHierarchyMatch
               ROWS BETWEEN 1 FOLLOWING
                        AND UNBOUNDED FOLLOWING)
          , 0) 
FROM
    AccountHierarchy AS h  
)

Ensuite, nous avons un CTE intermédiaire supplémentaire où nous utilisons les totaux et les numéros de ligne précédents - essentiellement pour trouver où les points finaux pour les branches de la structure arborescente:

, cte2 AS
(
SELECT
    cte1.*
    , rn3  = LAST_VALUE(Rn) OVER 
               (PARTITION BY Acct1Id, Acct2Id, Acct3Id 
                ORDER BY Acct4Id
                ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)       
    , rn2  = LAST_VALUE(Rn) OVER 
               (PARTITION BY Acct1Id, Acct2Id 
                ORDER BY Acct3Id, Acct4Id
                ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) 
    , rn1  = LAST_VALUE(Rn) OVER 
               (PARTITION BY Acct1Id 
                ORDER BY Acct2Id, Acct3Id, Acct4Id
                ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) 
    , rcc3 = LAST_VALUE(RunningCustomerCount) OVER 
               (PARTITION BY Acct1Id, Acct2Id, Acct3Id 
                ORDER BY Acct4Id
                ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)       
    , rcc2 = LAST_VALUE(RunningCustomerCount) OVER 
               (PARTITION BY Acct1Id, Acct2Id 
                ORDER BY Acct3Id, Acct4Id
                ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) 
    , rcc1 = LAST_VALUE(RunningCustomerCount) OVER 
               (PARTITION BY Acct1Id 
                ORDER BY Acct2Id, Acct3Id, Acct4Id
                ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) 
FROM
    cte1 
) 

et enfin nous construisons la dernière partie:

SELECT
    hier.AccountId
    , hier.AccountName
    ---                        -- columns skipped 
    , hier.CustomerCount

    , TotalCustomerCount = hier.CustomerCount
        + hier.RunningCustomerCount 
        - ca.LastRunningCustomerCount

    , hier.HierarchySort
    , hier.IdHierarchyMatch
FROM
    cte2 hier
  OUTER APPLY
    ( SELECT  LastRunningCustomerCount, Rn
      FROM
      ( SELECT LastRunningCustomerCount
              = RunningCustomerCount, Rn
        FROM (SELECT NULL a) x  WHERE 4 <= HierarchyLevel 
      UNION ALL
        SELECT rcc3, Rn3
        FROM (SELECT NULL a) x  WHERE 3 <= HierarchyLevel 
      UNION ALL
        SELECT rcc2, Rn2 
        FROM (SELECT NULL a) x  WHERE 2 <= HierarchyLevel 
      UNION ALL
        SELECT rcc1, Rn1
        FROM (SELECT NULL a) x  WHERE 1 <= HierarchyLevel 
      ) x
      ORDER BY Rn 
      OFFSET 0 ROWS
      FETCH NEXT 1 ROWS ONLY
      ) ca
ORDER BY
    hier.HierarchySort ; 

Et une simplification, en utilisant le même cte1que le code ci-dessus. Testez à SQL-Fiddle-2 . Veuillez noter que les deux solutions fonctionnent en supposant que vous avez un maximum de quatre niveaux dans votre arborescence:

SELECT
    hier.AccountId
    ---                      -- skipping rows
    , hier.CustomerCount

    , TotalCustomerCount = CustomerCount
        + RunningCustomerCount 
        - CASE HierarchyLevel
            WHEN 4 THEN RunningCustomerCount
            WHEN 3 THEN LAST_VALUE(RunningCustomerCount) OVER 
                   (PARTITION BY Acct1Id, Acct2Id, Acct3Id 
                    ORDER BY Acct4Id
                    ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)       
            WHEN 2 THEN LAST_VALUE(RunningCustomerCount) OVER 
                   (PARTITION BY Acct1Id, Acct2Id 
                    ORDER BY Acct3Id, Acct4Id
                    ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) 
            WHEN 1 THEN LAST_VALUE(RunningCustomerCount) OVER 
                   (PARTITION BY Acct1Id 
                    ORDER BY Acct2Id, Acct3Id, Acct4Id
                    ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) 
          END

    , hier.HierarchySort
    , hier.IdHierarchyMatch
FROM cte1 AS hier
ORDER BY
    hier.HierarchySort ; 

Une troisième approche, avec un seul CTE, pour la partie récursive et ensuite uniquement des fonctions d'agrégation de fenêtres ( SUM() OVER (...)), donc cela devrait fonctionner dans n'importe quelle version à partir de 2005. Test à SQL-Fiddle-3 Cette solution suppose, comme les précédentes, qu'il existe 4 niveaux maximum dans l'arborescence:

;WITH AccountHierarchy AS
(                                                                           
    SELECT
          AccountId      = Root.AcctId                                         
        , AccountName    = Root.Name                                         
        , ParentId       = Root.ParentId                                     
        , HierarchyLevel = 1                                                   
        , HierarchySort  = CAST(Root.Acctid AS VARCHAR(4000))                
        , HierarchyLabel = CAST(Root.Name AS VARCHAR(4000))                   
        , Acct1Id        = CAST(Root.Acctid AS VARCHAR(4000))                
        , Acct2Id        = CAST(NULL AS VARCHAR(4000))                       
        , Acct3Id        = CAST(NULL AS VARCHAR(4000))                       
        , Acct4Id        = CAST(NULL AS VARCHAR(4000))                       
        , Acct1Name      = CAST(Root.Name AS VARCHAR(4000))                  
        , Acct2Name      = CAST(NULL AS VARCHAR(4000))                       
        , Acct3Name      = CAST(NULL AS VARCHAR(4000))                       
        , Acct4Name      = CAST(NULL AS VARCHAR(4000))                       
        , CustomerCount  = Root.CustomerCount                                   

    FROM 
        account AS Root

    WHERE
        Root.ParentID IS NULL

    UNION ALL

    SELECT
          Recurse.Acctid 
        , Recurse.Name 
        , Recurse.ParentId 
        , Root.HierarchyLevel + 1 
        , CAST(Root.AccountName + '.' 
            + Recurse.Name AS VARCHAR(4000)) 
        , CAST(SPACE(Root.HierarchyLevel * 4) 
            + Recurse.Name AS VARCHAR(4000)) 
        , Root.Acct1Id 
        , CASE WHEN Root.HierarchyLevel = 1 
              THEN cast(Recurse.Acctid AS VARCHAR(4000)) 
              ELSE Root.Acct2Id 
          END 
        , CASE WHEN Root.HierarchyLevel = 2 
              THEN CAST(Recurse.Acctid AS VARCHAR(4000)) 
              ELSE Root.Acct3Id 
          END 
        , CASE WHEN Root.HierarchyLevel = 3 
              THEN CAST(Recurse.Acctid AS VARCHAR(4000)) 
              ELSE Root.Acct4Id 
          END 

        , cast(Root.AccountName as varchar(4000))          
        , CASE WHEN Root.HierarchyLevel = 1 
              THEN CAST(Recurse.Name AS VARCHAR(4000)) 
              ELSE Root.Acct2Name 
          END 
        , CASE WHEN Root.HierarchyLevel = 2 
              THEN CAST(Recurse.Name AS VARCHAR(4000)) 
              ELSE Root.Acct3Name 
          END 
        , CASE WHEN Root.HierarchyLevel = 3 
              THEN CAST(Recurse.Name AS VARCHAR(4000)) 
              ELSE Root.Acct4Name 
          END 
        , Recurse.CustomerCount 
    FROM 
        account AS Recurse INNER JOIN 
        AccountHierarchy AS Root ON Root.AccountId = Recurse.ParentId
)

SELECT
      h.AccountId
    , h.AccountName
    , h.ParentId
    , h.HierarchyLevel
    , IdHierarchy = 
          CAST(COALESCE(h.Acct4Id+'.','') 
               + COALESCE(h.Acct3Id+'.','') 
               + COALESCE(h.Acct2Id+'.','') 
               + h.Acct1Id AS VARCHAR(4000))
    , NameHierarchy = 
          CAST(COALESCE(h.Acct4Name+'.','') 
               + COALESCE(h.Acct3Name+'.','') 
               + COALESCE(h.Acct2Name+'.','') 
               + h.Acct1Name AS VARCHAR(4000))   
    , h.HierarchyLabel
    , h.Acct1Id
    , h.Acct1Name
    , h.Acct2Id
    , h.Acct2Name
    , h.Acct3Id
    , h.Acct3Name
    , h.Acct4Id
    , h.Acct4Name
    , h.CustomerCount
    , TotalCustomerCount =  
          CASE h.HierarchyLevel
            WHEN 4 THEN h.CustomerCount
            WHEN 3 THEN SUM(h.CustomerCount) OVER 
                   (PARTITION BY h.Acct1Id, h.Acct2Id, h.Acct3Id)       
            WHEN 2 THEN SUM(h.CustomerCount) OVER 
                   (PARTITION BY Acct1Id, h.Acct2Id) 
            WHEN 1 THEN SUM(h.CustomerCount) OVER 
                   (PARTITION BY h.Acct1Id) 
          END
    , h.HierarchySort
    , IdHierarchyMatch = 
          CAST(h.Acct1Id 
               + COALESCE('.'+h.Acct2Id,'') 
               + COALESCE('.'+h.Acct3Id,'') 
               + COALESCE('.'+h.Acct4Id,'') AS VARCHAR(4000))   
FROM
    AccountHierarchy AS h  
ORDER BY
    h.HierarchySort ; 

Une 4ème approche, qui calcule comme CTE intermédiaire, la table de clôture de la hiérarchie. Testez à SQL-Fiddle-4 . L'avantage est que pour le calcul des sommes, il n'y a pas de restriction sur le nombre de niveaux.

;WITH AccountHierarchy AS
( 
    -- skipping several line, identical to the 3rd approach above
)

, ClosureTable AS
( 
    SELECT
          AccountId      = Root.AcctId  
        , AncestorId     = Root.AcctId  
        , CustomerCount  = Root.CustomerCount 
    FROM 
        account AS Root

    UNION ALL

    SELECT
          Recurse.Acctid 
        , Root.AncestorId 
        , Recurse.CustomerCount
    FROM 
        account AS Recurse INNER JOIN 
        ClosureTable AS Root ON Root.AccountId = Recurse.ParentId
)

, ClosureGroup AS
(                                                                           
    SELECT
          AccountId           = AncestorId  
        , TotalCustomerCount  = SUM(CustomerCount)                             
    FROM 
        ClosureTable AS a
    GROUP BY
        AncestorId
)

SELECT
      h.AccountId
    , h.AccountName
    , h.ParentId
    , h.HierarchyLevel 
    , h.HierarchyLabel
    , h.CustomerCount
    , cg.TotalCustomerCount 

    , h.HierarchySort
FROM
    AccountHierarchy AS h  
  JOIN
    ClosureGroup AS cg
      ON cg.AccountId = h.AccountId
ORDER BY
    h.HierarchySort ;  
ypercubeᵀᴹ
la source
Correction du code (et du violon lié.) Il y avait une option QUAND manquante dans la réponse.
ypercubeᵀᴹ
+1 - J'aime l'utilisation des fonctions 2012. J'ai beaucoup d'apprentissage maintenant!
Max Vernon
ok, je viens de passer un peu de temps à plonger et j'ai réalisé que les performances étaient excellentes, mais les chiffres ne correspondent pas. Vérifiez les résultats par rapport à mon original. Je peux en quelque sorte voir où vous alliez avec les totaux en cours, mais il va falloir en changer certains pour que cela fonctionne comme prévu, et je ne suis pas arrivé à la bonne solution. Votre approche me permet de travailler avec du fourrage, mais ce n'est pas encore une solution viable.
liver.larson
Oh, je pense que c'est vraiment faux. Veuillez refuser.
ypercubeᵀᴹ
J'ai essayé de le corriger. Cela fonctionne bien avec mon petit échantillon, mais veuillez vérifier l'exactitude de vos données. À propos de l'efficacité, que puis-je dire, nous ne pouvons le savoir qu'en testant (à moins que votre nom ne soit @Paul White).
ypercubeᵀᴹ
5

Je pense que cela devrait accélérer les choses:

;With AccountHierarchy AS
(                                                                           
    SELECT
        Root.AcctId                                         AccountId
        , Root.Name                                         AccountName
        , Root.ParentId                                     ParentId
        , 1                                                 HierarchyLevel  
        , cast(Root.Acctid as varchar(4000))                IdHierarchyMatch        
        , cast(Root.Acctid as varchar(4000))                IdHierarchy
        , cast(replace(Root.Name,'.','') as varchar(4000))  NameHierarchy   
        , cast(Root.Acctid as varchar(4000))                HierarchySort
        , cast(Root.Name as varchar(4000))                  HierarchyLabel          ,
        Root.CustomerCount                                  CustomerCount   

    FROM 
        tempdb.dbo.account Root

    WHERE
        Root.ParentID is null

    UNION ALL

    SELECT
        Recurse.Acctid                                      AccountId
        , Recurse.Name                                      AccountName
        , Recurse.ParentId                                  ParentId
        , Root.HierarchyLevel + 1                           HierarchyLevel
        , CAST(CAST(Root.IdHierarchyMatch as varchar(40)) + '.' 
            + cast(recurse.Acctid as varchar(40))   as varchar(4000))   IdHierarchyMatch
        , cast(cast(recurse.Acctid as varchar(40)) + '.' 
            + Root.IdHierarchy  as varchar(4000))           IdHierarchy
        , cast(replace(recurse.Name,'.','') + '.' 
            + Root.NameHierarchy as varchar(4000))          NameHierarchy
        , cast(Root.AccountName + '.' 
            + Recurse.Name as varchar(4000))                HierarchySort   
        , cast(space(root.HierarchyLevel * 4) 
            + Recurse.Name as varchar(4000))                HierarchyLabel
        , Recurse.CustomerCount                             CustomerCount
    FROM
        tempdb.dbo.account Recurse INNER JOIN
        AccountHierarchy Root on Root.AccountId = Recurse.ParentId
)


SELECT
    hier.AccountId
    , Hier.AccountName
    , hier.ParentId
    , hier.HierarchyLevel
    , hier.IdHierarchy
    , hier.NameHierarchy
    , hier.HierarchyLabel
    , parsename(hier.IdHierarchy,1) Acct1Id
    , parsename(hier.NameHierarchy,1) Acct1Name
    , parsename(hier.IdHierarchy,2) Acct2Id
    , parsename(hier.NameHierarchy,2) Acct2Name
    , parsename(hier.IdHierarchy,3) Acct3Id
    , parsename(hier.NameHierarchy,3) Acct3Name
    , parsename(hier.IdHierarchy,4) Acct4Id
    , parsename(hier.NameHierarchy,4) Acct4Name
    , hier.CustomerCount
    , (
        SELECT  
            sum(children.CustomerCount)
        FROM
            AccountHierarchy Children
        WHERE
            Children.IdHierarchyMatch LIKE hier.IdHierarchyMatch + '%'
        ) TotalCustomerCount
        , HierarchySort
        , IdHierarchyMatch
FROM
    AccountHierarchy hier
ORDER BY
    hier.HierarchySort

J'ai ajouté une colonne dans le CTE nommé IdHierarchyMatchqui est la version directe de IdHierarchypour permettre à la clause de TotalCustomerCountsous - requête WHEREd'être sargable.

En comparant les coûts estimatifs des sous-arbres pour les plans d'exécution, cette méthode devrait être environ 5 fois plus rapide.

Max Vernon
la source
Merci d'avoir pris le temps de regarder ça. C'est drôle, c'était vraiment mon premier instinct, et je pensais que l'ajout d'un caractère générique à un champ n'était possible qu'en utilisant du SQL dynamique, et donc je n'ai même pas essayé. J'aurais dû vérifier. Le résultat est donc une nette amélioration à 2:49 (contre 3:53), mais pas autant que je l'espérais. Je vais laisser sans réponse pour voir quelles autres idées surgissent. Merci encore d'avoir pris le temps d'évaluer cela, vraiment. Je vous en suis reconnaissant.
liver.larson
Pour info, je viens de remarquer une erreur de syntaxe dans mon implémentation. Nous sommes à 2h04 du temps d'exécution. Encore mieux où j'ai commencé. Viser toujours plus vite.
liver.larson
1
Je suis content d'avoir aidé d'une petite manière. J'ai passé environ 2 heures la nuit dernière à essayer de résoudre le problème. J'ai un sentiment profond dans mon intestin, cela pourrait être résolu en utilisant une sorte de ROW_NUMER() OVER (ORDER BY...)ou quelque chose. Je ne pouvais tout simplement pas en tirer les bons chiffres. C'est une question vraiment géniale et intéressante. Bon exercice cérébral!
Max Vernon
J'ai essayé d'en faire une vue liée au schéma (matérialisée), dans le but d'ajouter un index sur le IdHierarchyMatchterrain, mais vous ne pouvez pas ajouter un index cluster sur une vue liée au schéma qui inclut un CTE. Je me demande si cette limitation est résolue dans SQL Server 2014.
Max Vernon
2
@MaxVernon Pour la version 2012: SQL-Fiddle
ypercubeᵀᴹ
3

Je lui ai aussi donné un coup de feu. Ce n'est pas très joli, mais il semble mieux fonctionner.

USE Tempdb
go

SET STATISTICS IO ON;
SET STATISTICS TIME OFF;
SET NOCOUNT ON;

--------
-- assuming the original table looks something like this 
-- and you cannot control it's indexes 
-- (only widened the data types a bit for the extra sample rows)
--------
CREATE TABLE dbo.Account
    (
      Acctid VARCHAR(10) NOT NULL ,
      Name VARCHAR(100) NULL ,
      ParentId VARCHAR(10) NULL ,
      CustomerCount INT NULL
    );

--------
-- inserting the same records as in your sample
--------
INSERT  Account
        SELECT  'A' ,
                'Best Bet' ,
                NULL ,
                21
        UNION ALL
        SELECT  'B' ,
                'eStore' ,
                'A' ,
                30
        UNION ALL
        SELECT  'C' ,
                'Big Bens' ,
                'B' ,
                75
        UNION ALL
        SELECT  'D' ,
                'Mr. Jimbo' ,
                'B' ,
                50
        UNION ALL
        SELECT  'E' ,
                'Dr. John' ,
                'C' ,
                100
        UNION ALL
        SELECT  'F' ,
                'Brick' ,
                'A' ,
                222
        UNION ALL
        SELECT  'G' ,
                'Mortar' ,
                'C' ,
                153;

--------
-- now lets up the ante a bit and add some extra rows with random parents 
-- to these 7 items, it is hard to measure differences with so few rows
--------
DECLARE @numberOfRows INT = 25000
DECLARE @from INT = 1
DECLARE @to INT = 7
DECLARE @T1 TABLE ( n INT ); 

WITH    cte ( n )
          AS ( SELECT   ROW_NUMBER() OVER ( ORDER BY CURRENT_TIMESTAMP )
               FROM     sys.messages
             )
    INSERT  INTO @T1
            SELECT  n
            FROM    cte
            WHERE   n <= @numberOfRows;

INSERT  INTO dbo.Account
        ( acctId ,
          name ,
          parentId ,
          Customercount
        )
        SELECT  CHAR(64 + RandomNumber) + CAST(n AS VARCHAR(10)) AS Id ,
                CAST('item ' + CHAR(64 + RandomNumber) + CAST(n AS VARCHAR(10)) AS VARCHAR(100)) ,
                CHAR(64 + RandomNumber) AS parentId ,
                ABS(CHECKSUM(NEWID()) % 100) + 1 AS RandomCustCount
        FROM    ( SELECT    n ,
                            ABS(CHECKSUM(NEWID()) % @to) + @from AS RandomNumber
                  FROM      @T1
                ) A;

--------
-- Assuming you cannot control it's indexes, in my tests we're better off taking the IO hit of copying the data
-- to some structure that is better optimized for this query. Not quite what I initially expected,  but we seem 
-- to be better off that way.
--------
CREATE TABLE tempdb.dbo.T1
    (
      AccountId VARCHAR(10) NOT NULL
                            PRIMARY KEY NONCLUSTERED ,
      AccountName VARCHAR(100) NOT NULL ,
      ParentId VARCHAR(10) NULL ,
      HierarchyLevel INT NULL ,
      HPath VARCHAR(1000) NULL ,
      IdHierarchy VARCHAR(1000) NULL ,
      NameHierarchy VARCHAR(1000) NULL ,
      HierarchyLabel VARCHAR(1000) NULL ,
      HierarchySort VARCHAR(1000) NULL ,
      CustomerCount INT NOT NULL
    );

CREATE CLUSTERED INDEX IX_Q1
ON tempdb.dbo.T1  ([ParentId]);

-- for summing customer counts over parents
CREATE NONCLUSTERED INDEX IX_Q2 
ON tempdb.dbo.T1  (HPath) INCLUDE(CustomerCount);

INSERT  INTO tempdb.dbo.T1
        ( AccountId ,
          AccountName ,
          ParentId ,
          HierarchyLevel ,
          HPath ,
          IdHierarchy ,
          NameHierarchy ,
          HierarchyLabel ,
          HierarchySort ,
          CustomerCount 
        )
        SELECT  Acctid AS AccountId ,
                Name AS AccountName ,
                ParentId AS ParentId ,
                NULL AS HierarchyLevel ,
                NULL AS HPath ,
                NULL AS IdHierarchy ,
                NULL AS NameHierarchy ,
                NULL AS HierarchyLabel ,
                NULL AS HierarchySort ,
                CustomerCount AS CustomerCount
        FROM    tempdb.dbo.account;



--------
-- I cannot seem to force an efficient way to do the sum while selecting over the recursive cte, 
-- so I took it aside. I am sure there is a more elegant way but I can't seem to make it happen. 
-- At least it performs better this way. But it remains a very expensive query.
--------
;
WITH    AccountHierarchy
          AS ( SELECT   Root.AccountId AS AcId ,
                        Root.ParentId ,
                        1 AS HLvl ,
                        CAST(Root.AccountId AS VARCHAR(1000)) AS [HPa] ,
                        CAST(Root.accountId AS VARCHAR(1000)) AS hid ,
                        CAST(REPLACE(Root.AccountName, '.', '') AS VARCHAR(1000)) AS hn ,
                        CAST(Root.accountid AS VARCHAR(1000)) AS hs ,
                        CAST(Root.accountname AS VARCHAR(1000)) AS hl
               FROM     tempdb.dbo.T1 Root
               WHERE    Root.ParentID IS NULL
               UNION ALL
               SELECT   Recurse.AccountId AS acid ,
                        Recurse.ParentId ParentId ,
                        Root.Hlvl + 1 AS hlvl ,
                        CAST(Root.HPa + '.' + Recurse.AccountId AS VARCHAR(1000)) AS hpa ,
                        CAST(recurse.AccountId + '.' + Root.hid AS VARCHAR(1000)) AS hid ,
                        CAST(REPLACE(recurse.AccountName, '.', '') + '.' + Root.hn AS VARCHAR(1000)) AS hn ,
                        CAST(Root.hs + '.' + Recurse.AccountName AS VARCHAR(1000)) AS hs ,
                        CAST(SPACE(root.hlvl * 4) + Recurse.AccountName AS VARCHAR(1000)) AS hl
               FROM     tempdb.dbo.T1 Recurse
                        INNER JOIN AccountHierarchy Root ON Root.AcId = Recurse.ParentId
             )
    UPDATE  tempdb.dbo.T1
    SET     HierarchyLevel = HLvl ,
            HPath = Hpa ,
            IdHierarchy = hid ,
            NameHierarchy = hn ,
            HierarchyLabel = hl ,
            HierarchySort = hs
    FROM    AccountHierarchy
    WHERE   AccountId = AcId;

SELECT  --HPath ,
        AccountId ,
        AccountName ,
        ParentId ,
        HierarchyLevel ,
        IdHierarchy ,
        NameHierarchy ,
        HierarchyLabel ,
        PARSENAME(IdHierarchy, 1) Acct1Id ,
        PARSENAME(NameHierarchy, 1) Acct1Name ,
        PARSENAME(IdHierarchy, 2) Acct2Id ,
        PARSENAME(NameHierarchy, 2) Acct2Name ,
        PARSENAME(IdHierarchy, 3) Acct3Id ,
        PARSENAME(NameHierarchy, 3) Acct3Name ,
        PARSENAME(IdHierarchy, 4) Acct4Id ,
        PARSENAME(NameHierarchy, 4) Acct4Name ,
        CustomerCount ,
        Cnt.TotalCustomerCount
FROM    tempdb.dbo.t1 Hier
        CROSS APPLY ( SELECT    SUM(CustomerCount) AS TotalCustomerCount
                      FROM      tempdb.dbo.t1
                      WHERE     HPath LIKE hier.HPath + '%'
                    ) Cnt
ORDER BY HierarchySort;

DROP TABLE tempdb.dbo.t1;
DROP TABLE tempdb.dbo.Account;
souplex
la source
vaillante tentative. Et c'est une génération de données d'échantillon assez douce. Je dois m'améliorer pour faire certaines de ces astuces. Je suis toujours à la recherche de cette solution élégante, j'attends.
liver.larson