PostgreSQL 树结构和递归 CTE 优化

Question

我试图在 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()

Answer 1

如果您确实很少需要修改这些数据，那么您可以简单地将 CTE 的结果存储在表中，并针对该表运行查询。您可以根据典型查询定义索引。
然后根据需要TRUNCATE重新填充 (和)。ANALYZE

另一方面，如果您可以将 CTE 放在单独的存储过程而不是视图中，则可以轻松地将条件放在 CTE 部分而不是最终部分SELECT（这基本上就是您查询的内容tree_view_1），这样行数就会少得多会参与递归。从查询计划来看，PostgreSQL 估计行数是基于一些与真实情况相去甚远的假设，可能会产生次优计划 - 使用 SP 解决方案可以在一定程度上减少这种影响。

编辑我可能会错过一些东西，但只是注意到在非递归术语中您不会过滤行。可能您只想在那里包含根节点（WHERE parent_id IS NULL） - 我希望通过这种方式减少行和递归。

编辑2 随着我从评论中慢慢变得清楚，我错误地认为原始问题中的递归是相反的。这里我的意思是从根节点开始并深入递归。