8.2 bug with outer join reordering

Thanks to rcohen on IRC yesterday for pointing this out and providing
his query + EXPLAIN output.

It looks like he still hasn't posted it to -bugs, and I was finally able
to reproduce it in a narrower, self contained test case, so I'm posting
this right now.

On 8.1 this returns 1 record. On 8.2 this returns 100000. It appears to
be applying the filter too soon, and then it does an outer join which
violates the WHERE.

Regards,
    Jeff Davis

test=> SELECT version();
                                              version
-------------------------------------------------------------------------
 PostgreSQL 8.2.0 on i686-pc-linux-gnu, compiled by GCC gcc (GCC) 3.4.5
20051201 (Red Hat 3.4.5-2)
(1 row)

test=> CREATE TABLE t1 (a int, b int);
CREATE TABLE
test=> CREATE TABLE t2 (c int, d int);
CREATE TABLE
test=> CREATE TABLE t3 (e int, f int);
CREATE TABLE
test=> CREATE TABLE t4 (g int, h int);
CREATE TABLE
test=>
test=> INSERT INTO t1 SELECT generate_series, 1 from generate_series
(1,100000);
INSERT 0 100000
test=> COPY t2 FROM stdin DELIMITER ',';
Enter data to be copied followed by a newline.
End with a backslash and a period on a line by itself.
>> 1,19
2,22
3,23
4,24
5,25
6,26
7,27
8,28
9,29
10,30
11,31
\.>> >> >> >> >> >> >> >> >> >> >>
test=> INSERT INTO t3 SELECT generate_series, 10 from generate_series
(1,10000);
INSERT 0 10000
test=> INSERT INTO t4 VALUES
test->   (19,4);
INSERT 0 1
test=>
test=> CREATE INDEX t3_e_idx ON t3 (e);
CREATE INDEX
test=> CREATE INDEX t4_g_idx ON t4 (g);
CREATE INDEX
test=> SELECT COUNT(*) FROM
test-> t1
test-> LEFT JOIN
test-> t2 ON ( t1.a = t2.c )
test-> LEFT JOIN
test-> t3 ON ( t2.d = t3.e )
test-> LEFT JOIN
test-> t4 ON ( t2.d = t4.g )
test-> WHERE ( t3.e = 19 OR t4.g = 19);
 count
--------
 100000
(1 row)

test=> EXPLAIN SELECT COUNT(*) FROM
test-> t1
test-> LEFT JOIN
test-> t2 ON ( t1.a = t2.c )
test-> LEFT JOIN
test-> t3 ON ( t2.d = t3.e )
test-> LEFT JOIN
test-> t4 ON ( t2.d = t4.g )
test-> WHERE ( t3.e = 19 OR t4.g = 19);
                                              QUERY PLAN
-------------------------------------------------------------------------
 Aggregate  (cost=831486.42..831486.43 rows=1 width=0)
   ->  Merge Left Join  (cost=22541.80..715990.92 rows=46198200 width=0)
         Merge Cond: (t1.a = t2.c)
         ->  Sort  (cost=10626.30..10864.44 rows=95254 width=4)
               Sort Key: t1.a
               ->  Seq Scan on t1  (cost=0.00..1443.54 rows=95254
width=4)
         ->  Sort  (cost=11915.49..12157.99 rows=97000 width=4)
               Sort Key: t2.c
               ->  Hash Left Join  (cost=136.35..2554.63 rows=97000
width=4)
                     Hash Cond: (t2.d = t4.g)
                     Filter: ((t3.e = 19) OR (t4.g = 19))
                     ->  Merge Right Join  (cost=135.34..2061.34
rows=97000 width=12)
                           Merge Cond: (t3.e = t2.d)
                           ->  Index Scan using t3_e_idx on t3
(cost=0.00..446.00 rows=10000 width=4)
                           ->  Sort  (cost=135.34..140.19 rows=1940
width=8)
                                 Sort Key: t2.d
                                 ->  Seq Scan on t2  (cost=0.00..29.40
rows=1940 width=8)
                     ->  Hash  (cost=1.01..1.01 rows=1 width=4)
                           ->  Seq Scan on t4  (cost=0.00..1.01 rows=1
width=4)
(19 rows)

test=>