Facts:

• PGSQL 8.4.2, Linux
• I make use of table inheritance
• Each Table contains 3 million rows
• Indexes on joining columns are set
• Table statistics (analyze, vacuum analyze) are up-to-date
• Only used table is "node" with varios partitioned sub-tables
• Recursive query (pg >= 8.4)

Now here is the explained query:

WITH    RECURSIVE
        rows AS
        (
        SELECT  *
        FROM    (
                SELECT  r.id, r.set, r.parent, r.masterid
                FROM    d_storage.node_dataset r
                WHERE   masterid = 3533933

                ) q
        UNION ALL
        SELECT  *
        FROM    (
                SELECT  c.id, c.set, c.parent, r.masterid
                FROM    rows r
                JOIN    a_storage.node c
                ON      c.parent = r.id

                ) q
        )
SELECT  r.masterid, r.id AS nodeid
FROM    rows r



                                                                           QUERY PLAN                                                                            
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
 CTE Scan on rows r  (cost=2742105.92..2862119.94 rows=6000701 width=16) (actual time=0.033..172111.204 rows=4 loops=1)
   CTE rows
     ->  Recursive Union  (cost=0.00..2742105.92 rows=6000701 width=28) (actual time=0.029..172111.183 rows=4 loops=1)
           ->  Index Scan using node_dataset_masterid on node_dataset r  (cost=0.00..8.60 rows=1 width=28) (actual time=0.025..0.027 rows=1 loops=1)
                 Index Cond: (masterid = 3533933)
           ->  Hash Join  (cost=0.33..262208.33 rows=600070 width=28) (actual time=40628.371..57370.361 rows=1 loops=3)
                 Hash Cond: (c.parent = r.id)
                 ->  Append  (cost=0.00..211202.04 rows=12001404 width=20) (actual time=0.011..46365.669 rows=12000004 loops=3)
                       ->  Seq Scan on node c  (cost=0.00..24.00 rows=1400 width=20) (actual time=0.002..0.002 rows=0 loops=3)
                       ->  Seq Scan on node_dataset c  (cost=0.00..55001.01 rows=3000001 width=20) (actual time=0.007..3426.593 rows=3000001 loops=3)
                       ->  Seq Scan on node_stammdaten c  (cost=0.00..52059.01 rows=3000001 width=20) (actual time=0.008..9049.189 rows=3000001 loops=3)
                       ->  Seq Scan on node_stammdaten_adresse c  (cost=0.00..52059.01 rows=3000001 width=20) (actual time=3.455..8381.725 rows=3000001 loops=3)
                       ->  Seq Scan on node_testdaten c  (cost=0.00..52059.01 rows=3000001 width=20) (actual time=1.810..5259.178 rows=3000001 loops=3)
                 ->  Hash  (cost=0.20..0.20 rows=10 width=16) (actual time=0.010..0.010 rows=1 loops=3)
                       ->  WorkTable Scan on rows r  (cost=0.00..0.20 rows=10 width=16) (actual time=0.002..0.004 rows=1 loops=3)
 Total runtime: 172111.371 ms
(16 rows)

(END) 

So far so bad, the planner decides to choose hash joins (good) but no indexes (bad).

Now after doing the following:

SET enable_hashjoins TO false;

The explained query looks like that:

                                                                                    QUERY PLAN                                                                                      
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 CTE Scan on rows r  (cost=15198247.00..15318261.02 rows=6000701 width=16) (actual time=0.038..49.221 rows=4 loops=1)
   CTE rows
     ->  Recursive Union  (cost=0.00..15198247.00 rows=6000701 width=28) (actual time=0.032..49.201 rows=4 loops=1)
           ->  Index Scan using node_dataset_masterid on node_dataset r  (cost=0.00..8.60 rows=1 width=28) (actual time=0.028..0.031 rows=1 loops=1)
                 Index Cond: (masterid = 3533933)
           ->  Nested Loop  (cost=0.00..1507822.44 rows=600070 width=28) (actual time=10.384..16.382 rows=1 loops=3)
                 Join Filter: (r.id = c.parent)
                 ->  WorkTable Scan on rows r  (cost=0.00..0.20 rows=10 width=16) (actual time=0.001..0.003 rows=1 loops=3)
                 ->  Append  (cost=0.00..113264.67 rows=3001404 width=20) (actual time=8.546..12.268 rows=1 loops=4)
                       ->  Seq Scan on node c  (cost=0.00..24.00 rows=1400 width=20) (actual time=0.001..0.001 rows=0 loops=4)
                       ->  Bitmap Heap Scan on node_dataset c  (cost=58213.87..113214.88 rows=3000001 width=20) (actual time=1.906..1.906 rows=0 loops=4)
                             Recheck Cond: (c.parent = r.id)
                             ->  Bitmap Index Scan on node_dataset_parent  (cost=0.00..57463.87 rows=3000001 width=0) (actual time=1.903..1.903 rows=0 loops=4)
                                   Index Cond: (c.parent = r.id)
                       ->  Index Scan using node_stammdaten_parent on node_stammdaten c  (cost=0.00..8.60 rows=1 width=20) (actual time=3.272..3.273 rows=0 loops=4)
                             Index Cond: (c.parent = r.id)
                       ->  Index Scan using node_stammdaten_adresse_parent on node_stammdaten_adresse c  (cost=0.00..8.60 rows=1 width=20) (actual time=4.333..4.333 rows=0 loops=4)
                             Index Cond: (c.parent = r.id)
                       ->  Index Scan using node_testdaten_parent on node_testdaten c  (cost=0.00..8.60 rows=1 width=20) (actual time=2.745..2.746 rows=0 loops=4)
                             Index Cond: (c.parent = r.id)
 Total runtime: 49.349 ms
(21 rows)

(END) 

-> incredibly faster, because indexes were used. Notice: Cost of the second query ist somewhat higher than for the first query.

So the main question is: Why does the planner make the first decision, instead of the second?

Also interesing:

Via

SET enable_seqscan TO false;

i temp. disabled seq scans. Than the planner used indexes and hash joins, and the query still was slow. So the problem seems to be the hash join.

Maybe someone can help in this confusing situation?

thx, R.