Subject: Wrong results due to missing quals

From: Richard Guo <[email-masked]>
Date: Wed, 24 May 2023 19:19:16 +0800

Testing with SQLancer reports a wrong results issue on master and I
reduced it to the repro query below.

create table t (a int, b int);

explain (costs off)
select * from t t1 left join
    (t t2 left join t t3 full join t t4 on false on false)
    left join t t5 on t2.a = t5.a
on t2.b = 1;
                    QUERY PLAN
--------------------------------------------------
 Nested Loop Left Join
   ->  Seq Scan on t t1
   ->  Materialize
         ->  Nested Loop Left Join
               ->  Nested Loop Left Join
                     Join Filter: false
                     ->  Seq Scan on t t2
                           Filter: (b = 1)
                     ->  Result
                           One-Time Filter: false
               ->  Materialize
                     ->  Seq Scan on t t5
(12 rows)

So the qual 't2.a = t5.a' is missing.

I looked into it and found that both clones of this joinqual are
rejected by clause_is_computable_at, because their required_relids do
not include the outer join of t2/(t3/t4), and meanwhile include nullable
rels of this outer join.

I think the root cause is that, as Tom pointed out in [1], we're not
maintaining required_relids very accurately.  In b9c755a2, we make
clause_is_computable_at test required_relids for clone clauses.  I think
this is how this issue sneaks in.

To fix it, it seems to me that the ideal way would be to always compute
accurate required_relids.  But I'm not sure how difficult it is.

[1] https://www.postgresql.org/message-id/395264.1684698283%40sss.pgh.pa.us

Thanks
Richard

---

From: Tom Lane <[email-masked]>
Date: Wed, 24 May 2023 11:10:21 -0400

> So the qual 't2.a = t5.a' is missing.

Ugh.

> this is how this issue sneaks in.

Yeah.  I'm starting to think that b9c755a2 took the wrong approach.
Really, required_relids is about making sure that a qual isn't
evaluated "too low", before all necessary joins have been formed.  But
clause_is_computable_at is charged with making sure we don't evaluate
it "too high", after some incompatible join has been formed.  There's
no really good reason to suppose that required_relids can serve both
purposes, even if it were computed perfectly accurately (and what is
perfect, anyway?).

So right now I'm playing with the idea of reverting the change in
clause_is_computable_at and seeing how else we can fix the previous
bug.  Don't have anything to show yet, but one thought is that maybe
deconstruct_distribute_oj_quals needs to set up clause_relids for
clone clauses differently.  Another idea is that maybe we need another
RestrictInfo field that's directly a set of OJ relids that this clause
can't be applied above.  That'd reduce clause_is_computable_at to
basically a bms_intersect test which would be nice speed-wise.  The
space consumption could be annoying, but I'm thinking that we might
only have to populate the field in clone clauses, which would
alleviate that issue.

			regards, tom lane