Joins on inherited tables

From: apb18(at)cornell(dot)edu
To: pgsql-performance(at)postgreSQL(dot)org
Subject: Joins on inherited tables
Date: 2003-10-01 16:14:13
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-performance

In some situations, it looks like the optimizer does not chose
efficient paths for joining inherited tables. For I created a
rather trivial formulation to serve as an example. I created the table
'numbers' comprising of the columns id (int) and value (text). I also
created the table 'evens' and 'odds' that inherit numbers, with no
additional columns. Into 'evens' I placed 50000 entries, each one with
an even (unique) id and random 'value'. Likewise, for 'odds', I created
50000 odd (and unique) id fields id fields and random 'value', and
created index on all ID fields of every table that has any rows (and

so.. my tables look like this:

Table "public.numbers"
Column | Type | Modifiers
id | integer |
value | text |

Table "public.evens"
Column | Type | Modifiers
id | integer |
value | text |
"ei" btree (id)
Inherits: numbers

Table "public.odds"
Column | Type | Modifiers
id | integer |
value | text |
"oi" btree (id)
Inherits: numbers

As per the above construction, 'evens' and 'odds' both have 50000
rows. 'numbers' contains none.

Now, I created a trivial query that would use 'numbers' as an inheritor
table in a join (a very stupid one, but a join nevertheless) as
follows, which produces a terrible, but correct, plan:

select value from (SELECT 1::integer as id) as ids JOIN numbers on
( =;
Hash Join (cost=0.02..2195.79 rows=501 width=19)
Hash Cond: ("outer".id = "inner".id)
-> Append (cost=0.00..1690.50 rows=100051 width=23)
-> Seq Scan on numbers (cost=0.00..0.00 rows=1 width=23)
-> Seq Scan on evens numbers (cost=0.00..845.25 rows=50025 width=23)
-> Seq Scan on odds numbers (cost=0.00..845.25 rows=50025 width=23)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Subquery Scan ids (cost=0.00..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)

Now, I subsitute 'evens' for 'numbers', so I am now joining with a normal,
non-inherited table. The plan is much better:

select value from (SELECT 1::integer as id) as ids JOIN evens on
( =;

Nested Loop (cost=0.00..3.05 rows=2 width=19)
-> Subquery Scan ids (cost=0.00..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Index Scan using ei on evens (cost=0.00..3.01 rows=1 width=23)
Index Cond: ( = "outer".id)

I would think that the ideal plan for the first query should be a nested
loop like the second that considers indexes where possible, and it would
look as follows:

Nested Loop
-> Subquery Scan ids
-> Result
-> Append
-> Seq Scan on numbers
-> Index Scan using ei on evens
Index Cond: ( = "")
-> Index Scan using oi on odds
Index Cond: ( = "")

So.. Why wouldn't postgres use such a plan? I could think of three
- The planner wasn't considering this plan due to some
fault of its own
- That plan makes no sense and would not be able to be run in the
executor, and therefore it would be wasteful to consider it.
- It truly is more expensive than a hash join

I've pretty much ruled out the third and I suspect the second is also
untrue (though have not proven that to myself), leaving the first. If it
is indeed the second, that the plan makes no sense, someone please let me

OK, so I took a look into the optimizer and over time got a better
understanding of what's going on, though I still don't understand it
completely. Here's my theory as to what's happening:

For this query, most of the path consideration takes place in
match_unsorted_outer() in path/joinpath.c. For the 'good' query against
the non-inherited 'evens' table, the good plan is generated in the line:

bestinnerjoin = best_inner_indexscan(...);

Since an inherited table doesn't have one single index over all its
inherited tables, this call produces a null bestinnerjoin.

Later on in match_unsorted_inner(), various access paths are considered
for a nested loop. One is bestinnerjoin (when it exists), and that is
how the 'good' query gets its nested loop with an index scan.

Other paths considered for inclusion in the nested loop are
'inner_cheapest_total' and 'inner_cheapest_startup'; These plans,
presumably, contain sequential scans, which are expensive enough in the
nested loop that the nested loop plan is suboptimal compared to a hash
join, which is what happens in the 'bad' query that joins against the
inheritor table.

Now, it seems to me as if the solution would be one of the following:

- create a new bestinnerjoin plan when best_inner_indexscan
returned null, yet the current relation is an inheritor.
This bestinnerjoin plan will use the optimal Append plan
that comprises of the optimal plans for the inherited
tables that are relevant for the joins (as in the
case of the hypothetical query above where the append consists
of a number of index and sequential scans)

- Consider the optimal Append path relevant to the join
later on when considering paths for use in a nested loop.
i.e. inner_cheapest_total or inner_cheapest_startup
will have to be this good append plan.

For 2, the problem seems to be that in creating the inner_cheapest_total,
joininfo nodes for each child relation do not exist. I experimented
by just copying the parents joininfo nodes to each child, and it looked
like it was considering index scans somewhere along the line, but the
final plan chosen did not use index scans. I didn't see where it
failed. I'm kinda skeptical of 3 anyway, because the
inner_cheapest_total in the 'good' query with out inheritance does not
appear to involve index scans at all.

So.. does anybody have any advice? Am I totally off base with
my assertions that a better plan can exist when joining inherited
tables? Does my analysis of the problem and possible solutions in the
optimizer make any sense? I basically pored over the source code, read
the documentation, and did little tests here and there to arrive at my
conclusions, but cannot claim to have a good global view of how
everything works.

Thanks very much



Browse pgsql-performance by date

  From Date Subject
Next Message Christopher Browne 2003-10-01 16:21:53 Re: inferior SCSI performance
Previous Message Jason Hihn 2003-10-01 15:13:15 Ideal Hardware?