在複雜的 ERP 系統中 許多實體具有等級性質當同質物體排列時 祖先-後代關係樹 - 這是企業的組織結構（所有這些分支機構、部門和工作組）、商品目錄、工作領域、銷售點的地理位置…
事實上，沒有 ，因此不會有任何層次結構。 但即使你不「為企業」工作，你仍然很容易遇到等級關係。 這是陳腔濫調，甚至你的家譜或購物中心的平面圖也是相同的結構。
在 DBMS 中儲存這樣一棵樹的方法有很多種，但今天我們將只專注於一個選項：
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
當你凝視層次結構的深處時，它正在耐心地等待，看看你使用這種結構的「天真的」方式會有多有效。
讓我們看看出現的典型問題、它們在 SQL 中的實現，並嘗試提高它們的效能。
#1. 兔子洞有多深？
為了明確起見，讓我們接受這個結構將反映組織結構中各部門的從屬關係：部門、部門、部門、分支機構、工作小組……——無論你怎麼稱呼它們。
首先，讓我們產生 10K 元素的“樹”
INSERT INTO hier
WITH RECURSIVE T AS (
SELECT
1::integer id
, '{1}'::integer[] pids
UNION ALL
SELECT
id + 1
, pids[1:(random() * array_length(pids, 1))::integer] || (id + 1)
FROM
T
WHERE
id < 10000
)
SELECT
pids[array_length(pids, 1)] id
, pids[array_length(pids, 1) - 1] pid
FROM
T;讓我們從最簡單的任務開始 - 尋找在特定部門或層級結構中工作的所有員工 - 尋找節點的所有子節點。 獲得後代的“深度”也很好......所有這些可能都是必要的，例如，構建某種 .
如果這些後代只有幾級，數量在十幾個以內還好，但如果超過五級，而且已經有幾十個後代了，那就可能出問題了。 讓我們看看傳統的樹狀搜尋選項是如何編寫（和工作）的。 但首先，讓我們先確定哪些節點對我們的研究最有趣。
最多的 “深的” 子樹：
WITH RECURSIVE T AS (
SELECT
id
, pid
, ARRAY[id] path
FROM
hier
WHERE
pid IS NULL
UNION ALL
SELECT
hier.id
, hier.pid
, T.path || hier.id
FROM
T
JOIN
hier
ON hier.pid = T.id
)
TABLE T ORDER BY array_length(path, 1) DESC; id | pid | path
---------------------------------------------
7624 | 7623 | {7615,7620,7621,7622,7623,7624}
4995 | 4994 | {4983,4985,4988,4993,4994,4995}
4991 | 4990 | {4983,4985,4988,4989,4990,4991}
...最多的 “寬的” 子樹：
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
對於這些查詢，我們使用典型的 遞迴連接:
顯然，使用這個請求模型 迭代次數將與後代總數相符 （其中有幾十個），這可能需要相當大量的資源，因此也需要時間。
讓我們檢查一下「最寬」的子樹：
WITH RECURSIVE T AS (
SELECT
id
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
hier.id
FROM
T
JOIN
hier
ON hier.pid = T.id
)
TABLE T;
如預期，我們找到了全部 30 筆記錄。 但他們為此花費了總時間的 60% - 因為他們還在索引中進行了 30 次搜尋。 能不能少做點？
按索引批量校對
我們需要對每個節點進行單獨的索引查詢嗎？ 事實證明不是——我們可以從索引中讀取 在一次通話中同時使用多個按鍵 在...的幫助下 = ANY(array).
在每個這樣的標識符組中，我們可以透過「節點」來取得上一個步驟中找到的所有 ID。 也就是說，在接下來的每一步中，我們都會 一次搜尋某個級別的所有後代.
只是，問題來了， 在遞歸選擇中，您無法在嵌套查詢中存取自身，但我們需要以某種方式僅選擇在上一級找到的內容...事實證明，不可能對整個選擇進行嵌套查詢，但對其特定字段進行嵌套查詢是可能的。 而且這個欄位也可以是一個陣列——這就是我們需要使用的 ANY.
聽起來有點瘋狂，但在圖中一切都很簡單。
WITH RECURSIVE T AS (
SELECT
ARRAY[id] id$
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
ARRAY(
SELECT
id
FROM
hier
WHERE
pid = ANY(T.id$)
) id$
FROM
T
WHERE
coalesce(id$, '{}') <> '{}' -- условие выхода из цикла - пустой массив
)
SELECT
unnest(id$) id
FROM
T;
這裡最重要的甚至不是 及時獲勝1.5倍，並且我們減去了更少的緩衝區，因為我們只有 5 次對索引的調用，而不是 30 次！
額外的好處是，在最終取消嵌套之後，標識符將保持按“級別”排序。
節點標誌
下一個有助於提高性能的考慮因素是 - “葉子”不能生孩子，也就是說，對他們來說根本不需要「往下看」。 在製定我們的任務時，這意味著如果我們沿著部門鏈到達一名員工，那麼就沒有必要沿著這個分支進一步尋找。
讓我們進入我們的表 額外的 boolean-場地，它會立即告訴我們樹中的這個特定條目是否是一個「節點」——也就是說，它是否可以有後代。
ALTER TABLE hier
ADD COLUMN branch boolean;
UPDATE
hier T
SET
branch = TRUE
WHERE
EXISTS(
SELECT
NULL
FROM
hier
WHERE
pid = T.id
LIMIT 1
);
-- Запрос успешно выполнен: 3033 строк изменено за 42 мс.偉大的！ 事實證明，所有樹元素中只有 30% 多一點有後代。
現在讓我們使用稍微不同的機制 - 透過以下方式連接到遞歸部分 LATERAL，這將允許我們立即訪問遞歸“表”的字段，並使用帶有基於節點的過濾條件的聚合函數來減少鍵的集合：
WITH RECURSIVE T AS (
SELECT
array_agg(id) id$
, array_agg(id) FILTER(WHERE branch) ns$
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
X.*
FROM
T
JOIN LATERAL (
SELECT
array_agg(id) id$
, array_agg(id) FILTER(WHERE branch) ns$
FROM
hier
WHERE
pid = ANY(T.ns$)
) X
ON coalesce(T.ns$, '{}') <> '{}'
)
SELECT
unnest(id$) id
FROM
T;
我們能夠再減少一次索引調用，並且 數量上贏得2倍以上 校對。
#2. 讓我們回到根源
如果您需要收集「樹上」所有元素的記錄，同時保留有關哪個來源表（以及具有哪些指標）導致其包含在樣本中的信息，則該演算法將非常有用 - 例如，生成摘要報告聚合成節點。
接下來的內容應該只被視為概念驗證，因為該請求事實證明非常麻煩。 但如果它主宰您的資料庫，您應該考慮使用類似的技術。
讓我們從幾個簡單的陳述開始：
- 資料庫中的相同記錄 最好只讀一遍.
- 來自資料庫的記錄 批量讀取效率更高比獨自一人。
現在讓我們嘗試建立我們需要的請求。
步驟1
顯然，在初始化遞歸時（沒有它我們會在哪裡！）我們必須根據初始標識符集減去葉子本身的記錄：
WITH RECURSIVE tree AS (
SELECT
rec -- это цельная запись таблицы
, id::text chld -- это "набор" приведших сюда исходных листьев
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
...
如果有人覺得「集合」儲存為字串而不是陣列很奇怪，那麼對此有一個簡單的解釋。 有一個內建的字串聚合「黏合」功能 string_agg，但不適用於數組。 雖然她 .
步驟2
現在我們將獲得一組需要進一步閱讀的部分 ID。 它們幾乎總是會在原始集合的不同記錄中重複 - 所以我們會 將他們分組，同時保留有關源葉的資訊。
但這裡有三個麻煩等著我們：
- 查詢的「子遞歸」部分不能包含聚合函數
GROUP BY. - 對遞歸「表」的參考不能位於巢狀子查詢中。
- 遞迴部分的請求不能包含CTE。
幸運的是，所有這些問題都很容易解決。 讓我們從最後開始。
遞迴部分的 CTE
在這裡 沒有 作品：
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)所以它有效，括號起作用！
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)針對遞歸「表」的巢狀查詢
嗯...無法在子查詢中存取遞歸 CTE。 但它可能在 CTE 內部！ 並且嵌套請求已經可以存取此 CTE！
GROUP BY 內部遞迴
這很不愉快，但是...我們有一個簡單的方法來模擬 GROUP BY 使用 DISTINCT ON 和視窗函數！
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!這就是它的工作原理！
SELECT DISTINCT ON((rec).pid)
(rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
tree
WHERE
(rec).pid IS NOT NULL現在我們明白為什麼數字 ID 會轉換為文字 - 這樣它們就可以用逗號分隔連接在一起！
步驟3
決賽，我們已經一無所有：
- 我們根據一組分組 ID 讀取「部分」記錄
- 我們將減去的部分與原始紙張的「集合」進行比較
- 使用“擴展”設定字串
unnest(string_to_array(chld, ',')::integer[])
WITH RECURSIVE tree AS (
SELECT
rec
, id::text chld
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
(
WITH prnt AS (
SELECT DISTINCT ON((rec).pid)
(rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
)
, nodes AS (
SELECT
rec
FROM
hier rec
WHERE
id = ANY(ARRAY(
SELECT
id
FROM
prnt
))
)
SELECT
nodes.rec
, prnt.chld
FROM
prnt
JOIN
nodes
ON (nodes.rec).id = prnt.id
)
)
SELECT
unnest(string_to_array(chld, ',')::integer[]) leaf
, (rec).*
FROM
tree;
來源： www.habr.com