Reducing duplicativeness of EquivalenceClass-derived clauses
While fooling with my longstanding outer-join variables changes
(I am making progress on that, honest), I happened to notice that
equivclass.c is leaving some money on the table by generating
redundant RestrictInfo clauses. It already attempts to not generate
the same clause twice, which can save a nontrivial amount of work
because we cache selectivity estimates and so on per-RestrictInfo.
I realized though that it will build and return a clause like
"a.x = b.y" even if it already has "b.y = a.x". This is just
wasteful. It's always been the case that equivclass.c will
produce clauses that are ordered according to its own whims.
Consumers that need the operands in a specific order, such as
index scans or hash joins, are required to commute the clause
to be the way they want it while building the finished plan.
Therefore, it shouldn't matter which order of the operands we
return, and giving back the commutator clause if available could
potentially save as much as half of the selectivity-estimation
work we do with these clauses subsequently.
Hence, PFA a patch that adjusts create_join_clause() to notice
commuted as well as exact matches among the EquivalenceClass's
existing clauses. This results in a number of changes visible in
regression test cases, but they're all clearly inconsequential.
The only thing that I think might be controversial here is that
I dropped the check for matching operator OID. To preserve that,
we'd have needed to use get_commutator() in the reverse-match cases,
which it seemed to me would be a completely unjustified expenditure
of cycles. The operators we select for freshly-generated clauses
will certainly always match those of previously-generated clauses.
Maybe there's a chance that they'd not match those of ec_sources
clauses (that is, the user-written clauses we started from), but
if they don't and that actually makes any difference then surely
we are talking about a buggy opclass definition.
I've not bothered to make any performance tests to see if there's
actually an easily measurable gain here. Saving some duplicative
selectivity estimates could be down in the noise ... but it's
surely worth the tiny number of extra tests added here.
Comments?
regards, tom lane
Attachments:
On Wed, Oct 26, 2022 at 6:09 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
While fooling with my longstanding outer-join variables changes
(I am making progress on that, honest), I happened to notice that
equivclass.c is leaving some money on the table by generating
redundant RestrictInfo clauses. It already attempts to not generate
the same clause twice, which can save a nontrivial amount of work
because we cache selectivity estimates and so on per-RestrictInfo.
I realized though that it will build and return a clause like
"a.x = b.y" even if it already has "b.y = a.x". This is just
wasteful. It's always been the case that equivclass.c will
produce clauses that are ordered according to its own whims.
Consumers that need the operands in a specific order, such as
index scans or hash joins, are required to commute the clause
to be the way they want it while building the finished plan.
Therefore, it shouldn't matter which order of the operands we
return, and giving back the commutator clause if available could
potentially save as much as half of the selectivity-estimation
work we do with these clauses subsequently.Hence, PFA a patch that adjusts create_join_clause() to notice
commuted as well as exact matches among the EquivalenceClass's
existing clauses. This results in a number of changes visible in
regression test cases, but they're all clearly inconsequential.
I think there is no problem with this idea, given the operands of
EC-derived clauses are commutative, and it seems no one would actually
rely on the order of the operands. I can see hashjoin/mergejoin would
commute hash/merge joinclauses if needed with get_switched_clauses().
The only thing that I think might be controversial here is that
I dropped the check for matching operator OID. To preserve that,
we'd have needed to use get_commutator() in the reverse-match cases,
which it seemed to me would be a completely unjustified expenditure
of cycles. The operators we select for freshly-generated clauses
will certainly always match those of previously-generated clauses.
Maybe there's a chance that they'd not match those of ec_sources
clauses (that is, the user-written clauses we started from), but
if they don't and that actually makes any difference then surely
we are talking about a buggy opclass definition.
The operator is chosen according to the two given EC members's data
type. Since we are dealing with the same pair of EC members, I think
the operator is always the same one. So it also seems no problem to drop
the check for operator. I wonder if we can even add an assertion if
we've found a RestrictInfo from ec_derives that the operator matches.
Thanks
Richard
Richard Guo <guofenglinux@gmail.com> writes:
On Wed, Oct 26, 2022 at 6:09 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
The only thing that I think might be controversial here is that
I dropped the check for matching operator OID. To preserve that,
we'd have needed to use get_commutator() in the reverse-match cases,
which it seemed to me would be a completely unjustified expenditure
of cycles. The operators we select for freshly-generated clauses
will certainly always match those of previously-generated clauses.
Maybe there's a chance that they'd not match those of ec_sources
clauses (that is, the user-written clauses we started from), but
if they don't and that actually makes any difference then surely
we are talking about a buggy opclass definition.
The operator is chosen according to the two given EC members's data
type. Since we are dealing with the same pair of EC members, I think
the operator is always the same one. So it also seems no problem to drop
the check for operator. I wonder if we can even add an assertion if
we've found a RestrictInfo from ec_derives that the operator matches.
Yeah, I considered that --- even if somehow an ec_sources entry isn't
an exact match, ec_derives ought to be. However, it still didn't seem
worth a get_commutator() call. We'd basically be expending cycles to
check that select_equality_operator yields the same result with the same
inputs as it did before, and that doesn't seem terribly interesting to
check. I'm also not sure what's the point of allowing divergence
from the requested operator in some but not all paths.
I added a bit of instrumentation to count how many times we need to build
new join clauses in create_join_clause. In the current core regression
tests, I see this change reducing the number of new join clauses built
here from 9673 to 5142 (out of 26652 calls). So not quite 50% savings,
but pretty close to it. That should mean that this change is about
a wash just in terms of the code it touches directly: each iteration
of the search loops is nearly twice as expensive as before, but we'll
only need to do about half as many. So whatever we save downstream
is pure gravy.
regards, tom lane
HI,
On Oct 26, 2022, 06:09 +0800, Tom Lane <tgl@sss.pgh.pa.us>, wrote:
While fooling with my longstanding outer-join variables changes
(I am making progress on that, honest), I happened to notice that
equivclass.c is leaving some money on the table by generating
redundant RestrictInfo clauses. It already attempts to not generate
the same clause twice, which can save a nontrivial amount of work
because we cache selectivity estimates and so on per-RestrictInfo.
I realized though that it will build and return a clause like
"a.x = b.y" even if it already has "b.y = a.x". This is just
wasteful. It's always been the case that equivclass.c will
produce clauses that are ordered according to its own whims.
Consumers that need the operands in a specific order, such as
index scans or hash joins, are required to commute the clause
to be the way they want it while building the finished plan.
Therefore, it shouldn't matter which order of the operands we
return, and giving back the commutator clause if available could
potentially save as much as half of the selectivity-estimation
work we do with these clauses subsequently.Hence, PFA a patch that adjusts create_join_clause() to notice
commuted as well as exact matches among the EquivalenceClass's
existing clauses. This results in a number of changes visible in
regression test cases, but they're all clearly inconsequential.The only thing that I think might be controversial here is that
I dropped the check for matching operator OID. To preserve that,
we'd have needed to use get_commutator() in the reverse-match cases,
which it seemed to me would be a completely unjustified expenditure
of cycles. The operators we select for freshly-generated clauses
will certainly always match those of previously-generated clauses.
Maybe there's a chance that they'd not match those of ec_sources
clauses (that is, the user-written clauses we started from), but
if they don't and that actually makes any difference then surely
we are talking about a buggy opclass definition.I've not bothered to make any performance tests to see if there's
actually an easily measurable gain here. Saving some duplicative
selectivity estimates could be down in the noise ... but it's
surely worth the tiny number of extra tests added here.Comments?
regards, tom lane
Make sense.
How about combine ec->ec_sources and ec->derives as one list for less codes?
```
foreach(lc, list_union(ec->ec_sources, ec->ec_derives))
{
rinfo = (RestrictInfo *) lfirst(lc);
if (rinfo->left_em == leftem &&
rinfo->right_em == rightem &&
rinfo->parent_ec == parent_ec)
return rinfo;
if (rinfo->left_em == rightem &&
rinfo->right_em == leftem &&
rinfo->parent_ec == parent_ec)
return rinfo;
}
```
I have a try, it will change some in join.out and avoid changes in tidscan.out.
Regards,
Zhang Mingli
Show quoted text
Zhang Mingli <zmlpostgres@gmail.com> writes:
How about combine ec->ec_sources and ec->derives as one list for less codes?
Keeping them separate is required for the broken-EC code paths.
Even if it weren't, I wouldn't merge them just to save a couple
of lines of code --- I think it's useful to be able to tell which
clauses the EC started from.
regards, tom lane
Hi,
On Oct 27, 2022, 21:29 +0800, Tom Lane <tgl@sss.pgh.pa.us>, wrote:
Zhang Mingli <zmlpostgres@gmail.com> writes:
How about combine ec->ec_sources and ec->derives as one list for less codes?
Keeping them separate is required for the broken-EC code paths.
Even if it weren't, I wouldn't merge them just to save a couple
of lines of code --- I think it's useful to be able to tell which
clauses the EC started from.regards, tom lane
Got it, thanks.
Regards,
Zhang Mingli