Mengoptimalkan hierarki CTE

15

Perbarui di bawah ini

Saya memiliki daftar akun dengan arsitektur akun khusus akun induk / orang tua untuk mewakili hierarki akun (SQL Server 2012). Saya membuat VIEW menggunakan CTE untuk memilah-milah hierarki, dan secara keseluruhan itu bekerja dengan indah, dan sebagaimana dimaksud. Saya dapat meminta hierarki di tingkat mana pun, dan melihat cabang dengan mudah.

Ada satu bidang logika bisnis yang perlu dikembalikan sebagai fungsi hierarki. Bidang di setiap catatan akun menjelaskan ukuran bisnis (kami akan menyebutnya CustomerCount). Logika yang saya perlu laporkan harus menggulung CustomerCount dari seluruh cabang. Dengan kata lain, diberikan akun, saya perlu meringkas nilai-nilai customercount untuk akun itu bersama dengan setiap anak di setiap cabang di bawah akun di sepanjang hierarki.

Saya berhasil menghitung bidang menggunakan bidang hierarki yang dibangun dalam CTE, yang terlihat seperti acct4.acct3.acct2.acct1. Masalah yang saya hadapi adalah membuatnya berjalan cepat. Tanpa bidang terhitung ini, kueri berjalan dalam ~ 3 detik. Ketika saya menambahkan di bidang terhitung, itu berubah menjadi permintaan 4 menit.

Ini adalah versi terbaik yang bisa saya dapatkan dengan mengembalikan hasil yang benar. Saya mencari ide tentang bagaimana saya bisa merestrukturisasi ini SEBAGAI PANDANGAN tanpa pengorbanan besar untuk kinerja.

Saya mengerti alasan mengapa ini berjalan lambat (harus menghitung predikat dalam klausa where), tetapi saya tidak bisa memikirkan cara lain untuk menyusunnya dan masih mendapatkan hasil yang sama.

Berikut ini beberapa contoh kode untuk membuat tabel dan melakukan CTE persis seperti yang berfungsi di lingkungan saya.

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

11/20/2013 UPDATE

Beberapa solusi yang disarankan membuat jus saya mengalir, dan saya mencoba pendekatan baru yang mendekati, tetapi memperkenalkan hambatan baru / berbeda. Sejujurnya, saya tidak tahu apakah ini membutuhkan pos terpisah atau tidak, tetapi ini terkait dengan solusi masalah ini.

Apa yang saya putuskan adalah bahwa yang membuat jumlah (customercount) menjadi sulit adalah identifikasi anak-anak dalam konteks hierarki yang dimulai dari atas dan meningkat. Jadi saya mulai dengan membuat hierarki yang dibangun dari bawah ke atas, menggunakan root yang didefinisikan oleh "akun yang bukan induk dari akun lain" dan melakukan rekursif bergabung mundur (root.parentacctid = recurse.acctid)

Dengan cara ini saya bisa menambahkan jumlah pelanggan anak ke orang tua saat rekursi terjadi. Karena saya perlu melaporkan, dan level, saya melakukan ini dari bawah ke atas selain dari atas ke bawah, kemudian bergabung dengan mereka melalui id akun. Pendekatan ini ternyata jauh lebih cepat daripada customercount kueri luar yang asli, tetapi saya mengalami beberapa kendala.

Pertama, saya secara tidak sengaja menangkap jumlah pelanggan duplikat untuk akun yang merupakan induk dari banyak anak. Saya menghitung pelanggan dua atau tiga kali lipat untuk beberapa acctid, dengan jumlah anak di sana. Solusi saya adalah membuat lagi cte yang menghitung berapa banyak node yang dimiliki acct, dan membagi acct.customercount selama rekursi, jadi ketika saya menjumlahkan seluruh cabang acct tidak dihitung ganda.

Jadi pada titik ini, hasil versi baru ini tidak benar, tetapi saya tahu mengapa. Bottomup cte membuat duplikat. Ketika rekursi berlalu, ia mencari apa saja di root (anak-anak tingkat bawah) yang merupakan anak dari sebuah akun di tabel akun. Pada rekursi ketiga, ia mengambil akun yang sama dengan yang kedua dan menempatkannya kembali.

Gagasan tentang cara melakukan bottom up cte, atau apakah ini membuat ide lain mengalir?

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
sumber
1
Sudahkah Anda mencoba memasukkan hasil CTE AccountHierarchy ke tabel temp (diindeks pada IdHierarchy) KEMUDIAN melakukan perhitungan dengan meminta dari tabel temp? Anda bisa menjalankan cara CTE diterapkan; mungkin saja Anda mengeksekusi seluruh CTE satu kali untuk SETIAP baris dalam CTE.
Jon Boulineau
1
Apa indeks pada tabel yang mendasarinya?
Mike Walsh
1
Dan berapa banyak baris dalam tabel sebenarnya?
Mike Walsh
2
@ MaxVernon Terima kasih. Belum banyak memposting, tapi jelas melihat perbedaan kualitas jawaban untuk pertanyaan yang tidak jelas.
liver.larson
@ JonBoulineau Saya telah mempertimbangkan mencoba sesuatu dengan temp tables, tetapi saya secara khusus mencoba untuk mengeksekusi ini sebagai tampilan, yang menghalangi temp tables. Adakah ide tentang cara menyiasati atau menguji pernyataan terakhir Anda?
liver.larson

Jawaban:

6

Sunting: ini adalah upaya kedua

Berdasarkan jawaban @Max Vernon, berikut adalah cara untuk mem-bypass penggunaan CTE di dalam subquery inline, yang seperti menggabungkan diri sendiri dengan CTE dan saya kira adalah alasan untuk efisiensi yang buruk. Ini menggunakan fungsi analitik yang hanya tersedia di SQL-Server versi 2012. Diuji di SQL-Fiddle

Bagian ini dapat dilewati dari membaca, ini adalah copy-paste dari jawaban 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
)

Di sini kami memesan baris CTE menggunakan IdHierarchyMatchdan kami menghitung nomor baris dan total berjalan (dari baris berikutnya hingga akhir.)

, 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  
)

Kemudian kita memiliki satu lagi CTE perantara di mana kita menggunakan total berjalan sebelumnya dan nomor baris - pada dasarnya untuk menemukan di mana titik akhir untuk cabang-cabang struktur pohon:

, 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 
) 

dan akhirnya kami membangun bagian terakhir:

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 ; 

Dan penyederhanaan, menggunakan kode yang sama cte1seperti di atas. Tes di SQL-Fiddle-2 . Harap perhatikan bahwa kedua solusi bekerja dengan asumsi bahwa Anda memiliki maksimum empat level di pohon Anda:

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 ; 

Pendekatan ketiga, dengan hanya satu CTE, untuk bagian rekursif dan kemudian hanya fungsi agregat jendela ( SUM() OVER (...)), sehingga harus bekerja dalam versi apa pun mulai 2005 ke atas. Tes di SQL-Fiddle-3 Solusi ini mengasumsikan, seperti yang sebelumnya, bahwa ada 4 level maksimum dalam hierarki pohon:

;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 ; 

Pendekatan ke-4, yang dihitung sebagai CTE perantara, tabel penutupan hierarki. Tes di SQL-Fiddle-4 . Manfaatnya adalah bahwa untuk perhitungan jumlah, tidak ada penolakan pada jumlah level.

;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ᵀᴹ
sumber
Mengoreksi kode (dan biola yang ditautkan.) Ada opsi KAPAN hilang dalam jawaban.
ypercubeᵀᴹ
+1 - Saya suka menggunakan fungsi 2012. Saya banyak belajar sekarang!
Max Vernon
ok, baru saja menghabiskan waktu menyelam, dan menyadari bahwa performanya hebat, tetapi angkanya tidak cocok. Periksa hasilnya dengan yang asli saya. Saya bisa melihat di mana Anda akan pergi dengan total berjalan, tetapi itu harus mengubah beberapa untuk bekerja sebagaimana dimaksud, dan saya belum sampai pada solusi yang tepat. Pendekatan Anda membuat saya beberapa makanan untuk bekerja dengan, tetapi itu belum solusi yang layak.
liver.larson
Oh, saya pikir itu salah besar. Mohon tidak diterima.
ypercubeᵀᴹ
Saya mencoba memperbaikinya. Ini berfungsi baik dengan sampel kecil saya, tetapi silakan uji kebenaran dengan data Anda. Tentang efisiensi, apa yang bisa saya katakan, kami hanya bisa tahu dengan pengujian (kecuali nama Anda @ Paul White).
ypercubeᵀᴹ
5

Saya percaya ini harus membuatnya lebih cepat:

;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

Saya menambahkan kolom di CTE bernama IdHierarchyMatchyang merupakan versi maju IdHierarchyuntuk memungkinkan klausa TotalCustomerCountsubquery WHEREmenjadi lebih besar.

Membandingkan perkiraan biaya subtree untuk rencana eksekusi, cara ini seharusnya sekitar 5 kali lebih cepat.

Max Vernon
sumber
Terima kasih telah meluangkan waktu untuk melihat ini. Ini lucu, itu sebenarnya insting pertama saya, dan berpikir bahwa menambahkan wildcard ke bidang hanya mungkin menggunakan SQL dinamis, dan bahkan tidak mencoba. Saya harus memeriksa. Jadi hasilnya adalah peningkatan yang nyata pada 2:49 (turun dari 3:53), tetapi tidak sebanyak yang saya harapkan. Saya akan pergi tanpa menjawab untuk melihat ide-ide lain apa yang muncul. Terima kasih lagi untuk meluangkan waktu untuk mengevaluasi ini, sungguh. Saya menghargainya.
liver.larson
FYI, baru saja melihat kesalahan sintaksis dalam implementasi saya. Kami turun ke waktu eksekusi 2:04. Masih lebih baik dari mana saya memulai. Masih membidik lebih cepat.
liver.larson
1
Hanya senang saya membantu dalam beberapa hal kecil. Saya menghabiskan sekitar 2 jam semalam mencoba untuk mengatasi masalah ini. Saya punya perasaan yang dalam di usus saya ini bisa diselesaikan dengan menggunakan beberapa jenis ROW_NUMER() OVER (ORDER BY...)atau sesuatu. Saya hanya tidak bisa mendapatkan angka yang benar dari itu. Itu pertanyaan yang sangat bagus dan menarik. Latihan otak yang bagus!
Max Vernon
Saya mencoba membuat ini menjadi tampilan skema-terikat (terwujud), untuk tujuan menambahkan indeks di IdHierarchyMatchlapangan, namun Anda tidak bisa menambahkan indeks berkerumun pada tampilan skema-terikat yang mencakup CTE. Saya ingin tahu apakah batasan ini diselesaikan dalam SQL Server 2014.
Max Vernon
2
@ MaxVernon Untuk versi 2012: SQL-Fiddle
ypercubeᵀᴹ
3

Saya mencobanya juga. Ini tidak terlalu cantik, tetapi tampaknya berkinerja lebih baik.

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;
suplex
sumber
upaya gagah berani. Dan itu beberapa contoh data generasi yang cukup manis. Saya perlu menjadi lebih baik dalam melakukan beberapa trik itu. Masih mencari solusi elegan yang saya yakin di luar sana menunggu.
liver.larson