Estrutura de árvore do PostgreSQL e otimização recursiva de CTE

Estou tentando representar uma estrutura de árvore no PostgreSQL (8.4) para poder consultar o caminho da raiz até um determinado nó ou encontrar todos os nós dentro de um sub-ramo.

Aqui está uma tabela de teste:

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);

Cada nó é identificado por (forest_id, node_id)(pode haver outro nó com o mesmo nome em outra floresta). Cada árvore começa em um nó raiz (onde parent_idé nulo), embora eu espere apenas um por floresta.

Aqui está a exibição que usa um CTE recursivo:

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;

Esta é uma versão ligeiramente modificada do exemplo na documentação , para levar em consideração o forest_id, e que retorna rec.node_idno recursivo SELECTem vez do que seria td.node_id.

Para obter o caminho da raiz para um determinado nó, esta consulta pode ser usada:

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

Para obter uma subárvore, esta consulta pode ser usada:

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

Para obter uma árvore completa dentro de uma determinada floresta:

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

A última consulta usa o seguinte plano de consulta (que pode ser visualizado em 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)

Como esperado, isso não é muito eficiente. Estou parcialmente surpreso por não parecer usar nenhum índice.

Considerando que esses dados seriam lidos com frequência, mas raramente modificados (talvez uma pequena modificação a cada duas semanas), quais são as técnicas possíveis para otimizar essas consultas e/ou representação de dados?

EDIT: Eu também gostaria de recuperar a árvore na primeira ordem de profundidade. O uso ORDER BY pathtambém degrada substancialmente a velocidade da consulta acima.

Exemplo de programa Python para preencher a tabela com dados de teste (requer Psycopg2 ), provavelmente um pouco mais do que eu esperava em uma situação mais realista:

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()