主页 / dba / 问题 / 20978
Accepted
Bruno
Asked: 2012-07-17 10:57:41 +0800 CST

PostgreSQL树结构和递归CTE优化

  • 772

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

1 个回答

  1. Best Answer

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

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

    编辑我可能会错过一些东西，但只是注意到在非递归术语中你没有过滤行。可能您只想在其中包含根节点 ( WHERE parent_id IS NULL) - 我希望这样的行和递归要少得多。

    编辑 2 因为从评论中我慢慢明白了，我误以为原始问题中的递归是相反的。这里我的意思是从根节点开始，深入递归。

    • 2

相关问题