Join Filter vs. Index Cond (performance regression 9.1->9.2+/HEAD)

This is distilled down from a performance regression problem that came
past on IRC earlier today:

create table t1 (a integer, b integer, c integer, primary key (a,b,c));
create table t2 (k2 integer, a integer, primary key (k2,a));
create table t3 (k3 integer, b integer, primary key (k3,b));
create table t4 (k4 integer, c integer, primary key (k4,c));
insert into t1 select i,i,i from generate_series(1,1000,20) i;
insert into t1 select 2,2,i from generate_series(1,500) i;
insert into t2 select i,i from generate_series(1,1000) i;
insert into t3 select i,i from generate_series(1,1000) i;
insert into t4 select i,i from generate_series(1,1000) i;
analyze;

explain analyze
select * from t4
left join t3 on (t4.c=t3.k3)
left join t2 on (t3.b=t2.k2)
left join t1 on (t1.a=t2.a and t1.b=t3.b and t1.c=t4.c)
where t4.k4=2;

The plan for this on 9.4.2 comes out like this:

Nested Loop Left Join (cost=1.10..17.28 rows=1 width=36) (actual time=0.089..0.448 rows=1 loops=1)
Join Filter: (t1.c = t4.c)
Rows Removed by Join Filter: 499
-> Nested Loop Left Join (cost=0.83..16.94 rows=1 width=24) (actual time=0.056..0.059 rows=1 loops=1)
-> Nested Loop Left Join (cost=0.55..16.60 rows=1 width=16) (actual time=0.044..0.046 rows=1 loops=1)
-> Index Only Scan using t4_pkey on t4 (cost=0.28..8.29 rows=1 width=8) (actual time=0.024..0.025 rows=1 loops=1)
Index Cond: (k4 = 2)
Heap Fetches: 1
-> Index Only Scan using t3_pkey on t3 (cost=0.28..8.29 rows=1 width=8) (actual time=0.011..0.012 rows=1 loops=1)
Index Cond: (k3 = t4.c)
Heap Fetches: 1
-> Index Only Scan using t2_pkey on t2 (cost=0.28..0.33 rows=1 width=8) (actual time=0.010..0.011 rows=1 loops=1)
Index Cond: (k2 = t3.b)
Heap Fetches: 1
-> Index Only Scan using t1_pkey on t1 (cost=0.28..0.33 rows=1 width=12) (actual time=0.025..0.281 rows=500 loops=1)
Index Cond: ((a = t2.a) AND (b = t3.b))
Heap Fetches: 500

Whereas 9.1 gives this:

Nested Loop Left Join (cost=0.00..33.12 rows=1 width=36) (actual time=0.074..0.096 rows=1 loops=1)
-> Nested Loop Left Join (cost=0.00..24.83 rows=1 width=24) (actual time=0.054..0.069 rows=1 loops=1)
-> Nested Loop Left Join (cost=0.00..16.55 rows=1 width=16) (actual time=0.039..0.048 rows=1 loops=1)
-> Index Scan using t4_pkey on t4 (cost=0.00..8.27 rows=1 width=8) (actual time=0.020..0.022 rows=1 loops=1)
Index Cond: (k4 = 2)
-> Index Scan using t3_pkey on t3 (cost=0.00..8.27 rows=1 width=8) (actual time=0.009..0.011 rows=1 loops=1)
Index Cond: (t4.c = k3)
-> Index Scan using t2_pkey on t2 (cost=0.00..8.27 rows=1 width=8) (actual time=0.008..0.010 rows=1 loops=1)
Index Cond: (t3.b = k2)
-> Index Scan using t1_pkey on t1 (cost=0.00..8.27 rows=1 width=12) (actual time=0.013..0.016 rows=1 loops=1)
Index Cond: ((a = t2.a) AND (b = t3.b) AND (c = t4.c))

In the real example, the join filter in the 9.4.2 plan was discarding 40
million rows, not just 500, so the performance impact was quite serious.

Obviously it makes little sense to use an (a,b,c) index to look up just
(a,b) and then filter on c; the question is, what is the planner doing
that leads it to get this so wrong? Finding a workaround for it was not
easy, either - the only thing that I found that worked was replacing the
t1 join with a lateral join with an OFFSET 0 clause to nobble the
planner entirely.

--
Andrew (irc:RhodiumToad)