遞歸地找到從樹中給定父節點下降的所有葉子的路徑

我正在嘗試編寫一個查詢來辨識樹結構表中特定父節點的每個最遠後代的路徑，例如：

   0     1
   |     |
   2     3
   |     |
   4     5
  / \    |
*6*  8  *7*
     |
    *9*

有很多父母，所有孩子都有一個父母，父母有0-5個孩子（但圖表很“長”——大多數父母只有一個孩子）。沒有周期。

我正在嘗試有效地辨識特定節點（而不是任何中間節點）的最遠後代的路徑。例如在上面：

• get_leaf_paths(1)將返回 1 行：{1, 3, 5, 7}
• get_leaf_paths(2)將返回 2 行：{2, 4, 6}和{2, 4, 8, 9}

樣品表：

CREATE TABLE graph (
   id bigint PRIMARY KEY,
   parent_id bigint,
   FOREIGN KEY (parent_id) REFERENCES graph(id)
);
INSERT INTO graph (id, parent_id)
   VALUES (0, NULL),
          (1, NULL),
          (2, 0),
          (3, 1),
          (4, 2),
          (5, 3),
          (6, 4),
          (7, 5),
          (8, 4),
          (9, 8);

我希望結果看起來像：

SELECT get_leaf_paths.* FROM get_leaf_paths(0);
path
-----
{0, 2, 4, 6}
{0, 2, 4, 8, 9}
(2 rows)

在我最初嘗試使用遞歸查詢的函式時，我在只選擇最遠的葉子時遇到了麻煩，特別是因為一些分支比其他分支短（例如6，9以上分支處於不同的深度）。路徑可能很深（數千或數百萬個元素），所以我還想避免為每個中間節點生成路徑的過多記憶體使用。

任何想法將不勝感激。謝謝！

WITH RECURSIVE
cte AS ( SELECT id, 
               parent_id, 
               id::TEXT path,
               NOT EXISTS ( SELECT NULL
                            FROM graph gr
                            WHERE graph.id = gr.parent_id ) is_leaf
               FROM graph 
               WHERE id = 2 /* initital node id */
        UNION ALL
        SELECT graph.id, 
               graph.parent_id, 
               cte.path || ',' || graph.id,
               NOT EXISTS ( SELECT NULL
                            FROM graph gr
                            WHERE graph.id = gr.parent_id ) 
        FROM cte JOIN graph ON cte.id = graph.parent_id)
SELECT path 
FROM cte
WHERE is_leaf

https://dbfiddle.uk/?rdbms=postgres_12&fiddle=2e40ff454f302033bf5e8cba8b0b0d85

也可以應用多個初始節點（WHERE id IN (0, 1)）。

引用自：https://dba.stackexchange.com/questions/289515