PostgreSQL 遞歸公用表表達式的 (Big O) 計算複雜度是多少？
例如，以 StackOverflow #44620695 這個問題，遞歸路徑聚合和 CTE 查詢由上而下樹 postgres為例，它使用遞歸 CTE 遍歷樹結構來確定從起始節點開始的路徑。
上面的螢幕截圖顯示了輸入數據、遞歸 CTE 結果和源數據的視覺化。
遞歸 CTE 對前面的結果進行迭代——對嗎？（正如在此處接受的答案中所建議的那樣） - 那麼時間複雜度會是這樣的
O(log n)嗎？
好的，我將提出一個解決方案。以優秀的文章“ A Gentle Introduction to Algorithm Complexity Analysis ”為指導，我相信我的問題（上圖）中範例的最壞情況復雜性如下。
鑑於此遞歸 CTE：
WITH RECURSIVE nodes(id, src, path, tgt) AS ( -- Anchor member: SELECT id, s, concat(s, '->', t), t, array[id] as all_parent_ids FROM tree WHERE s = 'a' UNION ALL -- Recursive member: SELECT t.id, t.s, concat(path, '->', t), t.t, all_parent_ids||t.id FROM tree t JOIN nodes n ON n.tgt = t.s AND t.id <> ALL (all_parent_ids) ) -- Invocation: SELECT path FROM nodes;
- 在 Anchor 成員（查詢定義）處，算法從表中選擇每一行；因此，在此步驟中，最大迭代次數 (
i) 和最大大小 (n) 是表中的行數；i < n，如果指定了表內的起點。- Recursive 成員從表中選擇每一行，從錨成員中指定的位置開始，所以這裡的最大迭代次數再次為：
i ≤ n。因此，對於上面的遞歸 CTE，我相信整體複雜性是
Θ(n).
（來自您的同伴部落格）
查詢返回以下 13 行：
a->b a->b->a a->b->c a->b->d a->b->c->e a->b->d->e a->b->c->h a->b->d->e->f a->b->c->e->f a->b->c->e->f->g a->b->d->e->f->g a->b->d->e->f->g->h a->b->c->e->f->g->h執行計劃（又名解釋計劃/查詢計劃）：
CTE Scan on nodes (cost=322.86..356.54 rows=1684 width=32) (actual time=0.027..0.120 rows=13 loops=1) CTE nodes -> Recursive Union (cost=4.18..322.86 rows=1684 width=132) (actual time=0.025..0.110 rows=13 loops=1) -> Bitmap Heap Scan on tree (cost=4.18..12.65 rows=4 width=132) (actual time=0.024..0.024 rows=1 loops=1) Recheck Cond: (s = 'a'::text) Heap Blocks: exact=1 -> Bitmap Index Scan on tree_s_t_key (cost=0.00..4.18 rows=4 width=0) (actual time=0.005..0.005 rows=1 loops=1) Index Cond: (s = 'a'::text) -> Hash Join (cost=1.30..27.65 rows=168 width=132) (actual time=0.009..0.012 rows=2 loops=6) Hash Cond: (t.s = n.tgt) Join Filter: (t.id <> ALL (n.all_parent_ids)) Rows Removed by Join Filter: 0 -> Seq Scan on tree t (cost=0.00..18.50 rows=850 width=68) (actual time=0.001..0.002 rows=10 loops=6) -> Hash (cost=0.80..0.80 rows=40 width=96) (actual time=0.001..0.001 rows=2 loops=6) Buckets: 1024 Batches: 1 Memory Usage: 9kB -> WorkTable Scan on nodes n (cost=0.00..0.80 rows=40 width=96) (actual time=0.000..0.001 rows=2 loops=6)執行計劃從最內縮進到最外，從下到上閱讀。對齊的縮進操作屬於位於它們上方的父操作，縮進較少。
手術後有兩組括號，第一組是估計成本，所以我將忽略它並談論實際成本。
- CTE 的“錨”部分對應於
Bitmap Index Scan（和它之後的點陣圖堆掃描，這實際上是同一掃描的第二階段），它顯示實際行 = 1 和循環 = 1，因此我們可以簡化並假設整個操作將是 O(1)- CTE 的“遞歸”部分對應於
Hash Join. 雜湊是在 a 上創建的WorkTable，這是一個為它保留 9kB 記憶體的記憶體結構，並使用具有 1024 個可能的儲存桶的雜湊函式 - 它認為這對於查詢來說已經足夠了。初始化 WorkTable 對複雜性有何影響？是否應該忽略它，因為它是一個實現細節還是很重要？- 有
WorkTable2 行並且循環了 6 次，但是每次掃描 WorkTable 是否具有相同的內容？既然數組正在累積並且箭頭被連接到前一次迭代的 s & t，它怎麼可能呢？必須在每個循環上對其進行修改或重建。那麼 2 行的 6 次重建加上 2 行的 6 次掃描？如果不分析 Postgres C 原始碼，執行計劃中沒有顯示的實現細節很難說。- 這
WorkTable被用作 Hash 來探測散列連接中的另一個表。另一個表是tree並且有一個tree包含 10 行的順序掃描（Seq Scan），它循環了 6 次，10 * 6 = 60. 所以是的 i <= N 如您的回答中所述，但我認為說複雜性與 i 相同是不正確的，它是 i * n 因為每次迭代都是對整個tree表的順序掃描，而不僅僅是一排。- 最終查詢結果（計劃第一行中的 CTE 掃描）顯示有 13 行和 1 個循環。這 13 包括 1 個錨行
2 * 6 = 12加上Hash Join. 這算不算另外13個？我會說是的，因為這一步花費的時間不止零；遞歸聯合在 0.110 結束，CTE 掃描在 0.120 結束。所以加起來
1 (anchor) ? ( Initialize WorkTable, contributes some small unknown time complexity) 12 ( worktable scan 2 rows * 6 loops) 12 ( hash 2 rows * 6 loops) 60 ( sequential scan of 10 rows of `tree` table * 6 loops) 12 ( hash join of 2 rows * 6 loops - is this double or triple counting?) 13 ( Final CTE Scan) = 110如果 N = 10（行），那麼這更像
O(n^2)二次復雜度，類似於嵌套循環操作，這是一個合理的比較。散列連接不是嵌套循環連接，它是一種優化，但在遞歸的上下文中，它不僅僅是執行一次。
我注意到你在部落格的末尾提到了
雖然在 RDB 中嵌入複雜圖（可以說）不是一個好主意，但考慮到遞歸 CTE 似乎是一種確定樹/圖中路徑的有效算法方法，這不是原因之一
我不得不不同意。遞歸 CTE 效率不高，它們實際上是顯式循環，而循環在 SQL 中通常是壞消息。有些情況是無法避免的，但如果可能的話應該避免。不過，我同意在這個案例中使用 cypher/gremlin/ 其他一些特定於圖形的語言或圖形數據庫。與其說他們有更好的算法，不如說他們有一些很好的技巧來預先計算和記憶體路徑、祖先和後代，並在圖形建構時儲存冗餘資料結構，以加快執行時查詢。