Re: Removing unneeded self joins

Hi hackers,

There is a join optimization we don't do -- removing inner join of a
table with itself on a unique column. Such joins are generated by
various ORMs, so from time to time our customers ask us to look into
this. Most recently, it was discussed on the list in relation to an
article comparing the optimizations that some DBMS make [1].

I started to explore what can be done about this. Attached is a proof of
concept patch. It works for some simple cases:

create table tt(a int primary key, b text);
explain select p.* from tt p join (select * from tt where b ~~ 'a%') q
on p.a = q.a;

                      QUERY PLAN
──────────────────────────────────────────────────────
 Seq Scan on tt p  (cost=0.00..25.88 rows=6 width=36)
   Filter: (b ~~ 'a%'::text)

It also works for semi-joins like `explain select p.* from tt p where
exists (select * from tt where b ~~ 'a%' and a = p.a);`. This requires a
preparatory step of reducing unique semi joins to inner joins, and we
already do this (reduce_unique_semijoin).

What this patch tries to do is to remove these inner joins when a single
join is being planned (populate_joinrel_with_paths). The main entry
point is reduce_self_unique_join. First, it proves that both input
relations are uniquely constrained by the same index given the
particular join clauses. We already have a way to find such indexes
(relation_has_unique_index_for), so I was able to reuse this. What I'm
not sure about is how to properly remove the join after that. For now, I
just pretend that the join relation being built is the outer baserel,
add to it the restrictions from the inner relation, and then plan it as
usual. Maybe there is a less hacky way to do it? I've seen elsewhere a
suggestion to use an AppendPath for a similar purpose, but here we can't
just use the outer relation we've already planned because the
restriction list is different.

I'd be glad to hear your thoughts on this.

[1]
/message-id/flat/CAMjNa7cC4X9YR-vAJS-jSYCajhRDvJQnN7m2sLH1wLh-_Z2bsw%40mail(dot)gmail(dot)com#CAMjNa7cC4X9YR-vAJS-jSYCajhRDvJQnN7m2sLH1wLh-_Z2bsw(at)mail(dot)gmail(dot)com

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:
> There is a join optimization we don't do -- removing inner join of a
> table with itself on a unique column. Such joins are generated by
> various ORMs, so from time to time our customers ask us to look into
> this. Most recently, it was discussed on the list in relation to an
> article comparing the optimizations that some DBMS make [1].

This is the sort of thing that I always wonder why the customers don't
ask the ORM to stop generating such damfool queries. Its *expensive*
for us to clean up after their stupidity; almost certainly, it would
take far fewer cycles, net, for them to be a bit smarter in the first
place.

regards, tom lane

On Wed, May 16, 2018 at 12:08 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:
>> There is a join optimization we don't do -- removing inner join of a
>> table with itself on a unique column. Such joins are generated by
>> various ORMs, so from time to time our customers ask us to look into
>> this. Most recently, it was discussed on the list in relation to an
>> article comparing the optimizations that some DBMS make [1].
>
> This is the sort of thing that I always wonder why the customers don't
> ask the ORM to stop generating such damfool queries. Its *expensive*
> for us to clean up after their stupidity; almost certainly, it would
> take far fewer cycles, net, for them to be a bit smarter in the first
> place.

The trouble, of course, is that the customer didn't write the ORM,
likely has no idea how it works, and doesn't want to run a modified
version of it even if they do. If the queries run faster on other
systems than they do on PostgreSQL, we get dinged -- not unjustly.

Also, I'm not sure that I believe that it's always easy to avoid
generating such queries. I mean, this case is trivial so it's easy to
say, well, just rewrite the query. But suppose that I have a fact
table over which I've created two views, each of which performs
various joins between the fact table and various lookup tables. My
queries are such that I normally need the joins in just one of these
two views and not the other to fetch the information I care about.
But every once in a while I need to run a report that involves pulling
every column possible. The obvious solution is to join the views on
the underlying table's primary key, but then you get this problem. Of
course there's a workaround: define a third view that does both sets
of joins-to-lookup-tables. But that starts to feel like you're
handholding the database; surely it's the database's job to optimize
queries, not the user's.

It's been about 10 years since I worked as a web developer, but I do
remember hitting this kind of problem from time to time and I'd really
like to see us do something about it. I wish we could optimize away
inner joins, too, for similar reasons.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Hi,

On 2018-05-16 12:26:48 -0400, Robert Haas wrote:
> Also, I'm not sure that I believe that it's always easy to avoid
> generating such queries.

Yea. There's obviously plenty cases where ORMs just want to make the
database hurt. But especially when building a join between a number of
tables based on various fields, it's not going to be easy for the ORM to
figure out which ones can be safely omitted. It'd need similar
optimization as we'd have to do, without having the infrastructure core
PG has. And then there's, as you say, views etc...

Greetings,

Andres Freund

On 16 May 2018 at 11:26, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Wed, May 16, 2018 at 12:08 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:
>>> There is a join optimization we don't do -- removing inner join of a
>>> table with itself on a unique column. Such joins are generated by
>>> various ORMs, so from time to time our customers ask us to look into
>>> this. Most recently, it was discussed on the list in relation to an
>>> article comparing the optimizations that some DBMS make [1].
>>
>> This is the sort of thing that I always wonder why the customers don't
>> ask the ORM to stop generating such damfool queries. Its *expensive*
>> for us to clean up after their stupidity; almost certainly, it would
>> take far fewer cycles, net, for them to be a bit smarter in the first
>> place.
>
> The trouble, of course, is that the customer didn't write the ORM,
> likely has no idea how it works, and doesn't want to run a modified
> version of it even if they do. If the queries run faster on other
> systems than they do on PostgreSQL, we get dinged -- not unjustly.
>
> Also, I'm not sure that I believe that it's always easy to avoid
> generating such queries. I mean, this case is trivial so it's easy to
> say, well, just rewrite the query. But suppose that I have a fact
> table over which I've created two views, each of which performs
> various joins between the fact table and various lookup tables. My
> queries are such that I normally need the joins in just one of these
> two views and not the other to fetch the information I care about.
> But every once in a while I need to run a report that involves pulling
> every column possible. The obvious solution is to join the views on
> the underlying table's primary key, but then you get this problem. Of
> course there's a workaround: define a third view that does both sets
> of joins-to-lookup-tables. But that starts to feel like you're
> handholding the database; surely it's the database's job to optimize
> queries, not the user's.
>
> It's been about 10 years since I worked as a web developer, but I do
> remember hitting this kind of problem from time to time and I'd really
> like to see us do something about it. I wish we could optimize away
> inner joins, too, for similar reasons.

I agree with everything you say.

What I would add is that I've seen cases where the extra joins do NOT
hurt performance, so the extra CPU used to remove the join hurts more
than the benefit of removing it. Yes, we tried it.

More advanced optimizations should only be applied when we've assessed
that the likely run time is high enough to make it worth investing in
further optimization.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Simon Riggs <simon(at)2ndquadrant(dot)com> writes:
> What I would add is that I've seen cases where the extra joins do NOT
> hurt performance, so the extra CPU used to remove the join hurts more
> than the benefit of removing it. Yes, we tried it.

Interesting. The concern I had was more about the cost imposed on every
query to detect self-joins and try to prove them useless, even in queries
where no benefit ensues. It's possible that we can get that down to the
point where it's negligible; but this says that even the successful-proof
case has to be very cheap.

regards, tom lane

> On May 16, 2018, at 1:58 PM, Andres Freund <andres(at)anarazel(dot)de> wrote:
>
> Hi,
>
> On 2018-05-16 12:26:48 -0400, Robert Haas wrote:
>> Also, I'm not sure that I believe that it's always easy to avoid
>> generating such queries.
>
> Yea. There's obviously plenty cases where ORMs just want to make the
> database hurt. But especially when building a join between a number of
> tables based on various fields, it's not going to be easy for the ORM to
> figure out which ones can be safely omitted. It'd need similar
> optimization as we'd have to do, without having the infrastructure core
> PG has. And then there's, as you say, views etc…

Are there specific examples of what the ORM code is that generated
the SQL? I’m more curious to see what people are writing that
generates such code. As earlier mentioned we could always report back
to the specific ORM maintainer(s) such examples and see if they could
tweak.

Jonathan

On 16 May 2018 at 15:10, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Simon Riggs <simon(at)2ndquadrant(dot)com> writes:
>> What I would add is that I've seen cases where the extra joins do NOT
>> hurt performance, so the extra CPU used to remove the join hurts more
>> than the benefit of removing it. Yes, we tried it.
>
> Interesting. The concern I had was more about the cost imposed on every
> query to detect self-joins and try to prove them useless, even in queries
> where no benefit ensues. It's possible that we can get that down to the
> point where it's negligible; but this says that even the successful-proof
> case has to be very cheap.

What I was advocating was an approach that varies according to the
query cost, so we don't waste time trying to tune the heck out of OLTP
queries, but for larger queries we might take a more considered
approach.

For advanced optimizations that are costly to check for, skip the
check if we are already below a cost threshold. The threshold would be
a heuristic that varies according to the cost of the check.

I realise that in this case we wouldn't know the full query cost until
we've done join planning, so we would need some lower bound estimate
to check whether its worth trying to remove joins.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 17 May 2018 at 03:43, Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
> I'd be glad to hear your thoughts on this.

(I only glanced at the patch)

I've thought and discussed this before on this list. I think the
arguments for and against it were much the same as you've received
already. If you trawl through the archives you'll see my argument for
matches quite closely to Robert regarding the nested-views. I
personally experienced this issue in my previous job, although it was
not with PostgreSQL.

I think it's worth doing this providing that we can fast-path out
quickly enough in cases where we can't possibly remove anything.
Likely the success of this patch depends on how quick that fast-path
is.

From my experience on join removals, I imagine all this can be done
just after the left join removal code has completed. I see your patch
does it much later, which I don't think is particularly great since
Paths have already been generated by that time. I think it makes sense
to do this as early as possible to save wasting planning work for
relations that will be removed.

I think all this can be done just after left joins are removed by
remove_useless_joins. You may like to move the code that exists in
that function today into a new static function named
remove_useless_left_joins, and put this new code in new static
function named remove_useless_self_joins:

1. Allocate an array root->simple_rel_array_size in size. Populate it
with a struct which is defined as struct { Index relid; Oid oid; }
2. Populate that array by looping over the simple_rel_array. Ignore
anything that's not a baserel with relkind = 'r'
3. qsort the array on Oid.
4. Make a pass over the array (up to its size - 1) looking for
elements where the current oid is the same as the next. Build a List
of RelIds containing all relids of Oids which are duplicated.
5. If no pairs. Abort.
6. Process each combination of pairs found in each Relids in the list
made in step 1. Probably start at the lowest relid.
7. For each pair:
a. If there's a join condition, ensure all join OpExprs are equality
exprs with a mergejoinable opno (copy what left join removal check
with the opno used). Ensure Vars used in the OpExpr have the same
attrno on each side.
b. For bonus points don't reject non-Vars used in the join
condition, but ensure they're equal and there are no non-immutable
functions inside.
c. Ensure relation_has_unique_index_for returns true for the Vars
(and Exprs if doing b) used in the join condition.
d. Choose the relation with the highest relid and rewrite the parse
changing the varno of all Vars to use the one of the relation with the
lowest relid.
e. list_concat baserestictinfos from removed relation onto other relation.
f. Check for Vars in the join condition that can contain NULLs and
lappend IS NOT NULLs into the baserestrictinfo. (Removing the join
could have removed NULL filtering)
g. Mark highest relid relation as DEAD. (See what the left join
removal code does (you may need to do some extra work around
equivalence classes))

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 17 May 2018 at 08:44, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> What I was advocating was an approach that varies according to the
> query cost, so we don't waste time trying to tune the heck out of OLTP
> queries, but for larger queries we might take a more considered
> approach.

That's tricky. If we do this, it should be done before Path
generation, so not much is known about the costs in those case.

Perhaps something can be done by looking at the number of relpages,
but I've no idea what that would be. Perhaps we need to see how costly
this operation is first before we try to think of ways to only apply
it conditionally?

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

David,

Many thanks for the detailed explanation. I'll try to code it up and
measure how much overhead it introduces.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Thu, May 17, 2018 at 3:43 AM, Alexander Kuzmenkov
<a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
> There is a join optimization we don't do -- removing inner join of a table
> with itself on a unique column. Such joins are generated by various ORMs, so
> from time to time our customers ask us to look into this. Most recently, it
> was discussed on the list in relation to an article comparing the
> optimizations that some DBMS make [1].
>
> ...
>
> I'd be glad to hear your thoughts on this.

+1

Some thoughts:

There might be some interesting corner cases involving self-joins in
UPDATE/DELETE statements, and also FOR UPDATE etc. Those can result
in some surprising results in a self-join (one side is subject to EPQ
and the other isn't) which I think might be changed by your patch
(though I didn't try it or read the patch very closely).

IIUC in DB2 (the clear winner at join elimination in the article you
mentioned), you get these sorts of things by default (optimisation
level 5 includes it), but not if you SET CURRENT QUERY OPTIMIZATION =
3 as many articles recommend for OLTP work. I think it's interesting
that they provide that knob rather than something automatic, and
interesting that there is one linear knob to classify your workload
rather than N knobs for N optimisations.

--
Thomas Munro
http://www.enterprisedb.com

HI,

On 2018-05-17 08:48:58 +1200, David Rowley wrote:
> On 17 May 2018 at 08:44, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> > What I was advocating was an approach that varies according to the
> > query cost, so we don't waste time trying to tune the heck out of OLTP
> > queries, but for larger queries we might take a more considered
> > approach.
>
> That's tricky. If we do this, it should be done before Path
> generation, so not much is known about the costs in those case.
>
> Perhaps something can be done by looking at the number of relpages,
> but I've no idea what that would be. Perhaps we need to see how costly
> this operation is first before we try to think of ways to only apply
> it conditionally?

I'm also not buying that this isn't a benefit in OLTP in general. Sure,
for a single query RTT costs are going to dominate, but if you use
prepared statements the costs are going to pay of over multiple
executions. Even just avoiding initializing unnecessary executor nodes
shows up in profiles.

Greetings,

Andres Freund

David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
> On 17 May 2018 at 08:44, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
>> What I was advocating was an approach that varies according to the
>> query cost, so we don't waste time trying to tune the heck out of OLTP
>> queries, but for larger queries we might take a more considered
>> approach.

> That's tricky. If we do this, it should be done before Path
> generation, so not much is known about the costs in those case.

Yeah. It'd have to be a very heuristic thing that doesn't account
for much beyond the number of relations in the query, and maybe their
sizes --- although I don't think we even know the latter at the
point where join removal would be desirable. (And note that one of
the desirable benefits of join removal is not having to find out the
sizes of removed rels ... so just swapping that around doesn't appeal.)

regards, tom lane

On 17 May 2018 at 10:13, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Yeah. It'd have to be a very heuristic thing that doesn't account
> for much beyond the number of relations in the query, and maybe their
> sizes --- although I don't think we even know the latter at the
> point where join removal would be desirable. (And note that one of
> the desirable benefits of join removal is not having to find out the
> sizes of removed rels ... so just swapping that around doesn't appeal.)

There's probably some argument for delaying obtaining the relation
size until after join removal and probably partition pruning too, but
it's currently done well before that in build_simple_rel, where the
RelOptInfo is built.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Thomas Munro <thomas(dot)munro(at)enterprisedb(dot)com> writes:
> IIUC in DB2 (the clear winner at join elimination in the article you
> mentioned), you get these sorts of things by default (optimisation
> level 5 includes it), but not if you SET CURRENT QUERY OPTIMIZATION =
> 3 as many articles recommend for OLTP work. I think it's interesting
> that they provide that knob rather than something automatic, and
> interesting that there is one linear knob to classify your workload
> rather than N knobs for N optimisations.

There's a lot to be said for that type of approach, as opposed to trying
to drive it off some necessarily-very-inexact preliminary estimate of
query cost. For example, the mere fact that you're joining giant tables
doesn't in itself suggest that extra efforts in query optimization will be
repaid. (If anything, it seems more likely that the user would've avoided
silliness like useless self-joins in such a case.)

A different line of thought is that, to me, the most intellectually
defensible rationale for efforts like const-simplification and join
removal is that opportunities for those things can arise after view
expansion, even in queries where the original query text didn't seem
to contain anything extraneous. (Robert and Andres alluded to this
upthread, but not very clearly.) So maybe we could track how much
the query got changed during rewriting, and use that to drive the
planner's decisions about how hard to work later on. But I'm not
very sure that this'd be superior to having a user-visible knob.

regards, tom lane

On 2018-05-16 18:37:11 -0400, Tom Lane wrote:
> Thomas Munro <thomas(dot)munro(at)enterprisedb(dot)com> writes:
> > IIUC in DB2 (the clear winner at join elimination in the article you
> > mentioned), you get these sorts of things by default (optimisation
> > level 5 includes it), but not if you SET CURRENT QUERY OPTIMIZATION =
> > 3 as many articles recommend for OLTP work. I think it's interesting
> > that they provide that knob rather than something automatic, and
> > interesting that there is one linear knob to classify your workload
> > rather than N knobs for N optimisations.
>
> There's a lot to be said for that type of approach, as opposed to trying
> to drive it off some necessarily-very-inexact preliminary estimate of
> query cost. For example, the mere fact that you're joining giant tables
> doesn't in itself suggest that extra efforts in query optimization will be
> repaid. (If anything, it seems more likely that the user would've avoided
> silliness like useless self-joins in such a case.)

For prepared statements we could also start making more expensive
optimizations after the first execution, when we know how long the query
took / how expensive it was (also, if we had a plan cache...).

Greetings,

Andres Freund

On 17 May 2018 at 10:37, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Thomas Munro <thomas(dot)munro(at)enterprisedb(dot)com> writes:
>> IIUC in DB2 (the clear winner at join elimination in the article you
>> mentioned), you get these sorts of things by default (optimisation
>> level 5 includes it), but not if you SET CURRENT QUERY OPTIMIZATION =
>> 3 as many articles recommend for OLTP work. I think it's interesting
>> that they provide that knob rather than something automatic, and
>> interesting that there is one linear knob to classify your workload
>> rather than N knobs for N optimisations.
>
> There's a lot to be said for that type of approach, as opposed to trying
> to drive it off some necessarily-very-inexact preliminary estimate of
> query cost. For example, the mere fact that you're joining giant tables
> doesn't in itself suggest that extra efforts in query optimization will be
> repaid. (If anything, it seems more likely that the user would've avoided
> silliness like useless self-joins in such a case.)
>
> A different line of thought is that, to me, the most intellectually
> defensible rationale for efforts like const-simplification and join
> removal is that opportunities for those things can arise after view
> expansion, even in queries where the original query text didn't seem
> to contain anything extraneous. (Robert and Andres alluded to this
> upthread, but not very clearly.) So maybe we could track how much
> the query got changed during rewriting, and use that to drive the
> planner's decisions about how hard to work later on. But I'm not
> very sure that this'd be superior to having a user-visible knob.

This seems like a good line of thought. Perhaps a knob is a good
first step, then maybe having the ability to set that knob to
"automatic" is something to aspire for later.

I don't think Alexander should work on this as part of this patch
though. Perhaps we can re-evaluate when Alexander posts some planner
benchmarks from the patch.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
> On 17 May 2018 at 10:13, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Yeah. It'd have to be a very heuristic thing that doesn't account
>> for much beyond the number of relations in the query, and maybe their
>> sizes --- although I don't think we even know the latter at the
>> point where join removal would be desirable. (And note that one of
>> the desirable benefits of join removal is not having to find out the
>> sizes of removed rels ... so just swapping that around doesn't appeal.)

> There's probably some argument for delaying obtaining the relation
> size until after join removal and probably partition pruning too, but
> it's currently done well before that in build_simple_rel, where the
> RelOptInfo is built.

Yeah, but that's something we ought to fix someday; IMO it's an artifact
of having wedged in remove_useless_joins without doing the extensive
refactoring that'd be needed to do it at a more desirable time. I don't
want to build user-visible behavior that's dependent on doing that wrong.

(But wait a second ... we could improve this without quite that much work:
instead of doing estimate_rel_size immediately during get_relation_info,
couldn't it be left until the set_base_rel_sizes pass? Since
RelationGetNumberOfBlocks involves kernel calls, skipping it for removed
rels seems worth doing.)

regards, tom lane

On 2018-05-16 18:55:41 -0400, Tom Lane wrote:
> David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
> > On 17 May 2018 at 10:13, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> >> Yeah. It'd have to be a very heuristic thing that doesn't account
> >> for much beyond the number of relations in the query, and maybe their
> >> sizes --- although I don't think we even know the latter at the
> >> point where join removal would be desirable. (And note that one of
> >> the desirable benefits of join removal is not having to find out the
> >> sizes of removed rels ... so just swapping that around doesn't appeal.)
>
> > There's probably some argument for delaying obtaining the relation
> > size until after join removal and probably partition pruning too, but
> > it's currently done well before that in build_simple_rel, where the
> > RelOptInfo is built.
>
> Yeah, but that's something we ought to fix someday; IMO it's an artifact
> of having wedged in remove_useless_joins without doing the extensive
> refactoring that'd be needed to do it at a more desirable time. I don't
> want to build user-visible behavior that's dependent on doing that wrong.

My patch that introduced a radix tree buffer mapping also keeps an
accurate relation size in memory, making it far cheaper to use. While I
depriorized the patchset for the moment (I'll post what I'm working on
first soon), that should address some of the cost till then.

Wonder if we shouldn't just cache an estimated relation size in the
relcache entry till then. For planning purposes we don't need to be
accurate, and usually activity that drastically expands relation size
will trigger relcache activity before long. Currently there's plenty
workloads where the lseeks(SEEK_END) show up pretty prominently.

Greetings,

Andres Freund

On 17 May 2018 at 10:55, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
>> There's probably some argument for delaying obtaining the relation
>> size until after join removal and probably partition pruning too, but
>> it's currently done well before that in build_simple_rel, where the
>> RelOptInfo is built.
>
> Yeah, but that's something we ought to fix someday; IMO it's an artifact
> of having wedged in remove_useless_joins without doing the extensive
> refactoring that'd be needed to do it at a more desirable time. I don't
> want to build user-visible behavior that's dependent on doing that wrong.
>
> (But wait a second ... we could improve this without quite that much work:
> instead of doing estimate_rel_size immediately during get_relation_info,
> couldn't it be left until the set_base_rel_sizes pass? Since
> RelationGetNumberOfBlocks involves kernel calls, skipping it for removed
> rels seems worth doing.)

I did mean just obtaining the sizes, not delaying building the
RelOptInfo. I see nothing that needs RelOptInfo->pages before
set_base_rel_size apart from the code which I mentioned about moving a
couple of days ago in [1].

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

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 17 May 2018 at 11:00, Andres Freund <andres(at)anarazel(dot)de> wrote:
> Wonder if we shouldn't just cache an estimated relation size in the
> relcache entry till then. For planning purposes we don't need to be
> accurate, and usually activity that drastically expands relation size
> will trigger relcache activity before long. Currently there's plenty
> workloads where the lseeks(SEEK_END) show up pretty prominently.

While I'm in favour of speeding that up, I think we'd get complaints
if we used a stale value. We could have uses pg_class.relpages all
along, but it would cause the planner to not work so well in face of
the relation changing size significantly between analyze runs.

FWIW the major case where that does show up is when generating a plan
for a partitioned table with many partitions then pruning all but a
few of them.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
> On 17 May 2018 at 11:00, Andres Freund <andres(at)anarazel(dot)de> wrote:
>> Wonder if we shouldn't just cache an estimated relation size in the
>> relcache entry till then. For planning purposes we don't need to be
>> accurate, and usually activity that drastically expands relation size
>> will trigger relcache activity before long. Currently there's plenty
>> workloads where the lseeks(SEEK_END) show up pretty prominently.

> While I'm in favour of speeding that up, I think we'd get complaints
> if we used a stale value.

Yeah, that scares me too. We'd then be in a situation where (arguably)
any relation extension should force a relcache inval. Not good.
I do not buy Andres' argument that the value is noncritical, either ---
particularly during initial population of a table, where the size could
go from zero to something-significant before autoanalyze gets around
to noticing.

I'm a bit skeptical of the idea of maintaining an accurate relation
size in shared memory, too. AIUI, a lot of the problem we see with
lseek(SEEK_END) has to do with contention inside the kernel for access
to the single-point-of-truth where the file's size is kept. Keeping
our own copy would eliminate kernel-call overhead, which can't hurt,
but it won't improve the contention angle.

regards, tom lane

On 2018-05-16 22:11:22 -0400, Tom Lane wrote:
> David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
> > On 17 May 2018 at 11:00, Andres Freund <andres(at)anarazel(dot)de> wrote:
> >> Wonder if we shouldn't just cache an estimated relation size in the
> >> relcache entry till then. For planning purposes we don't need to be
> >> accurate, and usually activity that drastically expands relation size
> >> will trigger relcache activity before long. Currently there's plenty
> >> workloads where the lseeks(SEEK_END) show up pretty prominently.
>
> > While I'm in favour of speeding that up, I think we'd get complaints
> > if we used a stale value.
>
> Yeah, that scares me too. We'd then be in a situation where (arguably)
> any relation extension should force a relcache inval. Not good.
> I do not buy Andres' argument that the value is noncritical, either ---
> particularly during initial population of a table, where the size could
> go from zero to something-significant before autoanalyze gets around
> to noticing.

I don't think every extension needs to force a relcache inval. It'd
instead be perfectly reasonable to define a rule that an inval is
triggered whenever crossing a 10% relation size boundary. Which'll lead
to invalidations for the first few pages, but much less frequently
later.

> I'm a bit skeptical of the idea of maintaining an accurate relation
> size in shared memory, too. AIUI, a lot of the problem we see with
> lseek(SEEK_END) has to do with contention inside the kernel for access
> to the single-point-of-truth where the file's size is kept. Keeping
> our own copy would eliminate kernel-call overhead, which can't hurt,
> but it won't improve the contention angle.

A syscall is several hundred instructions. An unlocked read - which'll
be be sufficient in many cases, given that the value can quickly be out
of date anyway - is a few cycles. Even with a barrier you're talking a
few dozen cycles. So I can't see how it'd not improve the contention.

But the main reason for keeping it in shmem is less the lseek avoidance
- although that's nice, context switches aren't great - but to make
relation extension need far less locking.

Greetings,

Andres Freund

On 17.05.2018 05:19, Andres Freund wrote:
> On 2018-05-16 22:11:22 -0400, Tom Lane wrote:
>> David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
>>> On 17 May 2018 at 11:00, Andres Freund <andres(at)anarazel(dot)de> wrote:
>>>> Wonder if we shouldn't just cache an estimated relation size in the
>>>> relcache entry till then. For planning purposes we don't need to be
>>>> accurate, and usually activity that drastically expands relation size
>>>> will trigger relcache activity before long. Currently there's plenty
>>>> workloads where the lseeks(SEEK_END) show up pretty prominently.
>>> While I'm in favour of speeding that up, I think we'd get complaints
>>> if we used a stale value.
>> Yeah, that scares me too. We'd then be in a situation where (arguably)
>> any relation extension should force a relcache inval. Not good.
>> I do not buy Andres' argument that the value is noncritical, either ---
>> particularly during initial population of a table, where the size could
>> go from zero to something-significant before autoanalyze gets around
>> to noticing.
> I don't think every extension needs to force a relcache inval. It'd
> instead be perfectly reasonable to define a rule that an inval is
> triggered whenever crossing a 10% relation size boundary. Which'll lead
> to invalidations for the first few pages, but much less frequently
> later.
>
>
>> I'm a bit skeptical of the idea of maintaining an accurate relation
>> size in shared memory, too. AIUI, a lot of the problem we see with
>> lseek(SEEK_END) has to do with contention inside the kernel for access
>> to the single-point-of-truth where the file's size is kept. Keeping
>> our own copy would eliminate kernel-call overhead, which can't hurt,
>> but it won't improve the contention angle.
> A syscall is several hundred instructions. An unlocked read - which'll
> be be sufficient in many cases, given that the value can quickly be out
> of date anyway - is a few cycles. Even with a barrier you're talking a
> few dozen cycles. So I can't see how it'd not improve the contention.
>
> But the main reason for keeping it in shmem is less the lseek avoidance
> - although that's nice, context switches aren't great - but to make
> relation extension need far less locking.
>
> Greetings,
>
> Andres Freund
>

I completely agree with Andreas. In my multithreaded Postgres prototype
file description cache (shared by all threads) becomes bottleneck
exactly because of each query execution requires
access to file system (lseek) to provide optimizer estimation of the
relation size, despite to the fact that all database fits in memory.
Well, this is certainly specific of shared descriptor's pool in my
prototype, but the fact the we have to perform lseek at each query
compilation seems to be annoying in any case.

And there is really no problem that cached relation size estimation is
not precise.  It really can be invalidated even if relation size is
changed more than some threshold value (1Mb?) or lease time for cached
value is expired.
May be it is reasonable to implement specific invalidation for relation
size esimation, to avoid complete invalidation and reconstruction of
relation description and all dependent objects.
In this case time-based invalidation seems to be the easiest choice to
implement. Repeating lseek each 10 or 1 second seems to have no
noticeable impact on performance and relation size can not dramatically
changed during this time.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Wed, May 16, 2018 at 6:13 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
>> On 17 May 2018 at 08:44, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
>>> What I was advocating was an approach that varies according to the
>>> query cost, so we don't waste time trying to tune the heck out of OLTP
>>> queries, but for larger queries we might take a more considered
>>> approach.
>
>> That's tricky. If we do this, it should be done before Path
>> generation, so not much is known about the costs in those case.
>
> Yeah. It'd have to be a very heuristic thing that doesn't account
> for much beyond the number of relations in the query, and maybe their
> sizes --- although I don't think we even know the latter at the
> point where join removal would be desirable. (And note that one of
> the desirable benefits of join removal is not having to find out the
> sizes of removed rels ... so just swapping that around doesn't appeal.)

As I've mentioned before, the problem we're talking about here is also
highly relevant to parallel query. We only want to bother generating
partial paths for queries that are expensive enough to justify
considering parallelism, but we don't know how expensive they are
until we finishing planning. The only way I could think of to tackle
that problem was to drive it off the relation sizes, but the presence
or absence of expensive functions in the target list can wildly change
the point at which parallelism potentially becomes useful. So we end
up sometimes wasting effort generating partial paths that are totally
useless, and at other times failing to generate partial paths that
would have been useful. (Really, I'd like to generate a lot more
partial paths than we do, trying out various numbers of workers, but
that would just make the existing problem worse.)

I have wondered about doing a preliminary pass over the tree where we
try to make a crude estimate of the amount of effort involved, and
then planning for real with that number in hand. But it seems like
there's so little information you could get at that early stage that
it would be hard to decide anything useful on that basis. You've got
to at least have relation sizes, and really you need some estimate of
the result cardinality as well. It seems like we currently can't
figure out cardinality without also computing paths, and I've wondered
if we could split those into two separate phases. But every time I
think about trying to do that I realize that my pain tolerance isn't
that high.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

David,

I tried to implement your suggestions, here are the patches.

The first patch mostly moves some code around without changing
functionality. It modifies innerrel_is_unique to not only cache the fact
that the relation is unique, but also
cache the index that guarantees uniqueness.

The second patch adds the unique self join removal code. It goes along
the lines of your plan. I didn't even have to examine join clauses
because the constraints imposed by innerrel_is_unique are strong enough
to guarantee that when it finds the same unique index for both
relations, the join can be removed. Namely, it requires mergejoinable
equality clauses for all columns of a unique index.

As a simple benchmark, I measured the duration of query_planner and
remove_useless_self_joins with clock_gettime() on the regression tests.
The following table shows average times in microseconds, median over 11
runs. First row is with this patch, and the second row doesn't call
remove_useless_self_joins and just calls clock_gettime to measure its
overhead.

              query_planner  remove_useless_self_joins

with removal       39.61            0.61

no removal         39.45            0.38

So, on this workload, unique self join removal adds about 0.2 mcs, or
0.6% of total time, to query_planner. I also tried a query that joins 26
relations, remove_useless_self_joins takes about 40 mcs. Still, this
time grows quadratically with number of relations we have to process, so
in the final patch I limit it to join_collapse_limit, which brings the
time down to 15 mcs. This is negligible compared to the total
query_planner time, which for 8 relations is about 3 ms, that is, 3
orders of magnitude higher.

These benchmarks mostly measure the path where we don't remove any
joins. I didn't time the join removal itself, because it wins quite some
time by allowing to plan one relation and one join less.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Here is a current version of the patch, still rather experimental. Since
the previous version, I fixed some bugs and added the possibility to
remove a relation even when it is mentioned in target lists. I have to
rewrite all references to the removed relation in targetlists and the
equivalence classes, so that they point to the remaining relation. I
change RestrictInfos in place, and update attr_needed and reltarget of
the remaining relation. I also update equivalence members, and delete
equivalence classes that become single-member.

I'm posting it a single file now, because all meaningful changes are in
analyzejoins.c anyway.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Sat, Jul 28, 2018 at 12:26 AM, Alexander Kuzmenkov
<a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
> Here is a current version of the patch, still rather experimental.

Hi Alexander,

The eval-qual-plan isolation test is failing:

- checking 1050 checking 600
+ checking 600 checking 600

That's the result of a self join with EPQ on one side of the join:

SELECT * FROM accounts a1, accounts a2
WHERE a1.accountid = a2.accountid
FOR UPDATE OF a1;

I think you need to disable the optimisation when there is a locking
clause on one side. Maybe it could be allowed if it's on both sides?
Not sure.

+ Assert(is_opclause(rinfo->clause));
+ Expr *leftOp = (Expr *) get_leftop(rinfo->clause);

You can't declare a variable here in C89.

--
Thomas Munro
http://www.enterprisedb.com

On 07/29/2018 01:42 PM, Thomas Munro wrote:
>
> I think you need to disable the optimisation when there is a locking
> clause on one side. Maybe it could be allowed if it's on both sides?
> Not sure.

Hi Thomas,

Thanks for testing. I think it should be OK to remove the join if the
row marks for both sides have the same type. I added the code to check
for that.

> You can't declare a variable here in C89.
>

Fixed.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Here is a rebased version of the patch. It includes some fixes after an
off-list review by Konstantin Knizhnik.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Here is a version that compiles.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 19 October 2018 at 01:47, Alexander Kuzmenkov
<a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
> Here is a version that compiles.

I had a quick read through this and I think its missing about a 1-page
comment section detailing when we can and when we cannot remove these
self joins, and what measures we must take when we do remove them.

Apart from that, I noted the following during my read:

1. I don't think this is the right way to do this. There are other
places where we alter the varnoold. For example:
search_indexed_tlist_for_var(). So you should likely be doing that too
rather than working around it.

@@ -166,10 +166,13 @@ _equalVar(const Var *a, const Var *b)
COMPARE_SCALAR_FIELD(vartypmod);
COMPARE_SCALAR_FIELD(varcollid);
COMPARE_SCALAR_FIELD(varlevelsup);
- COMPARE_SCALAR_FIELD(varnoold);
- COMPARE_SCALAR_FIELD(varoattno);
COMPARE_LOCATION_FIELD(location);

+ /*
+ * varnoold/varoattno are used only for debugging and may differ even
+ * when the variables are logically the same.
+ */
+

2. Surely the following loop is incorrect:

for (i = toKeep->min_attr; i <= toKeep->max_attr; i++)
{
int attno = i - toKeep->min_attr;
toKeep->attr_needed[attno] = bms_add_members(toKeep->attr_needed[attno],
toRemove->attr_needed[attno]);
}

What if toRemove has a lower min_attr or higher max_attr?

3. "wind" -> "find"

+ * When we wind such a join, we mark one of the participating relation as

4. I think the following shouldn't be happening:

+------------------------------------------------
Result
One-Time Filter: false
-(2 rows)
+ -> Index Scan using parent_pkey on parent x
+ Index Cond: (k = 1)
+(4 rows)

5. I'd have thought the opposite. Surely there are more chances of
this being useful with more joins?

+ /* Limit the number of joins we process to control the quadratic behavior. */
+ if (n > join_collapse_limit)
+ break;

6. In remove_self_joins_one_level() I think you should collect the
removed relations in a Relids rather than a list.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

El 08/11/18 a las 08:59, David Rowley escribió:
> On 19 October 2018 at 01:47, Alexander Kuzmenkov
> <a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
>> Here is a version that compiles.
> I had a quick read through this and I think its missing about a 1-page
> comment section detailing when we can and when we cannot remove these
> self joins, and what measures we must take when we do remove them.

I added some explanation to the comment for remove_useless_joins. This
is probably still not clear enough, so if you have any particular
questions I'll cover them too. While improving the comments, I found
some bugs around the handling of join clauses and broken ECs, so I fixed
them and added the tests.

> Apart from that, I noted the following during my read:
>
> 1. I don't think this is the right way to do this. There are other
> places where we alter the varnoold. For example:
> search_indexed_tlist_for_var(). So you should likely be doing that too
> rather than working around it.

Fixed.

> 2. Surely the following loop is incorrect:
>
> for (i = toKeep->min_attr; i <= toKeep->max_attr; i++)
> {
> int attno = i - toKeep->min_attr;
> toKeep->attr_needed[attno] = bms_add_members(toKeep->attr_needed[attno],
> toRemove->attr_needed[attno]);
> }
>
> What if toRemove has a lower min_attr or higher max_attr?

This shouldn't happen because this is always the same relation, and
max_attr is its physical number of attributes. There is an assertion
about this in remove_self_joins_one_group:
            /* A sanity check: the relations have the same Oid. */
            Assert(root->simple_rte_array[relids[i]]->relid ==
root->simple_rte_array[relids[o]]->relid);

> 3. "wind" -> "find"
>
> + * When we wind such a join, we mark one of the participating relation as

Fixed.

> 4. I think the following shouldn't be happening:
>
> +------------------------------------------------
> Result
> One-Time Filter: false
> -(2 rows)
> + -> Index Scan using parent_pkey on parent x
> + Index Cond: (k = 1)
> +(4 rows)

This happens because for join rels, we make some effort to prove that
they are empty and not make any paths for them, and we don't do this for
base rels. When we remove the join, this difference is exposed. Compare
to this query:

postgres=# explain select * from parent where k = 1 and k = 2;
                                   QUERY PLAN
────────────────────────────────────────────────────────────────────────────────
 Result  (cost=0.15..8.17 rows=1 width=8)
   One-Time Filter: false
   ->  Index Scan using parent_pkey on parent  (cost=0.15..8.17 rows=1
width=8)
         Index Cond: (k = 1)
(4 rows)

> 5. I'd have thought the opposite. Surely there are more chances of
> this being useful with more joins?
>
> + /* Limit the number of joins we process to control the quadratic behavior. */
> + if (n > join_collapse_limit)
> + break;

That is true, but we also have to think about the overhead when we don't
find any joins to remove. Without this cutoff, we have to examine every
pair of self-joins, so the run time grows quadratically with the number
of such joins in the query. I don't have a better idea on how to control
this.

> 6. In remove_self_joins_one_level() I think you should collect the
> removed relations in a Relids rather than a list.

Done.

--
Alexander Kuzmenkov
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company

Here is a rebased version with some bugfixes.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:
> Here is a rebased version with some bugfixes.

I noticed this had bit-rotted again. I've not really reviewed it, but
I rebased it up to HEAD, and fixed a couple small things:

* My compiler was bitching about misplaced declarations, so I moved
some variable declarations accordingly. I couldn't help noticing
that many of those wouldn't have been a problem in the first place
if you were following project style for loops around list_delete_cell
calls, which usually look more like this:

prev = NULL;
for (cell = list_head(root->rowMarks); cell; cell = next)
{
PlanRowMark *rc = (PlanRowMark *) lfirst(cell);

next = lnext(cell);
if (rt_fetch(rc->rti, root->parse->rtable)->rtekind == RTE_RESULT)
root->rowMarks = list_delete_cell(root->rowMarks, cell, prev);
else
prev = cell;
}

* I saw you had a problem with an existing test in join.sql that
was being optimized away because it used an ill-advised self-join.
I've pushed a fix for that, so it's not a problem as of HEAD.

I notice though that there's one unexplained plan change remaining
in join.out:

@@ -4365,11 +4365,13 @@ 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;
- QUERY PLAN
---------------------------
+ QUERY PLAN
+------------------------------------------------
Result
One-Time Filter: false
-(2 rows)
+ -> Index Scan using parent_pkey on parent x
+ Index Cond: (k = 1)
+(4 rows)

-- bug 5255: this is not optimizable by join removal
begin;

That sure looks like a bug. I don't have time to look for the
cause right now.

I also noticed that the test results show that when a table
is successfully optimized away, the remaining reference seems
to have the alias of the second reference not the first one.
That seems a little ... weird. It's just cosmetic of course, but
why is that?

Also, I did notice that you'd stuck a declaration for
"struct UniqueIndexInfo" into paths.h, which then compelled you
to include that header in planmain.h. This seems like poor style;
I'd have been inclined to put the struct in pathnodes.h instead.
That's assuming you need it at all -- in those two usages, seems
like it'd be just about as easy to return two separate Lists.
On the other hand, given

+ * unique_for_rels - list of (Relids, UniqueIndexInfo*) lists, where Relids
+ * is a set of other rels for which this one has been proven
+ * unique, and UniqueIndexInfo* stores information about the
+ * index that makes it unique, if any.

I wonder why you didn't include the Relids into UniqueIndexInfo as well
... and maybe make it a proper Node so that unique_for_rels could be
printed by outfuncs.c. So any way I slice it, it seems like this data
structure could use more careful contemplation.

Anyway, updated patch attached.

regards, tom lane

Hi Tom,

Thanks for the update.

On 2/22/19 03:25, Tom Lane wrote:
> * My compiler was bitching about misplaced declarations, so I moved
> some variable declarations accordingly. I couldn't help noticing
> that many of those wouldn't have been a problem in the first place
> if you were following project style for loops around list_delete_cell
> calls, which usually look more like this:

Changed them to conform to project style. After a couple of segfaults I
remembered why I wrote them the way I did: you can't use plain
'continue' with our style of loops and also have to update prev, and I
can't seem to remember to do that.

> I notice though that there's one unexplained plan change remaining
> in join.out:
>
> @@ -4365,11 +4365,13 @@ 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;
> - QUERY PLAN
> ---------------------------
> + QUERY PLAN
> +------------------------------------------------
> Result
> One-Time Filter: false
> -(2 rows)
> + -> Index Scan using parent_pkey on parent x
> + Index Cond: (k = 1)
> +(4 rows)
>
> -- bug 5255: this is not optimizable by join removal
> begin;
>
> That sure looks like a bug. I don't have time to look for the
> cause right now.

David also asked about this before. This is the same plan you'd get for
'select * from parent where k = 1 and k = 2', and this plan is exposed
by join removal. So this is not a bug in join removal itself.

> I also noticed that the test results show that when a table
> is successfully optimized away, the remaining reference seems
> to have the alias of the second reference not the first one.
> That seems a little ... weird. It's just cosmetic of course, but
> why is that?

Can you point me to a query that looks wrong?

> Also, I did notice that you'd stuck a declaration for
> "struct UniqueIndexInfo" into paths.h, which then compelled you
> to include that header in planmain.h. This seems like poor style;
> I'd have been inclined to put the struct in pathnodes.h instead.

Moved.

> I wonder why you didn't include the Relids into UniqueIndexInfo as well
> ... and maybe make it a proper Node so that unique_for_rels could be
> printed by outfuncs.c.

We also prove and cache the uniqueness for subqueries, for which the
UniqueIndexInfo is not relevant, that's why it was optional and stored
in a parallel list. Now I changed it to UniqueRelInfo which always has
outerrelids and optionally the unique index.

I also fixed a bug with not updating the references in HAVING clause.
New version is attached.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Fri, 1 Mar 2019 at 03:09, Alexander Kuzmenkov
<a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
> New version is attached.

I started looking over v11 and I'm wondering why you really need to
know which unique index proved the join unique?

I removed that check and I see it causes the following to remove the self-join:

create unique index on t1(a);
create unique index on t1(b);
explain select * from t1 inner join t1 t2 on t1.a=t2.b;
QUERY PLAN
--------------------------------------------------------
Seq Scan on t1 t2 (cost=0.00..38.25 rows=11 width=16)
Filter: (a = b)
(2 rows)

I had thought that the loop in is_unique_self_join() would have
rejected this, but looking more closely it's only checking the list of
join quals matched to each index match each other. Shouldn't it be
testing that the expressions on either side of the OpExprs are the
same after aligning the varnos? At the moment you're testing
innerrel_is_unique() for either side of the join, if you made this
change then couldn't you just test one rel and look for a unique index
on the join quals that match both sides of the join at the same time?
Probably relation_has_unique_index_for() is not the right tool for
that job, so you might need to write another function that does the
additional checks. Maybe it would be possible to split out some of the
code into helper functions so you don't have to copy the bulk of it.

The reason I mention this is that rel_is_distinct_for() also
considered subqueries. This allows the LEFT JOIN removal code to
remove joins like:

SELECT t1.* FROM t1 LEFT JOIN (SELECT DISTINCT a FROM t2) t2 on t1.a=t2.a;

In this case, the DISTINCT clause was used for unique proofs, not a
unique index.

It does not seem unreasonable that someone one day might want to
extend the self join removal code to do the same, e.g:

SELECT * FROM t1 INNER JOIN (SELECT DISTINCT a FROM t1) t2 on t1.a = t2.a;

and you're not setting it up to be very easy to do that because you're
insisting the proofs are unique indexes only.

What do you think?

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 3/14/19 14:21, David Rowley wrote:

> What do you think?

Let's recap the conditions when we can remove a self-join. It is when
for each outer row, 1) at most one inner row matches the join clauses,
and 2) it is the same row as the outer one. I'm not sure what (2) means
precisely in a general case, but for a plain table, we can identify
these rows by ctid. So when both sides have the same unique index with
the same clauses, we conclude that we are always dealing with the same
row (as identified by ctid) on both sides, hence the join can be
replaced with a scan.

The code I wrote just checks for the above conditions. The data we need
for these checks is a byproduct of checking the relations for
uniqueness, which we do anyway, so we just cache it for a negligible cost.

I didn't write it in a more generic way because I don't understand the
conditions for generic case. In your DISTINCT example, the join can be
removed indeed. But if we select some columns from the inner side apart
from the join ones, we can't remove the join anymore:

select * from t1, (select distinct on (a) a, b from t1) tt where t1.a =
tt.a;

I think this might be a different kind of optimization, where we remove
the self-join if the inner side is unique, and no inner columns are
selected besides the join ones.

Also, reading your letter I realized that I don't commute the index
clauses correctly before comparing them in is_unique_self_join, so I
fixed this in the new version of the patch.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Thu, 21 Mar 2019 at 01:20, Alexander Kuzmenkov
<a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
> Let's recap the conditions when we can remove a self-join. It is when
> for each outer row, 1) at most one inner row matches the join clauses,
> and 2) it is the same row as the outer one. I'm not sure what (2) means
> precisely in a general case, but for a plain table, we can identify
> these rows by ctid. So when both sides have the same unique index with
> the same clauses, we conclude that we are always dealing with the same
> row (as identified by ctid) on both sides, hence the join can be
> replaced with a scan.
>
> The code I wrote just checks for the above conditions. The data we need
> for these checks is a byproduct of checking the relations for
> uniqueness, which we do anyway, so we just cache it for a negligible cost.
>
> I didn't write it in a more generic way because I don't understand the
> conditions for generic case. In your DISTINCT example, the join can be
> removed indeed. But if we select some columns from the inner side apart
> from the join ones, we can't remove the join anymore:
>
> select * from t1, (select distinct on (a) a, b from t1) tt where t1.a =
> tt.a;
>
> I think this might be a different kind of optimization, where we remove
> the self-join if the inner side is unique, and no inner columns are
> selected besides the join ones.
>
>
> Also, reading your letter I realized that I don't commute the index
> clauses correctly before comparing them in is_unique_self_join, so I
> fixed this in the new version of the patch.

I really just don't think checking the unique indexes match is going
to cut it. You should be looking for a unique index where the join
clauses match on either side of the join, not looking independently
and then checking the indexes are the same ones.

Here's an example of what can go wrong with your current code:

drop table abc;
create table abc(a int, b int, c int);
create unique index on abc(a);
create unique index on abc(b);
create unique index on abc(c);
explain select * from abc a1 inner join abc a2 on a1.a=a2.b and a1.c=a2.c;
QUERY PLAN
---------------------------------------------------------
Seq Scan on abc a2 (cost=0.00..35.50 rows=10 width=24)
Filter: ((c IS NOT NULL) AND (a = b))
(2 rows)

The above seems fine, but let's try again, this time change the order
that the indexes are defined.

drop table abc;
create table abc(a int, b int, c int);
create unique index on abc(a);
create unique index on abc(c);
create unique index on abc(b);
explain select * from abc a1 inner join abc a2 on a1.a=a2.b and a1.c=a2.c;
QUERY PLAN
-----------------------------------------------------------------------
Hash Join (cost=61.00..102.11 rows=1 width=24)
Hash Cond: ((a1.a = a2.b) AND (a1.c = a2.c))
-> Seq Scan on abc a1 (cost=0.00..30.40 rows=2040 width=12)
-> Hash (cost=30.40..30.40 rows=2040 width=12)
-> Seq Scan on abc a2 (cost=0.00..30.40 rows=2040 width=12)
(5 rows)

oops. I think behaviour like this that depends on the order that
indexes are created is not going to cut it. Probably you maybe could
restrict the join qual list to just quals that have the same expr on
either side of the join, that way you could still use
innerrel_is_unique() to check the inner rel is unique. You'll likely
need to pass force_cache as false though, since you don't want to
cache non-uniqueness with a subset of joinquals. Doing that could
cause unique joins not to work when the join search is done via GEQO.
I also think this way would give you the subquery GROUP BY / DISTINCT
self join removal for just about free. However, there might be more
cleanup to be done in that case... I've not thought about that too
hard.

I'm going to set this to waiting on author, as that's quite a decent
sized change.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 3/21/19 01:54, David Rowley wrote:
> I really just don't think checking the unique indexes match is going
> to cut it. You should be looking for a unique index where the join
> clauses match on either side of the join, not looking independently
> and then checking the indexes are the same ones.

The bug you mention later is an implementation bug that can be fixed (I
will expand on that below). Besides this, do you think current self-join
detection algorithm has fundamental correctness problems? I am not aware
of such problems and this algorithm reflects my understanding of what
constitutes a removable self-join, so it would be helpful if you could
explain what exactly is wrong with it.

Your alternative idea sounds plausible, but I won't know it's correct
for sure until I implement it, which is a nontrivial amount of work. I
am also concerned that we will have to redo calculations similar to
innerrel_is_unique(), because having near-zero overhead is a hard
prerequisite for this patch, as was discussed upthread.

In short, I am reluctant to implement a new approach to detection until
I understand why the current one is fundamentally broken.

> Here's an example of what can go wrong with your current code:

This is a bug indeed. Unique index search is not exhaustive, so if many
indexes match the join quals, we might not find the same index for both
sides. I think this can be overcome if we switch to exhaustive search in
relation_has_unique_index_for, and then try to find matching indexes in
is_unique_self_join. Please see the new patch for the fix.

> I also think this way would give you the subquery GROUP BY / DISTINCT
> self join removal for just about free.

Could you explain how exactly we can generalize join removal to the
DISTINCT/GROUP BY case? I understand the removable self-joins as having
the same row on both sides of join, as identified by ctid, but I'm not
sure how to apply this to subqueries. Your earlier DISTINCT example
looked like it needed a different kind of join removal, with different
conditions for when it applies (please see my previous letter for details).

Another thing I'd like to mention is that this patch splits in two
independent parts, the detection of self-joins and their removal. While
we are looking for agreement on the detection part, could you also
review the removal part? I'm sure it has its own share of problems.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Sat, 23 Mar 2019 at 03:39, Alexander Kuzmenkov
<a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
> The bug you mention later is an implementation bug that can be fixed (I
> will expand on that below). Besides this, do you think current self-join
> detection algorithm has fundamental correctness problems? I am not aware
> of such problems and this algorithm reflects my understanding of what
> constitutes a removable self-join, so it would be helpful if you could
> explain what exactly is wrong with it.

I did explain what is wrong with it, and also showed an example of why
it is broken. I didn't see anything that looks fundamentally broken,
just the implementation needs more work.

> Your alternative idea sounds plausible, but I won't know it's correct
> for sure until I implement it, which is a nontrivial amount of work. I
> am also concerned that we will have to redo calculations similar to
> innerrel_is_unique(), because having near-zero overhead is a hard
> prerequisite for this patch, as was discussed upthread.

Are you worried about bypassing the unique rel cache is going to be too costly?

> > Here's an example of what can go wrong with your current code:
>
> This is a bug indeed. Unique index search is not exhaustive, so if many
> indexes match the join quals, we might not find the same index for both
> sides. I think this can be overcome if we switch to exhaustive search in
> relation_has_unique_index_for, and then try to find matching indexes in
> is_unique_self_join. Please see the new patch for the fix.

I really don't think modifying relation_has_unique_index_for to
collect details for up to 5 indexes is a good fix for this. It looks
like it's still possible to trigger this, just the example would need
to be more complex. Also, you've likely just more than doubled the
runtime of a successful match in relation_has_unique_index_for().
Previously, on average we'd have found that match halfway through the
list of indexes. Now it's most likely you'll end up looking at every
index, even after a match has been found. That does not seem well
aligned to keeping the CPU overhead for the patch low.

What is wrong with just weeding out join quals that don't have the
equivalent expression on either side before passing them to
relation_has_unique_index_for()? That'll save you from getting false
matches like I showed. To make that work it just seems mostly like
you'd mostly just need to swap the order of operations in the patch,
but you'd also likely end up needing to rip out all the UniqueRelInfo
code, since I don't think that'll be needed any longer. Likely that
means your entire patch would be limited to analyzejoins.c, although
I'm unsure what of the eclass editing code should be moved into
equivclass.c.

> > I also think this way would give you the subquery GROUP BY / DISTINCT
> > self join removal for just about free.
>
>
> Could you explain how exactly we can generalize join removal to the
> DISTINCT/GROUP BY case? I understand the removable self-joins as having
> the same row on both sides of join, as identified by ctid, but I'm not
> sure how to apply this to subqueries. Your earlier DISTINCT example
> looked like it needed a different kind of join removal, with different
> conditions for when it applies (please see my previous letter for details).

Well, by removing the requirement that the unique proofs have to come
from a unique index. I don't think you need to ensure this works for
your patch, it would be nice if it did for free. I just don't think
your implementation should block it from ever working.

> Another thing I'd like to mention is that this patch splits in two
> independent parts, the detection of self-joins and their removal. While
> we are looking for agreement on the detection part, could you also
> review the removal part? I'm sure it has its own share of problems.

I'd rather focus on the detection method before reviewing the removal
code. If there's some blocker in the detection code then the removal
code is not useful.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Sat, 23 Mar 2019 at 04:13, David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> wrote:
>
> On Sat, 23 Mar 2019 at 03:39, Alexander Kuzmenkov
> > This is a bug indeed. Unique index search is not exhaustive, so if many
> > indexes match the join quals, we might not find the same index for both
> > sides. I think this can be overcome if we switch to exhaustive search in
> > relation_has_unique_index_for, and then try to find matching indexes in
> > is_unique_self_join. Please see the new patch for the fix.
>
> I really don't think modifying relation_has_unique_index_for to
> collect details for up to 5 indexes is a good fix for this. It looks
> like it's still possible to trigger this, just the example would need
> to be more complex. Also, you've likely just more than doubled the
> runtime of a successful match in relation_has_unique_index_for().
> Previously, on average we'd have found that match halfway through the
> list of indexes. Now it's most likely you'll end up looking at every
> index, even after a match has been found. That does not seem well
> aligned to keeping the CPU overhead for the patch low.
>
> What is wrong with just weeding out join quals that don't have the
> equivalent expression on either side before passing them to
> relation_has_unique_index_for()? That'll save you from getting false
> matches like I showed. To make that work it just seems mostly like
> you'd mostly just need to swap the order of operations in the patch,
> but you'd also likely end up needing to rip out all the UniqueRelInfo
> code, since I don't think that'll be needed any longer. Likely that
> means your entire patch would be limited to analyzejoins.c, although
> I'm unsure what of the eclass editing code should be moved into
> equivclass.c.

I've done some minimal modifications to your v12 patch to make it work
the way I described. I ended up splitting out the joinqual list into
two lists; one that contains just self join quals that match on either
side, and the other with the remaining quals. We just pass the self
join matching quals to innerrel_is_unique() so we no longer can trick
it into matching with the wrong index.

I didn't modify remove_self_join_rel(). It could make use of the split
lists instead of checking what we've already checked in
split_selfjoin_quals(). i.e. selfjoinquals get a IS NOT NULL test
added to the basequals and the otherjoinquals have their varnos
changed and then applied to the basequals too.

There was a couple of regression test failures using your version of
the tests. One test just went back to what it was before you changed
the output and the other seems like a missed optimisation in your
version of the patch.

Namely, you didn't remove the self join in a case like:

explain select * from t1 inner join t1 t2 on t1.a=t2.a where t1.b = 1
and t2.b = 2;

but my version does. You had commented the test with:

-- If index conditions are different for each side, we won't select the same
-- row on both sides, so the join can't be removed.

but I don't quite understand why we can't remove the join in this
situation. For this particular case no rows can match, so maybe the
plan should really be the same as what happens when you do:

# explain select * from t1 where b = 1 and b = 2;
QUERY PLAN
-------------------------------------------------------------------------
Result (cost=0.15..8.17 rows=1 width=8)
One-Time Filter: false
-> Index Scan using t1_b_key on t1 (cost=0.15..8.17 rows=1 width=8)
Index Cond: (b = 1)
(4 rows)

For now, it still produces a plan like:

QUERY PLAN
-----------------------------------------------------------------------
Index Scan using t1_b_key on t1 t2 (cost=0.15..8.17 rows=1 width=16)
Index Cond: ((b = 2) AND (b = 1))
Filter: (a IS NOT NULL)
(3 rows)

My implementation of split_selfjoin_quals() still needs work. I only
wrote code to handle simple Vars. There could be Unique indexes on
exprs too, which the current code will fail to detect. I don't think
the join quals can contain vars from higher levels, but I didn't go to
the trouble of checking that in detail. If it's possible then we'll
need to reject those.

I also finished off the renaming of remove_useless_left_joins(). I
didn't go into any detail on the actual removal code.

I've attached a complete patch and also a delta against v12.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 3/25/19 07:07, David Rowley wrote:
> You had commented the test with:
>
> -- If index conditions are different for each side, we won't select the same
> -- row on both sides, so the join can't be removed.
>
> but I don't quite understand why we can't remove the join in this
> situation.

My rationale was that we're not exactly removing the join, but replacing
it with a scan. So it is not enough to just have a single row on each
side, it must be the same physical row. In this example, before the
transformation, t1.b is not equal to t2.b, but they become equal
afterwards. This looks somewhat wrong. On the other hand, if the
conditions are different, the resulting condition is going to evaluate
to constant false and we won't get any rows, so maybe it's OK.

This brings me again to the question of what are the conditions for join
removal. If the formulation with indexes is not general enough, what do
we use instead? I guess it could be something like this:

1. Given the (btree equality) join and restriction clauses, both sides
are unique on the same set of columns. That is, if we fix the values of
these columns, both sides have at most one matching row.

    a. For each of these columns, we have either

        i) a join clause that equates some expression referencing the
outer column to the same expression referencing the same inner column.

        ii) a clause for each relation that equates the same expression
referencing the outer and inner column to some other arbitrary
expression, possibly a different one for each side. This expression may
be a Const or some expression that references a Var of some third relation.

2. All the resulting columns can be calculated using either side of the
join. For now, just require that both sides are base relations that
refer to the same physical relation.

Two points are not clear to me here:

1. We don't handle join clauses to third relations, but can they be
treated the same way we treat Consts?

2. Can we simplify the join when we don't have any join clauses and only
have Consts? Or should we have at least one join clause that equates the
same inner and outer column? Why is one join clause enough?

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

I noticed you lost a couple of test cases in v14, so I added them back.

I also added a case where your implementation returns a different number
of rows compared to vanilla:

select * from sl t1, sl t2 where t1.a = t2.a and t1.b = 1;

Please see the attached v15.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 3/25/19 18:13, Alexander Kuzmenkov wrote:
>
> Please see the attached v15.
>

I won't be able to continue working on this because I'm changing jobs.
My colleague Arseny Sher is probably going to take over.

Here is a v16 that is a rebased v12, plus renames from v15, plus a
couple of bug fixes (use bms_is_empty instead of a NULL check, and
properly create a NullTest clause when replacing "X = X").

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Alexander Lakhin detected the bug in the 'remove self joins' patch:

test:
=====

CREATE TABLE t (a INT UNIQUE);
INSERT INTO t VALUES (1);
SELECT 1 FROM (SELECT x.* FROM t AS x, t AS y WHERE x.a = y.a) AS q,
LATERAL generate_series(1, q.a) gs(i);

Description:
============

FUNCTIONS, TABLEFUNCS and VALUES plan nodes uses direct link to the rte
table. We need to change varno references to relid which will be kept.

Version v.17 of the patch that fix the bug see in attachment.

--
Andrey Lepikhov
Postgres Professional
https://postgrespro.com
The Russian Postgres Company

On Thu, Jun 27, 2019 at 6:42 PM Andrey Lepikhov
<a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
> Version v.17 of the patch that fix the bug see in attachment.

While moving this to the September CF, I noticed that it needs to be
updated for the recent pg_list.h API changes.

--
Thomas Munro
https://enterprisedb.com

On 02/08/2019 04:54, Thomas Munro wrote:
> On Thu, Jun 27, 2019 at 6:42 PM Andrey Lepikhov
> <a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
>> Version v.17 of the patch that fix the bug see in attachment.
>
> While moving this to the September CF, I noticed that it needs to be
> updated for the recent pg_list.h API changes.
The patch was updated:
1. Changes caused by pg_list.h API changes.
2. Fix the problem of joint clause_relids and required_relids changes [1].
3. Add eclass mentions of removed relation into the kept relation (field
eclass_indexes was introduced by commit 3373c71553).

[1]
/message-id/flat/5c21029d-81a2-c999-6744-6a898fcc9a19%40postgrespro.ru

--
Andrey Lepikhov
Postgres Professional
https://postgrespro.com
The Russian Postgres Company

On 05.08.2019 14:24, Andrey Lepikhov wrote:
>
>
> On 02/08/2019 04:54, Thomas Munro wrote:
>> On Thu, Jun 27, 2019 at 6:42 PM Andrey Lepikhov
>> <a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
>>> Version v.17 of the patch that fix the bug see in attachment.
>>
>> While moving this to the September CF, I noticed that it needs to be
>> updated for the recent pg_list.h API changes.
> The patch was updated:
> 1. Changes caused by pg_list.h API changes.
> 2. Fix the problem of joint clause_relids and required_relids changes
> [1].
> 3. Add eclass mentions of removed relation into the kept relation
> (field eclass_indexes was introduced by commit 3373c71553).
>
> [1]
> /message-id/flat/5c21029d-81a2-c999-6744-6a898fcc9a19%40postgrespro.ru
>

One more bug is fixed in this patch: OR clauses were not correctly
updated in case of self join removal.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Some more bug fixes in this patch.

--

Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Slightly refactored version of the patch with more comments.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

v.21 in attechment fix small bug:
Now we move all non-mergejoinable clauses from joininfo to base restrict
info because of the relation will not be joined.

On 30/09/2019 13:29, Konstantin Knizhnik wrote:
>
> Slightly refactored version of the patch with more comments.
>

--
Andrey Lepikhov
Postgres Professional
https://postgrespro.com
The Russian Postgres Company

Rebased version v.22.
- Added enable_self_join_removal GUC (true is default)
- The joinquals of the relation that is being removed, redistributed in
accordance with the remove_rel_from_query () machinery.

--
Andrey Lepikhov
Postgres Professional
https://postgrespro.com
The Russian Postgres Company

On 1/27/20 11:10 PM, Andrey Lepikhov wrote:
> Rebased version v.22.
> - Added enable_self_join_removal GUC (true is default)
> - The joinquals of the relation that is being removed, redistributed in
> accordance with the remove_rel_from_query () machinery.

This patch no longer applies cleanly on
src/test/regress/sql/equivclass.sql:
http://cfbot.cputube.org/patch_27_1712.log

The CF entry has been updated to Waiting on Author.

Regards,
--
-David
david(at)pgmasters(dot)net

On 4/1/20 8:34 PM, David Steele wrote:
> This patch no longer applies cleanly on
> src/test/regress/sql/equivclass.sql:
> http://cfbot.cputube.org/patch_27_1712.log
>
> The CF entry has been updated to Waiting on Author.

v.23 in attachment:

1. The patch applies cleanly.
2. Add checks: two potentially self joined relations may belong to
different rules of order restriction in join_info_list.
3. Add test for item 2.

The CF entry has been updated to Needs review.

--
Andrey Lepikhov
Postgres Professional
https://postgrespro.com
The Russian Postgres Company

On Fri, 3 Apr 2020 at 17:43, Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
> v.23 in attachment:

Hi,

This is only a partial review as I see the patch still does not
incorporate the self join detection method I mentioned in March 2019
and the one the patch only partially works.

Here's the partial review which contains the details:

1. Change to aset.c not relevant to this patch.

--- a/src/backend/utils/mmgr/aset.c
+++ b/src/backend/utils/mmgr/aset.c
@@ -1485,7 +1485,6 @@ AllocSetCheck(MemoryContext context)

chsize = chunk->size; /* aligned chunk size */
dsize = chunk->requested_size; /* real data */
-
/*
* Check chunk size
*/

2. Why GUC_NOT_IN_SAMPLE?

+ {"enable_self_join_removal", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enable removal of unique self-joins."),
+ NULL,
+ GUC_NO_SHOW_ALL | GUC_NOT_IN_SAMPLE

3. I'd expect this to remove the join.

create table t1 (
a int not null unique,
b int not null unique,
c int not null unique,
d int not null,
e int not null
);

explain select * from t1 inner join t1 t2 on t1.a=t2.a and t1.b=t2.c;
QUERY PLAN
----------------------------------------------------------------------
Hash Join (cost=52.50..88.42 rows=1 width=40)
Hash Cond: ((t1.a = t2.a) AND (t1.b = t2.c))
-> Seq Scan on t1 (cost=0.00..27.00 rows=1700 width=20)
-> Hash (cost=27.00..27.00 rows=1700 width=20)
-> Seq Scan on t1 t2 (cost=0.00..27.00 rows=1700 width=20)
(5 rows)

This one seems to work.

This one *does* seem to work.

explain select * from t1 inner join t1 t2 on t1.a=t2.a and t1.d=t2.e;

You should likely implement the method I wrote in the final paragraph in [1]

The basic idea here is you first process the join quals:

t1.a=t2.a and t1.b=t2.c

and keep just the ones that use the same varattno on either side
(t1.a=t2.a). Perhaps it's not worth thinking about Exprs for now, or
if you think it is you can normalise the varnos to 1 and equal()

Then just pass the remaining quals to relation_has_unique_index_for().
If it returns true then there's no need to perform the opposite check
for the other relation. It would just return the same thing.

This will allow you to get rid of using the following as proofs:

/* We must have the same unique index for both relations. */
if (outerinfo->index->indexoid != innerinfo->index->indexoid)
return false;

... as I've shown above. This only works in some cases and that's not
really good enough.

Doing thing the way I describe will allow you to get rid of all the
UniqueRelInfo stuff.

4. Should be ok for partitioned tables though:

/*
* This optimization won't work for tables that have inheritance
* children.
*/
if (rte->inh)
continue;

David

[1] /message-id/CAKJS1f8p-KiEujr12k-oa52JNWWaQUjEjNg%2Bo1MGZk4mHBn_Rg%40mail.gmail.com

Thank you for this partial review, I included your changes:

On 9/23/20 9:23 AM, David Rowley wrote:
> On Fri, 3 Apr 2020 at 17:43, Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
> Doing thing the way I describe will allow you to get rid of all the
> UniqueRelInfo stuff.
Thanks for the review and sorry for the late reply.
I fixed small mistakes, mentioned in your letter.
Also I rewrote this patch at your suggestion [1].
Because of many changes, this patch can be viewed as a sketch.

To change self-join detection algorithm I used your delta patch from
[2]. I added in the split_selfjoin_quals routine complex expressions
handling for demonstration. But, it is not very useful with current
infrastructure, i think.

Also I implemented one additional way for self-join detection algorithm:
if the join target list isn't contained vars from inner relation, then
we can detect self-join with only quals like a1.x=a2.y if check
innerrel_is_unique is true.
Analysis of the target list is contained in the new routine -
tlist_contains_rel_exprs - rewritten version of the build_joinrel_tlist
routine.

Also changes of the join_is_removable() routine is removed from the
patch. I couldn't understand why it is needed here.

Note, this patch causes change of one join.sql regression test output.
It is not a bug, but maybe fixed.

Applied over commit 4a071afbd0.

> [1]
/message-id/CAKJS1f8p-KiEujr12k-oa52JNWWaQUjEjNg%2Bo1MGZk4mHBn_Rg%40mail.gmail.com
[2]
/message-id/CAKJS1f8cJOCGyoxi7a_LG7eu%2BWKF9%2BHTff3wp1KKS5gcUg2Qfg%40mail.gmail.com

--
regards,
Andrey Lepikhov
Postgres Professional

On 31.10.2020 12:26, Andrey V. Lepikhov wrote:
> Thank you for this partial review, I included your changes:
>
> On 9/23/20 9:23 AM, David Rowley wrote:
>> On Fri, 3 Apr 2020 at 17:43, Andrey Lepikhov
>> <a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
>> Doing thing the way I describe will allow you to get rid of all the
>> UniqueRelInfo stuff.
> Thanks for the review and sorry for the late reply.
> I fixed small mistakes, mentioned in your letter.
> Also I rewrote this patch at your suggestion [1].
> Because of many changes, this patch can be viewed as a sketch.
>
> To change self-join detection algorithm I used your delta patch from
> [2]. I added in the split_selfjoin_quals routine complex expressions
> handling for demonstration. But, it is not very useful with current
> infrastructure, i think.
>
> Also I implemented one additional way for self-join detection
> algorithm: if the join target list isn't contained vars from inner
> relation, then we can detect self-join with only quals like a1.x=a2.y
> if check innerrel_is_unique is true.
> Analysis of the target list is contained in the new routine -
> tlist_contains_rel_exprs - rewritten version of the
> build_joinrel_tlist routine.
>
> Also changes of the join_is_removable() routine is removed from the
> patch. I couldn't understand why it is needed here.
>
> Note, this patch causes change of one join.sql regression test output.
> It is not a bug, but maybe fixed.
>
> Applied over commit 4a071afbd0.
>
> > [1]
> /message-id/CAKJS1f8p-KiEujr12k-oa52JNWWaQUjEjNg%2Bo1MGZk4mHBn_Rg%40mail.gmail.com
> [2]
> /message-id/CAKJS1f8cJOCGyoxi7a_LG7eu%2BWKF9%2BHTff3wp1KKS5gcUg2Qfg%40mail.gmail.com
>
Status update for a commitfest entry.

This entry was "Waiting on author" during this CF. As I see, the latest
message contains new version of the patch. Does it need more work? Are
you going to continue working on it?

--
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 31/10/2020 11:26, Andrey V. Lepikhov wrote:
> + /*
> + * Process restrictlist to seperate out the self join quals from
> + * the other quals. e.g x = x goes to selfjoinquals and a = b to
> + * otherjoinquals.
> + */
> + split_selfjoin_quals(root, restrictlist, &selfjoinquals,
> + &otherjoinquals);
> +
> + if (list_length(selfjoinquals) == 0)
> + {
> + /*
> + * Have a chance to remove join if target list contains vars from
> + * the only one relation.
> + */
> + if (list_length(otherjoinquals) == 0)
> + {
> + /* Can't determine uniqueness without any quals. */
> + continue;
> +
> + }
> + else if (!tlist_contains_rel_exprs(root, joinrelids, inner))
> + {
> + if (!innerrel_is_unique(root, joinrelids, outer->relids,
> + inner, JOIN_INNER, otherjoinquals,
> + false))
> + continue;
> + }
> + else
> + /*
> + * The target list contains vars from both inner and outer
> + * relations.
> + */
> + continue;
> + }
> +
> + /*
> + * Determine if the inner table can duplicate outer rows. We must
> + * bypass the unique rel cache here since we're possibly using a
> + * subset of join quals. We can use 'force_cache' = true when all
> + * join quals are selfjoin quals. Otherwise we could end up
> + * putting false negatives in the cache.
> + */
> + else if (!innerrel_is_unique(root, joinrelids, outer->relids,
> + inner, JOIN_INNER, selfjoinquals,
> + list_length(otherjoinquals) == 0))
> + continue;

I don't understand the logic here. If 'selfjoinquals' is empty, it means
that there is no join qual between the two relations, right? How can we
ever remove the join in that case? And how does the target list affect
that? Can you give an example query of that?

> --- a/src/test/regress/expected/join.out
> +++ b/src/test/regress/expected/join.out
> @@ -4553,11 +4553,13 @@ 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;
> - QUERY PLAN
> ---------------------------
> + QUERY PLAN
> +------------------------------------------------
> Result
> One-Time Filter: false
> -(2 rows)
> + -> Index Scan using parent_pkey on parent x
> + Index Cond: (k = 1)
> +(4 rows)
>
> -- bug 5255: this is not optimizable by join removal
> begin;

That doesn't seem like an improvement...

My general impression of this patch is that it's a lot of code to deal
with a rare special case. At the beginning of this thread there was
discussion on the overhead that this might add to planning queries that
don't benefit, but adding a lot of code isn't nice either, even if the
performance is acceptable. That's not necessarily a show-stopper, but it
does make me much less excited about this. I'm not sure what to suggest
to do about that, except a really vague "Can you make is simpler?"

- Heikki

Thank you for the review,

On 27.11.2020 21:49, Heikki Linnakangas wrote:
> On 31/10/2020 11:26, Andrey V. Lepikhov wrote:
>> +            /*
>> +             * Process restrictlist to seperate out the self join
>> quals from
>> +             * the other quals. e.g x = x goes to selfjoinquals and a
>> = b to
>> +             * otherjoinquals.
>> +             */
>> +            split_selfjoin_quals(root, restrictlist, &selfjoinquals,
>> +                                 &otherjoinquals);
>> +
>> +            if (list_length(selfjoinquals) == 0)
>> +            {
>> +                /*
>> +                 * Have a chance to remove join if target list
>> contains vars from
>> +                 * the only one relation.
>> +                 */
>
> I don't understand the logic here. If 'selfjoinquals' is empty, it means
> that there is no join qual between the two relations, right? How can we
> ever remove the join in that case? And how does the target list affect
> that? Can you give an example query of that?

Maybe it is a problem of variable naming. Following the idea of David
Rowley, we split quals into two subsets: {x==x} and another, for example
{x=y}.
First set is an trivial case of self-join: if we have unique index on
the attribute 'x', then this join is self-join.
Second set is give us a chance: if right side is unique for right side
of the qual and no vars from right side end up in the target list of the
join, then this is a self-join case. Example:

CREATE TABLE a(x int, y int);
CREATE UNIQUE INDEX ON a(x);
SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.x; -- self-join
CREATE UNIQUE INDEX ON a(y);
SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- self-join too

>
>> --- a/src/test/regress/expected/join.out
>> +++ b/src/test/regress/expected/join.out
>> @@ -4553,11 +4553,13 @@ 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;
>> -        QUERY PLAN ---------------------------
>> +                   QUERY PLAN
>> +------------------------------------------------
>>   Result
>>     One-Time Filter: false
>> -(2 rows)
>> +   ->  Index Scan using parent_pkey on parent x
>> +         Index Cond: (k = 1)
>> +(4 rows)
>>
>>  -- bug 5255: this is not optimizable by join removal
>>  begin;
>
> That doesn't seem like an improvement...

I investigated this case. It is a planner feature: it simplifies dummy
joins and dummy scans to different plans. Maybe it can cause some
discussion, but this example so rare and doesn't make a problem.

> My general impression of this patch is that it's a lot of code to deal
> with a rare special case. At the beginning of this thread there was
> discussion on the overhead that this might add to planning queries that
> don't benefit, but adding a lot of code isn't nice either, even if the
> performance is acceptable. That's not necessarily a show-stopper, but it
> does make me much less excited about this. I'm not sure what to suggest
> to do about that, except a really vague "Can you make is simpler?"

Currently planner reduces useless outer joins and unique semijoins.
Reduce self join feature continues the development of the planner in the
same direction. For example, it is needed for ORM software.
Most of the code dedicated to removing unnecessary relation and
replacing of one oid with another. We are trying to use
remove_rel_from_query() machinery. Perhaps this will allow us to make
the code shorter.

--
regards,
Andrey Lepikhov
Postgres Professional

On 28/11/2020 19:21, Andrey Lepikhov wrote:
> On 27.11.2020 21:49, Heikki Linnakangas wrote:
>> On 31/10/2020 11:26, Andrey V. Lepikhov wrote:
>>> +            /*
>>> +             * Process restrictlist to seperate out the self join
>>> quals from
>>> +             * the other quals. e.g x = x goes to selfjoinquals and a
>>> = b to
>>> +             * otherjoinquals.
>>> +             */
>>> +            split_selfjoin_quals(root, restrictlist, &selfjoinquals,
>>> +                                 &otherjoinquals);
>>> +
>>> +            if (list_length(selfjoinquals) == 0)
>>> +            {
>>> +                /*
>>> +                 * Have a chance to remove join if target list
>>> contains vars from
>>> +                 * the only one relation.
>>> +                 */
>>
>> I don't understand the logic here. If 'selfjoinquals' is empty, it means
>> that there is no join qual between the two relations, right? How can we
>> ever remove the join in that case? And how does the target list affect
>> that? Can you give an example query of that?
>
> Maybe it is a problem of variable naming. Following the idea of David
> Rowley, we split quals into two subsets: {x==x} and another, for example
> {x=y}.
> First set is an trivial case of self-join: if we have unique index on
> the attribute 'x', then this join is self-join.
> Second set is give us a chance: if right side is unique for right side
> of the qual and no vars from right side end up in the target list of the
> join, then this is a self-join case. Example:
>
> CREATE TABLE a(x int, y int);
> CREATE UNIQUE INDEX ON a(x);
> SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.x; -- self-join
> CREATE UNIQUE INDEX ON a(y);
> SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- self-join too

The latter join is not "useless". The patch is returning incorrect
result for that query:

> postgres=# insert into a values (1, 2);
> INSERT 0 1
> postgres=# insert into a values (2, 1);
> INSERT 0 1
> postgres=# SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- WRONG RESULT
> x | y
> ---+---
> (0 rows)
>
> postgres=# set enable_self_join_removal=off;
> SET
> postgres=# SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- CORRECT RESULT
> x | y
> ---+---
> 1 | 2
> 2 | 1
> (2 rows)

- Heikki

On 11/29/20 10:10 PM, Heikki Linnakangas wrote:
> On 28/11/2020 19:21, Andrey Lepikhov wrote:
>> On 27.11.2020 21:49, Heikki Linnakangas wrote:
>> CREATE TABLE a(x int, y int);
>> CREATE UNIQUE INDEX ON a(x);
>> SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.x;  -- self-join
>> CREATE UNIQUE INDEX ON a(y);
>> SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y;  -- self-join too
>
> The latter join is not "useless". The patch is returning incorrect
> result for that query:
>
>> postgres=# insert into a values (1, 2);
>> INSERT 0 1
>> postgres=# insert into a values (2, 1);
>> INSERT 0 1
>> postgres=# SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- WRONG RESULT
>>  x | y ---+---
>> (0 rows)
>>
>> postgres=# set enable_self_join_removal=off;
>> SET
>> postgres=# SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- CORRECT
>> RESULT
>>  x | y ---+---
>>  1 | 2
>>  2 | 1
>> (2 rows)

Thanks, it is my fault. I tried to extend this patch with foreign key
references and made a mistake.
Currently I rollback this new option (see patch in attachment), but will
be working for a while to simplify this patch.

--
regards,
Andrey Lepikhov
Postgres Professional

Hi Andrey,

On Mon, Nov 30, 2020 at 2:51 PM Andrey V. Lepikhov
<a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
>
> On 11/29/20 10:10 PM, Heikki Linnakangas wrote:
> > On 28/11/2020 19:21, Andrey Lepikhov wrote:
> >> On 27.11.2020 21:49, Heikki Linnakangas wrote:
> >> CREATE TABLE a(x int, y int);
> >> CREATE UNIQUE INDEX ON a(x);
> >> SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.x; -- self-join
> >> CREATE UNIQUE INDEX ON a(y);
> >> SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- self-join too
> >
> > The latter join is not "useless". The patch is returning incorrect
> > result for that query:
> >
> >> postgres=# insert into a values (1, 2);
> >> INSERT 0 1
> >> postgres=# insert into a values (2, 1);
> >> INSERT 0 1
> >> postgres=# SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- WRONG RESULT
> >> x | y ---+---
> >> (0 rows)
> >>
> >> postgres=# set enable_self_join_removal=off;
> >> SET
> >> postgres=# SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y; -- CORRECT
> >> RESULT
> >> x | y ---+---
> >> 1 | 2
> >> 2 | 1
> >> (2 rows)
>
> Thanks, it is my fault. I tried to extend this patch with foreign key
> references and made a mistake.
> Currently I rollback this new option (see patch in attachment), but will
> be working for a while to simplify this patch.

Are you working to simplify the patch? This patch has been "Waiting on
Author" for 1 month and doesn't seem to pass cfbot tests. Please
update the patch.

Regards,

--
Masahiko Sawada
EnterpriseDB: https://www.enterprisedb.com/

On 1/7/21 7:08 PM, Masahiko Sawada wrote:
> On Mon, Nov 30, 2020 at 2:51 PM Andrey V. Lepikhov
> <a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
>> Thanks, it is my fault. I tried to extend this patch with foreign key
>> references and made a mistake.
>> Currently I rollback this new option (see patch in attachment), but will
>> be working for a while to simplify this patch.
>
> Are you working to simplify the patch? This patch has been "Waiting on
> Author" for 1 month and doesn't seem to pass cfbot tests. Please
> update the patch.

Yes, I'm working to improve this feature.
In attachment - fixed and rebased on ce6a71fa53.

--
regards,
Andrey Lepikhov
Postgres Professional

The following review has been posted through the commitfest application:
make installcheck-world: not tested
Implements feature: not tested
Spec compliant: not tested
Documentation: not tested

I've built and tested this, and it seems to function correctly to me. One question I have is whether the added "IS NOT NULL" filters can be omitted when they're unnecessary. Some of the resulting plans included an "IS NOT NULL" filter on a non-nullable column. To be clear, this is still an improvement (to me) without that.

Here's the simple test script I ran, on master ("before") and with the latest patch applied ("after").

CREATE TABLE users (id BIGINT PRIMARY KEY, nullable_int BIGINT UNIQUE, some_non_nullable_int BIGINT NOT NULL);
CREATE VIEW only_some_users AS (SELECT * FROM users WHERE id < 10);
CREATE VIEW some_other_users AS (SELECT * FROM users WHERE id > 3);

EXPLAIN SELECT *
FROM users u1
INNER JOIN users u2
ON u1.id = u2.id;
-- before does HASH JOIN
-- after does seq scan with "id IS NOT NULL" condition

EXPLAIN SELECT *
FROM only_some_users
INNER JOIN some_other_users
ON only_some_users.id = some_other_users.id;
-- before does HASH JOIN
-- after does no JOIN, instead does scan, with an extra "id IS NOT NULL condition" (in addition to id < 10, id > 3)

EXPLAIN SELECT *
FROM users u1
INNER JOIN users u2
ON u1.nullable_int = u2.nullable_int;
-- before does HASH JOIN
-- after does scan with (nullable_int IS NOT NULL) filter

EXPLAIN SELECT *
FROM users u1
INNER JOIN users u2
ON u1.id = u2.nullable_int;
-- before does HASH JOIN
-- after correctly unchanged

EXPLAIN SELECT *
FROM users u1
INNER JOIN users u2
ON u1.id = u2.some_non_nullable_int
INNER JOIN users u3
ON u2.some_non_nullable_int = u3.id;
-- before does 2x HASH JOIN
-- now does 1x HASH JOIN, with a sequential scan over users filtered by id IS NOT NULL

On 12/3/21 14:05, Hywel Carver wrote:
> I've built and tested this, and it seems to function correctly to me. One question I have is whether the added "IS NOT NULL" filters can be omitted when they're unnecessary. Some of the resulting plans included an "IS NOT NULL" filter on a non-nullable column. To be clear, this is still an improvement (to me) without that.

New version of the feature. Deeply refactored with main goal - to reduce
the code size) and rebased on current master.

Here I didn't work on 'unnecessary IS NOT NULL filter'.

--
regards,
Andrey Lepikhov
Postgres Professional

On 5/8/21 2:00 AM, Hywel Carver wrote:
> On Fri, May 7, 2021 at 8:23 AM Andrey Lepikhov
> <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
> Here I didn't work on 'unnecessary IS NOT NULL filter'.
>
> I've tested the new patch, and it is giving the same improved behaviour
> as the old patch.
Thank you for this efforts!

I cleaned the code of previous version, improved regression tests and
rebased on current master.

Also, I see that we could do additional optimizations for an
EC-generated selfjoin clause (See equivclass.patch for necessary
changes). Example:
explain (costs off)
select * from sj t1, sj t2 where t1.a = t1.b and t1.b = t2.b and t2.b =
t2.a;
QUERY PLAN
-----------------------------------------------------
Seq Scan on sj t2
Filter: ((a IS NOT NULL) AND (b = a) AND (a = b))
(2 rows)

But I'm not sure that this patch need to be a part of the self-join
removal feature because of code complexity.

--
regards,
Andrey Lepikhov
Postgres Professional

On 12/3/21 12:05, Hywel Carver wrote:
> I've built and tested this, and it seems to function correctly to me. One question I have is whether the added "IS NOT NULL" filters can be omitted when they're unnecessary. Some of the resulting plans included an "IS NOT NULL" filter on a non-nullable column. To be clear, this is still an improvement (to me) without that.
I think, here we could ask more general question: do we want to remove a
'IS NOT NULL' clause from the clause list if the rest of the list
implicitly implies it?

Right now we don't analyze list of clauses at all:
CREATE TABLE a (x int);

EXPLAIN (COSTS OFF)
SELECT * FROM a WHERE (x < 1) AND (X
IS NOT NULL) AND
(x < 1) AND (X IS NOT NULL);
QUERY PLAN
-------------------------------------------------------------------------
Seq Scan on a
Filter: ((x IS NOT NULL) AND (x IS NOT NULL) AND (x < 1) AND (x < 1))

And even worse:
EXPLAIN (ANALYZE, VERBOSE)
SELECT *
FROM a WHERE (X IS NOT NULL) AND (X IS NULL);
QUERY PLAN

----------------------------------------------------------------------------------------------------
Seq Scan on public.a (cost=0.00..15.00 rows=87 width=4) (actual
time=0.136..0.136 rows=0 loops=1)
Output: x
Filter: ((a.x IS NOT NULL) AND (a.x IS NULL))
Rows Removed by Filter: 1000

It could reduce a number of selectivity mistakes, but increase CPU
consumption.
If we had such a clause analyzing machinery, we could trivially remove
this unneeded qual.

--
regards,
Andrey Lepikhov
Postgres Professional

On Wed, 2021-06-30 at 14:21 +0300, Andrey Lepikhov wrote:
> I think, here we could ask more general question: do we want to remove a
> 'IS NOT NULL' clause from the clause list if the rest of the list
> implicitly implies it?
>
> EXPLAIN (ANALYZE, VERBOSE)
> SELECT *
> FROM a WHERE (X IS NOT NULL) AND (X IS NULL);
> QUERY PLAN
>
> ----------------------------------------------------------------------------------------------------
> Seq Scan on public.a (cost=0.00..15.00 rows=87 width=4) (actual time=0.136..0.136 rows=0 loops=1)
> Output: x
> Filter: ((a.x IS NOT NULL) AND (a.x IS NULL))
> Rows Removed by Filter: 1000
>
> It could reduce a number of selectivity mistakes, but increase CPU
> consumption.
> If we had such a clause analyzing machinery, we could trivially remove
> this unneeded qual.

On the other hand, sometimes something like that can be used to change
the optimizer's estimates to encourage certain plans.

We also don't optimize "ORDER BY x + 0" (which now you can use to prevent
an index scan) or the famous OFFSET 0, partly because it saves planning time,
partly because those can be useful tools.

Generally I have the impression that we are not too keen on spending
planning time on optimizing cases that can be trivially improved by rewriting
the query.

Yours,
Laurenz Albe

On 30/6/21 18:55, Laurenz Albe wrote:
> On Wed, 2021-06-30 at 14:21 +0300, Andrey Lepikhov wrote:
>> I think, here we could ask more general question: do we want to remove a
>> 'IS NOT NULL' clause from the clause list if the rest of the list
>> implicitly implies it?
> Generally I have the impression that we are not too keen on spending
> planning time on optimizing cases that can be trivially improved by rewriting
> the query.
Thank you, It's strong argument.
Such feature would look better as a part of an enterprise edition.

--
regards,
Andrey Lepikhov
Postgres Professional

> Generally I have the impression that we are not too keen on spending
> planning time on optimizing cases that can be trivially improved by
> rewriting the query.

Well in some cases they can't, when the query is not emitting redundant
predicates by itself but they are added by something else like a view or a RLS
policy.
Maybe it would be worth it to allow spending a bit more time planning for
those cases ?

Regards,

--
Ronan Dunklau

On Wed, Jun 30, 2021 at 12:21 PM Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru>
wrote:

> On 12/3/21 12:05, Hywel Carver wrote:
> > I've built and tested this, and it seems to function correctly to me.
> One question I have is whether the added "IS NOT NULL" filters can be
> omitted when they're unnecessary. Some of the resulting plans included an
> "IS NOT NULL" filter on a non-nullable column. To be clear, this is still
> an improvement (to me) without that.

I think, here we could ask more general question: do we want to remove a
> 'IS NOT NULL' clause from the clause list if the rest of the list
> implicitly implies it?

My suggestion was not to remove it, but to avoid adding it in the first
place. When your optimisation has found a join on a group of columns under
a uniqueness constraint, you would do something like this (forgive the
pseudo-code)

foreach(column, join_clause) {
if(column.nullable) { // This condition is what I'm suggesting is added
add_null_test(column, IS_NOT_NULL);
}
}

But it may be that that's not possible or practical at this point in the
code.

On 2/7/21 01:56, Hywel Carver wrote:
> On Wed, Jun 30, 2021 at 12:21 PM Andrey Lepikhov
> <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
> I think, here we could ask more general question: do we want to
> remove a
> 'IS NOT NULL' clause from the clause list if the rest of the list
> implicitly implies it?
>
>
> My suggestion was not to remove it, but to avoid adding it in the first
> place. When your optimisation has found a join on a group of columns
> under a uniqueness constraint, you would do something like this (forgive
> the pseudo-code)
>
> foreach(column, join_clause) {
>   if(column.nullable) { // This condition is what I'm suggesting is added
>     add_null_test(column, IS_NOT_NULL);
>   }
> }
>
> But it may be that that's not possible or practical at this point in the
> code.
I think, such option will require to implement a new machinery to prove
that arbitrary column couldn't produce NULL value.

--
regards,
Andrey Lepikhov
Postgres Professional

On Mon, Jul 5, 2021 at 2:20 PM Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru>
wrote:

> On 2/7/21 01:56, Hywel Carver wrote:
> > On Wed, Jun 30, 2021 at 12:21 PM Andrey Lepikhov
> > <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
> > I think, here we could ask more general question: do we want to
> > remove a
> > 'IS NOT NULL' clause from the clause list if the rest of the list
> > implicitly implies it?
> >
> >
> > My suggestion was not to remove it, but to avoid adding it in the first
> > place. When your optimisation has found a join on a group of columns
> > under a uniqueness constraint, you would do something like this (forgive
> > the pseudo-code)
> >
> > foreach(column, join_clause) {
> > if(column.nullable) { // This condition is what I'm suggesting is
> added
> > add_null_test(column, IS_NOT_NULL);
> > }
> > }
> >
> > But it may be that that's not possible or practical at this point in the
> > code.
> I think, such option will require to implement a new machinery to prove
> that arbitrary column couldn't produce NULL value.
>

Got it, and it makes sense to me that this would be out of scope for this
change.

I remember in the previous conversation about this, Tomas acknowledged that
while there are some silly queries that would benefit from this change,
there are also some well-written ones (e.g. properly denormalised table
structures, with decomposed views that need joining together in some
queries). So the optimization needs to be essentially free to run to
minimise impact on other queries.

Looking through the email chain, a previous version of this patch added
~0.6% to planning time in the worst case tested - does that meet the
"essentially free" requirement?

On Thu, May 27, 2021 at 12:21 PM Andrey V. Lepikhov
<a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
>
> On 5/8/21 2:00 AM, Hywel Carver wrote:
> > On Fri, May 7, 2021 at 8:23 AM Andrey Lepikhov
> > <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
> > Here I didn't work on 'unnecessary IS NOT NULL filter'.
> >
> > I've tested the new patch, and it is giving the same improved behaviour
> > as the old patch.
> Thank you for this efforts!
>
> I cleaned the code of previous version, improved regression tests and
> rebased on current master.
>
> Also, I see that we could do additional optimizations for an
> EC-generated selfjoin clause (See equivclass.patch for necessary
> changes). Example:
> explain (costs off)
> select * from sj t1, sj t2 where t1.a = t1.b and t1.b = t2.b and t2.b =
> t2.a;
> QUERY PLAN
> -----------------------------------------------------
> Seq Scan on sj t2
> Filter: ((a IS NOT NULL) AND (b = a) AND (a = b))
> (2 rows)
>
> But I'm not sure that this patch need to be a part of the self-join
> removal feature because of code complexity.

The patch does not apply on Head anymore, could you rebase and post a
patch. I'm changing the status to "Waiting for Author".

Regards,
Vignesh

On 6/7/21 13:49, Hywel Carver wrote:
> On Mon, Jul 5, 2021 at 2:20 PM Andrey Lepikhov
> <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
> Looking through the email chain, a previous version of this patch added
> ~0.6% to planning time in the worst case tested - does that meet the
> "essentially free" requirement?
I think these tests weren't full coverage of possible use cases. It will
depend on a number of relations in the query. For the JOIN of
partitioned tables, for example, the overhead could grow. But in the
context of overall planning time this overhead will be small till the
large number of relations.
Also, we made this feature optional to solve possible problems.
Rebased on 768ea9bcf9

--
regards,
Andrey Lepikhov
Postgres Professional

On Thu, Jul 15, 2021 at 7:49 AM Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru>
wrote:

> On 6/7/21 13:49, Hywel Carver wrote:
> > On Mon, Jul 5, 2021 at 2:20 PM Andrey Lepikhov
> > <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
> > Looking through the email chain, a previous version of this patch added
> > ~0.6% to planning time in the worst case tested - does that meet the
> > "essentially free" requirement?
> I think these tests weren't full coverage of possible use cases. It will
> depend on a number of relations in the query. For the JOIN of
> partitioned tables, for example, the overhead could grow. But in the
> context of overall planning time this overhead will be small till the
> large number of relations.
> Also, we made this feature optional to solve possible problems.
> Rebased on 768ea9bcf9
>
> --
> regards,
> Andrey Lepikhov
> Postgres Professional
>
Hi,

bq. We can proof the uniqueness

proof -> prove

1. Collect all mergejoinable join quals looks like a.x = b.x

quals looks like -> quals which look like

For update_ec_sources(), the variable cc is not used.

Cheers

On Thu, Jul 15, 2021 at 8:25 AM Zhihong Yu <zyu(at)yugabyte(dot)com> wrote:

>
>
> On Thu, Jul 15, 2021 at 7:49 AM Andrey Lepikhov <a(dot)lepikhov(at)postgrespro(dot)ru>
> wrote:
>
>> On 6/7/21 13:49, Hywel Carver wrote:
>> > On Mon, Jul 5, 2021 at 2:20 PM Andrey Lepikhov
>> > <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
>> > Looking through the email chain, a previous version of this patch added
>> > ~0.6% to planning time in the worst case tested - does that meet the
>> > "essentially free" requirement?
>> I think these tests weren't full coverage of possible use cases. It will
>> depend on a number of relations in the query. For the JOIN of
>> partitioned tables, for example, the overhead could grow. But in the
>> context of overall planning time this overhead will be small till the
>> large number of relations.
>> Also, we made this feature optional to solve possible problems.
>> Rebased on 768ea9bcf9
>>
>> --
>> regards,
>> Andrey Lepikhov
>> Postgres Professional
>>
> Hi,
>
> bq. We can proof the uniqueness
>
> proof -> prove
>
> 1. Collect all mergejoinable join quals looks like a.x = b.x
>
> quals looks like -> quals which look like
>
> For update_ec_sources(), the variable cc is not used.
>
> Cheers
>
Hi,

+ *otherjoinquals = rjoinquals;

Maybe rename rjoinquals as ojoinquals to align with the target variable
name.

+ int k; /* Index of kept relation */
+ int r = -1; /* Index of removed relation */

Naming k as kept, r as removed would make the code more readable (remain
starts with r but has opposite meaning).

+ if (bms_is_member(r, info->syn_righthand) &&
+ !bms_is_member(k, info->syn_righthand))
+ jinfo_check = false;
+
+ if (!jinfo_check)
+ break;

There are 4 if statements where jinfo_check is assigned false. Once
jinfo_check is assigned, we can break out of the loop - instead of checking
the remaining conditions.

+ else if (!innerrel_is_unique(root, joinrelids, outer->relids,

nit: the 'else' is not needed since the if block above it goes to next
iteration of the loop.

+ /* See for row marks. */
+ foreach (lc, root->rowMarks)

It seems once imark and omark are set, we can come out of the loop.

Cheers

On 7/16/21 12:28 AM, Zhihong Yu wrote:
>
>
> On Thu, Jul 15, 2021 at 8:25 AM Zhihong Yu <zyu(at)yugabyte(dot)com
> <mailto:zyu(at)yugabyte(dot)com>> wrote:
> bq. We can proof the uniqueness
>
> proof -> prove
Fixed
>
> 1. Collect all mergejoinable join quals looks like a.x = b.x
>
>  quals looks like -> quals which look like
>
> For update_ec_sources(), the variable cc is not used.
Fixed
> +   *otherjoinquals = rjoinquals;
>
> Maybe rename rjoinquals as ojoinquals to align with the target variable
> name.
Agree, fixed
>
> +   int k; /* Index of kept relation */
> +   int r = -1; /* Index of removed relation */
>
> Naming k as kept, r as removed would make the code more readable (remain
> starts with r but has opposite meaning).
I think it is correct now: k - index of inner (keeping) relation. r - of
outer (removing) relation.
>
> +               if (bms_is_member(r, info->syn_righthand) &&
> +                   !bms_is_member(k, info->syn_righthand))
> +                   jinfo_check = false;
> +
> +               if (!jinfo_check)
> +                   break;
>
> There are 4 if statements where jinfo_check is assigned false. Once
> jinfo_check is assigned, we can break out of the loop - instead of
> checking the remaining conditions.
Fixed
>
> +           else if (!innerrel_is_unique(root, joinrelids, outer->relids,
>
> nit: the 'else' is not needed since the if block above it goes to next
> iteration of the loop.
Fixed
>
> +           /* See for row marks. */
> +           foreach (lc, root->rowMarks)
>
> It seems once imark and omark are set, we can come out of the loop.
Maybe you right. fixed.

--
regards,
Andrey Lepikhov
Postgres Professional

On Thu, 1 Jul 2021 at 02:38, Ronan Dunklau <ronan(dot)dunklau(at)aiven(dot)io> wrote:
>
> Well in some cases they can't, when the query is not emitting redundant
> predicates by itself but they are added by something else like a view or a RLS
> policy.
> Maybe it would be worth it to allow spending a bit more time planning for
> those cases ?

Yeah, I'm generally in favour of doing more work in the optimizer to
save query authors work writing queries.

My question is whether it handles cases like:

select b.x,c.y
from t
join t2 as b on (b.id = t.id)
join t2 as c on (c.id = t.id)

That is, if you join against the same table twice on the same qual.
Does the EC mechanism turn this into a qual on b.id = c.id and then
turn this into a self-join that can be removed?

That's the usual pattern I've seen this arise. Not so much that people
write self joins explicitly but that they add a join to check some
column but that is happening in some isolated piece of code that
doesn't know that that join is already in the query. You can easily
end up with a lot of joins against the same table this way.

It's not far different from the old chestnut

select (select x from t2 where id = t.id) as x,
(select y from t2 where id = t.id) as y
from t

which is actually pretty hard to avoid sometimes.

--
greg

On Thu, Jul 15, 2021 at 05:49:11PM +0300, Andrey Lepikhov wrote:
> On 6/7/21 13:49, Hywel Carver wrote:
> > On Mon, Jul 5, 2021 at 2:20 PM Andrey Lepikhov
> > <a(dot)lepikhov(at)postgrespro(dot)ru <mailto:a(dot)lepikhov(at)postgrespro(dot)ru>> wrote:
> > Looking through the email chain, a previous version of this patch added
> > ~0.6% to planning time in the worst case tested - does that meet the
> > "essentially free" requirement?
> I think these tests weren't full coverage of possible use cases. It will
> depend on a number of relations in the query. For the JOIN of partitioned
> tables, for example, the overhead could grow. But in the context of overall
> planning time this overhead will be small till the large number of
> relations.
> Also, we made this feature optional to solve possible problems.
> Rebased on 768ea9bcf9
>

I made some tests in a machine with 16 cores and 32GB of RAM.
So we can see if this is an improvement.

This is what I found:

+-----------------------+----------+-----------+-----------+-------+-----------+-------+
| test | mode | master | enabled | % | disabled | % |
+-----------------------+----------+-----------+-----------+-------+-----------+-------+
| pgbench read only | standard | 64418.13 | 63942.94 | -0.74 | 62231.38 | -3.39 |
| pgbench read only | prepared | 108463.51 | 107002.13 | -1.35 | 100960.83 | -6.92 |
| pgbench read only | extended | 55409.65 | 56427.63 | 1.84 | 55927.62 | 0.93 |
+-----------------------+----------+-----------+-----------+-------+-----------+-------+
| pgbench read/write | standard | 9374.91 | 9135.21 | -2.56 | 8840.68 | -5.70 |
| pgbench read/write | prepared | 11849.86 | 11672.23 | -1.50 | 11393.39 | -3.85 |
| pgbench read/write | extended | 7976.80 | 7947.07 | -0.37 | 7788.99 | -2.35 |
+-----------------------+----------+-----------+-----------+-------+-----------+-------+
| select non optimize 1 | standard | 80.97 | 81.29 | 0.40 | 81.30 | 0.41 |
| select non optimize 1 | prepared | 81.29 | 81.28 | -0.01 | 80.89 | -0.49 |
| select non optimize 1 | extended | 81.07 | 80.81 | -0.32 | 80.98 | -0.11 |
+-----------------------+----------+-----------+-----------+-------+-----------+-------+
| select optimized 1 | standard | 15.84 | 13.90 |-12.25 | 15.80 | -0.25 |
| select optimized 1 | prepared | 15.24 | 13.82 | -9.32 | 15.55 | 2.03 |
| select optimized 1 | extended | 15.38 | 13.89 | -9.69 | 15.59 | 1.37 |
+-----------------------+----------+-----------+-----------+-------+-----------+-------+
| select optimized 2 | standard | 10204.91 | 10818.39 | 6.01 | 10261.07 | 0.55 |
| select optimized 2 | prepared | 13284.06 | 15579.33 | 17.28 | 13116.22 | -1.26 |
| select optimized 2 | extended | 10143.43 | 10645.23 | 4.95 | 10142.77 | -0.01 |
+-----------------------+----------+-----------+-----------+-------+-----------+-------+
| select shoe | standard | 5645.28 | 5661.71 | 0.29 | 6180.60 | 9.48 |
| select shoe | prepared | 9660.45 | 9602.37 | -0.60 | 9894.82 | 2.43 |
| select shoe | extended | 5666.47 | 5634.10 | -0.57 | 5757.26 | 1.60 |
+-----------------------+----------+-----------+-----------+-------+-----------+-------+

Obviously the pgbench runs are from the standard script. The numbers are
not clear for me, I can see improvementes with the patch only in one
case and, for some reason, if I disable the patch
(enable_self_join_removal='off') I still see a regression in normal
cases and curiosly an improvement in one case.

I'm attaching the queries. I used the users table that is down-thread
and loaded with ~200k rows using:

insert into users
select seq, case when random() < 0.2 then null else random() * 1000 end,
random() * 10000
from generate_series(1, 1000000) seq
on conflict (nullable_int) do nothing;

for master I just dumped the data from the table and loaded it. I'm also
attaching the queries I used.

After this tests, I'm not convinced this is actually providing something
performance-wise. At least not in its current state.

--
Jaime Casanova
Director de Servicios Profesionales
SystemGuards - Consultores de PostgreSQL

I don't think the benchmarking that's needed is to check whether
pruning unnecessary joins is helpful. Obviously it's going to be hard
to measure on simple queries and small tables. But the resulting plan
is unambiguously superior and in more complex cases could extra i/o.

The benchmarking people were looking for in the past was testing the
impact of the extra planning work in cases where it doesn't end up
being applied. I'm not sure what the worst case is, perhaps a many-way
self-join where the join clauses are not suitable for pruning?

On 1/3/2022 03:03, Greg Stark wrote:
> On Thu, 1 Jul 2021 at 02:38, Ronan Dunklau <ronan(dot)dunklau(at)aiven(dot)io> wrote:
>>
>> Well in some cases they can't, when the query is not emitting redundant
>> predicates by itself but they are added by something else like a view or a RLS
>> policy.
>> Maybe it would be worth it to allow spending a bit more time planning for
>> those cases ?
>
> Yeah, I'm generally in favour of doing more work in the optimizer to
> save query authors work writing queries.
>
> My question is whether it handles cases like:
>
> select b.x,c.y
> from t
> join t2 as b on (b.id = t.id)
> join t2 as c on (c.id = t.id)
>
> That is, if you join against the same table twice on the same qual.
> Does the EC mechanism turn this into a qual on b.id = c.id and then
> turn this into a self-join that can be removed?
Yes, the self-join removal machinery uses EC mechanism as usual to get
all join clauses. So, this case works (See demo in attachment).

Also, in new version of the patch I fixed one stupid bug: checking a
self-join candidate expression operator - we can remove only expressions
like F(arg1) = G(arg2).

--
regards,
Andrey Lepikhov
Postgres Professional

Hi,

On 2022-03-04 15:47:47 +0500, Andrey Lepikhov wrote:
> Also, in new version of the patch I fixed one stupid bug: checking a
> self-join candidate expression operator - we can remove only expressions
> like F(arg1) = G(arg2).

This CF entry currently fails tests: https://cirrus-ci.com/task/4632127944785920?logs=test_world#L1938

Looks like you're missing an adjustment of postgresql.conf.sample

Marked as waiting-on-author.

Greetings,

Andres Freund

On 3/22/22 05:58, Andres Freund wrote:
> Hi,
>
> On 2022-03-04 15:47:47 +0500, Andrey Lepikhov wrote:
>> Also, in new version of the patch I fixed one stupid bug: checking a
>> self-join candidate expression operator - we can remove only expressions
>> like F(arg1) = G(arg2).
>
> This CF entry currently fails tests: https://cirrus-ci.com/task/4632127944785920?logs=test_world#L1938
>
> Looks like you're missing an adjustment of postgresql.conf.sample
>
> Marked as waiting-on-author.
Thanks, I fixed it.

--
regards,
Andrey Lepikhov
Postgres Professional

Sigh. And now there's a patch conflict in a regression test expected
output: sysviews.out

Please rebase. Incidentally, make sure to check the expected output is
actually correct. It's easy to "fix" an expected output to
accidentally just memorialize an incorrect output.

Btw, it's the last week before feature freeze so time is of the essence.

On 4/1/22 20:27, Greg Stark wrote:
> Sigh. And now there's a patch conflict in a regression test expected
> output: sysviews.out
>
> Please rebase. Incidentally, make sure to check the expected output is
> actually correct. It's easy to "fix" an expected output to
> accidentally just memorialize an incorrect output.
>
> Btw, it's the last week before feature freeze so time is of the essence.Thanks,
patch in attachment rebased on current master.
Sorry for late answer.

--
regards,
Andrey Lepikhov
Postgres Professional

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?

--
Regards
Andrey Lepikhov
Postgres Professional

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.

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.
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.

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.

I'll update if I think of more interesting things to add.

--
Ronan Dunklau

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.
> 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 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
zyu(at)yugabyte(dot)com(dot)

[1]
/message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXeErW5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com

--
Regards
Andrey Lepikhov
Postgres Professional

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
> zyu(at)yugabyte(dot)com(dot)
>
> [1]
> /message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXeErW
> 5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com

--
Ronan Dunklau

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 Professional

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] /message-id/flat/830269.1656693747%40sss.pgh.pa.us

--
Ronan Dunklau

On Mon, Jul 4, 2022 at 6:52 AM Ronan Dunklau <ronan(dot)dunklau(at)aiven(dot)io> 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]
> /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

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 Professional

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

>

On Fri, Aug 26, 2022 at 3:02 PM Zhihong Yu <zyu(at)yugabyte(dot)com> 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

On 8/29/22 04:39, Zhihong Yu wrote:
>
>
> On Fri, Aug 26, 2022 at 3:02 PM Zhihong Yu <zyu(at)yugabyte(dot)com
> <mailto:zyu(at)yugabyte(dot)com>> 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 Professional

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

--
regards,
Andrey Lepikhov
Postgres Professional

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 +0000
+++ /tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out 2022-12-05 19:15:21.864183651 +0000
@@ -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

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 +0000
> +++ /tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out 2022-12-05 19:15:21.864183651 +0000
> @@ -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

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 <a(dot)lepikhov(at)postgrespro(dot)ru> 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 +0000
>> +++ /tmp/cirrus-ci-build/build/testrun/regress/regress/results/join.out 2022-12-05 19:15:21.864183651 +0000
>> @@ -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
> <v39-0001-Remove-self-joins.patch>

On Mon, 6 Mar 2023 at 00:30, Michał Kłeczek <michal(at)kleczek(dot)org> 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

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

On 4/4/2023 02:30, Gregory Stark (as CFM) wrote:
> On Mon, 6 Mar 2023 at 00:30, Michał Kłeczek <michal(at)kleczek(dot)org> 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.