Re: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware)

Hi,
sqlancer benchmark raised an issue with pushing down clauses in LEFT
JOINs. Example:

DROP TABLE IF EXISTS t1,t2,t3,t4 CASCADE;
CREATE TABLE t1 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t2 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t3 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t4 AS SELECT true AS x FROM generate_series(0,1) x;
ANALYZE;

EXPLAIN (ANALYZE, COSTS OFF)
SELECT ALL t1.x FROM t1, t2
LEFT OUTER JOIN t3
ON t3.x
LEFT OUTER JOIN t4
ON t3.x
WHERE t4.x ISNULL;

We should get zero tuples, right? But we have the explain:
Nested Loop (actual time=0.024..0.028 rows=4 loops=1)
...

REL_15_STABLE works correctly. As I remember, it could be induces by new
machinery, introduced by the 'Making Vars outer-join aware' patch.

Sorry for flood, if you are working on that issue.

--
regards,
Andrey Lepikhov
Postgres Professional

On Wed, Feb 22, 2023 at 2:48 PM Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru>
wrote:

> DROP TABLE IF EXISTS t1,t2,t3,t4 CASCADE;
> CREATE TABLE t1 AS SELECT true AS x FROM generate_series(0,1) x;
> CREATE TABLE t2 AS SELECT true AS x FROM generate_series(0,1) x;
> CREATE TABLE t3 AS SELECT true AS x FROM generate_series(0,1) x;
> CREATE TABLE t4 AS SELECT true AS x FROM generate_series(0,1) x;
> ANALYZE;
>
> EXPLAIN (ANALYZE, COSTS OFF)
> SELECT ALL t1.x FROM t1, t2
> LEFT OUTER JOIN t3
> ON t3.x
> LEFT OUTER JOIN t4
> ON t3.x
> WHERE t4.x ISNULL;

Thanks for the report! I think this is a new issue that was not
reported before. I simplify this query a little for easy debugging as

# explain (costs off)
select * from t1 left join t2 on true left join t3 on t2.x where t3.x is
null;
QUERY PLAN
----------------------------------------
Nested Loop Left Join
-> Seq Scan on t1
-> Materialize
-> Nested Loop Left Join
Join Filter: t2.x
Filter: (t3.x IS NULL)
-> Seq Scan on t2
-> Materialize
-> Seq Scan on t3
(9 rows)

The qual 't3.x IS NULL' is placed at the wrong place. This qual's Var
't3.x' is marked with t2/t3 join in its varnullingrels by the parser,
which is right for the user-given order. After we've commuted t1/t2
join and t2/t3 join, Var 't3.x' can actually be nulled by both t2/t3
join and t1/t2 join. We neglect to adjust this qual accordingly in this
case.

ISTM that for outer join identity 3, if we are given form
(A leftjoin B on (Pab)) leftjoin C on (Pbc)
then references to C Vars in higher qual levels would be marked with the
B/C join. If we've transformed it to form
A leftjoin (B leftjoin C on (Pbc)) on (Pab)
then references to C Vars in higher qual levels should be adjusted to
include both B/C join and A/B join in their varnullingrels.

References to A Vars and B Vars in higher qual levels do not have this
problem though.

Thanks
Richard

On Wed, Feb 22, 2023 at 6:24 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> ISTM that for outer join identity 3, if we are given form
> (A leftjoin B on (Pab)) leftjoin C on (Pbc)
> then references to C Vars in higher qual levels would be marked with the
> B/C join. If we've transformed it to form
> A leftjoin (B leftjoin C on (Pbc)) on (Pab)
> then references to C Vars in higher qual levels should be adjusted to
> include both B/C join and A/B join in their varnullingrels.
>

A quick hack that comes to my mind is that for a pushed down clause we
check all outer join relids it mentions and add the outer joins'
commute_below to the clause's required_relids, so that after we've
commuted the outer joins, the clause would still be placed in the right
place.

--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -2349,12 +2349,27 @@ distribute_qual_to_rels(PlannerInfo *root, Node
*clause,
}
else
{
+ ListCell *l;
+
/*
* Normal qual clause or degenerate outer-join clause. Either way,
we
* can mark it as pushed-down.
*/
is_pushed_down = true;

+ /*
+ * Add in commute_below of outer joins mentioned within the clause,
so
+ * that after we've commuted the outer joins, the clause would
still be
+ * placed correctly.
+ */
+ foreach(l, root->join_info_list)
+ {
+ SpecialJoinInfo *sji = (SpecialJoinInfo *) lfirst(l);
+
+ if (bms_is_member(sji->ojrelid, relids))
+ relids = bms_add_members(relids, sji->commute_below);
+ }
+

For a formal fix, I wonder if we need to generate multiple versions of
such a clause and apply the appropriate one depending on which join
order is chosen, just like what we do for left join quals in
deconstruct_distribute_oj_quals.

Thanks
Richard

On Thu, Feb 23, 2023 at 11:29 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> On Wed, Feb 22, 2023 at 6:24 PM Richard Guo <guofenglinux(at)gmail(dot)com>
> wrote:
>
>> ISTM that for outer join identity 3, if we are given form
>> (A leftjoin B on (Pab)) leftjoin C on (Pbc)
>> then references to C Vars in higher qual levels would be marked with the
>> B/C join. If we've transformed it to form
>> A leftjoin (B leftjoin C on (Pbc)) on (Pab)
>> then references to C Vars in higher qual levels should be adjusted to
>> include both B/C join and A/B join in their varnullingrels.
>>
>
> A quick hack that comes to my mind is that for a pushed down clause we
> check all outer join relids it mentions and add the outer joins'
> commute_below to the clause's required_relids, so that after we've
> commuted the outer joins, the clause would still be placed in the right
> place.
>

I've realized this hack is not correct :-(. References to A Vars and B
Vars in higher qual levels do not need this adjustment. So this code
change would add unnecessary relids for clauses that involve A Vars or B
Vars but not C Vars, resulting them being placed at higher place than
needed.

Maybe what we need is to add in commute_below_l (assuming it has been
recorded in SpecialJoinInfo) rather than commute_below of outer joins
mentioned within the clause?

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> ISTM that for outer join identity 3, if we are given form
> (A leftjoin B on (Pab)) leftjoin C on (Pbc)
> then references to C Vars in higher qual levels would be marked with the
> B/C join. If we've transformed it to form
> A leftjoin (B leftjoin C on (Pbc)) on (Pab)
> then references to C Vars in higher qual levels should be adjusted to
> include both B/C join and A/B join in their varnullingrels.

Hmm. I remember having convinced myself that we didn't need to change
anything above the commuting OJs, but now I can't reconstruct the
reasoning :-(.

I wonder whether we could instead fix things by deeming that the result
of the pushed-down B/C join does not yet produce correct C* variables,
so that we won't allow conditions involving them to drop below the
pushed-up A/B join. This would be a little bit messy in some places
because now we'd consider that the A/B join is adding two OJ relids
not just one to the output join relid set, while the B/C join is adding
no relids even though it must execute an outer join. (But we already
have that notion for semijoins and some antijoins, so maybe it's fine.)

regards, tom lane

On 23/2/2023 11:36, Richard Guo wrote:
> I've realized this hack is not correct :-(.  References to A Vars and B
> Vars in higher qual levels do not need this adjustment.  So this code
> change would add unnecessary relids for clauses that involve A Vars or B
> Vars but not C Vars, resulting them being placed at higher place than
> needed.
>
> Maybe what we need is to add in commute_below_l (assuming it has been
> recorded in SpecialJoinInfo) rather than commute_below of outer joins
> mentioned within the clause?
Doing a comparison of pg15 and master initsplan.c I found that a clear
and documented algorithm for delaying the application of a qual is lost
or replaced with some commute_* fields.
It is not clear how we guarantee correct application delay of a qual.
Which part of the code implements it now?

--
regards,
Andrey Lepikhov
Postgres Professional

On Fri, Feb 24, 2023 at 3:48 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> I wonder whether we could instead fix things by deeming that the result
> of the pushed-down B/C join does not yet produce correct C* variables,
> so that we won't allow conditions involving them to drop below the
> pushed-up A/B join. This would be a little bit messy in some places
> because now we'd consider that the A/B join is adding two OJ relids
> not just one to the output join relid set, while the B/C join is adding
> no relids even though it must execute an outer join. (But we already
> have that notion for semijoins and some antijoins, so maybe it's fine.)

I think I see your points. Semijoins and antijoins derived from
semijoins do not have rtindex, so they do not add any OJ relids to the
output join relid set. Do you mean we do the similar thing to the
pushed-down B/C join here by not adding B/C's ojrelid to the output B/C
join, but instead add it later when we've formed the pushed-up A/B join?

I tried the codes below to adjust joinrelids and then use the modified
joinrelids when constructing restrict and join clause lists for the
joinrel. It seems to be able to solve the presented case. But I'm not
sure if it'd break other cases.

+ ListCell *lc;
+ Relids commute_below_l = NULL;
+
+ foreach(lc, root->join_info_list)
+ {
+ SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(lc);
+
+ if (otherinfo->jointype != JOIN_LEFT)
+ continue;
+
+ /* collect commute_below_l */
+ if (bms_is_member(otherinfo->ojrelid, sjinfo->commute_below) &&
+ bms_overlap(otherinfo->syn_righthand, sjinfo->syn_lefthand))
+ commute_below_l =
+ bms_add_member(commute_below_l, otherinfo->ojrelid);
+
+ /*
+ * add the pushed-down B/C join's relid to A/B join's relid set
+ */
+ if (bms_is_member(otherinfo->ojrelid, sjinfo->commute_above_l) &&
+ bms_overlap(otherinfo->min_righthand, joinrelids))
+ joinrelids = bms_add_member(joinrelids, otherinfo->ojrelid);
+ }
+
+ /*
+ * delete the pushed-down B/C join's relid from B/C join
+ */
+ if (!bms_is_empty(commute_below_l) &&
+ !bms_overlap(commute_below_l, joinrelids))
+ joinrelids = bms_del_member(joinrelids, sjinfo->ojrelid);

Also I'm wondering whether we can just copy what we once did in
check_outerjoin_delay() to update required_relids of a pushed-down
clause. This seems to be a lazy but workable way.

Thanks
Richard

On Mon, Feb 27, 2023 at 2:23 PM Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru>
wrote:

> Doing a comparison of pg15 and master initsplan.c I found that a clear
> and documented algorithm for delaying the application of a qual is lost
> or replaced with some commute_* fields.
> It is not clear how we guarantee correct application delay of a qual.
> Which part of the code implements it now?

Do you mean function check_outerjoin_delay()? Yes it has been removed
in b448f1c8, since now we consider that outer joins listed in
varnullingrels or phnullingrels are used in the clause, so that the
clause would not be placed below outer joins that should null some of
its vars.

Such as in query

select * from t1 left join t2 on true where coalesce(t2.a,1) = 1;

we'd consider that the clause uses t2 as well as t1/t2 join, so it
cannot be pushed down below the left join.

Thanks
Richard

On 27/2/2023 13:16, Richard Guo wrote:
>
> On Mon, Feb 27, 2023 at 2:23 PM Andrey Lepikhov
> <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
>
> Doing a comparison of pg15 and master initsplan.c I found that a clear
> and documented algorithm for delaying the application of a qual is lost
> or replaced with some commute_* fields.
> It is not clear how we guarantee correct application delay of a qual.
> Which part of the code implements it now?
>
> Do you mean function check_outerjoin_delay()?  Yes it has been removed
> in b448f1c8, since now we consider that outer joins listed in
> varnullingrels or phnullingrels are used in the clause, so that the
> clause would not be placed below outer joins that should null some of
> its vars.
I see. But these logics looks non-equivalent.
relnode.c::build_joinrel_tlist() adds relid into varnullingrels only in
the case when the var exists in the target list. So, other joins, which
don't have links to the var, don't get into the bitmapset too.

--
regards,
Andrey Lepikhov
Postgres Professional

Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru> writes:
> On 27/2/2023 13:16, Richard Guo wrote:
>> Do you mean function check_outerjoin_delay()?  Yes it has been removed
>> in b448f1c8, since now we consider that outer joins listed in
>> varnullingrels or phnullingrels are used in the clause, so that the
>> clause would not be placed below outer joins that should null some of
>> its vars.

> I see. But these logics looks non-equivalent.

They're not meant to be equivalent. The new code should be more
flexible and more trustworthy --- in particular, there's nothing that
didn't suck about the old outerjoin_delayed mechanism. Before we had
only a very ad-hoc model of where outer-join quals could be evaluated.
I've spent the last sixteen years living in fear that somebody would
find a bug in it that couldn't be fixed without making many plans
disastrously worse. Now we have something that actually faithfully
represents where quals can be evaluated and why.

Admittedly the new stuff is having more teething pains than I'd hoped
for, but we'll work through it. Most of the bugs are stemming from
the fact that we now need a rigorous representation of what is
happening when we commute outer joins per identity 3, and we're
finding out that we are not quite there yet.

regards, tom lane

On 28/2/2023 00:02, Tom Lane wrote:
> Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru> writes:
>> On 27/2/2023 13:16, Richard Guo wrote:
>>> Do you mean function check_outerjoin_delay()?  Yes it has been removed
>>> in b448f1c8, since now we consider that outer joins listed in
>>> varnullingrels or phnullingrels are used in the clause, so that the
>>> clause would not be placed below outer joins that should null some of
>>> its vars.
>> I see. But these logics looks non-equivalent.
> Admittedly the new stuff is having more teething pains than I'd hoped
> for, but we'll work through it. Most of the bugs are stemming from
> the fact that we now need a rigorous representation of what is
> happening when we commute outer joins per identity 3, and we're
> finding out that we are not quite there yet.
Ok, maybe my language still not so fluent, as I think sometimes. In
accordance to the example above:
1. varnullingrels contains relids of entries which can null the var. In
our case it (correctly) contains t3 and OJ(t3,t4)
2. Syntactic scope of the clause correctly contains all relations and OJs
3. In the distribute_qual_to_rels I don't see a code which should
disallow pushing down a clause from higher syntactic level into nullable
side of OJ. Where is the logic which should limit the lowest level of
the clause push down?

--
regards,
Andrey Lepikhov
Postgres Professional

Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru> writes:
> Ok, maybe my language still not so fluent, as I think sometimes. In
> accordance to the example above:
> 1. varnullingrels contains relids of entries which can null the var. In
> our case it (correctly) contains t3 and OJ(t3,t4)
> 2. Syntactic scope of the clause correctly contains all relations and OJs
> 3. In the distribute_qual_to_rels I don't see a code which should
> disallow pushing down a clause from higher syntactic level into nullable
> side of OJ. Where is the logic which should limit the lowest level of
> the clause push down?

It's the same logic that prevents push-down to joins that lack a
relation you're trying to reference, namely the checks of
RestrictInfo.required_relids. If a clause should be referring to the
possibly-nulled version of some variable, then its required_relids now
include the relid of the outer join that nulls that variable, so we
can't push it to below that outer join.

This is straightforward enough until you start applying outer join
identity 3:

3. (A leftjoin B on (Pab)) leftjoin C on (Pbc)
= A leftjoin (B leftjoin C on (Pbc)) on (Pab)
granting that Pbc is strict for B

Suppose that we are given a FROM clause in the first form and
that there's a non-strict WHERE clause referencing a column of C.
That clause should certainly see the nulled version of C, so if we
implement the join as written then we can apply the WHERE clause as
a filter condition (not join condition) on the join of A/B to C.
However, if we decide to implement the join according to the second
form of the identity, then the current code believes it can push
the WHERE clause down so that it's a filter on the join of B to C.
It's not quite obvious that that's wrong, but it is: we might see
C values that are non-null at this point but will become null after
application of the A/B join. Then the WHERE clause gives misleading
answers, which is exactly what's going wrong in this example.

The way I'm proposing to fix this is to say that if the B/C join
is done first, then its output C columns do not yet satisfy the
nulling action of the syntactically-upper outer join, so we can't
yet apply clauses that need to see those outputs. We can implement
that by not adding the outer join's relid to the joinrelids produced
by the B/C join: then clauses containing such Vars won't look like
they can be pushed down to that join. Instead they'll get pushed
to the AB/C join, and to make that happen we'll have to add both
outer-join relids to the identifying relids of that join level.

BTW, there's no problem if we start from the second form of the
identity and transform to the first, because then any C references
above the join nest are already marked as requiring the nulling
actions of both of the joins, so they won't fall below the upper
join no matter which order we do the joins in.

So another way we could fix this is to run around and forcibly mark
all such Vars with the relids of both outer joins, thus producing
a parse tree that looks more like the second form of the identity.
However, we're pretty much committed already to keeping all Vars
marked according to the syntactic tree structure, so that solution
would require revisiting a lot of code (not to mention the cost of
mutating the parse tree like that). I don't want to go that way
unless really forced into it.

I have a WIP patch that does it like this, and it fixes the presented
case; but it's not complete so it's still failing some existing
regression tests. More later.

regards, tom lane

I wrote:
> I have a WIP patch that does it like this, and it fixes the presented
> case; but it's not complete so it's still failing some existing
> regression tests. More later.

Here's said patch. Although this fixes the described problem and
passes check-world, I'm not totally happy with it yet: it feels
like the new add_outer_joins_to_relids() function is too expensive
to be doing every time we construct a join relation. I wonder if
there is a way we can add more info to the SpecialJoinInfo data
structure to make it cheaper. An obvious improvement is to store
commute_below_l explicitly instead of recomputing it over and over,
but that isn't going to move the needle all that far. Is there a
way to not have to scan all the SpecialJoinInfos?

I may be worrying over nothing --- it's likely that the path
construction work that will happen after we make the join relation
RelOptInfo will swamp this cost anyway. But it feels ugly.

Another thing I'm wondering about is whether this'd let us get
rid of RestrictInfo.is_pushed_down and RINFO_IS_PUSHED_DOWN.
I tried really hard to remove those in favor of checking to see
whether a qual clause's required_relids include the outer join
being formed, which seems like a much more principled way of
deciding whether it's a filter or join clause. I couldn't get
that to work, but now I wonder if what I was running into was
really bugs associated with not understanding that we haven't
fully formed the lower outer join when we apply identity 3.

regards, tom lane

On Wed, Mar 1, 2023 at 3:10 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Here's said patch. Although this fixes the described problem and
> passes check-world, I'm not totally happy with it yet: it feels
> like the new add_outer_joins_to_relids() function is too expensive
> to be doing every time we construct a join relation.

It seems that this change may affect how we select the appropriate
outer-join clause from redundant versions of that clause for an outer
join, because we make that decision relying on the joinrelids of the
outer join and outer joins below. If we've decided not to add the outer
join's relid to an outer join, we'd choose a clause that does not
contain that outer join's relid. As a result, we may have mismatched
nullingrels in joinqual and the join's target entry. I see this problem
in the query below.

select * from t1 left join t2 on true left join t3 on t2.x left join t4 on
t3.x;

When we build the join of t2/t3 to t4, we have two versions of the
joinqual 't3.x', one with t2/t3 join in the nullingrels, and one
without. The latter one would be chosen since we haven't added t2/t3
join's ojrelid. However, the targetlist of t2/t3 join would have the
t3 Vars marked with the join's ojrelid. So that we see the mismatched
nullingrels.

Do we need to revise how we build target list for outer join by
adjusting the nullingrels of Vars and PHVs from input_rel in a similar
way?

Thanks
Richard

On Wed, Mar 1, 2023 at 2:44 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> Do we need to revise how we build target list for outer join by
> adjusting the nullingrels of Vars and PHVs from input_rel in a similar
> way?
>

Hmm. Doing this complicates matters even more. Maybe we can just loosen
the cross-check for nullingrels to cope with this change by using
NRM_SUBSET matches for joinquals (including mergeclauses, hashclauses
and hashkeys) in set_join_references()?

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> Hmm. Doing this complicates matters even more. Maybe we can just loosen
> the cross-check for nullingrels to cope with this change by using
> NRM_SUBSET matches for joinquals (including mergeclauses, hashclauses
> and hashkeys) in set_join_references()?

That would be sad ... it'd basically be conceding defeat at the task
of knowing that we've accurately placed joinquals, which is one of
the most fundamental things I wanted to get out of this rewrite.

I might accept weakening those assertions as a stopgap that we plan to
work on more later, except that I'm afraid that this is telling us
there are still bugs in the area.

What's feeling like it might be the best thing is to go ahead and
syntactically convert to the second form of identity 3 as soon as
we've determined it's applicable, so that upper C Vars are always
marked with both OJ relids. Not sure how much work is involved
there.

regards, tom lane

On Thu, Mar 2, 2023 at 11:27 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> What's feeling like it might be the best thing is to go ahead and
> syntactically convert to the second form of identity 3 as soon as
> we've determined it's applicable, so that upper C Vars are always
> marked with both OJ relids. Not sure how much work is involved
> there.

I'm thinking something that once we've determined identity 3 applies in
make_outerjoininfo we record information about how to adjust relids for
upper quals and store this info in all upper JoinTreeItems. Then
afterwards in distribute_qual_to_rels we check all this info stored in
current JoinTreeItem and adjust relids for the qual accordingly.

The info we record should consist of two parts, target_relids and
added_relids. Vars and PHVs in quals that belong to target_relids
should be adjusted to include added_relids.

Following this idea I come up with attached patch (no comments and test
cases yet). It fixes the presented case and passes check-world. Before
finishing it I'd like to know whether this idea works. Any comments are
appreciated.

Thanks
Richard

[ sorry for slow response ]

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> On Thu, Mar 2, 2023 at 11:27 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> What's feeling like it might be the best thing is to go ahead and
>> syntactically convert to the second form of identity 3 as soon as
>> we've determined it's applicable, so that upper C Vars are always
>> marked with both OJ relids. Not sure how much work is involved
>> there.

> I'm thinking something that once we've determined identity 3 applies in
> make_outerjoininfo we record information about how to adjust relids for
> upper quals and store this info in all upper JoinTreeItems. Then
> afterwards in distribute_qual_to_rels we check all this info stored in
> current JoinTreeItem and adjust relids for the qual accordingly.

> The info we record should consist of two parts, target_relids and
> added_relids. Vars and PHVs in quals that belong to target_relids
> should be adjusted to include added_relids.

> Following this idea I come up with attached patch (no comments and test
> cases yet). It fixes the presented case and passes check-world. Before
> finishing it I'd like to know whether this idea works. Any comments are
> appreciated.

This doesn't look hugely promising to me. We do need to do something
like "Vars/PHVs referencing join X now need to also reference join Y",
but I think we need to actually change the individual Vars/PHVs not
just fake it by hacking the required_relids of RestrictInfos. Otherwise
we're going to get assertion failures in setrefs.c about nullingrel
sets not matching up.

Also, in addition to upper-level quals, we need to apply the same
transformation to the query's targetlist and havingQual if anyway
(and perhaps also mergeActionList, not sure).

So the idea that I had was to, once we detect that X commutes with Y,
immediately call a function that recurses through the relevant parts
of root->parse and performs the required nullingrels updates. This'd
result in multiple transformation traversals if there are several
commuting pairs of joins, but I doubt that that would really pose a
performance problem. If it does, we could imagine splitting up
deconstruct_jointree still further, so that detection of commutable
OJs happens in a pass earlier than distribute_quals_to_rels, and then
we fix up Vars/PHVs throughout the tree in one scan done between those
passes. But an extra deconstruct recursion pass isn't free either, so
I don't want to do that unless we actually see a performance problem.
Assuming we don't do that but perform this transformation during
deconstruct_jointree phase 2, it'd be too late to modify quals of
already-processed join tree nodes, but that's fine because they
couldn't contain Vars needing adjustment. (We could exploit that
in an incomplete way by passing in the address of the current
JoinExpr, and not bothering to recurse below it.) There is code
roughly like this in prepjointree.c already --- in particular, we'd
need to steal its hack of mutating join quals but not the JoinExpr and
FromExpr nodes themselves, to avoid breaking the recursion-in-progress.

I can have a go at coding this, or you can if you'd like to.

regards, tom lane

On Tue, Mar 21, 2023 at 12:21 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> This doesn't look hugely promising to me. We do need to do something
> like "Vars/PHVs referencing join X now need to also reference join Y",
> but I think we need to actually change the individual Vars/PHVs not
> just fake it by hacking the required_relids of RestrictInfos. Otherwise
> we're going to get assertion failures in setrefs.c about nullingrel
> sets not matching up.

Agreed that we need to actually change the individual Vars/PHVs because
I find that with my patch it's not easy to fake the quals deduced from
ECs as there is no 'current JoinTreeItem' there. I'm not sure that
there is nullingrels mis-match issue though, because when forming an
outer join's target list we've ensured that the output Vars are always
marked according to the syntactic tree structure.

> So the idea that I had was to, once we detect that X commutes with Y,
> immediately call a function that recurses through the relevant parts
> of root->parse and performs the required nullingrels updates.

So IIUC the idea is that if we are given the first form of identity 3,
we update all upper C Vars so that they are marked with both OJ relids.
It seems that this may have nullingrels mis-match issue because of how
we form outer join's target list. Consider

A leftjoin B on (Pab) leftjoin C on (Pbc) inner join D on (Pcd)

At first C Vars in Pcd is marked only with B/C join. Then we detect
that A/B join commutes with B/C join so we update C Vars in Pcd as being
marked with B/C join and A/B join. However C Vars in the target list of
joinrel A/B/C would be marked only with B/C join as that is consistent
with the syntactic tree structure. So when we process the joinqual Pcd
for C/D join in setrefs.c, I think we would have assertion failures
about nullingrels mismatch. (This is just my imagination. I haven't
implemented the codes to verify it.)

Thanks
Richard

On Tue, Mar 21, 2023 at 2:23 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> On Tue, Mar 21, 2023 at 12:21 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>> So the idea that I had was to, once we detect that X commutes with Y,
>> immediately call a function that recurses through the relevant parts
>> of root->parse and performs the required nullingrels updates.
>
>
> So IIUC the idea is that if we are given the first form of identity 3,
> we update all upper C Vars so that they are marked with both OJ relids.
> It seems that this may have nullingrels mis-match issue because of how
> we form outer join's target list.
>

I do have a try coding along this idea to update all upper C Vars being
marked with both OJ relids if the two OJs commute according to identity
3. And then I realize there are several other adjustments needed to
make it work.

* As I imagined before, we need to revise how we form outer join's
target list to avoid nullingrels mismatch. Currently the outer join's
target list is built in a way that the output Vars have the same nulling
bitmaps that they would if the two joins had been done in syntactic
order. And now we need to change that to always marking the output C
Vars with both joins.

* We need to revise how we check if identity 3 applies and if so how we
adjust min_lefthand in make_outerjoininfo. Consider

A leftjoin B on (Pab) leftjoin C on (Pbc) leftjoin D on (Pcd)

So now the C Vars in Pcd are marked with A/B join and B/C join since the
two joins can commute. When it comes to check if C/D join can commute
with B/C join, the A/B join from C Vars' nullingrels would make us think
that C/D join cannot commute with B/C join, which is not correct.
Besides, C/D join's min_lefthand including A/B join is also problematic.

* We need to adjust how we generate multiple versions for LEFT JOIN
quals in deconstruct_distribute_oj_quals, to cope with any new added
nulling rel. But I haven't figured out this point clearly yet.

So it seems there is some work involved. I begin to wonder if this is
the way we want.

Thanks
Richard

On Wed, Mar 1, 2023 at 2:44 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> On Wed, Mar 1, 2023 at 3:10 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>> Here's said patch. Although this fixes the described problem and
>> passes check-world, I'm not totally happy with it yet: it feels
>> like the new add_outer_joins_to_relids() function is too expensive
>> to be doing every time we construct a join relation.
>
> Do we need to revise how we build target list for outer join by
> adjusting the nullingrels of Vars and PHVs from input_rel in a similar
> way?
>

After more thought on this idea I think it's more promising, as long as
we do proper adjustments to outer join's target list. AFAICS we need to
do two things for the adjustment.

* we need to check whether the outer join has been completely performed
before we add its relid to the nulling bitmap. For example, the pushed
down B/C join should not mark C Vars as nulled by itself. This can be
done by bms_is_member(sjinfo->ojrelid, joinrel->relids).

* for all the pushed down outer joins that have been completely
performed just by now, we need to add their relids to the nulling bitmap
if they can null the Var or PHV. For example, when we form the pulled
up A/B join, we need to mark C Vars as nulled by the pushed down B/C
join. To do this, I'm considering we can collect all the pushed down
outer joins in add_outer_joins_to_relids().

Attached is the patch to do adjustments to outer join's target list.
Note that it needs to be applied on the base of patch
'postpone-adding-pushed-down-ojrelid-to-relids.patch'.

Thanks
Richard

On Sat, Apr 1, 2023 at 10:15 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> On Wed, Mar 1, 2023 at 2:44 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
>
>> On Wed, Mar 1, 2023 at 3:10 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>
>>> Here's said patch. Although this fixes the described problem and
>>> passes check-world, I'm not totally happy with it yet: it feels
>>> like the new add_outer_joins_to_relids() function is too expensive
>>> to be doing every time we construct a join relation.
>>
>> Do we need to revise how we build target list for outer join by
>> adjusting the nullingrels of Vars and PHVs from input_rel in a similar
>> way?
>>
>
> After more thought on this idea I think it's more promising, as long as
> we do proper adjustments to outer join's target list. AFAICS we need to
> do two things for the adjustment.
>
> * we need to check whether the outer join has been completely performed
> before we add its relid to the nulling bitmap. For example, the pushed
> down B/C join should not mark C Vars as nulled by itself. This can be
> done by bms_is_member(sjinfo->ojrelid, joinrel->relids).
>
> * for all the pushed down outer joins that have been completely
> performed just by now, we need to add their relids to the nulling bitmap
> if they can null the Var or PHV. For example, when we form the pulled
> up A/B join, we need to mark C Vars as nulled by the pushed down B/C
> join. To do this, I'm considering we can collect all the pushed down
> outer joins in add_outer_joins_to_relids().
>
> Attached is the patch to do adjustments to outer join's target list.
> Note that it needs to be applied on the base of patch
> 'postpone-adding-pushed-down-ojrelid-to-relids.patch'.
>

I found a thinko in the v1 patch: we need to consider syn_righthand
rather than min_righthand of the pushed down outer joins as we want to
know if the Var or PHV actually comes from within the syntactically
nullable sides. Attach v2 to fix this.

I have some concerns that the new added foreach loop is too expensive to
be doing for each Var or PHV. But maybe it's no problem since we only
loop over pushed down joins here.

Thanks
Richard

On 4/4/23 08:00, Richard Guo wrote:
> I found a thinko in the v1 patch: we need to consider syn_righthand
> rather than min_righthand of the pushed down outer joins as we want to
> know if the Var or PHV actually comes from within the syntactically
> nullable sides.  Attach v2 to fix this.
>
> I have some concerns that the new added foreach loop is too expensive to
> be doing for each Var or PHV.  But maybe it's no problem since we only
> loop over pushed down joins here.
I have passed through your patch and the
'postpone-adding-pushed-down-ojrelid-to-relids' patch step-by-step. It
looks logically correct.
Honestly, I don't happy with the top patch, because it looks a bit
peculiar, but the sqlancer long test (which detected the problem before)
didn't show any problems here.
But one thought is bugging me: do we have a guarantee, what with these
Identity 3 transformations and 'delaying up to completely performed'
technique we don't lose some joininfo clauses?

--
Regards
Andrey Lepikhov
Postgres Professional

On Thu, Apr 20, 2023 at 1:06 PM Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru>
wrote:

> I have passed through your patch and the
> 'postpone-adding-pushed-down-ojrelid-to-relids' patch step-by-step. It
> looks logically correct.
> Honestly, I don't happy with the top patch, because it looks a bit
> peculiar, but the sqlancer long test (which detected the problem before)
> didn't show any problems here.

Thanks for testing the patches.

Currently in the patch the pushed down outer joins are collected in
add_outer_joins_to_relids() and then passed in build_joinrel_tlist()
where their relids might need to be added to Var's nulling bitmap.
Alternatively their relids can be calculated by removing
both_input_relids as well as sjinfo->ojrelid from joinrel->relids. But
in this way we'd have to loop over the whole join_info_list to get the
pushed down joins, which is less efficient than what the patch does.

> But one thought is bugging me: do we have a guarantee, what with these
> Identity 3 transformations and 'delaying up to completely performed'
> technique we don't lose some joininfo clauses?

Are you worried about upper clauses who reference to C vars? In the
second form when we've formed A/B join, which would have both outer
joins' relids in its relid set, the upper clause will be able to be
applied there, and it is the correct join level.

BTW, cfbot reminds that a rebase is needed. So re-attach the two
patches. Now I think it should be in 'Needs review' again in CF. I'll
go and do the change.

Thanks
Richard

On 4/21/23 14:34, Richard Guo wrote:
>
> On Thu, Apr 20, 2023 at 1:06 PM Andrey Lepikhov
> <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
> Are you worried about upper clauses who reference to C vars?  In the
> second form when we've formed A/B join, which would have both outer
> joins' relids in its relid set, the upper clause will be able to be
> applied there, and it is the correct join level.
Yes, of course. I thought about the case with INNER JOINs in between,
something like that:
a LEFT JOIN b ON b.x INNER JOIN c ON (b.x=c.x) LEFT JOIN d ON b.x ...
But, it is still a doubt.
>
> BTW, cfbot reminds that a rebase is needed.  So re-attach the two
> patches.  Now I think it should be in 'Needs review' again in CF.  I'll
> go and do the change.
Thanks!

--
Regards
Andrey Lepikhov
Postgres Professional

On Wed, Mar 1, 2023 at 3:10 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Here's said patch. Although this fixes the described problem and
> passes check-world, I'm not totally happy with it yet: it feels
> like the new add_outer_joins_to_relids() function is too expensive
> to be doing every time we construct a join relation. I wonder if
> there is a way we can add more info to the SpecialJoinInfo data
> structure to make it cheaper. An obvious improvement is to store
> commute_below_l explicitly instead of recomputing it over and over,
> but that isn't going to move the needle all that far. Is there a
> way to not have to scan all the SpecialJoinInfos?

I'm thinking about the way to improve add_outer_joins_to_relids() and
here is what I come up with. When we've completely formed a pushed up
outer join, actually we only need to consider the pushed-down joins that
are in its commute_above_l. But note that this process should be
recursive, meaning that if an outer join in its commute_above_l is also
considered qualified to be added to the relid set, we need to consider
that outer join's commute_above_l too. By this way we only need to
check the relevant SpecialJoinInfos, rather than scan the whole
join_info_list.

To do it we need a way to fetch SpecialJoinInfo by ojrelid. So 0001
patch introduces join_info_array for direct lookups of SpecialJoinInfo
by ojrelid. I find that it also benefits some existing functions, such
as clause_is_computable_at() and have_unsafe_outer_join_ref(). So I
started a new thread for it at [1].

0002 is the original patch that introduces add_outer_joins_to_relids().

0003 patch implements the improvement to add_outer_joins_to_relids().
All the pushed down joins that are needed to check are kept in
commute_above_relids. Each time we fetch and remove the first outer
join from commute_above_relids and check if that outer join is qualified
to be added to the relid set. If so we add it and also add its
commute_above_l to commute_above_relids. This process continues until
commute_above_relids becomes empty.

0004 patch adjusts outer join's target list as described before, but
leverages the new join_info_array to fetch relevant SpecialJoinInfos.

[1]
/message-id/flat/CAMbWs4_EyKimsqkkBAddEW8n1YyPjQd4gmnwYqqHHAUjKkBVQw%40mail.gmail.com

Thanks
Richard

On Thu, May 4, 2023 at 7:22 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> On Wed, Mar 1, 2023 at 3:10 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>> Here's said patch. Although this fixes the described problem and
>> passes check-world, I'm not totally happy with it yet: it feels
>> like the new add_outer_joins_to_relids() function is too expensive
>> to be doing every time we construct a join relation. I wonder if
>> there is a way we can add more info to the SpecialJoinInfo data
>> structure to make it cheaper. An obvious improvement is to store
>> commute_below_l explicitly instead of recomputing it over and over,
>> but that isn't going to move the needle all that far. Is there a
>> way to not have to scan all the SpecialJoinInfos?
>
>
> I'm thinking about the way to improve add_outer_joins_to_relids() and
> here is what I come up with. When we've completely formed a pushed up
> outer join, actually we only need to consider the pushed-down joins that
> are in its commute_above_l. But note that this process should be
> recursive, meaning that if an outer join in its commute_above_l is also
> considered qualified to be added to the relid set, we need to consider
> that outer join's commute_above_l too. By this way we only need to
> check the relevant SpecialJoinInfos, rather than scan the whole
> join_info_list.
>
> To do it we need a way to fetch SpecialJoinInfo by ojrelid. So 0001
> patch introduces join_info_array for direct lookups of SpecialJoinInfo
> by ojrelid. I find that it also benefits some existing functions, such
> as clause_is_computable_at() and have_unsafe_outer_join_ref(). So I
> started a new thread for it at [1].
>
> 0002 is the original patch that introduces add_outer_joins_to_relids().
>
> 0003 patch implements the improvement to add_outer_joins_to_relids().
> All the pushed down joins that are needed to check are kept in
> commute_above_relids. Each time we fetch and remove the first outer
> join from commute_above_relids and check if that outer join is qualified
> to be added to the relid set. If so we add it and also add its
> commute_above_l to commute_above_relids. This process continues until
> commute_above_relids becomes empty.
>
> 0004 patch adjusts outer join's target list as described before, but
> leverages the new join_info_array to fetch relevant SpecialJoinInfos.
>

Hi Tom, how do you think about the v3 patch?

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> Hi Tom, how do you think about the v3 patch?

I need to look at it. $life has been creating large distractions
for me lately, not to mention the release process ...

regards, tom lane

On Sun, May 7, 2023 at 10:39 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> Hi Tom, how do you think about the v3 patch?

Hi Richard,

Thanks for working on this.

Today I reported an issue that Tom speculated might be related, so I
tried these patches and they didn't seem to fix it. It might be an
unrelated problem, but I thought it might be a good idea to put a link
to that thread here just for awareness:

/message-id/CA+TgmoYco=hmg+iX1CW9Y1_CzNoSL81J03wUG-d2_3=rue+L2A@mail.gmail.com

--
Robert Haas
EDB: http://www.enterprisedb.com

On Thu, May 11, 2023 at 12:11 PM Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Sun, May 7, 2023 at 10:39 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> > Hi Tom, how do you think about the v3 patch?
>
> Hi Richard,
>
> Thanks for working on this.
>
> Today I reported an issue that Tom speculated might be related, so I
> tried these patches and they didn't seem to fix it. It might be an
> unrelated problem, but I thought it might be a good idea to put a link
> to that thread here just for awareness:
>
> /message-id/CA+TgmoYco=hmg+iX1CW9Y1_CzNoSL81J03wUG-d2_3=rue+L2A@mail.gmail.com

Seems like it was indeed unrelated.

--
Robert Haas
EDB: http://www.enterprisedb.com

On Fri, May 12, 2023 at 2:21 AM Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> > Today I reported an issue that Tom speculated might be related, so I
> > tried these patches and they didn't seem to fix it. It might be an
> > unrelated problem, but I thought it might be a good idea to put a link
> > to that thread here just for awareness:
> >
> >
> /message-id/CA+TgmoYco=hmg+iX1CW9Y1_CzNoSL81J03wUG-d2_3=rue+L2A@mail.gmail.com
>
> Seems like it was indeed unrelated.

Thanks for reporting that issue. Agreed that it's an unrelated problem
as it's more like a thinko in remove_rel_from_query() as Tom addressed
in c8b881d21f.

Thanks
Richard

I see that what you've been doing here is basically trying to rescue my
previous patch attempt. I'm not in love with that approach anymore.
I think a better fix is to do what I suggested a bit upthread: forcibly
mark upper "C" Vars with both joins in varnullingrels, so that the
planner is always working with upper quals that look like they'd come
from input written according to the second form of the identity.
Here's a patch series that does it that way.

Although this passes check-world for me, there are some loose ends
that could use review:

* Does update_commutable_vars() update everything it needs to?
I modeled it on prepjointree's perform_pullup_replace_vars(), but
since this is happening later during planning there are additional
derived data structures it needs to update. Did I miss any?
Also, is it really necessary to update parse->targetList, or would
updating root->processed_tlist be sufficient at this point?

* As implemented, we'll invoke update_commutable_vars() once per
commutable pair of joins, assuming that they are written in the
first form of identity 3 (which'd be the common case). Is that
costly enough to justify inventing some way to combine the updates
for all such pairs into one querytree traversal?

* I changed the API of add_nulling_relids() so that it could support
updating an RTE_SUBQUERY query. This breaks the possibility of applying
it to the whole main Query (it would make the wrong choice of initial
levelsup), but we never do that. Would it be better to invent an
alternate entry point so that both cases could be supported? Should
remove_nulling_relids be changed similarly?

Also, while checking the test cases shown upthread, I was interested to
notice that this code actually chooses a different join order in some
cases. For the example at [1], v15 does

Nested Loop Left Join (cost=0.00..4.46 rows=16 width=4)
-> Seq Scan on t1 (cost=0.00..1.02 rows=2 width=1)
-> Materialize (cost=0.00..3.26 rows=8 width=3)
-> Nested Loop Left Join (cost=0.00..3.22 rows=8 width=3)
Join Filter: t3.x
-> Nested Loop Left Join (cost=0.00..2.09 rows=4 width=2)
Join Filter: t2.x
-> Seq Scan on t2 (cost=0.00..1.02 rows=2 width=1)
-> Materialize (cost=0.00..1.03 rows=2 width=1)
-> Seq Scan on t3 (cost=0.00..1.02 rows=2 width=1)
-> Materialize (cost=0.00..1.03 rows=2 width=1)
-> Seq Scan on t4 (cost=0.00..1.02 rows=2 width=1)

but with this patch we do

Nested Loop Left Join (cost=0.00..4.45 rows=16 width=4)
Join Filter: t3.x
-> Nested Loop Left Join (cost=0.00..3.22 rows=8 width=3)
-> Seq Scan on t1 (cost=0.00..1.02 rows=2 width=1)
-> Materialize (cost=0.00..2.11 rows=4 width=2)
-> Nested Loop Left Join (cost=0.00..2.09 rows=4 width=2)
Join Filter: t2.x
-> Seq Scan on t2 (cost=0.00..1.02 rows=2 width=1)
-> Materialize (cost=0.00..1.03 rows=2 width=1)
-> Seq Scan on t3 (cost=0.00..1.02 rows=2 width=1)
-> Materialize (cost=0.00..1.03 rows=2 width=1)
-> Seq Scan on t4 (cost=0.00..1.02 rows=2 width=1)

This is correct AFAICS, and it's slightly cheaper, so an optimistic
conclusion would be that we're making a cost-based decision to use a plan
shape that the old code could not find for some reason. But these costs
are pretty close, within the "fuzz factor", so this might be a random
effect. It might be interesting to see if inserting unequal amounts
of data in the tables would drive the costs further apart, allowing
us to say that this code really does beat v15 in terms of planning
flexibility.

regards, tom lane

[1] /message-id/CAMbWs4-_KdVEJ62o6KbtA%2B_KJnQa7WZCc48VsPQ9in6TSN0Kxg%40mail.gmail.com

I wrote:
> This is correct AFAICS, and it's slightly cheaper, so an optimistic
> conclusion would be that we're making a cost-based decision to use a plan
> shape that the old code could not find for some reason. But these costs
> are pretty close, within the "fuzz factor", so this might be a random
> effect. It might be interesting to see if inserting unequal amounts
> of data in the tables would drive the costs further apart, allowing
> us to say that this code really does beat v15 in terms of planning
> flexibility.

Hah, indeed so:

DROP TABLE IF EXISTS t1,t2,t3,t4 CASCADE;
CREATE TABLE t1 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t2 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t3 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t4 AS SELECT true AS x FROM generate_series(0,1000) x;
ANALYZE t1,t2,t3,t4;

EXPLAIN --(COSTS OFF)
select * from t1
left join t2 on true
left join t3 on t2.x
left join t4 on t3.x;

v15 (and HEAD) find a plan of cost 180, this patch finds one
of cost 120. This test case is pretty artificial of course;
can we come up with a more plausible query that we win on?

regards, tom lane

On Sat, May 13, 2023 at 1:25 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> I see that what you've been doing here is basically trying to rescue my
> previous patch attempt. I'm not in love with that approach anymore.
> I think a better fix is to do what I suggested a bit upthread: forcibly
> mark upper "C" Vars with both joins in varnullingrels, so that the
> planner is always working with upper quals that look like they'd come
> from input written according to the second form of the identity.
> Here's a patch series that does it that way.

I explored this approach before and found that there are several
problems with it that we need to resolve to make it work [1]. I
reviewed the patches here and it seems that the second problem still
exists. Quote it here.

* We need to revise how we check if identity 3 applies and if so how we
adjust min_lefthand in make_outerjoininfo. Consider

A leftjoin B on (Pab) leftjoin C on (Pbc) leftjoin D on (Pcd)

So now the C Vars in Pcd are marked with A/B join and B/C join since the
two joins can commute. When it comes to check if C/D join can commute
with B/C join, the A/B join from C Vars' nullingrels would make us think
that C/D join cannot commute with B/C join, which is not correct.
Besides, C/D join's min_lefthand including A/B join is also problematic.

This problem would cause us to be unable to find some join orders. Here
is an example.

create table t (a int, b int);
insert into t select i, i from generate_series(1,1000)i;
analyze t;

explain (costs on)
select * from t t1
left join t t2 on t1.a = t2.a
left join t t3 on t2.a != t3.a
left join t t4 on t3.a = t4.a;

v15 does

QUERY PLAN
--------------------------------------------------------------------------------
Nested Loop Left Join (cost=55.00..15115.00 rows=999000 width=32)
Join Filter: (t2.a <> t3.a)
-> Hash Left Join (cost=27.50..56.25 rows=1000 width=16)
Hash Cond: (t1.a = t2.a)
-> Seq Scan on t t1 (cost=0.00..15.00 rows=1000 width=8)
-> Hash (cost=15.00..15.00 rows=1000 width=8)
-> Seq Scan on t t2 (cost=0.00..15.00 rows=1000 width=8)
-> Materialize (cost=27.50..61.25 rows=1000 width=16)
-> Hash Left Join (cost=27.50..56.25 rows=1000 width=16)
Hash Cond: (t3.a = t4.a)
-> Seq Scan on t t3 (cost=0.00..15.00 rows=1000 width=8)
-> Hash (cost=15.00..15.00 rows=1000 width=8)
-> Seq Scan on t t4 (cost=0.00..15.00 rows=1000
width=8)

but with this patch we do

QUERY PLAN
--------------------------------------------------------------------------------
Hash Left Join (cost=55.00..28837.50 rows=999000 width=32)
Hash Cond: (t3.a = t4.a)
-> Nested Loop Left Join (cost=27.50..15073.75 rows=999000 width=24)
Join Filter: (t2.a <> t3.a)
-> Hash Left Join (cost=27.50..56.25 rows=1000 width=16)
Hash Cond: (t1.a = t2.a)
-> Seq Scan on t t1 (cost=0.00..15.00 rows=1000 width=8)
-> Hash (cost=15.00..15.00 rows=1000 width=8)
-> Seq Scan on t t2 (cost=0.00..15.00 rows=1000
width=8)
-> Materialize (cost=0.00..20.00 rows=1000 width=8)
-> Seq Scan on t t3 (cost=0.00..15.00 rows=1000 width=8)
-> Hash (cost=15.00..15.00 rows=1000 width=8)
-> Seq Scan on t t4 (cost=0.00..15.00 rows=1000 width=8)

We could not find the order (t1/t2)/(t3/t4) because we think that t3/t4
join can not commute with t2/t3. As a result we get a much more
expensive plan (28837.50 VS 15115.00).

Also, it seems that PHVs in outer join's target list are not handled
correctly, check the query below which causes assertion failure in
search_indexed_tlist_for_phv.

# select * from t t1
left join (select now() from t t2
left join t t3 on t2.a = t3.a
left join t t4 on t3.a = t4.a) s on true
inner join t t5 on true;
server closed the connection unexpectedly

BTW, there is a typo in the 0001's subject. It should be
SpecialJoinInfo.commute_below rather than RestrictInfo.commute_below.

[1]
/message-id/CAMbWs4_Bt2YV-geNmLHyS6hmEbkX4C7rV4miaiMUK7%2Be2-gJfQ%40mail.gmail.com

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> On Sat, May 13, 2023 at 1:25 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Here's a patch series that does it that way.

> I explored this approach before and found that there are several
> problems with it that we need to resolve to make it work [1]. I
> reviewed the patches here and it seems that the second problem still
> exists. Quote it here.

Yeah, I realized over the weekend that I'd forgotten to update
deconstruct_distribute_oj_quals, and that the patch was missing some
potential join orders. Notably, the case that I thought was a performance
improvement turned out to be a mirage. It appears that the reason the
planner doesn't find the lowest-cost plan there is that it's following
the heuristic that it should avoid applying clause-free joins when
possible, so in that case it wants to put off the join to t1 as long
as possible. The bug forced it to make that join earlier which turned
out to be good. (I suppose this calls that whole heuristic into question;
but a few days before beta is no time to start revisiting heuristics
we've used for decades.)

> Also, it seems that PHVs in outer join's target list are not handled
> correctly, check the query below which causes assertion failure in
> search_indexed_tlist_for_phv.

Good catch! I think the problem here is that add_nulling_relids() is
being too aggressive: it's adding a nullingrel to a PHV when that's
nonsensical because the PHV is required to be computed above that join.
I fixed it with

- bms_overlap(phv->phrels, context->target_relids))
+ bms_is_subset(phv->phrels, context->target_relids))

which I think is sufficient, though if it proves not to be maybe we could
instead remove phv->phrels from the updated phnullingrels.

> BTW, there is a typo in the 0001's subject. It should be
> SpecialJoinInfo.commute_below rather than RestrictInfo.commute_below.

D'oh. Here's a patchset with these issues addressed.

regards, tom lane

On Tue, May 16, 2023 at 8:03 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> D'oh. Here's a patchset with these issues addressed.

I'm reviewing the v5 patches and I find that the following change in
deconstruct_distribute_oj_quals is suspicious.

if (joins_below)
{
/* Reset serial counter for this version of the quals */
root->last_rinfo_serial = save_last_rinfo_serial;

/*
* Add lower joins' relids to the qual. We should add them to
* Vars coming from the current join's LHS: we want to transform
* the second form of OJ identity 3 to the first form, in which
* Vars of relation B will appear nulled by the
* syntactically-upper OJ within the Pbc clause, but those of
* relation C will not. (In the notation used by
* optimizer/README, we're converting a qual of the form Pbc to
* Pb*c.)
*/
quals = (List *)
add_nulling_relids((Node *) quals,
sjinfo->syn_lefthand,
joins_below);

I doubt this is always right to add joins_below to all the vars
belonging to sjinfo->syn_lefthand. What if the joins in joins_below
cannot commute with each other? As a counterexample, consider the query
below which causes assertion failure in search_indexed_tlist_for_var.
The query is designed so that t1/t2 join cannot commute with t2/t3 join
but can commute with t3/t4 join.

explain (costs off)
select * from t t1
left join t t2 on true
left join t t3 on true
left join t t4 on t2.a = t3.a;
server closed the connection unexpectedly

Also, it seems that this logic may cause us to miss join quals in the
final plan. Consider the query below.

explain (costs off)
select * from t t1
left join t t2 on true
left join t t3 on t2.a = t3.a
left join t t4 on t3.a != t4.a;
QUERY PLAN
------------------------------------------------
Nested Loop Left Join
-> Seq Scan on t t1
-> Materialize
-> Nested Loop Left Join
-> Hash Left Join
Hash Cond: (t2.a = t3.a)
-> Seq Scan on t t2
-> Hash
-> Seq Scan on t t3
-> Materialize
-> Seq Scan on t t4
(11 rows)

So we've missed join qual 't3.a != t4.a' in this plan shape. For this
join qual , deconstruct_distribute_oj_quals() generated two versions,
one with empty nullingrels, the other with nullingrels {t1/t2, t2/t3}.
Both are not applicable at join level (t2/t3)/t4. I think we should
have another version with nullingrels {t2/t3} for this qual.

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> I doubt this is always right to add joins_below to all the vars
> belonging to sjinfo->syn_lefthand. What if the joins in joins_below
> cannot commute with each other? As a counterexample, consider the query
> below which causes assertion failure in search_indexed_tlist_for_var.
> The query is designed so that t1/t2 join cannot commute with t2/t3 join
> but can commute with t3/t4 join.

> explain (costs off)
> select * from t t1
> left join t t2 on true
> left join t t3 on true
> left join t t4 on t2.a = t3.a;

Hm. Actually, t1/t2 *can't* commute with the t4 join. You can re-order
the t2 and t3 joins per identity 2:

select * from t t1
left join t t3 on true
left join t t2 on true
left join t t4 on t2.a = t3.a;

but you're still stuck, identity 3 applies nowhere (because in either
case, the putative Pbc clause has also got a reference to A).

make_outerjoininfo is setting the t4 join's commute_below_l to include
t1/t2, but it seems to me that that indicates inadequate analysis in
make_outerjoininfo. Is there still a problem here if we get rid of
that overoptimistic conclusion? We should strive to do so even if
it's not fixing an observable problem, because in any case it's
causing the planner to waste time on unreachable join orders.

regards, tom lane

After further poking at this, I've concluded that you're right and
we should not try to make the "add extra nullingrels all the time"
approach work. It still seems theoretically cleaner to me, but
there are too many messy special cases.

Accordingly, here's a reviewed/revised version of the v3 patch series
you posted earlier. Significant changes:

* I was not impressed by the idea of adding a join_info_array to look
up by ojrelid. It seemed to me that your changes around that replaced
foreach loops over join_info_list with bms_next_member loops over
relid sets that you often had to do extra calculations to create.
Whether that's a performance win at all is debatable. Moreover,
I realized from testing this that situations where there are
pushed-down OJs are pretty rare (there are *none* in the core
regression tests before the cases added below), so optimizing for
that at the cost of extra cycles when it doesn't happen is probably
not the way.

* I did keep the idea of splitting up commute_below from my other
patch series. That's 0001 below and then I rebased 0002-0004 on
that.

* I'm not terribly happy with 0004 as it stands, specifically the
business of making build_join_rel recalculate pushed_down_ojrelids
from scratch. Again, that's adding cycles to the mainline case to
support an unusual case. It'd be better to make
add_outer_joins_to_relids have an extra output that is the
pushed_down_ojrelids set, and pass that forward. I ran out of time
to make that happen today, though.

* 0005 below adds the original test case and cases based on the other
examples given at various points in this thread. I put that last
because until 0004 one or the other of these tests fails miserably.
All the expected outputs here match what v15 does.

* While I've not done it here, I'm seriously considering reverting
those Asserts in setrefs.c back to somewhat-informative elogs,
at least till late in beta. It seems like we are still at a point
where we need to make it easy to acquire info about failures in this
logic, and using Asserts isn't all that conducive to that.

regards, tom lane

On Wed, May 17, 2023 at 11:10 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> * I'm not terribly happy with 0004 as it stands, specifically the
> business of making build_join_rel recalculate pushed_down_ojrelids
> from scratch. Again, that's adding cycles to the mainline case to
> support an unusual case. It'd be better to make
> add_outer_joins_to_relids have an extra output that is the
> pushed_down_ojrelids set, and pass that forward. I ran out of time
> to make that happen today, though.

Actually I did that in this way before I invented the join_info_array
thing. See patch 'v2-0001-Adjust-outer-join-s-target-list.patch' in
/message-id/CAMbWs49CB3txv_s3SwC1L2h1DiUPAn%2Bv0-O4UFfg33b%2BHXNnTg%40mail.gmail.com

A little difference is that that patch makes add_outer_joins_to_relids
collect pushed down joins rather than pushed down ojrelids, so that in
build_joinrel_tlist we can just loop over pushed down joins rather than
the whole join_info_list.

I rebased that patch on the v6 patch series and that is 0006 in the
attachment.

* While I've not done it here, I'm seriously considering reverting
> those Asserts in setrefs.c back to somewhat-informative elogs,
> at least till late in beta. It seems like we are still at a point
> where we need to make it easy to acquire info about failures in this
> logic, and using Asserts isn't all that conducive to that.

Agreed. While debugging in my local branch I usually replace the
related Asserts with elogs, to avoid frequent server crashes and to make
it easy for attaching to a live process with gdb.

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> On Wed, May 17, 2023 at 11:10 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> * I'm not terribly happy with 0004 as it stands, specifically the
>> business of making build_join_rel recalculate pushed_down_ojrelids
>> from scratch. Again, that's adding cycles to the mainline case to
>> support an unusual case. It'd be better to make
>> add_outer_joins_to_relids have an extra output that is the
>> pushed_down_ojrelids set, and pass that forward. I ran out of time
>> to make that happen today, though.

> Actually I did that in this way before I invented the join_info_array
> thing. See patch 'v2-0001-Adjust-outer-join-s-target-list.patch' in
> /message-id/CAMbWs49CB3txv_s3SwC1L2h1DiUPAn%2Bv0-O4UFfg33b%2BHXNnTg%40mail.gmail.com
> A little difference is that that patch makes add_outer_joins_to_relids
> collect pushed down joins rather than pushed down ojrelids, so that in
> build_joinrel_tlist we can just loop over pushed down joins rather than
> the whole join_info_list.

Ah, good idea. I made some cosmetic adjustments and pushed the lot.

We still have a couple of loose ends in this thread:

1. Do we need the change in add_nulling_relids that I postulated in [1]?

- bms_overlap(phv->phrels, context->target_relids))
+ bms_is_subset(phv->phrels, context->target_relids))

The test case that made that fall over no longer does so, but I'm
suspicious that this is still needed. I'm not quite sure though,
and I'm even less sure about the corresponding change in
remove_nulling_relids:

- !bms_overlap(phv->phrels, context->except_relids))
+ !bms_is_subset(phv->phrels, context->except_relids))

which I made up pretty much out of whole cloth.

2. Can we do anything to tighten make_outerjoininfo's computation of
potential commutator pairs, as I speculated in [2]? This isn't a bug
hazard anymore (I think), but adding useless bits there clearly does
cause us to waste cycles later. If we can tighten that cheaply, it
should be a win.

3. In general, it seems like what your fixes are doing is computing
transitive closures of the commute_above relationships. I wonder if
we can save anything by pre-calculating the closure sets. Again,
I don't want to add cycles in cases where the whole thing doesn't
apply, but maybe we'd not have to.

regards, tom lane

[1] /message-id/2489296.1684195396%40sss.pgh.pa.us
[2] /message-id/2766442.1684265014%40sss.pgh.pa.us

On Wed, May 17, 2023 at 11:28 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Ah, good idea. I made some cosmetic adjustments and pushed the lot.

Thanks for pushing it!

> We still have a couple of loose ends in this thread:
>
> 1. Do we need the change in add_nulling_relids that I postulated in [1]?
>
> - bms_overlap(phv->phrels, context->target_relids))
> + bms_is_subset(phv->phrels, context->target_relids))
>
> The test case that made that fall over no longer does so, but I'm
> suspicious that this is still needed. I'm not quite sure though,
> and I'm even less sure about the corresponding change in
> remove_nulling_relids:
>
> - !bms_overlap(phv->phrels, context->except_relids))
> + !bms_is_subset(phv->phrels,
> context->except_relids))
>
> which I made up pretty much out of whole cloth.

I'm not sure either. I cannot think of a scenario where this change
would make a difference. But I think this change is good to have. It
is more consistent with how we check if a PHV belongs to a relid set in
build_joinrel_tlist(), where we use

bms_is_subset(phv->phrels, sjinfo->syn_righthand)

to check if the PHV comes from within the syntactically nullable side of
the outer join.

> 2. Can we do anything to tighten make_outerjoininfo's computation of
> potential commutator pairs, as I speculated in [2]? This isn't a bug
> hazard anymore (I think), but adding useless bits there clearly does
> cause us to waste cycles later. If we can tighten that cheaply, it
> should be a win.

Agreed that we should try our best to get rid of non-commutable outer
joins from commute_below_l. Not sure how to do that currently. Maybe
we can add a TODO item for now?

> 3. In general, it seems like what your fixes are doing is computing
> transitive closures of the commute_above relationships. I wonder if
> we can save anything by pre-calculating the closure sets. Again,
> I don't want to add cycles in cases where the whole thing doesn't
> apply, but maybe we'd not have to.

Maybe we can pre-calculate the commute_above closure sets in
make_outerjoininfo and save it in SpecialJoinInfo? I haven't thought
through this.

BTW, it seems that there is a minor thinko in the changes. In the
outer-join removal logic, we use syn_xxxhand to compute the relid set
for the join we are considering to remove. I think this might be not
right, because the outer joins may not be performed in syntactic order.
Consider the query below

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

explain (costs off)
select 1 from t t1
left join (t t2 left join t t3 on t2.a = 1) on t2.a = 1;
server closed the connection unexpectedly

Attached is a patch to revert this logic to what it looked like before.

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> BTW, it seems that there is a minor thinko in the changes. In the
> outer-join removal logic, we use syn_xxxhand to compute the relid set
> for the join we are considering to remove. I think this might be not
> right, because the outer joins may not be performed in syntactic order.

No, I don't believe that. What we are interested in at this point is
the semantic effect (or lack of it) of the potentially-removable join.
It's fine to reason about that under the assumption that the joins will
be done in syntactic order. If later parts of the planner decide to
implement the joins in a different order, that cannot change the
conclusion about whether it's safe to remove a join --- otherwise,
either we were mistaken to remove the join, or the reordering logic
is wrong.

I prefer the code as it stands now because it helps to decouple the
join-removal reasoning from the join-reordering logic, limiting any
possible effect of bugs in the latter. (I think I might've had
some other reason for changing it as well, but can't reconstruct
that first thing in the morning.)

regards, tom lane

On Thu, May 18, 2023 at 9:28 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> > BTW, it seems that there is a minor thinko in the changes. In the
> > outer-join removal logic, we use syn_xxxhand to compute the relid set
> > for the join we are considering to remove. I think this might be not
> > right, because the outer joins may not be performed in syntactic order.
>
> No, I don't believe that. What we are interested in at this point is
> the semantic effect (or lack of it) of the potentially-removable join.
> It's fine to reason about that under the assumption that the joins will
> be done in syntactic order. If later parts of the planner decide to
> implement the joins in a different order, that cannot change the
> conclusion about whether it's safe to remove a join --- otherwise,
> either we were mistaken to remove the join, or the reordering logic
> is wrong.

Yeah, I think this is where the problem is. Using syn_xxxhand in
join_is_removable will cause us to be mistaken to think the join is
removable in some cases, because we might fail to notice the inner-rel
attributes are used above the join as we are checking the syntactic
relid set of the join.

Take the query shown upthread as an example, which would trigger an
Assert.

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

explain (costs off)
select 1 from t t1
left join (t t2 left join t t3 on t2.a = 1) on t2.a = 1;
server closed the connection unexpectedly

We'd be mistaken to think t1/t2 join is removable, because we are
checking its syntactic relid set, which includes all rels, and so that
are not aware that t2.a is used by t2/t3 join.

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> Take the query shown upthread as an example, which would trigger an
> Assert.

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

> explain (costs off)
> select 1 from t t1
> left join (t t2 left join t t3 on t2.a = 1) on t2.a = 1;
> server closed the connection unexpectedly

> We'd be mistaken to think t1/t2 join is removable, because we are
> checking its syntactic relid set, which includes all rels, and so that
> are not aware that t2.a is used by t2/t3 join.

Ah, now your point has finally penetrated my thick skull: we can't
remove a join if its output is referenced at any join level that
we could potentially postpone past the join of interest, even
when that join is syntactically below it. It seems like there
might be more than one way to skin that cat; maybe we could remove
it anyway and restrict the join order later? But I agree that
three days before beta isn't the time to be rethinking the join
removal rules.

I remembered why it was that I wanted to change this logic, though.
It wasn't totally clear to me that min_lefthand + min_righthand
would account properly for outer joins below the one of interest.
However, considering it now it seems like that will hold, so now
I think your patch is correct.

regards, tom lane

On 5/19/23 23:50, Tom Lane wrote:
> Richard Guo <guofenglinux(at)gmail(dot)com> writes:
>> ...
>> We'd be mistaken to think t1/t2 join is removable, because we are
>> checking its syntactic relid set, which includes all rels, and so that
>> are not aware that t2.a is used by t2/t3 join.
> ...
> I think your patch is correct.

Because the feature pushed into the master, I checked it with the
sqlancer tests. During all-weekend run no any problems were found.

--
Regards
Andrey Lepikhov
Postgres Professional

Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru> writes:
> Because the feature pushed into the master, I checked it with the
> sqlancer tests. During all-weekend run no any problems were found.

Thanks for looking! I strongly suspect that there still are some
problems in this area, but hopefully they are rare enough to go to
beta with. I'll keep thinking about the issue.

regards, tom lane