Merge Joins and Views

Hello,

I have a scenario with two tables, one with 5M rows and the other with
about 3.7M (a subset taken from the first table). Each is clustered
using its primary key (a single bigint column), and pg_stats shows that
the id's correlation is 1 for both tables. In addition, I have a view
over the 3.7M table that coalesces some columns that allow nulls.

So I'm running a simple query that does a left outer join from the 5M to
the 3.7M, which basically combines the information between the two (and
results in 5M rows, of course). It seems to me that the best plan
should involve two index scans and a merge join. However, I get
different plans depending on whether I use the view or the underlying
table directly, and even the use of ORDER BY -- see examples below for
details.

I don't know if this is a bug (I'm using version 8.3.0), but can anyone
please explain why the optimizer (or rule system?) behaves this way?

Thank you,
--Chris

-----Example 1:-----
SELECT * FROM a LEFT OUTER JOIN b ON (a.id = b.id);

Merge Left Join (cost=43.99..353657.21 rows=5001671 width=106) (actual
time=0.653..32529.319 rows=5000000 loops=1)
Merge Cond: (a.id = b.id)
-> Index Scan using a_pkey on a (cost=0.00..173752.86 rows=5001671
width=81) (actual time=0.353..9754.375 rows=5000000 loops=1)
-> Index Scan using b_pkey on b (cost=0.00..120980.85 rows=3713546
width=25) (actual time=0.279..8120.104 rows=3711523 loops=1) Total
runtime: 33836.167 ms

-----Example 2:-----
-- v is a view that does SELECT ... FROM b;
SELECT * FROM a LEFT OUTER JOIN v ON (a.id = v.id);

Merge Left Join (cost=580217.86..822178.09 rows=5001671 width=100)
(actual time=34260.004..67869.059 rows=5000000 loops=1)
Merge Cond: (a.id = b.id)
-> Index Scan using a_pkey on a (cost=0.00..173752.86 rows=5001671
width=81) (actual time=0.270..10104.528 rows=5000000 loops=1)
-> Materialize (cost=580217.86..626637.18 rows=3713546 width=19)
(actual time=34259.696..43199.389 rows=3711523 loops=1)
-> Sort (cost=580217.86..589501.72 rows=3713546 width=19)
(actual time=34259.679..39448.310 rows=3711523 loops=1)
Sort Key: b.id
Sort Method: external sort Disk: 136632kB
-> Seq Scan on b (cost=0.00..61693.46 rows=3713546
width=25) (actual time=0.094..10224.402 rows=3711523 loops=1) Total
runtime: 69202.529 ms

-----Example 3:-----
SELECT * FROM a LEFT OUTER JOIN (
SELECT * FROM v ORDER BY id
) sub ON (a.id = sub.id);

Merge Right Join (cost=0.00..390792.67 rows=5001671 width=100) (actual
time=0.497..38120.694 rows=5000000 loops=1)
Merge Cond: (b.id = a.id)
-> Index Scan using b_pkey on b (cost=0.00..120980.85 rows=3713546
width=25) (actual time=0.262..13686.064 rows=3711523 loops=1)
-> Index Scan using a_pkey on a (cost=0.00..173752.86 rows=5001671
width=81) (actual time=0.219..11233.746 rows=5000000 loops=1) Total
runtime: 39467.843 ms

Chris Mayfield <cmayfiel(at)cs(dot)purdue(dot)edu> writes:
> [ planner finds better plan with a forced ORDER BY ]

That shouldn't happen. Can you show the details of your case?
It may be something specific to the particular view definition...

regards, tom lane

See attached -- I've simplified my actual database quite a bit, but this
example shows the same results.

Thanks,
--Chris

Chris Mayfield <cmayfiel(at)cs(dot)purdue(dot)edu> writes:
> See attached -- I've simplified my actual database quite a bit, but this
> example shows the same results.

OK, here's the problem:

> CREATE VIEW v AS
> SELECT id, COALESCE(opt, 0) AS opt FROM b;

You're using this inside the nullable side of an outer join, and that
means the COALESCE() creates a problem: its output won't go to null
just because "opt" does. So the COALESCE has to be evaluated below
the outer join, which means that the view can't be "flattened" into
the upper query. You end up with a dumb seqscan that corresponds to
planning the view in isolation, and then the best way of joining that
with the other table is going to be the sort and merge join.

In the case where you introduce the intermediate sub-select, the
view *can* be flattened into that, producing
SELECT id, COALESCE(opt, 0) AS opt FROM b ORDER BY id
Again, that can't be flattened into the top query, but looking at
it in isolation the planner chooses an indexscan as the best plan
(by no means a sure thing, but it will do it if the index correlation
is high). And then the mergejoin without sort falls out from that.

So the long and the short of it is that the COALESCE acts as an
optimization fence in the presence of outer joins. We've seen this
before and there are some rough ideas about fixing it. (In fact,
I thought it was on the TODO list, but I can't find an entry now.)
Don't hold your breath though --- it'll take major planner surgery.

regards, tom lane

"Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> In the case where you introduce the intermediate sub-select, the
> view *can* be flattened into that, producing
> SELECT id, COALESCE(opt, 0) AS opt FROM b ORDER BY id
> Again, that can't be flattened into the top query, but looking at
> it in isolation the planner chooses an indexscan as the best plan
> (by no means a sure thing, but it will do it if the index correlation
> is high). And then the mergejoin without sort falls out from that.
>
> So the long and the short of it is that the COALESCE acts as an
> optimization fence in the presence of outer joins. We've seen this
> before and there are some rough ideas about fixing it. (In fact,
> I thought it was on the TODO list, but I can't find an entry now.)
> Don't hold your breath though --- it'll take major planner surgery.

In this case isn't all the planner needs the pathkey list to give it a hint
that that ordering might be useful? It can't re-order the join but it can
still try to produce those rows in any order which can be useful for the upper
joins.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's PostGIS support!

Thank you for your prompt reply, I appreciate your insight on this.

> So the COALESCE has to be evaluated below the outer join, which means
> that the view can't be "flattened" into the upper query.
> ...
> So the long and the short of it is that the COALESCE acts as an
> optimization fence in the presence of outer joins. We've seen this
> before and there are some rough ideas about fixing it.

You may already have this rough idea somewhere, but it seems to me that
the view could be flattened into the upper query as long as the join
predicates don't depend on coalesced columns. In the examples I sent,
even if the COALESCE is evaluated at the very end of the query, the
merge join (on the id columns) would still be correct.

--Chris

"Chris Mayfield" <cmayfiel(at)cs(dot)purdue(dot)edu> writes:

> You may already have this rough idea somewhere, but it seems to me that the
> view could be flattened into the upper query as long as the join predicates
> don't depend on coalesced columns. In the examples I sent, even if the
> COALESCE is evaluated at the very end of the query, the merge join (on the id
> columns) would still be correct.

I don't remember the example but that's not true in general, consider
something like

select *
from a
left outer join (
select *, coalesce(b.x,'foo') from b
) as b
using (a.y=b.y)

The coalesce() doesn't depend on any join predicates, but if it's evaluated
late it will be 'foo' for all the non-matching records instead of NULL.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's 24x7 Postgres support!

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
>> Don't hold your breath though --- it'll take major planner surgery.

> In this case isn't all the planner needs the pathkey list to give it a hint
> that that ordering might be useful?

You could maybe make that work if you were willing to speculatively
re-plan the entire subquery for each potentially useful ordering.
I think that would chew an unacceptable number of cycles though.
The upper planner doesn't have any clue about what indexes are available
in the lower query, so it would end up requesting a lot of useless
re-plans.

In any case the nullable-targetlist restriction causes a whole lot
of other problems that this wouldn't address. I'd rather spend my
time on solving the more general problem.

regards, tom lane

Chris Mayfield <cmayfiel(at)cs(dot)purdue(dot)edu> writes:
>>> So the long and the short of it is that the COALESCE acts as an
>>> optimization fence in the presence of outer joins. We've seen this
>>> before and there are some rough ideas about fixing it.

> You may already have this rough idea somewhere, but it seems to me that
> the view could be flattened into the upper query as long as the join
> predicates don't depend on coalesced columns. In the examples I sent,
> even if the COALESCE is evaluated at the very end of the query, the
> merge join (on the id columns) would still be correct.

But the output would not be: the join column would fail to go to null
when it was supposed to. See the example that made us put in that
restriction in the first place:
http://archives.postgresql.org/pgsql-bugs/2001-04/msg00223.php

regards, tom lane