PostgreSQL樹結構和遞歸CTE優化

我試圖在 PostgreSQL (8.4) 中表示樹結構，以便能夠查詢從根到給定節點的路徑或找到子分支中的所有節點。

這是一個測試表：

CREATE TABLE tree_data_1 (
   forest_id TEXT NOT NULL,
   node_id TEXT NOT NULL,
   parent_id TEXT,
   node_type TEXT,
   description TEXT,
   PRIMARY KEY (forest_id, node_id),
   FOREIGN KEY (forest_id, parent_id) REFERENCES tree_data_1 (forest_id, node_id)
);
CREATE INDEX tree_data_1_forestid_parent_idx ON tree_data_1(forest_id, parent_id);
CREATE INDEX tree_data_1_forestid_idx ON tree_data_1(forest_id);
CREATE INDEX tree_data_1_nodeid_idx ON tree_data_1(node_id);
CREATE INDEX tree_data_1_parent_idx ON tree_data_1(parent_id);

(forest_id, node_id)每個節點都由（在另一個林中可以有另一個同名的節點）標識。每棵樹都從一個根節點開始（其中parent_id為空），儘管我只期望每個森林有一個。

這是使用遞歸 CTE 的視圖：

CREATE OR REPLACE VIEW tree_view_1 AS
   WITH RECURSIVE rec_sub_tree(forest_id, node_id, parent_id, depth, path, cycle) AS (
       SELECT td.forest_id, td.node_id, td.parent_id, 0, ARRAY[td.node_id], FALSE FROM tree_data_1 td
       UNION ALL
       SELECT td.forest_id, rec.node_id, td.parent_id, rec.depth+1, td.node_id || rec.path, td.node_id = ANY(rec.path)
           FROM tree_data_1 td, rec_sub_tree rec
           WHERE td.forest_id = rec.forest_id AND rec.parent_id = td.node_id AND NOT cycle
    )
    SELECT forest_id, node_id, parent_id, depth, path
        FROM rec_sub_tree;

這是文件中範例的略微修改版本，考慮到forest_id, 並且返回rec.node_id遞歸SELECT而不是返回td.node_id。

獲取從根到給定節點的路徑，可以使用此查詢：

SELECT * FROM tree_view_1 WHERE forest_id='Forest A' AND node_id='...' AND parent_id IS NULL

得到一個子樹，這個查詢可以使用：

SELECT * FROM tree_view_1 WHERE forest_id='Forest A' AND parent_id='...'

在給定的森林中得到一棵完整的樹：

SELECT * FROM tree_view_1 WHERE forest_id='Forest A' AND parent_id IS NULL

最後一個查詢使用以下查詢計劃（可在explain.depesz.com上查看）：

CTE Scan on rec_sub_tree  (cost=1465505.41..1472461.19 rows=8 width=132) (actual time=0.067..62480.876 rows=133495 loops=1)
  Filter: ((parent_id IS NULL) AND (forest_id = 'Forest A'::text))
  CTE rec_sub_tree
    ->  Recursive Union  (cost=0.00..1465505.41 rows=309146 width=150) (actual time=0.048..53736.585 rows=1645992 loops=1)
          ->  Seq Scan on tree_data_1 td  (cost=0.00..6006.16 rows=247316 width=82) (actual time=0.034..975.796 rows=247316 loops=1)
          ->  Hash Join  (cost=13097.90..145331.63 rows=6183 width=150) (actual time=2087.065..5842.870 rows=199811 loops=7)
                Hash Cond: ((rec.forest_id = td.forest_id) AND (rec.parent_id = td.node_id))
                ->  WorkTable Scan on rec_sub_tree rec  (cost=0.00..49463.20 rows=1236580 width=132) (actual time=0.017..915.814 rows=235142 loops=7)
                      Filter: (NOT cycle)
                ->  Hash  (cost=6006.16..6006.16 rows=247316 width=82) (actual time=1871.964..1871.964 rows=247316 loops=7)
                      ->  Seq Scan on tree_data_1 td  (cost=0.00..6006.16 rows=247316 width=82) (actual time=0.017..872.725 rows=247316 loops=7)
Total runtime: 62978.883 ms
(12 rows)

正如預期的那樣，這不是很有效。我對它似乎沒有使用任何索引感到部分驚訝。

考慮到這些數據會被經常讀取但很少修改（可能每兩週進行一次小修改），有哪些可能的技術來優化此類查詢和/或數據表示？

**編輯：**我還想以深度優先的順序檢索樹。使用ORDER BY path也會大大降低上述查詢的速度。

---

用測試數據填充表的範例 Python 程序（需要Psycopg2），可能比我在更現實的情況下預期的要多一點：

from uuid import uuid4
import random
import psycopg2

random.seed(1234567890)
min_depth = 3
max_depth = 6
max_sub_width = 10
next_level_prob = 0.7

db_connection = psycopg2.connect(database='...')
cursor = db_connection.cursor()
query = "INSERT INTO tree_data_1(forest_id, node_id, parent_id) VALUES (%s, %s, %s)"

def generate_sub_tree(forest_id, parent_id=None, depth=0, node_ids=[]):
   if not node_ids:
       node_ids = [ str(uuid4()) for _ in range(random.randint(1, max_sub_width)) ]
   for node_id in node_ids:
       cursor.execute(query, [ forest_id, node_id, parent_id ])
       if depth < min_depth or (depth < max_depth and random.random() < next_level_prob):
           generate_sub_tree(forest_id, node_id, depth+1)

generate_sub_tree('Forest A', node_ids=['Node %d' % (i,) for i in range(10)])
generate_sub_tree('Forest B', node_ids=['Node %d' % (i,) for i in range(10)])

db_connection.commit()
db_connection.close()

如果您確實很少需要修改這些數據，那麼您可以簡單地將 CTE 的結果儲存在一個表中，然後針對該表執行查詢。您可以根據典型查詢定義索引。

然後根據需要TRUNCATE重新填充 (and ANALYZE)。

另一方面，如果您可以將 CTE 放在單獨的儲存過程中而不是視圖中，則可以輕鬆地將條件放在 CTE 部分而不是最終部分SELECT（這基本上是您查詢的內容tree_view_1），這樣行數就會少得多將參與遞歸。從查詢計劃來看，PostgreSQL 似乎基於一些與真實相去甚遠的假設來估計行數，可能會產生次優計劃——這種影響可以通過 SP 解決方案有所減少。

編輯我可能會錯過一些東西，但只是注意到在非遞歸術語中你沒有過濾行。可能您只想在其中包含根節點 ( WHERE parent_id IS NULL) - 我希望這樣的行和遞歸要少得多。

編輯 2 因為從評論中我慢慢明白了，我誤以為原始問題中的遞歸是相反的。這裡我的意思是從根節點開始，深入遞歸。

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