Обсуждение: 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=>

Jeff Davis <pgsql@j-davis.com> writes:
> 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.

AFAICS the outer join reordering is perfectly legal --- the problem is
that the WHERE condition is being allowed to bubble down too far.
I can't reproduce it with less than four tables, so it's a pretty
weird corner case.  Apparently there's something wrong with
distribute_qual_to_rels' logic for determining qual placement, but
I'm not sure what yet ...

            regards, tom lane

I wrote:
> I can't reproduce it with less than four tables, so it's a pretty
> weird corner case.  Apparently there's something wrong with
> distribute_qual_to_rels' logic for determining qual placement, but
> I'm not sure what yet ...

OK, I've localized the problem and been able to reduce it to a
three-table example.  Using the regression database:

select count(*) from tenk1 a left join tenk1 b on (a.unique1=b.unique1) left join onek c on (b.unique1=c.unique1)
where case c.ten when 1 then true else false end;

This should report 100, but in 8.2 it's reporting 10000, because the
WHERE condition is being pushed down below the outer join with "a".
(Note: you might think the WHERE should be just "c.ten = 1", but the
planner understands that that's strict and reduces all the left joins
to plain joins, hiding the bug.  It's not bright enough to see the
CASE as strict, however.)

The problem comes in distribute_qual_to_rels() where it's trying to
decide the minimum set of relations that have to be joined before the
WHERE qual can be applied:
        * For a non-outer-join qual, we can evaluate the qual as soon as (1)        * we have all the rels it mentions,
and(2) we are at or above any        * outer joins that can null any of these rels and are below the        * syntactic
locationof the given qual. To enforce the latter, scan        * the oj_info_list and merge the required-relid sets of
anysuch OJs        * into the clause's own reference list.  At the time we are called,        * the oj_info_list
containsonly outer joins below this qual.
 

The oj_info_list contains two outer joins, respectively having
min_lefthand = a    min_righthand = b
min_lefthand = b    min_righthand = c

which (correctly) asserts than we can do either the a/b or b/c join
first ... but not a/c first.  However, since the WHERE qual mentions
only c, distribute_qual_to_rels concludes that it can be applied as
soon as the b/c join is formed.  And because of the relative sizes
of the tables, the planner prefers to do that join before the a/c one.

The reason the bug doesn't exist in 8.1 and older is that those releases
applied essentially this logic using the *syntactic* sets of relations
contained in different levels of outer join, and so a qual using only
(c) would have a and b added to it based on the syntax tree alone.

I think that this can be fixed by having the code iterate over the
oj_info_list repeatedly, until unioning adds no more rels.  That is, in
the first pass we'd have (c) and we'd add b because c appears in the RHS
of the second OJ; then in the second pass we'd start with (b,c) and add
a because b appears in the RHS of the first OJ; then the third pass
would start with (a,b,c), find nothing to add, and be done.  This is
appropriate because an OJ having b on its RHS must in fact have been
syntactically above the b/c join --- the only reason it doesn't have c
in its RHS now is that make_outerjoininfo() decided it was safe to
interchange the ordering of the two OJs.  But a qual coming from above
both OJs can't be allowed to bubble down below either.

Comments?  Anyone see any remaining holes in this logic?
        regards, tom lane