Re: Removing unneeded self joins

[Dean Rasheed]

On Sat, 20 Jul 2024 at 12:39, Alexander Korotkov  wrote:
>
> > The new function replace_relid() looks to be the same as adjust_relid_set().
>
> They are similar, not the same.  replace_relid() has handling for
> negative newId, while adjust_relid_set() hasn't.  One thing I'd like
> to borrow from adjust_relid_set() to replace_relid() is the usage of
> IS_SPECIAL_VARNO() macro.

Ah, that makes sense. In that case, I'd say that replace_relid()
should go in analyzejoins.c (and be a local function there), since
that's the only place that requires this special negative newId
handling.

> It would be probably nice to move this logic into bms_replace_member()
> residing at bitmapset.c.  What do you think?

Maybe. It feels a little specialised though, so maybe it's not worth the effort.

I have been reviewing more of the patch, mainly focusing on the logic
in analyzejoins.c that decides when to apply SJE.

I understand broadly what the code is doing, but I still find it
somewhat hard to follow. One thing that makes it hard is that in
analyzejoins.c, "inner" and "outer" get swapped round at various
points. For example generate_join_implied_equalities() is defined like
this:

List *
generate_join_implied_equalities(PlannerInfo *root,
 Relids join_relids,
 Relids outer_relids,
 RelOptInfo *inner_rel,
 SpecialJoinInfo *sjinfo);

but remove_self_joins_one_group() calls it like this:

restrictlist = generate_join_implied_equalities(root, joinrelids,
inner->relids,
outer, NULL);

So you have to remember that "inner" is "outer" and "outer" is "inner"
when going into generate_join_implied_equalities() from
remove_self_joins_one_group(). And the same thing happens when calling
innerrel_is_unique_ext() and match_unique_clauses(). I think all that
could be resolved by swapping "inner" and "outer" in the variable
names and comments in remove_self_joins_one_group().

Another thing I noticed in remove_self_joins_one_group() was this:

/*
 * To enable SJE for the only degenerate case without any self
 * join clauses at all, add baserestrictinfo to this list. The
 * degenerate case works only if both sides have the same clause.
 * So doesn't matter which side to add.
 */
selfjoinquals = list_concat(selfjoinquals, outer->baserestrictinfo);

That appears to be pointless, because is_innerrel_unique_for() will
filter the restrictlist it is given, removing those baserestrictinfo
clauses (because I think they'll always have can_join = false). And
then relation_has_unique_index_ext() will re-add them:

/*
 * Examine the rel's restriction clauses for usable var = const clauses
 * that we can add to the restrictlist.
 */
foreach(ic, rel->baserestrictinfo)
{
... add suitable clauses
}

where "rel" is "innerrel" from is_innerrel_unique_for(), which is
"outer" from remove_self_joins_one_group(), so it's the same set of
baserestrictinfo clauses.

Something else that looks a little messy is this in innerrel_is_unique_ext():

/*
 * innerrel_is_unique_ext
 *Do the same as innerrel_is_unique(), but also set to '*extra_clauses'
 *additional clauses from a baserestrictinfo list that were used to prove
 *uniqueness.  A non NULL 'extra_clauses' indicates that we're checking
 *for self-join and correspondingly dealing with filtered clauses.
 */
bool
innerrel_is_unique_ext(PlannerInfo *root,
   ...
   List **extra_clauses)
{
boolself_join = (extra_clauses != NULL);

[logic depending on self_join]
}

This presumes that any caller interested in knowing the extra
baserestrictinfo clauses used to prove uniqueness must be looking at a
self join. That may be true today, but it doesn't seem like a good API
design choice. I think it would be better to just add "self_join" as
an extra parameter, and also maybe have the function return the
UniqueRelInfo containing the "extra_clauses", or NULL if it's not
unique. That way, it would be more extensible, if we wanted it to
return more information in the future.

Instead of adding relation_has_unique_index_ext(), maybe it would be
OK to just change the signature of relation_has_unique_index_for(). It
looks like it's only called from one other place outside
analyzejoins.c. Perhaps the same is true for innerrel_is_unique_ext().

Should match_unique_clauses() be comparing mergeopfamilies or opnos to
ensure that the clauses are using the same equality operator?

Regards,
Dean

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 20/7/2024 18:38, Alexander Korotkov wrote:

On Fri, Jul 19, 2024 at 11:30 AM Dean Rasheed  wrote:

On Wed, 17 Jul 2024 at 01:45, Alexander Korotkov  wrote:

We initially didn't use ChangeVarNodes() in SJE at all.  See the last
patch version without it [1].  We're trying to address Tom Lane's
proposal to re-use more of existing tree-manipulation infrastructure
[2].  I agree with you that the case with ChangeVarNodes() looks
questionable.  Do you have other ideas how we can re-use some more of
existing tree-manipulation infrastructure in SJE?
As I can see, ChangeVarNodes is dedicated to working with the query tree 
before the planning phase. SJE works right in the middle of the planning 
process. So, it may be more practical to keep it separate as a walker, 
as Dean has proposed. If the optimisation stuff changes, the walker code 
will be changed, too.


--
regards, Andrei Lepikhov

Re: Removing unneeded self joins

[Dean Rasheed]

On Wed, 17 Jul 2024 at 01:45, Alexander Korotkov  wrote:
>
> Jian He gave a try to ChangeVarNodes() [1].  That gives some
> improvement, but the vast majority of complexity is still here. I
> think the reason for complexity of SJE is that it's the first time we
> remove relation, which is actually *used* and therefore might has
> references in awful a lot of places.  In previous cases we removed
> relations, which were actually unused.
>

I had a quick look at this, and I have a couple of comments on the
rewriter changes.

The new function replace_relid() looks to be the same as adjust_relid_set().

The changes to ChangeVarNodes() look a little messy. There's a lot of
code duplicated between ChangeVarNodesExtended() and ChangeVarNodes(),
which could be avoided by having one call the other. Also, it would be
better for ChangeVarNodesExtended() to have a "flags" parameter
instead of an extra boolean parameter, to make it more extensible in
the future. However,...

I question whether ChangeVarNodesExtended() and the changes to
ChangeVarNodes() are really the right way to go about this.
ChangeVarNodes() in particular gains a lot more logic to handle
RestrictInfo nodes that doesn't really feel like it belongs there --
e.g., building  NullTest nodes is really specific to SJE, and doesn't
seem like it's something ChangeVarNodes() should be doing.

A better solution might be to add a new walker function to
analyzejoins.c that does just what SJE needs, which is different from
ChangeVarNodes() in a number of ways. For Var nodes, it might
ultimately be necessary to do more than just change the varno, to
solve the RETURNING/EPQ problems. For RestrictInfo nodes, there's a
lot of SJE-specific logic. The SJE code wants to ignore RangeTblRef
nodes, but it could delegate to ChangeVarNodes() for various other
node types to avoid code duplication. At the top level, the stuff that
ChangeVarNodes() does to fields of the Query struct would be different
for SJE, I think.

Regards,
Dean

Re: Removing unneeded self joins

[Pogosyan Vardan]

On 16.07.2024 21:30, Alexander Korotkov wrote:

Hi, Vardan!

Great, thank you!

On Tue, Jul 16, 2024 at 5:26 PM Вардан Погосян wrote:

I did the SJE testing at Andrey's request.
To do this, I used the automatic testing tool EET (Equivalent Expression 
Transformation) [1] with some modifications.
EET transforms the logical conditions in a query, creating multiple queries 
waiting for the same number of rows.

What revision of patch did you use?



I used Andrey's v4 patches.



In order to make sure that the SJE logic is executed at all, I tried to cover 
the code with ereports() as much as possible.

Could you share this?  Probably some of these ereports() we would like to keep.


I'm not sure if it can be saved. Many reports are some messy and no 
information that is really useful for the user.




During the testing process, I did not find any inconsistencies in the number of 
rows returned, as well as other critical problems.

Did you use assert-enabled build?  I guess you mean no server crashes,
right?  Also, could you share some statistics on how long did you run,
what number of queries did you execute etc.?

--
Regards,
Alexander Korotkov
Supabase


Of course, i used assertion-enabled build and server didn't fail.

EET ran 10 iterations with 100 random generated queries + 100 
transformed queries => 2000 queries in total.


I can't calculate exactly how many clauses EET generates after 
transformations, but according to rough estimates for all test time, 
about 8-9% clauses detected as self join during the entire testing period.


The last query saved by EET contains 4 clauses, and after 
transformations, the new query contains ~132 clauses. SJE was not used 
in the original query, but it was used 5 times after the conversion.

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi, Tom!

I'd like to give you and update on the progress with SJE.

On Mon, May 6, 2024 at 6:54 PM Tom Lane  wrote:
> Robert Haas  writes:
> > I want to go on record right now as disagreeing with the plan proposed
> > in the commit message for the revert commit, namely, committing this
> > again early in the v18 cycle. I don't think Tom would have proposed
> > reverting this feature unless he believed that it had more serious
> > problems than could be easily fixed in a short period of time. I think
> > that concern is well-founded, given the number of fixes that were
> > committed. It seems likely that the patch needs significant rework and
> > stabilization before it gets committed again, and I think it shouldn't
> > be committed again without explicit agreement from Tom or one of the
> > other committers who have significant experience with the query
> > planner.
>
> FWIW I accept some of the blame here, for not having paid any
> attention to the SJE work earlier.  I had other things on my mind
> for most of last year, and not enough bandwidth to help.
>
> The main thing I'd like to understand before we try this again is
> why SJE needed so much new query-tree-manipulation infrastructure.
> I would have expected it to be very similar to the left-join
> elimination we do already, and therefore to mostly just share the
> existing infrastructure.  (I also harbor suspicions that some of
> the new code existed just because someone didn't research what
> was already there --- for instance, the now-removed replace_varno
> sure looks like ChangeVarNodes should have been used instead.)

Jian He gave a try to ChangeVarNodes() [1].  That gives some
improvement, but the vast majority of complexity is still here. I
think the reason for complexity of SJE is that it's the first time we
remove relation, which is actually *used* and therefore might has
references in awful a lot of places.  In previous cases we removed
relations, which were actually unused.

There are actually alternative designs for this feature.  I've
proposed "alias relids" before [2].  But it's not clear we will
resolve more problems than create, given that it could break awfully a
lot of assumptions during query planning.  Andrei also proposed that
perl script could generate us a walker over planner structures [3].
Although this method might offer a structured approach, it seems like
overengineering for the problem at hand.

I believe it's worth giving the current approach another chance.
Vardan Pogosyan has conducted some tests, and I am in the process of
clarifying the details.  We could enhance the approach by adding more
comments to ensure that any changes in the planner data structure are
flagged for potential revisions in the SJE code.  What do you think?

> Another thing that made me pretty sad was 8c441c082 (Forbid SJE with
> result relation).  While I don't claim that that destroyed the entire
> use case for SJE, it certainly knocked its usefulness down by many
> notches, maybe even to the point where it's not worth putting in the
> effort needed to get it to re-committability.  So I think we need to
> look harder at finding a way around that.  Is the concern that
> RETURNING should return either old or new values depending on which
> RTE is mentioned?  If so, maybe the feature Dean has proposed to
> allow RETURNING to access old values [1] is a prerequisite to moving
> forward.  Alternatively, perhaps it'd be good enough to forbid SJE
> only when the non-target relation is actually mentioned in RETURNING.

As Andrei pointed it's possible to apply SJE to result relation [4],
but where it's not a target relation.   I guess the target relation
case is what you're most interested.  In this case we hit problem of
joining relation having different row marks.  In turn that triggers
EPQ problem [5] and probably more.  In order to resolve that we need a
way to store multiple (at least two, but sure if more is needed)
tuples for relation.  I still feel that we should postpone that,
because even basic SJE without target relation support is challenging.

There is probably a way to implement target relation support for PG18
after committing basic SJE.  But that would require a lot of your
design work and guidance.  I don't dare to design this kind of things.

Links.
1. 
https://www.postgresql.org/message-id/CACJufxHBLhOD1LerM643dgh%3DUZFGhPWfP1027D2x1W6DhF_BaQ%40mail.gmail.com
2. 
https://www.postgresql.org/message-id/CAPpHfdv6B8HCLdj8WidBryRrX0%2BX3F1rrR8uAuMQmp6rvPdscg%40mail.gmail.com
3. 
https://www.postgresql.org/message-id/96250a42-20e3-40f0-9d45-f53ae852f8ed%40gmail.com
4. 
https://www.postgresql.org/message-id/5b49501c-9cb3-4c5d-9d56-49704ff08143%40gmail.com
5. 
https://www.postgresql.org/message-id/flat/CAPpHfduM6X82ExT0r9UzFLJ12wOYPvRw5vT2Htq0gAPBgHhKeQ%40mail.gmail.com

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi, Vardan!

Great, thank you!

On Tue, Jul 16, 2024 at 5:26 PM Вардан Погосян  wrote:
> I did the SJE testing at Andrey's request.
> To do this, I used the automatic testing tool EET (Equivalent Expression 
> Transformation) [1] with some modifications.
> EET transforms the logical conditions in a query, creating multiple queries 
> waiting for the same number of rows.

What revision of patch did you use?

> In order to make sure that the SJE logic is executed at all, I tried to cover 
> the code with ereports() as much as possible.

Could you share this?  Probably some of these ereports() we would like to keep.

> During the testing process, I did not find any inconsistencies in the number 
> of rows returned, as well as other critical problems.

Did you use assert-enabled build?  I guess you mean no server crashes,
right?  Also, could you share some statistics on how long did you run,
what number of queries did you execute etc.?

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[Вардан Погосян]

Hi! I did the SJE testing at Andrey's request.To do this, I used the automatic testing tool EET (Equivalent _expression_ Transformation) [1] with some modifications. EET transforms the logical conditions in a query, creating multiple queries waiting for the same number of rows. In order to make sure that the SJE logic is executed at all, I tried to cover the code with ereports() as much as possible.During the testing process, I did not find any inconsistencies in the number of rows returned, as well as other critical problems.  [1] https://github.com/JZuming/EET -- Regards,Vardan Pogosyan 

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 7/15/24 14:35, jian he wrote:

On Mon, Jul 15, 2024 at 2:08 PM Andrei Lepikhov  wrote:


On 7/15/24 12:31, jian he wrote:

hi.
Here is the latest patch (v6),
I've made the following changes.

* disallow original Query->resultRelation participate in SJE.
for SELECT, nothing is changed. for UPDATE/DELETE/MERGE
we can do:
EXPLAIN (COSTS OFF)
UPDATE sj sq SET b = sq.b + sz.a FROM (select s1.* from sj s1 join sj
s2 on s1.a = s2.a) as sz
WHERE sz.a = sq.a;

here, only "(select s1.* from sj s1 join sj s2 on s1.a = s2.a)" can
apply to SJE.

but for now we cannot apply SJE to
EXPLAIN (COSTS OFF)
UPDATE sj sq SET b = sq.b + sz.a FROM sj as sz WHERE sz.a = sq.a;

so the EPQ abnormality issue[1] won't happen.


* add a new function: ChangeVarNodesExtended for
address concerns in  [2]

I see you still stay with the code line:
if (omark && imark && omark->markType != imark->markType)

It is definitely an error. What if omark is NULL, but imark is not? Why
not to skip this pair of relids? Or, at least, insert an assertion to
check that you filtered it earlier.



i  think "omark is NULL, but imark is not" case won't reach to
remove_self_joins_one_group.
In that case, omark associated RangeTblEntry->rtekind will be RTE_SUBQUERY,
and will be skipped earlier in remove_self_joins_recurse.


Still, do you think the following code is the right way to go?

if ((omark == NULL && imark != NULL) ||
(omark != NULL && imark == NULL) ||
(omark && imark && omark->markType != imark->markType))
   continue;
Sure, if query block needs RowMark it applies proper RowMark to each 
base relation. All pull-up transformations executes before this code.
But it is worth to set Assert at the point to check that nothing changed 
in the code above and the patch works correctly, am I wrong?



--
regards, Andrei Lepikhov

Re: Re: Removing unneeded self joins

[jian he]

On Mon, Jul 15, 2024 at 2:08 PM Andrei Lepikhov  wrote:
>
> On 7/15/24 12:31, jian he wrote:
> > hi.
> > Here is the latest patch (v6),
> > I've made the following changes.
> >
> > * disallow original Query->resultRelation participate in SJE.
> > for SELECT, nothing is changed. for UPDATE/DELETE/MERGE
> > we can do:
> > EXPLAIN (COSTS OFF)
> > UPDATE sj sq SET b = sq.b + sz.a FROM (select s1.* from sj s1 join sj
> > s2 on s1.a = s2.a) as sz
> > WHERE sz.a = sq.a;
> >
> > here, only "(select s1.* from sj s1 join sj s2 on s1.a = s2.a)" can
> > apply to SJE.
> >
> > but for now we cannot apply SJE to
> > EXPLAIN (COSTS OFF)
> > UPDATE sj sq SET b = sq.b + sz.a FROM sj as sz WHERE sz.a = sq.a;
> >
> > so the EPQ abnormality issue[1] won't happen.
> >
> >
> > * add a new function: ChangeVarNodesExtended for
> > address concerns in  [2]
> I see you still stay with the code line:
> if (omark && imark && omark->markType != imark->markType)
>
> It is definitely an error. What if omark is NULL, but imark is not? Why
> not to skip this pair of relids? Or, at least, insert an assertion to
> check that you filtered it earlier.
>

i  think "omark is NULL, but imark is not" case won't reach to
remove_self_joins_one_group.
In that case, omark associated RangeTblEntry->rtekind will be RTE_SUBQUERY,
and will be skipped earlier in remove_self_joins_recurse.


Still, do you think the following code is the right way to go?

if ((omark == NULL && imark != NULL) ||
(omark != NULL && imark == NULL) ||
(omark && imark && omark->markType != imark->markType))
  continue;

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 7/15/24 12:31, jian he wrote:

hi.
Here is the latest patch (v6),
I've made the following changes.

* disallow original Query->resultRelation participate in SJE.
for SELECT, nothing is changed. for UPDATE/DELETE/MERGE
we can do:
EXPLAIN (COSTS OFF)
UPDATE sj sq SET b = sq.b + sz.a FROM (select s1.* from sj s1 join sj
s2 on s1.a = s2.a) as sz
WHERE sz.a = sq.a;

here, only "(select s1.* from sj s1 join sj s2 on s1.a = s2.a)" can
apply to SJE.

but for now we cannot apply SJE to
EXPLAIN (COSTS OFF)
UPDATE sj sq SET b = sq.b + sz.a FROM sj as sz WHERE sz.a = sq.a;

so the EPQ abnormality issue[1] won't happen.


* add a new function: ChangeVarNodesExtended for
address concerns in  [2]

I see you still stay with the code line:
if (omark && imark && omark->markType != imark->markType)

It is definitely an error. What if omark is NULL, but imark is not? Why 
not to skip this pair of relids? Or, at least, insert an assertion to 
check that you filtered it earlier.


--
regards, Andrei Lepikhov

Re: Removing unneeded self joins

[Alexander Korotkov]

On Fri, Jul 12, 2024 at 1:30 PM Alexander Korotkov  wrote:
> On Fri, Jul 12, 2024 at 6:05 AM Andrei Lepikhov  wrote:
> > On 7/11/24 14:43, jian he wrote:
> > > On Tue, Jul 9, 2024 at 2:06 PM Andrei Lepikhov  wrote:
> > >>
> > >> On 7/2/24 07:25, jian he wrote:
> > >>> to make sure it's correct, I have added a lot of tests,
> > >>> Some of this may be contrived, maybe some of the tests are redundant.
> > >> Thanks for your job!
> > >> I passed through the patches and have some notes:
> > >> 1. Patch 0001 has not been applied anymore since the previous week's
> > >> changes in the core. Also, there is one place with trailing whitespace.
> > >
> > > thanks.
> > > because the previous thread mentioned the EPQ problem.
> > > in remove_useless_self_joins, i make it can only process CMD_SELECT query.
> > I would like to oppose here: IMO, it is just a mishap which we made
> > because of a long history of patch transformations. There we lost the
> > case where RowMark exists for only one of candidate relations.
> > Also, after review I think we don't need so many new tests. Specifically
> > for DML we already have one:
> >
> > EXPLAIN (COSTS OFF)
> > UPDATE sj sq SET b = 1 FROM sj as sz WHERE sq.a = sz.a;
> >
> > And we should just add something to elaborate it a bit.
> > See the patch in attachment containing my proposal to improve v4-0001
> > main SJE patch. I think it resolved the issue with EPQ assertion as well
> > as problems with returning value.
>
> I tried this.  I applied 0001 from [1] and 0002 from [2].  Then I
> tried the concurrent test case [3].  It still fails with assert for
> me.  But assert and related stuff is the least problem.  The big
> problem, as described in [3], is semantical change in query.  When EPQ
> is applied, we fetch the latest tuple of the target relation
> regardless snapshot.  But for the self-joined relation we should still
> use the snapshot-satisfying tuple.  I don't see even attempt to
> address this in your patch.  And as I pointed before, this appears
> quite complex.

Oh, sorry, I used wrong binaries during the check.  My test case works
correctly, because SJE doesn't apply to the target relation.

# explain update test set val = t.val + 1 from test t where test.id = t.id;
 QUERY PLAN
-
 Update on test  (cost=60.85..105.04 rows=0 width=0)
   ->  Hash Join  (cost=60.85..105.04 rows=2260 width=16)
 Hash Cond: (test.id = t.id)
 ->  Seq Scan on test  (cost=0.00..32.60 rows=2260 width=10)
 ->  Hash  (cost=32.60..32.60 rows=2260 width=14)
   ->  Seq Scan on test t  (cost=0.00..32.60 rows=2260 width=14)
(6 rows)

Previously, patch rejected applying SJE for result relation, which as
I see now is wrong.  Andrei's patch rejects SJE for target relation on
the base of row marks, which seems correct to me as the first glance.
So, this doesn't change anything regarding my conclusions regarding
applying SJE for target relation.  But the Andrei's patch yet looks
good indeed.

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi, Andrei!

On Fri, Jul 12, 2024 at 6:05 AM Andrei Lepikhov  wrote:
>
> On 7/11/24 14:43, jian he wrote:
> > On Tue, Jul 9, 2024 at 2:06 PM Andrei Lepikhov  wrote:
> >>
> >> On 7/2/24 07:25, jian he wrote:
> >>> to make sure it's correct, I have added a lot of tests,
> >>> Some of this may be contrived, maybe some of the tests are redundant.
> >> Thanks for your job!
> >> I passed through the patches and have some notes:
> >> 1. Patch 0001 has not been applied anymore since the previous week's
> >> changes in the core. Also, there is one place with trailing whitespace.
> >
> > thanks.
> > because the previous thread mentioned the EPQ problem.
> > in remove_useless_self_joins, i make it can only process CMD_SELECT query.
> I would like to oppose here: IMO, it is just a mishap which we made
> because of a long history of patch transformations. There we lost the
> case where RowMark exists for only one of candidate relations.
> Also, after review I think we don't need so many new tests. Specifically
> for DML we already have one:
>
> EXPLAIN (COSTS OFF)
> UPDATE sj sq SET b = 1 FROM sj as sz WHERE sq.a = sz.a;
>
> And we should just add something to elaborate it a bit.
> See the patch in attachment containing my proposal to improve v4-0001
> main SJE patch. I think it resolved the issue with EPQ assertion as well
> as problems with returning value.

I tried this.  I applied 0001 from [1] and 0002 from [2].  Then I
tried the concurrent test case [3].  It still fails with assert for
me.  But assert and related stuff is the least problem.  The big
problem, as described in [3], is semantical change in query.  When EPQ
is applied, we fetch the latest tuple of the target relation
regardless snapshot.  But for the self-joined relation we should still
use the snapshot-satisfying tuple.  I don't see even attempt to
address this in your patch.  And as I pointed before, this appears
quite complex.

Links.
1. 
https://www.postgresql.org/message-id/96250a42-20e3-40f0-9d45-f53ae852f8ed%40gmail.com
2. 
https://www.postgresql.org/message-id/5b49501c-9cb3-4c5d-9d56-49704ff08143%40gmail.com
3. 
https://www.postgresql.org/message-id/CAPpHfduM6X82ExT0r9UzFLJ12wOYPvRw5vT2Htq0gAPBgHhKeQ%40mail.gmail.com

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 7/11/24 14:43, jian he wrote:

On Tue, Jul 9, 2024 at 2:06 PM Andrei Lepikhov  wrote:


On 7/2/24 07:25, jian he wrote:

to make sure it's correct, I have added a lot of tests,
Some of this may be contrived, maybe some of the tests are redundant.

Thanks for your job!
I passed through the patches and have some notes:
1. Patch 0001 has not been applied anymore since the previous week's
changes in the core. Also, there is one place with trailing whitespace.


thanks.
because the previous thread mentioned the EPQ problem.
in remove_useless_self_joins, i make it can only process CMD_SELECT query.
I would like to oppose here: IMO, it is just a mishap which we made 
because of a long history of patch transformations. There we lost the 
case where RowMark exists for only one of candidate relations.
Also, after review I think we don't need so many new tests. Specifically 
for DML we already have one:


EXPLAIN (COSTS OFF)
UPDATE sj sq SET b = 1 FROM sj as sz WHERE sq.a = sz.a;

And we should just add something to elaborate it a bit.
See the patch in attachment containing my proposal to improve v4-0001 
main SJE patch. I think it resolved the issue with EPQ assertion as well 
as problems with returning value.


--
regards, Andrei Lepikhov
From c04add30999ecd64c51bde7db56a6e5637c16c74 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" 
Date: Tue, 9 Jul 2024 12:25:23 +0700
Subject: [PATCH] Apply SJE to DML queries: Just don't include result relation
 to the set of SJE candidates.

Also, fix the subtle bug with RowMarks.
---
 src/backend/optimizer/plan/analyzejoins.c | 24 +++--
 src/test/regress/expected/join.out| 61 +++
 src/test/regress/sql/join.sql | 17 ++-
 3 files changed, 84 insertions(+), 18 deletions(-)

diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index bb14597762..d2b9ba7c08 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -1860,10 +1860,6 @@ remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark,
 	/* restore the rangetblref in a proper order. */
 	restore_rangetblref((Node *) root->parse, toKeep->relid, toRemove->relid, 0, 0);
 
-	/* See remove_self_joins_one_group() */
-	Assert(root->parse->resultRelation != toRemove->relid);
-	Assert(root->parse->resultRelation != toKeep->relid);
-
 	/* Replace links in the planner info */
 	remove_rel_from_query(root, toRemove, toKeep->relid, NULL, NULL);
 
@@ -2046,14 +2042,6 @@ remove_self_joins_one_group(PlannerInfo *root, Relids relids)
 	{
 		RelOptInfo *inner = root->simple_rel_array[r];
 
-		/*
-		 * We don't accept result relation as either source or target relation
-		 * of SJE, because result relation has different behavior in
-		 * EvalPlanQual() and RETURNING clause.
-		 */
-		if (root->parse->resultRelation == r)
-			continue;
-
 		k = r;
 
 		while ((k = bms_next_member(relids, k)) > 0)
@@ -2069,9 +2057,6 @@ remove_self_joins_one_group(PlannerInfo *root, Relids relids)
 			PlanRowMark *imark = NULL;
 			List	   *uclauses = NIL;
 
-			if (root->parse->resultRelation == k)
-continue;
-
 			/* A sanity check: the relations have the same Oid. */
 			Assert(root->simple_rte_array[k]->relid ==
    root->simple_rte_array[r]->relid);
@@ -2121,7 +2106,8 @@ remove_self_joins_one_group(PlannerInfo *root, Relids relids)
 if (omark && imark)
 	break;
 			}
-			if (omark && imark && omark->markType != imark->markType)
+			if (((omark == NULL) ^ (imark == NULL)) ||
+(omark && omark->markType != imark->markType))
 continue;
 
 			/*
@@ -2231,7 +2217,8 @@ remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
 			 */
 			if (rte->rtekind == RTE_RELATION &&
 rte->relkind == RELKIND_RELATION &&
-rte->tablesample == NULL)
+rte->tablesample == NULL &&
+varno != root->parse->resultRelation)
 			{
 Assert(!bms_is_member(varno, relids));
 relids = bms_add_member(relids, varno);
@@ -2300,6 +2287,9 @@ remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
 
 relids = bms_del_members(relids, group);
 
+/* Don't apply SJE to result relation */
+Assert(!bms_is_member(root->parse->resultRelation, group));
+
 /*
  * Try to remove self-joins from a group of identical entries.
  * Make the next attempt iteratively - if something is deleted
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 4e4cec633a..78dfcd4866 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -7068,6 +7068,18 @@ UPDATE sj sq SET b = 1 FROM sj as sz WHERE sq.a = sz.a;
->  Seq Scan on sj sz
 (6 rows)
 
+EXPLAIN (COSTS OFF)
+UPDATE sj sq SET b = sz.b FROM sj as sz WHERE sq.a = sz.a;
+ QUERY PLAN  
+-
+ Update on sj sq
+   ->  Nested Loop
+ Join Filter: (sq.a =

Re: Removing unneeded self joins

[Alexander Korotkov]

On Thu, Jul 4, 2024 at 11:40 AM jian he  wrote:
> On Thu, Jul 4, 2024 at 11:04 AM Alexander Korotkov  
> wrote:
> >
> > On Thu, Jul 4, 2024 at 5:15 AM jian he  wrote:
> > > in remove_self_join_rel, i have
> > > ```ChangeVarNodes((Node *) root->parse, toRemove->relid, toKeep->relid, 
> > > 0);```
> > > which will change the joinlist(RangeTblRef)  from (1,2)  to (2,2).
> > > Immediately after this call, I wrote a function (restore_rangetblref)
> > > to restore the joinlist as original (1,2).
> > > then remove_rel_from_joinlist won't error out.
> > > see remove_self_join_rel, restore_rangetblref.
> >
> > Thank you, now this is clear.  Could we add additional parameters to
> > ChangeVarNodes() instead of adding a new function which reverts part
> > of changes.
> >
>
> I didn't dare to. we have 42 occurrences of ChangeVarNodes.
> adding a parameter to it only for one location seems not intuitive.
>
> Now I have tried.
> changing to
> `ChangeVarNodes(Node *node, int rt_index, int new_index, int
> sublevels_up, bool change_RangeTblRef)`
>
> /* Replace varno in all the query structures */
> ChangeVarNodes((Node *) root->parse, toRemove->relid, toKeep->relid, 0, 
> false);
> ```
>
> it seems to work, pass the regression test.
> ```ChangeVarNodes((Node *) root->parse, toRemove->relid,
> toKeep->relid, 0, false);```
> is in remove_self_join_rel, remove_self_joins_one_group,
> remove_self_joins_recurse.
> all other places are ```ChangeVarNodes((Node *) root->parse,
> toRemove->relid, toKeep->relid, 0, true);```
> so ChangeVarNodes add a parameter will only influence the SJE feature.

Good.  But I think it's not necessary to to replace function signature
in all the 42 occurrences.  This will make our patch unnecessarily
conflict with others.  Instead we can have two functions
ChangeVarNodes(original function signature) and
ChangeVarNodesExtended(extended function signature).  Then existing
occurrences can still use ChangeVarNodes(), which will be just
shortcut for ChangeVarNodesExtended().

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[jian he]

On Thu, Jul 4, 2024 at 11:04 AM Alexander Korotkov  wrote:
>
> On Thu, Jul 4, 2024 at 5:15 AM jian he  wrote:
> > in remove_self_join_rel, i have
> > ```ChangeVarNodes((Node *) root->parse, toRemove->relid, toKeep->relid, 
> > 0);```
> > which will change the joinlist(RangeTblRef)  from (1,2)  to (2,2).
> > Immediately after this call, I wrote a function (restore_rangetblref)
> > to restore the joinlist as original (1,2).
> > then remove_rel_from_joinlist won't error out.
> > see remove_self_join_rel, restore_rangetblref.
>
> Thank you, now this is clear.  Could we add additional parameters to
> ChangeVarNodes() instead of adding a new function which reverts part
> of changes.
>

I didn't dare to. we have 42 occurrences of ChangeVarNodes.
adding a parameter to it only for one location seems not intuitive.

Now I have tried.
changing to
`ChangeVarNodes(Node *node, int rt_index, int new_index, int
sublevels_up, bool change_RangeTblRef)`

/* Replace varno in all the query structures */
ChangeVarNodes((Node *) root->parse, toRemove->relid, toKeep->relid, 0, false);
```

it seems to work, pass the regression test.
```ChangeVarNodes((Node *) root->parse, toRemove->relid,
toKeep->relid, 0, false);```
is in remove_self_join_rel, remove_self_joins_one_group,
remove_self_joins_recurse.
all other places are ```ChangeVarNodes((Node *) root->parse,
toRemove->relid, toKeep->relid, 0, true);```
so ChangeVarNodes add a parameter will only influence the SJE feature.


I also tried, save to a temp list, but it did not work.
original_fromlist = list_copy_deep(root->parse->jointree->fromlist);
/* Replace varno in all the query structures */
ChangeVarNodes((Node *) root->parse, toRemove->relid, toKeep->relid, 0);
root->parse->jointree->fromlist = list_copy(original_fromlist);

Re: Removing unneeded self joins

[Alexander Korotkov]

On Thu, Jul 4, 2024 at 5:15 AM jian he  wrote:
> in remove_self_join_rel, i have
> ```ChangeVarNodes((Node *) root->parse, toRemove->relid, toKeep->relid, 0);```
> which will change the joinlist(RangeTblRef)  from (1,2)  to (2,2).
> Immediately after this call, I wrote a function (restore_rangetblref)
> to restore the joinlist as original (1,2).
> then remove_rel_from_joinlist won't error out.
> see remove_self_join_rel, restore_rangetblref.

Thank you, now this is clear.  Could we add additional parameters to
ChangeVarNodes() instead of adding a new function which reverts part
of changes.

> current mechanism, in this example context,
> SJE can translate ```update test set val = t.val + 1 from test t where
> test.id = t.id;``` as good as to
> ```update test set val = val + 1```.
> if we replace it that way, then this example would result val = 3.
>
> but without SJE,
> ```update test set val = t.val + 1 from test t where test.id = t.id;```
> will result val = 2.
>
> you mentioned the EPQ problem,  previously i don't know what that means.

Yes, I guessed so.  I should have come with more detailed explanation.

> now i see, I feel like it is quite challenging to resolve it.

Yep.  Glad to see we are on the same page.

This is why I think we could leave SJE for target relation of
modification queries for future.  I'd like to not devalue SELECT-only
SJE, given that this is a step forward anyway.

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[jian he]

On Wed, Jul 3, 2024 at 11:39 AM Alexander Korotkov  wrote:
>
> On Mon, Jun 17, 2024 at 3:00 AM jian he  wrote:
> > On Mon, May 6, 2024 at 11:55 PM Tom Lane  wrote:
> > >
> > > Robert Haas  writes:
> > > > I want to go on record right now as disagreeing with the plan proposed
> > > > in the commit message for the revert commit, namely, committing this
> > > > again early in the v18 cycle. I don't think Tom would have proposed
> > > > reverting this feature unless he believed that it had more serious
> > > > problems than could be easily fixed in a short period of time. I think
> > > > that concern is well-founded, given the number of fixes that were
> > > > committed. It seems likely that the patch needs significant rework and
> > > > stabilization before it gets committed again, and I think it shouldn't
> > > > be committed again without explicit agreement from Tom or one of the
> > > > other committers who have significant experience with the query
> > > > planner.
> > >
> > > FWIW I accept some of the blame here, for not having paid any
> > > attention to the SJE work earlier.  I had other things on my mind
> > > for most of last year, and not enough bandwidth to help.
> > >
> > > The main thing I'd like to understand before we try this again is
> > > why SJE needed so much new query-tree-manipulation infrastructure.
> > > I would have expected it to be very similar to the left-join
> > > elimination we do already, and therefore to mostly just share the
> > > existing infrastructure.  (I also harbor suspicions that some of
> > > the new code existed just because someone didn't research what
> > > was already there --- for instance, the now-removed replace_varno
> > > sure looks like ChangeVarNodes should have been used instead.)
> > >
> >
> > i have looked around the code.
> > about replace_varno and ChangeVarNodes:
> >
> > ChangeVarNodes
> > have
> > 
> > if (IsA(node, RangeTblRef))
> > {
> > RangeTblRef *rtr = (RangeTblRef *) node;
> >
> > if (context->sublevels_up == 0 &&
> > rtr->rtindex == context->rt_index)
> > rtr->rtindex = context->new_index;
> > /* the subquery itself is visited separately */
> > return false;
> > }
> > 
> > if ChangeVarNodes executed the above code in remove_useless_self_joins and
> > remove_self_joins_recurse. the joinlist(RangeTblRef) will change from (1,2)
> > to (2,2). then later, remove_rel_from_joinlist cannot remove the 1,
> > *nremoved will be zero.
> > then the below code error branch will be executed.
> > 
> > joinlist = remove_rel_from_joinlist(joinlist, relid, &nremoved);
> > if (nremoved != 1)
> > elog(ERROR, "failed to find relation %d in joinlist", relid);
> > ```
>
> Did you manage to overcome this problem in your patch?  If not, why do
> regression tests pass while this seems to affect pretty much every
> self-join removal?  If so, how did you do that?
>

in remove_self_join_rel, i have
```ChangeVarNodes((Node *) root->parse, toRemove->relid, toKeep->relid, 0);```
which will change the joinlist(RangeTblRef)  from (1,2)  to (2,2).
Immediately after this call, I wrote a function (restore_rangetblref)
to restore the joinlist as original (1,2).
then remove_rel_from_joinlist won't error out.
see remove_self_join_rel, restore_rangetblref.

Andrei Lepikhov:
+ /* Replace varno in all the query structures */
+ replace_varno((Node *) root->parse, toRemove->relid, toKeep->relid);
So Andrei Lepikhov's change didn't touch joinlist,
Query->resultRelation, Query->mergeTargetRelation.

Then in v3-0002 I tried to make SJE work with UPDATE, i thought it worked well,
because ChangeVarNodes also takes care of Query->resultRelation,
Query->mergeTargetRelation.
then later your EPQ demenonsate shows that's not enough.

so, in summary, in v3-0001, by changing all replace_varno to ChangeVarNodes
paves ways to make SJE apply to UPDATE/DELETE/MERGE.
It's just that we need to reverse some effects of ChangeVarNodes.
(restore_rangetblref)


> > > Another thing that made me pretty sad was 8c441c082 (Forbid SJE with
> > > result relation).  While I don't claim that that destroyed the entire
> > > use case for SJE, it certainly knocked its usefulness down by many
> > > notches, maybe even to the point where it's not worth putting in the
> > > effort needed to get it to re-committability.  So I think we need to
> > > look harder at finding a way around that.  Is the concern that
> > > RETURNING should return either old or new values depending on which
> > > RTE is mentioned?  If so, maybe the feature Dean has proposed to
> > > allow RETURNING to access old values [1] is a prerequisite to moving
> > > forward.  Alternatively, perhaps it'd be good enough to forbid SJE
> > > only when the non-target relation is actually mentioned in RETURNING.
> > >
>
> It appears you didn't try to address the EPQ problem, which seems to
> me even more serious than the RETURNING problem.
>
> See the following example.
>
> Session 1
> # create table test (id int primary key, val int);
> # insert into t

Re: Removing unneeded self joins

[Alexander Korotkov]

On Mon, Jun 17, 2024 at 3:00 AM jian he  wrote:
> On Mon, May 6, 2024 at 11:55 PM Tom Lane  wrote:
> >
> > Robert Haas  writes:
> > > I want to go on record right now as disagreeing with the plan proposed
> > > in the commit message for the revert commit, namely, committing this
> > > again early in the v18 cycle. I don't think Tom would have proposed
> > > reverting this feature unless he believed that it had more serious
> > > problems than could be easily fixed in a short period of time. I think
> > > that concern is well-founded, given the number of fixes that were
> > > committed. It seems likely that the patch needs significant rework and
> > > stabilization before it gets committed again, and I think it shouldn't
> > > be committed again without explicit agreement from Tom or one of the
> > > other committers who have significant experience with the query
> > > planner.
> >
> > FWIW I accept some of the blame here, for not having paid any
> > attention to the SJE work earlier.  I had other things on my mind
> > for most of last year, and not enough bandwidth to help.
> >
> > The main thing I'd like to understand before we try this again is
> > why SJE needed so much new query-tree-manipulation infrastructure.
> > I would have expected it to be very similar to the left-join
> > elimination we do already, and therefore to mostly just share the
> > existing infrastructure.  (I also harbor suspicions that some of
> > the new code existed just because someone didn't research what
> > was already there --- for instance, the now-removed replace_varno
> > sure looks like ChangeVarNodes should have been used instead.)
> >
>
> i have looked around the code.
> about replace_varno and ChangeVarNodes:
>
> ChangeVarNodes
> have
> 
> if (IsA(node, RangeTblRef))
> {
> RangeTblRef *rtr = (RangeTblRef *) node;
>
> if (context->sublevels_up == 0 &&
> rtr->rtindex == context->rt_index)
> rtr->rtindex = context->new_index;
> /* the subquery itself is visited separately */
> return false;
> }
> 
> if ChangeVarNodes executed the above code in remove_useless_self_joins and
> remove_self_joins_recurse. the joinlist(RangeTblRef) will change from (1,2)
> to (2,2). then later, remove_rel_from_joinlist cannot remove the 1,
> *nremoved will be zero.
> then the below code error branch will be executed.
> 
> joinlist = remove_rel_from_joinlist(joinlist, relid, &nremoved);
> if (nremoved != 1)
> elog(ERROR, "failed to find relation %d in joinlist", relid);
> ```

Did you manage to overcome this problem in your patch?  If not, why do
regression tests pass while this seems to affect pretty much every
self-join removal?  If so, how did you do that?

>
> -
> replace_varno and replace_varno_walker didn't replace
> Query->resultRelation, Query->mergeTargetRelation
> as ChangeVarNodes did.
>
> then replace_varno will have problems with DELETE, UPDATE, MERGE
> someway.
> ChangeVarNodes solved this problem.
>
>
> > Another thing that made me pretty sad was 8c441c082 (Forbid SJE with
> > result relation).  While I don't claim that that destroyed the entire
> > use case for SJE, it certainly knocked its usefulness down by many
> > notches, maybe even to the point where it's not worth putting in the
> > effort needed to get it to re-committability.  So I think we need to
> > look harder at finding a way around that.  Is the concern that
> > RETURNING should return either old or new values depending on which
> > RTE is mentioned?  If so, maybe the feature Dean has proposed to
> > allow RETURNING to access old values [1] is a prerequisite to moving
> > forward.  Alternatively, perhaps it'd be good enough to forbid SJE
> > only when the non-target relation is actually mentioned in RETURNING.
> >
> > regards, tom lane
> >
> > [1] 
> > https://www.postgresql.org/message-id/flat/CAEZATCWx0J0-v=Qjc6gXzR=KtsdvAE7Ow=D=mu50agoe+pv...@mail.gmail.com
>
> if only SELECT, no worth to make it being committed,
> do you think support DML but no support RETURNING worth the effort?

It appears you didn't try to address the EPQ problem, which seems to
me even more serious than the RETURNING problem.

See the following example.

Session 1
# create table test (id int primary key, val int);
# insert into test values (1,1);
# begin;
# update test set val = val + 1 where id = 1;

Session 2
# update test set val = t.val + 1 from test t where test.id = t.id;
(wait)

Session 1
# commit;

With v3 patch the query of session 2 fails on assert even before
starting to wait for the tuple lock.  But even if we fix that, I
expect that after SJE this example would result in val = 3.  Without
SJE, it would result with val = 2, because during EPQ alias t still
references the row version read according to the snapshot.  In order
to overcome that we need to distinguish Var, which points to the
latest version during EPQ, and Var, which points to the snapshot
version during EPQ.  Pro

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi!

On Thu, Jun 13, 2024 at 6:45 AM Andrei Lepikhov
 wrote:
> On 5/7/24 02:59, Robert Haas wrote:
> > On Mon, May 6, 2024 at 3:27 PM Alexander Korotkov  
> > wrote:
> >> I agree it was a hurry to put the plan into commit message.  I think
> >> Tom already gave valuable feedback [1] and probably we will get more.
> >> So, plan is to be decided.  One way or the other I'm not going to
> >> re-commit this without explicit Tom's consent.
> >
> > Thanks. I hope we find a way to make it happen.
> >
> Rebased onto current master. Nothing new except rebase-related changes
> and some comment fixes.

Thank you.  I've registered the patch on commitfest.

Do you plan to address the feedback from Tom Lane?

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[Robert Haas]

On Mon, May 6, 2024 at 3:27 PM Alexander Korotkov  wrote:
> I agree it was a hurry to put the plan into commit message.  I think
> Tom already gave valuable feedback [1] and probably we will get more.
> So, plan is to be decided.  One way or the other I'm not going to
> re-commit this without explicit Tom's consent.

Thanks. I hope we find a way to make it happen.

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

Re: Removing unneeded self joins

[Alexander Korotkov]

On Mon, May 6, 2024 at 5:44 PM Robert Haas  wrote:
> I want to go on record right now as disagreeing with the plan proposed
> in the commit message for the revert commit, namely, committing this
> again early in the v18 cycle. I don't think Tom would have proposed
> reverting this feature unless he believed that it had more serious
> problems than could be easily fixed in a short period of time. I think
> that concern is well-founded, given the number of fixes that were
> committed. It seems likely that the patch needs significant rework and
> stabilization before it gets committed again, and I think it shouldn't
> be committed again without explicit agreement from Tom or one of the
> other committers who have significant experience with the query
> planner. That is not to say that I don't approve generally of the idea
> of committing things earlier in the release cycle: I certainly do. It
> gives us more time to shake out problems with patches before we ship.
> But it only makes sense if we collectively believe that the patch is
> mostly correct, and only needs fine-tuning, and I think there are good
> reasons to believe that we shouldn't have that level of confidence in
> this case.

I agree it was a hurry to put the plan into commit message.  I think
Tom already gave valuable feedback [1] and probably we will get more.
So, plan is to be decided.  One way or the other I'm not going to
re-commit this without explicit Tom's consent.

Links.
1. https://www.postgresql.org/message-id/3622801.1715010885%40sss.pgh.pa.us

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[Alexander Korotkov]

On Mon, May 6, 2024 at 6:54 PM Tom Lane  wrote:
> Robert Haas  writes:
> > I want to go on record right now as disagreeing with the plan proposed
> > in the commit message for the revert commit, namely, committing this
> > again early in the v18 cycle. I don't think Tom would have proposed
> > reverting this feature unless he believed that it had more serious
> > problems than could be easily fixed in a short period of time. I think
> > that concern is well-founded, given the number of fixes that were
> > committed. It seems likely that the patch needs significant rework and
> > stabilization before it gets committed again, and I think it shouldn't
> > be committed again without explicit agreement from Tom or one of the
> > other committers who have significant experience with the query
> > planner.
>
> FWIW I accept some of the blame here, for not having paid any
> attention to the SJE work earlier.  I had other things on my mind
> for most of last year, and not enough bandwidth to help.
>
> The main thing I'd like to understand before we try this again is
> why SJE needed so much new query-tree-manipulation infrastructure.
> I would have expected it to be very similar to the left-join
> elimination we do already, and therefore to mostly just share the
> existing infrastructure.  (I also harbor suspicions that some of
> the new code existed just because someone didn't research what
> was already there --- for instance, the now-removed replace_varno
> sure looks like ChangeVarNodes should have been used instead.)

Thank you for pointing this.  This area certainly requires more investigation.

> Another thing that made me pretty sad was 8c441c082 (Forbid SJE with
> result relation).  While I don't claim that that destroyed the entire
> use case for SJE, it certainly knocked its usefulness down by many
> notches, maybe even to the point where it's not worth putting in the
> effort needed to get it to re-committability.  So I think we need to
> look harder at finding a way around that.  Is the concern that
> RETURNING should return either old or new values depending on which
> RTE is mentioned?  If so, maybe the feature Dean has proposed to
> allow RETURNING to access old values [1] is a prerequisite to moving
> forward.  Alternatively, perhaps it'd be good enough to forbid SJE
> only when the non-target relation is actually mentioned in RETURNING.

Another problem is EPQ.  During EPQ, we use most recent tuples for the
target relation and snapshot-satisfying tuples for joined relations.
And that affects RETURNING as well.  If we need to return values for
joined relation, that wouldn't be old values, but values of
snapshot-satisfying tuple which might be even older.

Proper support of this looks like quite amount of work for me.
Committing SJE to v18 with this looks challenging.  AFICS, going this
way would require substantial help from you.

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[Bruce Momjian]

On Mon, May  6, 2024 at 12:24:41PM -0400, Robert Haas wrote:
> Now that being said, I do also agree that the planner code is quite
> hard to understand, for various reasons. I don't think the structure
> of that code and the assumptions underlying it are as well-documented
> as they could be, and neither do I think that all of them are optimal.
> It has taken me a long time to learn as much as I know, and there is
> still quite a lot that I don't know. And I also agree that the planner
> does an unfortunate amount of in-place modification of existing
> structures without a lot of clarity about how it all works, and an
> unfortunate amount of data copying in some places, and even that the
> partition-wise join code isn't all that it could be. But I do not
> think that adds up to a conclusion that we should just be less
> ambitious with planner changes. Indeed, I would like to see us do
> more. There is certainly a lot of useful work that could be done. The
> trick is figuring out how to do it without breaking too many things,
> and that is not easy.

I agree with Robert.  While writting the Postgres 17 release notes, I am
excited to see the many optimizer improvements, and removing self-joins
from that list will be unfortunate.

I did write a blog entry in 2021 that suggested we could have
optimizer aggressiveness control to allow for more expensive
optimizations:

https://momjian.us/main/blogs/pgblog/2021.html#May_14_2021

-- 
  Bruce Momjian  https://momjian.us
  EDB  https://enterprisedb.com

  Only you can decide what is important to you.

Re: Removing unneeded self joins

[Robert Haas]

On Mon, May 6, 2024 at 12:01 PM Andrei Lepikhov
 wrote:
> Right now, it evolves extensively - new structures, variables,
> alternative copies of the same node trees with slightly changed
> properties ... This way allows us to quickly introduce some planning
> features (a lot of changes in planner logic since PG16 is evidence of
> that) and with still growing computing resources it allows postgres to
> fit RAM and proper planning time. But maybe we want to be more modest?
> The Ashutosh's work he has been doing this year shows how sometimes
> expensive the planner is. Perhaps we want machinery that will check the
> integrity of planning data except the setrefs, which fail to detect that
> occasionally?
> If an extensive approach is the only viable option, then it's clear that
> this and many other features are simply not suitable for Postgres
> Planner. It's disheartening that this patch didn't elicit such
> high-level feedback.

Well, as I said before, I think self-join elimination is a good
feature, and I believe that it belongs in PostgreSQL. However, I don't
believe that this implementation was done as well as it needed to be
done. A great deal of the work involved in a feature like this lies in
figuring out at what stage of processing certain kinds of
transformations ought to be done, and what cleanup is needed
afterward. It is difficult for anyone to get that completely right the
first time around; left join elimination also provoked a series of
after-the-fact bug fixes. However, I think those were fewer in number
and spread over a longer period of time.

Now that being said, I do also agree that the planner code is quite
hard to understand, for various reasons. I don't think the structure
of that code and the assumptions underlying it are as well-documented
as they could be, and neither do I think that all of them are optimal.
It has taken me a long time to learn as much as I know, and there is
still quite a lot that I don't know. And I also agree that the planner
does an unfortunate amount of in-place modification of existing
structures without a lot of clarity about how it all works, and an
unfortunate amount of data copying in some places, and even that the
partition-wise join code isn't all that it could be. But I do not
think that adds up to a conclusion that we should just be less
ambitious with planner changes. Indeed, I would like to see us do
more. There is certainly a lot of useful work that could be done. The
trick is figuring out how to do it without breaking too many things,
and that is not easy.

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

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 6/5/2024 21:44, Robert Haas wrote:

On Sat, May 4, 2024 at 10:46 PM Andrei Lepikhov
 wrote:

Having no objective negative feedback, we have no reason to change
anything in the design or any part of the code. It looks regrettable and
unusual.


To me, this sounds like you think it's someone else's job to tell you
what is wrong with the patch, or how to fix it, and if they don't,
then you should get to have the patch as part of PostgreSQL. But that
is not how we do things, nor should we. I agree that it sucks when you
need feedback and don't get it, and I've written about that elsewhere
and recently. But if you don't get feedback and as a result you can't
get the patch to an acceptable level, 

I'm really sorry that the level of my language caused a misunderstanding.
The main purpose of this work is to form a more or less certain view of 
the direction of the planner's development.
Right now, it evolves extensively - new structures, variables, 
alternative copies of the same node trees with slightly changed 
properties ... This way allows us to quickly introduce some planning 
features (a lot of changes in planner logic since PG16 is evidence of 
that) and with still growing computing resources it allows postgres to 
fit RAM and proper planning time. But maybe we want to be more modest? 
The Ashutosh's work he has been doing this year shows how sometimes 
expensive the planner is. Perhaps we want machinery that will check the 
integrity of planning data except the setrefs, which fail to detect that 
occasionally?
If an extensive approach is the only viable option, then it's clear that 
this and many other features are simply not suitable for Postgres 
Planner. It's disheartening that this patch didn't elicit such 
high-level feedback.


--
regards,
Andrei Lepikhov

Re: Removing unneeded self joins

[Tom Lane]

Robert Haas  writes:
> I want to go on record right now as disagreeing with the plan proposed
> in the commit message for the revert commit, namely, committing this
> again early in the v18 cycle. I don't think Tom would have proposed
> reverting this feature unless he believed that it had more serious
> problems than could be easily fixed in a short period of time. I think
> that concern is well-founded, given the number of fixes that were
> committed. It seems likely that the patch needs significant rework and
> stabilization before it gets committed again, and I think it shouldn't
> be committed again without explicit agreement from Tom or one of the
> other committers who have significant experience with the query
> planner.

FWIW I accept some of the blame here, for not having paid any
attention to the SJE work earlier.  I had other things on my mind
for most of last year, and not enough bandwidth to help.

The main thing I'd like to understand before we try this again is
why SJE needed so much new query-tree-manipulation infrastructure.
I would have expected it to be very similar to the left-join
elimination we do already, and therefore to mostly just share the
existing infrastructure.  (I also harbor suspicions that some of
the new code existed just because someone didn't research what
was already there --- for instance, the now-removed replace_varno
sure looks like ChangeVarNodes should have been used instead.)

Another thing that made me pretty sad was 8c441c082 (Forbid SJE with
result relation).  While I don't claim that that destroyed the entire
use case for SJE, it certainly knocked its usefulness down by many
notches, maybe even to the point where it's not worth putting in the
effort needed to get it to re-committability.  So I think we need to
look harder at finding a way around that.  Is the concern that
RETURNING should return either old or new values depending on which
RTE is mentioned?  If so, maybe the feature Dean has proposed to
allow RETURNING to access old values [1] is a prerequisite to moving
forward.  Alternatively, perhaps it'd be good enough to forbid SJE
only when the non-target relation is actually mentioned in RETURNING.

regards, tom lane

[1] 
https://www.postgresql.org/message-id/flat/CAEZATCWx0J0-v=Qjc6gXzR=KtsdvAE7Ow=D=mu50agoe+pv...@mail.gmail.com

Re: Removing unneeded self joins

[Bruce Momjian]

On Mon, May  6, 2024 at 10:44:33AM -0400, Robert Haas wrote:
> I want to go on record right now as disagreeing with the plan proposed
> in the commit message for the revert commit, namely, committing this
> again early in the v18 cycle. I don't think Tom would have proposed
> reverting this feature unless he believed that it had more serious
> problems than could be easily fixed in a short period of time. I think
> that concern is well-founded, given the number of fixes that were
> committed. It seems likely that the patch needs significant rework and
> stabilization before it gets committed again, and I think it shouldn't
> be committed again without explicit agreement from Tom or one of the
> other committers who have significant experience with the query
> planner. That is not to say that I don't approve generally of the idea
> of committing things earlier in the release cycle: I certainly do. It
> gives us more time to shake out problems with patches before we ship.
> But it only makes sense if we collectively believe that the patch is
> mostly correct, and only needs fine-tuning, and I think there are good
> reasons to believe that we shouldn't have that level of confidence in
> this case.

I think what Robert is saying is that it is an unacceptable plan to just
dump the code into PG 18 and clean it up in the following months --- it
needs more research before it is re-added to git.

-- 
  Bruce Momjian  https://momjian.us
  EDB  https://enterprisedb.com

  Only you can decide what is important to you.

Re: Removing unneeded self joins

[Robert Haas]

On Sat, May 4, 2024 at 10:46 PM Andrei Lepikhov
 wrote:
> Having no objective negative feedback, we have no reason to change
> anything in the design or any part of the code. It looks regrettable and
> unusual.

To me, this sounds like you think it's someone else's job to tell you
what is wrong with the patch, or how to fix it, and if they don't,
then you should get to have the patch as part of PostgreSQL. But that
is not how we do things, nor should we. I agree that it sucks when you
need feedback and don't get it, and I've written about that elsewhere
and recently. But if you don't get feedback and as a result you can't
get the patch to an acceptable level, or if you do get feedback but
the patch fails to reach an acceptable level anyway, then the only
correct decision is for us to not ship that code. That obviously sucks
from the point of view of the patch author, and also of the committer,
but consider the alternative. Once patches get through an initial
release and become part of the product, the responsibility for fixing
problems is understood to slowly move from the original committer to
the community as a whole. In practice, that means that a lot of the
work of fixing things that are broken, after some initial period, ends
up falling on committers other than the person who did the initial
commit. Even one or two problematic commits can generate an enormous
amount of work for people who weren't involved in the original
development and may not even have agreed with the development
direction, and it is more than fair for those people to express a view
about whether they are willing to carry that burden or not. When they
aren't, I do think that's regrettable, but I don't think it's unusual.
Just in this release, we've removed at least two previously-released
features because they're in bad shape and nobody's willing to maintain
them (snapshot too old, AIX support).

> After designing the feature, fixing its bugs, and reviewing joint
> patches on the commitfest, the question more likely lies in the planner
> design. For example, I wonder if anyone here knows why exactly the
> optimiser makes a copy of the whole query subtree in some places.
> Another example is PlannerInfo. Can we really control all the
> consequences of introducing, let's say, a new JoinDomain entity?

Bluntly, if you can't control those consequences, then you aren't
allowed to make that change.

I know first-hand how difficult some of these problems are. Sometime
in the last year or three, I spent weeks getting rid of ONE global
variable (ThisTimeLineID). It took an absolutely inordinate amount of
time, and it became clear to me that I was never going to get rid of
enough global variables in that part of the code to be able to write a
patch for the feature I wanted without risk of unforeseen
consequences. So I gave up on the entire feature. Maybe I'll try again
at some point, or maybe somebody else will feel like cleaning up that
code and then I can try again with a cleaner base, but what I don't
get to do is write a buggy patch for the feature I want and commit it
anyway. I either figure out a way to do it that I believe is low-risk
and that the community judges to be acceptable, or I don't do it.

I want to go on record right now as disagreeing with the plan proposed
in the commit message for the revert commit, namely, committing this
again early in the v18 cycle. I don't think Tom would have proposed
reverting this feature unless he believed that it had more serious
problems than could be easily fixed in a short period of time. I think
that concern is well-founded, given the number of fixes that were
committed. It seems likely that the patch needs significant rework and
stabilization before it gets committed again, and I think it shouldn't
be committed again without explicit agreement from Tom or one of the
other committers who have significant experience with the query
planner. That is not to say that I don't approve generally of the idea
of committing things earlier in the release cycle: I certainly do. It
gives us more time to shake out problems with patches before we ship.
But it only makes sense if we collectively believe that the patch is
mostly correct, and only needs fine-tuning, and I think there are good
reasons to believe that we shouldn't have that level of confidence in
this case.

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

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 3/5/2024 20:55, Robert Haas wrote:

One of my most embarrassing gaffes in this area personally was
a448e49bcbe40fb72e1ed85af910dd216d45bad8. I don't know how I managed
to commit the original patch without realizing it was going to cause
an increase in the WAL size, but I can tell you that when I realized
it, my heart sank through the floor.

I discovered this feature and agree that it looks like a severe problem.
Unfortunately, in the case of the SJE patch, the committer and reviewers 
don't provide negative feedback. We see the only (I'm not sure I use the 
proper English phrase) 'negative feelings' from people who haven't 
reviewed or analysed it at all (at least, they didn't mention it).


Considering the situation, I suggest setting the default value of 
enable_self_join_removal to false in PG17 for added safety and then 
changing it to true in early PG18.


Having no objective negative feedback, we have no reason to change 
anything in the design or any part of the code. It looks regrettable and 
unusual.


After designing the feature, fixing its bugs, and reviewing joint 
patches on the commitfest, the question more likely lies in the planner 
design. For example, I wonder if anyone here knows why exactly the 
optimiser makes a copy of the whole query subtree in some places. 
Another example is PlannerInfo. Can we really control all the 
consequences of introducing, let's say, a new JoinDomain entity?


You also mentioned 2024.pgconf.dev. Considering the current migration 
policy in some countries, it would be better to work through the online 
presence as equivalent to offline. Without an online part of the 
conference, the only way to communicate and discuss is through this 
mailing list.


--
regards,
Andrei Lepikhov

Re: Removing unneeded self joins

[Robert Haas]

On Fri, May 3, 2024 at 4:57 AM Alexander Korotkov  wrote:
> I agree to revert it for v17, but I'm not exactly sure the issue is
> design (nevertheless design review is very welcome as any other type
> of review).  The experience of the bugs arising with the SJE doesn't
> show me a particular weak spot in the feature.  It looks more like
> this patch has to revise awfully a lot planner data structures to
> replace one relid with another.  And I don't see the design, which
> could avoid that.  Somewhere in the thread I have proposed a concept
> of "alias relids".  However, I suspect that could leave us with more
> lurking bugs instead of the bug-free code.

I agree that reverting it for v17 makes sense. In terms of moving
forward, whether a design review is exactly the right idea or not, I'm
not sure. However, I think that the need to replace relids in a lot of
places is something that a design review might potentially flag as a
problem. Maybe there is some other approach that can avoid the need
for this.

On the other hand, maybe there's not. But in that case, the question
becomes how the patch author(s), and committer, are going to make sure
that most of the issues get flushed out before the initial commit.
What we can't do is say - we know that we need to replace relids in a
bunch of places, so we'll change the ones we know about, and then rely
on testing to find any that we missed. There has to be some kind of
systematic plan that everyone can agree should find all of the
affected places, and then if a few slip through, that's fine, that's
how life goes.

I haven't followed the self-join elimination work very closely, and I
do quite like the idea of the feature. However, looking over all the
follow-up commits, it's pretty hard to escape the conclusion that
there were a lot of cases that weren't adequately considered in the
initial work (lateral, result relations, PHVs, etc.). And that is a
big problem -- it really creates a lot of issues for the project when
a major feature commit misses whole areas that it needs to have
considered, as plenty of previous history will show. When anybody
starts to realize that they've not just had a few goofs but have
missed some whole affected area entirely, it's time to start thinking
about a revert.

One of my most embarrassing gaffes in this area personally was
a448e49bcbe40fb72e1ed85af910dd216d45bad8. I don't know how I managed
to commit the original patch without realizing it was going to cause
an increase in the WAL size, but I can tell you that when I realized
it, my heart sank through the floor. I'd love to return to that work
if we can all ever agree on a way of addressing that problem, but in
the meantime, that patch is very dead. And ... if somebody had taken
the time to give me a really good design review of that patch, they
might well have noticed, and saved me the embarrassment of committing
something that had no shot of remaining in the tree. Unfortunately,
one of the downsides of being a committer is that you tend to get less
of that sort of review, because people assume you know what you're
doing. Which is fabulous, when you actually do know what you're doing,
and really sucks, when you don't. One of the things I'd like to see
discussed at 2024.pgconf.dev is how we can improve this aspect of how
we work together.

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

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi, Tom!

On Fri, May 3, 2024 at 2:19 AM Tom Lane  wrote:
> Alexander Korotkov  writes:
> > I would appreciate your review of this patchset, and review from Andrei as 
> > well.
>
> I hate to say this ... but if we're still finding bugs this
> basic in SJE, isn't it time to give up on it for v17?
>
> I might feel better about it if there were any reason to think
> these were the last major bugs.  But you have already committed
> around twenty separate fixes for the original SJE patch, and
> now here you come with several more; so it doesn't seem like
> the defect rate has slowed materially.  There can be no doubt
> whatever that the original patch was far from commit-ready.

I think if we subtract from the SJE followup commits containing
improvements (extra comments, asserts) and fix for in-place Bitmapset
modification, which was there before, the number of fixes will be
closer to ten.  And the number of pending fixes will be two.  But I
totally get your concern that we're quite late in the release cycle
and new SJE-related issues continue to arise.  This leads to a
significant risk of raising many bugs for end users.

> I think we should revert SJE for v17 and do a thorough design
> review before trying again in v18.

I agree to revert it for v17, but I'm not exactly sure the issue is
design (nevertheless design review is very welcome as any other type
of review).  The experience of the bugs arising with the SJE doesn't
show me a particular weak spot in the feature.  It looks more like
this patch has to revise awfully a lot planner data structures to
replace one relid with another.  And I don't see the design, which
could avoid that.  Somewhere in the thread I have proposed a concept
of "alias relids".  However, I suspect that could leave us with more
lurking bugs instead of the bug-free code.

I suggest we should give this feature more review and testing, then
commit early v18.  That would leave us enough time to fix any other
issues before v18 release.

--
Regards,
Alexander Korotkov
Supabase

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 5/3/24 06:19, Tom Lane wrote:

Alexander Korotkov  writes:

I would appreciate your review of this patchset, and review from Andrei as well.


I hate to say this ... but if we're still finding bugs this
basic in SJE, isn't it time to give up on it for v17?

I might feel better about it if there were any reason to think
these were the last major bugs.  But you have already committed
around twenty separate fixes for the original SJE patch, and
now here you come with several more; so it doesn't seem like
the defect rate has slowed materially.  There can be no doubt
whatever that the original patch was far from commit-ready.

I think we should revert SJE for v17 and do a thorough design
review before trying again in v18.

I need to say I don't see any evidence of bad design.
I think this feature follows the example of 2489d76 [1], 1349d27 [2], 
and partitionwise join features — we get some issues from time to time, 
but these strengths and frequencies are significantly reduced.
First and foremost, this feature is highly isolated: like the PWJ 
feature, you can just disable (not enable?) SJE and it guarantees you 
will avoid the problems.
Secondly, this feature reflects the design decisions the optimiser has 
made before. It raises some questions: Do we really control the 
consistency of our paths and the plan tree? Maybe we hide our 
misunderstanding of its logic by extensively copying expression trees, 
sometimes without fundamental necessity. Perhaps the optimiser needs 
some abstraction layers or reconstruction to reduce the quickly growing 
complexity.
A good example here is [1]. IMO, the new promising feature it has 
introduced isn't worth the complexity it added to the planner.
SJE, much like OR <-> ANY transformation, introduces a fresh perspective 
into the planner: if we encounter a complex, redundant query, it may be 
more beneficial to invest in simplifying the internal query 
representation rather than adding new optimisations that will grapple 
with this complexity.
Also, SJE raised questions I've never seen before, like: Could we 
control the consistency of the PlannerInfo by changing something in the 
logic?
Considering the current state, I don't see any concrete outcomes or 
evidence that a redesign of the feature will lead us to a new path. 
However, I believe the presence of SJE in the core could potentially 
trigger improvements in the planner. As a result, I vote to stay with 
the feature. But remember, as an author, I'm not entirely objective, so 
let's wait for alternative opinions.


[1] Make Vars be outer-join-aware
[2] Improve performance of ORDER BY / DISTINCT aggregates

--
regards,
Andrei Lepikhov
Postgres Professional

Re: Removing unneeded self joins

[Tom Lane]

Alexander Korotkov  writes:
> I would appreciate your review of this patchset, and review from Andrei as 
> well.

I hate to say this ... but if we're still finding bugs this
basic in SJE, isn't it time to give up on it for v17?

I might feel better about it if there were any reason to think
these were the last major bugs.  But you have already committed
around twenty separate fixes for the original SJE patch, and
now here you come with several more; so it doesn't seem like
the defect rate has slowed materially.  There can be no doubt
whatever that the original patch was far from commit-ready.

I think we should revert SJE for v17 and do a thorough design
review before trying again in v18.

regards, tom lane

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi, Richard!

On Thu, May 2, 2024 at 4:14 PM Richard Guo  wrote:
> On Thu, May 2, 2024 at 6:08 PM Alexander Korotkov  
> wrote:
>> On Thu, May 2, 2024 at 12:45 PM Andrei Lepikhov
>>  wrote:
>> > One question for me is: Do we anticipate other lateral self-references
>> > except the TABLESAMPLE case? Looking into the extract_lateral_references
>> > implementation, I see the only RTE_SUBQUERY case to be afraid of. But we
>> > pull up subqueries before extracting lateral references. So, if we have
>> > a reference to a subquery, it means we will not flatten this subquery
>> > and don't execute SJE. Do we need more code, as you have written in the
>> > first patch?
>>
>> I think my first patch was crap anyway.  Your explanation seems
>> reasonable to me.  I'm not sure this requires any more code.  Probably
>> it would be enough to add more comments about this.
>
>
> The tablesample case is not the only factor that can cause a relation to
> have a lateral dependency on itself after self-join removal.  It can
> also happen with PHVs.  As an example, consider
>
> explain (costs off)
> select * from t t1
> left join lateral
>   (select t1.a as t1a, * from t t2) t2
> on true
> where t1.a = t2.a;
> server closed the connection unexpectedly
>
> This is because after self-join removal, a PlaceHolderInfo's ph_lateral
> might contain rels mentioned in ph_eval_at, which we should get rid of.
>
> For the tablesample case, I agree that we should not consider relations
> with TABLESAMPLE clauses as candidates to be removed.  Removing such a
> relation could potentially change the syntax of the query, as shown by
> Alexander's example.  It seems to me that we can just check that in
> remove_self_joins_recurse, while we're collecting the base relations
> that are considered to be candidates for removal.
>
> This leads to the attached patch.  This patch also includes some code
> refactoring for the surrounding code.

Great, thank you for your work on this!

I'd like to split this into separate patches for better granularity of
git history.  I also added 0001 patch, which makes first usage of the
SJE acronym in file to come with disambiguation.  Also, I've added
assert that ph_lateral and ph_eval_at didn't overlap before the
changes.  I think this should help from the potential situation when
the changes we do could mask another bug.

I would appreciate your review of this patchset, and review from Andrei as well.

--
Regards,
Alexander Korotkov
Supabase


v2-0002-Minor-refactoring-for-self-join-elimination-code.patch
Description: Binary data


v2-0003-Forbid-self-join-elimination-on-table-sampling-sc.patch
Description: Binary data


v2-0004-Fix-self-join-elimination-work-with-PlaceHolderIn.patch
Description: Binary data


v2-0001-Clarify-the-SJE-self-join-elimination-acronym.patch
Description: Binary data

Re: Removing unneeded self joins

[Richard Guo]

On Thu, May 2, 2024 at 6:08 PM Alexander Korotkov 
wrote:

> On Thu, May 2, 2024 at 12:45 PM Andrei Lepikhov
>  wrote:
> > One question for me is: Do we anticipate other lateral self-references
> > except the TABLESAMPLE case? Looking into the extract_lateral_references
> > implementation, I see the only RTE_SUBQUERY case to be afraid of. But we
> > pull up subqueries before extracting lateral references. So, if we have
> > a reference to a subquery, it means we will not flatten this subquery
> > and don't execute SJE. Do we need more code, as you have written in the
> > first patch?
>
> I think my first patch was crap anyway.  Your explanation seems
> reasonable to me.  I'm not sure this requires any more code.  Probably
> it would be enough to add more comments about this.


The tablesample case is not the only factor that can cause a relation to
have a lateral dependency on itself after self-join removal.  It can
also happen with PHVs.  As an example, consider

explain (costs off)
select * from t t1
left join lateral
  (select t1.a as t1a, * from t t2) t2
on true
where t1.a = t2.a;
server closed the connection unexpectedly

This is because after self-join removal, a PlaceHolderInfo's ph_lateral
might contain rels mentioned in ph_eval_at, which we should get rid of.

For the tablesample case, I agree that we should not consider relations
with TABLESAMPLE clauses as candidates to be removed.  Removing such a
relation could potentially change the syntax of the query, as shown by
Alexander's example.  It seems to me that we can just check that in
remove_self_joins_recurse, while we're collecting the base relations
that are considered to be candidates for removal.

This leads to the attached patch.  This patch also includes some code
refactoring for the surrounding code.

Thanks
Richard


v1-0001-Fix-bogus-lateral-dependency-after-self-join-removal.patch
Description: Binary data

Re: Removing unneeded self joins

[Alexander Korotkov]

On Thu, May 2, 2024 at 12:45 PM Andrei Lepikhov
 wrote:
>
> On 5/1/24 18:59, Alexander Korotkov wrote:
> > I think we probably could forbid SJE for the tables with TABLESAMPLE
> > altogether.  Please, check the attached patch.
> Your patch looks good to me. I added some comments and test case into
> the join.sql.

Thank you

> One question for me is: Do we anticipate other lateral self-references
> except the TABLESAMPLE case? Looking into the extract_lateral_references
> implementation, I see the only RTE_SUBQUERY case to be afraid of. But we
> pull up subqueries before extracting lateral references. So, if we have
> a reference to a subquery, it means we will not flatten this subquery
> and don't execute SJE. Do we need more code, as you have written in the
> first patch?

I think my first patch was crap anyway.  Your explanation seems
reasonable to me.  I'm not sure this requires any more code.  Probably
it would be enough to add more comments about this.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 5/1/24 18:59, Alexander Korotkov wrote:

I think we probably could forbid SJE for the tables with TABLESAMPLE
altogether.  Please, check the attached patch.
Your patch looks good to me. I added some comments and test case into 
the join.sql.


One question for me is: Do we anticipate other lateral self-references 
except the TABLESAMPLE case? Looking into the extract_lateral_references 
implementation, I see the only RTE_SUBQUERY case to be afraid of. But we 
pull up subqueries before extracting lateral references. So, if we have 
a reference to a subquery, it means we will not flatten this subquery 
and don't execute SJE. Do we need more code, as you have written in the 
first patch?


--
regards,
Andrei Lepikhov
Postgres Professional
From dac8afd2095586921dfcf5564e7f2979e89b77de Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" 
Date: Thu, 2 May 2024 16:17:52 +0700
Subject: [PATCH] Forbid self-join elimination on table sampling scans.

Having custom table sampling methods we can stuck into unpredictable issues
replacing join with scan operation. It may had sense to analyse possible
situations and enable SJE, but the real profit from this operation looks
too low.
---
 src/backend/optimizer/plan/analyzejoins.c |  8 
 src/backend/optimizer/plan/initsplan.c|  5 -
 src/test/regress/expected/join.out| 13 +
 src/test/regress/sql/join.sql |  5 +
 4 files changed, 30 insertions(+), 1 deletion(-)

diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 506fccd20c..bb89558dcd 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -2148,6 +2148,14 @@ remove_self_joins_one_group(PlannerInfo *root, Relids relids)
 			Assert(root->simple_rte_array[k]->relid ==
    root->simple_rte_array[r]->relid);
 
+			/*
+			 * To avoid corner cases with table sampling methods just forbid
+			 * SJE for table sampling entries.
+			 */
+			if (root->simple_rte_array[k]->tablesample ||
+root->simple_rte_array[r]->tablesample)
+continue;
+
 			/*
 			 * It is impossible to eliminate join of two relations if they
 			 * belong to different rules of order. Otherwise planner can't be
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index e2c68fe6f9..bf839bcaf6 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -415,7 +415,10 @@ extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
 	if (!rte->lateral)
 		return;
 
-	/* Fetch the appropriate variables */
+	/* Fetch the appropriate variables.
+	 * Changes in this place may need changes in SJE logic, see
+	 * the remove_self_joins_one_group routine.
+	 */
 	if (rte->rtekind == RTE_RELATION)
 		vars = pull_vars_of_level((Node *) rte->tablesample, 0);
 	else if (rte->rtekind == RTE_SUBQUERY)
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 8b640c2fc2..63143fe55f 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6900,6 +6900,19 @@ where s1.x = 1;
Filter: (1 = 1)
 (9 rows)
 
+-- Check that SJE doesn't touch TABLESAMPLE joins
+explain (costs off)
+SELECT * FROM emp1 t1 NATURAL JOIN LATERAL
+  (SELECT * FROM emp1 t2 TABLESAMPLE SYSTEM (t1.code));
+ QUERY PLAN  
+-
+ Nested Loop
+   ->  Seq Scan on emp1 t1
+   ->  Sample Scan on emp1 t2
+ Sampling: system (t1.code)
+ Filter: ((t1.id = id) AND (t1.code = code))
+(5 rows)
+
 -- Check that PHVs do not impose any constraints on removing self joins
 explain (verbose, costs off)
 select * from emp1 t1 join emp1 t2 on t1.id = t2.id left join
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index c4c6c7b8ba..184fd0876b 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2652,6 +2652,11 @@ select 1 from emp1 t1 left join
 on true
 where s1.x = 1;
 
+-- Check that SJE doesn't touch TABLESAMPLE joins
+explain (costs off)
+SELECT * FROM emp1 t1 NATURAL JOIN LATERAL
+  (SELECT * FROM emp1 t2 TABLESAMPLE SYSTEM (t1.code));
+
 -- Check that PHVs do not impose any constraints on removing self joins
 explain (verbose, costs off)
 select * from emp1 t1 join emp1 t2 on t1.id = t2.id left join
-- 
2.39.2

Re: Removing unneeded self joins

[Alexander Korotkov]

On Wed, May 1, 2024 at 2:00 PM Alexander Lakhin  wrote:
> 30.04.2024 13:20, Alexander Korotkov wrote:
> > On Tue, Apr 30, 2024 at 9:00 AM Alexander Lakhin  
> > wrote:
> >> I've discovered another failure, introduced by d3d55ce57.
> >> Please try the following:
> >> CREATE TABLE t (a int unique, b float);
> >> SELECT * FROM t NATURAL JOIN LATERAL
> >>(SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2;
> > I think we should just forbid SJE in case when relations to be merged
> > have cross-references with lateral vars.  The draft patch for this is
> > attached.  I'd like to ask Alexander to test it, Richard and Andrei to
> > review it.  Thank you!
>
> Beside LATERAL vars, it seems that SJR doesn't play well with TABLESAMPLE
> in general. For instance:
> CREATE TABLE t (a int unique);
> INSERT INTO t SELECT * FROM generate_series (1,100);
>
> SELECT COUNT(*) FROM (SELECT * FROM t TABLESAMPLE BERNOULLI(1)) t1
>   NATURAL JOIN (SELECT * FROM t TABLESAMPLE BERNOULLI(100)) t2;
> returned 100, 100, 100 for me, though with enable_self_join_removal = off,
> I got 4, 0, 1...

Right, thank you for reporting this.

BTW, I found another case where my previous fix doesn't work.

SELECT * FROM t NATURAL JOIN LATERAL (SELECT * FROM t t2 TABLESAMPLE
SYSTEM (t.b) NATURAL JOIN LATERAL(SELECT * FROM t t3 TABLESAMPLE
SYSTEM (t2.b)) t3) t2;

I think we probably could forbid SJE for the tables with TABLESAMPLE
altogether.  Please, check the attached patch.

--
Regards,
Alexander Korotkov


sje_tablesample.patch
Description: Binary data

Re: Removing unneeded self joins

[Alexander Lakhin]

30.04.2024 13:20, Alexander Korotkov wrote:

On Tue, Apr 30, 2024 at 9:00 AM Alexander Lakhin  wrote:

I've discovered another failure, introduced by d3d55ce57.
Please try the following:
CREATE TABLE t (a int unique, b float);
SELECT * FROM t NATURAL JOIN LATERAL
   (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2;

I think we should just forbid SJE in case when relations to be merged
have cross-references with lateral vars.  The draft patch for this is
attached.  I'd like to ask Alexander to test it, Richard and Andrei to
review it.  Thank you!


Beside LATERAL vars, it seems that SJR doesn't play well with TABLESAMPLE
in general. For instance:
CREATE TABLE t (a int unique);
INSERT INTO t SELECT * FROM generate_series (1,100);

SELECT COUNT(*) FROM (SELECT * FROM t TABLESAMPLE BERNOULLI(1)) t1
 NATURAL JOIN (SELECT * FROM t TABLESAMPLE BERNOULLI(100)) t2;
returned 100, 100, 100 for me, though with enable_self_join_removal = off,
I got 4, 0, 1...

Best regards,
Alexander

Re: Removing unneeded self joins

[Alexander Korotkov]

On Tue, Apr 30, 2024 at 9:00 AM Alexander Lakhin  wrote:
> 23.10.2023 12:47, Alexander Korotkov wrote:
> > I think this patch makes substantial improvement to query planning.
> > It has received plenty of reviews.  The code is currently in quite
> > good shape.  I didn't manage to find the cases when this optimization
> > causes significant overhead to planning time.  Even if such cases will
> > be spotted there is a GUC option to disable this feature.  So, I'll
> > push this if there are no objections.
>
> I've discovered another failure, introduced by d3d55ce57.
> Please try the following:
> CREATE TABLE t (a int unique, b float);
> SELECT * FROM t NATURAL JOIN LATERAL
>   (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2;

I think we should just forbid SJE in case when relations to be merged
have cross-references with lateral vars.  The draft patch for this is
attached.  I'd like to ask Alexander to test it, Richard and Andrei to
review it.  Thank you!

--
Regards,
Alexander Korotkov


sje_skip_cross_lateral_vars.patch
Description: Binary data

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi, Alexander!

On Tue, Apr 30, 2024 at 9:00 AM Alexander Lakhin  wrote:
> 23.10.2023 12:47, Alexander Korotkov wrote:
> > I think this patch makes substantial improvement to query planning.
> > It has received plenty of reviews.  The code is currently in quite
> > good shape.  I didn't manage to find the cases when this optimization
> > causes significant overhead to planning time.  Even if such cases will
> > be spotted there is a GUC option to disable this feature.  So, I'll
> > push this if there are no objections.
>
> I've discovered another failure, introduced by d3d55ce57.
> Please try the following:
> CREATE TABLE t (a int unique, b float);
> SELECT * FROM t NATURAL JOIN LATERAL
>   (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2;
>
> With asserts enabled, it triggers
> TRAP: failed Assert("!bms_is_member(rti, lateral_relids)"), File: 
> "initsplan.c", Line: 697, PID: 3074054
> ExceptionalCondition at assert.c:52:13
> create_lateral_join_info at initsplan.c:700:8
> query_planner at planmain.c:257:2
> grouping_planner at planner.c:1523:17
> subquery_planner at planner.c:1098:2
> standard_planner at planner.c:415:9
> planner at planner.c:282:12
> pg_plan_query at postgres.c:904:9
> pg_plan_queries at postgres.c:996:11
> exec_simple_query at postgres.c:1193:19
> PostgresMain at postgres.c:4684:27
>
> With no asserts, I get:
> ERROR:  failed to construct the join relation
>
> Please take a look at this.

I'm looking into this, thank you!

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Alexander Lakhin]

Hello Alexander,

23.10.2023 12:47, Alexander Korotkov wrote:

I think this patch makes substantial improvement to query planning.
It has received plenty of reviews.  The code is currently in quite
good shape.  I didn't manage to find the cases when this optimization
causes significant overhead to planning time.  Even if such cases will
be spotted there is a GUC option to disable this feature.  So, I'll
push this if there are no objections.


I've discovered another failure, introduced by d3d55ce57.
Please try the following:
CREATE TABLE t (a int unique, b float);
SELECT * FROM t NATURAL JOIN LATERAL
 (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2;

With asserts enabled, it triggers
TRAP: failed Assert("!bms_is_member(rti, lateral_relids)"), File: 
"initsplan.c", Line: 697, PID: 3074054
ExceptionalCondition at assert.c:52:13
create_lateral_join_info at initsplan.c:700:8
query_planner at planmain.c:257:2
grouping_planner at planner.c:1523:17
subquery_planner at planner.c:1098:2
standard_planner at planner.c:415:9
planner at planner.c:282:12
pg_plan_query at postgres.c:904:9
pg_plan_queries at postgres.c:996:11
exec_simple_query at postgres.c:1193:19
PostgresMain at postgres.c:4684:27

With no asserts, I get:
ERROR:  failed to construct the join relation

Please take a look at this.

Best regards,
Alexander

Re: Removing unneeded self joins

[Noah Misch]

Hello,

On Sat, Feb 24, 2024 at 01:02:01PM +0200, Alexander Korotkov wrote:
> On Sat, Feb 24, 2024 at 7:12 AM Noah Misch  wrote:
> > On Sat, Feb 24, 2024 at 12:36:59AM +0200, Alexander Korotkov wrote:
> > > On Thu, Feb 22, 2024 at 10:51 AM Andrei Lepikhov 
> > >  wrote:
> > > > On 21/2/2024 14:26, Richard Guo wrote:
> > > > > I think the right fix for these issues is to introduce a new element
> > > > > 'sublevels_up' in ReplaceVarnoContext, and enhance 
> > > > > replace_varno_walker
> > > > > to 1) recurse into subselects with sublevels_up increased, and 2)
> > > > > perform the replacement only when varlevelsup is equal to 
> > > > > sublevels_up.
> > > > This code looks good. No idea how we have lost it before.
> > >
> > > Thanks to Richard for the patch and to Andrei for review.  I also find
> > > code looking good.  Pushed with minor edits from me.
> >
> > I feel this, commit 466979e, misses a few of our project standards:
> >
> > - The patch makes many non-whitespace changes to existing test queries.  
> > This
> >   makes it hard to review the consequences of the non-test part of the 
> > patch.
> >   Did you minimize such edits?  Of course, not every such edit is avoidable.
> >
> > - The commit message doesn't convey whether this is refactoring or is a bug
> >   fix.  This makes it hard to write release notes, among other things.  From
> >   this mailing list thread, it gather it's a bug fix in 489072ab7a, hence
> >   v17-specific.  The commit message for 489072ab7a is also silent about that
> >   commit's status as refactoring or as a bug fix.
> >
> > - Normally, I could answer the previous question by reading the test case
> >   diffs.  However, in addition to the first point about non-whitespace
> >   changes, the first three join.sql patch hunks just change whitespace.
> >   Worse, since they move line breaks, "git diff -w" doesn't filter them out.
> >
> > To what extent are those community standards vs. points of individual
> > committer preference?  Please tell me where I'm wrong here.
> 
> I agree that commit 466979e is my individual committer failure.  I
> should have written a better, more clear commit message and separate
> tests refactoring from the bug fix.
> 
> I'm not so sure about 489072ab7a (except it provides a wrong fix).  It
> has a "Reported-by:" field meaning it's a problem reported by a
> particular person.  The "Discussion:" points directly to the reported
> test case.  And commit contains the relevant test case.  The commit
> message could be more wordy though.

Agreed, the first and third points don't apply to 489072ab7a.  Thanks to that,
one can deduce from its new test case query that it fixes a bug.  It sounds
like we agree about commit 466979e, so that's good.

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi, Noah!

On Sat, Feb 24, 2024 at 7:12 AM Noah Misch  wrote:
> On Sat, Feb 24, 2024 at 12:36:59AM +0200, Alexander Korotkov wrote:
> > On Thu, Feb 22, 2024 at 10:51 AM Andrei Lepikhov 
> >  wrote:
> > > On 21/2/2024 14:26, Richard Guo wrote:
> > > > I think the right fix for these issues is to introduce a new element
> > > > 'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker
> > > > to 1) recurse into subselects with sublevels_up increased, and 2)
> > > > perform the replacement only when varlevelsup is equal to sublevels_up.
> > > This code looks good. No idea how we have lost it before.
> >
> > Thanks to Richard for the patch and to Andrei for review.  I also find
> > code looking good.  Pushed with minor edits from me.
>
> I feel this, commit 466979e, misses a few of our project standards:
>
> - The patch makes many non-whitespace changes to existing test queries.  This
>   makes it hard to review the consequences of the non-test part of the patch.
>   Did you minimize such edits?  Of course, not every such edit is avoidable.
>
> - The commit message doesn't convey whether this is refactoring or is a bug
>   fix.  This makes it hard to write release notes, among other things.  From
>   this mailing list thread, it gather it's a bug fix in 489072ab7a, hence
>   v17-specific.  The commit message for 489072ab7a is also silent about that
>   commit's status as refactoring or as a bug fix.
>
> - Normally, I could answer the previous question by reading the test case
>   diffs.  However, in addition to the first point about non-whitespace
>   changes, the first three join.sql patch hunks just change whitespace.
>   Worse, since they move line breaks, "git diff -w" doesn't filter them out.
>
> To what extent are those community standards vs. points of individual
> committer preference?  Please tell me where I'm wrong here.

I agree that commit 466979e is my individual committer failure.  I
should have written a better, more clear commit message and separate
tests refactoring from the bug fix.

I'm not so sure about 489072ab7a (except it provides a wrong fix).  It
has a "Reported-by:" field meaning it's a problem reported by a
particular person.  The "Discussion:" points directly to the reported
test case.  And commit contains the relevant test case.  The commit
message could be more wordy though.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Noah Misch]

On Sat, Feb 24, 2024 at 12:36:59AM +0200, Alexander Korotkov wrote:
> On Thu, Feb 22, 2024 at 10:51 AM Andrei Lepikhov  
> wrote:
> > On 21/2/2024 14:26, Richard Guo wrote:
> > > I think the right fix for these issues is to introduce a new element
> > > 'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker
> > > to 1) recurse into subselects with sublevels_up increased, and 2)
> > > perform the replacement only when varlevelsup is equal to sublevels_up.
> > This code looks good. No idea how we have lost it before.
> 
> Thanks to Richard for the patch and to Andrei for review.  I also find
> code looking good.  Pushed with minor edits from me.

I feel this, commit 466979e, misses a few of our project standards:

- The patch makes many non-whitespace changes to existing test queries.  This
  makes it hard to review the consequences of the non-test part of the patch.
  Did you minimize such edits?  Of course, not every such edit is avoidable.

- The commit message doesn't convey whether this is refactoring or is a bug
  fix.  This makes it hard to write release notes, among other things.  From
  this mailing list thread, it gather it's a bug fix in 489072ab7a, hence
  v17-specific.  The commit message for 489072ab7a is also silent about that
  commit's status as refactoring or as a bug fix.

- Normally, I could answer the previous question by reading the test case
  diffs.  However, in addition to the first point about non-whitespace
  changes, the first three join.sql patch hunks just change whitespace.
  Worse, since they move line breaks, "git diff -w" doesn't filter them out.

To what extent are those community standards vs. points of individual
committer preference?  Please tell me where I'm wrong here.

Re: Removing unneeded self joins

[Alexander Korotkov]

On Thu, Feb 22, 2024 at 10:51 AM Andrei Lepikhov
 wrote:
> On 21/2/2024 14:26, Richard Guo wrote:
> > I think the right fix for these issues is to introduce a new element
> > 'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker
> > to 1) recurse into subselects with sublevels_up increased, and 2)
> > perform the replacement only when varlevelsup is equal to sublevels_up.
> This code looks good. No idea how we have lost it before.

Thanks to Richard for the patch and to Andrei for review.  I also find
code looking good.  Pushed with minor edits from me.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 21/2/2024 14:26, Richard Guo wrote:

I think the right fix for these issues is to introduce a new element
'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker
to 1) recurse into subselects with sublevels_up increased, and 2)
perform the replacement only when varlevelsup is equal to sublevels_up.

This code looks good. No idea how we have lost it before.


While writing the fix, I noticed some outdated comments.  Such as in
remove_rel_from_query, the first for loop updates otherrel's attr_needed
as well as lateral_vars, but the comment only mentions attr_needed.  So
this patch also fixes some outdated comments.

Thanks, looks good.


While writing the test cases, I found that the test cases for SJE are
quite messy.  Below are what I have noticed:

* There are several test cases using catalog tables like pg_class,
pg_stats, pg_index, etc. for testing join removal.  I don't see a reason
why we need to use catalog tables, and I think this just raises the risk
of instability.

I see only one unusual query with the pg_class involved.


* In many test cases, a mix of uppercase and lowercase keywords is used
in one query.  I think it'd better to maintain consistency by using
either all uppercase or all lowercase keywords in one query.

I see uppercase -> lowercase change:
select t1.*, t2.a as ax from sj t1 join sj t2
and lowercase -> uppercase in many other cases:
explain (costs off)
I guess it is a matter of taste, so give up for the committer decision. 
Technically, it's OK.


* In most situations, we verify the plan and the output of a query like:

explain (costs off)
select ...;
select ...;

The two select queries are supposed to be the same.  But in the SJE test
cases, I have noticed instances where the two select queries differ from
each other.

This patch also includes some cosmetic tweaks for SJE test cases.  It
does not change the test cases using catalog tables though.  I think
that should be a seperate patch.
I can't assess the necessity of changing these dozens of lines of code 
because I follow another commenting style, but technically, it's still OK.


--
regards,
Andrei Lepikhov
Postgres Professional

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 21/2/2024 14:26, Richard Guo wrote:

This patch also includes some cosmetic tweaks for SJE test cases.  It
does not change the test cases using catalog tables though.  I think
that should be a seperate patch.
Thanks for this catch, it is really messy thing, keeping aside the 
question why we need two different subtrees for the same query.

I will look into your fix.

--
regards,
Andrei Lepikhov
Postgres Professional

Re: Removing unneeded self joins

[Richard Guo]

On Mon, Feb 19, 2024 at 1:24 PM Andrei Lepikhov 
wrote:

> On 18/2/2024 23:18, Alexander Korotkov wrote:
> > On Sun, Feb 18, 2024 at 5:04 PM Alexander Korotkov 
> wrote:
> >> On Sun, Feb 18, 2024 at 3:00 PM Alexander Lakhin 
> wrote:
> >>> Please look at the following query which fails with an error since
> >>> d3d55ce57:
> >>>
> >>> create table t (i int primary key);
> >>>
> >>> select t3.i from t t1
> >>>   join t t2 on t1.i = t2.i,
> >>>   lateral (select t1.i limit 1) t3;
> >>>
> >>> ERROR:  non-LATERAL parameter required by subquery
> >>
> >> Thank you for spotting.  I'm looking at this.
> >
> > Attached is a draft patch fixing this query.  Could you, please, recheck?
> I reviewed this patch. Why do you check only the target list? I guess
> these links can be everywhere. See the patch in the attachment with the
> elaborated test and slightly changed code.


I just noticed that this fix has been committed in 489072ab7a, but it's
just flat wrong.

* The fix walks the subquery and replaces all the Vars with a varno
equal to the relid of the removing rel, without checking the
varlevelsup.  That is to say, a Var that belongs to the subquery itself
might also be replaced, which is wrong.  For instance,

create table t (i int primary key);

explain (costs off)
select t3.i from t t1
  join t t2 on t1.i = t2.i
  join lateral (select * from (select t1.i offset 0) offset 0) t3 on true;
ERROR:  no relation entry for relid 2


* The fix only traverses one level within the subquery, so Vars that
appear in subqueries with multiple levels cannot be replaced.  For
instance,

explain (costs off)
select t4.i from t t1
  join t t2 on t1.i = t2.i
  join lateral (select t3.i from t t3, (select t1.i) offset 0) t4 on true;
ERROR:  non-LATERAL parameter required by subquery


I think the right fix for these issues is to introduce a new element
'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker
to 1) recurse into subselects with sublevels_up increased, and 2)
perform the replacement only when varlevelsup is equal to sublevels_up.

Attached is a patch for the fix.

While writing the fix, I noticed some outdated comments.  Such as in
remove_rel_from_query, the first for loop updates otherrel's attr_needed
as well as lateral_vars, but the comment only mentions attr_needed.  So
this patch also fixes some outdated comments.

While writing the test cases, I found that the test cases for SJE are
quite messy.  Below are what I have noticed:

* There are several test cases using catalog tables like pg_class,
pg_stats, pg_index, etc. for testing join removal.  I don't see a reason
why we need to use catalog tables, and I think this just raises the risk
of instability.

* In many test cases, a mix of uppercase and lowercase keywords is used
in one query.  I think it'd better to maintain consistency by using
either all uppercase or all lowercase keywords in one query.

* In most situations, we verify the plan and the output of a query like:

explain (costs off)
select ...;
select ...;

The two select queries are supposed to be the same.  But in the SJE test
cases, I have noticed instances where the two select queries differ from
each other.

This patch also includes some cosmetic tweaks for SJE test cases.  It
does not change the test cases using catalog tables though.  I think
that should be a seperate patch.

Thanks
Richard


v1-0001-Replace-lateral-references-to-removed-rels-in-subqueries.patch
Description: Binary data

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 18/2/2024 23:18, Alexander Korotkov wrote:

On Sun, Feb 18, 2024 at 5:04 PM Alexander Korotkov  wrote:

On Sun, Feb 18, 2024 at 3:00 PM Alexander Lakhin  wrote:

09.01.2024 01:09, Alexander Korotkov wrote:

Fixed in 30b4955a46.


Please look at the following query which fails with an error since
d3d55ce57:

create table t (i int primary key);

select t3.i from t t1
  join t t2 on t1.i = t2.i,
  lateral (select t1.i limit 1) t3;

ERROR:  non-LATERAL parameter required by subquery


Thank you for spotting.  I'm looking at this.


Attached is a draft patch fixing this query.  Could you, please, recheck?
I reviewed this patch. Why do you check only the target list? I guess 
these links can be everywhere. See the patch in the attachment with the 
elaborated test and slightly changed code.


--
regards,
Andrei Lepikhov
Postgres Professional
From 7f94a3c96fd410522b87e570240cdb96b300dd31 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" 
Date: Mon, 19 Feb 2024 12:17:55 +0700
Subject: [PATCH] Replace relids in lateral subquery target list during SJE

---
 src/backend/optimizer/plan/analyzejoins.c | 29 ++-
 src/test/regress/expected/join.out| 44 +++
 src/test/regress/sql/join.sql | 12 +++
 3 files changed, 84 insertions(+), 1 deletion(-)

diff --git a/src/backend/optimizer/plan/analyzejoins.c 
b/src/backend/optimizer/plan/analyzejoins.c
index e494acd51a..072298f66c 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -395,7 +395,34 @@ remove_rel_from_query(PlannerInfo *root, RelOptInfo *rel,
}
 
/* Update lateral references. */
-   replace_varno((Node *) otherrel->lateral_vars, relid, subst);
+   if (root->hasLateralRTEs)
+   {
+   RangeTblEntry *rte = root->simple_rte_array[rti];
+   ReplaceVarnoContext ctx = {.from = relid,.to = subst};
+
+   if (rte->lateral)
+   {
+   replace_varno((Node *) otherrel->lateral_vars, 
relid, subst);
+
+   /*
+* Although we pass root->parse through cleanup 
procedure,
+* but parse->rtable and rte contains refs to 
different copies
+* of the subquery.
+*/
+   if (otherrel->rtekind == RTE_SUBQUERY)
+   query_tree_walker(rte->subquery, 
replace_varno_walker, &ctx,
+ 
QTW_EXAMINE_SORTGROUP);
+#ifdef USE_ASSERT_CHECKING
+   /* Just check possibly hidden non-replaced 
relids */
+   Assert(!bms_is_member(relid, pull_varnos(root, 
(Node *) rte->tablesample)));
+   Assert(!bms_is_member(relid, pull_varnos(root, 
(Node *) rte->functions)));
+   Assert(!bms_is_member(relid, pull_varnos(root, 
(Node *) rte->tablefunc)));
+   Assert(!bms_is_member(relid, pull_varnos(root, 
(Node *) rte->values_lists)));
+#endif
+   }
+   }
+
+
}
 
/*
diff --git a/src/test/regress/expected/join.out 
b/src/test/regress/expected/join.out
index 0c2cba8921..d560a4a6b9 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6349,6 +6349,50 @@ on true;
->  Seq Scan on int8_tbl y
 (7 rows)
 
+-- Test processing target lists in lateral subqueries
+explain (verbose, costs off)
+SELECT t3.a FROM sj t1, sj t2,
+LATERAL (SELECT t1.a WHERE t1.a <> 1
+GROUP BY (t1.a) HAVING t1.a > 0 ORDER BY t1.a LIMIT 1) t3,
+LATERAL (SELECT t1.a,t3.a WHERE t1.a <> t3.a+t2.a
+GROUP BY (t3.a) HAVING t1.a > t3.a*t3.a+t2.a/t1.a LIMIT 2) t4,
+LATERAL (SELECT * FROM sj TABLESAMPLE bernoulli(t1.a/t2.a)
+REPEATABLE (t1.a+t2.a)) t5,
+LATERAL generate_series(1, t1.a + t2.a) AS t6
+WHERE t1.a = t2.a;
+  QUERY PLAN   

+---
+ Nested Loop
+   Output: (t2.a)
+   ->  Nested Loop
+ Output: t2.a, (t2.a)
+ ->  Nested Loop
+   Output: t2.a, (t2.a)
+   ->  Nested Loop
+ Output: t2.a, (t2.a)
+ ->  Seq Scan on public.sj t2
+   Output: t2.a, t2.b, t2.c
+   Filter: (t2.a IS NOT NULL)
+ ->  Limit
+   Output: (t2.a)
+   ->  Group
+ Output: t2.a
+   

Re: Removing unneeded self joins

[Alexander Lakhin]

18.02.2024 19:18, Alexander Korotkov wrote:

Attached is a draft patch fixing this query. Could you, please, recheck?


Yes, this patch fixes the behavior for that query (I've also tried several
similar queries). Though I don't know the code well enough to judge the
code change.

Best regards,
Alexander

Re: Removing unneeded self joins

[Alexander Korotkov]

On Sun, Feb 18, 2024 at 5:04 PM Alexander Korotkov  wrote:
> On Sun, Feb 18, 2024 at 3:00 PM Alexander Lakhin  wrote:
> > 09.01.2024 01:09, Alexander Korotkov wrote:
> >
> > Fixed in 30b4955a46.
> >
> >
> > Please look at the following query which fails with an error since
> > d3d55ce57:
> >
> > create table t (i int primary key);
> >
> > select t3.i from t t1
> >  join t t2 on t1.i = t2.i,
> >  lateral (select t1.i limit 1) t3;
> >
> > ERROR:  non-LATERAL parameter required by subquery
>
> Thank you for spotting.  I'm looking at this.

Attached is a draft patch fixing this query.  Could you, please, recheck?

--
Regards,
Alexander Korotkov


0001-Replace-relids-in-lateral-subquery-target-list-du-v1.patch
Description: Binary data

Re: Removing unneeded self joins

[Alexander Korotkov]

On Sun, Feb 18, 2024 at 3:00 PM Alexander Lakhin  wrote:
> 09.01.2024 01:09, Alexander Korotkov wrote:
>
> Fixed in 30b4955a46.
>
>
> Please look at the following query which fails with an error since
> d3d55ce57:
>
> create table t (i int primary key);
>
> select t3.i from t t1
>  join t t2 on t1.i = t2.i,
>  lateral (select t1.i limit 1) t3;
>
> ERROR:  non-LATERAL parameter required by subquery

Thank you for spotting.  I'm looking at this.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Alexander Lakhin]

Hi Alexander,

09.01.2024 01:09, Alexander Korotkov wrote:

Fixed in 30b4955a46.


Please look at the following query which fails with an error since
d3d55ce57:

create table t (i int primary key);

select t3.i from t t1
 join t t2 on t1.i = t2.i,
 lateral (select t1.i limit 1) t3;

ERROR:  non-LATERAL parameter required by subquery

Best regards,
Alexander

Re: Removing unneeded self joins

[Alexander Korotkov]

On Tue, Jan 9, 2024 at 8:08 AM Alexander Korotkov  wrote:
> On Tue, Jan 9, 2024 at 6:00 AM Alexander Lakhin  wrote:
> > 09.01.2024 01:09, Alexander Korotkov wrote:
> > > Fixed in 30b4955a46.
> >
> > Thank you for fixing that!
> >
> > I've found another anomaly coined with d3d55ce57. This query:
> > CREATE TABLE t(a int PRIMARY KEY, b int);
> > INSERT INTO t VALUES  (1, 1), (2, 1);
> >
> > WITH t1 AS (SELECT * FROM t)
> > UPDATE t SET b = t1.b + 1 FROM t1
> > WHERE t.a = t1.a RETURNING t.a, t1.b;
> >
> > gives "ERROR:  variable not found in subplan target lists" on d3d55ce57, but
> > starting from a7928a57b it gives an incorrect result:
> >   a | b
> > ---+---
> >   1 | 2
> >   2 | 2
> > (2 rows)
>
> I see.  It seems to be not safe to apply SJE to the modify table
> target relation because it could use a different snapshot for the
> RETURNING clause.  I think we should just forbid SJE to involve the
> modify table target relation.  I'm planning to fix this later today.

Fixed in 8c441c08279.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Alexander Korotkov]

On Tue, Jan 9, 2024 at 6:00 AM Alexander Lakhin  wrote:
> 09.01.2024 01:09, Alexander Korotkov wrote:
> > Fixed in 30b4955a46.
>
> Thank you for fixing that!
>
> I've found another anomaly coined with d3d55ce57. This query:
> CREATE TABLE t(a int PRIMARY KEY, b int);
> INSERT INTO t VALUES  (1, 1), (2, 1);
>
> WITH t1 AS (SELECT * FROM t)
> UPDATE t SET b = t1.b + 1 FROM t1
> WHERE t.a = t1.a RETURNING t.a, t1.b;
>
> gives "ERROR:  variable not found in subplan target lists" on d3d55ce57, but
> starting from a7928a57b it gives an incorrect result:
>   a | b
> ---+---
>   1 | 2
>   2 | 2
> (2 rows)

I see.  It seems to be not safe to apply SJE to the modify table
target relation because it could use a different snapshot for the
RETURNING clause.  I think we should just forbid SJE to involve the
modify table target relation.  I'm planning to fix this later today.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Alexander Lakhin]

09.01.2024 01:09, Alexander Korotkov wrote:

Fixed in 30b4955a46.


Thank you for fixing that!

I've found another anomaly coined with d3d55ce57. This query:
CREATE TABLE t(a int PRIMARY KEY, b int);
INSERT INTO t VALUES  (1, 1), (2, 1);

WITH t1 AS (SELECT * FROM t)
UPDATE t SET b = t1.b + 1 FROM t1
WHERE t.a = t1.a RETURNING t.a, t1.b;

gives "ERROR:  variable not found in subplan target lists" on d3d55ce57, but
starting from a7928a57b it gives an incorrect result:
 a | b
---+---
 1 | 2
 2 | 2
(2 rows)


Best regards,
Alexander

Re: Removing unneeded self joins

[Alexander Korotkov]

On Mon, Jan 8, 2024 at 10:20 PM Alexander Korotkov  wrote:
> On Mon, Jan 8, 2024 at 10:00 PM Alexander Lakhin  wrote:
> > Please look at the following query which produces an incorrect result since
> > d3d55ce57:
> > CREATE TABLE t(a int PRIMARY KEY, b int);
> > INSERT INTO t VALUES  (1, 1), (2, 1);
> > SELECT * FROM t WHERE EXISTS (SELECT * FROM t t2 WHERE t2.a = t.b AND t2.b 
> > > 0);
> >
> >   a | b
> > ---+---
> >   1 | 1
> > (1 row)
> >
> > I think that the expected result is:
> >   a | b
> > ---+---
> >   1 | 1
> >   2 | 1
> > (2 rows)
>
> Thank you for your report.  I'm looking at this now.

Fixed in 30b4955a46.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Alexander Korotkov]

On Mon, Jan 8, 2024 at 10:00 PM Alexander Lakhin  wrote:
> Please look at the following query which produces an incorrect result since
> d3d55ce57:
> CREATE TABLE t(a int PRIMARY KEY, b int);
> INSERT INTO t VALUES  (1, 1), (2, 1);
> SELECT * FROM t WHERE EXISTS (SELECT * FROM t t2 WHERE t2.a = t.b AND t2.b > 
> 0);
>
>   a | b
> ---+---
>   1 | 1
> (1 row)
>
> I think that the expected result is:
>   a | b
> ---+---
>   1 | 1
>   2 | 1
> (2 rows)

Thank you for your report.  I'm looking at this now.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Alexander Lakhin]

Hello Andrei and Alexander,

Please look at the following query which produces an incorrect result since
d3d55ce57:
CREATE TABLE t(a int PRIMARY KEY, b int);
INSERT INTO t VALUES  (1, 1), (2, 1);
SELECT * FROM t WHERE EXISTS (SELECT * FROM t t2 WHERE t2.a = t.b AND t2.b > 0);

 a | b
---+---
 1 | 1
(1 row)

I think that the expected result is:
 a | b
---+---
 1 | 1
 2 | 1
(2 rows)

Best regards,
Alexander

Re: Removing unneeded self joins

[Alexander Lakhin]

Hi Andrei,

29.12.2023 12:58, Andrei Lepikhov wrote:

Thanks for the report!
The problem is with the resultRelation field. We forget to replace the relid 
here.
Could you check your issue with the patch in the attachment? Does it resolve 
this case?



Yes, with the patch applied I see no error.
Thank you!

Best regards,
Alexander

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 29/12/2023 12:00, Alexander Lakhin wrote:

Hi Alexander,

23.10.2023 14:29, Alexander Korotkov wrote:

Fixed all of the above. Thank you for catching this!


I've discovered that starting from d3d55ce57 the following query:
CREATE TABLE t(a int PRIMARY KEY);

WITH tt AS (SELECT * FROM t)
UPDATE t SET a = tt.a + 1 FROM tt
WHERE tt.a = t.a RETURNING t.a;

triggers an error "variable not found in subplan target lists".
(Commits 8a8ed916f and b5fb6736e don't fix this, unfortunately.)


Thanks for the report!
The problem is with the resultRelation field. We forget to replace the 
relid here.
Could you check your issue with the patch in the attachment? Does it 
resolve this case?


--
regards,
Andrei Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/plan/analyzejoins.c 
b/src/backend/optimizer/plan/analyzejoins.c
index 6c02fe8908..f79c673afd 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -1861,6 +1861,8 @@ remove_self_join_rel(PlannerInfo *root, PlanRowMark 
*kmark, PlanRowMark *rmark,
/* Replace varno in all the query structures */
query_tree_walker(root->parse, replace_varno_walker, &ctx,
  QTW_EXAMINE_SORTGROUP);
+   if (root->parse->resultRelation == toRemove->relid)
+   root->parse->resultRelation = toKeep->relid;
 
/* Replace links in the planner info */
remove_rel_from_query(root, toRemove, toKeep->relid, NULL, NULL);
@@ -1870,6 +1872,9 @@ remove_self_join_rel(PlannerInfo *root, PlanRowMark 
*kmark, PlanRowMark *rmark,
  toRemove->relid, toKeep->relid);
replace_varno((Node *) root->processed_groupClause,
  toRemove->relid, toKeep->relid);
+   replace_relid(root->all_result_relids, toRemove->relid, toKeep->relid);
+   replace_relid(root->leaf_result_relids, toRemove->relid, toKeep->relid);
+
 
/*
 * There may be references to the rel in root->fkey_list, but if so,

Re: Removing unneeded self joins

[Alexander Lakhin]

Hi Alexander,

23.10.2023 14:29, Alexander Korotkov wrote:

Fixed all of the above. Thank you for catching this!


I've discovered that starting from d3d55ce57 the following query:
CREATE TABLE t(a int PRIMARY KEY);

WITH tt AS (SELECT * FROM t)
UPDATE t SET a = tt.a + 1 FROM tt
WHERE tt.a = t.a RETURNING t.a;

triggers an error "variable not found in subplan target lists".
(Commits 8a8ed916f and b5fb6736e don't fix this, unfortunately.)

Best regards,
Alexander

Re: Removing unneeded self joins

[Alexander Korotkov]

On Mon, Oct 23, 2023 at 2:00 PM Alexander Lakhin  wrote:
> 23.10.2023 12:47, Alexander Korotkov wrote:
> > I think this patch makes substantial improvement to query planning.
> > It has received plenty of reviews.  The code is currently in quite
> > good shape.  I didn't manage to find the cases when this optimization
> > causes significant overhead to planning time.  Even if such cases will
> > be spotted there is a GUC option to disable this feature.  So, I'll
> > push this if there are no objections.
>
> On a quick glance, I've noticed following typos/inconsistencies in the
> patch, which maybe worth fixing:
> s/cadidates/candidates/
> s/uniquiness/uniqueness/
> s/selfjoin/self-join/
> s/seperate/separate/
>
> Also, shouldn't the reference "see generate_implied_equalities" be
> "see generate_implied_equalities_for_column"?

Fixed all of the above.  Thank you for catching this!

--
Regards,
Alexander Korotkov


0001-Remove-useless-self-joins-v48.patch
Description: Binary data

Re: Removing unneeded self joins

[Alexander Lakhin]

Hi Alexander,

23.10.2023 12:47, Alexander Korotkov wrote:

I think this patch makes substantial improvement to query planning.
It has received plenty of reviews.  The code is currently in quite
good shape.  I didn't manage to find the cases when this optimization
causes significant overhead to planning time.  Even if such cases will
be spotted there is a GUC option to disable this feature.  So, I'll
push this if there are no objections.


On a quick glance, I've noticed following typos/inconsistencies in the
patch, which maybe worth fixing:
s/cadidates/candidates/
s/uniquiness/uniqueness/
s/selfjoin/self-join/
s/seperate/separate/

Also, shouldn't the reference "see generate_implied_equalities" be
"see generate_implied_equalities_for_column"?

Best regards,
Alexander

Re: Removing unneeded self joins

[Alexander Korotkov]

On Mon, Oct 23, 2023 at 6:43 AM Andrei Lepikhov
 wrote:
> On 22/10/2023 05:01, Alexander Korotkov wrote:
> > On Thu, Oct 19, 2023 at 6:16 AM Andrei Lepikhov
> >  wrote:
> >> On 19/10/2023 01:50, Alexander Korotkov wrote:
> >>> This query took 3778.432 ms with self-join removal disabled, and
> >>> 3756.009 ms with self-join removal enabled.  So, no measurable
> >>> overhead.  Similar to the higher number of joins.  Can you imagine
> >>> some extreme case when self-join removal could introduce significant
> >>> overhead in comparison with other optimizer parts?  If not, should we
> >>> remove self_join_search_limit GUC?
> >> Thanks,
> >> It was Zhihong Yu who worried about that case [1]. And my purpose was to
> >> show a method to avoid such a problem if it would be needed.
> >> I guess the main idea here is that we have a lot of self-joins, but only
> >> few of them (or no one) can be removed.
> >> I can't imagine a practical situation when we can be stuck in the
> >> problems here. So, I vote to remove this GUC.
> >
> > I've removed the self_join_search_limit.  Anyway there is
> > enable_self_join_removal if the self join removal algorithm causes any
> > problems.  I also did some grammar corrections for the comments.  I
> > think the patch is getting to the committable shape.  I noticed some
> > failures on commitfest.cputube.org.  I'd like to check how this
> > version will pass it.
>
> I have observed the final patch. A couple of minor changes can be made
> (see attachment).

Thank you, Andrei!  I've integrated your changes into the patch.

> Also, I see room for improvement, but it can be done later. For example,
> we limit the optimization to only ordinary tables in this patch. It can
> be extended at least with partitioned and foreign tables soon.

Yes, I think it's reasonable to postpone some improvements.  It's
important to get the basic feature in, make sure it's safe and stable.
Then we can make improvements incrementally.

I think this patch makes substantial improvement to query planning.
It has received plenty of reviews.  The code is currently in quite
good shape.  I didn't manage to find the cases when this optimization
causes significant overhead to planning time.  Even if such cases will
be spotted there is a GUC option to disable this feature.  So, I'll
push this if there are no objections.

--
Regards,
Alexander Korotkov


0001-Remove-useless-self-joins-v47.patch
Description: Binary data

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 22/10/2023 05:01, Alexander Korotkov wrote:

On Thu, Oct 19, 2023 at 6:16 AM Andrei Lepikhov
 wrote:

On 19/10/2023 01:50, Alexander Korotkov wrote:

This query took 3778.432 ms with self-join removal disabled, and
3756.009 ms with self-join removal enabled.  So, no measurable
overhead.  Similar to the higher number of joins.  Can you imagine
some extreme case when self-join removal could introduce significant
overhead in comparison with other optimizer parts?  If not, should we
remove self_join_search_limit GUC?

Thanks,
It was Zhihong Yu who worried about that case [1]. And my purpose was to
show a method to avoid such a problem if it would be needed.
I guess the main idea here is that we have a lot of self-joins, but only
few of them (or no one) can be removed.
I can't imagine a practical situation when we can be stuck in the
problems here. So, I vote to remove this GUC.


I've removed the self_join_search_limit.  Anyway there is
enable_self_join_removal if the self join removal algorithm causes any
problems.  I also did some grammar corrections for the comments.  I
think the patch is getting to the committable shape.  I noticed some
failures on commitfest.cputube.org.  I'd like to check how this
version will pass it.


I have observed the final patch. A couple of minor changes can be made 
(see attachment).
Also, I see room for improvement, but it can be done later. For example, 
we limit the optimization to only ordinary tables in this patch. It can 
be extended at least with partitioned and foreign tables soon.


--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/plan/analyzejoins.c 
b/src/backend/optimizer/plan/analyzejoins.c
index 6b848aadad..b84197dadb 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -23,7 +23,6 @@
 #include "postgres.h"
 
 #include "catalog/pg_class.h"
-#include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/joininfo.h"
@@ -50,7 +49,7 @@ typedef struct UniqueRelInfo
 } UniqueRelInfo;
 
 /*
- * The context for replace_varno_walker() containing source and target relids2
+ * The context for replace_varno_walker() containing source and target relids.
  */
 typedef struct
 {

Re: Removing unneeded self joins

[Alexander Korotkov]

On Thu, Oct 19, 2023 at 6:16 AM Andrei Lepikhov
 wrote:
> On 19/10/2023 01:50, Alexander Korotkov wrote:
> > This query took 3778.432 ms with self-join removal disabled, and
> > 3756.009 ms with self-join removal enabled.  So, no measurable
> > overhead.  Similar to the higher number of joins.  Can you imagine
> > some extreme case when self-join removal could introduce significant
> > overhead in comparison with other optimizer parts?  If not, should we
> > remove self_join_search_limit GUC?
> Thanks,
> It was Zhihong Yu who worried about that case [1]. And my purpose was to
> show a method to avoid such a problem if it would be needed.
> I guess the main idea here is that we have a lot of self-joins, but only
> few of them (or no one) can be removed.
> I can't imagine a practical situation when we can be stuck in the
> problems here. So, I vote to remove this GUC.

I've removed the self_join_search_limit.  Anyway there is
enable_self_join_removal if the self join removal algorithm causes any
problems.  I also did some grammar corrections for the comments.  I
think the patch is getting to the committable shape.  I noticed some
failures on commitfest.cputube.org.  I'd like to check how this
version will pass it.

--
Regards,
Alexander Korotkov


0001-Remove-useless-self-joins-v46.patch
Description: Binary data

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 19/10/2023 01:50, Alexander Korotkov wrote:

On Mon, Oct 16, 2023 at 11:28 AM Andrei Lepikhov
 wrote:

On 12/10/2023 18:32, Alexander Korotkov wrote:

On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov
 wrote:

On 4/10/2023 14:34, Alexander Korotkov wrote:

   > Relid replacement machinery is the most contradictory code here. We used
   > a utilitarian approach and implemented a simplistic variant.

   > > 2) It would be nice to skip the insertion of IS NOT NULL checks when
   > > they are not necessary.  [1] points that infrastructure from [2] might
   > > be useful.  The patchset from [2] seems committed mow.  However, I
   > > can't see it is directly helpful in this matter.  Could we just skip
   > > adding IS NOT NULL clause for the columns, that have
   > > pg_attribute.attnotnull set?
   > Thanks for the links, I will look into that case.

To be more precise, in the attachment, you can find a diff to the main
patch, which shows the volume of changes to achieve the desired behaviour.
Some explains in regression tests shifted. So, I've made additional tests:

DROP TABLE test CASCADE;
CREATE TABLE test (a int, b int not null);
CREATE UNIQUE INDEX abc ON test(b);
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b;
CREATE UNIQUE INDEX abc1 ON test(a,b);
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b;
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a);
DROP INDEX abc1;
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b);

We have almost the results we wanted to have. But in the last explain
you can see that nothing happened with the OR clause. We should use the
expression mutator instead of walker to handle such clauses. But It
doesn't process the RestrictInfo node ... I'm inclined to put a solution
of this issue off for a while.


OK.  I think it doesn't worth to eliminate IS NULL quals with this
complexity (at least at this stage of work).

I made improvements over the code.  Mostly new comments, grammar
corrections of existing comments and small refactoring.

Also, I found that the  suggestion from David Rowley [1] to qsort
array of relations to faster find duplicates is still unaddressed.
I've implemented it.  That helps to evade quadratic complexity with
large number of relations.

Also I've incorporated improvements from Alena Rybakina except one for
skipping SJ removal when no SJ quals is found.  It's not yet clear for
me if this check fix some cases. But at least optimization got skipped
in some useful cases (as you can see in regression tests).


I would like to propose one more minor improvement (see in attachment).
The idea here is that after removing a self-join and changing clauses we
should re-probe the set of relids with the same Oid, because we can find
more removable self-joins (see the demo test in join.sql).



Thank you, I've integrated this into the patch.  BTW, the patch
introduces two new GUC variables: enable_self_join_removal,
self_join_search_limit.  enable_self_join_removal variable turns
on/off optimization at all.  self_join_search_limit variable limits
its usage by the number of joins.  AFICS, self_join_search_limit is
intended to protect us from quadratic complexity self-join removal
has.  I tried to reproduce the extreme case.

SELECT count(*) FROM pgbench_accounts a0, pgbench_accounts a1, ...,
pgbench_accounts a100 WHERE a0.aid = 1 AND a1.aid = a0.aid + 1 AND ...
AND a100.aid = a99.aid + 1;

This query took 3778.432 ms with self-join removal disabled, and
3756.009 ms with self-join removal enabled.  So, no measurable
overhead.  Similar to the higher number of joins.  Can you imagine
some extreme case when self-join removal could introduce significant
overhead in comparison with other optimizer parts?  If not, should we
remove self_join_search_limit GUC?

Thanks,
It was Zhihong Yu who worried about that case [1]. And my purpose was to 
show a method to avoid such a problem if it would be needed.
I guess the main idea here is that we have a lot of self-joins, but only 
few of them (or no one) can be removed.
I can't imagine a practical situation when we can be stuck in the 
problems here. So, I vote to remove this GUC.



[1] 
https://www.postgresql.org/message-id/CALNJ-vTyL-LpvSOPZxpC63Et3LJLUAFZSfRqGEhT5Rj7_EEj7w%40mail.gmail.com


--
regards,
Andrey Lepikhov
Postgres Professional

Re: Removing unneeded self joins

[Alexander Korotkov]

On Mon, Oct 16, 2023 at 11:28 AM Andrei Lepikhov
 wrote:
> On 12/10/2023 18:32, Alexander Korotkov wrote:
> > On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov
> >  wrote:
> >> On 4/10/2023 14:34, Alexander Korotkov wrote:
> >>>   > Relid replacement machinery is the most contradictory code here. We 
> >>> used
> >>>   > a utilitarian approach and implemented a simplistic variant.
> >>>
> >>>   > > 2) It would be nice to skip the insertion of IS NOT NULL checks when
> >>>   > > they are not necessary.  [1] points that infrastructure from [2] 
> >>> might
> >>>   > > be useful.  The patchset from [2] seems committed mow.  However, I
> >>>   > > can't see it is directly helpful in this matter.  Could we just skip
> >>>   > > adding IS NOT NULL clause for the columns, that have
> >>>   > > pg_attribute.attnotnull set?
> >>>   > Thanks for the links, I will look into that case.
> >> To be more precise, in the attachment, you can find a diff to the main
> >> patch, which shows the volume of changes to achieve the desired behaviour.
> >> Some explains in regression tests shifted. So, I've made additional tests:
> >>
> >> DROP TABLE test CASCADE;
> >> CREATE TABLE test (a int, b int not null);
> >> CREATE UNIQUE INDEX abc ON test(b);
> >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
> >> WHERE t1.b=t2.b;
> >> CREATE UNIQUE INDEX abc1 ON test(a,b);
> >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
> >> WHERE t1.b=t2.b;
> >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
> >> WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a);
> >> DROP INDEX abc1;
> >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
> >> WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b);
> >>
> >> We have almost the results we wanted to have. But in the last explain
> >> you can see that nothing happened with the OR clause. We should use the
> >> expression mutator instead of walker to handle such clauses. But It
> >> doesn't process the RestrictInfo node ... I'm inclined to put a solution
> >> of this issue off for a while.
> >
> > OK.  I think it doesn't worth to eliminate IS NULL quals with this
> > complexity (at least at this stage of work).
> >
> > I made improvements over the code.  Mostly new comments, grammar
> > corrections of existing comments and small refactoring.
> >
> > Also, I found that the  suggestion from David Rowley [1] to qsort
> > array of relations to faster find duplicates is still unaddressed.
> > I've implemented it.  That helps to evade quadratic complexity with
> > large number of relations.
> >
> > Also I've incorporated improvements from Alena Rybakina except one for
> > skipping SJ removal when no SJ quals is found.  It's not yet clear for
> > me if this check fix some cases. But at least optimization got skipped
> > in some useful cases (as you can see in regression tests).
>
> I would like to propose one more minor improvement (see in attachment).
> The idea here is that after removing a self-join and changing clauses we
> should re-probe the set of relids with the same Oid, because we can find
> more removable self-joins (see the demo test in join.sql).


Thank you, I've integrated this into the patch.  BTW, the patch
introduces two new GUC variables: enable_self_join_removal,
self_join_search_limit.  enable_self_join_removal variable turns
on/off optimization at all.  self_join_search_limit variable limits
its usage by the number of joins.  AFICS, self_join_search_limit is
intended to protect us from quadratic complexity self-join removal
has.  I tried to reproduce the extreme case.

SELECT count(*) FROM pgbench_accounts a0, pgbench_accounts a1, ...,
pgbench_accounts a100 WHERE a0.aid = 1 AND a1.aid = a0.aid + 1 AND ...
AND a100.aid = a99.aid + 1;

This query took 3778.432 ms with self-join removal disabled, and
3756.009 ms with self-join removal enabled.  So, no measurable
overhead.  Similar to the higher number of joins.  Can you imagine
some extreme case when self-join removal could introduce significant
overhead in comparison with other optimizer parts?  If not, should we
remove self_join_search_limit GUC?

--
Regards,
Alexander Korotkov


0001-Remove-useless-self-joins-v45.patch
Description: Binary data

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 12/10/2023 18:32, Alexander Korotkov wrote:

On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov
 wrote:

On 4/10/2023 14:34, Alexander Korotkov wrote:

  > Relid replacement machinery is the most contradictory code here. We used
  > a utilitarian approach and implemented a simplistic variant.

  > > 2) It would be nice to skip the insertion of IS NOT NULL checks when
  > > they are not necessary.  [1] points that infrastructure from [2] might
  > > be useful.  The patchset from [2] seems committed mow.  However, I
  > > can't see it is directly helpful in this matter.  Could we just skip
  > > adding IS NOT NULL clause for the columns, that have
  > > pg_attribute.attnotnull set?
  > Thanks for the links, I will look into that case.

To be more precise, in the attachment, you can find a diff to the main
patch, which shows the volume of changes to achieve the desired behaviour.
Some explains in regression tests shifted. So, I've made additional tests:

DROP TABLE test CASCADE;
CREATE TABLE test (a int, b int not null);
CREATE UNIQUE INDEX abc ON test(b);
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b;
CREATE UNIQUE INDEX abc1 ON test(a,b);
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b;
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a);
DROP INDEX abc1;
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b);

We have almost the results we wanted to have. But in the last explain
you can see that nothing happened with the OR clause. We should use the
expression mutator instead of walker to handle such clauses. But It
doesn't process the RestrictInfo node ... I'm inclined to put a solution
of this issue off for a while.


OK.  I think it doesn't worth to eliminate IS NULL quals with this
complexity (at least at this stage of work).

I made improvements over the code.  Mostly new comments, grammar
corrections of existing comments and small refactoring.

Also, I found that the  suggestion from David Rowley [1] to qsort
array of relations to faster find duplicates is still unaddressed.
I've implemented it.  That helps to evade quadratic complexity with
large number of relations.

Also I've incorporated improvements from Alena Rybakina except one for
skipping SJ removal when no SJ quals is found.  It's not yet clear for
me if this check fix some cases. But at least optimization got skipped
in some useful cases (as you can see in regression tests).


I would like to propose one more minor improvement (see in attachment). 
The idea here is that after removing a self-join and changing clauses we 
should re-probe the set of relids with the same Oid, because we can find 
more removable self-joins (see the demo test in join.sql).


--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/plan/analyzejoins.c 
b/src/backend/optimizer/plan/analyzejoins.c
index 7b8dc7a2b7..f7ccda5231 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -2298,6 +2298,7 @@ remove_self_joins_recurse(PlannerInfo *root, List 
*joinlist, Relids toRemove)
{
/* Create group of relation indexes with the 
same oid */
Relids  group = NULL;
+   Relids  removed;
 
while (i < j)
{
@@ -2306,8 +2307,21 @@ remove_self_joins_recurse(PlannerInfo *root, List 
*joinlist, Relids toRemove)
}
 
relids = bms_del_members(relids, group);
-   toRemove = bms_add_members(toRemove,
-   
remove_self_joins_one_group(root, group));
+
+   /*
+* Try to remove self-joins from a group of 
identical entries.
+* Make next attempt iteratively - if something 
is deleted from
+* a group, changes in clauses and equivalence 
classes can give
+* us a chance to find more candidates.
+*/
+   do {
+   Assert(!bms_overlap(group, toRemove));
+   removed = 
remove_self_joins_one_group(root, group);
+   toRemove = bms_add_members(toRemove, 
removed);
+   group = bms_del_members(group, removed);
+   } while (!bms_is_empty(removed) &&
+bms_membership(group) == 
BMS_MULTIPLE);
+   bms_free(removed);
bms_free(group);
   

Re: Removing unneeded self joins

[a.rybakina]

On 13.10.2023 12:03, Andrei Lepikhov wrote:

On 13/10/2023 15:56, a.rybakina wrote:



Also I've incorporated improvements from Alena Rybakina except one for
skipping SJ removal when no SJ quals is found.  It's not yet clear for
me if this check fix some cases. But at least optimization got skipped
in some useful cases (as you can see in regression tests).


Agree. I wouldn't say I like it too. But also, I suggest skipping 
some unnecessary assertions proposed in that patch:
Assert(toKeep->relid != -1); - quite strange. Why -1? Why not all 
the negative numbers, at least?
Assert(is_opclause(orinfo->clause)); - above we skip clauses with 
rinfo->mergeopfamilies == NIL. Each mergejoinable clause is already 
checked as is_opclause.

All these changes (see in the attachment) are optional.

I don't mind about asserts, maybe I misunderstood something in the 
patch.


About skipping SJ removal when no SJ quals is found, I assume it is 
about it:


split_selfjoin_quals(root, restrictlist, &selfjoinquals,
                               &otherjoinquals, inner->relid, 
outer->relid);


+            if (list_length(selfjoinquals) == 0)
+             {
+                 /*
+                  * XXX:
+                  * we would detect self-join without quals like 
'x==x' if we had
+                  * an foreign key constraint on some of other quals 
and this join
+                  * haven't any columns from the outer in the target 
list.

+                  * But it is still complex task.
+                  */
+                 continue;
+             }

as far as I remember, this is the place where it is checked that the 
SJ list is empty and it is logical, in my opinion, that no 
transformations should be performed if no elements are found for them.
You forget we have "Degenerate" case, as Alexander mentioned above. 
What if you have something like that:

SELECT ... FROM A a1, A a2 WHERE a1.id=1 AND a2.id=1;
In this case, uniqueness can be achieved by the baserestrictinfo 
"A.id=1", if we have an unique index on this column.



Yes, sorry, I missed it. thanks again for the explanation 🙂

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 13/10/2023 15:56, a.rybakina wrote:



Also I've incorporated improvements from Alena Rybakina except one for
skipping SJ removal when no SJ quals is found.  It's not yet clear for
me if this check fix some cases. But at least optimization got skipped
in some useful cases (as you can see in regression tests).


Agree. I wouldn't say I like it too. But also, I suggest skipping some 
unnecessary assertions proposed in that patch:
Assert(toKeep->relid != -1); - quite strange. Why -1? Why not all the 
negative numbers, at least?
Assert(is_opclause(orinfo->clause)); - above we skip clauses with 
rinfo->mergeopfamilies == NIL. Each mergejoinable clause is already 
checked as is_opclause.

All these changes (see in the attachment) are optional.


I don't mind about asserts, maybe I misunderstood something in the patch.

About skipping SJ removal when no SJ quals is found, I assume it is 
about it:


split_selfjoin_quals(root, restrictlist, &selfjoinquals,
                               &otherjoinquals, inner->relid, 
outer->relid);


+            if (list_length(selfjoinquals) == 0)
+             {
+                 /*
+                  * XXX:
+                  * we would detect self-join without quals like 'x==x' 
if we had
+                  * an foreign key constraint on some of other quals 
and this join

+                  * haven't any columns from the outer in the target list.
+                  * But it is still complex task.
+                  */
+                 continue;
+             }

as far as I remember, this is the place where it is checked that the SJ 
list is empty and it is logical, in my opinion, that no transformations 
should be performed if no elements are found for them.
You forget we have "Degenerate" case, as Alexander mentioned above. What 
if you have something like that:

SELECT ... FROM A a1, A a2 WHERE a1.id=1 AND a2.id=1;
In this case, uniqueness can be achieved by the baserestrictinfo 
"A.id=1", if we have an unique index on this column.


--
regards,
Andrey Lepikhov
Postgres Professional

Re: Removing unneeded self joins

[a.rybakina]

Also I've incorporated improvements from Alena Rybakina except one for
skipping SJ removal when no SJ quals is found.  It's not yet clear for
me if this check fix some cases. But at least optimization got skipped
in some useful cases (as you can see in regression tests).


Agree. I wouldn't say I like it too. But also, I suggest skipping some 
unnecessary assertions proposed in that patch:
Assert(toKeep->relid != -1); - quite strange. Why -1? Why not all the 
negative numbers, at least?
Assert(is_opclause(orinfo->clause)); - above we skip clauses with 
rinfo->mergeopfamilies == NIL. Each mergejoinable clause is already 
checked as is_opclause.

All these changes (see in the attachment) are optional.


I don't mind about asserts, maybe I misunderstood something in the patch.

About skipping SJ removal when no SJ quals is found, I assume it is 
about it:


split_selfjoin_quals(root, restrictlist, &selfjoinquals,
                              &otherjoinquals, inner->relid, 
outer->relid);


+            if (list_length(selfjoinquals) == 0)
+             {
+                 /*
+                  * XXX:
+                  * we would detect self-join without quals like 'x==x' 
if we had
+                  * an foreign key constraint on some of other quals 
and this join

+                  * haven't any columns from the outer in the target list.
+                  * But it is still complex task.
+                  */
+                 continue;
+             }

as far as I remember, this is the place where it is checked that the SJ 
list is empty and it is logical, in my opinion, that no transformations 
should be performed if no elements are found for them.


As for the cases where SJ did not work, maybe this is just right if 
there are no elements for processing these cases. I'll try to check or 
come up with tests for them. If I'm wrong, write.


On 11.10.2023 06:51, Andrei Lepikhov wrote:

On 11/10/2023 02:29, Alena Rybakina wrote:

I have reviewed your patch and I noticed a few things.


Thanks for your efforts,

I have looked at the latest version of the code, I assume that the 
error lies in the replace_varno_walker function, especially in the 
place where we check the node by type Var, and does not form any 
NullTest node.


It's not a bug, it's an optimization we discussed with Alexander above.

Secondly, I added some code in some places to catch erroneous cases 
and added a condition when we should not try to apply the 
self-join-removal transformation due to the absence of an empty 
self-join list after searching for it and in general if there are no 
joins in the query. Besides, I added a query for testing and wrote 
about it above. I have attached my diff file.

Ok, I will look at this
In addition, I found a comment for myself that was not clear to me. I 
would be glad if you could explain it to me.


You mentioned superior outer join in the comment, unfortunately, I 
didn't find anything about it in the PostgreSQL code, and this 
explanation remained unclear to me. Could you explain in more detail 
what you meant?
I meant here that only clauses pushed by 
reconsider_outer_join_clauses() can be found in the joininfo list, and 
they are not relevant, as you can understand.
Having written that, I realized that it was a false statement. ;) - 
joininfo can also contain results of previous SJE iterations, look:


CREATE TABLE test (oid int PRIMARY KEY);
CREATE UNIQUE INDEX ON test((oid*oid));
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c1.oid=c2.oid AND c1.oid*c2.oid=c3.oid*c3.oid;
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c1.oid=c3.oid AND c1.oid*c3.oid=c2.oid*c2.oid;
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c3.oid=c2.oid AND c3.oid*c2.oid=c1.oid*c1.oid; 


Ok, I understood. Thank you for explanation.


--
Regards,
Alena Rybakina

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 12/10/2023 18:32, Alexander Korotkov wrote:

On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov

We have almost the results we wanted to have. But in the last explain
you can see that nothing happened with the OR clause. We should use the
expression mutator instead of walker to handle such clauses. But It
doesn't process the RestrictInfo node ... I'm inclined to put a solution
of this issue off for a while.


OK.  I think it doesn't worth to eliminate IS NULL quals with this
complexity (at least at this stage of work).


Yeah. I think It would be meaningful in the case of replacing also 
nested x IS NOT NULL with nothing. But it requires using a mutator 
instead of the walker and may be done more accurately next time.



I made improvements over the code.  Mostly new comments, grammar
corrections of existing comments and small refactoring.


Great!


Also, I found that the  suggestion from David Rowley [1] to qsort
array of relations to faster find duplicates is still unaddressed.
I've implemented it.  That helps to evade quadratic complexity with
large number of relations.


I see. The thread is too long so far, thanks for the catch.


Also I've incorporated improvements from Alena Rybakina except one for
skipping SJ removal when no SJ quals is found.  It's not yet clear for
me if this check fix some cases. But at least optimization got skipped
in some useful cases (as you can see in regression tests).


Agree. I wouldn't say I like it too. But also, I suggest skipping some 
unnecessary assertions proposed in that patch:
Assert(toKeep->relid != -1); - quite strange. Why -1? Why not all the 
negative numbers, at least?
Assert(is_opclause(orinfo->clause)); - above we skip clauses with 
rinfo->mergeopfamilies == NIL. Each mergejoinable clause is already 
checked as is_opclause.

All these changes (see in the attachment) are optional.

--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/plan/analyzejoins.c 
b/src/backend/optimizer/plan/analyzejoins.c
index f0746f35a3..7b8dc7a2b7 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -1710,8 +1710,6 @@ remove_self_join_rel(PlannerInfo *root, PlanRowMark 
*kmark, PlanRowMark *rmark,
List   *binfo_candidates = NIL;
ReplaceVarnoContext ctx = {.from = toRemove->relid,.to = toKeep->relid};
 
-   Assert(toKeep->relid != -1);
-
/*
 * Replace index of removing table with the keeping one. The technique 
of
 * removing/distributing restrictinfo is used here to attach just 
appeared
@@ -2017,8 +2015,6 @@ match_unique_clauses(PlannerInfo *root, RelOptInfo 
*outer, List *uclauses,
/* Don't consider clauses which aren't similar 
to 'F(X)=G(Y)' */
continue;
 
-   Assert(is_opclause(orinfo->clause));
-
oclause = bms_is_empty(orinfo->left_relids) ?
get_rightop(orinfo->clause) : 
get_leftop(orinfo->clause);
c2 = (bms_is_empty(orinfo->left_relids) ?
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 2ff4881fdf..96ebd6eed3 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -367,7 +367,6 @@ CatalogId
 CatalogIdMapEntry
 CatalogIndexState
 ChangeVarNodes_context
-ReplaceVarnoContext
 CheckPoint
 CheckPointStmt
 CheckpointStatsData
@@ -2341,6 +2340,7 @@ ReorderBufferUpdateProgressTxnCB
 ReorderTuple
 RepOriginId
 ReparameterizeForeignPathByChild_function
+ReplaceVarnoContext
 ReplaceVarsFromTargetList_context
 ReplaceVarsNoMatchOption
 ReplicaIdentityStmt
@@ -2474,6 +2474,7 @@ SeenRelsEntry
 SelectLimit
 SelectStmt
 Selectivity
+SelfJoinCandidate
 SemTPadded
 SemiAntiJoinFactors
 SeqScan

Re: Removing unneeded self joins

[Alexander Korotkov]

On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov
 wrote:
> On 4/10/2023 14:34, Alexander Korotkov wrote:
> >  > Relid replacement machinery is the most contradictory code here. We used
> >  > a utilitarian approach and implemented a simplistic variant.
> >
> >  > > 2) It would be nice to skip the insertion of IS NOT NULL checks when
> >  > > they are not necessary.  [1] points that infrastructure from [2] might
> >  > > be useful.  The patchset from [2] seems committed mow.  However, I
> >  > > can't see it is directly helpful in this matter.  Could we just skip
> >  > > adding IS NOT NULL clause for the columns, that have
> >  > > pg_attribute.attnotnull set?
> >  > Thanks for the links, I will look into that case.
> To be more precise, in the attachment, you can find a diff to the main
> patch, which shows the volume of changes to achieve the desired behaviour.
> Some explains in regression tests shifted. So, I've made additional tests:
>
> DROP TABLE test CASCADE;
> CREATE TABLE test (a int, b int not null);
> CREATE UNIQUE INDEX abc ON test(b);
> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
> WHERE t1.b=t2.b;
> CREATE UNIQUE INDEX abc1 ON test(a,b);
> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
> WHERE t1.b=t2.b;
> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
> WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a);
> DROP INDEX abc1;
> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
> WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b);
>
> We have almost the results we wanted to have. But in the last explain
> you can see that nothing happened with the OR clause. We should use the
> expression mutator instead of walker to handle such clauses. But It
> doesn't process the RestrictInfo node ... I'm inclined to put a solution
> of this issue off for a while.

OK.  I think it doesn't worth to eliminate IS NULL quals with this
complexity (at least at this stage of work).

I made improvements over the code.  Mostly new comments, grammar
corrections of existing comments and small refactoring.

Also, I found that the  suggestion from David Rowley [1] to qsort
array of relations to faster find duplicates is still unaddressed.
I've implemented it.  That helps to evade quadratic complexity with
large number of relations.

Also I've incorporated improvements from Alena Rybakina except one for
skipping SJ removal when no SJ quals is found.  It's not yet clear for
me if this check fix some cases. But at least optimization got skipped
in some useful cases (as you can see in regression tests).

Links
1. 
https://www.postgresql.org/message-id/CAKJS1f8ySSsBfooH3bJK7OD3LBEbDb99d8J_FtqDd6w50p-eAQ%40mail.gmail.com
2. 
https://www.postgresql.org/message-id/96f66ae3-df10-4060-9844-4c9633062cd3%40yandex.ru

--
Regards,
Alexander Korotkov


0001-Remove-useless-self-joins-v44.patch
Description: Binary data

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 11/10/2023 02:29, Alena Rybakina wrote:

I have reviewed your patch and I noticed a few things.


Thanks for your efforts,

I have looked at the latest version of the code, I assume that the error 
lies in the replace_varno_walker function, especially in the place where 
we check the node by type Var, and does not form any NullTest node.


It's not a bug, it's an optimization we discussed with Alexander above.

Secondly, I added some code in some places to catch erroneous cases and 
added a condition when we should not try to apply the self-join-removal 
transformation due to the absence of an empty self-join list after 
searching for it and in general if there are no joins in the query. 
Besides, I added a query for testing and wrote about it above. I have 
attached my diff file.

Ok, I will look at this
In addition, I found a comment for myself that was not clear to me. I 
would be glad if you could explain it to me.


You mentioned superior outer join in the comment, unfortunately, I 
didn't find anything about it in the PostgreSQL code, and this 
explanation remained unclear to me. Could you explain in more detail 
what you meant?
I meant here that only clauses pushed by reconsider_outer_join_clauses() 
can be found in the joininfo list, and they are not relevant, as you can 
understand.
Having written that, I realized that it was a false statement. ;) - 
joininfo can also contain results of previous SJE iterations, look:


CREATE TABLE test (oid int PRIMARY KEY);
CREATE UNIQUE INDEX ON test((oid*oid));
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c1.oid=c2.oid AND c1.oid*c2.oid=c3.oid*c3.oid;
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c1.oid=c3.oid AND c1.oid*c3.oid=c2.oid*c2.oid;
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c3.oid=c2.oid AND c3.oid*c2.oid=c1.oid*c1.oid;

Having executed this SQL code, you could see that in the last query, the 
SJE feature didn't delete one of the JOINs because of the reason I had 
written above.

It's not an one-minute fix - I will try to propose solution a bit later.

--
regards,
Andrey Lepikhov
Postgres Professional

Re: Removing unneeded self joins

[Alena Rybakina]

Hi!

I have reviewed your patch and I noticed a few things.

First of all, I think I found a bug in your latest patch version, and 
this query shows it:


EXPLAIN (COSTS OFF)
SELECT c.oid, e.oid FROM pg_class c FULL JOIN (
  SELECT e1.oid FROM pg_extension e1, pg_extension e2
  WHERE e1.oid=e2.oid) AS e
  ON c.oid=e.oid;

In the current version we get such a query plan:

   QUERY PLAN
-
 Hash Full Join
   Hash Cond: (c.oid = e2.oid)
   ->  Seq Scan on pg_class c
   ->  Hash
 ->  Seq Scan on pg_extension e2
(5 rows)

But I think it should be:

QUERY PLAN
-
Hash Full Join
Hash Cond: (c.oid = e2.oid)
-> Seq Scan on pg_class c
-> Hash
-> Seq Scan on pg_extension e2
*Filter: (oid IS NOT NULL)*
(6 rows)

I have looked at the latest version of the code, I assume that the error 
lies in the replace_varno_walker function, especially in the place where 
we check the node by type Var, and does not form any NullTest node.


if (OidIsValid(reloid) && get_attnotnull(reloid, attnum)) -- this 
condition works

    {
  rinfo->clause = (Expr *) makeBoolConst(true, false);
    }
    else
    {
  NullTest   *ntest = makeNode(NullTest);

  ntest->arg = leftOp;
  ntest->nulltesttype = IS_NOT_NULL;
  ntest->argisrow = false;
  ntest->location = -1;
  rinfo->clause = (Expr *) ntest;
    }


Secondly, I added some code in some places to catch erroneous cases and 
added a condition when we should not try to apply the self-join-removal 
transformation due to the absence of an empty self-join list after 
searching for it and in general if there are no joins in the query. 
Besides, I added a query for testing and wrote about it above. I have 
attached my diff file.



In addition, I found a comment for myself that was not clear to me. I 
would be glad if you could explain it to me.


You mentioned superior outer join in the comment, unfortunately, I 
didn't find anything about it in the PostgreSQL code, and this 
explanation remained unclear to me. Could you explain in more detail 
what you meant?


/*
 * At this stage joininfo lists of inner and outer can contain
 * only clauses, required for *a superior outer join* that can't
 * influence on this optimization. So, we can avoid to call the
 * build_joinrel_restrictlist() routine.
*/
 restrictlist = generate_join_implied_equalities(root, joinrelids,
  inner->relids,
  outer, NULL);

--

Regards,
Alena Rybakina
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 3e10083905c..5ba5ca693f1 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -1704,6 +1704,8 @@ remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark,
 	List			   *binfo_candidates = NIL;
 	ReplaceVarnoContext	ctx = {.from = toRemove->relid, .to = toKeep->relid};
 
+	Assert(toKeep->relid != -1);
+
 	/*
 	 * Replace index of removing table with the keeping one. The technique of
 	 * removing/distributing restrictinfo is used here to attach just appeared
@@ -2007,6 +2009,8 @@ match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses,
 /* Don't consider clauses which aren't similar to 'F(X)=G(Y)' */
 continue;
 
+			Assert(is_opclause(orinfo->clause));
+
 			oclause = bms_is_empty(orinfo->left_relids) ?
 	get_rightop(orinfo->clause) : get_leftop(orinfo->clause);
 			c2 = (bms_is_empty(orinfo->left_relids) ?
@@ -2150,6 +2154,18 @@ remove_self_joins_one_group(PlannerInfo *root, Relids relids)
 			split_selfjoin_quals(root, restrictlist, &selfjoinquals,
  &otherjoinquals, inner->relid, outer->relid);
 
+			if (list_length(selfjoinquals) == 0)
+ 			{
+ /*
+  * XXX:
+  * we would detect self-join without quals like 'x==x' if we had
+  * an foreign key constraint on some of other quals and this join
+  * haven't any columns from the outer in the target list.
+  * But it is still complex task.
+  */
+ continue;
+ 			}
+
 			/*
 			 * To enable SJE for the only degenerate case without any self join
 			 * clauses at all, add baserestrictinfo to this list.
@@ -2332,7 +2348,7 @@ remove_useless_self_joins(PlannerInfo *root, List *joinlist)
 	Relids	ToRemove = NULL;
 	int		relid = -1;
 
-	if (!enable_self_join_removal)
+	if ((list_length(joinlist) <=1 && !IsA(linitial(joinlist), List)) || !enable_self_join_removal)
 		return joinlist;
 
 	/*
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 10b23944feb..800410d6b18 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -5807,13 +5807,11 @@ explain (costs off)
 select p.* from
   (parent p left join child c on (p.k = c.k)) join parent x on p.k = x.k
   where p.k = 1 and p.k = 2;
-

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 4/10/2023 14:34, Alexander Korotkov wrote:

 > Relid replacement machinery is the most contradictory code here. We used
 > a utilitarian approach and implemented a simplistic variant.

 > > 2) It would be nice to skip the insertion of IS NOT NULL checks when
 > > they are not necessary.  [1] points that infrastructure from [2] might
 > > be useful.  The patchset from [2] seems committed mow.  However, I
 > > can't see it is directly helpful in this matter.  Could we just skip
 > > adding IS NOT NULL clause for the columns, that have
 > > pg_attribute.attnotnull set?
 > Thanks for the links, I will look into that case.
To be more precise, in the attachment, you can find a diff to the main 
patch, which shows the volume of changes to achieve the desired behaviour.

Some explains in regression tests shifted. So, I've made additional tests:

DROP TABLE test CASCADE;
CREATE TABLE test (a int, b int not null);
CREATE UNIQUE INDEX abc ON test(b);
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b;
CREATE UNIQUE INDEX abc1 ON test(a,b);
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b;
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a);
DROP INDEX abc1;
explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b);

We have almost the results we wanted to have. But in the last explain 
you can see that nothing happened with the OR clause. We should use the 
expression mutator instead of walker to handle such clauses. But It 
doesn't process the RestrictInfo node ... I'm inclined to put a solution 
of this issue off for a while.


--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/plan/analyzejoins.c 
b/src/backend/optimizer/plan/analyzejoins.c
index a127239d30..c12aa15fc9 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -73,7 +73,7 @@ static bool is_innerrel_unique_for(PlannerInfo *root,
   List 
*restrictlist,
   List 
**extra_clauses);
 static Bitmapset *replace_relid(Relids relids, int oldId, int newId);
-static void replace_varno(Node *node, int from, int to);
+static void replace_varno(PlannerInfo *root, Node *node, int from, int to);
 
 
 /*
@@ -388,7 +388,7 @@ remove_rel_from_query_common(PlannerInfo *root, RelOptInfo 
*rel,
}
 
/* Update lateral references. */
-   replace_varno((Node *) otherrel->lateral_vars, relid, subst);
+   replace_varno(root, (Node *) otherrel->lateral_vars, relid, 
subst);
}
 
/*
@@ -425,7 +425,7 @@ remove_rel_from_query_common(PlannerInfo *root, RelOptInfo 
*rel,
sjinf->commute_below_l = replace_relid(sjinf->commute_below_l, 
ojrelid, subst);
sjinf->commute_below_r = replace_relid(sjinf->commute_below_r, 
ojrelid, subst);
 
-   replace_varno((Node *) sjinf->semi_rhs_exprs, relid, subst);
+   replace_varno(root, (Node *) sjinf->semi_rhs_exprs, relid, 
subst);
}
 
/*
@@ -1399,6 +1399,7 @@ is_innerrel_unique_for(PlannerInfo *root,
 
 typedef struct ReplaceVarnoContext
 {
+   PlannerInfo *root;
int from;
int to;
 } ReplaceVarnoContext;
@@ -1420,6 +1421,11 @@ replace_varno_walker(Node *node, ReplaceVarnoContext 
*ctx)
}
return false;
}
+
+   /*
+* Expression walker doesn't know about RestrictInfo node. Do recursive 
pass
+* into the clauses manually.
+*/
if (IsA(node, RestrictInfo))
{
RestrictInfo   *rinfo = (RestrictInfo *) node;
@@ -1429,20 +1435,26 @@ replace_varno_walker(Node *node, ReplaceVarnoContext 
*ctx)
 
if (bms_is_member(ctx->from, rinfo->clause_relids))
{
-   replace_varno((Node *) rinfo->clause, ctx->from, 
ctx->to);
-   replace_varno((Node *) rinfo->orclause, ctx->from, 
ctx->to);
-   rinfo->clause_relids = 
replace_relid(rinfo->clause_relids, ctx->from, ctx->to);
-   rinfo->left_relids = replace_relid(rinfo->left_relids, 
ctx->from, ctx->to);
-   rinfo->right_relids = 
replace_relid(rinfo->right_relids, ctx->from, ctx->to);
+   replace_varno(ctx->root, (Node *) rinfo->clause, 
ctx->from, ctx->to);
+   replace_varno(ctx->root, (Node *) rinfo->orclause, 
ctx->from, ctx->to);
+   rinfo->clause_relids =
+   
replace_relid(rinfo->clause_relids, ctx->from, ctx->to);
+   rinfo->left_relids =
+   
replace_relid(rinfo->left_relids, ctx->from, ctx->to);
+

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 4/10/2023 14:34, Alexander Korotkov wrote:

Hi!

On Wed, Oct 4, 2023 at 9:56 AM Andrei Lepikhov 
mailto:a.lepik...@postgrespro.ru>> wrote:

 > On 4/10/2023 07:12, Alexander Korotkov wrote:
 > > On Tue, Sep 12, 2023 at 4:58 PM Andrey Lepikhov
 > > mailto:a.lepik...@postgrespro.ru>> wrote:
 > >> On 5/7/2023 21:28, Andrey Lepikhov wrote:
 > >>> During the significant code revision in v.41 I lost some replacement
 > >>> operations. Here is the fix and extra tests to check this in the 
future.

 > >>> Also, Tom added the JoinDomain structure five months ago, and I added
 > >>> code to replace relids for that place too.
 > >>> One more thing, I found out that we didn't replace SJs, defined by
 > >>> baserestrictinfos if no one self-join clause have existed for the 
join.

 > >>> Now, it is fixed, and the test has been added.
 > >>> To understand changes readily, see the delta file in the attachment.
 > >> Here is new patch in attachment. Rebased on current master and some
 > >> minor gaffes are fixed.
 > >
 > > I went through the thread and I think the patch gets better shape.  A
 > > couple of notes from my side.
 > > 1) Why replace_relid() makes a copy of lids only on insert/replace of
 > > a member, but performs deletion in-place?
 >
 > Shortly speaking, it was done according to the 'Paranoid' strategy.
 > The main reason for copying before deletion was the case with the rinfo
 > required_relids and clause_relids. They both point to the same Bitmapset
 > in some cases. And we feared such things for other fields.
 > Right now, it may be redundant because we resolved the issue mentioned
 > above in replace_varno_walker.

OK, but my point is still that you should be paranoid in all the cases 
or none of the cases.  Right now (newId < 0) branch doesn't copy source 
relids, but bms_is_member(oldId, relids) does copy.  Also, I think 
whether we copy or not should be reflected in the function comment.


/*
  * Substitute newId by oldId in relids.
  */
static Bitmapset *
replace_relid(Relids relids, int oldId, int newId)
{
     if (oldId < 0)
         return relids;

     if (newId < 0)
         /* Delete relid without substitution. */
         return bms_del_member(relids, oldId);

     if (bms_is_member(oldId, relids))
         return bms_add_member(bms_del_member(bms_copy(relids), oldId), 
newId);


     return relids;
}


We tried to use replace_relid() for both cases of JOIN deletion: 
unneeded outer join and self-join, and the relid deletion is used only 
in the first case. Such an approach was used there for a long time, and 
we just didn't change it.

I am prone to removing the copy operation in the code of relid replacement.



 > Relid replacement machinery is the most contradictory code here. We used
 > a utilitarian approach and implemented a simplistic variant.

 > > 2) It would be nice to skip the insertion of IS NOT NULL checks when
 > > they are not necessary.  [1] points that infrastructure from [2] might
 > > be useful.  The patchset from [2] seems committed mow.  However, I
 > > can't see it is directly helpful in this matter.  Could we just skip
 > > adding IS NOT NULL clause for the columns, that have
 > > pg_attribute.attnotnull set?
 > Thanks for the links, I will look into that case.

Thanks for the curious issue.
The new field Var::varnullingrels introduced in [2] doesn't make sense 
here, as I see: we operate with plain relations only, and I don't know 
how it can be applied to an arbitrary subtree contained OUTER JOINs.
The second option, the attnotnull flag, can be used in this code. We 
haven't implemented it because the process_equivalence routine doesn't 
check the attnotnull before creating NullTest.
In general, it is not a difficult operation - we just need to add a 
trivial get_attnotnull() routine to lssycache.c likewise 
get_attgenerated() and other functions.
But, replace_varno uses the walker to change the relid. The mentioned 
replacement, like

X=X --> X IS NOT NULL
can be applied on different levels of the expression, look:
A a1 JOIN A a2 ON (a1.id=a2.id) WHERE (a1.x AND (a1.y=a2.y))
Here, we can replace id=id and y=y. It may need some 'unwanted clauses' 
collection procedure and a second pass through the expression tree to 
remove them. It may add some unpredictable overhead.
We can replace such a clause with a trivial 'TRUE' clause, of course. 
But is it the feature you have requested?


--
regards,
Andrey Lepikhov
Postgres Professional

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi!

On Wed, Oct 4, 2023 at 9:56 AM Andrei Lepikhov 
wrote:
> On 4/10/2023 07:12, Alexander Korotkov wrote:
> > On Tue, Sep 12, 2023 at 4:58 PM Andrey Lepikhov
> >  wrote:
> >> On 5/7/2023 21:28, Andrey Lepikhov wrote:
> >>> During the significant code revision in v.41 I lost some replacement
> >>> operations. Here is the fix and extra tests to check this in the
future.
> >>> Also, Tom added the JoinDomain structure five months ago, and I added
> >>> code to replace relids for that place too.
> >>> One more thing, I found out that we didn't replace SJs, defined by
> >>> baserestrictinfos if no one self-join clause have existed for the
join.
> >>> Now, it is fixed, and the test has been added.
> >>> To understand changes readily, see the delta file in the attachment.
> >> Here is new patch in attachment. Rebased on current master and some
> >> minor gaffes are fixed.
> >
> > I went through the thread and I think the patch gets better shape.  A
> > couple of notes from my side.
> > 1) Why replace_relid() makes a copy of lids only on insert/replace of
> > a member, but performs deletion in-place?
>
> Shortly speaking, it was done according to the 'Paranoid' strategy.
> The main reason for copying before deletion was the case with the rinfo
> required_relids and clause_relids. They both point to the same Bitmapset
> in some cases. And we feared such things for other fields.
> Right now, it may be redundant because we resolved the issue mentioned
> above in replace_varno_walker.

OK, but my point is still that you should be paranoid in all the cases or
none of the cases.  Right now (newId < 0) branch doesn't copy source
relids, but bms_is_member(oldId, relids) does copy.  Also, I think whether
we copy or not should be reflected in the function comment.

/*
 * Substitute newId by oldId in relids.
 */
static Bitmapset *
replace_relid(Relids relids, int oldId, int newId)
{
if (oldId < 0)
return relids;

if (newId < 0)
/* Delete relid without substitution. */
return bms_del_member(relids, oldId);

if (bms_is_member(oldId, relids))
return bms_add_member(bms_del_member(bms_copy(relids), oldId),
newId);

return relids;
}

> Relid replacement machinery is the most contradictory code here. We used
> a utilitarian approach and implemented a simplistic variant.

> > 2) It would be nice to skip the insertion of IS NOT NULL checks when
> > they are not necessary.  [1] points that infrastructure from [2] might
> > be useful.  The patchset from [2] seems committed mow.  However, I
> > can't see it is directly helpful in this matter.  Could we just skip
> > adding IS NOT NULL clause for the columns, that have
> > pg_attribute.attnotnull set?
> Thanks for the links, I will look into that case.

OK, thank you.

--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Andrei Lepikhov]

On 4/10/2023 07:12, Alexander Korotkov wrote:

Hi!

Thanks for the review!


I think this is a neat optimization.

On Tue, Sep 12, 2023 at 4:58 PM Andrey Lepikhov
 wrote:

On 5/7/2023 21:28, Andrey Lepikhov wrote:

During the significant code revision in v.41 I lost some replacement
operations. Here is the fix and extra tests to check this in the future.
Also, Tom added the JoinDomain structure five months ago, and I added
code to replace relids for that place too.
One more thing, I found out that we didn't replace SJs, defined by
baserestrictinfos if no one self-join clause have existed for the join.
Now, it is fixed, and the test has been added.
To understand changes readily, see the delta file in the attachment.

Here is new patch in attachment. Rebased on current master and some
minor gaffes are fixed.


I went through the thread and I think the patch gets better shape.  A
couple of notes from my side.
1) Why replace_relid() makes a copy of lids only on insert/replace of
a member, but performs deletion in-place?


Shortly speaking, it was done according to the 'Paranoid' strategy.
The main reason for copying before deletion was the case with the rinfo 
required_relids and clause_relids. They both point to the same Bitmapset 
in some cases. And we feared such things for other fields.
Right now, it may be redundant because we resolved the issue mentioned 
above in replace_varno_walker.


Relid replacement machinery is the most contradictory code here. We used 
a utilitarian approach and implemented a simplistic variant.



2) It would be nice to skip the insertion of IS NOT NULL checks when
they are not necessary.  [1] points that infrastructure from [2] might
be useful.  The patchset from [2] seems committed mow.  However, I
can't see it is directly helpful in this matter.  Could we just skip
adding IS NOT NULL clause for the columns, that have
pg_attribute.attnotnull set?

Thanks for the links, I will look into that case.


Links
1. https://www.postgresql.org/message-id/2375492.jE0xQCEvom%40aivenronan
2.  https://www.postgresql.org/message-id/flat/830269.1656693747%40sss.pgh.pa.us


--
regards,
Andrey Lepikhov
Postgres Professional

Re: Removing unneeded self joins

[Alexander Korotkov]

Hi!

I think this is a neat optimization.

On Tue, Sep 12, 2023 at 4:58 PM Andrey Lepikhov
 wrote:
> On 5/7/2023 21:28, Andrey Lepikhov wrote:
> > During the significant code revision in v.41 I lost some replacement
> > operations. Here is the fix and extra tests to check this in the future.
> > Also, Tom added the JoinDomain structure five months ago, and I added
> > code to replace relids for that place too.
> > One more thing, I found out that we didn't replace SJs, defined by
> > baserestrictinfos if no one self-join clause have existed for the join.
> > Now, it is fixed, and the test has been added.
> > To understand changes readily, see the delta file in the attachment.
> Here is new patch in attachment. Rebased on current master and some
> minor gaffes are fixed.

I went through the thread and I think the patch gets better shape.  A
couple of notes from my side.
1) Why replace_relid() makes a copy of lids only on insert/replace of
a member, but performs deletion in-place?
2) It would be nice to skip the insertion of IS NOT NULL checks when
they are not necessary.  [1] points that infrastructure from [2] might
be useful.  The patchset from [2] seems committed mow.  However, I
can't see it is directly helpful in this matter.  Could we just skip
adding IS NOT NULL clause for the columns, that have
pg_attribute.attnotnull set?

Links
1. https://www.postgresql.org/message-id/2375492.jE0xQCEvom%40aivenronan
2.  https://www.postgresql.org/message-id/flat/830269.1656693747%40sss.pgh.pa.us


--
Regards,
Alexander Korotkov

Re: Removing unneeded self joins

[Andrey Lepikhov]

On 5/7/2023 21:28, Andrey Lepikhov wrote:

Hi,

During the significant code revision in v.41 I lost some replacement 
operations. Here is the fix and extra tests to check this in the future.
Also, Tom added the JoinDomain structure five months ago, and I added 
code to replace relids for that place too.
One more thing, I found out that we didn't replace SJs, defined by 
baserestrictinfos if no one self-join clause have existed for the join. 
Now, it is fixed, and the test has been added.

To understand changes readily, see the delta file in the attachment.
Here is new patch in attachment. Rebased on current master and some 
minor gaffes are fixed.


--
regards,
Andrey Lepikhov
Postgres Professional
From 70bb5cf3d11b2797f1a9c7b04740435135229d29 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" 
Date: Tue, 12 Sep 2023 18:25:51 +0700
Subject: [PATCH] Remove self-joins.

Self Join Elimination (SJE) feature removes an inner join of a plain table to
itself in the query tree if is proved that the join can be replaced with
a scan without impact to the query result.
Self join and inner relation are replaced with the outer in query, equivalence
classes and planner info structures. Also, inner restrictlist moves to the
outer one with removing duplicated clauses. Thus, this optimization reduces
length of range table list (especially it make sense for partitioned relations),
reduces number of restriction clauses === selectivity estimations and
potentially can improve total planner prediction for the query.

The SJE proof based on innerrel_is_unique machinery.

We can remove a self-join when for each outer row:
1. At most one inner row matches the join clause.
2. Each matched inner row must be (physically) the same row as the outer one.

In this patch we use the next approach to identify a self-join:
1. Collect all mergejoinable join quals which look like a.x = b.x
2. Add to the list above baseretrictinfo of inner table.
3. Check innerrel_is_unique() for the qual list. If it returns false, skip this
pair of joining tables.
4. Check uniqueness, proved by the baserestrictinfo clauses. To prove 
possibility
of the self-join elimination inner and outer clauses must have exact match.

Relation replacement procedure is not trivial and it is partly combined with 
the one,
used to remove useless left joins.

Tests, covering this feature, added to the join.sql.
Some regression tests changed due to self-join removal logic.
---
 doc/src/sgml/config.sgml  |   16 +
 src/backend/optimizer/path/indxpath.c |   38 +
 src/backend/optimizer/plan/analyzejoins.c | 1094 -
 src/backend/optimizer/plan/planmain.c |5 +
 src/backend/utils/misc/guc_tables.c   |   22 +
 src/include/optimizer/paths.h |3 +
 src/include/optimizer/planmain.h  |7 +
 src/test/regress/expected/equivclass.out  |   32 +
 src/test/regress/expected/join.out|  824 -
 src/test/regress/expected/sysviews.out|3 +-
 src/test/regress/expected/updatable_views.out |   17 +-
 src/test/regress/sql/equivclass.sql   |   16 +
 src/test/regress/sql/join.sql |  360 ++
 src/tools/pgindent/typedefs.list  |2 +
 14 files changed, 2375 insertions(+), 64 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 6bc1b215db..43c07b0d3b 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5299,6 +5299,22 @@ ANY num_sync ( 
+  enable_self_join_removal (boolean)
+  
+   enable_self_join_removal configuration 
parameter
+  
+  
+  
+   
+   Enables or disables the query planner's optimization which analyses
+query tree and replaces self joins with semantically equivalent single
+scans. Take into consideration only plain tables.
+The default is on.
+   
+  
+ 
+
  
   enable_seqscan (boolean)
   
diff --git a/src/backend/optimizer/path/indxpath.c 
b/src/backend/optimizer/path/indxpath.c
index 6a93d767a5..508285d1ef 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3494,6 +3494,21 @@ bool
 relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
  List *restrictlist,
  List *exprlist, List 
*oprlist)
+{
+   return relation_has_unique_index_ext(root, rel, restrictlist,
+   
 exprlist, oprlist, NULL);
+}
+
+/*
+ * relation_has_unique_index_ext
+ * if extra_clauses isn't NULL, return baserestrictinfo clauses which were
+ * used to derive uniqueness.
+ */
+bool
+relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel,
+ List *restrictlist,
+

Re: Removing unneeded self joins

[Andrey Lepikhov]

Hi,

During the significant code revision in v.41 I lost some replacement 
operations. Here is the fix and extra tests to check this in the future.
Also, Tom added the JoinDomain structure five months ago, and I added 
code to replace relids for that place too.
One more thing, I found out that we didn't replace SJs, defined by 
baserestrictinfos if no one self-join clause have existed for the join. 
Now, it is fixed, and the test has been added.

To understand changes readily, see the delta file in the attachment.

--
regards,
Andrey Lepikhov
Postgres Professional
From 8f5a432f6fbbcad1fd2937f33af09e9328690b6b Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" 
Date: Tue, 4 Jul 2023 16:07:50 +0700
Subject: [PATCH] Add lost arrangements of relids and varnos. Add the test to
 check it. Add one more cleaning procedure on JoinDomain relids which was
 introduced recently with commit 3bef56e. Fix the corner case when we haven't
 removed SJ if the selfjoinquals list was empty.

---
 src/backend/optimizer/plan/analyzejoins.c | 15 ++-
 src/test/regress/expected/join.out| 26 ---
 src/test/regress/expected/updatable_views.out | 17 +---
 src/test/regress/sql/join.sql |  9 +++
 4 files changed, 53 insertions(+), 14 deletions(-)

diff --git a/src/backend/optimizer/plan/analyzejoins.c 
b/src/backend/optimizer/plan/analyzejoins.c
index a93e4ce05c..15234b7a3b 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -424,6 +424,8 @@ remove_rel_from_query_common(PlannerInfo *root, RelOptInfo 
*rel,
sjinf->commute_above_r = replace_relid(sjinf->commute_above_r, 
ojrelid, subst);
sjinf->commute_below_l = replace_relid(sjinf->commute_below_l, 
ojrelid, subst);
sjinf->commute_below_r = replace_relid(sjinf->commute_below_r, 
ojrelid, subst);
+
+   replace_varno((Node *) sjinf->semi_rhs_exprs, relid, subst);
}
 
/*
@@ -465,6 +467,8 @@ remove_rel_from_query_common(PlannerInfo *root, RelOptInfo 
*rel,
/* ph_needed might or might not become empty */
phv->phrels = replace_relid(phv->phrels, relid, subst);
phv->phrels = replace_relid(phv->phrels, ojrelid, 
subst);
+   phinfo->ph_lateral = replace_relid(phinfo->ph_lateral, 
relid, subst);
+   phinfo->ph_var->phrels = 
replace_relid(phinfo->ph_var->phrels, relid, subst);
Assert(!bms_is_empty(phv->phrels));
Assert(phv->phnullingrels == NULL); /* no need to 
adjust */
}
@@ -1545,6 +1549,7 @@ update_eclass(EquivalenceClass *ec, int from, int to)
}
 
em->em_relids = replace_relid(em->em_relids, from, to);
+   em->em_jdomain->jd_relids = 
replace_relid(em->em_jdomain->jd_relids, from, to);
 
/* We only process inner joins */
replace_varno((Node *) em->em_expr, from, to);
@@ -2101,7 +2106,7 @@ remove_self_joins_one_group(PlannerInfo *root, Relids 
relids)
 */
restrictlist = generate_join_implied_equalities(root, 
joinrelids,

inner->relids,
-   
outer, 0);
+   
outer, NULL);
 
/*
 * Process restrictlist to seperate the self join quals 
out of
@@ -2111,6 +2116,14 @@ remove_self_joins_one_group(PlannerInfo *root, Relids 
relids)
split_selfjoin_quals(root, restrictlist, &selfjoinquals,
 
&otherjoinquals, inner->relid, outer->relid);
 
+   /*
+* To enable SJE for the only degenerate case without 
any self join
+* clauses at all, add baserestrictinfo to this list.
+* Degenerate case works only if both sides have the 
same clause. So
+* doesn't matter which side to add.
+*/
+   selfjoinquals = list_concat(selfjoinquals, 
outer->baserestrictinfo);
+
/*
 * Determine if the inner table can duplicate outer 
rows.  We must
 * bypass the unique rel cache here since we're 
possibly using a
diff --git a/src/test/regress/expected/join.out 
b/src/test/regress/expected/join.out
index b1f43f6ff8..027c356bcc 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -5807,11 +5807,13 @@ ex

Re: Removing unneeded self joins

[Andrey Lepikhov]

On 4/4/2023 02:30, Gregory Stark (as CFM) wrote:

On Mon, 6 Mar 2023 at 00:30, Michał Kłeczek  wrote:


Hi All,

I just wanted to ask about the status and plans for this patch.
I can see it being stuck at “Waiting for Author” status in several commit tests.


Sadly it seems to now be badly in need of a rebase. There are large
hunks failing in the guts of analyzejoins.c as well as minor failures
elsewhere and lots of offsets which need to be reviewed.

I think given the lack of activity it's out of time for this release
at this point. I'm moving it ahead to the next CF.

Hi,

Version 41 is heavily remade of the feature:

1. In previous versions, I tried to reuse remove_rel_from_query() for 
both left and self-join removal. But for now, I realized that it is a 
bit different procedures which treat different operations. In this 
patch, only common stages of the PlannerInfo fixing process are united 
in one function.
2. Transferring clauses from the removing table to keeping one is more 
transparent now and contains comments.
3. Equivalence classes update procedure was changed according to David's 
commit 3373c71. As I see, Tom has added remove_rel_from_eclass since the 
last v.40 version, and it looks pretty similar to the update_eclass 
routine in this patch.


It passes regression tests, but some questions are still open:
1. Should we look for duplicated or redundant clauses (the same for 
eclasses) during the clause transfer procedure? On the one side, we 
reduce the length of restrict lists that can impact planning or 
executing time. Additionally, we improve the accuracy of cardinality 
estimation. On the other side, it is one more place that can make 
planning time much longer in specific cases. It would have been better 
to avoid calling the equal() function here, but it's the only way to 
detect duplicated inequality expressions.
2. Could we reuse ChangeVarNodes instead of sje_walker(), merge 
remove_rel_from_restrictinfo with replace_varno?
3. Also, I still don't finish with the split_selfjoin_quals: some 
improvements could be made.


--
regards,
Andrey Lepikhov
Postgres Professional
From 4a342b9789f5be209318c13fb7ec336fcbd2aee5 Mon Sep 17 00:00:00 2001
From: Andrey Lepikhov 
Date: Mon, 15 May 2023 09:04:51 +0500
Subject: [PATCH] Remove self-joins.

A Self Join Elimination (SJE) feature removes inner join of plain table to 
itself
in a query tree if can be proved that the join can be replaced with a scan.
The proof based on innerrel_is_unique machinery.

We can remove a self-join when for each outer row:
1. At most one inner row matches the join clause.
2. If the join target list contains any inner vars, an inner row
must be (physically) the same row as the outer one.

In this patch we use the next approach to identify a self-join:
1. Collect all mergejoinable join quals which look like a.x = b.x
2. Check innerrel_is_unique() for the qual list from (1). If it
returns true, then outer row matches only the same row from the inner
relation.
3. If uniqueness of outer relation is deduced from baserestrictinfo clause like
'x=const' on unique field(s), check what the inner has the same clause with the
same constant(s).
4. Compare RowMarks of inner and outer relations. They must have the same
strength.

Some regression tests changed due to self-join removal logic.
---
 doc/src/sgml/config.sgml  |   16 +
 src/backend/optimizer/path/indxpath.c |   38 +
 src/backend/optimizer/plan/analyzejoins.c | 1077 -
 src/backend/optimizer/plan/planmain.c |5 +
 src/backend/utils/misc/guc_tables.c   |   22 +
 src/include/optimizer/paths.h |3 +
 src/include/optimizer/planmain.h  |7 +
 src/test/regress/expected/equivclass.out  |   32 +
 src/test/regress/expected/join.out|  798 +++
 src/test/regress/expected/sysviews.out|3 +-
 src/test/regress/sql/equivclass.sql   |   16 +
 src/test/regress/sql/join.sql |  351 +++
 src/tools/pgindent/typedefs.list  |2 +
 13 files changed, 2319 insertions(+), 51 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 6262cb7bb2..68215e1093 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5419,6 +5419,22 @@ ANY num_sync ( 
+  enable_self_join_removal (boolean)
+  
+   enable_self_join_removal configuration 
parameter
+  
+  
+  
+   
+   Enables or disables the query planner's optimization which analyses
+query tree and replaces self joins with semantically equivalent single
+scans. Take into consideration only plain tables.
+The default is on.
+   
+  
+ 
+
  
   enable_seqscan (boolean)
   
diff --git a/src/backend/optimizer/path/indxpath.c 
b/src/backend/optimizer/path/indxpath.c
index 0065c8992b..57bdc6811f 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3491,6 +3491,21 @@

Re: Removing unneeded self joins

[Andrey Lepikhov]

On 3/6/23 10:30, Michał Kłeczek wrote:
> Hi All,
>
> I just wanted to ask about the status and plans for this patch.
> I can see it being stuck at “Waiting for Author” status in several
> commit tests.
>
> I think this patch would be really beneficial for us as we heavily use
> views to structure out code.
> Each view is responsible for providing some calculated values and 
they > are joined in a query to retrieve the full set of information.

>
> Not sure how the process works and how I could help (I am absolutely
> not capable of helping with coding I am afraid - but could sponsor a
> (small :) ) bounty to speed things up).

Yes, I am still working on this feature. Because of significant changes 
in the optimizer code which Tom & Richard had been doing last months, I 
didn't touch it for a while. But now this work can be continued.


Current patch is rebased on current master. Because of the nullable_rels 
logic, introduced recently, ojrelids were highly spreaded across planner 
bitmapsets. So, JE logic was changed.


But now, I'm less happy with the code. It seems we need to refactor it:
1. According to reports of some performance engineers, the feature can 
cause overhead ~0.5% on trivial queries without joins at all. We should 
discover the patch and find the way for quick and cheap return, if the 
statement contains no one join or, maybe stronger, no one self join.
2. During join elimination we replace clauses like 'x=x' with 'x IS NOT 
NULL'. It is a weak point because we change clause semantic 
(mergejoinable to non-mergejoinable, in this example) and could forget 
consistently change some RestrictInfo fields.
3. In the previous versions we changed the remove_rel_from_query routine 
trying to use it in both 'Useless outer join' and 'Self join' 
elimination optimizations. Now, because of the 'ojrelid' field it looks 
too complicated. Do we need to split this routine again?


--
Regards
Andrey Lepikhov
Postgres Professional
From cb4340577dab0e8cf5531e9934f5734fda178490 Mon Sep 17 00:00:00 2001
From: Andrey Lepikhov 
Date: Mon, 15 May 2023 09:04:51 +0500
Subject: [PATCH] Remove self-joins.

A Self Join Elimination (SJE) feature removes inner join of plain table to itself
in a query tree if can be proved that the join can be replaced with a scan.
The proof based on innerrel_is_unique machinery.

We can remove a self-join when for each outer row:
1. At most one inner row matches the join clause.
2. If the join target list contains any inner vars, an inner row
must be (physically) the same row as the outer one.

In this patch we use the next approach to identify a self-join:
1. Collect all mergejoinable join quals which look like a.x = b.x
2. Check innerrel_is_unique() for the qual list from (1). If it
returns true, then outer row matches only the same row from the inner
relation.
3. If uniqueness of outer relation is deduced from baserestrictinfo clause like
'x=const' on unique field(s), check what the inner has the same clause with the
same constant(s).
4. Compare RowMarks of inner and outer relations. They must have the same
strength.

Some regression tests changed due to self-join removal logic.
---
 doc/src/sgml/config.sgml  |   16 +
 src/backend/optimizer/path/indxpath.c |   38 +
 src/backend/optimizer/plan/analyzejoins.c | 1093 -
 src/backend/optimizer/plan/planmain.c |5 +
 src/backend/utils/misc/guc_tables.c   |   22 +
 src/include/optimizer/paths.h |3 +
 src/include/optimizer/planmain.h  |7 +
 src/test/regress/expected/equivclass.out  |   32 +
 src/test/regress/expected/join.out|  774 +++
 src/test/regress/expected/sysviews.out|3 +-
 src/test/regress/sql/equivclass.sql   |   16 +
 src/test/regress/sql/join.sql |  340 +++
 src/tools/pgindent/typedefs.list  |2 +
 13 files changed, 2313 insertions(+), 38 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 5da74b3c40..b47d11759e 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5437,6 +5437,22 @@ ANY num_sync ( 
+  enable_self_join_removal (boolean)
+  
+   enable_self_join_removal configuration parameter
+  
+  
+  
+   
+   Enables or disables the query planner's optimization which analyses
+query tree and replaces self joins with semantically equivalent single
+scans. Take into consideration only plain tables.
+The default is on.
+   
+  
+ 
+
  
   enable_seqscan (boolean)
   
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 1436dbc2f2..1b1aa9083c 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3491,6 +3491,21 @@ bool
 relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 			  List *restrictlist,
 			  List *exprlist, List *oprlist)
+{
+	return relation_ha

Re: Removing unneeded self joins

[Gregory Stark (as CFM)]

On Mon, 6 Mar 2023 at 00:30, Michał Kłeczek  wrote:
>
> Hi All,
>
> I just wanted to ask about the status and plans for this patch.
> I can see it being stuck at “Waiting for Author” status in several commit 
> tests.

Sadly it seems to now be badly in need of a rebase. There are large
hunks failing in the guts of analyzejoins.c as well as minor failures
elsewhere and lots of offsets which need to be reviewed.

I think given the lack of activity it's out of time for this release
at this point. I'm moving it ahead to the next CF.



--
Gregory Stark
As Commitfest Manager

Re: Removing unneeded self joins

[Michał Kłeczek]

Hi All,

I just wanted to ask about the status and plans for this patch.
I can see it being stuck at “Waiting for Author” status in several commit tests.

I think this patch would be really beneficial for us as we heavily use views to 
structure out code.
Each view is responsible for providing some calculated values and they are 
joined in a query to retrieve the full set of information.

Not sure how the process works and how I could help (I am absolutely not 
capable of helping with coding I am afraid - but could sponsor a (small :) ) 
bounty to speed things up).

Thanks,
Michal

> On 16 Dec 2022, at 07:45, Andrey Lepikhov  wrote:
> 
> On 12/6/22 23:46, Andres Freund wrote:
>> This doesn't pass the main regression tests due to a plan difference.
>> https://cirrus-ci.com/task/5537518245380096
>> https://api.cirrus-ci.com/v1/artifact/task/5537518245380096/testrun/build/testrun/regress/regress/regression.diffs
>> diff -U3 /tmp/cirrus-ci-build/src/test/regress/expected/join.out 
>> /tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out
>> --- /tmp/cirrus-ci-build/src/test/regress/expected/join.out  2022-12-05 
>> 19:11:52.453920838 +
>> +++ /tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out  
>> 2022-12-05 19:15:21.864183651 +
>> @@ -5806,7 +5806,7 @@
>>   Nested Loop
>> Join Filter: (sj_t3.id = sj_t1.id)
>> ->  Nested Loop
>> - Join Filter: (sj_t3.id = sj_t2.id)
>> + Join Filter: (sj_t2.id = sj_t3.id)
>>   ->  Nested Loop Semi Join
>> ->  Nested Loop
>>   ->  HashAggregate
> This change in the test behaviour is induced by the a5fc4641
> "Avoid making commutatively-duplicate clauses in EquivalenceClasses."
> Nothing special, as I see. Attached patch fixes this.
> 
> -- 
> Regards
> Andrey Lepikhov
> Postgres Professional
> 

Re: Removing unneeded self joins

[Andrey Lepikhov]

On 12/6/22 23:46, Andres Freund wrote:

This doesn't pass the main regression tests due to a plan difference.
https://cirrus-ci.com/task/5537518245380096
https://api.cirrus-ci.com/v1/artifact/task/5537518245380096/testrun/build/testrun/regress/regress/regression.diffs

diff -U3 /tmp/cirrus-ci-build/src/test/regress/expected/join.out 
/tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out
--- /tmp/cirrus-ci-build/src/test/regress/expected/join.out 2022-12-05 
19:11:52.453920838 +
+++ /tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out 
2022-12-05 19:15:21.864183651 +
@@ -5806,7 +5806,7 @@
   Nested Loop
 Join Filter: (sj_t3.id = sj_t1.id)
 ->  Nested Loop
- Join Filter: (sj_t3.id = sj_t2.id)
+ Join Filter: (sj_t2.id = sj_t3.id)
   ->  Nested Loop Semi Join
 ->  Nested Loop
   ->  HashAggregate

This change in the test behaviour is induced by the a5fc4641
"Avoid making commutatively-duplicate clauses in EquivalenceClasses."
Nothing special, as I see. Attached patch fixes this.

--
Regards
Andrey Lepikhov
Postgres Professional
From 3e546637561bf4c6d195bc7c95b1e05263e797e2 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" 
Date: Wed, 5 Oct 2022 16:58:34 +0500
Subject: [PATCH] Remove self-joins.

A Self Join Removal (SJR) feature removes inner join of plain table to itself
in a query plan if can be proved that the join can be replaced with a scan.
The proof based on innerrel_is_unique machinery.

We can remove a self-join when for each outer row:
1. At most one inner row matches the join clauses.
2. If the join target list contains any inner vars, an inner row
must be (physically) the same row as the outer one.

In this patch we use Rowley's [1] approach to identify a self-join:
1. Collect all mergejoinable join quals which look like a.x = b.x
2. Check innerrel_is_unique() for the qual list from (1). If it
returns true, then outer row matches only the same row from the inner
relation.
3. If uniqueness of outer relation deduces from baserestrictinfo clause like
'x=const' on unique field(s), check that inner has the same clause with the
same constant(s).
4. Compare RowMarks of inner and outer relations. They must have the same
strength.

Some regression tests changed due to self-join removal logic.

[1] https://www.postgresql.org/message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXeErW5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com
---
 doc/src/sgml/config.sgml  |   16 +
 src/backend/optimizer/path/indxpath.c |   38 +
 src/backend/optimizer/plan/analyzejoins.c | 1046 -
 src/backend/optimizer/plan/planmain.c |5 +
 src/backend/utils/misc/guc_tables.c   |   22 +
 src/include/optimizer/paths.h |3 +
 src/include/optimizer/planmain.h  |7 +
 src/test/regress/expected/equivclass.out  |   32 +
 src/test/regress/expected/join.out|  774 +++
 src/test/regress/expected/sysviews.out|3 +-
 src/test/regress/sql/equivclass.sql   |   16 +
 src/test/regress/sql/join.sql |  340 +++
 src/tools/pgindent/typedefs.list  |2 +
 13 files changed, 2278 insertions(+), 26 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 8e4145979d..2f9948d5f8 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5311,6 +5311,22 @@ ANY num_sync ( 
+  enable_self_join_removal (boolean)
+  
+   enable_self_join_removal configuration parameter
+  
+  
+  
+   
+Enables or disables the query planner's optimization which analyses
+query tree and replaces self joins with semantically equivalent single
+scans. Take into consideration only plain tables.
+The default is on.
+   
+  
+ 
+
  
   enable_seqscan (boolean)
   
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 914bfd90bc..8d57c68b1f 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3494,6 +3494,21 @@ bool
 relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 			  List *restrictlist,
 			  List *exprlist, List *oprlist)
+{
+	return relation_has_unique_index_ext(root, rel, restrictlist,
+		 exprlist, oprlist, NULL);
+}
+
+/*
+ * relation_has_unique_index_ext
+ * if extra_clauses isn't NULL, return baserestrictinfo clauses which were
+ * used to derive uniqueness.
+ */
+bool
+relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel,
+			  List *restrictlist,
+			  List *exprlist, List *oprlist,
+			  List **extra_clauses)
 {
 	ListCell   *ic;
 
@@ -3549,6 +3564,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 	{
 		IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
 		int			c;
+		List	   *exprs = NIL;
 
 		/*
 		 * If the index is not unique, or not immediately enforced, or if it

Re: Removing unneeded self joins

[Andres Freund]

Hi,

On 2022-10-05 17:25:18 +0500, Andrey Lepikhov wrote:
> New version, rebased onto current master.
> Nothing special, just rebase.

This doesn't pass the main regression tests due to a plan difference.
https://cirrus-ci.com/task/5537518245380096
https://api.cirrus-ci.com/v1/artifact/task/5537518245380096/testrun/build/testrun/regress/regress/regression.diffs

diff -U3 /tmp/cirrus-ci-build/src/test/regress/expected/join.out 
/tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out
--- /tmp/cirrus-ci-build/src/test/regress/expected/join.out 2022-12-05 
19:11:52.453920838 +
+++ /tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out 
2022-12-05 19:15:21.864183651 +
@@ -5806,7 +5806,7 @@
  Nested Loop
Join Filter: (sj_t3.id = sj_t1.id)
->  Nested Loop
- Join Filter: (sj_t3.id = sj_t2.id)
+ Join Filter: (sj_t2.id = sj_t3.id)
  ->  Nested Loop Semi Join
->  Nested Loop
  ->  HashAggregate

Greetings,

Andres Freund

Re: Removing unneeded self joins

[Andrey Lepikhov]

New version, rebased onto current master.
Nothing special, just rebase.

--
regards,
Andrey Lepikhov
Postgres Professional
From 03aab7a2431032166c9ea5f52fbcccaf7168abec Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" 
Date: Wed, 5 Oct 2022 16:58:34 +0500
Subject: [PATCH] Remove self-joins.

A Self Join Removal (SJR) feature removes inner join of plain table to itself
in a query plan if can be proved that the join can be replaced with a scan.
The proof based on innerrel_is_unique machinery.

We can remove a self-join when for each outer row:
1. At most one inner row matches the join clauses.
2. If the join target list contains any inner vars, an inner row
must be (physically) the same row as the outer one.

In this patch we use Rowley's [1] approach to identify a self-join:
1. Collect all mergejoinable join quals which look like a.x = b.x
2. Check innerrel_is_unique() for the qual list from (1). If it
returns true, then outer row matches only the same row from the inner
relation.
3. If uniqueness of outer relation deduces from baserestrictinfo clause like
'x=const' on unique field(s), check that inner has the same clause with the
same constant(s).
4. Compare RowMarks of inner and outer relations. They must have the same
strength.

Some regression tests changed due to self-join removal logic.

[1] 
https://www.postgresql.org/message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXeErW5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com
---
 doc/src/sgml/config.sgml  |   16 +
 src/backend/optimizer/path/indxpath.c |   38 +
 src/backend/optimizer/plan/analyzejoins.c | 1046 -
 src/backend/optimizer/plan/planmain.c |5 +
 src/backend/utils/misc/guc_tables.c   |   22 +
 src/include/optimizer/paths.h |3 +
 src/include/optimizer/planmain.h  |7 +
 src/test/regress/expected/equivclass.out  |   32 +
 src/test/regress/expected/join.out|  774 +++
 src/test/regress/expected/sysviews.out|3 +-
 src/test/regress/sql/equivclass.sql   |   16 +
 src/test/regress/sql/join.sql |  340 +++
 src/tools/pgindent/typedefs.list  |2 +
 13 files changed, 2278 insertions(+), 26 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index d750290f13..5ce2d4d2fa 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5290,6 +5290,22 @@ ANY num_sync ( 
+  enable_self_join_removal (boolean)
+  
+   enable_self_join_removal configuration 
parameter
+  
+  
+  
+   
+Enables or disables the query planner's optimization which analyses
+query tree and replaces self joins with semantically equivalent single
+scans. Take into consideration only plain tables.
+The default is on.
+   
+  
+ 
+
  
   enable_seqscan (boolean)
   
diff --git a/src/backend/optimizer/path/indxpath.c 
b/src/backend/optimizer/path/indxpath.c
index c31fcc917d..51f672a65c 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3513,6 +3513,21 @@ bool
 relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
  List *restrictlist,
  List *exprlist, List 
*oprlist)
+{
+   return relation_has_unique_index_ext(root, rel, restrictlist,
+   
 exprlist, oprlist, NULL);
+}
+
+/*
+ * relation_has_unique_index_ext
+ * if extra_clauses isn't NULL, return baserestrictinfo clauses which were
+ * used to derive uniqueness.
+ */
+bool
+relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel,
+ List *restrictlist,
+ List *exprlist, List 
*oprlist,
+ List **extra_clauses)
 {
ListCell   *ic;
 
@@ -3568,6 +3583,7 @@ relation_has_unique_index_for(PlannerInfo *root, 
RelOptInfo *rel,
{
IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
int c;
+   List   *exprs = NIL;
 
/*
 * If the index is not unique, or not immediately enforced, or 
if it's
@@ -3616,6 +3632,24 @@ relation_has_unique_index_for(PlannerInfo *root, 
RelOptInfo *rel,
if (match_index_to_operand(rexpr, c, ind))
{
matched = true; /* column is unique */
+
+   if 
(bms_membership(rinfo->clause_relids) == BMS_SINGLETON)
+   {
+   MemoryContext oldMemCtx =
+   
MemoryContextSwitchTo(root->plann

Re: Removing unneeded self joins

[Andrey Lepikhov]

On 8/29/22 04:39, Zhihong Yu wrote:



On Fri, Aug 26, 2022 at 3:02 PM Zhihong Yu > wrote:


Hi,
For v36-0001-Remove-self-joins.patch :

bq removes inner join of plane table to itself

plane table -> plain table

For relation_has_unique_index_ext(), it seems when extra_clauses
is NULL, there is no need to compute `exprs`.

Cheers

Done



For remove_self_joins_recurse():

+                   if (bms_num_members(relids) > join_collapse_limit)
+                       break;

The above line just comes out of the switch statement. This check should 
be done again between foreach and switch.

Otherwise the above check wouldn't achieve what you want.

Cheers

Thanks for highlighting the problem.
I guess, usage either of join_collapse_limit or from_collapse_limit 
isn't practical here.
That we really afraid here - many senseless search cycles of self-joins. 
And it may have higher limit than GUCs above. So I introduced a guc, 
called "self_join_search_limit" (so far undocumented) that is an 
explicit limit for a set of plain relations in FROM-list to search 
self-joins.


--
Regards
Andrey Lepikhov
Postgres ProfessionalFrom 6283d6e21214e34d3c1a6351fa9f6ac1aeb75ce8 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" 
Date: Fri, 26 Aug 2022 15:17:53 +0300
Subject: [PATCH] Remove self-joins.

A Self Join Removal (SJR) feature removes inner join of plain table to itself
in a query plan if can be proved that the join can be replaced with a scan.
The proof based on innerrel_is_unique machinery.

We can remove a self-join when for each outer row:
1. At most one inner row matches the join clauses.
2. If the join target list contains any inner vars, an inner row
must be (physically) the same row as the outer one.

In this patch we use Rowley's [1] approach to identify a self-join:
1. Collect all mergejoinable join quals which look like a.x = b.x
2. Check innerrel_is_unique() for the qual list from (1). If it
returns true, then outer row matches only the same row from the inner
relation.
3. If uniqueness of outer relation deduces from baserestrictinfo clause like
'x=const' on unique field(s), check that inner has the same clause with the
same constant(s).
4. Compare RowMarks of inner and outer relations. They must have the same
strength.

Some regression tests changed due to self-join removal logic.

[1] https://www.postgresql.org/message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXeErW5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com
---
 doc/src/sgml/config.sgml  |   16 +
 src/backend/optimizer/path/indxpath.c |   38 +
 src/backend/optimizer/plan/analyzejoins.c | 1046 -
 src/backend/optimizer/plan/planmain.c |5 +
 src/backend/utils/misc/guc.c  |   22 +
 src/include/optimizer/paths.h |3 +
 src/include/optimizer/planmain.h  |7 +
 src/test/regress/expected/equivclass.out  |   32 +
 src/test/regress/expected/join.out|  774 +++
 src/test/regress/expected/sysviews.out|3 +-
 src/test/regress/sql/equivclass.sql   |   16 +
 src/test/regress/sql/join.sql |  340 +++
 src/tools/pgindent/typedefs.list  |2 +
 13 files changed, 2278 insertions(+), 26 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index a5cd4e44c7..2cfb62f97f 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5297,6 +5297,22 @@ ANY num_sync ( 
+  enable_self_join_removal (boolean)
+  
+   enable_self_join_removal configuration parameter
+  
+  
+  
+   
+Enables or disables the query planner's optimization which analyses
+query tree and replaces self joins with semantically equivalent single
+scans. Take into consideration only plain tables.
+The default is on.
+   
+  
+ 
+
  
   enable_seqscan (boolean)
   
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 045ff2e487..c41e7256be 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3495,6 +3495,21 @@ bool
 relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 			  List *restrictlist,
 			  List *exprlist, List *oprlist)
+{
+	return relation_has_unique_index_ext(root, rel, restrictlist,
+		 exprlist, oprlist, NULL);
+}
+
+/*
+ * relation_has_unique_index_ext
+ * if extra_clauses isn't NULL, return baserestrictinfo clauses which were
+ * used to derive uniqueness.
+ */
+bool
+relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel,
+			  List *restrictlist,
+			  List *exprlist, List *oprlist,
+			  List **extra_clauses)
 {
 	ListCell   *ic;
 
@@ -3550,6 +3565,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 	{
 		IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
 		int			c;
+		List	   *exprs = NIL;
 
 		/*
 		 * If the index is not unique, o

Re: Removing unneeded self joins

[Zhihong Yu]

On Fri, Aug 26, 2022 at 3:02 PM Zhihong Yu  wrote:

> Hi,
> For v36-0001-Remove-self-joins.patch :
>
> bq removes inner join of plane table to itself
>
> plane table -> plain table
>
> For relation_has_unique_index_ext(), it seems when extra_clauses is NULL,
> there is no need to compute `exprs`.
>
> Cheers
>

For remove_self_joins_recurse():

+   if (bms_num_members(relids) > join_collapse_limit)
+   break;

The above line just comes out of the switch statement. This check should be
done again between foreach and switch.
Otherwise the above check wouldn't achieve what you want.

Cheers

Re: Removing unneeded self joins

[Zhihong Yu]

Hi,
For v36-0001-Remove-self-joins.patch :

bq removes inner join of plane table to itself

plane table -> plain table

For relation_has_unique_index_ext(), it seems when extra_clauses is NULL,
there is no need to compute `exprs`.

Cheers

>

Re: Removing unneeded self joins

[Andrey Lepikhov]

On 30/6/2022 17:11, Andrey Lepikhov wrote:

On 19/5/2022 16:47, Ronan Dunklau wrote:

I'll take a look at that one.

New version of the patch, rebased on current master:
1. pgindent over the patch have passed.
2. number of changed files is reduced.
3. Some documentation and comments is added.

New version rebased on new master, minor changes and tests added.

--
regards,
Andrey Lepikhov
Postgres ProfessionalFrom 8d864515da68728ddee10d455f8bdb64d34277aa Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" 
Date: Fri, 26 Aug 2022 15:17:53 +0300
Subject: [PATCH] Remove self-joins.

A Self Join Removal (SJR) feature removes inner join of plane table to itself
in a query plan if can be proved that the join can be replaced with a scan.
The proof based on innerrel_is_unique machinery.

We can remove a self-join when for each outer row:
1. At most one inner row matches the join clauses.
2. If the join target list contains any inner vars, an inner row
must be (physically) the same row as the outer one.

In this patch we use Rowley's [1] approach to identify a self-join:
1. Collect all mergejoinable join quals which look like a.x = b.x
2. Check innerrel_is_unique() for the qual list from (1). If it
returns true, then outer row matches only the same row from the inner
relation.
3. If uniqueness of outer relation deduces from baserestrictinfo clause like
'x=const' on unique field(s), check that inner has the same clause with the
same constant(s).
4. Compare RowMarks of inner and outer relations. They must have the same
strength.

Some regression tests changed due to self-join removal logic.

[1] 
https://www.postgresql.org/message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXeErW5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com
---
 doc/src/sgml/config.sgml  |   16 +
 src/backend/optimizer/path/indxpath.c |   39 +
 src/backend/optimizer/plan/analyzejoins.c | 1045 -
 src/backend/optimizer/plan/planmain.c |5 +
 src/backend/utils/misc/guc.c  |   10 +
 src/include/optimizer/paths.h |3 +
 src/include/optimizer/planmain.h  |6 +
 src/test/regress/expected/equivclass.out  |   32 +
 src/test/regress/expected/join.out|  735 +++
 src/test/regress/expected/sysviews.out|3 +-
 src/test/regress/sql/equivclass.sql   |   16 +
 src/test/regress/sql/join.sql |  329 +++
 src/tools/pgindent/typedefs.list  |2 +
 13 files changed, 2215 insertions(+), 26 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index a5cd4e44c7..2cfb62f97f 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5297,6 +5297,22 @@ ANY num_sync ( 
+  enable_self_join_removal (boolean)
+  
+   enable_self_join_removal configuration 
parameter
+  
+  
+  
+   
+Enables or disables the query planner's optimization which analyses
+query tree and replaces self joins with semantically equivalent single
+scans. Take into consideration only plain tables.
+The default is on.
+   
+  
+ 
+
  
   enable_seqscan (boolean)
   
diff --git a/src/backend/optimizer/path/indxpath.c 
b/src/backend/optimizer/path/indxpath.c
index 045ff2e487..a9f8f89312 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3495,8 +3495,24 @@ bool
 relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
  List *restrictlist,
  List *exprlist, List 
*oprlist)
+{
+   return relation_has_unique_index_ext(root, rel, restrictlist,
+   
 exprlist, oprlist, NULL);
+}
+
+/*
+ * relation_has_unique_index_ext
+ * if extra_clauses isn't NULL, return baserestrictinfo clauses which were
+ * used to derive uniqueness.
+ */
+bool
+relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel,
+ List *restrictlist,
+ List *exprlist, List 
*oprlist,
+ List **extra_clauses)
 {
ListCell   *ic;
+   List   *exprs;
 
Assert(list_length(exprlist) == list_length(oprlist));
 
@@ -3551,6 +3567,8 @@ relation_has_unique_index_for(PlannerInfo *root, 
RelOptInfo *rel,
IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
int c;
 
+   exprs = NIL;
+
/*
 * If the index is not unique, or not immediately enforced, or 
if it's
 * a partial index that doesn't match the query, it's useless 
here.
@@ -3598,6 +3616,23 @@ relation_has_unique_index_for(PlannerInfo *root, 
RelOptInfo *rel,
if (match_index_to_operand(rexpr, 

Re: Removing unneeded self joins

[Zhihong Yu]

On Mon, Jul 4, 2022 at 6:52 AM Ronan Dunklau  wrote:

> Le jeudi 30 juin 2022, 16:11:51 CEST Andrey Lepikhov a écrit :
> > On 19/5/2022 16:47, Ronan Dunklau wrote:
> > > I'll take a look at that one.
> >
> > New version of the patch, rebased on current master:
> > 1. pgindent over the patch have passed.
> > 2. number of changed files is reduced.
> > 3. Some documentation and comments is added.
>
> Hello Andrey,
>
> Thanks for the updates.
>
> The general approach seems sensible to me, so I'm going to focus on some
> details.
>
> In a very recent thread [1], Tom Lane is proposing to add infrastructure
> to make Var aware of their nullability by outer joins. I wonder if that
> would help with avoiding the need for adding is not null clauses when the
> column is known not null ?
> If we have a precedent for adding a BitmapSet to the Var itself, maybe the
> whole discussion regarding keeping track of nullability can be extended to
> the original column nullability ?
>
> Also, I saw it was mentioned earlier in the thread but how difficult would
> it be to process the transformed quals through the EquivalenceClass
> machinery and the qual simplification ?
> For example, if the target audience of this patch is ORM, or inlined
> views, it wouldn't surprise me to see queries of this kind in the wild,
> which could be avoided altogether:
>
> postgres=# explain (costs off) select * from sj s1 join sj s2 on s1.a =
> s2.a where s1.b = 2 and s2.b =3;
>  QUERY PLAN
> -
>  Seq Scan on sj s2
>Filter: ((a IS NOT NULL) AND (b = 3) AND (b = 2))
> (2 lignes)
>
>
> +   for (counter = 0; counter < list_length(*sources);)
> +   {
> +   ListCell   *cell = list_nth_cell(*sources, counter);
> +   RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(cell));
> +   int counter1;
> +
> 
> + ec->ec_members = list_delete_cell(ec->ec_members, cell);
>
>
> Why don't you use foreach() and foreach_delete_current macros for
> iterating and removing items in the lists, both in update_ec_members and
> update_ec_sources ?
>
>
> +   if ((bms_is_member(k, info->syn_lefthand) ^
> +bms_is_member(r,
> info->syn_lefthand)) ||
> +   (bms_is_member(k,
> info->syn_righthand) ^
> +bms_is_member(r,
> info->syn_righthand)))
>
> I think this is more compact and easier to follow than the previous
> version, but I'm not sure how common it is in postgres source code to use
> that kind of construction ?
>
> Some review about the comments:
>
>
> I see you keep using the terms "the keeping relation" and "the removing
> relation" in reference to the relation that is kept and the one that is
> removed.
> Aside from the grammar (the kept relation or the removed relation), maybe
> it would make it clearer to call them something else. In other parts of the
> code, you used "the remaining relation / the removed relation" which makes
> sense.
>
>  /*
>   * Remove the target relid from the planner's data structures, having
> - * determined that there is no need to include it in the query.
> + * determined that there is no need to include it in the query. Or replace
> + * with another relid.
> + * To reusability, this routine can work in two modes: delete relid from
> a plan
> + * or replace it. It is used in replace mode in a self-join removing
> process.
>
> This could be rephrased: ", optionally replacing it with another relid.
> The latter is used by the self-join removing process."
>
>
> [1]
> https://www.postgresql.org/message-id/flat/830269.1656693747%40sss.pgh.pa.us
>
> --
> Ronan Dunklau
>
>
> Hi,
bq. this is more compact and easier to follow than the previous version

A code comment can be added above the expression (involving XOR) to explain
the purpose of the expression.

Cheers

Re: Removing unneeded self joins

[Ronan Dunklau]

Le jeudi 30 juin 2022, 16:11:51 CEST Andrey Lepikhov a écrit :
> On 19/5/2022 16:47, Ronan Dunklau wrote:
> > I'll take a look at that one.
> 
> New version of the patch, rebased on current master:
> 1. pgindent over the patch have passed.
> 2. number of changed files is reduced.
> 3. Some documentation and comments is added.

Hello Andrey,

Thanks for the updates. 

The general approach seems sensible to me, so I'm going to focus on some 
details. 

In a very recent thread [1], Tom Lane is proposing to add infrastructure to 
make Var aware of their nullability by outer joins. I wonder if that would help 
with avoiding the need for adding is not null clauses when the column is known 
not null ?
If we have a precedent for adding a BitmapSet to the Var itself, maybe the 
whole discussion regarding keeping track of nullability can be extended to the 
original column nullability ?

Also, I saw it was mentioned earlier in the thread but how difficult would it 
be to process the transformed quals through the EquivalenceClass machinery and 
the qual simplification ? 
For example, if the target audience of this patch is ORM, or inlined views, it 
wouldn't surprise me to see queries of this kind in the wild, which could be 
avoided altogether:

postgres=# explain (costs off) select * from sj s1 join sj s2 on s1.a = s2.a 
where s1.b = 2 and s2.b =3;
 QUERY PLAN  
-
 Seq Scan on sj s2
   Filter: ((a IS NOT NULL) AND (b = 3) AND (b = 2))
(2 lignes)


+   for (counter = 0; counter < list_length(*sources);)
+   {
+   ListCell   *cell = list_nth_cell(*sources, counter);
+   RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(cell));
+   int counter1;
+

+ ec->ec_members = list_delete_cell(ec->ec_members, cell);


Why don't you use foreach() and foreach_delete_current macros for iterating and 
removing items in the lists, both in update_ec_members and update_ec_sources ?


+   if ((bms_is_member(k, info->syn_lefthand) ^
+bms_is_member(r, info->syn_lefthand)) 
||
+   (bms_is_member(k, info->syn_righthand) ^
+bms_is_member(r, info->syn_righthand)))

I think this is more compact and easier to follow than the previous version, 
but I'm not sure how common it is in postgres source code to use that kind of 
construction ?

Some review about the comments:


I see you keep using the terms "the keeping relation" and "the removing 
relation" in reference to the relation that is kept and the one that is removed.
Aside from the grammar (the kept relation or the removed relation), maybe it 
would make it clearer to call them something else. In other parts of the code, 
you used "the remaining relation / the removed relation" which makes sense.

 /*
  * Remove the target relid from the planner's data structures, having
- * determined that there is no need to include it in the query.
+ * determined that there is no need to include it in the query. Or replace
+ * with another relid.
+ * To reusability, this routine can work in two modes: delete relid from a plan
+ * or replace it. It is used in replace mode in a self-join removing process.

This could be rephrased: ", optionally replacing it with another relid. The 
latter is used by the self-join removing process."


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

-- 
Ronan Dunklau

Re: Removing unneeded self joins

[Andrey Lepikhov]

On 19/5/2022 16:47, Ronan Dunklau wrote:

I'll take a look at that one.

New version of the patch, rebased on current master:
1. pgindent over the patch have passed.
2. number of changed files is reduced.
3. Some documentation and comments is added.

--
regards,
Andrey Lepikhov
Postgres ProfessionalFrom 9ce71f1d0ffefa9d77edfa30fc189bc0425ebbbe Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" 
Date: Thu, 15 Jul 2021 15:26:13 +0300
Subject: [PATCH] Remove self-joins.

A Self Join Removal (SJR) feature removes inner join of plane table to itself
in a query plan if can be proved that the join can be replaced with a scan.
The proof based on innerrel_is_unique machinery.

We can remove a self-join when for each outer row:
1. At most one inner row matches the join clauses.
2. If the join target list contains any inner vars, an inner row
must be (physically) the same row as the outer one.

In this patch we use Rowley's [1] approach to identify a self-join:
1. Collect all mergejoinable join quals which look like a.x = b.x
2. Check innerrel_is_unique() for the qual list from (1). If it
returns true, then outer row matches only the same row from the inner
relation.
3. If uniqueness of outer relation deduces from baserestrictinfo clause like
'x=const' on unique field(s), check that inner has the same clause with the
same constant(s).
4. Compare RowMarks of inner and outer relations. They must have the same
strength.

Some regression tests changed due to self-join removal logic.

[1] 
https://www.postgresql.org/message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXeErW5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com
---
 doc/src/sgml/config.sgml  |   16 +
 src/backend/optimizer/path/indxpath.c |   39 +
 src/backend/optimizer/plan/analyzejoins.c | 1045 -
 src/backend/optimizer/plan/planmain.c |5 +
 src/backend/utils/misc/guc.c  |   10 +
 src/include/optimizer/paths.h |3 +
 src/include/optimizer/planmain.h  |6 +
 src/test/regress/expected/equivclass.out  |   32 +
 src/test/regress/expected/join.out|  686 ++
 src/test/regress/expected/sysviews.out|3 +-
 src/test/regress/sql/equivclass.sql   |   16 +
 src/test/regress/sql/join.sql |  305 ++
 src/tools/pgindent/typedefs.list  |2 +
 13 files changed, 2142 insertions(+), 26 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 48478b1024..2226117c62 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5287,6 +5287,22 @@ ANY num_sync ( 
+  enable_self_join_removal (boolean)
+  
+   enable_self_join_removal configuration 
parameter
+  
+  
+  
+   
+Enables or disables the query planner's optimization which analyses
+query tree and replaces self joins with semantically equivalent single
+scans. Take into consideration only plain tables.
+The default is on.
+   
+  
+ 
+
  
   enable_seqscan (boolean)
   
diff --git a/src/backend/optimizer/path/indxpath.c 
b/src/backend/optimizer/path/indxpath.c
index 0ef70ad7f1..2eb05c79ce 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3498,8 +3498,24 @@ bool
 relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
  List *restrictlist,
  List *exprlist, List 
*oprlist)
+{
+   return relation_has_unique_index_ext(root, rel, restrictlist,
+   
 exprlist, oprlist, NULL);
+}
+
+/*
+ * relation_has_unique_index_ext
+ * if extra_clauses isn't NULL, return baserestrictinfo clauses which were
+ * used to derive uniqueness.
+ */
+bool
+relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel,
+ List *restrictlist,
+ List *exprlist, List 
*oprlist,
+ List **extra_clauses)
 {
ListCell   *ic;
+   List   *exprs;
 
Assert(list_length(exprlist) == list_length(oprlist));
 
@@ -3554,6 +3570,8 @@ relation_has_unique_index_for(PlannerInfo *root, 
RelOptInfo *rel,
IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
int c;
 
+   exprs = NIL;
+
/*
 * If the index is not unique, or not immediately enforced, or 
if it's
 * a partial index that doesn't match the query, it's useless 
here.
@@ -3601,6 +3619,23 @@ relation_has_unique_index_for(PlannerInfo *root, 
RelOptInfo *rel,
if (match_index_to_operand(rexpr, c, ind))
{
matched = true; /* column is u

Re: Removing unneeded self joins

[Ronan Dunklau]

Le jeudi 19 mai 2022, 12:48:18 CEST Andrey Lepikhov a écrit :
> On 5/17/22 19:14, Ronan Dunklau wrote:
> > Le vendredi 13 mai 2022, 07:07:47 CEST Andrey Lepikhov a écrit :
> >> New version of the feature.
> >> Here a minor bug with RowMarks is fixed. A degenerated case is fixed,
> >> when uniqueness of an inner deduced not from join quals, but from a
> >> baserestrictinfo clauses 'x=const', where x - unique field.
> >> Code, dedicated to solve second issue is controversial, so i attached
> >> delta.txt for quick observation.
> >> Maybe we should return to previous version of code, when we didn't split
> >> restriction list into join quals and base quals?
> > 
> > Hello,
> > 
> > I tried to find problematic cases, which would make the planning time grow
> > unacceptably, and couldn't devise it.
> > 
> > The worst case scenario I could think of was as follows:
> >   - a query with many different self joins
> >   - an abundance of unique indexes on combinations of this table columns
> >   to
> > 
> > consider
> > 
> >   - additional predicates on the where clause on columns.
> 
> Looking into the patch I can imagine, that the most difficult case is
> when a set of relations with the same OID is huge, but only small part
> of them (or nothing) can be removed.
> Also, removing a clause from restrictinfo list or from equivalence class
> adds non-linear complexity. So, you can dig this way ).
> 
> > The base table I used for this was a table with 40 integers. 39 unique
> > indexes were defined on every combination of (c1, cX) with cX being
> > columns c2 to c40.
> > 
> > I turned geqo off, set from_collapse_limit and join_collapse_limit to
> > unreasonably high values (30), and tried to run queries of the form:
> > 
> > SELECT * FROM test_table t1
> > JOIN test_table tX ON t1.c1 = tX.c1 AND t1.c[X+2] = tX.cX
> > ...
> > JOIN test_table tX ON t1.c1 = tX.c1 AND t1.c[X+2] = tX.cX.
> > 
> > So no self join can be eliminated in that case.
> 
> I think, you should compare t1.cX with tX.cX to eliminate self-join.
> Cross-unique-index proof isn't supported now.

Yes, that's the point. I wanted to try to introduce as much complexity as I 
could, without actually performing any self join elimination. The idea was to 
try to come up with the worst case scenario.
> 
> > The performance was very similar with or without the GUC enabled. I tested
> > the same thing without the patch, since the test for uniqueness has been
> > slightly altered and incurs a new allocation, but it doesn't seem to
> > change.
> > 
> > One interesting side effect of this patch, is that removing any unneeded
> > self join cuts down the planification time very significantly, as we
> > lower the number of combinations to consider.
> 
> Even more - removing a join we improve cardinality estimation.
> 
> > As for the code:
> >   - Comments on relation_has_unique_index_ext and
> >   relation_has_unique_index_for> 
> > should be rewritten, as relation_has_unique_index_for is now just a
> > special
> > case of relation_has_unique_index_ext. By the way, the comment would
> > probably be better read as: "but if extra_clauses isn't NULL".
> > 
> >   - The whole thing about "extra_clauses", ie, baserestrictinfos which
> >   were
> > 
> > used to determine uniqueness, is not very clear. Most functions where the
> > new argument has been added have not seen an update in their comments,
> > and the name itself doesn't really convey the intented meaning: perhaps
> > required_non_join_clauses ?
> > 
> > The way this works should be explained a bit more thoroughly, for example
> > in remove_self_joins_one_group the purpose of uclauses should be
> > explained. The fact that degenerate_case returns true when we don't have
> > any additional base restrict info is also confusing, as well as the
> > degenerate_case name.
> Agree,
> but after this case thoughts wander in my head: should we make one step
> back to pre-[1] approach? It looks like we have quite similar changes,
> but without special function for a 'degenerate case' detection and
> restrictlist splitting.

I'll take a look at that one. 

> 
> > I'll update if I think of more interesting things to add.
> 
> Thank you for your efforts!
> 
> See in attachment next version which fixes mistakes detected by
> z...@yugabyte.com.
> 
> [1]
> https://www.postgresql.org/message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXeErW
> 5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com


-- 
Ronan Dunklau