Re: OUTER JOIN performance regression remains in 8.3beta4

Hmm ... I think I've managed to invent a test case, and unfortunately
for you, what it shows is that 8.2 is optimizing the query incorrectly.

create table t1 (f1 int primary key);
create table t2 (f2 int primary key);
create table t3 (f3 int primary key);
insert into t1 values(53);
insert into t2 values(53);

explain select * from
t2 left join t3 on (f2 = f3)
left join t1 on (f3 = f1)
where f2 = 53;

select * from
t2 left join t3 on (f2 = f3)
left join t1 on (f3 = f1)
where f2 = 53;

What I get from this in 8.3 is

f2 | f3 | f1
----+----+----
53 | |
(1 row)

whereas 8.2 (at least at branch tip, can't say for sure about earlier
dot-releases) returns

f2 | f3 | f1
----+----+----
53 | | 53
(1 row)

which I claim is the wrong answer. If there is no matching t3 row, then
the first join should produce a null-extended row with f3=NULL, and this
row *cannot* match the t1 row with f1=53. We should therefore again do
a null-extension.

8.2 produces this plan:

Nested Loop Left Join (cost=0.00..24.82 rows=1 width=12)
-> Nested Loop Left Join (cost=0.00..16.55 rows=1 width=8)
-> Index Scan using t2_pkey on t2 (cost=0.00..8.27 rows=1 width=4)
Index Cond: (f2 = 53)
-> Index Scan using t3_pkey on t3 (cost=0.00..8.27 rows=1 width=4)
Index Cond: (f3 = 53)
-> Index Scan using t1_pkey on t1 (cost=0.00..8.27 rows=1 width=4)
Index Cond: (f1 = 53)

which shows it has incorrectly propagated the constant to replace both
of the join conditions. 8.3 is doing this:

Nested Loop Left Join (cost=0.00..24.83 rows=1 width=12)
-> Index Scan using t2_pkey on t2 (cost=0.00..8.27 rows=1 width=4)
Index Cond: (f2 = 53)
-> Nested Loop Left Join (cost=0.00..16.55 rows=1 width=8)
-> Index Scan using t3_pkey on t3 (cost=0.00..8.27 rows=1 width=4)
Index Cond: (f3 = 53)
-> Index Scan using t1_pkey on t1 (cost=0.00..8.27 rows=1 width=4)
Index Cond: (t3.f3 = t1.f1)

which shows it has replaced the f2=f3 join condition with constants,
which is safe, but has not replaced f3=f1.

If we were to write

select * from
t2 left join t3 on (f2 = f3)
left join t1 on (f2 = f1)
where f2 = 53;

then we get the three-constant-indexscans plan out of 8.3 as well. So
the first question for you is whether it is intentional that your query
joins CTHE to CHST rather than to CH.

It's possible that we could teach 8.3 to propagate the constant and keep
the join condition in cases like this; that is, after EquivalenceClass
processing we'd want to have the clauses
f2 = 53
f3 = 53 (8.3 already knows to deduce this)
f1 = 53 (this is the one at issue)
f1 = f3
where the last is not redundant because of the possibility that one side
has gone to null by the time it's applied. However, the clause f1 = 53
is OK to invent and apply at the t1 table scan because any row not
meeting this condition can certainly not contribute to the join result.
(Anyone see any flaws in that reasoning?) I'm a bit hesitant to monkey
with it at this late stage of the release process, though.

BTW, the two plans above are just about equivalent both in cost and
real-world performance, so it might look like propagating the constant
condition to f1 isn't really worth doing anyway. The problem is that
you've got a non-optimizable view in the way. Extending the example,

create view v as select *,'dummy'::text AS junk from t1;

explain select * from
t2 left join t3 on (f2 = f3)
left join v on (f3 = f1)
where f2 = 53;

8.2 generates the same plan as before, whereas 8.3 produces

Nested Loop Left Join (cost=0.00..104.55 rows=1 width=44)
-> Index Scan using t2_pkey on t2 (cost=0.00..8.27 rows=1 width=4)
Index Cond: (f2 = 53)
-> Nested Loop Left Join (cost=0.00..96.27 rows=1 width=40)
Join Filter: (t1.f1 = t3.f3)
-> Index Scan using t3_pkey on t3 (cost=0.00..8.27 rows=1 width=4)
Index Cond: (f3 = 53)
-> Seq Scan on t1 (cost=0.00..34.00 rows=2400 width=4)

and it's that seqscan that is killing performance. The reason for this
is that the v view can't be flattened due to the non-nullable output
column, so it has to be planned separately and you get a seqscan.
If we generate the constant condition f1 = 53 then it can be pushed down
into the view and so you get the indexscan anyhow, even though it's
really a separate planner invocation doing that.

Fixing this would involve some fooling with the machinations around
the left_join_clauses and right_join_clauses lists --- not sure how
big a patch would be needed.

We've also got to think about un-breaking 8.2.

[ Pokes at older branches... ] Oh, that's interesting, 8.1 seems to do
the right thing already!

Nested Loop Left Join (cost=0.00..16.50 rows=1 width=44)
Join Filter: ("outer".f3 = "inner".f1)
-> Nested Loop Left Join (cost=0.00..10.66 rows=1 width=8)
-> Index Scan using t2_pkey on t2 (cost=0.00..5.82 rows=1 width=4)
Index Cond: (f2 = 53)
-> Index Scan using t3_pkey on t3 (cost=0.00..4.82 rows=1 width=4)
Index Cond: (f3 = 53)
-> Index Scan using t1_pkey on t1 (cost=0.00..5.82 rows=1 width=4)
Index Cond: (f1 = 53)

I wonder where along the line it got broken?

regards, tom lane