Обсуждение: 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] https://www.postgresql.org/message-id/flat/CAMjNa7cC4X9YR-vAJS-jSYCajhRDvJQnN7m2sLH1wLh-_Z2bsw%40mail.gmail.com#CAMjNa7cC4X9YR-vAJS-jSYCajhRDvJQnN7m2sLH1wLh-_Z2bsw@mail.gmail.com -- Alexander Kuzmenkov Postgres Professional: http://www.postgrespro.com The Russian Postgres Company
Вложения
Alexander Kuzmenkov <a.kuzmenkov@postgrespro.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@sss.pgh.pa.us> wrote: > Alexander Kuzmenkov <a.kuzmenkov@postgrespro.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@gmail.com> wrote: > On Wed, May 16, 2018 at 12:08 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote: >> Alexander Kuzmenkov <a.kuzmenkov@postgrespro.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@2ndquadrant.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@anarazel.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@sss.pgh.pa.us> wrote: > Simon Riggs <simon@2ndquadrant.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.kuzmenkov@postgrespro.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@2ndquadrant.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.kuzmenkov@postgrespro.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@2ndquadrant.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.rowley@2ndquadrant.com> writes:
> On 17 May 2018 at 08:44, Simon Riggs <simon@2ndquadrant.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@sss.pgh.pa.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.munro@enterprisedb.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.munro@enterprisedb.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@sss.pgh.pa.us> wrote: > Thomas Munro <thomas.munro@enterprisedb.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.rowley@2ndquadrant.com> writes:
> On 17 May 2018 at 10:13, Tom Lane <tgl@sss.pgh.pa.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.rowley@2ndquadrant.com> writes: > > On 17 May 2018 at 10:13, Tom Lane <tgl@sss.pgh.pa.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@sss.pgh.pa.us> wrote: > David Rowley <david.rowley@2ndquadrant.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] https://www.postgresql.org/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@anarazel.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.rowley@2ndquadrant.com> writes:
> On 17 May 2018 at 11:00, Andres Freund <andres@anarazel.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.rowley@2ndquadrant.com> writes: > > On 17 May 2018 at 11:00, Andres Freund <andres@anarazel.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.rowley@2ndquadrant.com> writes: >>> On 17 May 2018 at 11:00, Andres Freund <andres@anarazel.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@sss.pgh.pa.us> wrote: > David Rowley <david.rowley@2ndquadrant.com> writes: >> On 17 May 2018 at 08:44, Simon Riggs <simon@2ndquadrant.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.kuzmenkov@postgrespro.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 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.kuzmenkov@postgrespro.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.kuzmenkov@postgrespro.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.kuzmenkov@postgrespro.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
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 3434219..86c9453 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3583,7 +3583,8 @@ ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
* relation_has_unique_index_for
* Determine whether the relation provably has at most one row satisfying
* a set of equality conditions, because the conditions constrain all
- * columns of some unique index.
+ * columns of some unique index. If index_info is not null, it is set to
+ * point to a new UniqueIndexInfo containing the index and conditions.
*
* The conditions can be represented in either or both of two ways:
* 1. A list of RestrictInfo nodes, where the caller has already determined
@@ -3604,7 +3605,8 @@ ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
bool
relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
List *restrictlist,
- List *exprlist, List *oprlist)
+ List *exprlist, List *oprlist,
+ UniqueIndexInfo **index_info)
{
ListCell *ic;
@@ -3660,6 +3662,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
{
IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
int c;
+ List *matched_restrictlist = NIL;
/*
* If the index is not unique, or not immediately enforced, or if it's
@@ -3708,6 +3711,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
if (match_index_to_operand(rexpr, c, ind))
{
matched = true; /* column is unique */
+ matched_restrictlist = lappend(matched_restrictlist, rinfo);
break;
}
}
@@ -3750,7 +3754,22 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
/* Matched all key columns of this index? */
if (c == ind->nkeycolumns)
+ {
+ if (index_info != NULL)
+ {
+ /* This may be called in GEQO memory context. */
+ MemoryContext oldContext = MemoryContextSwitchTo(root->planner_cxt);
+ *index_info = palloc(sizeof(UniqueIndexInfo));
+ (*index_info)->index = ind;
+ (*index_info)->clauses = list_copy(matched_restrictlist);
+ MemoryContextSwitchTo(oldContext);
+ }
+ if (matched_restrictlist)
+ list_free(matched_restrictlist);
return true;
+ }
+ if (matched_restrictlist)
+ list_free(matched_restrictlist);
}
return false;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index d8ff4bf..89cd236 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -176,7 +176,8 @@ add_paths_to_joinrel(PlannerInfo *root,
innerrel,
JOIN_INNER,
restrictlist,
- false);
+ false,
+ NULL /*index_info*/);
break;
default:
extra.inner_unique = innerrel_is_unique(root,
@@ -185,7 +186,8 @@ add_paths_to_joinrel(PlannerInfo *root,
innerrel,
jointype,
restrictlist,
- false);
+ false,
+ NULL /*index_info*/);
break;
}
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index a4efa69..19e5139 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -22,6 +22,7 @@
*/
#include "postgres.h"
+#include "catalog/pg_class.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/joininfo.h"
@@ -39,14 +40,15 @@ static void remove_rel_from_query(PlannerInfo *root, int relid,
static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
- List *clause_list);
+ List *clause_list, UniqueIndexInfo **info);
static Oid distinct_col_search(int colno, List *colnos, List *opids);
static bool is_innerrel_unique_for(PlannerInfo *root,
Relids joinrelids,
Relids outerrelids,
RelOptInfo *innerrel,
JoinType jointype,
- List *restrictlist);
+ List *restrictlist,
+ UniqueIndexInfo **info);
/*
@@ -58,7 +60,7 @@ static bool is_innerrel_unique_for(PlannerInfo *root,
* data structures that have to be updated are accessible via "root".
*/
List *
-remove_useless_joins(PlannerInfo *root, List *joinlist)
+remove_useless_left_joins(PlannerInfo *root, List *joinlist)
{
ListCell *lc;
@@ -162,7 +164,6 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
int innerrelid;
RelOptInfo *innerrel;
Relids joinrelids;
- List *clause_list = NIL;
ListCell *l;
int attroff;
@@ -238,67 +239,24 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
}
/*
- * Search for mergejoinable clauses that constrain the inner rel against
- * either the outer rel or a pseudoconstant. If an operator is
- * mergejoinable then it behaves like equality for some btree opclass, so
- * it's what we want. The mergejoinability test also eliminates clauses
- * containing volatile functions, which we couldn't depend on.
+ * Check for pushed-down clauses referencing the inner rel. If there is
+ * such a clause then join removal has to be disallowed. We have to
+ * check this despite the previous attr_needed checks because of the
+ * possibility of pushed-down clauses referencing the rel.
*/
foreach(l, innerrel->joininfo)
{
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
-
- /*
- * If it's not a join clause for this outer join, we can't use it.
- * Note that if the clause is pushed-down, then it is logically from
- * above the outer join, even if it references no other rels (it might
- * be from WHERE, for example).
- */
- if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
- {
- /*
- * If such a clause actually references the inner rel then join
- * removal has to be disallowed. We have to check this despite
- * the previous attr_needed checks because of the possibility of
- * pushed-down clauses referencing the rel.
- */
- if (bms_is_member(innerrelid, restrictinfo->clause_relids))
+ if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids)
+ && bms_is_member(innerrel->relid, restrictinfo->clause_relids))
return false;
- continue; /* else, ignore; not useful here */
- }
-
- /* Ignore if it's not a mergejoinable clause */
- if (!restrictinfo->can_join ||
- restrictinfo->mergeopfamilies == NIL)
- continue; /* not mergejoinable */
-
- /*
- * Check if clause has the form "outer op inner" or "inner op outer",
- * and if so mark which side is inner.
- */
- if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
- innerrel->relids))
- continue; /* no good for these input relations */
-
- /* OK, add to list */
- clause_list = lappend(clause_list, restrictinfo);
}
- /*
- * Now that we have the relevant equality join clauses, try to prove the
- * innerrel distinct.
- */
- if (rel_is_distinct_for(root, innerrel, clause_list))
- return true;
-
- /*
- * Some day it would be nice to check for other methods of establishing
- * distinctness.
- */
- return false;
+ return is_innerrel_unique_for(root, joinrelids, sjinfo->min_lefthand,
+ innerrel, sjinfo->jointype, innerrel->joininfo,
+ NULL /*unique_index*/);
}
-
/*
* Remove the target relid from the planner's data structures, having
* determined that there is no need to include it in the query.
@@ -568,7 +526,7 @@ reduce_unique_semijoins(PlannerInfo *root)
/* Test whether the innerrel is unique for those clauses. */
if (!innerrel_is_unique(root,
joinrelids, sjinfo->min_lefthand, innerrel,
- JOIN_SEMI, restrictlist, true))
+ JOIN_SEMI, restrictlist, true, NULL /*index_info*/))
continue;
/* OK, remove the SpecialJoinInfo from the list. */
@@ -643,9 +601,13 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
* Note that the passed-in clause_list may be destructively modified! This
* is OK for current uses, because the clause_list is built by the caller for
* the sole purpose of passing to this function.
+ *
+ * If unique_index is not null, it is set to point to the index that guarantees
+ * uniqueness for a base relation.
*/
static bool
-rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
+rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
+ UniqueIndexInfo **index_info)
{
/*
* We could skip a couple of tests here if we assume all callers checked
@@ -661,8 +623,8 @@ rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
* relation_has_unique_index_for automatically adds any usable
* restriction clauses for the rel, so we needn't do that here.
*/
- if (relation_has_unique_index_for(root, rel, clause_list, NIL, NIL))
- return true;
+ return relation_has_unique_index_for(root, rel, clause_list, NIL, NIL,
+ index_info);
}
else if (rel->rtekind == RTE_SUBQUERY)
{
@@ -966,6 +928,10 @@ distinct_col_search(int colno, List *colnos, List *opids)
* heuristic about whether to cache negative answers; it should be "true"
* if making an inquiry that is not part of the normal bottom-up join search
* sequence.
+ *
+ * If index_info_out is not null, it is set to point to a new UniqueIndexInfo
+ * allocated in root memory context, that describes the index that guarantees
+ * uniqueness.
*/
bool
innerrel_is_unique(PlannerInfo *root,
@@ -974,12 +940,23 @@ innerrel_is_unique(PlannerInfo *root,
RelOptInfo *innerrel,
JoinType jointype,
List *restrictlist,
- bool force_cache)
+ bool force_cache,
+ UniqueIndexInfo **index_info_out)
{
MemoryContext old_context;
ListCell *lc;
+ UniqueIndexInfo *index_info;
+
+ if (index_info_out)
+ *index_info_out = NULL;
- /* Certainly can't prove uniqueness when there are no joinclauses */
+ /*
+ * It is possible to prove uniqueness even in the absence of joinclauses,
+ * just from baserestrictinfos alone. However, in these cases the inner
+ * relation returns one row at most, so join removal won't give much
+ * benefit. It seems better to save some planning time by ignoring these
+ * cases.
+ */
if (restrictlist == NIL)
return false;
@@ -999,10 +976,14 @@ innerrel_is_unique(PlannerInfo *root,
*/
foreach(lc, innerrel->unique_for_rels)
{
- Relids unique_for_rels = (Relids) lfirst(lc);
+ Relids unique_for_rels = (Relids) linitial(lfirst(lc));
if (bms_is_subset(unique_for_rels, outerrelids))
+ {
+ if (index_info_out)
+ *index_info_out = lsecond(lfirst(lc));
return true; /* Success! */
+ }
}
/*
@@ -1019,7 +1000,7 @@ innerrel_is_unique(PlannerInfo *root,
/* No cached information, so try to make the proof. */
if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
- jointype, restrictlist))
+ jointype, restrictlist, &index_info))
{
/*
* Cache the positive result for future probes, being sure to keep it
@@ -1033,9 +1014,12 @@ innerrel_is_unique(PlannerInfo *root,
*/
old_context = MemoryContextSwitchTo(root->planner_cxt);
innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
- bms_copy(outerrelids));
+ list_make2(bms_copy(outerrelids), index_info));
MemoryContextSwitchTo(old_context);
+ if (index_info_out)
+ *index_info_out = index_info;
+
return true; /* Success! */
}
else
@@ -1081,7 +1065,8 @@ is_innerrel_unique_for(PlannerInfo *root,
Relids outerrelids,
RelOptInfo *innerrel,
JoinType jointype,
- List *restrictlist)
+ List *restrictlist,
+ UniqueIndexInfo **index_info)
{
List *clause_list = NIL;
ListCell *lc;
@@ -1123,5 +1108,830 @@ is_innerrel_unique_for(PlannerInfo *root,
}
/* Let rel_is_distinct_for() do the hard work */
- return rel_is_distinct_for(root, innerrel, clause_list);
+ return rel_is_distinct_for(root, innerrel, clause_list, index_info);
+}
+
+typedef struct
+{
+ Index oldRelid;
+ Index newRelid;
+} ChangeVarnoContext;
+
+static bool
+change_varno_walker(Node *node, ChangeVarnoContext *context)
+{
+ if (node == NULL)
+ return false;
+
+ if (IsA(node, Var) && ((Var *) node)->varno == context->oldRelid)
+ {
+ ((Var *) node)->varno = context->newRelid;
+ ((Var *) node)->varnoold = context->newRelid;
+ return false;
+ }
+
+ return expression_tree_walker(node, change_varno_walker, context);
+}
+
+/*
+ * For all Vars in the expression that have varno = oldRelid, set
+ * varno = newRelid.
+ */
+static void
+change_varno(Expr *expr, Index oldRelid, Index newRelid)
+{
+ ChangeVarnoContext context;
+ context.oldRelid = oldRelid;
+ context.newRelid = newRelid;
+ change_varno_walker((Node *) expr, &context);
+}
+
+/*
+ * Substitute newId for oldId in relids.
+ */
+static void
+change_relid(Relids *relids, Index oldId, Index newId)
+{
+ if (bms_is_member(oldId, *relids))
+ *relids = bms_add_member(bms_del_member(*relids, oldId), newId);
+}
+
+/*
+ * Update EC members to point to the remaining relation instead of the removed
+ * one, removing duplicates.
+ */
+static void
+update_ec_members(EquivalenceClass *ec, Index toRemove, Index toKeep)
+{
+ ListCell *prev = NULL;
+ ListCell *cell = NULL;
+ ListCell *next = list_head(ec->ec_members);
+
+ while (next)
+ {
+ EquivalenceMember *em;
+ ListCell *otherCell;
+
+ prev = cell;
+ cell = next;
+ next = lnext(next);
+ em = lfirst(cell);
+
+ if (!bms_is_member(toRemove, em->em_relids))
+ continue;
+
+ change_relid(&em->em_relids, toRemove, toKeep);
+ /* We only process inner joins */
+ Assert(em->em_nullable_relids == NULL);
+ change_varno(em->em_expr, toRemove, toKeep);
+
+ /*
+ * After we switched the equivalence member to the remaining relation,
+ * check that it is not the same as the existing member, and if it
+ * is, delete it.
+ */
+ foreach (otherCell, ec->ec_members)
+ {
+ EquivalenceMember *other;
+
+ if (otherCell == cell)
+ continue;
+
+ other = castNode(EquivalenceMember, lfirst(otherCell));
+ if (equal(other->em_expr, em->em_expr))
+ {
+ ec->ec_members = list_delete_cell(ec->ec_members, cell, prev);
+ cell = prev;
+ break;
+ }
+ }
+ }
+}
+
+/*
+ * Update EC sources to point to the remaining relation instead of the
+ * removed one.
+ */
+static void
+update_ec_sources(List **sources, Index toRemove, Index toKeep)
+{
+ ListCell *prev = NULL;
+ ListCell *cell = NULL;
+ ListCell *next = list_head(*sources);
+
+ while (next)
+ {
+ RestrictInfo *rinfo;
+ ListCell *otherCell;
+
+ prev = cell;
+ cell = next;
+ next = lnext(next);
+ rinfo = castNode(RestrictInfo, lfirst(cell));
+
+ if (!bms_is_member(toRemove, rinfo->required_relids))
+ continue;
+
+ change_varno(rinfo->clause, toRemove, toKeep);
+
+ /*
+ * After switching the clause to the remaining relation, check it
+ * for redundancy with existing ones. We don't have to check for
+ * redundancy with derived clauses, because we've just deleted them.
+ */
+ foreach (otherCell, *sources)
+ {
+ RestrictInfo *other;
+
+ if (otherCell == cell)
+ continue;
+
+ other = castNode(RestrictInfo, lfirst(otherCell));
+ if (equal(rinfo->clause, other->clause))
+ {
+ *sources = list_delete_cell(*sources, cell, prev);
+ cell = prev;
+ break;
+ }
+ }
+
+ if (otherCell == NULL)
+ {
+ /* We will keep this RestrictInfo, correct its relids. */
+ change_relid(&rinfo->required_relids, toRemove, toKeep);
+ change_relid(&rinfo->left_relids, toRemove, toKeep);
+ change_relid(&rinfo->right_relids, toRemove, toKeep);
+ change_relid(&rinfo->clause_relids, toRemove, toKeep);
+ }
+ }
+}
+
+/*
+ * Scratch space for the unique self join removal code.
+ */
+typedef struct
+{
+ PlannerInfo *root;
+
+ /* Temporary array for relation ids. */
+ Index *relids;
+
+ /*
+ * Array of Relids, one for each relation, indexed by relation id.
+ * Each element is a set of relation ids with which this relation
+ * has a special join.
+ */
+ Relids *special_join_rels;
+
+ /* Array of row marks indexed by relid. */
+ PlanRowMark **row_marks;
+
+ /* Bitmapset for join relids that is used to avoid reallocation. */
+ Relids joinrelids;
+
+ /*
+ * Top-level targetlist of the query. We have to update any references
+ * it has to the relations we remove.
+ */
+ List *targetlist;
+} UsjScratch;
+
+/*
+ * Remove a relation after we have proven that it participates only in an
+ * unneeded unique self join.
+ *
+ * The joinclauses list is destructively changed.
+ */
+static void
+remove_self_join_rel(UsjScratch *scratch, Relids joinrelids, List *joinclauses,
+ RelOptInfo *toKeep, RelOptInfo *toRemove)
+{
+ PlannerInfo *root = scratch->root;
+ ListCell *cell;
+ List *toAppend;
+
+ /*
+ * Transfer join and restriction clauses from the removed relation to the
+ * remaining one. We change the Vars of the clause to point to the remaining
+ * relation instead of the removed one. The clauses that require a subset of
+ * joinrelids become restriction clauses of the remaining relation, and
+ * others remain join clauses. We append them to baserestrictinfo and
+ * joininfo respectively, trying not to introduce duplicates.
+ *
+ * We also have to process the 'joinclauses' list here, because it contains
+ * EC-derived join clauses which must become filter clauses. It is not enough
+ * to just correct the ECs, because the EC-derived restrictions are generated
+ * before join removal (see generate_base_implied_equalities).
+ */
+ toAppend = list_concat(joinclauses, toRemove->baserestrictinfo);
+ toAppend = list_concat(toAppend, toRemove->joininfo);
+
+ foreach(cell, toAppend)
+ {
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, cell);
+ bool is_join_clause = !bms_is_subset(rinfo->required_relids, joinrelids);
+ List **target = is_join_clause ? &toKeep->joininfo : &toKeep->baserestrictinfo;
+ ListCell *otherCell;
+
+ /* We can't have an EC-derived clause that joins to some third relation */
+ Assert( !(is_join_clause && rinfo->parent_ec != NULL) );
+
+ /*
+ * Replace the references to the removed relation with references to
+ * the remaining one. We won't necessarily add this clause, because
+ * it may be already present in the joininfo or baserestrictinfo.
+ * Still, we have to switch it to point to the remaining relation.
+ * This is important for join clauses that reference both relations,
+ * because they are included in both joininfos.
+ */
+ change_varno(rinfo->clause, toRemove->relid, toKeep->relid);
+ change_relid(&rinfo->required_relids, toRemove->relid, toKeep->relid);
+ change_relid(&rinfo->left_relids, toRemove->relid, toKeep->relid);
+ change_relid(&rinfo->right_relids, toRemove->relid, toKeep->relid);
+ change_relid(&rinfo->clause_relids, toRemove->relid, toKeep->relid);
+
+ /*
+ * Don't add the clause if it is already present in the list, or
+ * derived from the same equivalence class, or is the same as another
+ * clause.
+ */
+ foreach (otherCell, *target)
+ {
+ RestrictInfo *other = lfirst(otherCell);
+ if (other == rinfo
+ || (rinfo->parent_ec != NULL
+ && other->parent_ec == rinfo->parent_ec)
+ || equal(rinfo->clause, other->clause))
+ {
+ break;
+ }
+ }
+ if (otherCell != NULL)
+ continue;
+
+ /*
+ * If the clause has the form of "X=X", replace it with null test.
+ */
+ if (rinfo->mergeopfamilies)
+ {
+ Expr *leftOp = (Expr *) get_leftop(rinfo->clause);
+ Expr *rightOp = (Expr *) get_rightop(rinfo->clause);
+
+ if (leftOp != NULL && equal(leftOp, rightOp))
+ {
+ NullTest *test = makeNode(NullTest);
+ test->arg = leftOp;
+ test->nulltesttype = IS_NOT_NULL;
+ test->argisrow = false;
+ test->location = -1;
+ rinfo->clause = (Expr *) test;
+ }
+ }
+
+ *target = lappend(*target, rinfo);
+ }
+
+ /*
+ * Transfer the targetlist and attr_needed flags.
+ */
+ Assert(toRemove->reltarget->sortgrouprefs == 0);
+
+ foreach (cell, toRemove->reltarget->exprs)
+ {
+ Expr *node = lfirst(cell);
+ change_varno(node, toRemove->relid, toKeep->relid);
+ if (!list_member(toKeep->reltarget->exprs, node))
+ toKeep->reltarget->exprs = lappend(toKeep->reltarget->exprs,
+ node);
+ }
+
+ for (int 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]);
+ }
+
+ /*
+ * If the removed relation has a row mark, transfer it to the remaining one.
+ *
+ * If both rels have row marks, just keep the one corresponding to the
+ * remaining relation, because we verified earlier that they have the same
+ * strength.
+ *
+ * Also make sure that the scratch->row_marks cache is up to date, because
+ * we are going to use it for further join removals.
+ */
+ if (scratch->row_marks[toRemove->relid])
+ {
+ PlanRowMark **markToRemove = &scratch->row_marks[toRemove->relid];
+ PlanRowMark **markToKeep = &scratch->row_marks[toKeep->relid];
+ if (*markToKeep)
+ {
+ Assert((*markToKeep)->markType == (*markToRemove)->markType);
+
+ root->rowMarks = list_delete_ptr(root->rowMarks, *markToKeep);
+ *markToKeep = NULL;
+ }
+ else
+ {
+ *markToKeep = *markToRemove;
+ *markToRemove = NULL;
+
+ /* Shouldn't have inheritance children here. */
+ Assert((*markToKeep)->rti == (*markToKeep)->prti);
+
+ (*markToKeep)->rti = toKeep->relid;
+ (*markToKeep)->prti = toKeep->relid;
+ }
+ }
+
+ /*
+ * Likewise replace references in SpecialJoinInfo data structures.
+ *
+ * This is relevant in case the join we're deleting is nested inside
+ * some special joins: the upper joins' relid sets have to be adjusted.
+ */
+ foreach (cell, root->join_info_list)
+ {
+ SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(cell);
+
+ change_relid(&sjinfo->min_lefthand, toRemove->relid, toKeep->relid);
+ change_relid(&sjinfo->min_righthand, toRemove->relid, toKeep->relid);
+ change_relid(&sjinfo->syn_lefthand, toRemove->relid, toKeep->relid);
+ change_relid(&sjinfo->syn_righthand, toRemove->relid, toKeep->relid);
+ }
+
+ /*
+ * Likewise update references in PlaceHolderVar data structures.
+ */
+ foreach(cell, root->placeholder_list)
+ {
+ PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(cell);
+
+ /*
+ * We are at an inner join of two base relations. A placeholder
+ * can't be needed here or evaluated here.
+ */
+ Assert(!bms_is_subset(phinfo->ph_eval_at, joinrelids));
+ Assert(!bms_is_subset(phinfo->ph_needed, joinrelids));
+
+ change_relid(&phinfo->ph_eval_at, toRemove->relid, toKeep->relid);
+ change_relid(&phinfo->ph_needed, toRemove->relid, toKeep->relid);
+ change_relid(&phinfo->ph_lateral, toRemove->relid, toKeep->relid);
+ change_relid(&phinfo->ph_var->phrels, toRemove->relid, toKeep->relid);
+ }
+
+ /*
+ * Update the equivalence classes that reference the removed relations.
+ */
+ foreach(cell, root->eq_classes)
+ {
+ EquivalenceClass *ec = lfirst(cell);
+
+ if (!bms_is_member(toRemove->relid, ec->ec_relids))
+ {
+ /*
+ * This EC doesn't reference the removed relation,
+ * nothing to be done for it.
+ */
+ continue;
+ }
+
+ /*
+ * Update the EC members to reference the remaining relation
+ * instead of the removed one.
+ */
+ update_ec_members(ec, toRemove->relid, toKeep->relid);
+ change_relid(&ec->ec_relids, toRemove->relid, toKeep->relid);
+
+ /*
+ * We will now update source and derived clauses of the EC.
+ *
+ * Restriction clauses for base relations are already distributed
+ * to the respective baserestrictinfo lists (see
+ * generate_implied_equalities). The above code has already
+ * processed this list, and updated these clauses to reference
+ * the remaining relation, so we can skip them here based on their
+ * relids.
+ *
+ * Likewise, we have already processed the join clauses that join
+ * the removed relation to the remaining one.
+ *
+ * Finally, there are join clauses that join the removed relation
+ * to some third relation. We could delete just delete them and
+ * generate on demand, but sometimes we can't do this because there
+ * is no suitable equality operator (see the handling of ec_broken).
+ * In such cases we are going to use the source clauses, so we have
+ * to correct them too.
+ *
+ * Derived clauses can be generated again, so it is simpler to just
+ * delete them.
+ */
+ list_free(ec->ec_derives);
+ ec->ec_derives = NULL;
+ update_ec_sources(&ec->ec_sources, toRemove->relid, toKeep->relid);
+ }
+
+ /*
+ * Mark the rel as "dead" to show it is no longer part of the join tree.
+ * (Removing it from the baserel array altogether seems too risky.)
+ */
+ toRemove->reloptkind = RELOPT_DEADREL;
+
+ /*
+ * Update references to the removed relation from other baserels.
+ */
+ for (int i = 1; i < root->simple_rel_array_size; i++)
+ {
+ RelOptInfo *otherrel = root->simple_rel_array[i];
+ int attroff;
+
+ /* no point in processing target rel itself */
+ if (i == toRemove->relid)
+ continue;
+
+ /* there may be empty slots corresponding to non-baserel RTEs */
+ if (otherrel == NULL)
+ continue;
+
+ Assert(otherrel->relid == i); /* sanity check on array */
+
+ /* Update attr_needed arrays. */
+ for (attroff = otherrel->max_attr - otherrel->min_attr;
+ attroff >= 0; attroff--)
+ {
+ change_relid(&otherrel->attr_needed[attroff], toRemove->relid,
+ toKeep->relid);
+ }
+
+ /* Update lateral references. */
+ foreach (cell, otherrel->lateral_vars)
+ change_varno(lfirst(cell), toRemove->relid, toKeep->relid);
+ }
+}
+
+/*
+ * Test whether the relations are joined on the same unique column.
+ */
+static bool
+is_unique_self_join(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer,
+ RelOptInfo *inner, List *restrictlist)
+{
+ UniqueIndexInfo *outeridx = NULL;
+ UniqueIndexInfo *inneridx = NULL;
+ ListCell *outerCell, *innerCell;
+
+ innerrel_is_unique(root, joinrelids, inner->relids,
+ outer, JOIN_INNER, restrictlist, true, &outeridx);
+ if (!outeridx)
+ return false;
+
+ innerrel_is_unique(root, joinrelids, outer->relids,
+ inner, JOIN_INNER, restrictlist, true, &inneridx);
+ if (!inneridx)
+ return false;
+
+ /* We must have the same unique index for both relations. */
+ if (outeridx->index->indexoid != inneridx->index->indexoid)
+ return false;
+
+ /*
+ * The clauses that make a relation unique must be the same for both
+ * relations, or else we won't match the same row on each side of join.
+ *
+ * The lists of matching clauses are ordered as the index columns, so we
+ * just compare the list elements one by one. The varnos are different,
+ * so we copy the clauses and replace all mentions of outer varno with the
+ * inner, so that we can use equal().
+ */
+ forboth(innerCell, inneridx->clauses, outerCell, outeridx->clauses)
+ {
+ Expr *innerExpr = copyObject(castNode(RestrictInfo, lfirst(innerCell))->clause);
+ Expr *outerExpr = copyObject(castNode(RestrictInfo, lfirst(outerCell))->clause);
+ change_varno(outerExpr, outer->relid, inner->relid);
+ change_varno(innerExpr, outer->relid, inner->relid);
+ if (!equal(outerExpr, innerExpr))
+ {
+ pfree(outerExpr);
+ pfree(innerExpr);
+ return false;
+ }
+ pfree(outerExpr);
+ pfree(innerExpr);
+ }
+
+ return true;
+}
+
+/*
+ * Find and remove unique self joins in a group of base relations that have
+ * the same Oid.
+ *
+ * Returns a set of relids that were removed.
+ */
+static Relids
+remove_self_joins_one_group(UsjScratch *scratch, Index *relids, int n)
+{
+ PlannerInfo *root = scratch->root;
+ Relids joinrelids = scratch->joinrelids;
+ Relids result = NULL;
+ int i, o;
+ ListCell *lc;
+
+ if (n < 2)
+ return NULL;
+
+ for (o = 0; o < n; o++)
+ {
+ RelOptInfo *outer = root->simple_rel_array[relids[o]];
+
+ for (i = o + 1; i < n; i++)
+ {
+ RelOptInfo *inner = root->simple_rel_array[relids[i]];
+ List *restrictlist;
+
+ /* A sanity check: the relations have the same Oid. */
+ Assert(root->simple_rte_array[relids[i]]->relid
+ == root->simple_rte_array[relids[o]]->relid);
+
+ /*
+ * This optimization applies to inner joins only, so skip any relations
+ * that form a special join.
+ */
+ if (bms_is_member(relids[i], scratch->special_join_rels[relids[o]]))
+ continue;
+
+ /* Reuse joinrelids bitset to avoid reallocation. */
+ joinrelids = bms_del_members(joinrelids, joinrelids);
+
+ /*
+ * We only deal with base rels here, so their relids bitset
+ * contains only one member -- their relid.
+ */
+ joinrelids = bms_add_member(joinrelids, relids[o]);
+ joinrelids = bms_add_member(joinrelids, relids[i]);
+
+ /* Is it a unique self join? */
+ restrictlist = build_joinrel_restrictlist(root, joinrelids, outer,
+ inner);
+ if (!is_unique_self_join(root, joinrelids, outer, inner,
+ restrictlist))
+ continue;
+
+ /*
+ * We can't remove the join if the relations have row marks of
+ * different strength (e.g. one is locked FOR UPDATE and another
+ * just has ROW_MARK_REFERENCE for EvalPlanQual rechecking).
+ */
+ if (scratch->row_marks[relids[i]] && scratch->row_marks[relids[o]]
+ && scratch->row_marks[relids[i]]->markType
+ != scratch->row_marks[relids[o]]->markType)
+ {
+ continue;
+ }
+
+ /*
+ * We can remove either relation, so remove the outer one,
+ * to simplify this loop.
+ */
+ remove_self_join_rel(scratch, joinrelids, restrictlist, inner, outer);
+ result = bms_add_member(result, relids[o]);
+
+ /*
+ * Replace varno in root targetlist.
+ */
+ foreach(lc, scratch->targetlist)
+ change_varno(lfirst(lc), relids[o], relids[i]);
+
+ /* We removed the outer relation, try the next one. */
+ break;
+ }
+ }
+
+ scratch->joinrelids = joinrelids;
+ return result;
+}
+
+/*
+ * A qsort comparator to sort the relids by the relation Oid.
+ */
+static int
+compare_rte(const Index *left, const Index *right, PlannerInfo *root)
+{
+ Oid l = root->simple_rte_array[*left]->relid;
+ Oid r = root->simple_rte_array[*right]->relid;
+ return l < r ? 1 : ( l == r ? 0 : -1 );
+}
+
+/*
+ * Find and remove unique self joins on a particular level of the join tree.
+ *
+ * We sort the relations by Oid and then examine each group with the same Oid.
+ * If we removed any relation, remove it from joinlist as well.
+ */
+static void
+remove_self_joins_one_level(UsjScratch *scratch, List **joinlist)
+{
+ ListCell *prev, *cell, *next;
+ Relids relidsToRemove = NULL;
+ Oid groupOid;
+ int groupStart;
+ int i;
+ int n = 0;
+ Index *relid_ascending = scratch->relids;
+ PlannerInfo *root = scratch->root;
+
+ /*
+ * Collect the ids of base relations at this level of the join tree.
+ */
+ foreach (cell, *joinlist)
+ {
+ RangeTblEntry *rte;
+ RelOptInfo *rel;
+ RangeTblRef *ref = (RangeTblRef *) lfirst(cell);
+ if (!IsA(ref, RangeTblRef))
+ continue;
+
+ rte = root->simple_rte_array[ref->rtindex];
+ rel = root->simple_rel_array[ref->rtindex];
+
+ /* We only care about base relations from which we select something. */
+ if (rte->rtekind != RTE_RELATION || rte->relkind != RELKIND_RELATION
+ || rel == NULL)
+ {
+ continue;
+ }
+
+ /* This optimization won't work for tables that have inheritance children. */
+ if (rte->inh)
+ continue;
+
+ relid_ascending[n++] = ref->rtindex;
+
+ /* Limit the number of joins we process to control the quadratic behavior. */
+ if (n > join_collapse_limit)
+ break;
+ }
+
+ if (n < 2)
+ return;
+
+ /*
+ * Find and process the groups of relations that have same Oid.
+ */
+ qsort_arg(relid_ascending, n, sizeof(*relid_ascending),
+ (qsort_arg_comparator) compare_rte, root);
+ groupOid = root->simple_rte_array[relid_ascending[0]]->relid;
+ groupStart = 0;
+ for (i = 1; i < n; i++)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[relid_ascending[i]];
+ Assert(rte->relid != InvalidOid);
+ if (rte->relid != groupOid)
+ {
+ relidsToRemove = bms_add_members(relidsToRemove,
+ remove_self_joins_one_group(scratch, &relid_ascending[groupStart],
+ i - groupStart));
+ groupOid = rte->relid;
+ groupStart = i;
+ }
+ }
+ Assert(groupOid != InvalidOid);
+ Assert(groupStart < n);
+ relidsToRemove = bms_add_members(relidsToRemove,
+ remove_self_joins_one_group(scratch, &relid_ascending[groupStart],
+ n - groupStart));
+
+ /* Delete the removed relations from joinlist. */
+ cell = NULL;
+ next = list_head(*joinlist);
+ while (next)
+ {
+ Node *node;
+
+ prev = cell;
+ cell = next;
+ next = lnext(next);
+ node = lfirst(cell);
+
+ if (IsA(node, RangeTblRef)
+ && bms_is_member(((RangeTblRef*) node)->rtindex, relidsToRemove))
+ {
+ *joinlist = list_delete_cell(*joinlist, cell, prev);
+ cell = prev;
+ }
+ }
+}
+
+/*
+ * Find and remove unique self joins on a single level of a join tree, and
+ * recurse to handle deeper levels.
+ */
+static void
+remove_self_joins_recurse(UsjScratch *scratch, List **joinlist)
+{
+ ListCell *lc;
+ foreach (lc, *joinlist)
+ {
+ switch (((Node*) lfirst(lc))->type)
+ {
+ case T_List:
+ remove_self_joins_recurse(scratch, (List **) &lfirst(lc));
+ break;
+ case T_RangeTblRef:
+ break;
+ default:
+ Assert(false);
+ }
+ }
+ remove_self_joins_one_level(scratch, joinlist);
+}
+
+/*
+ * Find and remove useless self joins.
+ *
+ * We search for joins where the same relation is joined to itself on all
+ * columns of some unique index. If this condition holds, then, for
+ * each outer row, only one inner row matches, and it is the same row
+ * of the same relation. This allows us to remove the join and replace
+ * it with a scan that combines WHERE clauses from both sides. The join
+ * clauses themselves assume the form of X = X and can be replaced with
+ * NOT NULL clauses.
+ *
+ * For the sake of simplicity, we don't apply this optimization to special
+ * joins. Here is a list of what we could do in some particular cases:
+ * 'a a1 semi join a a2': is reduced to inner by reduce_unique_semijoins,
+ * and then removed normally.
+ * 'a a1 anti join a a2': could simplify to a scan with 'outer quals AND
+ * (IS NULL on join columns OR NOT inner quals)'.
+ * 'a a1 left join a a2': could simplify to a scan like inner, but without
+ * NOT NULL condtions on join columns.
+ * 'a a1 left join (a a2 join b)': can't simplify this, because join to b
+ * can both remove rows and introduce duplicates.
+ *
+ * To search for removable joins, we order all the relations on their Oid,
+ * go over each set with the same Oid, and consider each pair of relations
+ * in this set. We check that both relation are made unique by the same
+ * unique index with the same clauses.
+ *
+ * To remove the join, we mark one of the participating relation as
+ * dead, and rewrite all references to it to point to the remaining
+ * relation. This includes modifying RestrictInfos, EquivalenceClasses and
+ * EquivalenceMembers. We also have to modify the row marks. The join clauses
+ * of the removed relation become either restriction or join clauses, based on
+ * whether they reference any relations not participating in the removed join.
+ *
+ * 'targetlist' is the top-level targetlist of query. If it has any references
+ * to the removed relations, we update them to point to the remaining ones.
+ */
+void
+remove_useless_self_joins(PlannerInfo *root, List **joinlist, List *targetlist)
+{
+ ListCell *lc;
+ UsjScratch scratch;
+
+ scratch.root = root;
+ scratch.relids = palloc(root->simple_rel_array_size * sizeof(Index));
+ scratch.special_join_rels = palloc0(root->simple_rel_array_size * sizeof(Relids));
+ scratch.row_marks = palloc0(root->simple_rel_array_size * sizeof(PlanRowMark *));
+ scratch.joinrelids = NULL;
+ scratch.targetlist = targetlist;
+
+ /* Find out which relations have special joins to which. */
+ foreach(lc, root->join_info_list)
+ {
+ SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);
+ int bit = -1;
+ while ((bit = bms_next_member(info->min_lefthand, bit)) >= 0)
+ {
+ RelOptInfo *rel = find_base_rel(root, bit);
+ scratch.special_join_rels[rel->relid] =
+ bms_add_members(scratch.special_join_rels[rel->relid],
+ info->min_righthand);
+ }
+
+ bit = -1;
+ while ((bit = bms_next_member(info->min_righthand, bit)) >= 0)
+ {
+ RelOptInfo *rel = find_base_rel(root, bit);
+ scratch.special_join_rels[rel->relid] =
+ bms_add_members(scratch.special_join_rels[rel->relid],
+ info->min_lefthand);
+ }
+ }
+
+ /* Collect row marks. */
+ foreach (lc, root->rowMarks)
+ {
+ PlanRowMark *rowMark = (PlanRowMark *) lfirst(lc);
+
+ /* Can't have more than one row mark for a relation. */
+ Assert(scratch.row_marks[rowMark->rti] == NULL);
+
+ scratch.row_marks[rowMark->rti] = rowMark;
+ }
+
+ /* Finally, remove the joins. */
+ remove_self_joins_recurse(&scratch, joinlist);
}
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 3cedd01..8d6036c 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -224,7 +224,7 @@ query_planner(PlannerInfo *root, List *tlist,
* jointree preprocessing, but the necessary information isn't available
* until we've built baserel data structures and classified qual clauses.
*/
- joinlist = remove_useless_joins(root, joinlist);
+ joinlist = remove_useless_left_joins(root, joinlist);
/*
* Also, reduce any semijoins with unique inner rels to plain inner joins.
@@ -233,6 +233,11 @@ query_planner(PlannerInfo *root, List *tlist,
reduce_unique_semijoins(root);
/*
+ * Remove self joins on a unique column.
+ */
+ remove_useless_self_joins(root, &joinlist, tlist);
+
+ /*
* Now distribute "placeholders" to base rels as needed. This has to be
* done after join removal because removal could change whether a
* placeholder is evaluable at a base rel.
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 169e51e..493f425 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1578,7 +1578,8 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
if (rel->rtekind == RTE_RELATION && sjinfo->semi_can_btree &&
relation_has_unique_index_for(root, rel, NIL,
sjinfo->semi_rhs_exprs,
- sjinfo->semi_operators))
+ sjinfo->semi_operators,
+ NULL /*index_info*/))
{
pathnode->umethod = UNIQUE_PATH_NOOP;
pathnode->path.rows = rel->rows;
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 4130514..fde4118 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -39,14 +39,10 @@ typedef struct JoinHashEntry
static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *input_rel);
-static List *build_joinrel_restrictlist(PlannerInfo *root,
- RelOptInfo *joinrel,
- RelOptInfo *outer_rel,
- RelOptInfo *inner_rel);
static void build_joinrel_joinlist(RelOptInfo *joinrel,
RelOptInfo *outer_rel,
RelOptInfo *inner_rel);
-static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
+static List *subbuild_joinrel_restrictlist(Relids joinrelids,
List *joininfo_list,
List *new_restrictlist);
static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
@@ -556,7 +552,7 @@ build_join_rel(PlannerInfo *root,
*/
if (restrictlist_ptr)
*restrictlist_ptr = build_joinrel_restrictlist(root,
- joinrel,
+ joinrel->relids,
outer_rel,
inner_rel);
return joinrel;
@@ -659,7 +655,7 @@ build_join_rel(PlannerInfo *root,
* caller might or might not need the restrictlist, but I need it anyway
* for set_joinrel_size_estimates().)
*/
- restrictlist = build_joinrel_restrictlist(root, joinrel,
+ restrictlist = build_joinrel_restrictlist(root, joinrel->relids,
outer_rel, inner_rel);
if (restrictlist_ptr)
*restrictlist_ptr = restrictlist;
@@ -981,7 +977,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
* the various joinlist entries ultimately refer to RestrictInfos
* pushed into them by distribute_restrictinfo_to_rels().
*
- * 'joinrel' is a join relation node
+ * 'joinrelids' is a join relation id set
* 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
* to form joinrel.
*
@@ -994,9 +990,9 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
* RestrictInfo nodes are no longer context-dependent. Instead, just include
* the original nodes in the lists made for the join relation.
*/
-static List *
+List *
build_joinrel_restrictlist(PlannerInfo *root,
- RelOptInfo *joinrel,
+ Relids joinrelids,
RelOptInfo *outer_rel,
RelOptInfo *inner_rel)
{
@@ -1007,8 +1003,8 @@ build_joinrel_restrictlist(PlannerInfo *root,
* eliminating any duplicates (important since we will see many of the
* same clauses arriving from both input relations).
*/
- result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
- result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result);
+ result = subbuild_joinrel_restrictlist(joinrelids, outer_rel->joininfo, NIL);
+ result = subbuild_joinrel_restrictlist(joinrelids, inner_rel->joininfo, result);
/*
* Add on any clauses derived from EquivalenceClasses. These cannot be
@@ -1017,7 +1013,7 @@ build_joinrel_restrictlist(PlannerInfo *root,
*/
result = list_concat(result,
generate_join_implied_equalities(root,
- joinrel->relids,
+ joinrelids,
outer_rel->relids,
inner_rel));
@@ -1043,7 +1039,7 @@ build_joinrel_joinlist(RelOptInfo *joinrel,
}
static List *
-subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
+subbuild_joinrel_restrictlist(Relids joinrelids,
List *joininfo_list,
List *new_restrictlist)
{
@@ -1053,7 +1049,7 @@ subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
- if (bms_is_subset(rinfo->required_relids, joinrel->relids))
+ if (bms_is_subset(rinfo->required_relids, joinrelids))
{
/*
* This clause becomes a restriction clause for the joinrel, since
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index a008ae0..4d1e9ac 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -520,8 +520,10 @@ typedef struct PartitionSchemeData *PartitionScheme;
* populate these fields, for base rels; but someday they might be used for
* join rels too:
*
- * unique_for_rels - list of Relid sets, each one being a set of other
- * rels for which this one has been proven unique
+ * 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.
* non_unique_for_rels - list of Relid sets, each one being a set of
* other rels for which we have tried and failed to prove
* this one unique
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 574bb85..7eb59c1 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -287,6 +287,11 @@ extern RelOptInfo *build_join_rel(PlannerInfo *root,
RelOptInfo *inner_rel,
SpecialJoinInfo *sjinfo,
List **restrictlist_ptr);
+
+extern List *build_joinrel_restrictlist(PlannerInfo *root,
+ Relids joinrelids,
+ RelOptInfo *outer_rel,
+ RelOptInfo *inner_rel);
extern Relids min_join_parameterization(PlannerInfo *root,
Relids joinrelids,
RelOptInfo *outer_rel,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 040335a..725d2c2 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -71,9 +71,20 @@ extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel);
* routines to generate index paths
*/
extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel);
+/*
+ * UniqueIndexInfo describes a unique index and its corresponding clauses
+ * that guarantee the uniqueness of a relation.
+ */
+typedef struct UniqueIndexInfo
+{
+ IndexOptInfo *index;
+ List *clauses;
+} UniqueIndexInfo;
+
extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
List *restrictlist,
- List *exprlist, List *oprlist);
+ List *exprlist, List *oprlist,
+ UniqueIndexInfo **info);
extern bool indexcol_is_bool_constant_for_query(IndexOptInfo *index,
int indexcol);
extern bool match_index_to_operand(Node *operand, int indexcol,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 3bbdb5e..e697ff6 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -16,6 +16,7 @@
#include "nodes/pathnodes.h"
#include "nodes/plannodes.h"
+#include "optimizer/paths.h"
/* GUC parameters */
#define DEFAULT_CURSOR_TUPLE_FRACTION 0.1
@@ -95,13 +96,18 @@ extern void match_foreign_keys_to_quals(PlannerInfo *root);
/*
* prototypes for plan/analyzejoins.c
*/
-extern List *remove_useless_joins(PlannerInfo *root, List *joinlist);
+extern List *remove_useless_left_joins(PlannerInfo *root, List *joinlist);
extern void reduce_unique_semijoins(PlannerInfo *root);
extern bool query_supports_distinctness(Query *query);
extern bool query_is_distinct_for(Query *query, List *colnos, List *opids);
+
extern bool innerrel_is_unique(PlannerInfo *root,
Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel,
- JoinType jointype, List *restrictlist, bool force_cache);
+ JoinType jointype, List *restrictlist, bool force_cache,
+ UniqueIndexInfo **index_info);
+
+extern void remove_useless_self_joins(PlannerInfo *root, List **jointree,
+ List *tlist);
/*
* prototypes for plan/setrefs.c
diff --git a/src/test/regress/expected/equivclass.out b/src/test/regress/expected/equivclass.out
index c448d85..a57905f 100644
--- a/src/test/regress/expected/equivclass.out
+++ b/src/test/regress/expected/equivclass.out
@@ -439,3 +439,35 @@ explain (costs off)
Filter: ((unique1 = unique1) OR (unique2 = unique2))
(2 rows)
+-- Test that broken ECs are processed correctly during self join removal.
+-- Disable merge joins so that we don't get an error about missing commutator.
+-- Test both orientations of the join clause, because only one of them breaks
+-- the EC.
+set enable_mergejoin to off;
+explain (costs off)
+ select * from ec0 m join ec0 n on m.ff = n.ff
+ join ec1 p on m.ff + n.ff = p.f1;
+ QUERY PLAN
+----------------------------------------
+ Nested Loop
+ Join Filter: ((n.ff + n.ff) = p.f1)
+ -> Seq Scan on ec1 p
+ -> Materialize
+ -> Seq Scan on ec0 n
+ Filter: (ff IS NOT NULL)
+(6 rows)
+
+explain (costs off)
+ select * from ec0 m join ec0 n on m.ff = n.ff
+ join ec1 p on p.f1::int8 = (m.ff + n.ff)::int8alias1;
+ QUERY PLAN
+---------------------------------------------------------------
+ Nested Loop
+ Join Filter: ((p.f1)::bigint = ((n.ff + n.ff))::int8alias1)
+ -> Seq Scan on ec1 p
+ -> Materialize
+ -> Seq Scan on ec0 n
+ Filter: (ff IS NOT NULL)
+(6 rows)
+
+reset enable_mergejoin;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 593aec2..230c19c 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/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;
@@ -4486,6 +4488,205 @@ select * from
(0 rows)
--
+-- test that semi- or inner self-joins on a unique column are removed
+--
+-- enable only nestloop to get more predictable plans
+set enable_hashjoin to off;
+set enable_mergejoin to off;
+create table sj (a int unique, b int);
+insert into sj values (1, null), (null, 2), (2, 1);
+analyze sj;
+select p.* from sj p, sj q where q.a = p.a and q.b = q.a - 1;
+ a | b
+---+---
+ 2 | 1
+(1 row)
+
+explain (costs off)
+select p.* from sj p, sj q where q.a = p.a and q.b = q.a - 1;
+ QUERY PLAN
+-----------------------------------------------
+ Seq Scan on sj q
+ Filter: ((a IS NOT NULL) AND (b = (a - 1)))
+(2 rows)
+
+explain (costs off)
+select * from sj p
+where exists (select * from sj q
+ where q.a = p.a and q.b < 10);
+ QUERY PLAN
+------------------------------------------
+ Seq Scan on sj q
+ Filter: ((a IS NOT NULL) AND (b < 10))
+(2 rows)
+
+-- subselect that references the removed relation
+explain (costs off)
+select t1.a, (select a from sj where a = t2.a and a = t1.a)
+from sj t1, sj t2
+where t1.a = t2.a;
+ QUERY PLAN
+------------------------------------------
+ Seq Scan on sj t2
+ Filter: (a IS NOT NULL)
+ SubPlan 1
+ -> Result
+ One-Time Filter: (t2.a = t2.a)
+ -> Seq Scan on sj
+ Filter: (a = t2.a)
+(7 rows)
+
+-- self-join under outer join
+explain (costs off)
+select * from sj x join sj y on x.a = y.a
+left join int8_tbl z on x.a = z.q1;
+ QUERY PLAN
+------------------------------------
+ Nested Loop Left Join
+ Join Filter: (y.a = z.q1)
+ -> Seq Scan on sj y
+ Filter: (a IS NOT NULL)
+ -> Materialize
+ -> Seq Scan on int8_tbl z
+(6 rows)
+
+explain (costs off)
+select * from sj x join sj y on x.a = y.a
+left join int8_tbl z on y.a = z.q1;
+ QUERY PLAN
+------------------------------------
+ Nested Loop Left Join
+ Join Filter: (y.a = z.q1)
+ -> Seq Scan on sj y
+ Filter: (a IS NOT NULL)
+ -> Materialize
+ -> Seq Scan on int8_tbl z
+(6 rows)
+
+-- Test that placeholders are updated correctly after join removal
+explain (costs off)
+select * from (values (1)) x
+left join (select coalesce(y.q1, 1) from int8_tbl y
+ right join sj j1 inner join sj j2 on j1.a = j2.a
+ on true) z
+on true;
+ QUERY PLAN
+------------------------------------------
+ Nested Loop Left Join
+ -> Result
+ -> Nested Loop Left Join
+ -> Seq Scan on sj j2
+ Filter: (a IS NOT NULL)
+ -> Materialize
+ -> Seq Scan on int8_tbl y
+(7 rows)
+
+-- update lateral references
+explain (costs off)
+select 1 from (select x.* from sj x, sj y where x.a = y.a) q,
+ lateral generate_series(1, q.a) gs(i);
+ QUERY PLAN
+-------------------------------------------
+ Nested Loop
+ -> Seq Scan on sj y
+ Filter: (a IS NOT NULL)
+ -> Function Scan on generate_series gs
+(4 rows)
+
+explain (costs off)
+select 1 from (select y.* from sj x, sj y where x.a = y.a) q,
+ lateral generate_series(1, q.a) gs(i);
+ QUERY PLAN
+-------------------------------------------
+ Nested Loop
+ -> Seq Scan on sj y
+ Filter: (a IS NOT NULL)
+ -> Function Scan on generate_series gs
+(4 rows)
+
+-- Test that a non-EC-derived join clause is processed correctly. Use an
+-- outer join so that we can't form an EC.
+explain (costs off) select * from sj p join sj q on p.a = q.a
+ left join sj r on p.a + q.a = r.a;
+ QUERY PLAN
+------------------------------------
+ Nested Loop Left Join
+ Join Filter: ((q.a + q.a) = r.a)
+ -> Seq Scan on sj q
+ Filter: (a IS NOT NULL)
+ -> Materialize
+ -> Seq Scan on sj r
+(6 rows)
+
+-- Check that attr_needed is updated correctly after self-join removal. In
+-- this test, k1.b is required at either j1 or j2. If this info is lost,
+-- join targetlist for (k1, k2) will not contain k1.b. Use index scan for
+-- k1 so that we don't get 'b' from physical tlist used for seqscan. Also
+-- disable reordering of joins because this test depends on a particular
+-- join tree.
+create table sk (a int, b int);
+create index sk_a_idx on sk(a);
+set join_collapse_limit to 1;
+set enable_seqscan to off;
+explain (costs off) select 1 from
+ (sk k1 join sk k2 on k1.a = k2.a)
+ join (sj j1 join sj j2 on j1.a = j2.a) on j1.b = k1.b;
+ QUERY PLAN
+-----------------------------------------------------
+ Nested Loop
+ Join Filter: (k1.b = j2.b)
+ -> Nested Loop
+ -> Index Scan using sk_a_idx on sk k1
+ -> Index Only Scan using sk_a_idx on sk k2
+ Index Cond: (a = k1.a)
+ -> Materialize
+ -> Index Scan using sj_a_key on sj j2
+ Index Cond: (a IS NOT NULL)
+(9 rows)
+
+explain (costs off) select 1 from
+ (sk k1 join sk k2 on k1.a = k2.a)
+ join (sj j1 join sj j2 on j1.a = j2.a) on j2.b = k1.b;
+ QUERY PLAN
+-----------------------------------------------------
+ Nested Loop
+ Join Filter: (k1.b = j2.b)
+ -> Nested Loop
+ -> Index Scan using sk_a_idx on sk k1
+ -> Index Only Scan using sk_a_idx on sk k2
+ Index Cond: (a = k1.a)
+ -> Materialize
+ -> Index Scan using sj_a_key on sj j2
+ Index Cond: (a IS NOT NULL)
+(9 rows)
+
+reset join_collapse_limit;
+reset enable_seqscan;
+-- 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.
+create table sl(a int, b int);
+create unique index sl_ab on sl(a, b);
+explain (costs off)
+select * from sl t1, sl t2
+where t1.a = t2.a and t1.b = 1 and t2.b = 2;
+ QUERY PLAN
+----------------------------------------------
+ Nested Loop
+ Join Filter: (t1.a = t2.a)
+ -> Bitmap Heap Scan on sl t1
+ Recheck Cond: (b = 1)
+ -> Bitmap Index Scan on sl_ab
+ Index Cond: (b = 1)
+ -> Materialize
+ -> Bitmap Heap Scan on sl t2
+ Recheck Cond: (b = 2)
+ -> Bitmap Index Scan on sl_ab
+ Index Cond: (b = 2)
+(11 rows)
+
+reset enable_hashjoin;
+reset enable_mergejoin;
+--
-- Test hints given on incorrect column references are useful
--
select t1.uunique1 from
diff --git a/src/test/regress/sql/equivclass.sql b/src/test/regress/sql/equivclass.sql
index 85aa65d..b1e2483 100644
--- a/src/test/regress/sql/equivclass.sql
+++ b/src/test/regress/sql/equivclass.sql
@@ -262,3 +262,20 @@ explain (costs off)
-- this could be converted, but isn't at present
explain (costs off)
select * from tenk1 where unique1 = unique1 or unique2 = unique2;
+
+
+-- Test that broken ECs are processed correctly during self join removal.
+-- Disable merge joins so that we don't get an error about missing commutator.
+-- Test both orientations of the join clause, because only one of them breaks
+-- the EC.
+set enable_mergejoin to off;
+
+explain (costs off)
+ select * from ec0 m join ec0 n on m.ff = n.ff
+ join ec1 p on m.ff + n.ff = p.f1;
+
+explain (costs off)
+ select * from ec0 m join ec0 n on m.ff = n.ff
+ join ec1 p on p.f1::int8 = (m.ff + n.ff)::int8alias1;
+
+reset enable_mergejoin;
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 34d21d0..4b0ea7b 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1570,6 +1570,96 @@ select * from
int8_tbl x join (int4_tbl x cross join int4_tbl y(ff)) j on q1 = f1; -- ok
--
+-- test that semi- or inner self-joins on a unique column are removed
+--
+
+-- enable only nestloop to get more predictable plans
+set enable_hashjoin to off;
+set enable_mergejoin to off;
+
+create table sj (a int unique, b int);
+insert into sj values (1, null), (null, 2), (2, 1);
+analyze sj;
+
+select p.* from sj p, sj q where q.a = p.a and q.b = q.a - 1;
+
+explain (costs off)
+select p.* from sj p, sj q where q.a = p.a and q.b = q.a - 1;
+
+explain (costs off)
+select * from sj p
+where exists (select * from sj q
+ where q.a = p.a and q.b < 10);
+
+-- subselect that references the removed relation
+explain (costs off)
+select t1.a, (select a from sj where a = t2.a and a = t1.a)
+from sj t1, sj t2
+where t1.a = t2.a;
+
+-- self-join under outer join
+explain (costs off)
+select * from sj x join sj y on x.a = y.a
+left join int8_tbl z on x.a = z.q1;
+
+explain (costs off)
+select * from sj x join sj y on x.a = y.a
+left join int8_tbl z on y.a = z.q1;
+
+-- Test that placeholders are updated correctly after join removal
+explain (costs off)
+select * from (values (1)) x
+left join (select coalesce(y.q1, 1) from int8_tbl y
+ right join sj j1 inner join sj j2 on j1.a = j2.a
+ on true) z
+on true;
+
+-- update lateral references
+explain (costs off)
+select 1 from (select x.* from sj x, sj y where x.a = y.a) q,
+ lateral generate_series(1, q.a) gs(i);
+
+explain (costs off)
+select 1 from (select y.* from sj x, sj y where x.a = y.a) q,
+ lateral generate_series(1, q.a) gs(i);
+
+-- Test that a non-EC-derived join clause is processed correctly. Use an
+-- outer join so that we can't form an EC.
+explain (costs off) select * from sj p join sj q on p.a = q.a
+ left join sj r on p.a + q.a = r.a;
+
+-- Check that attr_needed is updated correctly after self-join removal. In
+-- this test, k1.b is required at either j1 or j2. If this info is lost,
+-- join targetlist for (k1, k2) will not contain k1.b. Use index scan for
+-- k1 so that we don't get 'b' from physical tlist used for seqscan. Also
+-- disable reordering of joins because this test depends on a particular
+-- join tree.
+create table sk (a int, b int);
+create index sk_a_idx on sk(a);
+set join_collapse_limit to 1;
+set enable_seqscan to off;
+explain (costs off) select 1 from
+ (sk k1 join sk k2 on k1.a = k2.a)
+ join (sj j1 join sj j2 on j1.a = j2.a) on j1.b = k1.b;
+explain (costs off) select 1 from
+ (sk k1 join sk k2 on k1.a = k2.a)
+ join (sj j1 join sj j2 on j1.a = j2.a) on j2.b = k1.b;
+reset join_collapse_limit;
+reset enable_seqscan;
+
+-- 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.
+create table sl(a int, b int);
+create unique index sl_ab on sl(a, b);
+
+explain (costs off)
+select * from sl t1, sl t2
+where t1.a = t2.a and t1.b = 1 and t2.b = 2;
+
+reset enable_hashjoin;
+reset enable_mergejoin;
+
+--
-- Test hints given on incorrect column references are useful
--
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.kuzmenkov@postgrespro.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.kuzmenkov@postgrespro.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.kuzmenkov@postgrespro.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.rowley@2ndquadrant.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.lepikhov@postgrespro.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.lepikhov@postgrespro.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] https://www.postgresql.org/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.lepikhov@postgrespro.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] > https://www.postgresql.org/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@pgmasters.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.lepikhov@postgrespro.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] https://www.postgresql.org/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.lepikhov@postgrespro.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] https://www.postgresql.org/message-id/CAKJS1f8p-KiEujr12k-oa52JNWWaQUjEjNg%2Bo1MGZk4mHBn_Rg%40mail.gmail.com [2] https://www.postgresql.org/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.lepikhov@postgrespro.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] > https://www.postgresql.org/message-id/CAKJS1f8p-KiEujr12k-oa52JNWWaQUjEjNg%2Bo1MGZk4mHBn_Rg%40mail.gmail.com > [2] > https://www.postgresql.org/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.lepikhov@postgrespro.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.lepikhov@postgrespro.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
Вложения
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 NOTNULL" filters can be omitted when they're unnecessary. Some of the resulting plans included an "IS NOT NULL" filter ona 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.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.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
NOTNULL" filters can be omitted when they're unnecessary. Some of the resulting plans included an "IS NOT NULL" filter
ona 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.lepikhov@postgrespro.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.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.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.lepikhov@postgrespro.ru> wrote:
On 2/7/21 01:56, Hywel Carver wrote:
> On Wed, Jun 30, 2021 at 12:21 PM Andrey Lepikhov
> <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.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.lepikhov@postgrespro.ru> wrote: > > On 5/8/21 2:00 AM, Hywel Carver wrote: > > On Fri, May 7, 2021 at 8:23 AM Andrey Lepikhov > > <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.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.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.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.lepikhov@postgrespro.ru> wrote:
On 6/7/21 13:49, Hywel Carver wrote:
> On Mon, Jul 5, 2021 at 2:20 PM Andrey Lepikhov
> <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.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@yugabyte.com> wrote:
On Thu, Jul 15, 2021 at 7:49 AM Andrey Lepikhov <a.lepikhov@postgrespro.ru> wrote:On 6/7/21 13:49, Hywel Carver wrote:
> On Mon, Jul 5, 2021 at 2:20 PM Andrey Lepikhov
> <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.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 ProfessionalHi,bq. We can proof the uniquenessproof -> prove1. Collect all mergejoinable join quals looks like a.x = b.xquals looks like -> quals which look likeFor 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 */
+ 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;
+ !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)
+ 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@yugabyte.com > <mailto:zyu@yugabyte.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.dunklau@aiven.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.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.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.dunklau@aiven.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
Вложения
Hi,
w.r.t. v33-0001-Remove-self-joins.patch :
removes inner join of plane table -> removes inner join of plain table
in an query plan -> in a query plan
+ * Used as the relation_has_unique_index_for,
Since relation_has_unique_index_for() becomes a wrapper of relation_has_unique_index_ext, the above sentence doesn't make much sense. I think you can drop this part.
but if extra_clauses doesn't NULL -> If extra_clauses isn't NULL
+ is_req_equal =
+ (rinfo->required_relids == rinfo->clause_relids) ? true : false;
+ (rinfo->required_relids == rinfo->clause_relids) ? true : false;
The above can be simplified to:
is_req_equal = rinfo->required_relids == rinfo->clause_relids;
+ ListCell *otherCell;
otherCell should be initialized to NULL.
+ if (bms_is_member(k, info->syn_lefthand) &&
+ !bms_is_member(r, info->syn_lefthand))
+ jinfo_check = false;
+ else if (bms_is_member(k, info->syn_righthand) &&
+ !bms_is_member(r, info->syn_righthand))
+ jinfo_check = false;
+ else if (bms_is_member(r, info->syn_lefthand) &&
+ !bms_is_member(k, info->syn_lefthand))
+ jinfo_check = false;
+ !bms_is_member(r, info->syn_lefthand))
+ jinfo_check = false;
+ else if (bms_is_member(k, info->syn_righthand) &&
+ !bms_is_member(r, info->syn_righthand))
+ jinfo_check = false;
+ else if (bms_is_member(r, info->syn_lefthand) &&
+ !bms_is_member(k, info->syn_lefthand))
+ jinfo_check = false;
I think the above code can be simplified:
If bms_is_member(k, info->syn_lefthand) ^ bms_is_member(r, info->syn_lefthand) is true, jinfo_check is false.
If bms_is_member(k, info->syn_righthand) ^ bms_is_member(r, info->syn_righthand) is true, jinfo_check is false.
Otherwise jinfo_check is true.
Cheers
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@yugabyte.com. [1] https://www.postgresql.org/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@yugabyte.com. > > [1] > https://www.postgresql.org/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
outerjoins. I wonder if that would help with avoiding the need for adding is not null clauses when the column is known
notnull ?
If we have a precedent for adding a BitmapSet to the Var itself, maybe the whole discussion regarding keeping track of
nullabilitycan 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
throughthe 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
thiskind 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_membersand 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
postgressource 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
keptand 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
somethingelse. In other parts of the code, you used "the remaining relation / the removed relation" which makes sense.
/*
* Remove the target relid from the planner's data structures, having
- * determined that there is no need to include it in the query.
+ * determined that there is no need to include it in the query. Or replace
+ * with another relid.
+ * To reusability, this routine can work in two modes: delete relid from a plan
+ * or replace it. It is used in replace mode in a self-join removing process.
This could be rephrased: ", optionally replacing it with another relid. The latter is used by the self-join removing
process."
[1] https://www.postgresql.org/message-id/flat/830269.1656693747%40sss.pgh.pa.us
--
Ronan Dunklau
On Mon, Jul 4, 2022 at 6:52 AM Ronan Dunklau <ronan.dunklau@aiven.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] https://www.postgresql.org/message-id/flat/830269.1656693747%40sss.pgh.pa.us
--
Ronan Dunklau
Hi,
bq. this is more compact and easier to follow than the previous version
A code comment can be added above the expression (involving XOR) to explain the purpose of the expression.
Cheers
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@yugabyte.com> wrote:
Hi,For v36-0001-Remove-self-joins.patch :bq removes inner join of plane table to itselfplane table -> plain tableFor 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():
+ 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@yugabyte.com > <mailto:zyu@yugabyte.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 ofinformation. Not sure how the process works and how I could help (I am absolutely not capable of helping with coding I am afraid - butcould sponsor a (small :) ) bounty to speed things up). Thanks, Michal > On 16 Dec 2022, at 07:45, Andrey Lepikhov <a.lepikhov@postgrespro.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@kleczek.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@kleczek.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. It passes regression tests, but some questions are still open: 1. Should we look for duplicated or redundant clauses (the same for eclasses) during the clause transfer procedure? On the one side, we reduce the length of restrict lists that can impact planning or executing time. Additionally, we improve the accuracy of cardinality estimation. On the other side, it is one more place that can make planning time much longer in specific cases. It would have been better to avoid calling the equal() function here, but it's the only way to detect duplicated inequality expressions. 2. Could we reuse ChangeVarNodes instead of sje_walker(), merge remove_rel_from_restrictinfo with replace_varno? 3. Also, I still don't finish with the split_selfjoin_quals: some improvements could be made. -- regards, Andrey Lepikhov Postgres Professional
Вложения
Hi, During the significant code revision in v.41 I lost some replacement operations. Here is the fix and extra tests to check this in the future. Also, Tom added the JoinDomain structure five months ago, and I added code to replace relids for that place too. One more thing, I found out that we didn't replace SJs, defined by baserestrictinfos if no one self-join clause have existed for the join. Now, it is fixed, and the test has been added. To understand changes readily, see the delta file in the attachment. -- regards, Andrey Lepikhov Postgres Professional
Вложения
On 5/7/2023 21:28, Andrey Lepikhov wrote: > Hi, > > During the significant code revision in v.41 I lost some replacement > operations. Here is the fix and extra tests to check this in the future. > Also, Tom added the JoinDomain structure five months ago, and I added > code to replace relids for that place too. > One more thing, I found out that we didn't replace SJs, defined by > baserestrictinfos if no one self-join clause have existed for the join. > Now, it is fixed, and the test has been added. > To understand changes readily, see the delta file in the attachment. Here is new patch in attachment. Rebased on current master and some minor gaffes are fixed. -- regards, Andrey Lepikhov Postgres Professional
Вложения
Hi! I think this is a neat optimization. On Tue, Sep 12, 2023 at 4:58 PM Andrey Lepikhov <a.lepikhov@postgrespro.ru> wrote: > On 5/7/2023 21:28, Andrey Lepikhov wrote: > > During the significant code revision in v.41 I lost some replacement > > operations. Here is the fix and extra tests to check this in the future. > > Also, Tom added the JoinDomain structure five months ago, and I added > > code to replace relids for that place too. > > One more thing, I found out that we didn't replace SJs, defined by > > baserestrictinfos if no one self-join clause have existed for the join. > > Now, it is fixed, and the test has been added. > > To understand changes readily, see the delta file in the attachment. > Here is new patch in attachment. Rebased on current master and some > minor gaffes are fixed. I went through the thread and I think the patch gets better shape. A couple of notes from my side. 1) Why replace_relid() makes a copy of lids only on insert/replace of a member, but performs deletion in-place? 2) It would be nice to skip the insertion of IS NOT NULL checks when they are not necessary. [1] points that infrastructure from [2] might be useful. The patchset from [2] seems committed mow. However, I can't see it is directly helpful in this matter. Could we just skip adding IS NOT NULL clause for the columns, that have pg_attribute.attnotnull set? Links 1. https://www.postgresql.org/message-id/2375492.jE0xQCEvom%40aivenronan 2. https://www.postgresql.org/message-id/flat/830269.1656693747%40sss.pgh.pa.us ------ Regards, Alexander Korotkov
On 4/10/2023 07:12, Alexander Korotkov wrote: > Hi! Thanks for the review! > > I think this is a neat optimization. > > On Tue, Sep 12, 2023 at 4:58 PM Andrey Lepikhov > <a.lepikhov@postgrespro.ru> wrote: >> On 5/7/2023 21:28, Andrey Lepikhov wrote: >>> During the significant code revision in v.41 I lost some replacement >>> operations. Here is the fix and extra tests to check this in the future. >>> Also, Tom added the JoinDomain structure five months ago, and I added >>> code to replace relids for that place too. >>> One more thing, I found out that we didn't replace SJs, defined by >>> baserestrictinfos if no one self-join clause have existed for the join. >>> Now, it is fixed, and the test has been added. >>> To understand changes readily, see the delta file in the attachment. >> Here is new patch in attachment. Rebased on current master and some >> minor gaffes are fixed. > > I went through the thread and I think the patch gets better shape. A > couple of notes from my side. > 1) Why replace_relid() makes a copy of lids only on insert/replace of > a member, but performs deletion in-place? Shortly speaking, it was done according to the 'Paranoid' strategy. The main reason for copying before deletion was the case with the rinfo required_relids and clause_relids. They both point to the same Bitmapset in some cases. And we feared such things for other fields. Right now, it may be redundant because we resolved the issue mentioned above in replace_varno_walker. Relid replacement machinery is the most contradictory code here. We used a utilitarian approach and implemented a simplistic variant. > 2) It would be nice to skip the insertion of IS NOT NULL checks when > they are not necessary. [1] points that infrastructure from [2] might > be useful. The patchset from [2] seems committed mow. However, I > can't see it is directly helpful in this matter. Could we just skip > adding IS NOT NULL clause for the columns, that have > pg_attribute.attnotnull set? Thanks for the links, I will look into that case. > > Links > 1. https://www.postgresql.org/message-id/2375492.jE0xQCEvom%40aivenronan > 2. https://www.postgresql.org/message-id/flat/830269.1656693747%40sss.pgh.pa.us -- regards, Andrey Lepikhov Postgres Professional
Hi!
> On 4/10/2023 07:12, Alexander Korotkov wrote:
> > On Tue, Sep 12, 2023 at 4:58 PM Andrey Lepikhov
> > <a.lepikhov@postgrespro.ru> wrote:
> >> On 5/7/2023 21:28, Andrey Lepikhov wrote:
> >>> During the significant code revision in v.41 I lost some replacement
> >>> operations. Here is the fix and extra tests to check this in the future.
> >>> Also, Tom added the JoinDomain structure five months ago, and I added
> >>> code to replace relids for that place too.
> >>> One more thing, I found out that we didn't replace SJs, defined by
> >>> baserestrictinfos if no one self-join clause have existed for the join.
> >>> Now, it is fixed, and the test has been added.
> >>> To understand changes readily, see the delta file in the attachment.
> >> Here is new patch in attachment. Rebased on current master and some
> >> minor gaffes are fixed.
> >
> > I went through the thread and I think the patch gets better shape. A
> > couple of notes from my side.
> > 1) Why replace_relid() makes a copy of lids only on insert/replace of
> > a member, but performs deletion in-place?
>
> Shortly speaking, it was done according to the 'Paranoid' strategy.
> The main reason for copying before deletion was the case with the rinfo
> required_relids and clause_relids. They both point to the same Bitmapset
> in some cases. And we feared such things for other fields.
> Right now, it may be redundant because we resolved the issue mentioned
> above in replace_varno_walker.
OK, but my point is still that you should be paranoid in all the cases or none of the cases. Right now (newId < 0) branch doesn't copy source relids, but bms_is_member(oldId, relids) does copy. Also, I think whether we copy or not should be reflected in the function comment.
/*
* Substitute newId by oldId in relids.
*/
static Bitmapset *
replace_relid(Relids relids, int oldId, int newId)
{
if (oldId < 0)
return relids;
if (newId < 0)
/* Delete relid without substitution. */
return bms_del_member(relids, oldId);
if (bms_is_member(oldId, relids))
return bms_add_member(bms_del_member(bms_copy(relids), oldId), newId);
return relids;
}
> Relid replacement machinery is the most contradictory code here. We used
> a utilitarian approach and implemented a simplistic variant.
> > 2) It would be nice to skip the insertion of IS NOT NULL checks when
> > they are not necessary. [1] points that infrastructure from [2] might
> > be useful. The patchset from [2] seems committed mow. However, I
> > can't see it is directly helpful in this matter. Could we just skip
> > adding IS NOT NULL clause for the columns, that have
> > pg_attribute.attnotnull set?
> Thanks for the links, I will look into that case.
OK, thank you.
------
Regards,
Alexander Korotkov
On 4/10/2023 14:34, Alexander Korotkov wrote:
> Hi!
>
> On Wed, Oct 4, 2023 at 9:56 AM Andrei Lepikhov
> <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.ru>> wrote:
> > On 4/10/2023 07:12, Alexander Korotkov wrote:
> > > On Tue, Sep 12, 2023 at 4:58 PM Andrey Lepikhov
> > > <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.ru>> wrote:
> > >> On 5/7/2023 21:28, Andrey Lepikhov wrote:
> > >>> During the significant code revision in v.41 I lost some replacement
> > >>> operations. Here is the fix and extra tests to check this in the
> future.
> > >>> Also, Tom added the JoinDomain structure five months ago, and I added
> > >>> code to replace relids for that place too.
> > >>> One more thing, I found out that we didn't replace SJs, defined by
> > >>> baserestrictinfos if no one self-join clause have existed for the
> join.
> > >>> Now, it is fixed, and the test has been added.
> > >>> To understand changes readily, see the delta file in the attachment.
> > >> Here is new patch in attachment. Rebased on current master and some
> > >> minor gaffes are fixed.
> > >
> > > I went through the thread and I think the patch gets better shape. A
> > > couple of notes from my side.
> > > 1) Why replace_relid() makes a copy of lids only on insert/replace of
> > > a member, but performs deletion in-place?
> >
> > Shortly speaking, it was done according to the 'Paranoid' strategy.
> > The main reason for copying before deletion was the case with the rinfo
> > required_relids and clause_relids. They both point to the same Bitmapset
> > in some cases. And we feared such things for other fields.
> > Right now, it may be redundant because we resolved the issue mentioned
> > above in replace_varno_walker.
>
> OK, but my point is still that you should be paranoid in all the cases
> or none of the cases. Right now (newId < 0) branch doesn't copy source
> relids, but bms_is_member(oldId, relids) does copy. Also, I think
> whether we copy or not should be reflected in the function comment.
>
> /*
> * Substitute newId by oldId in relids.
> */
> static Bitmapset *
> replace_relid(Relids relids, int oldId, int newId)
> {
> if (oldId < 0)
> return relids;
>
> if (newId < 0)
> /* Delete relid without substitution. */
> return bms_del_member(relids, oldId);
>
> if (bms_is_member(oldId, relids))
> return bms_add_member(bms_del_member(bms_copy(relids), oldId),
> newId);
>
> return relids;
> }
We tried to use replace_relid() for both cases of JOIN deletion:
unneeded outer join and self-join, and the relid deletion is used only
in the first case. Such an approach was used there for a long time, and
we just didn't change it.
I am prone to removing the copy operation in the code of relid replacement.
>
> > Relid replacement machinery is the most contradictory code here. We used
> > a utilitarian approach and implemented a simplistic variant.
>
> > > 2) It would be nice to skip the insertion of IS NOT NULL checks when
> > > they are not necessary. [1] points that infrastructure from [2] might
> > > be useful. The patchset from [2] seems committed mow. However, I
> > > can't see it is directly helpful in this matter. Could we just skip
> > > adding IS NOT NULL clause for the columns, that have
> > > pg_attribute.attnotnull set?
> > Thanks for the links, I will look into that case.
Thanks for the curious issue.
The new field Var::varnullingrels introduced in [2] doesn't make sense
here, as I see: we operate with plain relations only, and I don't know
how it can be applied to an arbitrary subtree contained OUTER JOINs.
The second option, the attnotnull flag, can be used in this code. We
haven't implemented it because the process_equivalence routine doesn't
check the attnotnull before creating NullTest.
In general, it is not a difficult operation - we just need to add a
trivial get_attnotnull() routine to lssycache.c likewise
get_attgenerated() and other functions.
But, replace_varno uses the walker to change the relid. The mentioned
replacement, like
X=X --> X IS NOT NULL
can be applied on different levels of the expression, look:
A a1 JOIN A a2 ON (a1.id=a2.id) WHERE (a1.x AND (a1.y=a2.y))
Here, we can replace id=id and y=y. It may need some 'unwanted clauses'
collection procedure and a second pass through the expression tree to
remove them. It may add some unpredictable overhead.
We can replace such a clause with a trivial 'TRUE' clause, of course.
But is it the feature you have requested?
--
regards,
Andrey Lepikhov
Postgres Professional
On 4/10/2023 14:34, Alexander Korotkov wrote: > > Relid replacement machinery is the most contradictory code here. We used > > a utilitarian approach and implemented a simplistic variant. > > > > 2) It would be nice to skip the insertion of IS NOT NULL checks when > > > they are not necessary. [1] points that infrastructure from [2] might > > > be useful. The patchset from [2] seems committed mow. However, I > > > can't see it is directly helpful in this matter. Could we just skip > > > adding IS NOT NULL clause for the columns, that have > > > pg_attribute.attnotnull set? > > Thanks for the links, I will look into that case. To be more precise, in the attachment, you can find a diff to the main patch, which shows the volume of changes to achieve the desired behaviour. Some explains in regression tests shifted. So, I've made additional tests: DROP TABLE test CASCADE; CREATE TABLE test (a int, b int not null); CREATE UNIQUE INDEX abc ON test(b); explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) WHERE t1.b=t2.b; CREATE UNIQUE INDEX abc1 ON test(a,b); explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) WHERE t1.b=t2.b; explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a); DROP INDEX abc1; explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b); We have almost the results we wanted to have. But in the last explain you can see that nothing happened with the OR clause. We should use the expression mutator instead of walker to handle such clauses. But It doesn't process the RestrictInfo node ... I'm inclined to put a solution of this issue off for a while. -- regards, Andrey Lepikhov Postgres Professional
Вложения
Hi!
I have reviewed your patch and I noticed a few things.
First of all, I think I found a bug in your latest patch version, and this query shows it:EXPLAIN (COSTS OFF)
SELECT c.oid, e.oid FROM pg_class c FULL JOIN (
SELECT e1.oid FROM pg_extension e1, pg_extension e2
WHERE e1.oid=e2.oid) AS e
ON c.oid=e.oid;
In the current version we get such a query plan: QUERY PLAN
-----------------------------------------
Hash Full Join
Hash Cond: (c.oid = e2.oid)
-> Seq Scan on pg_class c
-> Hash
-> Seq Scan on pg_extension e2
(5 rows)
But I think it should be:
QUERY PLAN
-----------------------------------------
Hash Full Join
Hash Cond: (c.oid = e2.oid)
-> Seq Scan on pg_class c
-> Hash
-> Seq Scan on pg_extension e2
Filter: (oid IS NOT NULL)
(6 rows)
I have looked at the latest version of the code, I assume that the error lies in the replace_varno_walker function, especially in the place where we check the node by type Var, and does not form any NullTest node.if (OidIsValid(reloid) && get_attnotnull(reloid, attnum)) -- this condition works
{
rinfo->clause = (Expr *) makeBoolConst(true, false);
}
else
{
NullTest *ntest = makeNode(NullTest);
ntest->arg = leftOp;
ntest->nulltesttype = IS_NOT_NULL;
ntest->argisrow = false;
ntest->location = -1;
rinfo->clause = (Expr *) ntest;
}
Secondly, I added some code in some places to catch erroneous cases and added a condition when we should not try to apply the self-join-removal transformation due to the absence of an empty self-join list after searching for it and in general if there are no joins in the query. Besides, I added a query for testing and wrote about it above. I have attached my diff file.
In addition, I found a comment for myself that was not clear to me. I would be glad if you could explain it to me.
You mentioned superior outer join in the comment, unfortunately, I didn't find anything about it in the PostgreSQL code, and this explanation remained unclear to me. Could you explain in more detail what you meant?
/*
* At this stage joininfo lists of inner and outer can contain
* only clauses, required for a superior outer join that can't
* influence on this optimization. So, we can avoid to call the
* build_joinrel_restrictlist() routine.
*/
restrictlist = generate_join_implied_equalities(root, joinrelids,
inner->relids,
outer, NULL);
--
Regards, Alena Rybakina
Вложения
On 11/10/2023 02:29, Alena Rybakina wrote: > I have reviewed your patch and I noticed a few things. Thanks for your efforts, > I have looked at the latest version of the code, I assume that the error > lies in the replace_varno_walker function, especially in the place where > we check the node by type Var, and does not form any NullTest node. It's not a bug, it's an optimization we discussed with Alexander above. > Secondly, I added some code in some places to catch erroneous cases and > added a condition when we should not try to apply the self-join-removal > transformation due to the absence of an empty self-join list after > searching for it and in general if there are no joins in the query. > Besides, I added a query for testing and wrote about it above. I have > attached my diff file. Ok, I will look at this > In addition, I found a comment for myself that was not clear to me. I > would be glad if you could explain it to me. > > You mentioned superior outer join in the comment, unfortunately, I > didn't find anything about it in the PostgreSQL code, and this > explanation remained unclear to me. Could you explain in more detail > what you meant? I meant here that only clauses pushed by reconsider_outer_join_clauses() can be found in the joininfo list, and they are not relevant, as you can understand. Having written that, I realized that it was a false statement. ;) - joininfo can also contain results of previous SJE iterations, look: CREATE TABLE test (oid int PRIMARY KEY); CREATE UNIQUE INDEX ON test((oid*oid)); explain SELECT count(*) FROM test c1, test c2, test c3 WHERE c1.oid=c2.oid AND c1.oid*c2.oid=c3.oid*c3.oid; explain SELECT count(*) FROM test c1, test c2, test c3 WHERE c1.oid=c3.oid AND c1.oid*c3.oid=c2.oid*c2.oid; explain SELECT count(*) FROM test c1, test c2, test c3 WHERE c3.oid=c2.oid AND c3.oid*c2.oid=c1.oid*c1.oid; Having executed this SQL code, you could see that in the last query, the SJE feature didn't delete one of the JOINs because of the reason I had written above. It's not an one-minute fix - I will try to propose solution a bit later. -- regards, Andrey Lepikhov Postgres Professional
On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > On 4/10/2023 14:34, Alexander Korotkov wrote: > > > Relid replacement machinery is the most contradictory code here. We used > > > a utilitarian approach and implemented a simplistic variant. > > > > > > 2) It would be nice to skip the insertion of IS NOT NULL checks when > > > > they are not necessary. [1] points that infrastructure from [2] might > > > > be useful. The patchset from [2] seems committed mow. However, I > > > > can't see it is directly helpful in this matter. Could we just skip > > > > adding IS NOT NULL clause for the columns, that have > > > > pg_attribute.attnotnull set? > > > Thanks for the links, I will look into that case. > To be more precise, in the attachment, you can find a diff to the main > patch, which shows the volume of changes to achieve the desired behaviour. > Some explains in regression tests shifted. So, I've made additional tests: > > DROP TABLE test CASCADE; > CREATE TABLE test (a int, b int not null); > CREATE UNIQUE INDEX abc ON test(b); > explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) > WHERE t1.b=t2.b; > CREATE UNIQUE INDEX abc1 ON test(a,b); > explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) > WHERE t1.b=t2.b; > explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) > WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a); > DROP INDEX abc1; > explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) > WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b); > > We have almost the results we wanted to have. But in the last explain > you can see that nothing happened with the OR clause. We should use the > expression mutator instead of walker to handle such clauses. But It > doesn't process the RestrictInfo node ... I'm inclined to put a solution > of this issue off for a while. OK. I think it doesn't worth to eliminate IS NULL quals with this complexity (at least at this stage of work). I made improvements over the code. Mostly new comments, grammar corrections of existing comments and small refactoring. Also, I found that the suggestion from David Rowley [1] to qsort array of relations to faster find duplicates is still unaddressed. I've implemented it. That helps to evade quadratic complexity with large number of relations. Also I've incorporated improvements from Alena Rybakina except one for skipping SJ removal when no SJ quals is found. It's not yet clear for me if this check fix some cases. But at least optimization got skipped in some useful cases (as you can see in regression tests). Links 1. https://www.postgresql.org/message-id/CAKJS1f8ySSsBfooH3bJK7OD3LBEbDb99d8J_FtqDd6w50p-eAQ%40mail.gmail.com 2. https://www.postgresql.org/message-id/96f66ae3-df10-4060-9844-4c9633062cd3%40yandex.ru ------ Regards, Alexander Korotkov
Вложения
On 12/10/2023 18:32, Alexander Korotkov wrote: > On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov >> We have almost the results we wanted to have. But in the last explain >> you can see that nothing happened with the OR clause. We should use the >> expression mutator instead of walker to handle such clauses. But It >> doesn't process the RestrictInfo node ... I'm inclined to put a solution >> of this issue off for a while. > > OK. I think it doesn't worth to eliminate IS NULL quals with this > complexity (at least at this stage of work). Yeah. I think It would be meaningful in the case of replacing also nested x IS NOT NULL with nothing. But it requires using a mutator instead of the walker and may be done more accurately next time. > I made improvements over the code. Mostly new comments, grammar > corrections of existing comments and small refactoring. Great! > Also, I found that the suggestion from David Rowley [1] to qsort > array of relations to faster find duplicates is still unaddressed. > I've implemented it. That helps to evade quadratic complexity with > large number of relations. I see. The thread is too long so far, thanks for the catch. > Also I've incorporated improvements from Alena Rybakina except one for > skipping SJ removal when no SJ quals is found. It's not yet clear for > me if this check fix some cases. But at least optimization got skipped > in some useful cases (as you can see in regression tests). Agree. I wouldn't say I like it too. But also, I suggest skipping some unnecessary assertions proposed in that patch: Assert(toKeep->relid != -1); - quite strange. Why -1? Why not all the negative numbers, at least? Assert(is_opclause(orinfo->clause)); - above we skip clauses with rinfo->mergeopfamilies == NIL. Each mergejoinable clause is already checked as is_opclause. All these changes (see in the attachment) are optional. -- regards, Andrey Lepikhov Postgres Professional
Вложения
Also I've incorporated improvements from Alena Rybakina except one for
skipping SJ removal when no SJ quals is found. It's not yet clear for
me if this check fix some cases. But at least optimization got skipped
in some useful cases (as you can see in regression tests).
Agree. I wouldn't say I like it too. But also, I suggest skipping some unnecessary assertions proposed in that patch:
Assert(toKeep->relid != -1); - quite strange. Why -1? Why not all the negative numbers, at least?
Assert(is_opclause(orinfo->clause)); - above we skip clauses with rinfo->mergeopfamilies == NIL. Each mergejoinable clause is already checked as is_opclause.
All these changes (see in the attachment) are optional.
I don't mind about asserts, maybe I misunderstood something in the patch.
About skipping SJ removal when no SJ quals is found, I assume it is about it:split_selfjoin_quals(root, restrictlist, &selfjoinquals,
&otherjoinquals, inner->relid, outer->relid);
+ if (list_length(selfjoinquals) == 0)
+ {
+ /*
+ * XXX:
+ * we would detect self-join without quals like 'x==x' if we had
+ * an foreign key constraint on some of other quals and this join
+ * haven't any columns from the outer in the target list.
+ * But it is still complex task.
+ */
+ continue;
+ }
as far as I remember, this is the place where it is checked that the SJ list is empty and it is logical, in my opinion, that no transformations should be performed if no elements are found for them.
As for the cases where SJ did not work, maybe this is just right if there are no elements for processing these cases. I'll try to check or come up with tests for them. If I'm wrong, write.
On 11.10.2023 06:51, Andrei Lepikhov wrote:
On 11/10/2023 02:29, Alena Rybakina wrote:I have reviewed your patch and I noticed a few things.
Thanks for your efforts,I have looked at the latest version of the code, I assume that the error lies in the replace_varno_walker function, especially in the place where we check the node by type Var, and does not form any NullTest node.
It's not a bug, it's an optimization we discussed with Alexander above.Secondly, I added some code in some places to catch erroneous cases and added a condition when we should not try to apply the self-join-removal transformation due to the absence of an empty self-join list after searching for it and in general if there are no joins in the query. Besides, I added a query for testing and wrote about it above. I have attached my diff file.Ok, I will look at thisIn addition, I found a comment for myself that was not clear to me. I would be glad if you could explain it to me.I meant here that only clauses pushed by reconsider_outer_join_clauses() can be found in the joininfo list, and they are not relevant, as you can understand.
You mentioned superior outer join in the comment, unfortunately, I didn't find anything about it in the PostgreSQL code, and this explanation remained unclear to me. Could you explain in more detail what you meant?
Having written that, I realized that it was a false statement. ;) - joininfo can also contain results of previous SJE iterations, look:
CREATE TABLE test (oid int PRIMARY KEY);
CREATE UNIQUE INDEX ON test((oid*oid));
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c1.oid=c2.oid AND c1.oid*c2.oid=c3.oid*c3.oid;
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c1.oid=c3.oid AND c1.oid*c3.oid=c2.oid*c2.oid;
explain
SELECT count(*)
FROM test c1, test c2, test c3
WHERE c3.oid=c2.oid AND c3.oid*c2.oid=c1.oid*c1.oid;
Ok, I understood. Thank you for explanation.
-- Regards, Alena Rybakina
On 13/10/2023 15:56, a.rybakina wrote:
>
>>> Also I've incorporated improvements from Alena Rybakina except one for
>>> skipping SJ removal when no SJ quals is found. It's not yet clear for
>>> me if this check fix some cases. But at least optimization got skipped
>>> in some useful cases (as you can see in regression tests).
>>
>> Agree. I wouldn't say I like it too. But also, I suggest skipping some
>> unnecessary assertions proposed in that patch:
>> Assert(toKeep->relid != -1); - quite strange. Why -1? Why not all the
>> negative numbers, at least?
>> Assert(is_opclause(orinfo->clause)); - above we skip clauses with
>> rinfo->mergeopfamilies == NIL. Each mergejoinable clause is already
>> checked as is_opclause.
>> All these changes (see in the attachment) are optional.
>>
> I don't mind about asserts, maybe I misunderstood something in the patch.
>
> About skipping SJ removal when no SJ quals is found, I assume it is
> about it:
>
> split_selfjoin_quals(root, restrictlist, &selfjoinquals,
> &otherjoinquals, inner->relid,
> outer->relid);
>
> + if (list_length(selfjoinquals) == 0)
> + {
> + /*
> + * XXX:
> + * we would detect self-join without quals like 'x==x'
> if we had
> + * an foreign key constraint on some of other quals
> and this join
> + * haven't any columns from the outer in the target list.
> + * But it is still complex task.
> + */
> + continue;
> + }
>
> as far as I remember, this is the place where it is checked that the SJ
> list is empty and it is logical, in my opinion, that no transformations
> should be performed if no elements are found for them.
You forget we have "Degenerate" case, as Alexander mentioned above. What
if you have something like that:
SELECT ... FROM A a1, A a2 WHERE a1.id=1 AND a2.id=1;
In this case, uniqueness can be achieved by the baserestrictinfo
"A.id=1", if we have an unique index on this column.
--
regards,
Andrey Lepikhov
Postgres Professional
On 13.10.2023 12:03, Andrei Lepikhov wrote:
> On 13/10/2023 15:56, a.rybakina wrote:
>>
>>>> Also I've incorporated improvements from Alena Rybakina except one for
>>>> skipping SJ removal when no SJ quals is found. It's not yet clear for
>>>> me if this check fix some cases. But at least optimization got skipped
>>>> in some useful cases (as you can see in regression tests).
>>>
>>> Agree. I wouldn't say I like it too. But also, I suggest skipping
>>> some unnecessary assertions proposed in that patch:
>>> Assert(toKeep->relid != -1); - quite strange. Why -1? Why not all
>>> the negative numbers, at least?
>>> Assert(is_opclause(orinfo->clause)); - above we skip clauses with
>>> rinfo->mergeopfamilies == NIL. Each mergejoinable clause is already
>>> checked as is_opclause.
>>> All these changes (see in the attachment) are optional.
>>>
>> I don't mind about asserts, maybe I misunderstood something in the
>> patch.
>>
>> About skipping SJ removal when no SJ quals is found, I assume it is
>> about it:
>>
>> split_selfjoin_quals(root, restrictlist, &selfjoinquals,
>> &otherjoinquals, inner->relid,
>> outer->relid);
>>
>> + if (list_length(selfjoinquals) == 0)
>> + {
>> + /*
>> + * XXX:
>> + * we would detect self-join without quals like
>> 'x==x' if we had
>> + * an foreign key constraint on some of other quals
>> and this join
>> + * haven't any columns from the outer in the target
>> list.
>> + * But it is still complex task.
>> + */
>> + continue;
>> + }
>>
>> as far as I remember, this is the place where it is checked that the
>> SJ list is empty and it is logical, in my opinion, that no
>> transformations should be performed if no elements are found for them.
> You forget we have "Degenerate" case, as Alexander mentioned above.
> What if you have something like that:
> SELECT ... FROM A a1, A a2 WHERE a1.id=1 AND a2.id=1;
> In this case, uniqueness can be achieved by the baserestrictinfo
> "A.id=1", if we have an unique index on this column.
>
Yes, sorry, I missed it. thanks again for the explanation 🙂
On 12/10/2023 18:32, Alexander Korotkov wrote: > On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov > <a.lepikhov@postgrespro.ru> wrote: >> On 4/10/2023 14:34, Alexander Korotkov wrote: >>> > Relid replacement machinery is the most contradictory code here. We used >>> > a utilitarian approach and implemented a simplistic variant. >>> >>> > > 2) It would be nice to skip the insertion of IS NOT NULL checks when >>> > > they are not necessary. [1] points that infrastructure from [2] might >>> > > be useful. The patchset from [2] seems committed mow. However, I >>> > > can't see it is directly helpful in this matter. Could we just skip >>> > > adding IS NOT NULL clause for the columns, that have >>> > > pg_attribute.attnotnull set? >>> > Thanks for the links, I will look into that case. >> To be more precise, in the attachment, you can find a diff to the main >> patch, which shows the volume of changes to achieve the desired behaviour. >> Some explains in regression tests shifted. So, I've made additional tests: >> >> DROP TABLE test CASCADE; >> CREATE TABLE test (a int, b int not null); >> CREATE UNIQUE INDEX abc ON test(b); >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >> WHERE t1.b=t2.b; >> CREATE UNIQUE INDEX abc1 ON test(a,b); >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >> WHERE t1.b=t2.b; >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >> WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a); >> DROP INDEX abc1; >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >> WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b); >> >> We have almost the results we wanted to have. But in the last explain >> you can see that nothing happened with the OR clause. We should use the >> expression mutator instead of walker to handle such clauses. But It >> doesn't process the RestrictInfo node ... I'm inclined to put a solution >> of this issue off for a while. > > OK. I think it doesn't worth to eliminate IS NULL quals with this > complexity (at least at this stage of work). > > I made improvements over the code. Mostly new comments, grammar > corrections of existing comments and small refactoring. > > Also, I found that the suggestion from David Rowley [1] to qsort > array of relations to faster find duplicates is still unaddressed. > I've implemented it. That helps to evade quadratic complexity with > large number of relations. > > Also I've incorporated improvements from Alena Rybakina except one for > skipping SJ removal when no SJ quals is found. It's not yet clear for > me if this check fix some cases. But at least optimization got skipped > in some useful cases (as you can see in regression tests). I would like to propose one more minor improvement (see in attachment). The idea here is that after removing a self-join and changing clauses we should re-probe the set of relids with the same Oid, because we can find more removable self-joins (see the demo test in join.sql). -- regards, Andrey Lepikhov Postgres Professional
Вложения
On Mon, Oct 16, 2023 at 11:28 AM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > On 12/10/2023 18:32, Alexander Korotkov wrote: > > On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov > > <a.lepikhov@postgrespro.ru> wrote: > >> On 4/10/2023 14:34, Alexander Korotkov wrote: > >>> > Relid replacement machinery is the most contradictory code here. We used > >>> > a utilitarian approach and implemented a simplistic variant. > >>> > >>> > > 2) It would be nice to skip the insertion of IS NOT NULL checks when > >>> > > they are not necessary. [1] points that infrastructure from [2] might > >>> > > be useful. The patchset from [2] seems committed mow. However, I > >>> > > can't see it is directly helpful in this matter. Could we just skip > >>> > > adding IS NOT NULL clause for the columns, that have > >>> > > pg_attribute.attnotnull set? > >>> > Thanks for the links, I will look into that case. > >> To be more precise, in the attachment, you can find a diff to the main > >> patch, which shows the volume of changes to achieve the desired behaviour. > >> Some explains in regression tests shifted. So, I've made additional tests: > >> > >> DROP TABLE test CASCADE; > >> CREATE TABLE test (a int, b int not null); > >> CREATE UNIQUE INDEX abc ON test(b); > >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) > >> WHERE t1.b=t2.b; > >> CREATE UNIQUE INDEX abc1 ON test(a,b); > >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) > >> WHERE t1.b=t2.b; > >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) > >> WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a); > >> DROP INDEX abc1; > >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) > >> WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b); > >> > >> We have almost the results we wanted to have. But in the last explain > >> you can see that nothing happened with the OR clause. We should use the > >> expression mutator instead of walker to handle such clauses. But It > >> doesn't process the RestrictInfo node ... I'm inclined to put a solution > >> of this issue off for a while. > > > > OK. I think it doesn't worth to eliminate IS NULL quals with this > > complexity (at least at this stage of work). > > > > I made improvements over the code. Mostly new comments, grammar > > corrections of existing comments and small refactoring. > > > > Also, I found that the suggestion from David Rowley [1] to qsort > > array of relations to faster find duplicates is still unaddressed. > > I've implemented it. That helps to evade quadratic complexity with > > large number of relations. > > > > Also I've incorporated improvements from Alena Rybakina except one for > > skipping SJ removal when no SJ quals is found. It's not yet clear for > > me if this check fix some cases. But at least optimization got skipped > > in some useful cases (as you can see in regression tests). > > I would like to propose one more minor improvement (see in attachment). > The idea here is that after removing a self-join and changing clauses we > should re-probe the set of relids with the same Oid, because we can find > more removable self-joins (see the demo test in join.sql). Thank you, I've integrated this into the patch. BTW, the patch introduces two new GUC variables: enable_self_join_removal, self_join_search_limit. enable_self_join_removal variable turns on/off optimization at all. self_join_search_limit variable limits its usage by the number of joins. AFICS, self_join_search_limit is intended to protect us from quadratic complexity self-join removal has. I tried to reproduce the extreme case. SELECT count(*) FROM pgbench_accounts a0, pgbench_accounts a1, ..., pgbench_accounts a100 WHERE a0.aid = 1 AND a1.aid = a0.aid + 1 AND ... AND a100.aid = a99.aid + 1; This query took 3778.432 ms with self-join removal disabled, and 3756.009 ms with self-join removal enabled. So, no measurable overhead. Similar to the higher number of joins. Can you imagine some extreme case when self-join removal could introduce significant overhead in comparison with other optimizer parts? If not, should we remove self_join_search_limit GUC? ------ Regards, Alexander Korotkov
Вложения
On 19/10/2023 01:50, Alexander Korotkov wrote: > On Mon, Oct 16, 2023 at 11:28 AM Andrei Lepikhov > <a.lepikhov@postgrespro.ru> wrote: >> On 12/10/2023 18:32, Alexander Korotkov wrote: >>> On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov >>> <a.lepikhov@postgrespro.ru> wrote: >>>> On 4/10/2023 14:34, Alexander Korotkov wrote: >>>>> > Relid replacement machinery is the most contradictory code here. We used >>>>> > a utilitarian approach and implemented a simplistic variant. >>>>> >>>>> > > 2) It would be nice to skip the insertion of IS NOT NULL checks when >>>>> > > they are not necessary. [1] points that infrastructure from [2] might >>>>> > > be useful. The patchset from [2] seems committed mow. However, I >>>>> > > can't see it is directly helpful in this matter. Could we just skip >>>>> > > adding IS NOT NULL clause for the columns, that have >>>>> > > pg_attribute.attnotnull set? >>>>> > Thanks for the links, I will look into that case. >>>> To be more precise, in the attachment, you can find a diff to the main >>>> patch, which shows the volume of changes to achieve the desired behaviour. >>>> Some explains in regression tests shifted. So, I've made additional tests: >>>> >>>> DROP TABLE test CASCADE; >>>> CREATE TABLE test (a int, b int not null); >>>> CREATE UNIQUE INDEX abc ON test(b); >>>> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >>>> WHERE t1.b=t2.b; >>>> CREATE UNIQUE INDEX abc1 ON test(a,b); >>>> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >>>> WHERE t1.b=t2.b; >>>> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >>>> WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a); >>>> DROP INDEX abc1; >>>> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >>>> WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b); >>>> >>>> We have almost the results we wanted to have. But in the last explain >>>> you can see that nothing happened with the OR clause. We should use the >>>> expression mutator instead of walker to handle such clauses. But It >>>> doesn't process the RestrictInfo node ... I'm inclined to put a solution >>>> of this issue off for a while. >>> >>> OK. I think it doesn't worth to eliminate IS NULL quals with this >>> complexity (at least at this stage of work). >>> >>> I made improvements over the code. Mostly new comments, grammar >>> corrections of existing comments and small refactoring. >>> >>> Also, I found that the suggestion from David Rowley [1] to qsort >>> array of relations to faster find duplicates is still unaddressed. >>> I've implemented it. That helps to evade quadratic complexity with >>> large number of relations. >>> >>> Also I've incorporated improvements from Alena Rybakina except one for >>> skipping SJ removal when no SJ quals is found. It's not yet clear for >>> me if this check fix some cases. But at least optimization got skipped >>> in some useful cases (as you can see in regression tests). >> >> I would like to propose one more minor improvement (see in attachment). >> The idea here is that after removing a self-join and changing clauses we >> should re-probe the set of relids with the same Oid, because we can find >> more removable self-joins (see the demo test in join.sql). > > > Thank you, I've integrated this into the patch. BTW, the patch > introduces two new GUC variables: enable_self_join_removal, > self_join_search_limit. enable_self_join_removal variable turns > on/off optimization at all. self_join_search_limit variable limits > its usage by the number of joins. AFICS, self_join_search_limit is > intended to protect us from quadratic complexity self-join removal > has. I tried to reproduce the extreme case. > > SELECT count(*) FROM pgbench_accounts a0, pgbench_accounts a1, ..., > pgbench_accounts a100 WHERE a0.aid = 1 AND a1.aid = a0.aid + 1 AND ... > AND a100.aid = a99.aid + 1; > > This query took 3778.432 ms with self-join removal disabled, and > 3756.009 ms with self-join removal enabled. So, no measurable > overhead. Similar to the higher number of joins. Can you imagine > some extreme case when self-join removal could introduce significant > overhead in comparison with other optimizer parts? If not, should we > remove self_join_search_limit GUC? Thanks, It was Zhihong Yu who worried about that case [1]. And my purpose was to show a method to avoid such a problem if it would be needed. I guess the main idea here is that we have a lot of self-joins, but only few of them (or no one) can be removed. I can't imagine a practical situation when we can be stuck in the problems here. So, I vote to remove this GUC. [1] https://www.postgresql.org/message-id/CALNJ-vTyL-LpvSOPZxpC63Et3LJLUAFZSfRqGEhT5Rj7_EEj7w%40mail.gmail.com -- regards, Andrey Lepikhov Postgres Professional
On Thu, Oct 19, 2023 at 6:16 AM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > On 19/10/2023 01:50, Alexander Korotkov wrote: > > This query took 3778.432 ms with self-join removal disabled, and > > 3756.009 ms with self-join removal enabled. So, no measurable > > overhead. Similar to the higher number of joins. Can you imagine > > some extreme case when self-join removal could introduce significant > > overhead in comparison with other optimizer parts? If not, should we > > remove self_join_search_limit GUC? > Thanks, > It was Zhihong Yu who worried about that case [1]. And my purpose was to > show a method to avoid such a problem if it would be needed. > I guess the main idea here is that we have a lot of self-joins, but only > few of them (or no one) can be removed. > I can't imagine a practical situation when we can be stuck in the > problems here. So, I vote to remove this GUC. I've removed the self_join_search_limit. Anyway there is enable_self_join_removal if the self join removal algorithm causes any problems. I also did some grammar corrections for the comments. I think the patch is getting to the committable shape. I noticed some failures on commitfest.cputube.org. I'd like to check how this version will pass it. ------ Regards, Alexander Korotkov
Вложения
On 22/10/2023 05:01, Alexander Korotkov wrote: > On Thu, Oct 19, 2023 at 6:16 AM Andrei Lepikhov > <a.lepikhov@postgrespro.ru> wrote: >> On 19/10/2023 01:50, Alexander Korotkov wrote: >>> This query took 3778.432 ms with self-join removal disabled, and >>> 3756.009 ms with self-join removal enabled. So, no measurable >>> overhead. Similar to the higher number of joins. Can you imagine >>> some extreme case when self-join removal could introduce significant >>> overhead in comparison with other optimizer parts? If not, should we >>> remove self_join_search_limit GUC? >> Thanks, >> It was Zhihong Yu who worried about that case [1]. And my purpose was to >> show a method to avoid such a problem if it would be needed. >> I guess the main idea here is that we have a lot of self-joins, but only >> few of them (or no one) can be removed. >> I can't imagine a practical situation when we can be stuck in the >> problems here. So, I vote to remove this GUC. > > I've removed the self_join_search_limit. Anyway there is > enable_self_join_removal if the self join removal algorithm causes any > problems. I also did some grammar corrections for the comments. I > think the patch is getting to the committable shape. I noticed some > failures on commitfest.cputube.org. I'd like to check how this > version will pass it. I have observed the final patch. A couple of minor changes can be made (see attachment). Also, I see room for improvement, but it can be done later. For example, we limit the optimization to only ordinary tables in this patch. It can be extended at least with partitioned and foreign tables soon. -- regards, Andrey Lepikhov Postgres Professional
Вложения
On Mon, Oct 23, 2023 at 6:43 AM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > On 22/10/2023 05:01, Alexander Korotkov wrote: > > On Thu, Oct 19, 2023 at 6:16 AM Andrei Lepikhov > > <a.lepikhov@postgrespro.ru> wrote: > >> On 19/10/2023 01:50, Alexander Korotkov wrote: > >>> This query took 3778.432 ms with self-join removal disabled, and > >>> 3756.009 ms with self-join removal enabled. So, no measurable > >>> overhead. Similar to the higher number of joins. Can you imagine > >>> some extreme case when self-join removal could introduce significant > >>> overhead in comparison with other optimizer parts? If not, should we > >>> remove self_join_search_limit GUC? > >> Thanks, > >> It was Zhihong Yu who worried about that case [1]. And my purpose was to > >> show a method to avoid such a problem if it would be needed. > >> I guess the main idea here is that we have a lot of self-joins, but only > >> few of them (or no one) can be removed. > >> I can't imagine a practical situation when we can be stuck in the > >> problems here. So, I vote to remove this GUC. > > > > I've removed the self_join_search_limit. Anyway there is > > enable_self_join_removal if the self join removal algorithm causes any > > problems. I also did some grammar corrections for the comments. I > > think the patch is getting to the committable shape. I noticed some > > failures on commitfest.cputube.org. I'd like to check how this > > version will pass it. > > I have observed the final patch. A couple of minor changes can be made > (see attachment). Thank you, Andrei! I've integrated your changes into the patch. > Also, I see room for improvement, but it can be done later. For example, > we limit the optimization to only ordinary tables in this patch. It can > be extended at least with partitioned and foreign tables soon. Yes, I think it's reasonable to postpone some improvements. It's important to get the basic feature in, make sure it's safe and stable. Then we can make improvements incrementally. I think this patch makes substantial improvement to query planning. It has received plenty of reviews. The code is currently in quite good shape. I didn't manage to find the cases when this optimization causes significant overhead to planning time. Even if such cases will be spotted there is a GUC option to disable this feature. So, I'll push this if there are no objections. ------ Regards, Alexander Korotkov
Вложения
Hi Alexander, 23.10.2023 12:47, Alexander Korotkov wrote: > I think this patch makes substantial improvement to query planning. > It has received plenty of reviews. The code is currently in quite > good shape. I didn't manage to find the cases when this optimization > causes significant overhead to planning time. Even if such cases will > be spotted there is a GUC option to disable this feature. So, I'll > push this if there are no objections. On a quick glance, I've noticed following typos/inconsistencies in the patch, which maybe worth fixing: s/cadidates/candidates/ s/uniquiness/uniqueness/ s/selfjoin/self-join/ s/seperate/separate/ Also, shouldn't the reference "see generate_implied_equalities" be "see generate_implied_equalities_for_column"? Best regards, Alexander
On Mon, Oct 23, 2023 at 2:00 PM Alexander Lakhin <exclusion@gmail.com> wrote: > 23.10.2023 12:47, Alexander Korotkov wrote: > > I think this patch makes substantial improvement to query planning. > > It has received plenty of reviews. The code is currently in quite > > good shape. I didn't manage to find the cases when this optimization > > causes significant overhead to planning time. Even if such cases will > > be spotted there is a GUC option to disable this feature. So, I'll > > push this if there are no objections. > > On a quick glance, I've noticed following typos/inconsistencies in the > patch, which maybe worth fixing: > s/cadidates/candidates/ > s/uniquiness/uniqueness/ > s/selfjoin/self-join/ > s/seperate/separate/ > > Also, shouldn't the reference "see generate_implied_equalities" be > "see generate_implied_equalities_for_column"? Fixed all of the above. Thank you for catching this! ------ Regards, Alexander Korotkov
Вложения
Hi Alexander, 23.10.2023 14:29, Alexander Korotkov wrote: > Fixed all of the above. Thank you for catching this! I've discovered that starting from d3d55ce57 the following query: CREATE TABLE t(a int PRIMARY KEY); WITH tt AS (SELECT * FROM t) UPDATE t SET a = tt.a + 1 FROM tt WHERE tt.a = t.a RETURNING t.a; triggers an error "variable not found in subplan target lists". (Commits 8a8ed916f and b5fb6736e don't fix this, unfortunately.) Best regards, Alexander
On 29/12/2023 12:00, Alexander Lakhin wrote: > Hi Alexander, > > 23.10.2023 14:29, Alexander Korotkov wrote: >> Fixed all of the above. Thank you for catching this! > > I've discovered that starting from d3d55ce57 the following query: > CREATE TABLE t(a int PRIMARY KEY); > > WITH tt AS (SELECT * FROM t) > UPDATE t SET a = tt.a + 1 FROM tt > WHERE tt.a = t.a RETURNING t.a; > > triggers an error "variable not found in subplan target lists". > (Commits 8a8ed916f and b5fb6736e don't fix this, unfortunately.) Thanks for the report! The problem is with the resultRelation field. We forget to replace the relid here. Could you check your issue with the patch in the attachment? Does it resolve this case? -- regards, Andrei Lepikhov Postgres Professional
Вложения
Hi Andrei, 29.12.2023 12:58, Andrei Lepikhov wrote: > Thanks for the report! > The problem is with the resultRelation field. We forget to replace the relid here. > Could you check your issue with the patch in the attachment? Does it resolve this case? > Yes, with the patch applied I see no error. Thank you! Best regards, Alexander
Hello Andrei and Alexander, Please look at the following query which produces an incorrect result since d3d55ce57: CREATE TABLE t(a int PRIMARY KEY, b int); INSERT INTO t VALUES (1, 1), (2, 1); SELECT * FROM t WHERE EXISTS (SELECT * FROM t t2 WHERE t2.a = t.b AND t2.b > 0); a | b ---+--- 1 | 1 (1 row) I think that the expected result is: a | b ---+--- 1 | 1 2 | 1 (2 rows) Best regards, Alexander
On Mon, Jan 8, 2024 at 10:00 PM Alexander Lakhin <exclusion@gmail.com> wrote: > Please look at the following query which produces an incorrect result since > d3d55ce57: > CREATE TABLE t(a int PRIMARY KEY, b int); > INSERT INTO t VALUES (1, 1), (2, 1); > SELECT * FROM t WHERE EXISTS (SELECT * FROM t t2 WHERE t2.a = t.b AND t2.b > 0); > > a | b > ---+--- > 1 | 1 > (1 row) > > I think that the expected result is: > a | b > ---+--- > 1 | 1 > 2 | 1 > (2 rows) Thank you for your report. I'm looking at this now. ------ Regards, Alexander Korotkov
On Mon, Jan 8, 2024 at 10:20 PM Alexander Korotkov <aekorotkov@gmail.com> wrote: > On Mon, Jan 8, 2024 at 10:00 PM Alexander Lakhin <exclusion@gmail.com> wrote: > > Please look at the following query which produces an incorrect result since > > d3d55ce57: > > CREATE TABLE t(a int PRIMARY KEY, b int); > > INSERT INTO t VALUES (1, 1), (2, 1); > > SELECT * FROM t WHERE EXISTS (SELECT * FROM t t2 WHERE t2.a = t.b AND t2.b > 0); > > > > a | b > > ---+--- > > 1 | 1 > > (1 row) > > > > I think that the expected result is: > > a | b > > ---+--- > > 1 | 1 > > 2 | 1 > > (2 rows) > > Thank you for your report. I'm looking at this now. Fixed in 30b4955a46. ------ Regards, Alexander Korotkov
09.01.2024 01:09, Alexander Korotkov wrote: > Fixed in 30b4955a46. Thank you for fixing that! I've found another anomaly coined with d3d55ce57. This query: CREATE TABLE t(a int PRIMARY KEY, b int); INSERT INTO t VALUES (1, 1), (2, 1); WITH t1 AS (SELECT * FROM t) UPDATE t SET b = t1.b + 1 FROM t1 WHERE t.a = t1.a RETURNING t.a, t1.b; gives "ERROR: variable not found in subplan target lists" on d3d55ce57, but starting from a7928a57b it gives an incorrect result: a | b ---+--- 1 | 2 2 | 2 (2 rows) Best regards, Alexander
On Tue, Jan 9, 2024 at 6:00 AM Alexander Lakhin <exclusion@gmail.com> wrote: > 09.01.2024 01:09, Alexander Korotkov wrote: > > Fixed in 30b4955a46. > > Thank you for fixing that! > > I've found another anomaly coined with d3d55ce57. This query: > CREATE TABLE t(a int PRIMARY KEY, b int); > INSERT INTO t VALUES (1, 1), (2, 1); > > WITH t1 AS (SELECT * FROM t) > UPDATE t SET b = t1.b + 1 FROM t1 > WHERE t.a = t1.a RETURNING t.a, t1.b; > > gives "ERROR: variable not found in subplan target lists" on d3d55ce57, but > starting from a7928a57b it gives an incorrect result: > a | b > ---+--- > 1 | 2 > 2 | 2 > (2 rows) I see. It seems to be not safe to apply SJE to the modify table target relation because it could use a different snapshot for the RETURNING clause. I think we should just forbid SJE to involve the modify table target relation. I'm planning to fix this later today. ------ Regards, Alexander Korotkov
On Tue, Jan 9, 2024 at 8:08 AM Alexander Korotkov <aekorotkov@gmail.com> wrote: > On Tue, Jan 9, 2024 at 6:00 AM Alexander Lakhin <exclusion@gmail.com> wrote: > > 09.01.2024 01:09, Alexander Korotkov wrote: > > > Fixed in 30b4955a46. > > > > Thank you for fixing that! > > > > I've found another anomaly coined with d3d55ce57. This query: > > CREATE TABLE t(a int PRIMARY KEY, b int); > > INSERT INTO t VALUES (1, 1), (2, 1); > > > > WITH t1 AS (SELECT * FROM t) > > UPDATE t SET b = t1.b + 1 FROM t1 > > WHERE t.a = t1.a RETURNING t.a, t1.b; > > > > gives "ERROR: variable not found in subplan target lists" on d3d55ce57, but > > starting from a7928a57b it gives an incorrect result: > > a | b > > ---+--- > > 1 | 2 > > 2 | 2 > > (2 rows) > > I see. It seems to be not safe to apply SJE to the modify table > target relation because it could use a different snapshot for the > RETURNING clause. I think we should just forbid SJE to involve the > modify table target relation. I'm planning to fix this later today. Fixed in 8c441c08279. ------ Regards, Alexander Korotkov
Hi Alexander,
09.01.2024 01:09, Alexander Korotkov wrote:
09.01.2024 01:09, Alexander Korotkov wrote:
Fixed in 30b4955a46.
Please look at the following query which fails with an error since
d3d55ce57:
create table t (i int primary key);
select t3.i from t t1
join t t2 on t1.i = t2.i,
lateral (select t1.i limit 1) t3;
ERROR: non-LATERAL parameter required by subquery
Best regards,
Alexander
On Sun, Feb 18, 2024 at 3:00 PM Alexander Lakhin <exclusion@gmail.com> wrote: > 09.01.2024 01:09, Alexander Korotkov wrote: > > Fixed in 30b4955a46. > > > Please look at the following query which fails with an error since > d3d55ce57: > > create table t (i int primary key); > > select t3.i from t t1 > join t t2 on t1.i = t2.i, > lateral (select t1.i limit 1) t3; > > ERROR: non-LATERAL parameter required by subquery Thank you for spotting. I'm looking at this. ------ Regards, Alexander Korotkov
On Sun, Feb 18, 2024 at 5:04 PM Alexander Korotkov <aekorotkov@gmail.com> wrote: > On Sun, Feb 18, 2024 at 3:00 PM Alexander Lakhin <exclusion@gmail.com> wrote: > > 09.01.2024 01:09, Alexander Korotkov wrote: > > > > Fixed in 30b4955a46. > > > > > > Please look at the following query which fails with an error since > > d3d55ce57: > > > > create table t (i int primary key); > > > > select t3.i from t t1 > > join t t2 on t1.i = t2.i, > > lateral (select t1.i limit 1) t3; > > > > ERROR: non-LATERAL parameter required by subquery > > Thank you for spotting. I'm looking at this. Attached is a draft patch fixing this query. Could you, please, recheck? ------ Regards, Alexander Korotkov
Вложения
18.02.2024 19:18, Alexander Korotkov wrote: > Attached is a draft patch fixing this query. Could you, please, recheck? Yes, this patch fixes the behavior for that query (I've also tried several similar queries). Though I don't know the code well enough to judge the code change. Best regards, Alexander
On 18/2/2024 23:18, Alexander Korotkov wrote: > On Sun, Feb 18, 2024 at 5:04 PM Alexander Korotkov <aekorotkov@gmail.com> wrote: >> On Sun, Feb 18, 2024 at 3:00 PM Alexander Lakhin <exclusion@gmail.com> wrote: >>> 09.01.2024 01:09, Alexander Korotkov wrote: >>> >>> Fixed in 30b4955a46. >>> >>> >>> Please look at the following query which fails with an error since >>> d3d55ce57: >>> >>> create table t (i int primary key); >>> >>> select t3.i from t t1 >>> join t t2 on t1.i = t2.i, >>> lateral (select t1.i limit 1) t3; >>> >>> ERROR: non-LATERAL parameter required by subquery >> >> Thank you for spotting. I'm looking at this. > > Attached is a draft patch fixing this query. Could you, please, recheck? I reviewed this patch. Why do you check only the target list? I guess these links can be everywhere. See the patch in the attachment with the elaborated test and slightly changed code. -- regards, Andrei Lepikhov Postgres Professional
Вложения
On Mon, Feb 19, 2024 at 1:24 PM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote:
On 18/2/2024 23:18, Alexander Korotkov wrote:
> On Sun, Feb 18, 2024 at 5:04 PM Alexander Korotkov <aekorotkov@gmail.com> wrote:
>> On Sun, Feb 18, 2024 at 3:00 PM Alexander Lakhin <exclusion@gmail.com> wrote:
>>> Please look at the following query which fails with an error since
>>> d3d55ce57:
>>>
>>> create table t (i int primary key);
>>>
>>> select t3.i from t t1
>>> join t t2 on t1.i = t2.i,
>>> lateral (select t1.i limit 1) t3;
>>>
>>> ERROR: non-LATERAL parameter required by subquery
>>
>> Thank you for spotting. I'm looking at this.
>
> Attached is a draft patch fixing this query. Could you, please, recheck?
I reviewed this patch. Why do you check only the target list? I guess
these links can be everywhere. See the patch in the attachment with the
elaborated test and slightly changed code.
I just noticed that this fix has been committed in 489072ab7a, but it's
just flat wrong.
* The fix walks the subquery and replaces all the Vars with a varno
equal to the relid of the removing rel, without checking the
varlevelsup. That is to say, a Var that belongs to the subquery itself
might also be replaced, which is wrong. For instance,
create table t (i int primary key);
explain (costs off)
select t3.i from t t1
join t t2 on t1.i = t2.i
join lateral (select * from (select t1.i offset 0) offset 0) t3 on true;
ERROR: no relation entry for relid 2
* The fix only traverses one level within the subquery, so Vars that
appear in subqueries with multiple levels cannot be replaced. For
instance,
explain (costs off)
select t4.i from t t1
join t t2 on t1.i = t2.i
join lateral (select t3.i from t t3, (select t1.i) offset 0) t4 on true;
ERROR: non-LATERAL parameter required by subquery
I think the right fix for these issues is to introduce a new element
'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker
to 1) recurse into subselects with sublevels_up increased, and 2)
perform the replacement only when varlevelsup is equal to sublevels_up.
Attached is a patch for the fix.
While writing the fix, I noticed some outdated comments. Such as in
remove_rel_from_query, the first for loop updates otherrel's attr_needed
as well as lateral_vars, but the comment only mentions attr_needed. So
this patch also fixes some outdated comments.
While writing the test cases, I found that the test cases for SJE are
quite messy. Below are what I have noticed:
* There are several test cases using catalog tables like pg_class,
pg_stats, pg_index, etc. for testing join removal. I don't see a reason
why we need to use catalog tables, and I think this just raises the risk
of instability.
* In many test cases, a mix of uppercase and lowercase keywords is used
in one query. I think it'd better to maintain consistency by using
either all uppercase or all lowercase keywords in one query.
* In most situations, we verify the plan and the output of a query like:
explain (costs off)
select ...;
select ...;
The two select queries are supposed to be the same. But in the SJE test
cases, I have noticed instances where the two select queries differ from
each other.
This patch also includes some cosmetic tweaks for SJE test cases. It
does not change the test cases using catalog tables though. I think
that should be a seperate patch.
Thanks
Richard
just flat wrong.
* The fix walks the subquery and replaces all the Vars with a varno
equal to the relid of the removing rel, without checking the
varlevelsup. That is to say, a Var that belongs to the subquery itself
might also be replaced, which is wrong. For instance,
create table t (i int primary key);
explain (costs off)
select t3.i from t t1
join t t2 on t1.i = t2.i
join lateral (select * from (select t1.i offset 0) offset 0) t3 on true;
ERROR: no relation entry for relid 2
* The fix only traverses one level within the subquery, so Vars that
appear in subqueries with multiple levels cannot be replaced. For
instance,
explain (costs off)
select t4.i from t t1
join t t2 on t1.i = t2.i
join lateral (select t3.i from t t3, (select t1.i) offset 0) t4 on true;
ERROR: non-LATERAL parameter required by subquery
I think the right fix for these issues is to introduce a new element
'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker
to 1) recurse into subselects with sublevels_up increased, and 2)
perform the replacement only when varlevelsup is equal to sublevels_up.
Attached is a patch for the fix.
While writing the fix, I noticed some outdated comments. Such as in
remove_rel_from_query, the first for loop updates otherrel's attr_needed
as well as lateral_vars, but the comment only mentions attr_needed. So
this patch also fixes some outdated comments.
While writing the test cases, I found that the test cases for SJE are
quite messy. Below are what I have noticed:
* There are several test cases using catalog tables like pg_class,
pg_stats, pg_index, etc. for testing join removal. I don't see a reason
why we need to use catalog tables, and I think this just raises the risk
of instability.
* In many test cases, a mix of uppercase and lowercase keywords is used
in one query. I think it'd better to maintain consistency by using
either all uppercase or all lowercase keywords in one query.
* In most situations, we verify the plan and the output of a query like:
explain (costs off)
select ...;
select ...;
The two select queries are supposed to be the same. But in the SJE test
cases, I have noticed instances where the two select queries differ from
each other.
This patch also includes some cosmetic tweaks for SJE test cases. It
does not change the test cases using catalog tables though. I think
that should be a seperate patch.
Thanks
Richard
Вложения
On 21/2/2024 14:26, Richard Guo wrote: > This patch also includes some cosmetic tweaks for SJE test cases. It > does not change the test cases using catalog tables though. I think > that should be a seperate patch. Thanks for this catch, it is really messy thing, keeping aside the question why we need two different subtrees for the same query. I will look into your fix. -- regards, Andrei Lepikhov Postgres Professional
On 21/2/2024 14:26, Richard Guo wrote: > I think the right fix for these issues is to introduce a new element > 'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker > to 1) recurse into subselects with sublevels_up increased, and 2) > perform the replacement only when varlevelsup is equal to sublevels_up. This code looks good. No idea how we have lost it before. > > While writing the fix, I noticed some outdated comments. Such as in > remove_rel_from_query, the first for loop updates otherrel's attr_needed > as well as lateral_vars, but the comment only mentions attr_needed. So > this patch also fixes some outdated comments. Thanks, looks good. > > While writing the test cases, I found that the test cases for SJE are > quite messy. Below are what I have noticed: > > * There are several test cases using catalog tables like pg_class, > pg_stats, pg_index, etc. for testing join removal. I don't see a reason > why we need to use catalog tables, and I think this just raises the risk > of instability. I see only one unusual query with the pg_class involved. > > * In many test cases, a mix of uppercase and lowercase keywords is used > in one query. I think it'd better to maintain consistency by using > either all uppercase or all lowercase keywords in one query. I see uppercase -> lowercase change: select t1.*, t2.a as ax from sj t1 join sj t2 and lowercase -> uppercase in many other cases: explain (costs off) I guess it is a matter of taste, so give up for the committer decision. Technically, it's OK. > > * In most situations, we verify the plan and the output of a query like: > > explain (costs off) > select ...; > select ...; > > The two select queries are supposed to be the same. But in the SJE test > cases, I have noticed instances where the two select queries differ from > each other. > > This patch also includes some cosmetic tweaks for SJE test cases. It > does not change the test cases using catalog tables though. I think > that should be a seperate patch. I can't assess the necessity of changing these dozens of lines of code because I follow another commenting style, but technically, it's still OK. -- regards, Andrei Lepikhov Postgres Professional
On Thu, Feb 22, 2024 at 10:51 AM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > On 21/2/2024 14:26, Richard Guo wrote: > > I think the right fix for these issues is to introduce a new element > > 'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker > > to 1) recurse into subselects with sublevels_up increased, and 2) > > perform the replacement only when varlevelsup is equal to sublevels_up. > This code looks good. No idea how we have lost it before. Thanks to Richard for the patch and to Andrei for review. I also find code looking good. Pushed with minor edits from me. ------ Regards, Alexander Korotkov
On Sat, Feb 24, 2024 at 12:36:59AM +0200, Alexander Korotkov wrote: > On Thu, Feb 22, 2024 at 10:51 AM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > > On 21/2/2024 14:26, Richard Guo wrote: > > > I think the right fix for these issues is to introduce a new element > > > 'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker > > > to 1) recurse into subselects with sublevels_up increased, and 2) > > > perform the replacement only when varlevelsup is equal to sublevels_up. > > This code looks good. No idea how we have lost it before. > > Thanks to Richard for the patch and to Andrei for review. I also find > code looking good. Pushed with minor edits from me. I feel this, commit 466979e, misses a few of our project standards: - The patch makes many non-whitespace changes to existing test queries. This makes it hard to review the consequences of the non-test part of the patch. Did you minimize such edits? Of course, not every such edit is avoidable. - The commit message doesn't convey whether this is refactoring or is a bug fix. This makes it hard to write release notes, among other things. From this mailing list thread, it gather it's a bug fix in 489072ab7a, hence v17-specific. The commit message for 489072ab7a is also silent about that commit's status as refactoring or as a bug fix. - Normally, I could answer the previous question by reading the test case diffs. However, in addition to the first point about non-whitespace changes, the first three join.sql patch hunks just change whitespace. Worse, since they move line breaks, "git diff -w" doesn't filter them out. To what extent are those community standards vs. points of individual committer preference? Please tell me where I'm wrong here.
Hi, Noah! On Sat, Feb 24, 2024 at 7:12 AM Noah Misch <noah@leadboat.com> wrote: > On Sat, Feb 24, 2024 at 12:36:59AM +0200, Alexander Korotkov wrote: > > On Thu, Feb 22, 2024 at 10:51 AM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > > > On 21/2/2024 14:26, Richard Guo wrote: > > > > I think the right fix for these issues is to introduce a new element > > > > 'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker > > > > to 1) recurse into subselects with sublevels_up increased, and 2) > > > > perform the replacement only when varlevelsup is equal to sublevels_up. > > > This code looks good. No idea how we have lost it before. > > > > Thanks to Richard for the patch and to Andrei for review. I also find > > code looking good. Pushed with minor edits from me. > > I feel this, commit 466979e, misses a few of our project standards: > > - The patch makes many non-whitespace changes to existing test queries. This > makes it hard to review the consequences of the non-test part of the patch. > Did you minimize such edits? Of course, not every such edit is avoidable. > > - The commit message doesn't convey whether this is refactoring or is a bug > fix. This makes it hard to write release notes, among other things. From > this mailing list thread, it gather it's a bug fix in 489072ab7a, hence > v17-specific. The commit message for 489072ab7a is also silent about that > commit's status as refactoring or as a bug fix. > > - Normally, I could answer the previous question by reading the test case > diffs. However, in addition to the first point about non-whitespace > changes, the first three join.sql patch hunks just change whitespace. > Worse, since they move line breaks, "git diff -w" doesn't filter them out. > > To what extent are those community standards vs. points of individual > committer preference? Please tell me where I'm wrong here. I agree that commit 466979e is my individual committer failure. I should have written a better, more clear commit message and separate tests refactoring from the bug fix. I'm not so sure about 489072ab7a (except it provides a wrong fix). It has a "Reported-by:" field meaning it's a problem reported by a particular person. The "Discussion:" points directly to the reported test case. And commit contains the relevant test case. The commit message could be more wordy though. ------ Regards, Alexander Korotkov
Hello, On Sat, Feb 24, 2024 at 01:02:01PM +0200, Alexander Korotkov wrote: > On Sat, Feb 24, 2024 at 7:12 AM Noah Misch <noah@leadboat.com> wrote: > > On Sat, Feb 24, 2024 at 12:36:59AM +0200, Alexander Korotkov wrote: > > > On Thu, Feb 22, 2024 at 10:51 AM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > > > > On 21/2/2024 14:26, Richard Guo wrote: > > > > > I think the right fix for these issues is to introduce a new element > > > > > 'sublevels_up' in ReplaceVarnoContext, and enhance replace_varno_walker > > > > > to 1) recurse into subselects with sublevels_up increased, and 2) > > > > > perform the replacement only when varlevelsup is equal to sublevels_up. > > > > This code looks good. No idea how we have lost it before. > > > > > > Thanks to Richard for the patch and to Andrei for review. I also find > > > code looking good. Pushed with minor edits from me. > > > > I feel this, commit 466979e, misses a few of our project standards: > > > > - The patch makes many non-whitespace changes to existing test queries. This > > makes it hard to review the consequences of the non-test part of the patch. > > Did you minimize such edits? Of course, not every such edit is avoidable. > > > > - The commit message doesn't convey whether this is refactoring or is a bug > > fix. This makes it hard to write release notes, among other things. From > > this mailing list thread, it gather it's a bug fix in 489072ab7a, hence > > v17-specific. The commit message for 489072ab7a is also silent about that > > commit's status as refactoring or as a bug fix. > > > > - Normally, I could answer the previous question by reading the test case > > diffs. However, in addition to the first point about non-whitespace > > changes, the first three join.sql patch hunks just change whitespace. > > Worse, since they move line breaks, "git diff -w" doesn't filter them out. > > > > To what extent are those community standards vs. points of individual > > committer preference? Please tell me where I'm wrong here. > > I agree that commit 466979e is my individual committer failure. I > should have written a better, more clear commit message and separate > tests refactoring from the bug fix. > > I'm not so sure about 489072ab7a (except it provides a wrong fix). It > has a "Reported-by:" field meaning it's a problem reported by a > particular person. The "Discussion:" points directly to the reported > test case. And commit contains the relevant test case. The commit > message could be more wordy though. Agreed, the first and third points don't apply to 489072ab7a. Thanks to that, one can deduce from its new test case query that it fixes a bug. It sounds like we agree about commit 466979e, so that's good.
Hello Alexander,
23.10.2023 12:47, Alexander Korotkov wrote:
> I think this patch makes substantial improvement to query planning.
> It has received plenty of reviews. The code is currently in quite
> good shape. I didn't manage to find the cases when this optimization
> causes significant overhead to planning time. Even if such cases will
> be spotted there is a GUC option to disable this feature. So, I'll
> push this if there are no objections.
I've discovered another failure, introduced by d3d55ce57.
Please try the following:
CREATE TABLE t (a int unique, b float);
SELECT * FROM t NATURAL JOIN LATERAL
(SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2;
With asserts enabled, it triggers
TRAP: failed Assert("!bms_is_member(rti, lateral_relids)"), File: "initsplan.c", Line: 697, PID: 3074054
ExceptionalCondition at assert.c:52:13
create_lateral_join_info at initsplan.c:700:8
query_planner at planmain.c:257:2
grouping_planner at planner.c:1523:17
subquery_planner at planner.c:1098:2
standard_planner at planner.c:415:9
planner at planner.c:282:12
pg_plan_query at postgres.c:904:9
pg_plan_queries at postgres.c:996:11
exec_simple_query at postgres.c:1193:19
PostgresMain at postgres.c:4684:27
With no asserts, I get:
ERROR: failed to construct the join relation
Please take a look at this.
Best regards,
Alexander
Hi, Alexander!
On Tue, Apr 30, 2024 at 9:00 AM Alexander Lakhin <exclusion@gmail.com> wrote:
> 23.10.2023 12:47, Alexander Korotkov wrote:
> > I think this patch makes substantial improvement to query planning.
> > It has received plenty of reviews. The code is currently in quite
> > good shape. I didn't manage to find the cases when this optimization
> > causes significant overhead to planning time. Even if such cases will
> > be spotted there is a GUC option to disable this feature. So, I'll
> > push this if there are no objections.
>
> I've discovered another failure, introduced by d3d55ce57.
> Please try the following:
> CREATE TABLE t (a int unique, b float);
> SELECT * FROM t NATURAL JOIN LATERAL
> (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2;
>
> With asserts enabled, it triggers
> TRAP: failed Assert("!bms_is_member(rti, lateral_relids)"), File: "initsplan.c", Line: 697, PID: 3074054
> ExceptionalCondition at assert.c:52:13
> create_lateral_join_info at initsplan.c:700:8
> query_planner at planmain.c:257:2
> grouping_planner at planner.c:1523:17
> subquery_planner at planner.c:1098:2
> standard_planner at planner.c:415:9
> planner at planner.c:282:12
> pg_plan_query at postgres.c:904:9
> pg_plan_queries at postgres.c:996:11
> exec_simple_query at postgres.c:1193:19
> PostgresMain at postgres.c:4684:27
>
> With no asserts, I get:
> ERROR: failed to construct the join relation
>
> Please take a look at this.
I'm looking into this, thank you!
------
Regards,
Alexander Korotkov
On Tue, Apr 30, 2024 at 9:00 AM Alexander Lakhin <exclusion@gmail.com> wrote: > 23.10.2023 12:47, Alexander Korotkov wrote: > > I think this patch makes substantial improvement to query planning. > > It has received plenty of reviews. The code is currently in quite > > good shape. I didn't manage to find the cases when this optimization > > causes significant overhead to planning time. Even if such cases will > > be spotted there is a GUC option to disable this feature. So, I'll > > push this if there are no objections. > > I've discovered another failure, introduced by d3d55ce57. > Please try the following: > CREATE TABLE t (a int unique, b float); > SELECT * FROM t NATURAL JOIN LATERAL > (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2; I think we should just forbid SJE in case when relations to be merged have cross-references with lateral vars. The draft patch for this is attached. I'd like to ask Alexander to test it, Richard and Andrei to review it. Thank you! ------ Regards, Alexander Korotkov
Вложения
30.04.2024 13:20, Alexander Korotkov wrote: > On Tue, Apr 30, 2024 at 9:00 AM Alexander Lakhin <exclusion@gmail.com> wrote: >> I've discovered another failure, introduced by d3d55ce57. >> Please try the following: >> CREATE TABLE t (a int unique, b float); >> SELECT * FROM t NATURAL JOIN LATERAL >> (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2; > I think we should just forbid SJE in case when relations to be merged > have cross-references with lateral vars. The draft patch for this is > attached. I'd like to ask Alexander to test it, Richard and Andrei to > review it. Thank you! Beside LATERAL vars, it seems that SJR doesn't play well with TABLESAMPLE in general. For instance: CREATE TABLE t (a int unique); INSERT INTO t SELECT * FROM generate_series (1,100); SELECT COUNT(*) FROM (SELECT * FROM t TABLESAMPLE BERNOULLI(1)) t1 NATURAL JOIN (SELECT * FROM t TABLESAMPLE BERNOULLI(100)) t2; returned 100, 100, 100 for me, though with enable_self_join_removal = off, I got 4, 0, 1... Best regards, Alexander
On Wed, May 1, 2024 at 2:00 PM Alexander Lakhin <exclusion@gmail.com> wrote: > 30.04.2024 13:20, Alexander Korotkov wrote: > > On Tue, Apr 30, 2024 at 9:00 AM Alexander Lakhin <exclusion@gmail.com> wrote: > >> I've discovered another failure, introduced by d3d55ce57. > >> Please try the following: > >> CREATE TABLE t (a int unique, b float); > >> SELECT * FROM t NATURAL JOIN LATERAL > >> (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b)) t2; > > I think we should just forbid SJE in case when relations to be merged > > have cross-references with lateral vars. The draft patch for this is > > attached. I'd like to ask Alexander to test it, Richard and Andrei to > > review it. Thank you! > > Beside LATERAL vars, it seems that SJR doesn't play well with TABLESAMPLE > in general. For instance: > CREATE TABLE t (a int unique); > INSERT INTO t SELECT * FROM generate_series (1,100); > > SELECT COUNT(*) FROM (SELECT * FROM t TABLESAMPLE BERNOULLI(1)) t1 > NATURAL JOIN (SELECT * FROM t TABLESAMPLE BERNOULLI(100)) t2; > returned 100, 100, 100 for me, though with enable_self_join_removal = off, > I got 4, 0, 1... Right, thank you for reporting this. BTW, I found another case where my previous fix doesn't work. SELECT * FROM t NATURAL JOIN LATERAL (SELECT * FROM t t2 TABLESAMPLE SYSTEM (t.b) NATURAL JOIN LATERAL(SELECT * FROM t t3 TABLESAMPLE SYSTEM (t2.b)) t3) t2; I think we probably could forbid SJE for the tables with TABLESAMPLE altogether. Please, check the attached patch. ------ Regards, Alexander Korotkov
Вложения
On 5/1/24 18:59, Alexander Korotkov wrote: > I think we probably could forbid SJE for the tables with TABLESAMPLE > altogether. Please, check the attached patch. Your patch looks good to me. I added some comments and test case into the join.sql. One question for me is: Do we anticipate other lateral self-references except the TABLESAMPLE case? Looking into the extract_lateral_references implementation, I see the only RTE_SUBQUERY case to be afraid of. But we pull up subqueries before extracting lateral references. So, if we have a reference to a subquery, it means we will not flatten this subquery and don't execute SJE. Do we need more code, as you have written in the first patch? -- regards, Andrei Lepikhov Postgres Professional
Вложения
On Thu, May 2, 2024 at 12:45 PM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > > On 5/1/24 18:59, Alexander Korotkov wrote: > > I think we probably could forbid SJE for the tables with TABLESAMPLE > > altogether. Please, check the attached patch. > Your patch looks good to me. I added some comments and test case into > the join.sql. Thank you > One question for me is: Do we anticipate other lateral self-references > except the TABLESAMPLE case? Looking into the extract_lateral_references > implementation, I see the only RTE_SUBQUERY case to be afraid of. But we > pull up subqueries before extracting lateral references. So, if we have > a reference to a subquery, it means we will not flatten this subquery > and don't execute SJE. Do we need more code, as you have written in the > first patch? I think my first patch was crap anyway. Your explanation seems reasonable to me. I'm not sure this requires any more code. Probably it would be enough to add more comments about this. ------ Regards, Alexander Korotkov
On Thu, May 2, 2024 at 6:08 PM Alexander Korotkov <aekorotkov@gmail.com> wrote:
On Thu, May 2, 2024 at 12:45 PM Andrei Lepikhov
<a.lepikhov@postgrespro.ru> wrote:
> One question for me is: Do we anticipate other lateral self-references
> except the TABLESAMPLE case? Looking into the extract_lateral_references
> implementation, I see the only RTE_SUBQUERY case to be afraid of. But we
> pull up subqueries before extracting lateral references. So, if we have
> a reference to a subquery, it means we will not flatten this subquery
> and don't execute SJE. Do we need more code, as you have written in the
> first patch?
I think my first patch was crap anyway. Your explanation seems
reasonable to me. I'm not sure this requires any more code. Probably
it would be enough to add more comments about this.
The tablesample case is not the only factor that can cause a relation to
have a lateral dependency on itself after self-join removal. It can
also happen with PHVs. As an example, consider
explain (costs off)
select * from t t1
left join lateral
(select t1.a as t1a, * from t t2) t2
on true
where t1.a = t2.a;
server closed the connection unexpectedly
This is because after self-join removal, a PlaceHolderInfo's ph_lateral
might contain rels mentioned in ph_eval_at, which we should get rid of.
For the tablesample case, I agree that we should not consider relations
with TABLESAMPLE clauses as candidates to be removed. Removing such a
relation could potentially change the syntax of the query, as shown by
Alexander's example. It seems to me that we can just check that in
remove_self_joins_recurse, while we're collecting the base relations
that are considered to be candidates for removal.
This leads to the attached patch. This patch also includes some code
refactoring for the surrounding code.
Thanks
Richard
have a lateral dependency on itself after self-join removal. It can
also happen with PHVs. As an example, consider
explain (costs off)
select * from t t1
left join lateral
(select t1.a as t1a, * from t t2) t2
on true
where t1.a = t2.a;
server closed the connection unexpectedly
This is because after self-join removal, a PlaceHolderInfo's ph_lateral
might contain rels mentioned in ph_eval_at, which we should get rid of.
For the tablesample case, I agree that we should not consider relations
with TABLESAMPLE clauses as candidates to be removed. Removing such a
relation could potentially change the syntax of the query, as shown by
Alexander's example. It seems to me that we can just check that in
remove_self_joins_recurse, while we're collecting the base relations
that are considered to be candidates for removal.
This leads to the attached patch. This patch also includes some code
refactoring for the surrounding code.
Thanks
Richard
Вложения
Hi, Richard! On Thu, May 2, 2024 at 4:14 PM Richard Guo <guofenglinux@gmail.com> wrote: > On Thu, May 2, 2024 at 6:08 PM Alexander Korotkov <aekorotkov@gmail.com> wrote: >> On Thu, May 2, 2024 at 12:45 PM Andrei Lepikhov >> <a.lepikhov@postgrespro.ru> wrote: >> > One question for me is: Do we anticipate other lateral self-references >> > except the TABLESAMPLE case? Looking into the extract_lateral_references >> > implementation, I see the only RTE_SUBQUERY case to be afraid of. But we >> > pull up subqueries before extracting lateral references. So, if we have >> > a reference to a subquery, it means we will not flatten this subquery >> > and don't execute SJE. Do we need more code, as you have written in the >> > first patch? >> >> I think my first patch was crap anyway. Your explanation seems >> reasonable to me. I'm not sure this requires any more code. Probably >> it would be enough to add more comments about this. > > > The tablesample case is not the only factor that can cause a relation to > have a lateral dependency on itself after self-join removal. It can > also happen with PHVs. As an example, consider > > explain (costs off) > select * from t t1 > left join lateral > (select t1.a as t1a, * from t t2) t2 > on true > where t1.a = t2.a; > server closed the connection unexpectedly > > This is because after self-join removal, a PlaceHolderInfo's ph_lateral > might contain rels mentioned in ph_eval_at, which we should get rid of. > > For the tablesample case, I agree that we should not consider relations > with TABLESAMPLE clauses as candidates to be removed. Removing such a > relation could potentially change the syntax of the query, as shown by > Alexander's example. It seems to me that we can just check that in > remove_self_joins_recurse, while we're collecting the base relations > that are considered to be candidates for removal. > > This leads to the attached patch. This patch also includes some code > refactoring for the surrounding code. Great, thank you for your work on this! I'd like to split this into separate patches for better granularity of git history. I also added 0001 patch, which makes first usage of the SJE acronym in file to come with disambiguation. Also, I've added assert that ph_lateral and ph_eval_at didn't overlap before the changes. I think this should help from the potential situation when the changes we do could mask another bug. I would appreciate your review of this patchset, and review from Andrei as well. ------ Regards, Alexander Korotkov Supabase
Вложения
Alexander Korotkov <aekorotkov@gmail.com> writes:
> I would appreciate your review of this patchset, and review from Andrei as well.
I hate to say this ... but if we're still finding bugs this
basic in SJE, isn't it time to give up on it for v17?
I might feel better about it if there were any reason to think
these were the last major bugs. But you have already committed
around twenty separate fixes for the original SJE patch, and
now here you come with several more; so it doesn't seem like
the defect rate has slowed materially. There can be no doubt
whatever that the original patch was far from commit-ready.
I think we should revert SJE for v17 and do a thorough design
review before trying again in v18.
regards, tom lane
On 5/3/24 06:19, Tom Lane wrote: > Alexander Korotkov <aekorotkov@gmail.com> writes: >> I would appreciate your review of this patchset, and review from Andrei as well. > > I hate to say this ... but if we're still finding bugs this > basic in SJE, isn't it time to give up on it for v17? > > I might feel better about it if there were any reason to think > these were the last major bugs. But you have already committed > around twenty separate fixes for the original SJE patch, and > now here you come with several more; so it doesn't seem like > the defect rate has slowed materially. There can be no doubt > whatever that the original patch was far from commit-ready. > > I think we should revert SJE for v17 and do a thorough design > review before trying again in v18. I need to say I don't see any evidence of bad design. I think this feature follows the example of 2489d76 [1], 1349d27 [2], and partitionwise join features — we get some issues from time to time, but these strengths and frequencies are significantly reduced. First and foremost, this feature is highly isolated: like the PWJ feature, you can just disable (not enable?) SJE and it guarantees you will avoid the problems. Secondly, this feature reflects the design decisions the optimiser has made before. It raises some questions: Do we really control the consistency of our paths and the plan tree? Maybe we hide our misunderstanding of its logic by extensively copying expression trees, sometimes without fundamental necessity. Perhaps the optimiser needs some abstraction layers or reconstruction to reduce the quickly growing complexity. A good example here is [1]. IMO, the new promising feature it has introduced isn't worth the complexity it added to the planner. SJE, much like OR <-> ANY transformation, introduces a fresh perspective into the planner: if we encounter a complex, redundant query, it may be more beneficial to invest in simplifying the internal query representation rather than adding new optimisations that will grapple with this complexity. Also, SJE raised questions I've never seen before, like: Could we control the consistency of the PlannerInfo by changing something in the logic? Considering the current state, I don't see any concrete outcomes or evidence that a redesign of the feature will lead us to a new path. However, I believe the presence of SJE in the core could potentially trigger improvements in the planner. As a result, I vote to stay with the feature. But remember, as an author, I'm not entirely objective, so let's wait for alternative opinions. [1] Make Vars be outer-join-aware [2] Improve performance of ORDER BY / DISTINCT aggregates -- regards, Andrei Lepikhov Postgres Professional
Hi, Tom! On Fri, May 3, 2024 at 2:19 AM Tom Lane <tgl@sss.pgh.pa.us> wrote: > Alexander Korotkov <aekorotkov@gmail.com> writes: > > I would appreciate your review of this patchset, and review from Andrei as well. > > I hate to say this ... but if we're still finding bugs this > basic in SJE, isn't it time to give up on it for v17? > > I might feel better about it if there were any reason to think > these were the last major bugs. But you have already committed > around twenty separate fixes for the original SJE patch, and > now here you come with several more; so it doesn't seem like > the defect rate has slowed materially. There can be no doubt > whatever that the original patch was far from commit-ready. I think if we subtract from the SJE followup commits containing improvements (extra comments, asserts) and fix for in-place Bitmapset modification, which was there before, the number of fixes will be closer to ten. And the number of pending fixes will be two. But I totally get your concern that we're quite late in the release cycle and new SJE-related issues continue to arise. This leads to a significant risk of raising many bugs for end users. > I think we should revert SJE for v17 and do a thorough design > review before trying again in v18. I agree to revert it for v17, but I'm not exactly sure the issue is design (nevertheless design review is very welcome as any other type of review). The experience of the bugs arising with the SJE doesn't show me a particular weak spot in the feature. It looks more like this patch has to revise awfully a lot planner data structures to replace one relid with another. And I don't see the design, which could avoid that. Somewhere in the thread I have proposed a concept of "alias relids". However, I suspect that could leave us with more lurking bugs instead of the bug-free code. I suggest we should give this feature more review and testing, then commit early v18. That would leave us enough time to fix any other issues before v18 release. ------ Regards, Alexander Korotkov Supabase
On Fri, May 3, 2024 at 4:57 AM Alexander Korotkov <aekorotkov@gmail.com> wrote: > I agree to revert it for v17, but I'm not exactly sure the issue is > design (nevertheless design review is very welcome as any other type > of review). The experience of the bugs arising with the SJE doesn't > show me a particular weak spot in the feature. It looks more like > this patch has to revise awfully a lot planner data structures to > replace one relid with another. And I don't see the design, which > could avoid that. Somewhere in the thread I have proposed a concept > of "alias relids". However, I suspect that could leave us with more > lurking bugs instead of the bug-free code. I agree that reverting it for v17 makes sense. In terms of moving forward, whether a design review is exactly the right idea or not, I'm not sure. However, I think that the need to replace relids in a lot of places is something that a design review might potentially flag as a problem. Maybe there is some other approach that can avoid the need for this. On the other hand, maybe there's not. But in that case, the question becomes how the patch author(s), and committer, are going to make sure that most of the issues get flushed out before the initial commit. What we can't do is say - we know that we need to replace relids in a bunch of places, so we'll change the ones we know about, and then rely on testing to find any that we missed. There has to be some kind of systematic plan that everyone can agree should find all of the affected places, and then if a few slip through, that's fine, that's how life goes. I haven't followed the self-join elimination work very closely, and I do quite like the idea of the feature. However, looking over all the follow-up commits, it's pretty hard to escape the conclusion that there were a lot of cases that weren't adequately considered in the initial work (lateral, result relations, PHVs, etc.). And that is a big problem -- it really creates a lot of issues for the project when a major feature commit misses whole areas that it needs to have considered, as plenty of previous history will show. When anybody starts to realize that they've not just had a few goofs but have missed some whole affected area entirely, it's time to start thinking about a revert. One of my most embarrassing gaffes in this area personally was a448e49bcbe40fb72e1ed85af910dd216d45bad8. I don't know how I managed to commit the original patch without realizing it was going to cause an increase in the WAL size, but I can tell you that when I realized it, my heart sank through the floor. I'd love to return to that work if we can all ever agree on a way of addressing that problem, but in the meantime, that patch is very dead. And ... if somebody had taken the time to give me a really good design review of that patch, they might well have noticed, and saved me the embarrassment of committing something that had no shot of remaining in the tree. Unfortunately, one of the downsides of being a committer is that you tend to get less of that sort of review, because people assume you know what you're doing. Which is fabulous, when you actually do know what you're doing, and really sucks, when you don't. One of the things I'd like to see discussed at 2024.pgconf.dev is how we can improve this aspect of how we work together. -- Robert Haas EDB: http://www.enterprisedb.com
On 3/5/2024 20:55, Robert Haas wrote: > One of my most embarrassing gaffes in this area personally was > a448e49bcbe40fb72e1ed85af910dd216d45bad8. I don't know how I managed > to commit the original patch without realizing it was going to cause > an increase in the WAL size, but I can tell you that when I realized > it, my heart sank through the floor. I discovered this feature and agree that it looks like a severe problem. Unfortunately, in the case of the SJE patch, the committer and reviewers don't provide negative feedback. We see the only (I'm not sure I use the proper English phrase) 'negative feelings' from people who haven't reviewed or analysed it at all (at least, they didn't mention it). Considering the situation, I suggest setting the default value of enable_self_join_removal to false in PG17 for added safety and then changing it to true in early PG18. Having no objective negative feedback, we have no reason to change anything in the design or any part of the code. It looks regrettable and unusual. After designing the feature, fixing its bugs, and reviewing joint patches on the commitfest, the question more likely lies in the planner design. For example, I wonder if anyone here knows why exactly the optimiser makes a copy of the whole query subtree in some places. Another example is PlannerInfo. Can we really control all the consequences of introducing, let's say, a new JoinDomain entity? You also mentioned 2024.pgconf.dev. Considering the current migration policy in some countries, it would be better to work through the online presence as equivalent to offline. Without an online part of the conference, the only way to communicate and discuss is through this mailing list. -- regards, Andrei Lepikhov
On Sat, May 4, 2024 at 10:46 PM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > Having no objective negative feedback, we have no reason to change > anything in the design or any part of the code. It looks regrettable and > unusual. To me, this sounds like you think it's someone else's job to tell you what is wrong with the patch, or how to fix it, and if they don't, then you should get to have the patch as part of PostgreSQL. But that is not how we do things, nor should we. I agree that it sucks when you need feedback and don't get it, and I've written about that elsewhere and recently. But if you don't get feedback and as a result you can't get the patch to an acceptable level, or if you do get feedback but the patch fails to reach an acceptable level anyway, then the only correct decision is for us to not ship that code. That obviously sucks from the point of view of the patch author, and also of the committer, but consider the alternative. Once patches get through an initial release and become part of the product, the responsibility for fixing problems is understood to slowly move from the original committer to the community as a whole. In practice, that means that a lot of the work of fixing things that are broken, after some initial period, ends up falling on committers other than the person who did the initial commit. Even one or two problematic commits can generate an enormous amount of work for people who weren't involved in the original development and may not even have agreed with the development direction, and it is more than fair for those people to express a view about whether they are willing to carry that burden or not. When they aren't, I do think that's regrettable, but I don't think it's unusual. Just in this release, we've removed at least two previously-released features because they're in bad shape and nobody's willing to maintain them (snapshot too old, AIX support). > After designing the feature, fixing its bugs, and reviewing joint > patches on the commitfest, the question more likely lies in the planner > design. For example, I wonder if anyone here knows why exactly the > optimiser makes a copy of the whole query subtree in some places. > Another example is PlannerInfo. Can we really control all the > consequences of introducing, let's say, a new JoinDomain entity? Bluntly, if you can't control those consequences, then you aren't allowed to make that change. I know first-hand how difficult some of these problems are. Sometime in the last year or three, I spent weeks getting rid of ONE global variable (ThisTimeLineID). It took an absolutely inordinate amount of time, and it became clear to me that I was never going to get rid of enough global variables in that part of the code to be able to write a patch for the feature I wanted without risk of unforeseen consequences. So I gave up on the entire feature. Maybe I'll try again at some point, or maybe somebody else will feel like cleaning up that code and then I can try again with a cleaner base, but what I don't get to do is write a buggy patch for the feature I want and commit it anyway. I either figure out a way to do it that I believe is low-risk and that the community judges to be acceptable, or I don't do it. I want to go on record right now as disagreeing with the plan proposed in the commit message for the revert commit, namely, committing this again early in the v18 cycle. I don't think Tom would have proposed reverting this feature unless he believed that it had more serious problems than could be easily fixed in a short period of time. I think that concern is well-founded, given the number of fixes that were committed. It seems likely that the patch needs significant rework and stabilization before it gets committed again, and I think it shouldn't be committed again without explicit agreement from Tom or one of the other committers who have significant experience with the query planner. That is not to say that I don't approve generally of the idea of committing things earlier in the release cycle: I certainly do. It gives us more time to shake out problems with patches before we ship. But it only makes sense if we collectively believe that the patch is mostly correct, and only needs fine-tuning, and I think there are good reasons to believe that we shouldn't have that level of confidence in this case. -- Robert Haas EDB: http://www.enterprisedb.com
On Mon, May 6, 2024 at 10:44:33AM -0400, Robert Haas wrote: > I want to go on record right now as disagreeing with the plan proposed > in the commit message for the revert commit, namely, committing this > again early in the v18 cycle. I don't think Tom would have proposed > reverting this feature unless he believed that it had more serious > problems than could be easily fixed in a short period of time. I think > that concern is well-founded, given the number of fixes that were > committed. It seems likely that the patch needs significant rework and > stabilization before it gets committed again, and I think it shouldn't > be committed again without explicit agreement from Tom or one of the > other committers who have significant experience with the query > planner. That is not to say that I don't approve generally of the idea > of committing things earlier in the release cycle: I certainly do. It > gives us more time to shake out problems with patches before we ship. > But it only makes sense if we collectively believe that the patch is > mostly correct, and only needs fine-tuning, and I think there are good > reasons to believe that we shouldn't have that level of confidence in > this case. I think what Robert is saying is that it is an unacceptable plan to just dump the code into PG 18 and clean it up in the following months --- it needs more research before it is re-added to git. -- Bruce Momjian <bruce@momjian.us> https://momjian.us EDB https://enterprisedb.com Only you can decide what is important to you.
Robert Haas <robertmhaas@gmail.com> writes:
> I want to go on record right now as disagreeing with the plan proposed
> in the commit message for the revert commit, namely, committing this
> again early in the v18 cycle. I don't think Tom would have proposed
> reverting this feature unless he believed that it had more serious
> problems than could be easily fixed in a short period of time. I think
> that concern is well-founded, given the number of fixes that were
> committed. It seems likely that the patch needs significant rework and
> stabilization before it gets committed again, and I think it shouldn't
> be committed again without explicit agreement from Tom or one of the
> other committers who have significant experience with the query
> planner.
FWIW I accept some of the blame here, for not having paid any
attention to the SJE work earlier. I had other things on my mind
for most of last year, and not enough bandwidth to help.
The main thing I'd like to understand before we try this again is
why SJE needed so much new query-tree-manipulation infrastructure.
I would have expected it to be very similar to the left-join
elimination we do already, and therefore to mostly just share the
existing infrastructure. (I also harbor suspicions that some of
the new code existed just because someone didn't research what
was already there --- for instance, the now-removed replace_varno
sure looks like ChangeVarNodes should have been used instead.)
Another thing that made me pretty sad was 8c441c082 (Forbid SJE with
result relation). While I don't claim that that destroyed the entire
use case for SJE, it certainly knocked its usefulness down by many
notches, maybe even to the point where it's not worth putting in the
effort needed to get it to re-committability. So I think we need to
look harder at finding a way around that. Is the concern that
RETURNING should return either old or new values depending on which
RTE is mentioned? If so, maybe the feature Dean has proposed to
allow RETURNING to access old values [1] is a prerequisite to moving
forward. Alternatively, perhaps it'd be good enough to forbid SJE
only when the non-target relation is actually mentioned in RETURNING.
regards, tom lane
[1] https://www.postgresql.org/message-id/flat/CAEZATCWx0J0-v=Qjc6gXzR=KtsdvAE7Ow=D=mu50AgOe+pvisQ@mail.gmail.com
On 6/5/2024 21:44, Robert Haas wrote: > On Sat, May 4, 2024 at 10:46 PM Andrei Lepikhov > <a.lepikhov@postgrespro.ru> wrote: >> Having no objective negative feedback, we have no reason to change >> anything in the design or any part of the code. It looks regrettable and >> unusual. > > To me, this sounds like you think it's someone else's job to tell you > what is wrong with the patch, or how to fix it, and if they don't, > then you should get to have the patch as part of PostgreSQL. But that > is not how we do things, nor should we. I agree that it sucks when you > need feedback and don't get it, and I've written about that elsewhere > and recently. But if you don't get feedback and as a result you can't > get the patch to an acceptable level, I'm really sorry that the level of my language caused a misunderstanding. The main purpose of this work is to form a more or less certain view of the direction of the planner's development. Right now, it evolves extensively - new structures, variables, alternative copies of the same node trees with slightly changed properties ... This way allows us to quickly introduce some planning features (a lot of changes in planner logic since PG16 is evidence of that) and with still growing computing resources it allows postgres to fit RAM and proper planning time. But maybe we want to be more modest? The Ashutosh's work he has been doing this year shows how sometimes expensive the planner is. Perhaps we want machinery that will check the integrity of planning data except the setrefs, which fail to detect that occasionally? If an extensive approach is the only viable option, then it's clear that this and many other features are simply not suitable for Postgres Planner. It's disheartening that this patch didn't elicit such high-level feedback. -- regards, Andrei Lepikhov
On Mon, May 6, 2024 at 12:01 PM Andrei Lepikhov <a.lepikhov@postgrespro.ru> wrote: > Right now, it evolves extensively - new structures, variables, > alternative copies of the same node trees with slightly changed > properties ... This way allows us to quickly introduce some planning > features (a lot of changes in planner logic since PG16 is evidence of > that) and with still growing computing resources it allows postgres to > fit RAM and proper planning time. But maybe we want to be more modest? > The Ashutosh's work he has been doing this year shows how sometimes > expensive the planner is. Perhaps we want machinery that will check the > integrity of planning data except the setrefs, which fail to detect that > occasionally? > If an extensive approach is the only viable option, then it's clear that > this and many other features are simply not suitable for Postgres > Planner. It's disheartening that this patch didn't elicit such > high-level feedback. Well, as I said before, I think self-join elimination is a good feature, and I believe that it belongs in PostgreSQL. However, I don't believe that this implementation was done as well as it needed to be done. A great deal of the work involved in a feature like this lies in figuring out at what stage of processing certain kinds of transformations ought to be done, and what cleanup is needed afterward. It is difficult for anyone to get that completely right the first time around; left join elimination also provoked a series of after-the-fact bug fixes. However, I think those were fewer in number and spread over a longer period of time. Now that being said, I do also agree that the planner code is quite hard to understand, for various reasons. I don't think the structure of that code and the assumptions underlying it are as well-documented as they could be, and neither do I think that all of them are optimal. It has taken me a long time to learn as much as I know, and there is still quite a lot that I don't know. And I also agree that the planner does an unfortunate amount of in-place modification of existing structures without a lot of clarity about how it all works, and an unfortunate amount of data copying in some places, and even that the partition-wise join code isn't all that it could be. But I do not think that adds up to a conclusion that we should just be less ambitious with planner changes. Indeed, I would like to see us do more. There is certainly a lot of useful work that could be done. The trick is figuring out how to do it without breaking too many things, and that is not easy. -- Robert Haas EDB: http://www.enterprisedb.com
On Mon, May 6, 2024 at 12:24:41PM -0400, Robert Haas wrote:
> Now that being said, I do also agree that the planner code is quite
> hard to understand, for various reasons. I don't think the structure
> of that code and the assumptions underlying it are as well-documented
> as they could be, and neither do I think that all of them are optimal.
> It has taken me a long time to learn as much as I know, and there is
> still quite a lot that I don't know. And I also agree that the planner
> does an unfortunate amount of in-place modification of existing
> structures without a lot of clarity about how it all works, and an
> unfortunate amount of data copying in some places, and even that the
> partition-wise join code isn't all that it could be. But I do not
> think that adds up to a conclusion that we should just be less
> ambitious with planner changes. Indeed, I would like to see us do
> more. There is certainly a lot of useful work that could be done. The
> trick is figuring out how to do it without breaking too many things,
> and that is not easy.
I agree with Robert. While writting the Postgres 17 release notes, I am
excited to see the many optimizer improvements, and removing self-joins
from that list will be unfortunate.
I did write a blog entry in 2021 that suggested we could have
optimizer aggressiveness control to allow for more expensive
optimizations:
https://momjian.us/main/blogs/pgblog/2021.html#May_14_2021
--
Bruce Momjian <bruce@momjian.us> https://momjian.us
EDB https://enterprisedb.com
Only you can decide what is important to you.
On Mon, May 6, 2024 at 6:54 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > Robert Haas <robertmhaas@gmail.com> writes: > > I want to go on record right now as disagreeing with the plan proposed > > in the commit message for the revert commit, namely, committing this > > again early in the v18 cycle. I don't think Tom would have proposed > > reverting this feature unless he believed that it had more serious > > problems than could be easily fixed in a short period of time. I think > > that concern is well-founded, given the number of fixes that were > > committed. It seems likely that the patch needs significant rework and > > stabilization before it gets committed again, and I think it shouldn't > > be committed again without explicit agreement from Tom or one of the > > other committers who have significant experience with the query > > planner. > > FWIW I accept some of the blame here, for not having paid any > attention to the SJE work earlier. I had other things on my mind > for most of last year, and not enough bandwidth to help. > > The main thing I'd like to understand before we try this again is > why SJE needed so much new query-tree-manipulation infrastructure. > I would have expected it to be very similar to the left-join > elimination we do already, and therefore to mostly just share the > existing infrastructure. (I also harbor suspicions that some of > the new code existed just because someone didn't research what > was already there --- for instance, the now-removed replace_varno > sure looks like ChangeVarNodes should have been used instead.) Thank you for pointing this. This area certainly requires more investigation. > Another thing that made me pretty sad was 8c441c082 (Forbid SJE with > result relation). While I don't claim that that destroyed the entire > use case for SJE, it certainly knocked its usefulness down by many > notches, maybe even to the point where it's not worth putting in the > effort needed to get it to re-committability. So I think we need to > look harder at finding a way around that. Is the concern that > RETURNING should return either old or new values depending on which > RTE is mentioned? If so, maybe the feature Dean has proposed to > allow RETURNING to access old values [1] is a prerequisite to moving > forward. Alternatively, perhaps it'd be good enough to forbid SJE > only when the non-target relation is actually mentioned in RETURNING. Another problem is EPQ. During EPQ, we use most recent tuples for the target relation and snapshot-satisfying tuples for joined relations. And that affects RETURNING as well. If we need to return values for joined relation, that wouldn't be old values, but values of snapshot-satisfying tuple which might be even older. Proper support of this looks like quite amount of work for me. Committing SJE to v18 with this looks challenging. AFICS, going this way would require substantial help from you. ------ Regards, Alexander Korotkov Supabase
On Mon, May 6, 2024 at 5:44 PM Robert Haas <robertmhaas@gmail.com> wrote: > I want to go on record right now as disagreeing with the plan proposed > in the commit message for the revert commit, namely, committing this > again early in the v18 cycle. I don't think Tom would have proposed > reverting this feature unless he believed that it had more serious > problems than could be easily fixed in a short period of time. I think > that concern is well-founded, given the number of fixes that were > committed. It seems likely that the patch needs significant rework and > stabilization before it gets committed again, and I think it shouldn't > be committed again without explicit agreement from Tom or one of the > other committers who have significant experience with the query > planner. That is not to say that I don't approve generally of the idea > of committing things earlier in the release cycle: I certainly do. It > gives us more time to shake out problems with patches before we ship. > But it only makes sense if we collectively believe that the patch is > mostly correct, and only needs fine-tuning, and I think there are good > reasons to believe that we shouldn't have that level of confidence in > this case. I agree it was a hurry to put the plan into commit message. I think Tom already gave valuable feedback [1] and probably we will get more. So, plan is to be decided. One way or the other I'm not going to re-commit this without explicit Tom's consent. Links. 1. https://www.postgresql.org/message-id/3622801.1715010885%40sss.pgh.pa.us ------ Regards, Alexander Korotkov Supabase
On Mon, May 6, 2024 at 3:27 PM Alexander Korotkov <aekorotkov@gmail.com> wrote: > I agree it was a hurry to put the plan into commit message. I think > Tom already gave valuable feedback [1] and probably we will get more. > So, plan is to be decided. One way or the other I'm not going to > re-commit this without explicit Tom's consent. Thanks. I hope we find a way to make it happen. -- Robert Haas EDB: http://www.enterprisedb.com