（對(duì)Nested Sets計(jì)算的替代）
Introduction
在我之前的文章中“Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets” 我們學(xué)習(xí)了一種新的发钝、高性能的方法，在不到一分鐘的時(shí)間內(nèi)將一百萬(wàn)節(jié)點(diǎn)鄰接表轉(zhuǎn)換為嵌套集。問(wèn)題是，我們所做的就是轉(zhuǎn)換汉匙。我們?nèi)匀恍枰瓿梢恍┤蝿?wù)拌倍，這些任務(wù)可能與層次結(jié)構(gòu)有關(guān)。例如纬傲，轉(zhuǎn)換只允許我們計(jì)算層次結(jié)構(gòu)問(wèn)題的答案襟衰，例如每個(gè)節(jié)點(diǎn)有多少個(gè)后代?每個(gè)節(jié)點(diǎn)的銷售額是多少贴铜？對(duì)于每一個(gè)節(jié)點(diǎn)的每一層的后代？每個(gè)節(jié)點(diǎn)的所有后代的總銷售額是多少?每個(gè)級(jí)別只有 7 個(gè)等級(jí) （典型的MLM 要求） 的后代的總銷售額是什么瀑晒？雖然嵌套的集結(jié)構(gòu)肯定會(huì)使計(jì)算這些問(wèn)題變得更容易阀湿，但是應(yīng)該有一個(gè)更簡(jiǎn)單的方法來(lái)回答這些問(wèn)題，而不是編寫(xiě)自定義代碼來(lái)分別處理每個(gè)節(jié)點(diǎn)瑰妄。它不應(yīng)該花費(fèi)比(現(xiàn)在快速)轉(zhuǎn)換到嵌套集的時(shí)間更多的時(shí)間。
本文將向您展示如何快速計(jì)算所有這些內(nèi)容映砖，并為整個(gè)百萬(wàn)個(gè)節(jié)點(diǎn)層次結(jié)構(gòu)提供更多信息 without Nested Sets.
注意间坐，對(duì)于嵌套的集，永遠(yuǎn)不會(huì)有一個(gè)替代，特別是當(dāng)您需要以正確的順序列出一個(gè)層次結(jié)構(gòu)的成員或進(jìn)行“drill downs”（深入分析竹宋？）時(shí)劳澄。但是我們可以這樣做，這樣你就不需要在很多情況下計(jì)算你可能會(huì)詢問(wèn)等級(jí)的東西蜈七。
Who This Article is For
本文針對(duì)的是那些已經(jīng)至少對(duì)層次結(jié)構(gòu)有基本了解的人秒拔，比如鄰接表是什么，以及它應(yīng)該如何維護(hù)飒硅。本文還需要對(duì)t-sql有一個(gè)很好的理解砂缩，還有一些"Black Arts"的方法（like the Tally Table, for example），這是由DBA的良好社區(qū)開(kāi)發(fā)的三娩。
這篇文章中有一些術(shù)語(yǔ)庵芭，在前一篇文章中已經(jīng)討論過(guò)了。出于這個(gè)原因雀监，本文還假設(shè)您已經(jīng)閱讀并理解了前面的文章:http://www.sqlservercentral.com/articles/Hierarchy/94040/.
最后但并非最不重要的是双吆，有一些存儲(chǔ)過(guò)程構(gòu)建了從前一篇文章中提出的測(cè)試數(shù)據(jù)，并且在本文末尾的“參考資料”一節(jié)中介紹了這些數(shù)據(jù)会前。這些procs是如何工作的好乐，遠(yuǎn)遠(yuǎn)超出了本文的范圍。如果您想知道更多關(guān)于它們是如何工作的瓦宜，那么procs本身就包含了一些很重的文檔蔚万，這些文檔應(yīng)該能夠滿足您的好奇心(并且感謝您的好奇心！)
The Example Hierarchy and Quick Review（示例層次結(jié)構(gòu)和快速回顧）
如果您執(zhí)行附帶的“BuildSmallEmployeeTable”存儲(chǔ)過(guò)程歉提，沒(méi)有參數(shù)笛坦，那么它將在TempDB中構(gòu)建一個(gè)“Employee”表，它看起來(lái)就像我們之前在轉(zhuǎn)換到嵌套集時(shí)構(gòu)建的Bowers苔巨。
圖形上版扩，它看起來(lái)像下面的。
我們使用一個(gè)名為“dbo.RebuildNestedSets”的存儲(chǔ)過(guò)程的形式侄泽，使用一些高性能代碼從一個(gè)鄰接表轉(zhuǎn)換到嵌套集礁芦。“重新構(gòu)建”的集合“也被連接了”悼尾。
總結(jié)一下存儲(chǔ)過(guò)程,它首先運(yùn)行rCTE(遞歸CTE)以生成需要構(gòu)建嵌套集的幾列信息,然后它運(yùn)行下面的代碼來(lái)實(shí)際構(gòu)建嵌套的集合
--===== Declare a working variable to hold the result of the calculation
-- of the LeftBower so that it may be easily used to create the
-- RightBower in a single scan of the final table.
DECLARE @LeftBower INT
;
--===== Create the Nested Sets from the information available in the table
-- and in the following CTE. This uses the proprietary form of UPDATE
-- available in SQL Serrver for extra performance.
WITH cteCountDownlines AS
( --=== Count each occurance of EmployeeID in the sort path
SELECT EmployeeID = CAST(SUBSTRING(h.SortPath,t.N,4) AS INT),
NodeCount = COUNT(*) --Includes current node
FROM dbo.Hierarchy h,
dbo.HTally t
WHERE t.N BETWEEN 1 AND DATALENGTH(SortPath)
GROUP BY SUBSTRING(h.SortPath,t.N,4)
) --=== Update the NodeCount and calculate both Bowers
UPDATE h
SET @LeftBower = LeftBower = 2 * NodeNumber - HLevel,
h.NodeCount = downline.NodeCount,
h.RightBower = (downline.NodeCount - 1) * 2 + @LeftBower + 1
FROM dbo.Hierarchy h
JOIN cteCountDownlines downline
ON h.EmployeeID = downline.EmployeeID
;
我們需要知道的一件事是計(jì)算Bowers的(行話柿扣，指的是前一篇文章)，即每個(gè)節(jié)點(diǎn)的下一行(行話闺魏，指的是前一篇文章)的后代總數(shù)未状。實(shí)際執(zhí)行該操作的代碼是上述代碼的下面一行代碼。
NodeCount = COUNT(*) --Includes current node
獲得該節(jié)點(diǎn)數(shù)的關(guān)鍵在于析桥，實(shí)際上是將SortPath中的二進(jìn)制(4)employeeid拆分為SortPath司草。在即將到來(lái)的代碼中也是如此艰垂。
A More Complex Problem
讓我們將一些新信息添加到我們的小員工表中。讓我們將每個(gè)員工節(jié)點(diǎn)的總銷售額添加到一個(gè)給定的月份(不管它是什么)埋虹。小的員工組織結(jié)構(gòu)圖是這樣的猜憎。注意，每個(gè)節(jié)點(diǎn)的第4行是員工在給定月份的總銷售額搔课。
現(xiàn)在胰柑，讓我們來(lái)定義我們通常希望如何處理這些數(shù)據(jù)的嵌套集。我用黃色高亮了“Bob”爬泥，因?yàn)檫@是我們用來(lái)解釋一切的節(jié)點(diǎn)柬讨。我還用不同的顏色強(qiáng)調(diào)了Bob的下一行，這樣我們就能看到那里發(fā)生了什么急灭。這是我們想要計(jì)算的關(guān)于Bob的計(jì)算(MLMers將會(huì)喜歡這個(gè))姐浮。
1.計(jì)算Bob的下一行中節(jié)點(diǎn)的總數(shù)，包括Bob的節(jié)點(diǎn)葬馋。
2.計(jì)算每個(gè)相對(duì)級(jí)別的節(jié)點(diǎn)總數(shù),在Bob的downline 卖鲤，包括Bob的level.
3.計(jì)算Bob的downline 的總銷售額，包括Bob的節(jié)點(diǎn).
4.計(jì)算Bob的downline 每一個(gè)相對(duì)級(jí)別的總銷售額畴嘶，包括Bob的水平蛋逾。
5.計(jì)算Bob的下一行中每個(gè)相對(duì)級(jí)別的相對(duì)級(jí)別，包括Bob的級(jí)別窗悯。Bob的相對(duì)水平是1区匣。
6.計(jì)算Bob的下一行的總數(shù)量，包括Bob的級(jí)別
7.計(jì)算每一層的總數(shù)蒋院。
還有很多其他的計(jì)算方法你也可以做亏钩，比如計(jì)算每個(gè)Bob的下一行的銷售額的百分比，但是這些都取決于上面列出的7個(gè)計(jì)算欺旧，所以我把這些計(jì)算留給你姑丑。
這些計(jì)算的真正妙處在于，我們將一次性完成所有這些計(jì)算辞友，并將結(jié)果存儲(chǔ)在我稱為“Pre-Aggregated Hierarchical Table”中(有些人可能稱之為“data mart”)栅哀。我們要在計(jì)算嵌套集的相同時(shí)間內(nèi)做所有的事情。
Step 1: Create the Interim Hierarchy Table(創(chuàng)建臨時(shí)層次結(jié)構(gòu)表)
我們需要做的第一件事是將鄰接表轉(zhuǎn)換為嵌套集的第一步称龙。
面的代碼不僅將鄰接表復(fù)制到一個(gè)新表(dbo.層級(jí))留拾，它還使用遞歸CTE(簡(jiǎn)稱rCTE)來(lái)計(jì)算典型的SortPath和HLevel列。在第一篇文章中鲫尊，我對(duì)代碼所做的惟一更改是刪除與創(chuàng)建嵌套集相關(guān)的所有列痴柔，并為銷售添加一個(gè)占位符列。其他一切都和以前一樣疫向。
-- ===========================================================================
-- 1. Read ALL the nodes in a given level as indicated by the parent/
-- child relationship in the Adjacency List.
-- 2. As we read the nodes in a given level, mark each node with the
-- current level number.
-- 3. As we read the nodes in a given level, convert the EmployeeID to
-- a Binary(4) and concatenate it with the parents in the previous
-- level’s binary string of EmployeeID’s. This will build the
-- SortPath.
--===========================================================================
--===== Conditionally drop the final table to make reruns easier in SSMS.
IF OBJECT_ID('FK_Hierarchy_Hierarchy') IS NOT NULL
ALTER TABLE dbo.Hierarchy
DROP CONSTRAINT FK_Hierarchy_Hierarchy;
IF OBJECT_ID('dbo.Hierarchy','U') IS NOT NULL
DROP TABLE dbo.Hierarchy;
--===== Build the new table on-the-fly including some place holders
WITH cteBuildPath AS
( --=== This is the "anchor" part of the recursive CTE.
-- The only thing it does is load the Root Node.
SELECT anchor.EmployeeID,
anchor.ManagerID,
HLevel = 1,
SortPath = CAST(
CAST(anchor.EmployeeID AS BINARY(4))
AS VARBINARY(4000)) --Up to 1000 levels deep.
FROM dbo.Employee AS anchor
WHERE ManagerID IS NULL --Only the Root Node has a NULL ManagerID
UNION ALL
--==== This is the "recursive" part of the CTE that adds 1 for each level
-- and concatenates each level of EmployeeID's to the SortPath column.
SELECT recur.EmployeeID,
recur.ManagerID,
HLevel = cte.HLevel + 1,
SortPath = CAST( --This does the concatenation to build SortPath
cte.SortPath + CAST(Recur.EmployeeID AS BINARY(4))
AS VARBINARY(4000))
FROM dbo.Employee AS recur WITH (TABLOCK)
INNER JOIN cteBuildPath AS cte
ON cte.EmployeeID = recur.ManagerID
) --=== This final INSERT/SELECT creates an iterim working table to hold the
-- original Adjacency List, the hierarchal level of each node, and the
-- SortPath which is the binary representation of each node's upline.
-- The ISNULLs make NOT NULL columns
SELECT EmployeeID = ISNULL(sorted.EmployeeID,0),
sorted.ManagerID,
Sales = ISNULL(CAST(0 AS BIGINT),0), --Place Holder
HLevel = ISNULL(sorted.HLevel,0),
SortPath = ISNULL(sorted.SortPath,sorted.SortPath)
INTO dbo.Hierarchy
FROM cteBuildPath AS sorted
OPTION (MAXRECURSION 100) --Change this IF necessary
;
SELECT * FROM dbo.Hierarchy ORDER BY SortPath;
這是我們的努力所得到的竞帽。
請(qǐng)注意扛施，原來(lái)的鄰接表在EmployeeID和ManagerID列中存在。SortPath列與上一篇文章中的內(nèi)容相同屹篓。它包含每個(gè)EmployeeID 從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)從左到右為 Binary(4) （4 字節(jié)十六進(jìn)制） 表示。我們還計(jì)算了每個(gè)節(jié)點(diǎn)與根節(jié)點(diǎn)一起使用“1”的級(jí)別的級(jí)別匙奴。
作為一種側(cè)欄堆巧，這種類型的rCTE在本質(zhì)上不是RBAR1，因?yàn)樗幚砻總€(gè)迭代的整組行泼菌。這些集合是節(jié)點(diǎn)的整個(gè)級(jí)別谍肤，如果這是波音747飛機(jī)上的數(shù)百萬(wàn)零件，你會(huì)發(fā)現(xiàn)所有這些部分只有18個(gè)左右哗伯，而rCTE只需要進(jìn)行18次迭代荒揣。
還要注意，我們沒(méi)有添加任何索引焊刹。事實(shí)證明系任，在EmployeeID列中添加一個(gè)索引實(shí)際上會(huì)使即將到來(lái)的代碼運(yùn)行的速度大約是原來(lái)的兩倍，盡管我們會(huì)得到一個(gè)合并連接虐块。不要在這個(gè)臨時(shí)表中添加索引俩滥！如果您打算將這個(gè)表與嵌套的集計(jì)算(左和右的Bowers等等)放在一起，在完成下面的步驟之后贺奠，添加您需要的索引霜旧。
返回到當(dāng)前的代碼，我們還保留并預(yù)填充了一個(gè)銷售列儡率。讓我們填滿挂据。
Step 2: Fill in the Sales Data
您可能會(huì)為EmployeeID提供一個(gè)單獨(dú)的銷售表，并對(duì)dbo進(jìn)行更新儿普。我們創(chuàng)建的層次結(jié)構(gòu)表崎逃，用一個(gè)月的時(shí)間填充銷售列(例如)。既然這不是火箭科學(xué)箕肃，我敢肯定你已經(jīng)知道如何做這樣的事情了婚脱，我現(xiàn)在不會(huì)用一個(gè)例子來(lái)煩你(在本文末尾的最后代碼中有這樣一個(gè)例子)。
但是勺像，我需要用銷售數(shù)量填充這個(gè)示例表障贸，因?yàn)槲覀冊(cè)诒碇杏羞@么少的節(jié)點(diǎn)，我希望每個(gè)人都有相同的數(shù)據(jù)吟宦，所以我要用一些硬編碼的數(shù)據(jù)來(lái)進(jìn)行更新篮洁。這里的代碼。
--===== Add an index to expedite the update of Sales data添加一個(gè)索引來(lái)加快銷售數(shù)據(jù)的更新
ALTER TABLE dbo.Hierarchy
ADD PRIMARY KEY CLUSTERED (EmployeeID)
;
--===== Populate the Hierarchy table with current Sales data.使用當(dāng)前的銷售數(shù)據(jù)填充層次結(jié)構(gòu)表殃姓。
UPDATE h
SET h.Sales = s.Sales
FROM dbo.Hierarchy h
INNER JOIN
(
SELECT 26,200000 UNION ALL
SELECT 2, 90000 UNION ALL
SELECT 3,100000 UNION ALL
SELECT 6, 75000 UNION ALL
SELECT 8, 80000 UNION ALL
SELECT 7, 60000 UNION ALL
SELECT 12, 50000 UNION ALL
SELECT 14, 55000 UNION ALL
SELECT 17, 70000 UNION ALL
SELECT 18, 40000 UNION ALL
SELECT 20, 40000 UNION ALL
SELECT 21, 30000 UNION ALL
SELECT 39, 90000 UNION ALL
SELECT 40,120000
) s (EmployeeID, Sales)
ON h.EmployeeID = s.EmployeeID
;
SELECT * FROM dbo.Hierarchy ORDER BY SortPath
;
這是現(xiàn)在的表格袁波。
我用顏色編碼了數(shù)據(jù)瓦阐，以匹配Bob的顏色編碼和他從組織結(jié)構(gòu)圖上的下一行。如果您查看SortPath篷牌，您實(shí)際上可以看到“嵌套集”睡蟋，即使我們沒(méi)有使用嵌套集。每個(gè)新級(jí)別都包含在從左到右的前一級(jí)枷颊。
Step 3: Calculate Everything
正如您在步驟2中所看到的戳杀，如果我們將SortPath拆分為EmployeeID，并帶來(lái)銷售和HLevel列夭苗，那么我們就可以合計(jì)銷售信卡、每個(gè)節(jié)點(diǎn)的下一行節(jié)點(diǎn)的數(shù)量以及更多。我們實(shí)際上可以在一個(gè)高性能查詢中計(jì)算我們想要的所有7個(gè)項(xiàng)目题造。
同樣傍菇，這需要我們?cè)谇耙黄恼轮袆?chuàng)建的特殊的“HTally”表，它從“1”開(kāi)始界赔，按“4”計(jì)數(shù)丢习，如1、5仔蝌、9泛领、13等。這些值告訴我們每個(gè)EmployeeID的起始位置在SortPath中敛惊，以便將每個(gè)4字節(jié)(8個(gè)十六進(jìn)制字符)分配給EmployeeID一個(gè)簡(jiǎn)單的任務(wù)渊鞋。
構(gòu)建HTally表(HTally.sql)的代碼包含在本文末尾的“參考資料”一節(jié)中的ZIP文件中。現(xiàn)在請(qǐng)運(yùn)行這段代碼瞧挤。
這個(gè)步驟實(shí)際上有三個(gè)子步驟锡宋，我們將使用級(jí)聯(lián)CTEs(簡(jiǎn)稱“cCTE”)來(lái)完成這一步驟。
1.從SortPath中分離出員工特恬，并將每個(gè)銷售金額和HLevel都帶在一起执俩，這樣我們就可以在接下來(lái)的步驟中對(duì)銷售額進(jìn)行匯總。
2.按EmployeeID 和HLevel進(jìn)行聚合癌刽。我們還創(chuàng)建并計(jì)算此步驟中每個(gè)雇員的每個(gè)聚合級(jí)別的“相對(duì)級(jí)別”(RLevel)役首。
3.將一些子總數(shù)添加到步驟2中使用過(guò)濾的ROLLUP創(chuàng)建的聚合體中。這為每個(gè)EmployeeID創(chuàng)建了一個(gè)大的行显拜，并為每個(gè)相對(duì)級(jí)別(RLevel)向前計(jì)算了先前計(jì)算的子總數(shù)衡奥。
Step 3, Sub-Step 1: Split the SortPath
這段代碼與我們?cè)诘谝黄恼轮惺褂玫拇a幾乎完全相同。HTally表用于在SortPath中標(biāo)識(shí)每個(gè)EmployeeID的起始位置远荠，并將每4個(gè)字節(jié)分解矮固。EmployeeID的二進(jìn)制(4)表示轉(zhuǎn)換為一個(gè)INT，以供人類的可讀性譬淳，如果我們需要將最終表加入到原始鄰接表(或任何其他表)的最終表中档址，以獲得諸如雇員姓名之類的東西盹兢，那么就可以消除隱式轉(zhuǎn)換。
代碼還會(huì)獲取HLevel和銷售額守伸，這樣我們就可以在接下來(lái)的步驟中對(duì)銷售進(jìn)行匯總绎秒。
下面是這個(gè)子步驟的代碼。(請(qǐng)注意尼摹，代碼的每個(gè)子部分都是更大的級(jí)聯(lián)CTE的一部分)
--===== Conditionally drop the final table to make reruns easier in SSMS.
IF OBJECT_ID('dbo.Hierarchy','U') IS NOT NULL
DROP TABLE dbo.PreAggregatedHierarchy
;
WITH
cteSplit AS
(--==== Splits the path into elements (including Sales and HLevel)
-- so that we can aggregate them by EmployeeID and HLevel.
-- Can't aggregate here without including the SortPath so we don't.
SELECT EmployeeID = CAST(SUBSTRING(h.SortPath,t.N,4) AS INT),
h.HLevel, h.Sales
FROM dbo.HTally AS t
CROSS JOIN dbo.Hierarchy AS h
WHERE t.N BETWEEN 1 AND DATALENGTH(SortPath)
),
Step 3, Sub-Step 2: Aggregate the Sales by EmployeeID and HLevel（聚合）
這一步真的沒(méi)有什么魔法替裆。它是一個(gè)相當(dāng)直接的向前聚合和一個(gè)簡(jiǎn)單的組。這里唯一的“奇怪”的事情是窘问，我們通過(guò)EmployeeID分區(qū)一個(gè)簡(jiǎn)單的rownumber()來(lái)計(jì)算RLevel，并按照雇員的downline中包含的每個(gè)層次的層次結(jié)構(gòu)進(jìn)行排序宜咒。我們需要這個(gè)列(RLevel)來(lái)在即將到來(lái)的子步驟3中創(chuàng)建子總數(shù)
cteAggregate AS
(--==== Creates the aggregates and introduces the "Relative Level" column.創(chuàng)建聚合并引入“相對(duì)級(jí)別”列
-- NodeCount = Count of nodes in downline for each EmployeeID by Level按級(jí)別計(jì)算每個(gè)EmployeeID的節(jié)點(diǎn)數(shù)
-- Sales = Total Sales in downline for each EmployeeID by Level.每個(gè)員工的總銷售額按水平downline 惠赫。
SELECT EmployeeID,
HLevel,
RLevel = ROW_NUMBER() OVER (PARTITION BY EmployeeID
ORDER BY EmployeeID, HLevel),
NodeCount = COUNT(*),
Sales = SUM(CAST(Sales AS MONEY))
FROM cteSplit
GROUP BY EmployeeID, HLevel
)
Step 3, Sub-Step 3: Use ROLLUP to Create Sub-Totals by Relative Level使用ROLLUP來(lái)根據(jù)相對(duì)級(jí)別創(chuàng)建子總數(shù)
在這段代碼中有一小部分可能不太明顯的魔法。我們需要從前面的CTE中引入幾個(gè)列故黑，將它們包含在我們的最終表中。問(wèn)題是，我們實(shí)際上并不想把它們包含在這個(gè)組中吨枉，這不僅會(huì)使這個(gè)組變得更加復(fù)雜揍堰，而且還會(huì)導(dǎo)致卷起來(lái)產(chǎn)生大量不必要的行，而我們不得不扔掉這些行诗轻。
為了解決這些問(wèn)題钳宪，我們只需要將已經(jīng)聚合的數(shù)據(jù)聚合起來(lái)。由于每個(gè)EmployeeID的HLevel在這一點(diǎn)上都是獨(dú)一無(wú)二的扳炬，因此我們可以通過(guò)使用MIN聚合函數(shù)來(lái)聚合它吏颖。
ROLLUP還將創(chuàng)建一個(gè)帶有NULL EmployeeID的“grand total”行。這一行的總數(shù)實(shí)際上是不正確的恨樟，因?yàn)樗宋覀兩傻乃兄貜?fù)行的總數(shù)半醉。換句話說(shuō)，一個(gè)EmployeeID的每個(gè)相對(duì)級(jí)別的子總數(shù)將包含在每個(gè)節(jié)點(diǎn)的upline的子總數(shù)的子總數(shù)中劝术，這導(dǎo)致了一個(gè)不正確的“總體”計(jì)算缩多。為了避免在輸出中顯示這一行，我們只需將它的NULL EmployeeID轉(zhuǎn)換成一個(gè)“0”养晋，然后告訴輸出忽略這一行衬吆，使用一個(gè)過(guò)濾器忽略任何EmployeeID不具有EmployeeID的EmployeeID。
--===== Adds a "Rollup" to create all the subtotals that we need.添加一個(gè)“Rollup”來(lái)創(chuàng)建我們需要的所有子總數(shù)
-- We couldn't do this in the previous step because we didn't know what(在之前的步驟中我們無(wú)法做到這一點(diǎn)因?yàn)槲覀儾恢?
-- the "Relative Level" was for each row, yet.然而匙握，每一行的“相對(duì)級(jí)別”都是如此咆槽。
-- The HAVING eliminates unnecessary subtotals that are created.（消除創(chuàng)建的不必要的子總數(shù)）
SELECT EmployeeID = ISNULL(a.EmployeeID,0), --Convert NULL total lines to 0
HLevel = MIN(a.HLevel), --Just so we don't have to GROUP BY
RLevel = ISNULL(CAST(a.RLevel AS TINYINT),0),
NodeCount = SUM(a.NodeCount), --Just so we don't have to GROUP BY
Sales = SUM(a.Sales) --Just so we don't have to GROUP BY(這樣我們就不需要分組了
INTO dbo.PreAggregatedHierarchy
FROM cteAggregate a
GROUP BY EmployeeID, RLevel WITH ROLLUP
HAVING EmployeeID > 0 --Eliminates the NULL total lines for cleaner output 為更清潔的輸出消除空總行
;
當(dāng)然，在使用這個(gè)結(jié)果表時(shí)圈纺，我們會(huì)添加至少一個(gè)對(duì)性能至關(guān)重要的索引秦忿，但是讓我們看看在最終的“PreAggregateHierarchy”表中得到了什么麦射。
The Result Can Replace the Need for Nested Sets結(jié)果可以替代對(duì)嵌套集的需求
為了避免回顧本文的開(kāi)頭，這里有一個(gè)組織結(jié)構(gòu)圖和我們使用過(guò)的銷售數(shù)據(jù)灯谣，我添加了棕褐色的顏色(和我的色盲朋友的顏色對(duì)比鮮明的虛線)潜秋，以代表Bob的下線內(nèi)所有的銷售，包括Bob胎许。
并且峻呛，我們可以看到我們創(chuàng)建的代碼的前幾行數(shù)據(jù)。
SELECT * FROM dbo.PreAggregatedHierarchy ORDER BY EmployeeID, RLevel;
再一次辜窑，Bob是EmployeeID 3钩述，我在輸出中用顏色表示了他的行。讓我們先看一下黃色行中的Bob(在左邊的第6行)穆碎。如果你回頭看一下組織結(jié)構(gòu)圖牙勘，Bob就處于他自己的底線。相對(duì)而言所禀，他處于他的下一行的一級(jí)方面，這在RLevel列中反映為“1”。對(duì)于Bob所處的相對(duì)級(jí)別色徘，他是這個(gè)級(jí)別上唯一的節(jié)點(diǎn)恭金，這反映在NodeCount列中。Bob的銷售額也在10萬(wàn)美元褂策，這反映在銷售欄中横腿。
Bob還有另外兩個(gè)級(jí)別的下行。Vivian辙培、Bill和 Natalie在Bob’s 下一行中占據(jù)了下一個(gè)層次蔑水。相對(duì)而言，這是Bob的第二個(gè)級(jí)別扬蕊，這反映在RLevel中搀别，作為Bob的綠色行(第7行)的“2”(EmployeeID仍然是Bob的“3”),由于Bob的第二個(gè)相對(duì)級(jí)別有3個(gè)員工，所以在NodeCount中反映了這一行的“3”尾抑。這三名員工的銷售額也達(dá)到了18萬(wàn)美元這也反映在這一行的銷售欄中歇父。
Bob的第三個(gè)相對(duì)級(jí)別有2個(gè)人，其銷售總額達(dá)到$105,000再愈，所有這些都反映在RLevel榜苫、NodeCount和藍(lán)色行的銷售列(第8行)。
如果您為Bob(EmployeeID=3)取Max(RLevel)翎冲，那么您就會(huì)知道Bob在他的下一行中包含的所有級(jí)別垂睬，包括他自己。
最后但并非最不重要的是，(第5行)是Bob整個(gè)下線的總行驹饺。RLevel是“0”钳枕，表示這是一個(gè)大的總數(shù)，而不是一個(gè)相對(duì)級(jí)別的總和赏壹。NodeCount是“6”鱼炒，即Bob的下一行有多少個(gè)節(jié)點(diǎn)，包括他自己蝌借。最后昔瞧，銷售欄包含Bob的整個(gè)產(chǎn)品線的銷售總額，包括Bob菩佑。
作為一個(gè)可能被證明有用的工件自晰，每一行的原始層次結(jié)構(gòu)也被保留。例如稍坯，如果我們不僅要知道整個(gè)層次結(jié)構(gòu)的總銷售額還要知道整個(gè)層次結(jié)構(gòu)的總銷售額?您可以嘗試實(shí)現(xiàn)多維數(shù)據(jù)集缀磕，而不是使用ROLLUP或任何時(shí)間消耗和代碼冗長(zhǎng)的方法或……我們只需要記住，根節(jié)點(diǎn)將包含所有這些信息劣光。由于表中沒(méi)有空ManagerID來(lái)標(biāo)識(shí)根節(jié)點(diǎn)，所以您可能會(huì)認(rèn)為我們必須返回到原始的鄰接表來(lái)查找根節(jié)點(diǎn)的EmployeeID糟把。不是真的!我們知道绢涡，只有一個(gè)根節(jié)點(diǎn)，它可以獨(dú)自生活在HLevel 1中遣疯⌒劭桑考慮到這個(gè)想法，下面的非常簡(jiǎn)單的代碼(請(qǐng)?jiān)彙斑@個(gè)例子”)將會(huì)發(fā)現(xiàn)整個(gè)層次結(jié)構(gòu)的總銷售額和層次結(jié)構(gòu)中的每個(gè)層次的總銷售額缠犀。我們將在最終代碼中添加索引数苫，即使在一百萬(wàn)個(gè)節(jié)點(diǎn)層次結(jié)構(gòu)中，結(jié)果也幾乎是即時(shí)的辨液。
SELECT *
FROM dbo.PreAggregatedHierarchy
WHERE EmployeeID IN
(
SELECT TOP 1 EmployeeID
FROM dbo.PreAggregatedHierarchy
WHERE HLevel = 1
)
ORDER BY HLevel, RLevel;
下面是來(lái)自小員工表的結(jié)果虐急。
對(duì)你傳銷來(lái)說(shuō)，在人群中滔迈，根據(jù)你的水平驅(qū)動(dòng)資格來(lái)計(jì)算每月的支出止吁，使用這種pre-aggregated hierarchy table類型，如果您有類似于7級(jí)的單級(jí)支付結(jié)構(gòu)燎悍，那么您當(dāng)然會(huì)限制這個(gè)表只包含每個(gè)節(jié)點(diǎn)7個(gè)級(jí)別敬惦。里程碑式的獎(jiǎng)金也很容易計(jì)算。
這也適用于“二進(jìn)制”結(jié)構(gòu)谈山，盡管它對(duì)確保層次結(jié)構(gòu)的二進(jìn)制性質(zhì)沒(méi)有任何作用俄删。無(wú)論如何，你應(yīng)該已經(jīng)有了這樣的約束。
Yeah, but how fast is it?是的畴椰，但是它有多快?
在前一篇文章中臊诊，我們發(fā)現(xiàn)我們可以在大約54秒內(nèi)將一百萬(wàn)個(gè)節(jié)點(diǎn)鄰接表轉(zhuǎn)換為嵌套集。讓我們來(lái)看看這篇文章中代碼的好壞迅矛。我們將首先構(gòu)建一百萬(wàn)個(gè)節(jié)點(diǎn)層次結(jié)構(gòu)妨猩，構(gòu)建一百萬(wàn)個(gè)節(jié)點(diǎn)銷售表，然后將所有代碼與所有正確的索引放在一起秽褒，看看會(huì)發(fā)生什么壶硅。我也不打算將最終表中的下一行節(jié)點(diǎn)限制為7。我們的“一應(yīng)俱全”销斟！
The Test Data
您將在本文底部的“參考資料”一節(jié)中找到一個(gè)存儲(chǔ)過(guò)程庐椒，以構(gòu)建一個(gè)大型的雇員層次結(jié)構(gòu)表。如果您還沒(méi)有這樣做蚂踊，請(qǐng)打開(kāi)“構(gòu)建大型employeetable”的代碼并執(zhí)行它來(lái)構(gòu)建過(guò)程约谈，它都在TempDB中運(yùn)行，只是為了安全起見(jiàn)犁钟。我們不想不小心丟了任何人的真正的表棱诱。
接下來(lái)，運(yùn)行以下代碼涝动。它將同時(shí)構(gòu)建百萬(wàn)節(jié)點(diǎn)“Employee”表和百萬(wàn)行“current月中銷售”表迈勋。我的筆記本電腦大約需要11秒鐘。
-===== Do this in a nice, safe place that everyone has.
USE tempdb
;
--===== Build the million row employee table.
-- This takes about 17 seconds on my laptop and builds the correct
-- indexes, as well. Because of the second parameter, it builds
-- a more realistic hierarchy with randomized EmployeeID's.
EXEC dbo.BuildLargeEmployeeTable 1000000 ,1
;
--===== Conditionally drop the final table to make reruns easier in SSMS.
IF OBJECT_ID('dbo.CurrentMonthlySales','U') IS NOT NULL
DROP TABLE dbo.CurrentMonthlySales
;
--===== Create and randomly populate the new Sales table on-the-fly.
-- Each EmployeeID will have somewhere between $0 and $1,000 of sales.
-- This only takes about 3 seconds on my laptop.
SELECT TOP 1000000
EmployeeID = IDENTITY(INT,1,1),
Sales = ABS(CHECKSUM(NEWID()))%1001
INTO dbo.CurrentMonthlySales
FROM sys.all_columns ac1
CROSS JOIN sys.all_columns ac2
;
--===== Add the expected Clustered Index as a Primary Key
-- This only adds about a second of time to the run.
ALTER TABLE dbo.CurrentMonthlySales
ADD CONSTRAINT PK_CurrentMonthlySales
PRIMARY KEY CLUSTERED (EmployeeID)
;
Putting the Code Together 把代碼放在一起
下面的內(nèi)容可以轉(zhuǎn)換為存儲(chǔ)過(guò)程醋粟。這是我們?cè)谶@篇文章中所經(jīng)歷的所有代碼靡菇，以及一些額外的代碼來(lái)添加一個(gè)為了簡(jiǎn)單起見(jiàn)而省略的索引。如果你運(yùn)行下面的代碼,它將建立臨時(shí)表“層次結(jié)構(gòu)”(你可以很容易地轉(zhuǎn)換為一個(gè)臨時(shí)表,如果需要的話),銷售數(shù)字適用于從上面我們剛剛創(chuàng)建的“CurrentMonthlySales”表,構(gòu)建最終的“PreAggregatedHierarchy”表,并添加最后一個(gè)表的聚集索引米愿。 這里的代碼厦凤。
下面是顯示行數(shù)和持續(xù)時(shí)間的運(yùn)行結(jié)果。
(1000000 row(s) affected)
(1000000 row(s) affected)
(3231566 row(s) affected)
Duration: 00:01:01:943 (hh:mi:ss:mmm)
想象一下育苟。在一百萬(wàn)個(gè)節(jié)點(diǎn)層次結(jié)構(gòu)中较鼓，您需要做的大多數(shù)工作都是在大約62秒內(nèi)完成并存儲(chǔ)在一個(gè)現(xiàn)成的預(yù)聚合表中。
Hold the Phone! 3.3 Million Rows? Why?請(qǐng)別掛電話违柏，330萬(wàn)行笨腥，為什么？
在最后的表中勇垛，所有“額外”的行都是從哪里來(lái)的?請(qǐng)記住脖母，層次結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)都可以在下行線中有多個(gè)級(jí)別，并且每個(gè)節(jié)點(diǎn)對(duì)于該節(jié)點(diǎn)的總金額也有一個(gè)“0”級(jí)闲孤。如果您有一百萬(wàn)個(gè)節(jié)點(diǎn)層次結(jié)構(gòu)谆级，每個(gè)節(jié)點(diǎn)都有7個(gè)級(jí)別的下行線(對(duì)于離葉節(jié)點(diǎn)或葉節(jié)點(diǎn)本身最近的節(jié)點(diǎn)烤礁，實(shí)際上不可能)，這將會(huì)產(chǎn)生一個(gè)800萬(wàn)行表格肥照。100萬(wàn)的相對(duì)水平和100萬(wàn)的“0”級(jí)脚仔。
不要被這樣的行擴(kuò)展或最終表的大小嚇倒。這就是創(chuàng)建索引的目的舆绎，以確保此類表上的查找和其他聚合將以極快的速度運(yùn)行鲤脏。問(wèn)問(wèn)傳銷公司的人。800萬(wàn)行吕朵，相對(duì)瘦的桌子對(duì)他們來(lái)說(shuō)毫無(wú)意義猎醇。:-)
I Can’t Afford the 62 Seconds of “DownTime” 我無(wú)法承受62秒的“停機(jī)”
如果最后的預(yù)聚合層次結(jié)構(gòu)表，24/7/.999999999 web site or application是信息的來(lái)源努溃，如果你在經(jīng)營(yíng)一個(gè)世界范圍的多層次直銷公司硫嘶，那么你真的無(wú)法承受62秒的停機(jī)時(shí)間。在重新構(gòu)建表時(shí)梧税，您確實(shí)不想讓任何成員對(duì)“宕機(jī)”一分鐘感到憤怒沦疾。
那么你會(huì)怎么做呢?
這很簡(jiǎn)單。在構(gòu)建新版本時(shí)第队，有一個(gè)同義詞(或直通視圖)指向 pre-aggregated hierarchy表的當(dāng)前版本哮塞。完成后，只需將同義詞或視圖重新指向新表并刪除舊表(或?qū)⑵浔４鏋橐粋€(gè)月的月比較)〉是現(xiàn)在的“停機(jī)時(shí)間”是用幾秒的時(shí)間來(lái)衡量的
下個(gè)月彻桃，你做同樣的事情。只需要在兩個(gè)表之間保持“反覆”的同義詞或視圖晾蜘。
您甚至可以將主鍵的構(gòu)建包括在這樣的在線方式中，如果您讓系統(tǒng)為您命名PKs眠屎，而不是將它們添加為“命名約束”剔交。添加其他索引是件很容易的事，因?yàn)樵跀?shù)據(jù)庫(kù)中改衩，索引名稱不必是惟一的岖常，就像約束需要的那樣。
Conclusion
不要讓這成為你的“結(jié)論”葫督。您是否決定將一個(gè)鄰接表的高性能轉(zhuǎn)換與我們?cè)诘谝黄恼轮兴龅囊粯咏甙埃诒疚闹惺褂妙A(yù)聚合的層次結(jié)構(gòu)表，或者是一些有趣的進(jìn)一步的混合橄镜，我們剛剛觸及了層次結(jié)構(gòu)和所有你可以用它們做的事情偎快。正如您所看到的，代碼并不需要復(fù)雜或執(zhí)行得很差洽胶，因?yàn)槲覀冇幸话偃f(wàn)行晒夹。
這兩篇文章的主要目的是向你展示你可以擁有多層蛋糕（一種等級(jí)制度，對(duì)雙關(guān)語(yǔ)很抱歉)然后吃它，您可以享受到鄰接表的所有快速丐怯、簡(jiǎn)單和簡(jiǎn)單的維護(hù)好處喷好，并且仍然可以通過(guò)嵌套集和/或您可能使用的預(yù)聚合的層次表來(lái)報(bào)告馬力，而不是嵌套集读跷。
如果您已經(jīng)將您的層次結(jié)構(gòu)轉(zhuǎn)換為僅使用嵌套集梗搅，并且希望使用鄰接表來(lái)實(shí)現(xiàn)易于維護(hù)，請(qǐng)不要絕望效览。只需做一個(gè)web搜索“將嵌套的集合轉(zhuǎn)換為一個(gè)鄰接表”无切。我還沒(méi)有測(cè)試過(guò)您在性能方面會(huì)發(fā)現(xiàn)的任何方法，但是它們至少看起來(lái)是基于集合的钦铺，并且應(yīng)該是相當(dāng)快的订雾。除此之外，你只需要做一次矛洞。:-)
最后那當(dāng)然也是最重要的洼哎。，如果你保持“dbo.Hierarchy”為嵌套集,你沒(méi)有理由不讓你的鄰接表像以前一樣擁有最好的3個(gè)世界沼本，在"Hierarchy" table中包含嵌套集噩峦，在“預(yù)聚合層次結(jié)構(gòu)”表中對(duì)大多數(shù)層次化問(wèn)題進(jìn)行預(yù)先聚合的回答。
Acknowledgements
和前一篇文章一樣抽兆，如果沒(méi)有我從幾個(gè)個(gè)人中獲得的一些知識(shí)识补，這篇文章是不可能的，尤其是直接或間接的辫红。這里沒(méi)有提到它們的空間凭涂，但這里有一些。
首先贴妻，當(dāng)你說(shuō)“SQL中的層次結(jié)構(gòu)”或“嵌套”的時(shí)候切油，你必須站起來(lái)，向Joe Celko致敬名惩，他在這幾年里所做的工作澎胡。他逐字地寫(xiě)了這本書(shū)。
：我還想感謝Grant Fritchey的工作娩鹉，他在像我這樣的人身上做了一項(xiàng)令人難以置信的工作攻谁，他如何閱讀“執(zhí)行計(jì)劃”。我有幸和他的優(yōu)秀作品回顧了他的關(guān)于解剖執(zhí)行計(jì)劃的書(shū)籍弯予，他們教會(huì)了我如何弄清楚我需要做什么戚宦，以及添加哪些索引以使那些懶惰的代碼以光速運(yùn)行。他的一本書(shū)在SQLServerCentral上可以在下面的URL中找到锈嫩。是的阁苞，你可以免費(fèi)下載困檩，然后我必須告訴你，沒(méi)有它那槽，你的圖書(shū)館是不完整的悼沿。
http://www.sqlservercentral.com/articles/books/65831/
我還想感謝Peter Larsson(又稱“比索”)，他在教導(dǎo)人們(比如我)的“預(yù)聚合”和一些我在小組中提出的各種各樣的技巧骚灸，而不是由他們來(lái)分組糟趾。就我而言，彼得創(chuàng)造了“預(yù)聚合”這個(gè)詞甚牲，我在很多領(lǐng)域都使用了他的技術(shù)义郑，在這些領(lǐng)域，我需要?jiǎng)?chuàng)造高性能的聚合丈钙。
最后非驮，我不知道是誰(shuí)寫(xiě)了我在使用數(shù)字表格時(shí)看到的第一篇文章(Tally Tables)，但感謝你讓我的生活變得更簡(jiǎn)單雏赦。感謝Adam Machanic第一次提出“Calendar Tables”的主題劫笙，這讓我想到了關(guān)于數(shù)字(數(shù)字)的文章。
