BUG #18627: Regression (15 -> 16) - Join removal not performed when join condition spans multiple tables

On Mon, 23 Sept 2024 at 00:55, PG Bug reporting form
<noreply@postgresql.org> wrote:

Postgres 15 is able to nicely remove all the joins and gives a nice tidy
query plan:
```
Seq Scan on origin o (cost=0.00..16.50 rows=650 width=32)
```

Postgres 16 (and 17rc1) on the other hand are giving me this query plan
instead:
```
Hash Left Join (cost=24.62..42.84 rows=650 width=32)

Thanks for the report.

It looks like the first bad commit is acc5821e4d (Further fixes in
qual nullingrel adjustment for outer join commutation)

I doubt breaking this was an intended change of the nullable Var work.
Tom can likely confirm.

David

David Rowley <dgrowleyml@gmail.com> writes:

On Mon, 23 Sept 2024 at 00:55, PG Bug reporting form
<noreply@postgresql.org> wrote:
It looks like the first bad commit is acc5821e4d (Further fixes in
qual nullingrel adjustment for outer join commutation)
I doubt breaking this was an intended change of the nullable Var work.
Tom can likely confirm.

Hmm ... I did not work through exactly why it broke at that particular
commit and not somewhen else, but what I conclude is that it's fairly
accidental that it ever worked at all. join_is_removable is rejecting
removal of the syntactically-lower join because it thinks that
i.version_id is still needed "above" the join, even though we
previously removed the upper join condition:

(gdb)
219 if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
(gdb) call bmsToString (inputrelids)
$5 = 0x2ecd968 "(b 1 2)"
(gdb) call bmsToString (joinrelids)
$6 = 0x2eac408 "(b 1 2 3)"
(gdb) call bmsToString (innerrel->attr_needed[attroff])
$7 = 0x2eac818 "(b 1 2 3)"

This happens because remove_rel_from_query only cleaned relid 4
(destination d) out of the attr_needed data; it didn't really
account for the fact that i.version_id is no longer needed anywhere
once that ON clause is gone. That is, really at this point
attr_needed[attroff] ought to be empty, and it isn't.

Pre-v16, the case managed to work because we didn't track outer
joins (here, relid 3 for the syntactically-lower join) in
attr_needed, and so this test succeeded anyway. That feels fairly
accidental though; it seems likely that there are related cases
that could be optimized and never have been.

The "clean and obviously correct" answer would be to recompute
all the attr_needed values from scratch after removing the upper
outer join. That seems impractically expensive. What I'm
thinking about is to test against joinrelids here instead of
inputrelids. As the adjacent comment says, that would get the
wrong answer for "pushed down" conditions, but we could revert
to the pre-v16 hack of checking relevant join conditions in
the loop further down, ie put back this kluge:

if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
{
/*
* If such a clause actually references the inner rel then join
* removal has to be disallowed. We have to check this despite
* the previous attr_needed checks because of the possibility of
* pushed-down clauses referencing the rel.
*/
if (bms_is_member(innerrelid, restrictinfo->clause_relids))
return false;
continue; /* else, ignore; not useful here */
}

That's ugly for sure, and it would only revert to the status
quo ante. But I'm not seeing a better way right now.

regards, tom lane

On Mon, Sep 23, 2024 at 12:56 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

What I'm
thinking about is to test against joinrelids here instead of
inputrelids. As the adjacent comment says, that would get the
wrong answer for "pushed down" conditions, but we could revert
to the pre-v16 hack of checking relevant join conditions in
the loop further down, ie put back this kluge:

if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
{
/*
* If such a clause actually references the inner rel then join
* removal has to be disallowed. We have to check this despite
* the previous attr_needed checks because of the possibility of
* pushed-down clauses referencing the rel.
*/
if (bms_is_member(innerrelid, restrictinfo->clause_relids))
return false;
continue; /* else, ignore; not useful here */
}

That's ugly for sure, and it would only revert to the status
quo ante. But I'm not seeing a better way right now.

It seems to me that this approach basically reverts the changes in
8538519db. I'm afraid this would re-introduce the bug fixed by that
commit. For instance, this approach would incorrectly remove the join
in the query below:

create table t (a int unique, b int);

explain (costs off)
select 1 from t t1 left join t t2 on t1.a = t2.a where t1.b = coalesce(t2.b, 0);
QUERY PLAN
------------------
Seq Scan on t t1
(1 row)

... because it does not realize that there might be references to the
innerrel in ECs. (Pre-v16 this join removal is prevented by the
delay_upper_joins flag.)

Besides, we have the logic that a PHV needn't prevent join removal if
it mentions the innerrel in ph_eval_at but its contained expression
doesn't actually reference the innerrel (see cad569205). I think the
proposed approach would also break this logic. For instance, in the
query below, the t2/t3 join should be removed but is prevented by the
PHV.

explain (costs off)
select 1 from t t1 left join
(select 1 as x from t t2 left join t t3 on t2.a = t3.a) s on true
where s.x = 1;
QUERY PLAN
------------------------------------------
Nested Loop Left Join
Filter: ((1) = 1)
-> Seq Scan on t t1
-> Materialize
-> Hash Left Join
Hash Cond: (t2.a = t3.a)
-> Seq Scan on t t2
-> Hash
-> Seq Scan on t t3
(9 rows)

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:

On Mon, Sep 23, 2024 at 12:56 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

That's ugly for sure, and it would only revert to the status
quo ante. But I'm not seeing a better way right now.

It seems to me that this approach basically reverts the changes in
8538519db. I'm afraid this would re-introduce the bug fixed by that
commit.

Ugh, you're probably right.

I'm taking a second look at the idea of regenerating the attr_needed
values altogether. It doesn't look that bad, especially if we cheat
to the extent of preserving the existing "relation 0" bits (that is,
tlist and HAVING references). That's fine since we could never
remove a rel that supplies Vars used in those places. Then we
basically have to reconstruct surviving references from

* EquivalenceClasses
* joinclauses (available from the rels' joinlists)
* lateral references (available from the rels' lateral_vars lists)
* surviving placeholders (much like fix_placeholder_input_needed_levels)

The need to again call pull_var_clause on these clauses is mildly
annoying but I think it won't be that bad runtime-wise. Slightly
more annoying is that a joinclause mentioning N relations would be
visited N times. Perhaps we could de-duplicate using rinfo
serial numbers?

While I've not written any code yet, it seems like this route
would lead to a bigger patch than we'd want to back-patch into
v16 or v17. So that's not great; but on the other hand it took
a year for anyone to notice this regression, so maybe we can get
away with not fixing it in those branches.

regards, tom lane

I wrote:

I'm taking a second look at the idea of regenerating the attr_needed
values altogether. It doesn't look that bad, especially if we cheat
to the extent of preserving the existing "relation 0" bits (that is,
tlist and HAVING references). That's fine since we could never
remove a rel that supplies Vars used in those places.

Here's a finished patch that fixes it along those lines.

I worried that this might have nasty performance impact, so I added
some instr_time calls (not included in patch) to check the runtime of
remove_useless_joins() by itself as well as the overall planner run
time. Using a test case like

SELECT a.id
FROM a
LEFT JOIN b ON a.id = b.id

I found that HEAD takes about 500ns on my machine to run
remove_useless_joins, out of a total planner run time of about 12.5us.
With the patch, it's more like 530ns, but the total planner run time
seems barely different. So I find that totally acceptable, especially
if it helps us find join removals we missed before.

This seems straightforward enough that maybe we could put it into
v16/v17 after all, although I'm still leaning towards not doing so.

To validate the patch, verify that add_vars_to_targetlist is
presently the only function that adds bits to attr_needed or
ph_needed. Then check that for every caller of that function,
I've added parallel code to re-insert those bits (except for
callers that set the "relation 0" bit, which we handle by not
removing that bit in the first place).

Comments?

regards, tom lane