CTE Recursive

於 MSDN 「Recursive Queries Using Common Table Expressions」所說，遞迴的 CTE 必須包含兩個部份，一個是固定部份，另一個則是遞迴部份。而整個遞迴 CTE 的架構長的如下所示：

WITH cte_name ( column_name [,...n] )
AS
(
CTE_query_definition –- 固定部份的定義.
UNION ALL
CTE_query_definition –- 遞迴部份的定義，且參考了 cte_name
)
-- 使用 CTE 的宣告
SELECT * FROM cte_name

舉一個範例來說明，假設某家公司從 BOSS 開始，下面分了 AP 與 CT 兩個事業處，而每個事業處底下又分了好幾個部門。

create table #tmp(CompanyID int not null primary key,
ParentCompanyID int null,
CompanyName nvarchar(50) )

insert into #tmp (CompanyID,ParentCompanyID,CompanyName)
values
(1,NULL,'BOSS')

insert into #tmp (CompanyID,ParentCompanyID,CompanyName)
values
(2,1,'AP')

insert into #tmp (CompanyID,ParentCompanyID,CompanyName)
values
(3,1,'CT')

insert into #tmp (CompanyID,ParentCompanyID,CompanyName)
values
(4,2,'E100')

insert into #tmp (CompanyID,ParentCompanyID,CompanyName)
values
(5,2,'E200')

insert into #tmp (CompanyID,ParentCompanyID,CompanyName)
values
(6,3,'K100')

insert into #tmp (CompanyID,ParentCompanyID,CompanyName)
values
(7,3,'K200')

insert into #tmp (CompanyID,ParentCompanyID,CompanyName)
values
(8,3,'K300')

select * from #tmp

有了以上的基本資料後，接下來透過 CTE 的遞迴語法來獲得公司的樹狀結果。

;with CompanyTree(ParentCompanyID,CompanyID,CompanyName,CompanyLevel)
as
(
 select ParentCompanyID,CompanyID,CompanyName,0 as CompanyLevel from #tmp 
 where ParentCompanyID is null
 union all
 select c.ParentCompanyID,c.CompanyID,c.CompanyName,p.CompanyLevel+1 from #tmp c
 inner join CompanyTree p on c.ParentCompanyID=p.CompanyID
)
select * from CompanyTree OPTION (Maxrecursion 20)

drop table #tmp

上面 CTE 的語法中，固定部份是：

select ParentCompanyID,CompanyID,CompanyName,0 as CompanyLevel from #tmp
where ParentCompanyID is null

這語法很明顯是把父子關係裡我們所謂的根節點 Root 找出來，所以他的查詢條件是找父親索引 (ParentCompanyID) 為 NULL 的資料。自訂欄位 CompanyLevel 則是用來顯示樹狀結構的深度，由於在固定部份所取得的都是 Root 資料，所以樹狀深度都是 0，所得到的結果用 T₀ 來表示 .

接下來，則是透過 UNION ALL 將遞迴部份的資料加進來。

select c.ParentCompanyID,c.CompanyID,c.CompanyName,p.CompanyLevel+1 from #tmp c
inner join CompanyTree p on c.ParentCompanyID=p.CompanyID

我們用 T₁ 來表示第 1 次迴圈的結果集合。由目前的範例，我們會獲得

主要是因為在固定部份 T₀ 我們一開始得到的是

所以透過 c.ParentCompanyID=p.CompanyID
(或視為 #tmp.ParentCompanyID = CompanyTree.CompanyID)
的關聯條件就可以得到 AP 與 CT 兩筆資料。這一次的關聯條件，翻譯成白話，就好像是問說：原始資料裡面，有誰的爸爸叫做 1 的阿？而翻譯成SQL 條件，就是：

#tmp.ParentCompanyID=1

，於是就會跑出 AP 與 CT 這兩個結果。

接著進行第 2 次迴圈後，則 T2 所得到的結果，分別是 ：

AP 的

與 BP的

這兩部份的加總，也就是 E100、E200、K100、K200。


而遞迴的特性，會一直持續的往下探尋，直到找不到資料為止，也就是從 T₁ … T_n 。
目前的範例，則是將  T₁,T₂ 這 2 層的資料回傳。
最後的樹狀結果加總 T₀ … T_n 所有資料 ，如下所示：

或許一開始會有個疑問，為什麼一定要用 UNION ALL ，為什麼一定要用 inner join，但當你試著用其他選擇，例如改成 UNION 後，會得到以下錯誤訊息：

Recursive common table expression 'CompanyTree' does not contain
a top-level UNION ALL operator.

改成 left join 後會得到

Outer join is not allowed in the recursive part of a
recursive common table expression 'CompanyTree'.

就可以發現，其他的選擇，會造成 CTE 遞迴的語法錯誤，沒得商量。

此外，CTE 其實還有一個比較特別的參數設定可以使用。由於其強大的遞迴功能，為了避免使用者因為邏輯上的錯誤而造成了無限迴圈，他提供使用者自行定義要往下探尋幾層的限制。假設你已經知道自己的樹狀結構不會超過 10 層，那你可以在程式裡面加上  OPTION (Maxrecursion 10)，當迴圈超過10層時，程式就會出現錯誤訊息而終止，不會跑無限迴圈。
超過10 層的錯誤訊息：

The statement terminated. The maximum recursion 10 has been exhausted
before statement completion.

完整程式如下：

;with CompanyTree(ParentCompanyID,CompanyID,CompanyName,CompanyLevel)
as
(
 select ParentCompanyID,CompanyID,CompanyName,0 as CompanyLevel from #tmp 
 where ParentCompanyID is null
 union all
 select c.ParentCompanyID,c.CompanyID,c.CompanyName,p.CompanyLevel+1 from #tmp c
 inner join CompanyTree p on c.ParentCompanyID=p.CompanyID
)
select * from CompanyTree OPTION (Maxrecursion 10)

這個 Maxrecursion 或許你不會想去設定，但必須要注意，即便你沒設定，但它的預設值卻幫你設定好了，預設是 100 ，也就是說，當你的探尋深度有可能超過100 時，記得要將這個參數調整為設合您的大小。他的設定範圍為 0 ~ 32767，0 則表示沒有限制，也就是說可以超過 32767，但請注意，當你的迴圈深度達到這麼深時，整個的執行效能是非常差的。


Ref:
01:Recursive Queries Using Common Table Expressions

02:一般資料表運算式(Common Table Expressions, CTE)