public inbox for [email protected]
help / color / mirror / Atom feed[PATCH 1/3] bootstrap: convert Typ to a List*
5+ messages / 3 participants
[nested] [flat]
* [PATCH 1/3] bootstrap: convert Typ to a List*
@ 2020-11-20 02:48 Justin Pryzby <[email protected]>
0 siblings, 0 replies; 5+ messages in thread
From: Justin Pryzby @ 2020-11-20 02:48 UTC (permalink / raw)
---
src/backend/bootstrap/bootstrap.c | 69 ++++++++++++++-----------------
1 file changed, 31 insertions(+), 38 deletions(-)
diff --git a/src/backend/bootstrap/bootstrap.c b/src/backend/bootstrap/bootstrap.c
index 6f615e6622..18eb62ca47 100644
--- a/src/backend/bootstrap/bootstrap.c
+++ b/src/backend/bootstrap/bootstrap.c
@@ -159,7 +159,7 @@ struct typmap
FormData_pg_type am_typ;
};
-static struct typmap **Typ = NULL;
+static List *Typ = NIL; /* List of struct typmap* */
static struct typmap *Ap = NULL;
static Datum values[MAXATTR]; /* current row's attribute values */
@@ -597,7 +597,7 @@ boot_openrel(char *relname)
* pg_type must be filled before any OPEN command is executed, hence we
* can now populate the Typ array if we haven't yet.
*/
- if (Typ == NULL)
+ if (Typ == NIL)
populate_typ_array();
if (boot_reldesc != NULL)
@@ -688,7 +688,7 @@ DefineAttr(char *name, char *type, int attnum, int nullness)
typeoid = gettype(type);
- if (Typ != NULL)
+ if (Typ != NIL)
{
attrtypes[attnum]->atttypid = Ap->am_oid;
attrtypes[attnum]->attlen = Ap->am_typ.typlen;
@@ -877,36 +877,25 @@ populate_typ_array(void)
Relation rel;
TableScanDesc scan;
HeapTuple tup;
- int nalloc;
- int i;
-
- Assert(Typ == NULL);
- nalloc = 512;
- Typ = (struct typmap **)
- MemoryContextAlloc(TopMemoryContext, nalloc * sizeof(struct typmap *));
+ Assert(Typ == NIL);
rel = table_open(TypeRelationId, NoLock);
scan = table_beginscan_catalog(rel, 0, NULL);
- i = 0;
while ((tup = heap_getnext(scan, ForwardScanDirection)) != NULL)
{
Form_pg_type typForm = (Form_pg_type) GETSTRUCT(tup);
+ struct typmap *newtyp;
+ MemoryContext old;
- /* make sure there will be room for a trailing NULL pointer */
- if (i >= nalloc - 1)
- {
- nalloc *= 2;
- Typ = (struct typmap **)
- repalloc(Typ, nalloc * sizeof(struct typmap *));
- }
- Typ[i] = (struct typmap *)
- MemoryContextAlloc(TopMemoryContext, sizeof(struct typmap));
- Typ[i]->am_oid = typForm->oid;
- memcpy(&(Typ[i]->am_typ), typForm, sizeof(Typ[i]->am_typ));
- i++;
+ old = MemoryContextSwitchTo(TopMemoryContext);
+ newtyp = (struct typmap *) palloc(sizeof(struct typmap));
+ Typ = lappend(Typ, newtyp);
+ MemoryContextSwitchTo(old);
+
+ newtyp->am_oid = typForm->oid;
+ memcpy(&newtyp->am_typ, typForm, sizeof(newtyp->am_typ));
}
- Typ[i] = NULL; /* Fill trailing NULL pointer */
table_endscan(scan);
table_close(rel, NoLock);
}
@@ -925,16 +914,17 @@ populate_typ_array(void)
static Oid
gettype(char *type)
{
- if (Typ != NULL)
+ if (Typ != NIL)
{
- struct typmap **app;
+ ListCell *lc;
- for (app = Typ; *app != NULL; app++)
+ foreach (lc, Typ)
{
- if (strncmp(NameStr((*app)->am_typ.typname), type, NAMEDATALEN) == 0)
+ struct typmap *app = lfirst(lc);
+ if (strncmp(NameStr(app->am_typ.typname), type, NAMEDATALEN) == 0)
{
- Ap = *app;
- return (*app)->am_oid;
+ Ap = app;
+ return app->am_oid;
}
}
}
@@ -980,14 +970,17 @@ boot_get_type_io_data(Oid typid,
if (Typ != NULL)
{
/* We have the boot-time contents of pg_type, so use it */
- struct typmap **app;
- struct typmap *ap;
-
- app = Typ;
- while (*app && (*app)->am_oid != typid)
- ++app;
- ap = *app;
- if (ap == NULL)
+ struct typmap *ap = NULL;
+ ListCell *lc;
+
+ foreach (lc, Typ)
+ {
+ ap = lfirst(lc);
+ if (ap->am_oid == typid)
+ break;
+ }
+
+ if (!ap || ap->am_oid != typid)
elog(ERROR, "type OID %u not found in Typ list", typid);
*typlen = ap->am_typ.typlen;
--
2.26.2
--------------8FD28E9B65A94BB176003065
Content-Type: text/x-patch; charset=UTF-8;
name="0002-Allow-composite-types-in-bootstrap-20210116.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0002-Allow-composite-types-in-bootstrap-20210116.patch"
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: [PoC] Reducing planning time when tables have many partitions
@ 2024-12-12 12:09 Alvaro Herrera <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Alvaro Herrera @ 2024-12-12 12:09 UTC (permalink / raw)
To: Yuya Watari <[email protected]>; +Cc: Ashutosh Bapat <[email protected]>; Dmitry Dolgov <[email protected]>; PostgreSQL Developers <[email protected]>; jian he <[email protected]>; Alena Rybakina <[email protected]>; Andrei Lepikhov <[email protected]>; David Rowley <[email protected]>; Thom Brown <[email protected]>; Zhang Mingli <[email protected]>; Tom Lane <[email protected]>
Hello Yuya,
On 2024-Dec-11, Yuya Watari wrote:
> On Tue, Dec 3, 2024 at 7:38 PM Alvaro Herrera <[email protected]> wrote:
> >
> > I don't think planning time in assert-enabled builds is something we
> > should worry about, at all. Planning time in production builds is the
> > important one.
>
> Thank you for your reply. Making debug builds too slow is not good for
> developers,
I'm repeating myself, but I disagree that this is something we should
spend _any_ time on. Developers running assertion-enabled builds do not
care if a complicated query with one thousand partitions is planned in
500 ms instead of 300 ms. Heck, I bet nobody cares if it took 2000 ms
either, because, you know what? The developers don't have a thousand
partitions to begin with; if they do, it's precisely because they want
to measure this kind of effect. This is not going to bother anyone
ever, unless you stick a hundred of these queries in the regression
tests. In regression tests you're going to have, say, 64 partitions at
most, because having more than that doesn't test anything additional;
having that go from 40 ms to 60 ms (or whatever) isn't going to bother
anyone.
If anything, you can add a note to remove the USE_ASSERTIONS blocks once
we get past the beta process; by then any bugs will have been noticed
and the asserts will be of less value.
I would like to see this patch series get committed, and this concern
about planning time in development builds under conditions that are
unrealistic for testing is slowing the process down. (The process is
slow enough. This patch has already missed two releases.) Please stop.
Memory usage and planning time in production builds is important. You
can better spend your energy there.
Thanks
--
Álvaro Herrera 48°01'N 7°57'E — https://www.EnterpriseDB.com/
"La gente vulgar sólo piensa en pasar el tiempo;
el que tiene talento, en aprovecharlo"
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: [PoC] Reducing planning time when tables have many partitions
@ 2024-12-13 08:44 Yuya Watari <[email protected]>
parent: Alvaro Herrera <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Yuya Watari @ 2024-12-13 08:44 UTC (permalink / raw)
To: Alvaro Herrera <[email protected]>; +Cc: Ashutosh Bapat <[email protected]>; Dmitry Dolgov <[email protected]>; PostgreSQL Developers <[email protected]>; jian he <[email protected]>; Alena Rybakina <[email protected]>; Andrei Lepikhov <[email protected]>; David Rowley <[email protected]>; Thom Brown <[email protected]>; Zhang Mingli <[email protected]>; Tom Lane <[email protected]>
Hello Alvaro,
Thank you for your reply, and I'm sorry if my previous emails caused
confusion or made it seem like I was ignoring more important issues.
On Thu, Dec 12, 2024 at 9:09 PM Alvaro Herrera <[email protected]> wrote:
>
> I'm repeating myself, but I disagree that this is something we should
> spend _any_ time on. Developers running assertion-enabled builds do not
> care if a complicated query with one thousand partitions is planned in
> 500 ms instead of 300 ms. Heck, I bet nobody cares if it took 2000 ms
> either, because, you know what? The developers don't have a thousand
> partitions to begin with; if they do, it's precisely because they want
> to measure this kind of effect. This is not going to bother anyone
> ever, unless you stick a hundred of these queries in the regression
> tests. In regression tests you're going to have, say, 64 partitions at
> most, because having more than that doesn't test anything additional;
> having that go from 40 ms to 60 ms (or whatever) isn't going to bother
> anyone.
I agree that focusing too much on assert-enabled builds is not
productive at this point. In my last email, I shared benchmark results
for debug builds, but I understand your point that even a few seconds
of regression is not practically important for debug builds.
For context, there have been reports in the past of minute-order
regressions in assert-enabled builds (100 seconds [1] and 50 seconds
[2]). I mentioned these minute-order regressions not to refocus the
discussion on debug builds right now, but to clarify why we have been
concerned about them in the past. I should have shared this background
and done appropriate benchmarks (not millisecond regressions, but
minutes). My sincere apologies. Once we have addressed the primary
goals (release build performance and memory usage), I will revisit
these regressions.
> If anything, you can add a note to remove the USE_ASSERTIONS blocks once
> we get past the beta process; by then any bugs will have been noticed
> and the asserts will be of less value.
Thank you for your advice. I will consider removing these assertions
after the beta process or using OPTIMIZER_DEBUG, which is Ashutosh's
idea.
> I would like to see this patch series get committed, and this concern
> about planning time in development builds under conditions that are
> unrealistic for testing is slowing the process down. (The process is
> slow enough. This patch has already missed two releases.) Please stop.
I will speed up the process for committing this patch series.
> Memory usage and planning time in production builds is important. You
> can better spend your energy there.
As you said, we have another big problem, which is memory usage. I
will focus on the memory usage problem first, as you suggested. After
fixing those problems, we can revisit the assert-enabled build
regressions as a final step if necessary. What do you think about this
approach?
[1] https://www.postgresql.org/message-id/d8db5b4e-e358-2567-8c56-a85d2d8013df%40postgrespro.ru
[2] https://www.postgresql.org/message-id/CAExHW5uVZ3E5RT9cXHaxQ_DEK7tasaMN%3DD6rPHcao5gcXanY5w%40mail.g...
--
Best regards,
Yuya Watari
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: [PoC] Reducing planning time when tables have many partitions
@ 2024-12-13 10:53 Alvaro Herrera <[email protected]>
parent: Yuya Watari <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Alvaro Herrera @ 2024-12-13 10:53 UTC (permalink / raw)
To: Yuya Watari <[email protected]>; +Cc: Ashutosh Bapat <[email protected]>; Dmitry Dolgov <[email protected]>; PostgreSQL Developers <[email protected]>; jian he <[email protected]>; Alena Rybakina <[email protected]>; Andrei Lepikhov <[email protected]>; David Rowley <[email protected]>; Thom Brown <[email protected]>; Zhang Mingli <[email protected]>; Tom Lane <[email protected]>
Hello,
On 2024-Dec-13, Yuya Watari wrote:
> Thank you for your reply, and I'm sorry if my previous emails caused
> confusion or made it seem like I was ignoring more important issues.
Not to worry!
> > Memory usage and planning time in production builds [are] important.
> > You can better spend your energy there.
>
> As you said, we have another big problem, which is memory usage. I
> will focus on the memory usage problem first, as you suggested.
That's great, thanks.
BTW I forgot to mention it yesterday, but I was surprised that you
attached Ashutosh's old patch for planner memory usage reporting.
This feature is already in EXPLAIN (MEMORY), so you don't need any patch
to measure memory consumption ... or does your patch add some detail
that isn't already in the code?
> After fixing those problems, we can revisit the assert-enabled build
> regressions as a final step if necessary. What do you think about this
> approach?
Sounds good.
--
Álvaro Herrera PostgreSQL Developer — https://www.EnterpriseDB.com/
"I can't go to a restaurant and order food because I keep looking at the
fonts on the menu. Five minutes later I realize that it's also talking
about food" (Donald Knuth)
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: [PoC] Reducing planning time when tables have many partitions
@ 2024-12-20 05:26 Yuya Watari <[email protected]>
parent: Alvaro Herrera <[email protected]>
0 siblings, 0 replies; 5+ messages in thread
From: Yuya Watari @ 2024-12-20 05:26 UTC (permalink / raw)
To: Alvaro Herrera <[email protected]>; +Cc: Ashutosh Bapat <[email protected]>; Dmitry Dolgov <[email protected]>; PostgreSQL Developers <[email protected]>; jian he <[email protected]>; Alena Rybakina <[email protected]>; Andrei Lepikhov <[email protected]>; David Rowley <[email protected]>; Thom Brown <[email protected]>; Zhang Mingli <[email protected]>; Tom Lane <[email protected]>
Hello Alvaro and all,
Thank you for the quick reply and I apologize for the delay in responding.
On Fri, Dec 13, 2024 at 7:53 PM Alvaro Herrera <[email protected]> wrote:
>
> BTW I forgot to mention it yesterday, but I was surprised that you
> attached Ashutosh's old patch for planner memory usage reporting.
> This feature is already in EXPLAIN (MEMORY), so you don't need any patch
> to measure memory consumption ... or does your patch add some detail
> that isn't already in the code?
Thank you for pointing this out. I did not add anything beyond the
rebase. I apologize for not noticing this. I have now re-run the same
experiments as in [1] using EXPLAIN (MEMORY).
> > As you said, we have another big problem, which is memory usage. I
> > will focus on the memory usage problem first, as you suggested.
>
> That's great, thanks.
In v29-0008, which is attached to this email, I introduced a new
approach to reduce memory usage during planning. Patch 0002 added
Bitmapset indexes over RestrictInfos. Previously, when retrieving
RestrictInfos, we had to perform intersections or unions of these
Bitmapset indexes, resulting in frequent allocations and copies of
temporary Bitmapsets. This was a significant source of memory
consumption.
The v29-0008 patch adds an iterator mechanism that emulates
bms_next_member(), bms_intersect() and bms_union() operations without
allocating additional Bitmapsets. Instead of constructing new
temporary Bitmapsets for each operation, the iterator performs these
operations on the fly. This approach eliminates the need for temporary
Bitmapsets and reduces memory usage.
I have attached updated experimental results below (tables and figure)
showing the effect of this iterator mechanism on memory usage and
planning time. In summary, the main results are as follows:
* Memory Usage: The v29-0008 change significantly reduces memory
consumption, especially in query B (44.4% reduction).
* Planning Time: While we still see a significant overall improvement
in planning time compared to master, there is some regression observed
in cases with a very large number of tables compared to v28. Notably,
this regression does not occur in smaller size cases such as
'installcheck'.
Table 1: Memory usage (MB)
(n: the number of partitions of each table; PWJ: partition-wise join)
-----------------------------------------------------
Query | n | PWJ | Master | v28 | v29
-----------------------------------------------------
A | 1024 | OFF | 47.818 | 69.000 | 59.156
A | 1024 | ON | 119.969 | 141.150 | 131.307
B | 256 | OFF | 89.429 | 196.217 | 109.088
B | 256 | ON | 4945.597 | 5052.386 | 4965.257
-----------------------------------------------------
---------------------------------------------------------------
Query | n | PWJ | v28 - v29 | 1 - v29 / v28 | v29 - Master
---------------------------------------------------------------
A | 1024 | OFF | 9.844 | 14.3% | 11.338
A | 1024 | ON | 9.844 | 7.0% | 11.338
B | 256 | OFF | 87.129 | 44.4% | 19.659
B | 256 | ON | 87.129 | 1.7% | 19.660
---------------------------------------------------------------
Table 2: Total planning time for installcheck (seconds)
------------------------------------------
Version | Mean | Median | Stddev
------------------------------------------
Master | 0.898575 | 0.897965 | 0.005739
v28 | 0.909598 | 0.906713 | 0.010797
v29 | 0.907552 | 0.906640 | 0.008023
------------------------------------------
Table 3: Speedup for installcheck (higher is better)
--------------------------
Version | Mean | Median
--------------------------
v28 | 98.8% | 99.0%
v29 | 99.0% | 99.0%
--------------------------
Table 4: Planning time for query A (ms)
----------------------------------
n | Master | v28 | v29
----------------------------------
1 | 0.243 | 0.247 | 0.246
2 | 0.263 | 0.269 | 0.269
4 | 0.327 | 0.349 | 0.338
8 | 0.433 | 0.435 | 0.438
16 | 0.617 | 0.615 | 0.608
32 | 1.061 | 1.000 | 0.982
64 | 2.083 | 1.955 | 1.938
128 | 5.774 | 4.225 | 4.209
256 | 17.521 | 10.446 | 10.682
384 | 32.913 | 16.196 | 16.669
512 | 57.379 | 22.274 | 23.392
640 | 92.402 | 28.751 | 30.526
768 | 148.043 | 34.923 | 38.501
896 | 257.313 | 50.124 | 54.165
1024 | 335.586 | 49.742 | 56.389
----------------------------------
Table 5: Speedup of query A (higher is better)
------------------------
n | v28 | v29
------------------------
1 | 98.3% | 98.9%
2 | 98.0% | 98.0%
4 | 93.6% | 96.6%
8 | 99.5% | 98.9%
16 | 100.3% | 101.4%
32 | 106.2% | 108.0%
64 | 106.6% | 107.5%
128 | 136.7% | 137.2%
256 | 167.7% | 164.0%
384 | 203.2% | 197.5%
512 | 257.6% | 245.3%
640 | 321.4% | 302.7%
768 | 423.9% | 384.5%
896 | 513.3% | 475.1%
1024 | 674.6% | 595.1%
------------------------
Table 6: Planning time for query B (ms)
-----------------------------------
n | Master | v28 | v29
-----------------------------------
1 | 11.675 | 11.755 | 11.651
2 | 11.210 | 11.282 | 11.169
4 | 11.745 | 11.677 | 11.556
8 | 12.896 | 12.545 | 12.324
16 | 15.455 | 14.112 | 14.024
32 | 21.642 | 17.531 | 17.585
64 | 44.220 | 26.481 | 26.910
128 | 129.947 | 47.559 | 51.107
256 | 772.431 | 105.115 | 131.829
-----------------------------------
Table 7: Speedup of query B (higher is better)
-----------------------
n | v28 | v29
-----------------------
1 | 99.3% | 100.2%
2 | 99.4% | 100.4%
4 | 100.6% | 101.6%
8 | 102.8% | 104.6%
16 | 109.5% | 110.2%
32 | 123.5% | 123.1%
64 | 167.0% | 164.3%
128 | 273.2% | 254.3%
256 | 734.8% | 585.9%
-----------------------
As shown in the above tables and the attached figure, the iterator
mechanism reduces memory usage (especially for query B, where we
observed a 44.4% reduction). Partition-wise join has no impact on
memory usage in either query A or B.
For planning time, v29 maintains the improvements seen in previous
versions, although there is some regression at large sizes (for
example, about 25.4% slower or 26.7ms more in query B with 256
partitions). For small sizes (a few partitions in the queries A and B,
and 'installcheck'), there is not much difference in planning time
between v28 and v29.
Overall, v29 demonstrates a better balance between planning time and
memory usage. There may still be room for further optimization of the
iterator mechanism, but I believe this is a good step towards
addressing previous concerns. I would appreciate any feedback or
suggestions.
[1] https://www.postgresql.org/message-id/CAJ2pMkZMKwdjYRUGA0%3Dza4SUrgpBJ5_JDYuVeG%3DEsbv1dKSouQ%40mail...
--
Best regards,
Yuya Watari
Attachments:
[image/png] figure.png (243.9K, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/2-figure.png)
download | view image
[application/octet-stream] v29-0001-Speed-up-searches-for-child-EquivalenceMembers.patch (62.3K, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/3-v29-0001-Speed-up-searches-for-child-EquivalenceMembers.patch)
download | inline diff:
From 750d1d66aaef2afab645c45e2a8b52732ff3c149 Mon Sep 17 00:00:00 2001
From: Yuya Watari <[email protected]>
Date: Fri, 25 Aug 2023 10:43:36 +0900
Subject: [PATCH v29 1/8] Speed up searches for child EquivalenceMembers
Traditionally, child EquivalenceMembers were in the
EquivalenceClass->ec_members. When we wanted to find some child members
matching a request, we had to perform a linear search. This search
became heavy when tables had many partitions, leading to much planning
time.
After this commit, child EquivalenceMembers no longer exist in
ec_members. Instead, RelOptInfos have them. This change demonstrates a
significant performance improvement in planning time.
---
contrib/postgres_fdw/postgres_fdw.c | 36 +-
src/backend/optimizer/path/equivclass.c | 464 ++++++++++++++++++++----
src/backend/optimizer/path/indxpath.c | 47 ++-
src/backend/optimizer/path/pathkeys.c | 9 +-
src/backend/optimizer/plan/createplan.c | 61 ++--
src/backend/optimizer/util/inherit.c | 14 +
src/backend/optimizer/util/relnode.c | 89 +++++
src/include/nodes/pathnodes.h | 61 ++++
src/include/optimizer/pathnode.h | 18 +
src/include/optimizer/paths.h | 12 +-
src/tools/pgindent/typedefs.list | 1 +
11 files changed, 698 insertions(+), 114 deletions(-)
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index c0810fbd7c8..e68c116164c 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7828,13 +7828,35 @@ conversion_error_callback(void *arg)
EquivalenceMember *
find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
{
- ListCell *lc;
-
PgFdwRelationInfo *fpinfo = (PgFdwRelationInfo *) rel->fdw_private;
+ Relids top_parent_rel_relids;
+ EquivalenceChildMemberIterator it;
+ EquivalenceMember *em;
+
+ /*
+ * First, we translate the given Relids to their top-level parents. This
+ * is required because an EquivalenceClass contains only parent
+ * EquivalenceMembers, and we have to translate top-level ones to get
+ * child members. We can skip such translations if we now see top-level
+ * ones, i.e., when top_parent_rel is NULL. See the
+ * find_relids_top_parents()'s definition for more details.
+ */
+ top_parent_rel_relids = find_relids_top_parents(root, rel->relids);
- foreach(lc, ec->ec_members)
+ /*
+ * If we need to see child EquivalenceMembers, we access them via
+ * EquivalenceChildMemberIterator during the iteration.
+ */
+ setup_eclass_child_member_iterator(&it, ec);
+ while ((em = eclass_child_member_iterator_next(&it)))
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ /*
+ * If child EquivalenceMembers may match the request, we add and
+ * iterate over them by calling iterate_child_rel_equivalences().
+ */
+ if (unlikely(top_parent_rel_relids != NULL) && !em->em_is_child &&
+ bms_is_subset(em->em_relids, top_parent_rel_relids))
+ iterate_child_rel_equivalences(&it, root, ec, em, rel->relids);
/*
* Note we require !bms_is_empty, else we'd accept constant
@@ -7846,6 +7868,7 @@ find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
is_foreign_expr(root, rel, em->em_expr))
return em;
}
+ dispose_eclass_child_member_iterator(&it);
return NULL;
}
@@ -7899,9 +7922,8 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
if (em->em_is_const)
continue;
- /* Ignore child members */
- if (em->em_is_child)
- continue;
+ /* Child members should not exist in ec_members */
+ Assert(!em->em_is_child);
/* Match if same expression (after stripping relabel) */
em_expr = em->em_expr;
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index fae137dd825..25ce4dd2242 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -33,10 +33,14 @@
#include "utils/lsyscache.h"
+static EquivalenceMember *make_eq_member(EquivalenceClass *ec,
+ Expr *expr, Relids relids,
+ JoinDomain *jdomain,
+ EquivalenceMember *parent,
+ Oid datatype);
static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
Expr *expr, Relids relids,
JoinDomain *jdomain,
- EquivalenceMember *parent,
Oid datatype);
static void generate_base_implied_equalities_const(PlannerInfo *root,
EquivalenceClass *ec);
@@ -68,6 +72,11 @@ static bool reconsider_outer_join_clause(PlannerInfo *root,
static bool reconsider_full_join_clause(PlannerInfo *root,
OuterJoinClauseInfo *ojcinfo);
static JoinDomain *find_join_domain(PlannerInfo *root, Relids relids);
+static void add_transformed_child_version(EquivalenceChildMemberIterator *it,
+ PlannerInfo *root,
+ EquivalenceClass *ec,
+ EquivalenceMember *parent_em,
+ RelOptInfo *child_rel);
static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root,
Relids relids);
static Bitmapset *get_common_eclass_indexes(PlannerInfo *root, Relids relids1,
@@ -373,7 +382,7 @@ process_equivalence(PlannerInfo *root,
{
/* Case 3: add item2 to ec1 */
em2 = add_eq_member(ec1, item2, item2_relids,
- jdomain, NULL, item2_type);
+ jdomain, item2_type);
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
@@ -390,7 +399,7 @@ process_equivalence(PlannerInfo *root,
{
/* Case 3: add item1 to ec2 */
em1 = add_eq_member(ec2, item1, item1_relids,
- jdomain, NULL, item1_type);
+ jdomain, item1_type);
ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
ec2->ec_min_security = Min(ec2->ec_min_security,
restrictinfo->security_level);
@@ -422,9 +431,9 @@ process_equivalence(PlannerInfo *root,
ec->ec_max_security = restrictinfo->security_level;
ec->ec_merged = NULL;
em1 = add_eq_member(ec, item1, item1_relids,
- jdomain, NULL, item1_type);
+ jdomain, item1_type);
em2 = add_eq_member(ec, item2, item2_relids,
- jdomain, NULL, item2_type);
+ jdomain, item2_type);
root->eq_classes = lappend(root->eq_classes, ec);
@@ -510,11 +519,16 @@ canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
}
/*
- * add_eq_member - build a new EquivalenceMember and add it to an EC
+ * make_eq_member
+ *
+ * Build a new EquivalenceMember without adding it to an EC. If 'parent'
+ * parameter is NULL, the result will be a parent member, otherwise a child
+ * member. Note that child EquivalenceMembers should not be added to its
+ * parent EquivalenceClass.
*/
static EquivalenceMember *
-add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
- JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
+make_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
+ JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
{
EquivalenceMember *em = makeNode(EquivalenceMember);
@@ -525,6 +539,8 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
em->em_datatype = datatype;
em->em_jdomain = jdomain;
em->em_parent = parent;
+ em->em_child_relids = NULL;
+ em->em_child_joinrel_relids = NULL;
if (bms_is_empty(relids))
{
@@ -545,11 +561,29 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
{
ec->ec_relids = bms_add_members(ec->ec_relids, relids);
}
- ec->ec_members = lappend(ec->ec_members, em);
return em;
}
+/*
+ * add_eq_member - build a new parent EquivalenceMember and add it to an EC
+ *
+ * Note: We don't have a function to add a child member like
+ * add_child_eq_member() because how to do it depends on the relations they are
+ * translated from. See add_child_rel_equivalences() and
+ * add_child_join_rel_equivalences() to see how to add child members.
+ */
+static EquivalenceMember *
+add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
+ JoinDomain *jdomain, Oid datatype)
+{
+ EquivalenceMember *em = make_eq_member(ec, expr, relids, jdomain,
+ NULL, datatype);
+
+ ec->ec_members = lappend(ec->ec_members, em);
+ return em;
+}
+
/*
* get_eclass_for_sort_expr
@@ -598,6 +632,17 @@ get_eclass_for_sort_expr(PlannerInfo *root,
EquivalenceMember *newem;
ListCell *lc1;
MemoryContext oldcontext;
+ Relids top_parent_rel;
+
+ /*
+ * First, we translate the given Relids to their top-level parents. This
+ * is required because an EquivalenceClass contains only parent
+ * EquivalenceMembers, and we have to translate top-level ones to get
+ * child members. We can skip such translations if we now see top-level
+ * ones, i.e., when top_parent_rel is NULL. See the
+ * find_relids_top_parents()'s definition for more details.
+ */
+ top_parent_rel = find_relids_top_parents(root, rel);
/*
* Ensure the expression exposes the correct type and collation.
@@ -616,7 +661,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
- ListCell *lc2;
+ EquivalenceChildMemberIterator it;
+ EquivalenceMember *cur_em;
/*
* Never match to a volatile EC, except when we are looking at another
@@ -631,16 +677,28 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
- foreach(lc2, cur_ec->ec_members)
+ /*
+ * If we need to see child EquivalenceMembers, we access them via
+ * EquivalenceChildMemberIterator during the iteration.
+ */
+ setup_eclass_child_member_iterator(&it, cur_ec);
+ while ((cur_em = eclass_child_member_iterator_next(&it)) != NULL)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+ /*
+ * If child EquivalenceMembers may match the request, we add and
+ * iterate over them by calling iterate_child_rel_equivalences().
+ */
+ if (unlikely(top_parent_rel != NULL) && !cur_em->em_is_child &&
+ bms_equal(cur_em->em_relids, top_parent_rel))
+ iterate_child_rel_equivalences(&it, root, cur_ec, cur_em, rel);
/*
- * Ignore child members unless they match the request.
+ * Ignore child members unless they match the request. If this
+ * EquivalenceMember is a child, i.e., translated above, it should
+ * match the request. We cannot assert this if a request is
+ * bms_is_subset().
*/
- if (cur_em->em_is_child &&
- !bms_equal(cur_em->em_relids, rel))
- continue;
+ Assert(!cur_em->em_is_child || bms_equal(cur_em->em_relids, rel));
/*
* Match constants only within the same JoinDomain (see
@@ -653,6 +711,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
equal(expr, cur_em->em_expr))
return cur_ec; /* Match! */
}
+ dispose_eclass_child_member_iterator(&it);
}
/* No match; does caller want a NULL result? */
@@ -690,7 +749,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
expr_relids = pull_varnos(root, (Node *) expr);
newem = add_eq_member(newec, copyObject(expr), expr_relids,
- jdomain, NULL, opcintype);
+ jdomain, opcintype);
/*
* add_eq_member doesn't check for volatile functions, set-returning
@@ -760,19 +819,35 @@ get_eclass_for_sort_expr(PlannerInfo *root,
* Child EC members are ignored unless they belong to given 'relids'.
*/
EquivalenceMember *
-find_ec_member_matching_expr(EquivalenceClass *ec,
+find_ec_member_matching_expr(PlannerInfo *root, EquivalenceClass *ec,
Expr *expr,
Relids relids)
{
- ListCell *lc;
+ Relids top_parent_relids;
+ EquivalenceChildMemberIterator it;
+ EquivalenceMember *em;
+
+ /*
+ * First, we translate the given Relids to their top-level parents. This
+ * is required because an EquivalenceClass contains only parent
+ * EquivalenceMembers, and we have to translate top-level ones to get
+ * child members. We can skip such translations if we now see top-level
+ * ones, i.e., when top_parent_rel is NULL. See the
+ * find_relids_top_parents()'s definition for more details.
+ */
+ top_parent_relids = find_relids_top_parents(root, relids);
/* We ignore binary-compatible relabeling on both ends */
while (expr && IsA(expr, RelabelType))
expr = ((RelabelType *) expr)->arg;
- foreach(lc, ec->ec_members)
+ /*
+ * If we need to see child EquivalenceMembers, we access them via
+ * EquivalenceChildMemberIterator during the iteration.
+ */
+ setup_eclass_child_member_iterator(&it, ec);
+ while ((em = eclass_child_member_iterator_next(&it)) != NULL)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
Expr *emexpr;
/*
@@ -782,6 +857,14 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
if (em->em_is_const)
continue;
+ /*
+ * If child EquivalenceMembers may match the request, we add and
+ * iterate over them by calling iterate_child_rel_equivalences().
+ */
+ if (unlikely(top_parent_relids != NULL) && !em->em_is_child &&
+ bms_is_subset(em->em_relids, top_parent_relids))
+ iterate_child_rel_equivalences(&it, root, ec, em, relids);
+
/*
* Ignore child members unless they belong to the requested rel.
*/
@@ -799,6 +882,7 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
if (equal(emexpr, expr))
return em;
}
+ dispose_eclass_child_member_iterator(&it);
return NULL;
}
@@ -841,7 +925,9 @@ find_computable_ec_member(PlannerInfo *root,
bool require_parallel_safe)
{
List *exprvars;
- ListCell *lc;
+ Relids top_parent_relids;
+ EquivalenceChildMemberIterator it;
+ EquivalenceMember *em;
/*
* Pull out the Vars and quasi-Vars present in "exprs". In the typical
@@ -854,9 +940,23 @@ find_computable_ec_member(PlannerInfo *root,
PVC_INCLUDE_WINDOWFUNCS |
PVC_INCLUDE_PLACEHOLDERS);
- foreach(lc, ec->ec_members)
+ /*
+ * First, we translate the given Relids to their top-level parents. This
+ * is required because an EquivalenceClass contains only parent
+ * EquivalenceMembers, and we have to translate top-level ones to get
+ * child members. We can skip such translations if we now see top-level
+ * ones, i.e., when top_parent_rel is NULL. See the
+ * find_relids_top_parents()'s definition for more details.
+ */
+ top_parent_relids = find_relids_top_parents(root, relids);
+
+ /*
+ * If we need to see child EquivalenceMembers, we access them via
+ * EquivalenceChildMemberIterator during the iteration.
+ */
+ setup_eclass_child_member_iterator(&it, ec);
+ while ((em = eclass_child_member_iterator_next(&it)) != NULL)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
List *emvars;
ListCell *lc2;
@@ -867,6 +967,14 @@ find_computable_ec_member(PlannerInfo *root,
if (em->em_is_const)
continue;
+ /*
+ * If child EquivalenceMembers may match the request, we add and
+ * iterate over them by calling iterate_child_rel_equivalences().
+ */
+ if (unlikely(top_parent_relids != NULL) && !em->em_is_child &&
+ bms_is_subset(em->em_relids, top_parent_relids))
+ iterate_child_rel_equivalences(&it, root, ec, em, relids);
+
/*
* Ignore child members unless they belong to the requested rel.
*/
@@ -900,6 +1008,7 @@ find_computable_ec_member(PlannerInfo *root,
return em; /* found usable expression */
}
+ dispose_eclass_child_member_iterator(&it);
return NULL;
}
@@ -938,7 +1047,7 @@ relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel,
{
Expr *targetexpr = (Expr *) lfirst(lc);
- em = find_ec_member_matching_expr(ec, targetexpr, rel->relids);
+ em = find_ec_member_matching_expr(root, ec, targetexpr, rel->relids);
if (!em)
continue;
@@ -1563,7 +1672,19 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
List *new_members = NIL;
List *outer_members = NIL;
List *inner_members = NIL;
- ListCell *lc1;
+ Relids top_parent_join_relids;
+ EquivalenceChildMemberIterator it;
+ EquivalenceMember *cur_em;
+
+ /*
+ * First, we translate the given Relids to their top-level parents. This
+ * is required because an EquivalenceClass contains only parent
+ * EquivalenceMembers, and we have to translate top-level ones to get
+ * child members. We can skip such translations if we now see top-level
+ * ones, i.e., when top_parent_rel is NULL. See the
+ * find_relids_top_parents()'s definition for more details.
+ */
+ top_parent_join_relids = find_relids_top_parents(root, join_relids);
/*
* First, scan the EC to identify member values that are computable at the
@@ -1573,10 +1694,20 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
* enforce that any newly computable members are all equal to each other
* as well as to at least one input member, plus enforce at least one
* outer-rel member equal to at least one inner-rel member.
+ *
+ * If we need to see child EquivalenceMembers, we access them via
+ * EquivalenceChildMemberIterator during the iteration.
*/
- foreach(lc1, ec->ec_members)
+ setup_eclass_child_member_iterator(&it, ec);
+ while ((cur_em = eclass_child_member_iterator_next(&it)) != NULL)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+ /*
+ * If child EquivalenceMembers may match the request, we add and
+ * iterate over them by calling iterate_child_rel_equivalences().
+ */
+ if (unlikely(top_parent_join_relids != NULL) && !cur_em->em_is_child &&
+ bms_is_subset(cur_em->em_relids, top_parent_join_relids))
+ iterate_child_rel_equivalences(&it, root, ec, cur_em, join_relids);
/*
* We don't need to check explicitly for child EC members. This test
@@ -1593,6 +1724,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
else
new_members = lappend(new_members, cur_em);
}
+ dispose_eclass_child_member_iterator(&it);
/*
* First, select the joinclause if needed. We can equate any one outer
@@ -1610,6 +1742,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
Oid best_eq_op = InvalidOid;
int best_score = -1;
RestrictInfo *rinfo;
+ ListCell *lc1;
foreach(lc1, outer_members)
{
@@ -1684,6 +1817,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
List *old_members = list_concat(outer_members, inner_members);
EquivalenceMember *prev_em = NULL;
RestrictInfo *rinfo;
+ ListCell *lc1;
/* For now, arbitrarily take the first old_member as the one to use */
if (old_members)
@@ -1691,7 +1825,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
foreach(lc1, new_members)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+ cur_em = (EquivalenceMember *) lfirst(lc1);
if (prev_em != NULL)
{
@@ -2404,6 +2538,7 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
if (matchleft && matchright)
{
cur_ec->ec_members = list_delete_nth_cell(cur_ec->ec_members, coal_idx);
+ Assert(!bms_is_empty(coal_em->em_relids));
return true;
}
@@ -2525,8 +2660,8 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2, Oid opfamily)
{
EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
- if (em->em_is_child)
- continue; /* ignore children here */
+ /* Child members should not exist in ec_members */
+ Assert(!em->em_is_child);
if (equal(item1, em->em_expr))
item1member = true;
else if (equal(item2, em->em_expr))
@@ -2597,8 +2732,8 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
Var *var;
- if (em->em_is_child)
- continue; /* ignore children here */
+ /* Child members should not exist in ec_members */
+ Assert(!em->em_is_child);
/* EM must be a Var, possibly with RelabelType */
var = (Var *) em->em_expr;
@@ -2695,6 +2830,7 @@ add_child_rel_equivalences(PlannerInfo *root,
Relids top_parent_relids = child_rel->top_parent_relids;
Relids child_relids = child_rel->relids;
int i;
+ ListCell *lc;
/*
* EC merging should be complete already, so we can use the parent rel's
@@ -2707,7 +2843,6 @@ add_child_rel_equivalences(PlannerInfo *root,
while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
- int num_members;
/*
* If this EC contains a volatile expression, then generating child
@@ -2720,15 +2855,9 @@ add_child_rel_equivalences(PlannerInfo *root,
/* Sanity check eclass_indexes only contain ECs for parent_rel */
Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
- /*
- * We don't use foreach() here because there's no point in scanning
- * newly-added child members, so we can stop after the last
- * pre-existing EC member.
- */
- num_members = list_length(cur_ec->ec_members);
- for (int pos = 0; pos < num_members; pos++)
+ foreach(lc, cur_ec->ec_members)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+ EquivalenceMember *cur_em = lfirst_node(EquivalenceMember, lc);
if (cur_em->em_is_const)
continue; /* ignore consts here */
@@ -2741,8 +2870,8 @@ add_child_rel_equivalences(PlannerInfo *root,
* combinations of children. (But add_child_join_rel_equivalences
* may add targeted combinations for partitionwise-join purposes.)
*/
- if (cur_em->em_is_child)
- continue; /* ignore children here */
+ /* Child members should not exist in ec_members */
+ Assert(!cur_em->em_is_child);
/*
* Consider only members that reference and can be computed at
@@ -2758,6 +2887,7 @@ add_child_rel_equivalences(PlannerInfo *root,
/* OK, generate transformed child version */
Expr *child_expr;
Relids new_relids;
+ EquivalenceMember *child_em;
if (parent_rel->reloptkind == RELOPT_BASEREL)
{
@@ -2787,9 +2917,20 @@ add_child_rel_equivalences(PlannerInfo *root,
top_parent_relids);
new_relids = bms_add_members(new_relids, child_relids);
- (void) add_eq_member(cur_ec, child_expr, new_relids,
- cur_em->em_jdomain,
- cur_em, cur_em->em_datatype);
+ child_em = make_eq_member(cur_ec, child_expr, new_relids,
+ cur_em->em_jdomain,
+ cur_em, cur_em->em_datatype);
+ child_rel->eclass_child_members = lappend(child_rel->eclass_child_members,
+ child_em);
+
+ /*
+ * We save the knowledge that 'child_em' can be translated
+ * using 'child_rel'. This knowledge is useful for
+ * add_transformed_child_version() to find child members from
+ * the given Relids.
+ */
+ cur_em->em_child_relids = bms_add_member(cur_em->em_child_relids,
+ child_rel->relid);
/* Record this EC index for the child rel */
child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
@@ -2818,6 +2959,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
Relids child_relids = child_joinrel->relids;
Bitmapset *matching_ecs;
MemoryContext oldcontext;
+ ListCell *lc;
int i;
Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
@@ -2839,7 +2981,6 @@ add_child_join_rel_equivalences(PlannerInfo *root,
while ((i = bms_next_member(matching_ecs, i)) >= 0)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
- int num_members;
/*
* If this EC contains a volatile expression, then generating child
@@ -2852,15 +2993,9 @@ add_child_join_rel_equivalences(PlannerInfo *root,
/* Sanity check on get_eclass_indexes_for_relids result */
Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
- /*
- * We don't use foreach() here because there's no point in scanning
- * newly-added child members, so we can stop after the last
- * pre-existing EC member.
- */
- num_members = list_length(cur_ec->ec_members);
- for (int pos = 0; pos < num_members; pos++)
+ foreach(lc, cur_ec->ec_members)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+ EquivalenceMember *cur_em = lfirst_node(EquivalenceMember, lc);
if (cur_em->em_is_const)
continue; /* ignore consts here */
@@ -2869,8 +3004,8 @@ add_child_join_rel_equivalences(PlannerInfo *root,
* We consider only original EC members here, not
* already-transformed child members.
*/
- if (cur_em->em_is_child)
- continue; /* ignore children here */
+ /* Child members should not exist in ec_members */
+ Assert(!cur_em->em_is_child);
/*
* We may ignore expressions that reference a single baserel,
@@ -2885,6 +3020,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
/* Yes, generate transformed child version */
Expr *child_expr;
Relids new_relids;
+ EquivalenceMember *child_em;
if (parent_joinrel->reloptkind == RELOPT_JOINREL)
{
@@ -2915,9 +3051,21 @@ add_child_join_rel_equivalences(PlannerInfo *root,
top_parent_relids);
new_relids = bms_add_members(new_relids, child_relids);
- (void) add_eq_member(cur_ec, child_expr, new_relids,
- cur_em->em_jdomain,
- cur_em, cur_em->em_datatype);
+ child_em = make_eq_member(cur_ec, child_expr, new_relids,
+ cur_em->em_jdomain,
+ cur_em, cur_em->em_datatype);
+ child_joinrel->eclass_child_members =
+ lappend(child_joinrel->eclass_child_members, child_em);
+
+ /*
+ * We save the knowledge that 'child_em' can be translated
+ * using 'child_joinrel'. This knowledge is useful for
+ * add_transformed_child_version() to find child members from
+ * the given Relids.
+ */
+ cur_em->em_child_joinrel_relids =
+ bms_add_member(cur_em->em_child_joinrel_relids,
+ child_joinrel->join_rel_list_index);
}
}
}
@@ -2986,6 +3134,161 @@ add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel,
list_length(root->eq_classes) - 1);
}
+/*
+ * setup_eclass_child_member_iterator
+ * Setup an EquivalenceChildMemberIterator 'it' so that it can iterate over
+ * EquivalenceMembers in 'ec'.
+ *
+ * Once used, the caller should dispose of the iterator by calling
+ * dispose_eclass_child_member_iterator().
+ */
+void
+setup_eclass_child_member_iterator(EquivalenceChildMemberIterator *it,
+ EquivalenceClass *ec)
+{
+ it->index = -1;
+ it->modified = false;
+ it->ec_members = ec->ec_members;
+}
+
+/*
+ * eclass_child_member_iterator_next
+ * Get a next EquivalenceMember from an EquivalenceChildMemberIterator 'it'
+ * that was setup by setup_eclass_child_member_iterator(). NULL is returned
+ * if there are no members left.
+ */
+EquivalenceMember *
+eclass_child_member_iterator_next(EquivalenceChildMemberIterator *it)
+{
+ if (++it->index < list_length(it->ec_members))
+ return list_nth_node(EquivalenceMember, it->ec_members, it->index);
+ return NULL;
+}
+
+/*
+ * dispose_eclass_child_member_iterator
+ * Free any memory allocated by the iterator.
+ */
+void
+dispose_eclass_child_member_iterator(EquivalenceChildMemberIterator *it)
+{
+ /*
+ * XXX Should we use list_free()? I decided to use this style to take
+ * advantage of speculative execution.
+ */
+ if (unlikely(it->modified))
+ pfree(it->ec_members);
+}
+
+/*
+ * add_transformed_child_version
+ * Add a transformed EquivalenceMember referencing the given child_rel to
+ * the iterator.
+ *
+ * This function is expected to be called only from
+ * iterate_child_rel_equivalences().
+ */
+static void
+add_transformed_child_version(EquivalenceChildMemberIterator *it,
+ PlannerInfo *root,
+ EquivalenceClass *ec,
+ EquivalenceMember *parent_em,
+ RelOptInfo *child_rel)
+{
+ ListCell *lc;
+
+ foreach(lc, child_rel->eclass_child_members)
+ {
+ EquivalenceMember *child_em = lfirst_node(EquivalenceMember, lc);
+
+ /* Skip unwanted EquivalenceMembers */
+ if (child_em->em_parent != parent_em)
+ continue;
+
+ /*
+ * If this is the first time the iterator's list has been modified, we
+ * need to make a copy of it.
+ */
+ if (!it->modified)
+ {
+ it->ec_members = list_copy(it->ec_members);
+ it->modified = true;
+ }
+
+ /* Add this child EquivalenceMember to the list */
+ it->ec_members = lappend(it->ec_members, child_em);
+ }
+}
+
+/*
+ * iterate_child_rel_equivalences
+ * Add transformed EquivalenceMembers referencing child rels in the given
+ * child_relids to the iterator.
+ *
+ * The transformation is done in add_transformed_child_version().
+ */
+void
+iterate_child_rel_equivalences(EquivalenceChildMemberIterator *it,
+ PlannerInfo *root,
+ EquivalenceClass *ec,
+ EquivalenceMember *parent_em,
+ Relids child_relids)
+{
+ int i;
+ Relids matching_relids;
+
+ /* The given EquivalenceMember should be parent */
+ Assert(!parent_em->em_is_child);
+
+ /*
+ * EquivalenceClass->ec_members has only parent EquivalenceMembers. Child
+ * members are translated using child RelOptInfos and stored in them. This
+ * is done in add_child_rel_equivalences() and
+ * add_child_join_rel_equivalences(). To retrieve child EquivalenceMembers
+ * of some parent, we need to know which RelOptInfos have such child
+ * members. This information is stored in indexes named em_child_relids
+ * and em_child_joinrel_relids.
+ *
+ * This function iterates over the child EquivalenceMembers that reference
+ * the given 'child_relids'. To do this, we first intersect 'child_relids'
+ * with these indexes. The result contains Relids of RelOptInfos that have
+ * child EquivalenceMembers we want to retrieve. Then we get the child
+ * members from the RelOptInfos using add_transformed_child_version().
+ *
+ * We need to do these steps for each of the two indexes.
+ */
+
+ /*
+ * First, we translate simple rels.
+ */
+ matching_relids = bms_intersect(parent_em->em_child_relids,
+ child_relids);
+ i = -1;
+ while ((i = bms_next_member(matching_relids, i)) >= 0)
+ {
+ /* Add transformed child version for this child rel */
+ RelOptInfo *child_rel = root->simple_rel_array[i];
+
+ Assert(child_rel != NULL);
+ add_transformed_child_version(it, root, ec, parent_em, child_rel);
+ }
+ bms_free(matching_relids);
+
+ /*
+ * Next, we try to translate join rels.
+ */
+ i = -1;
+ while ((i = bms_next_member(parent_em->em_child_joinrel_relids, i)) >= 0)
+ {
+ /* Add transformed child version for this child join rel */
+ RelOptInfo *child_joinrel =
+ list_nth_node(RelOptInfo, root->join_rel_list, i);
+
+ Assert(child_joinrel != NULL);
+ add_transformed_child_version(it, root, ec, parent_em, child_joinrel);
+ }
+}
+
/*
* generate_implied_equalities_for_column
@@ -3019,7 +3322,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
{
List *result = NIL;
bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
- Relids parent_relids;
+ Relids parent_relids,
+ top_parent_rel_relids;
int i;
/* Should be OK to rely on eclass_indexes */
@@ -3028,6 +3332,16 @@ generate_implied_equalities_for_column(PlannerInfo *root,
/* Indexes are available only on base or "other" member relations. */
Assert(IS_SIMPLE_REL(rel));
+ /*
+ * First, we translate the given Relids to their top-level parents. This
+ * is required because an EquivalenceClass contains only parent
+ * EquivalenceMembers, and we have to translate top-level ones to get
+ * child members. We can skip such translations if we now see top-level
+ * ones, i.e., when top_parent_rel is NULL. See the
+ * find_relids_top_parents()'s definition for more details.
+ */
+ top_parent_rel_relids = find_relids_top_parents(root, rel->relids);
+
/* If it's a child rel, we'll need to know what its parent(s) are */
if (is_child_rel)
parent_relids = find_childrel_parents(root, rel);
@@ -3040,6 +3354,7 @@ generate_implied_equalities_for_column(PlannerInfo *root,
EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
EquivalenceMember *cur_em;
ListCell *lc2;
+ EquivalenceChildMemberIterator it;
/* Sanity check eclass_indexes only contain ECs for rel */
Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
@@ -3060,16 +3375,25 @@ generate_implied_equalities_for_column(PlannerInfo *root,
* column gets matched to. This is annoying but it only happens in
* corner cases, so for now we live with just reporting the first
* match. See also get_eclass_for_sort_expr.)
+ *
+ * If we need to see child EquivalenceMembers, we access them via
+ * EquivalenceChildMemberIterator during the iteration.
*/
- cur_em = NULL;
- foreach(lc2, cur_ec->ec_members)
+ setup_eclass_child_member_iterator(&it, cur_ec);
+ while ((cur_em = eclass_child_member_iterator_next(&it)) != NULL)
{
- cur_em = (EquivalenceMember *) lfirst(lc2);
+ /*
+ * If child EquivalenceMembers may match the request, we add and
+ * iterate over them by calling iterate_child_rel_equivalences().
+ */
+ if (unlikely(top_parent_rel_relids != NULL) && !cur_em->em_is_child &&
+ bms_equal(cur_em->em_relids, top_parent_rel_relids))
+ iterate_child_rel_equivalences(&it, root, cur_ec, cur_em, rel->relids);
if (bms_equal(cur_em->em_relids, rel->relids) &&
callback(root, rel, cur_ec, cur_em, callback_arg))
break;
- cur_em = NULL;
}
+ dispose_eclass_child_member_iterator(&it);
if (!cur_em)
continue;
@@ -3084,8 +3408,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
Oid eq_op;
RestrictInfo *rinfo;
- if (other_em->em_is_child)
- continue; /* ignore children here */
+ /* Child members should not exist in ec_members */
+ Assert(!other_em->em_is_child);
/* Make sure it'll be a join to a different rel */
if (other_em == cur_em ||
@@ -3303,8 +3627,8 @@ eclass_useful_for_merging(PlannerInfo *root,
{
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
- if (cur_em->em_is_child)
- continue; /* ignore children here */
+ /* Child members should not exist in ec_members */
+ Assert(!cur_em->em_is_child);
if (!bms_overlap(cur_em->em_relids, relids))
return true;
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 5d102a0d371..4a42752486e 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -190,7 +190,7 @@ static IndexClause *expand_indexqual_rowcompare(PlannerInfo *root,
IndexOptInfo *index,
Oid expr_op,
bool var_on_left);
-static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
+static void match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
List **clause_columns_p);
static Expr *match_clause_to_ordering_op(IndexOptInfo *index,
@@ -934,7 +934,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
* query_pathkeys will allow an incremental sort to be considered on
* the index's partially sorted results.
*/
- match_pathkeys_to_index(index, root->query_pathkeys,
+ match_pathkeys_to_index(root, index, root->query_pathkeys,
&orderbyclauses,
&orderbyclausecols);
if (list_length(root->query_pathkeys) == list_length(orderbyclauses))
@@ -3726,12 +3726,23 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* item in the given 'pathkeys' list.
*/
static void
-match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
+match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
List **clause_columns_p)
{
+ Relids top_parent_index_relids;
ListCell *lc1;
+ /*
+ * First, we translate the given Relids to their top-level parents. This
+ * is required because an EquivalenceClass contains only parent
+ * EquivalenceMembers, and we have to translate top-level ones to get
+ * child members. We can skip such translations if we now see top-level
+ * ones, i.e., when top_parent_rel is NULL. See the
+ * find_relids_top_parents()'s definition for more details.
+ */
+ top_parent_index_relids = find_relids_top_parents(root, index->rel->relids);
+
*orderby_clauses_p = NIL; /* set default results */
*clause_columns_p = NIL;
@@ -3743,7 +3754,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
{
PathKey *pathkey = (PathKey *) lfirst(lc1);
bool found = false;
- ListCell *lc2;
+ EquivalenceChildMemberIterator it;
+ EquivalenceMember *member;
/* Pathkey must request default sort order for the target opfamily */
@@ -3762,16 +3774,36 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
* child member of more than one EC. Therefore, the same index could
* be considered to match more than one pathkey list, which is OK
* here. See also get_eclass_for_sort_expr.)
+ *
+ * If we need to see child EquivalenceMembers, we access them via
+ * EquivalenceChildMemberIterator during the iteration.
*/
- foreach(lc2, pathkey->pk_eclass->ec_members)
+ setup_eclass_child_member_iterator(&it, pathkey->pk_eclass);
+ while ((member = eclass_child_member_iterator_next(&it)))
{
- EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
int indexcol;
+ /*
+ * If child EquivalenceMembers may match the request, we add and
+ * iterate over them by calling iterate_child_rel_equivalences().
+ */
+ if (unlikely(top_parent_index_relids != NULL) && !member->em_is_child &&
+ bms_equal(member->em_relids, top_parent_index_relids))
+ iterate_child_rel_equivalences(&it, root, pathkey->pk_eclass, member,
+ index->rel->relids);
+
/* No possibility of match if it references other relations */
- if (!bms_equal(member->em_relids, index->rel->relids))
+ if (!member->em_is_child &&
+ !bms_equal(member->em_relids, index->rel->relids))
continue;
+ /*
+ * If this EquivalenceMember is a child, i.e., translated above,
+ * it should match the request. We cannot assert this if a request
+ * is bms_is_subset().
+ */
+ Assert(bms_equal(member->em_relids, index->rel->relids));
+
/*
* We allow any column of the index to match each pathkey; they
* don't have to match left-to-right as you might expect. This is
@@ -3800,6 +3832,7 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
if (found) /* don't want to look at remaining members */
break;
}
+ dispose_eclass_child_member_iterator(&it);
/*
* Return the matches found so far when this pathkey couldn't be
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 03c2ac36e05..b8f9c5f0e93 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1151,8 +1151,8 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
Oid sub_expr_coll = sub_eclass->ec_collation;
ListCell *k;
- if (sub_member->em_is_child)
- continue; /* ignore children here */
+ /* Child members should not exist in ec_members */
+ Assert(!sub_member->em_is_child);
foreach(k, subquery_tlist)
{
@@ -1709,8 +1709,11 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
{
EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+ /* Child members should not exist in ec_members */
+ Assert(!em->em_is_child);
+
/* Potential future join partner? */
- if (!em->em_is_const && !em->em_is_child &&
+ if (!em->em_is_const &&
!bms_overlap(em->em_relids, joinrel->relids))
score++;
}
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 178c572b021..b5f8d5fad0a 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -264,7 +264,9 @@ static IncrementalSort *make_incrementalsort(Plan *lefttree,
int numCols, int nPresortedCols,
AttrNumber *sortColIdx, Oid *sortOperators,
Oid *collations, bool *nullsFirst);
-static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
+static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
+ Plan *lefttree,
+ List *pathkeys,
Relids relids,
const AttrNumber *reqColIdx,
bool adjust_tlist_in_place,
@@ -273,9 +275,11 @@ static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
Oid **p_sortOperators,
Oid **p_collations,
bool **p_nullsFirst);
-static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
+static Sort *make_sort_from_pathkeys(PlannerInfo *root,
+ Plan *lefttree,
+ List *pathkeys,
Relids relids);
-static IncrementalSort *make_incrementalsort_from_pathkeys(Plan *lefttree,
+static IncrementalSort *make_incrementalsort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
List *pathkeys, Relids relids, int nPresortedCols);
static Sort *make_sort_from_groupcols(List *groupcls,
AttrNumber *grpColIdx,
@@ -297,7 +301,7 @@ static Group *make_group(List *tlist, List *qual, int numGroupCols,
AttrNumber *grpColIdx, Oid *grpOperators, Oid *grpCollations,
Plan *lefttree);
static Unique *make_unique_from_sortclauses(Plan *lefttree, List *distinctList);
-static Unique *make_unique_from_pathkeys(Plan *lefttree,
+static Unique *make_unique_from_pathkeys(PlannerInfo *root, Plan *lefttree,
List *pathkeys, int numCols);
static Gather *make_gather(List *qptlist, List *qpqual,
int nworkers, int rescan_param, bool single_copy, Plan *subplan);
@@ -1285,7 +1289,7 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
* function result; it must be the same plan node. However, we then
* need to detect whether any tlist entries were added.
*/
- (void) prepare_sort_from_pathkeys((Plan *) plan, pathkeys,
+ (void) prepare_sort_from_pathkeys(root, (Plan *) plan, pathkeys,
best_path->path.parent->relids,
NULL,
true,
@@ -1329,7 +1333,7 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
* don't need an explicit sort, to make sure they are returning
* the same sort key columns the Append expects.
*/
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
subpath->parent->relids,
nodeSortColIdx,
false,
@@ -1470,7 +1474,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
* function result; it must be the same plan node. However, we then need
* to detect whether any tlist entries were added.
*/
- (void) prepare_sort_from_pathkeys(plan, pathkeys,
+ (void) prepare_sort_from_pathkeys(root, plan, pathkeys,
best_path->path.parent->relids,
NULL,
true,
@@ -1501,7 +1505,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
/* Compute sort column info, and adjust subplan's tlist as needed */
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
subpath->parent->relids,
node->sortColIdx,
false,
@@ -1981,7 +1985,7 @@ create_gather_merge_plan(PlannerInfo *root, GatherMergePath *best_path)
Assert(pathkeys != NIL);
/* Compute sort column info, and adjust subplan's tlist as needed */
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
best_path->subpath->parent->relids,
gm_plan->sortColIdx,
false,
@@ -2195,7 +2199,7 @@ create_sort_plan(PlannerInfo *root, SortPath *best_path, int flags)
* relids. Thus, if this sort path is based on a child relation, we must
* pass its relids.
*/
- plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys,
+ plan = make_sort_from_pathkeys(root, subplan, best_path->path.pathkeys,
IS_OTHER_REL(best_path->subpath->parent) ?
best_path->path.parent->relids : NULL);
@@ -2219,7 +2223,7 @@ create_incrementalsort_plan(PlannerInfo *root, IncrementalSortPath *best_path,
/* See comments in create_sort_plan() above */
subplan = create_plan_recurse(root, best_path->spath.subpath,
flags | CP_SMALL_TLIST);
- plan = make_incrementalsort_from_pathkeys(subplan,
+ plan = make_incrementalsort_from_pathkeys(root, subplan,
best_path->spath.path.pathkeys,
IS_OTHER_REL(best_path->spath.subpath->parent) ?
best_path->spath.path.parent->relids : NULL,
@@ -2288,7 +2292,7 @@ create_upper_unique_plan(PlannerInfo *root, UpperUniquePath *best_path, int flag
subplan = create_plan_recurse(root, best_path->subpath,
flags | CP_LABEL_TLIST);
- plan = make_unique_from_pathkeys(subplan,
+ plan = make_unique_from_pathkeys(root, subplan,
best_path->path.pathkeys,
best_path->numkeys);
@@ -4550,7 +4554,8 @@ create_mergejoin_plan(PlannerInfo *root,
if (!use_incremental_sort)
{
sort_plan = (Plan *)
- make_sort_from_pathkeys(outer_plan,
+ make_sort_from_pathkeys(root,
+ outer_plan,
best_path->outersortkeys,
outer_relids);
@@ -4559,7 +4564,8 @@ create_mergejoin_plan(PlannerInfo *root,
else
{
sort_plan = (Plan *)
- make_incrementalsort_from_pathkeys(outer_plan,
+ make_incrementalsort_from_pathkeys(root,
+ outer_plan,
best_path->outersortkeys,
outer_relids,
presorted_keys);
@@ -4584,7 +4590,7 @@ create_mergejoin_plan(PlannerInfo *root,
*/
Relids inner_relids = inner_path->parent->relids;
- Sort *sort = make_sort_from_pathkeys(inner_plan,
+ Sort *sort = make_sort_from_pathkeys(root, inner_plan,
best_path->innersortkeys,
inner_relids);
@@ -6234,7 +6240,7 @@ make_incrementalsort(Plan *lefttree, int numCols, int nPresortedCols,
* or a Result stacked atop lefttree).
*/
static Plan *
-prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
+prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
Relids relids,
const AttrNumber *reqColIdx,
bool adjust_tlist_in_place,
@@ -6301,7 +6307,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
tle = get_tle_by_resno(tlist, reqColIdx[numsortkeys]);
if (tle)
{
- em = find_ec_member_matching_expr(ec, tle->expr, relids);
+ em = find_ec_member_matching_expr(root, ec, tle->expr, relids);
if (em)
{
/* found expr at right place in tlist */
@@ -6329,7 +6335,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
foreach(j, tlist)
{
tle = (TargetEntry *) lfirst(j);
- em = find_ec_member_matching_expr(ec, tle->expr, relids);
+ em = find_ec_member_matching_expr(root, ec, tle->expr, relids);
if (em)
{
/* found expr already in tlist */
@@ -6345,7 +6351,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
/*
* No matching tlist item; look for a computable expression.
*/
- em = find_computable_ec_member(NULL, ec, tlist, relids, false);
+ em = find_computable_ec_member(root, ec, tlist, relids, false);
if (!em)
elog(ERROR, "could not find pathkey item to sort");
pk_datatype = em->em_datatype;
@@ -6416,7 +6422,8 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
* 'relids' is the set of relations required by prepare_sort_from_pathkeys()
*/
static Sort *
-make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids)
+make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+ Relids relids)
{
int numsortkeys;
AttrNumber *sortColIdx;
@@ -6425,7 +6432,7 @@ make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids)
bool *nullsFirst;
/* Compute sort column info, and adjust lefttree as needed */
- lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys,
+ lefttree = prepare_sort_from_pathkeys(root, lefttree, pathkeys,
relids,
NULL,
false,
@@ -6451,8 +6458,9 @@ make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids)
* 'nPresortedCols' is the number of presorted columns in input tuples
*/
static IncrementalSort *
-make_incrementalsort_from_pathkeys(Plan *lefttree, List *pathkeys,
- Relids relids, int nPresortedCols)
+make_incrementalsort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+ List *pathkeys, Relids relids,
+ int nPresortedCols)
{
int numsortkeys;
AttrNumber *sortColIdx;
@@ -6461,7 +6469,7 @@ make_incrementalsort_from_pathkeys(Plan *lefttree, List *pathkeys,
bool *nullsFirst;
/* Compute sort column info, and adjust lefttree as needed */
- lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys,
+ lefttree = prepare_sort_from_pathkeys(root, lefttree, pathkeys,
relids,
NULL,
false,
@@ -6820,7 +6828,8 @@ make_unique_from_sortclauses(Plan *lefttree, List *distinctList)
* as above, but use pathkeys to identify the sort columns and semantics
*/
static Unique *
-make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
+make_unique_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+ int numCols)
{
Unique *node = makeNode(Unique);
Plan *plan = &node->plan;
@@ -6883,7 +6892,7 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
foreach(j, plan->targetlist)
{
tle = (TargetEntry *) lfirst(j);
- em = find_ec_member_matching_expr(ec, tle->expr, NULL);
+ em = find_ec_member_matching_expr(root, ec, tle->expr, NULL);
if (em)
{
/* found expr already in tlist */
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index c5b906a9d43..3c2198ea5bd 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -470,6 +470,7 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
RelationGetRelid(parentrel);
Oid childOID = RelationGetRelid(childrel);
RangeTblEntry *childrte;
+ Index topParentRTindex;
Index childRTindex;
AppendRelInfo *appinfo;
TupleDesc child_tupdesc;
@@ -577,6 +578,19 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
Assert(root->append_rel_array[childRTindex] == NULL);
root->append_rel_array[childRTindex] = appinfo;
+ /*
+ * Find a top parent rel's index and save it to top_parent_relid_array.
+ */
+ if (root->top_parent_relid_array == NULL)
+ root->top_parent_relid_array =
+ (Index *) palloc0(root->simple_rel_array_size * sizeof(Index));
+ Assert(root->top_parent_relid_array[childRTindex] == 0);
+ topParentRTindex = parentRTindex;
+ while (root->append_rel_array[topParentRTindex] != NULL &&
+ root->append_rel_array[topParentRTindex]->parent_relid != 0)
+ topParentRTindex = root->append_rel_array[topParentRTindex]->parent_relid;
+ root->top_parent_relid_array[childRTindex] = topParentRTindex;
+
/*
* Build a PlanRowMark if parent is marked FOR UPDATE/SHARE.
*/
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index f96573eb5d6..ce494364173 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -123,11 +123,14 @@ setup_simple_rel_arrays(PlannerInfo *root)
if (root->append_rel_list == NIL)
{
root->append_rel_array = NULL;
+ root->top_parent_relid_array = NULL;
return;
}
root->append_rel_array = (AppendRelInfo **)
palloc0(size * sizeof(AppendRelInfo *));
+ root->top_parent_relid_array = (Index *)
+ palloc0(size * sizeof(Index));
/*
* append_rel_array is filled with any already-existing AppendRelInfos,
@@ -148,6 +151,27 @@ setup_simple_rel_arrays(PlannerInfo *root)
root->append_rel_array[child_relid] = appinfo;
}
+
+ /*
+ * Find a top parent rel's relid for each AppendRelInfo. We cannot do this
+ * in the last foreach loop because there may be multi-level parent-child
+ * relations.
+ */
+ for (int i = 0; i < size; i++)
+ {
+ int top_parent_relid;
+
+ if (root->append_rel_array[i] == NULL)
+ continue;
+
+ top_parent_relid = root->append_rel_array[i]->parent_relid;
+
+ while (root->append_rel_array[top_parent_relid] != NULL &&
+ root->append_rel_array[top_parent_relid]->parent_relid != 0)
+ top_parent_relid = root->append_rel_array[top_parent_relid]->parent_relid;
+
+ root->top_parent_relid_array[i] = top_parent_relid;
+ }
}
/*
@@ -175,12 +199,25 @@ expand_planner_arrays(PlannerInfo *root, int add_size)
repalloc0_array(root->simple_rte_array, RangeTblEntry *, root->simple_rel_array_size, new_size);
if (root->append_rel_array)
+ {
root->append_rel_array =
repalloc0_array(root->append_rel_array, AppendRelInfo *, root->simple_rel_array_size, new_size);
+ root->top_parent_relid_array =
+ repalloc0_array(root->top_parent_relid_array, Index, root->simple_rel_array_size, new_size);
+ }
else
+ {
root->append_rel_array =
palloc0_array(AppendRelInfo *, new_size);
+ /*
+ * We do not allocate top_parent_relid_array here so that
+ * find_relids_top_parents() can early find all of the given Relids
+ * are top-level.
+ */
+ root->top_parent_relid_array = NULL;
+ }
+
root->simple_rel_array_size = new_size;
}
@@ -234,6 +271,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
rel->subplan_params = NIL;
rel->rel_parallel_workers = -1; /* set up in get_relation_info */
rel->amflags = 0;
+ rel->eclass_child_members = NIL;
rel->serverid = InvalidOid;
if (rte->rtekind == RTE_RELATION)
{
@@ -629,6 +667,12 @@ add_join_rel(PlannerInfo *root, RelOptInfo *joinrel)
/* GEQO requires us to append the new joinrel to the end of the list! */
root->join_rel_list = lappend(root->join_rel_list, joinrel);
+ /*
+ * Store the index of this joinrel to use in
+ * add_child_join_rel_equivalences().
+ */
+ joinrel->join_rel_list_index = list_length(root->join_rel_list) - 1;
+
/* store it into the auxiliary hashtable if there is one. */
if (root->join_rel_hash)
{
@@ -741,6 +785,7 @@ build_join_rel(PlannerInfo *root,
joinrel->subplan_params = NIL;
joinrel->rel_parallel_workers = -1;
joinrel->amflags = 0;
+ joinrel->eclass_child_members = NIL;
joinrel->serverid = InvalidOid;
joinrel->userid = InvalidOid;
joinrel->useridiscurrent = false;
@@ -928,6 +973,7 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
joinrel->subroot = NULL;
joinrel->subplan_params = NIL;
joinrel->amflags = 0;
+ joinrel->eclass_child_members = NIL;
joinrel->serverid = InvalidOid;
joinrel->userid = InvalidOid;
joinrel->useridiscurrent = false;
@@ -1490,6 +1536,7 @@ fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
upperrel->cheapest_total_path = NULL;
upperrel->cheapest_unique_path = NULL;
upperrel->cheapest_parameterized_paths = NIL;
+ upperrel->eclass_child_members = NIL; /* XXX Is this required? */
root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
@@ -1530,6 +1577,48 @@ find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
}
+/*
+ * find_relids_top_parents_slow
+ * Slow path of find_relids_top_parents() macro.
+ *
+ * Do not call this directly; use the macro instead. See the macro comment for
+ * more details.
+ */
+Relids
+find_relids_top_parents_slow(PlannerInfo *root, Relids relids)
+{
+ Index *top_parent_relid_array = root->top_parent_relid_array;
+ Relids result;
+ bool is_top_parent;
+ int i;
+
+ /* This function should be called in the slow path */
+ Assert(top_parent_relid_array != NULL);
+
+ result = NULL;
+ is_top_parent = true;
+ i = -1;
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ int top_parent_relid = (int) top_parent_relid_array[i];
+
+ if (top_parent_relid == 0)
+ top_parent_relid = i; /* 'i' has no parents, so add itself */
+ else if (top_parent_relid != i)
+ is_top_parent = false;
+ result = bms_add_member(result, top_parent_relid);
+ }
+
+ if (is_top_parent)
+ {
+ bms_free(result);
+ return NULL;
+ }
+
+ return result;
+}
+
+
/*
* get_baserel_parampathinfo
* Get the ParamPathInfo for a parameterized path for a base relation,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 0759e00e96d..d351bc5fa85 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -248,6 +248,14 @@ struct PlannerInfo
*/
struct AppendRelInfo **append_rel_array pg_node_attr(read_write_ignore);
+ /*
+ * top_parent_relid_array is the same length as simple_rel_array and holds
+ * the top-level parent indexes of the corresponding rels within
+ * simple_rel_array. The element can be zero if the rel has no parents,
+ * i.e., is itself in a top-level.
+ */
+ Index *top_parent_relid_array pg_node_attr(read_write_ignore);
+
/*
* all_baserels is a Relids set of all base relids (but not joins or
* "other" rels) in the query. This is computed in deconstruct_jointree.
@@ -957,6 +965,17 @@ typedef struct RelOptInfo
/* Bitmask of optional features supported by the table AM */
uint32 amflags;
+ /*
+ * information about a join rel
+ */
+ /* index in root->join_rel_list of this rel */
+ Index join_rel_list_index;
+
+ /*
+ * EquivalenceMembers referencing this rel
+ */
+ List *eclass_child_members;
+
/*
* Information about foreign tables and foreign joins
*/
@@ -1376,6 +1395,12 @@ typedef struct JoinDomain
* entry: consider SELECT random() AS a, random() AS b ... ORDER BY b,a.
* So we record the SortGroupRef of the originating sort clause.
*
+ * EquivalenceClass->ec_members can only have parent members, and child members
+ * are stored in RelOptInfos, from which those child members are translated. To
+ * lookup child EquivalenceMembers, we use EquivalenceChildMemberIterator. See
+ * its comment for usage. The approach to lookup child members quickly is
+ * described as iterate_child_rel_equivalences() comment.
+ *
* NB: if ec_merged isn't NULL, this class has been merged into another, and
* should be ignored in favor of using the pointed-to class.
*
@@ -1448,10 +1473,46 @@ typedef struct EquivalenceMember
bool em_is_child; /* derived version for a child relation? */
Oid em_datatype; /* the "nominal type" used by the opfamily */
JoinDomain *em_jdomain; /* join domain containing the source clause */
+ Relids em_child_relids; /* all relids of child rels */
+ Bitmapset *em_child_joinrel_relids; /* indexes in root->join_rel_list
+ * of join rel children */
/* if em_is_child is true, this links to corresponding EM for top parent */
struct EquivalenceMember *em_parent pg_node_attr(read_write_ignore);
} EquivalenceMember;
+/*
+ * EquivalenceChildMemberIterator
+ *
+ * EquivalenceClass has only parent EquivalenceMembers, so we need to translate
+ * child members if necessary. EquivalenceChildMemberIterator provides a way to
+ * iterate over translated child members during the loop in addition to all of
+ * the parent EquivalenceMembers.
+ *
+ * The most common way to use this struct is as follows:
+ * -----
+ * EquivalenceClass *ec = given;
+ * Relids rel = given;
+ * EquivalenceChildMemberIterator it;
+ * EquivalenceMember *em;
+ *
+ * setup_eclass_child_member_iterator(&it, ec);
+ * while ((em = eclass_child_member_iterator_next(&it)) != NULL)
+ * {
+ * use em ...;
+ * if (we need to iterate over child EquivalenceMembers)
+ * iterate_child_rel_equivalences(&it, root, ec, em, rel);
+ * use em ...;
+ * }
+ * dispose_eclass_child_member_iterator(&it);
+ * -----
+ */
+typedef struct
+{
+ int index; /* current index within 'ec_members'. */
+ bool modified; /* is 'ec_members' a newly allocated one? */
+ List *ec_members; /* parent and child members */
+} EquivalenceChildMemberIterator;
+
/*
* PathKeys
*
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 1035e6560c1..5e79cf1f63b 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -332,6 +332,24 @@ extern Relids min_join_parameterization(PlannerInfo *root,
extern RelOptInfo *fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind,
Relids relids);
extern Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel);
+
+/*
+ * find_relids_top_parents
+ * Compute the set of top-parent relids of rel.
+ *
+ * Replaces all Relids appearing in the given 'relids' as their top-level
+ * parents. The result will be NULL if and only if all of the given relids are
+ * top-level.
+ *
+ * The motivation for having this feature as a macro rather than a function is
+ * that Relids are top-level in most cases. We can quickly determine when
+ * root->top_parent_relid_array is NULL.
+ */
+#define find_relids_top_parents(root, relids) \
+ (likely((root)->top_parent_relid_array == NULL) \
+ ? NULL : find_relids_top_parents_slow(root, relids))
+extern Relids find_relids_top_parents_slow(PlannerInfo *root, Relids relids);
+
extern ParamPathInfo *get_baserel_parampathinfo(PlannerInfo *root,
RelOptInfo *baserel,
Relids required_outer);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 54869d44013..50812e3a5d8 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -137,7 +137,8 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
Index sortref,
Relids rel,
bool create_it);
-extern EquivalenceMember *find_ec_member_matching_expr(EquivalenceClass *ec,
+extern EquivalenceMember *find_ec_member_matching_expr(PlannerInfo *root,
+ EquivalenceClass *ec,
Expr *expr,
Relids relids);
extern EquivalenceMember *find_computable_ec_member(PlannerInfo *root,
@@ -179,6 +180,15 @@ extern void add_setop_child_rel_equivalences(PlannerInfo *root,
RelOptInfo *child_rel,
List *child_tlist,
List *setop_pathkeys);
+extern void setup_eclass_child_member_iterator(EquivalenceChildMemberIterator *it,
+ EquivalenceClass *ec);
+extern EquivalenceMember *eclass_child_member_iterator_next(EquivalenceChildMemberIterator *it);
+extern void dispose_eclass_child_member_iterator(EquivalenceChildMemberIterator *it);
+extern void iterate_child_rel_equivalences(EquivalenceChildMemberIterator *it,
+ PlannerInfo *root,
+ EquivalenceClass *ec,
+ EquivalenceMember *parent_em,
+ Relids child_relids);
extern List *generate_implied_equalities_for_column(PlannerInfo *root,
RelOptInfo *rel,
ec_matches_callback_type callback,
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index ce33e55bf1d..9673feef969 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -684,6 +684,7 @@ EphemeralNamedRelation
EphemeralNamedRelationData
EphemeralNamedRelationMetadata
EphemeralNamedRelationMetadataData
+EquivalenceChildMemberIterator
EquivalenceClass
EquivalenceMember
ErrorContextCallback
--
2.45.2.windows.1
[application/octet-stream] v29-0002-Introduce-indexes-for-RestrictInfo.patch (42.9K, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/4-v29-0002-Introduce-indexes-for-RestrictInfo.patch)
download | inline diff:
From 559b292ebb2792c71551aca4d088df73dbfb6651 Mon Sep 17 00:00:00 2001
From: Yuya Watari <[email protected]>
Date: Fri, 25 Aug 2023 10:44:25 +0900
Subject: [PATCH v29 2/8] Introduce indexes for RestrictInfo
This commit adds indexes to speed up searches for RestrictInfos. When
there are many child partitions and we have to perform planning for join
operations on the tables, we have to handle a large number of
RestrictInfos, resulting in a long planning time.
This commit adds ec_[source|derive]_indexes to speed up the search. We
can use the indexes to filter out unwanted RestrictInfos, and improve
the planning performance.
Author: David Rowley <[email protected]> and me, and includes rebase by
Alena Rybakina <[email protected]> [1].
[1] https://www.postgresql.org/message-id/72d292a1-06ff-432a-a803-af5053786444%40yandex.ru
---
src/backend/nodes/outfuncs.c | 6 +-
src/backend/nodes/readfuncs.c | 2 +
src/backend/optimizer/path/costsize.c | 3 +-
src/backend/optimizer/path/equivclass.c | 516 ++++++++++++++++++++--
src/backend/optimizer/plan/analyzejoins.c | 49 +-
src/backend/optimizer/plan/planner.c | 2 +
src/backend/optimizer/prep/prepjointree.c | 2 +
src/backend/optimizer/util/appendinfo.c | 2 +
src/backend/optimizer/util/inherit.c | 7 +
src/backend/optimizer/util/restrictinfo.c | 5 +
src/include/nodes/parsenodes.h | 6 +
src/include/nodes/pathnodes.h | 41 +-
src/include/optimizer/paths.h | 21 +-
13 files changed, 593 insertions(+), 69 deletions(-)
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 9827cf16be4..bd6a79b57a7 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -466,8 +466,8 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
WRITE_NODE_FIELD(ec_opfamilies);
WRITE_OID_FIELD(ec_collation);
WRITE_NODE_FIELD(ec_members);
- WRITE_NODE_FIELD(ec_sources);
- WRITE_NODE_FIELD(ec_derives);
+ WRITE_BITMAPSET_FIELD(ec_source_indexes);
+ WRITE_BITMAPSET_FIELD(ec_derive_indexes);
WRITE_BITMAPSET_FIELD(ec_relids);
WRITE_BOOL_FIELD(ec_has_const);
WRITE_BOOL_FIELD(ec_has_volatile);
@@ -573,6 +573,8 @@ _outRangeTblEntry(StringInfo str, const RangeTblEntry *node)
WRITE_BOOL_FIELD(lateral);
WRITE_BOOL_FIELD(inFromCl);
WRITE_NODE_FIELD(securityQuals);
+ WRITE_BITMAPSET_FIELD(eclass_source_indexes);
+ WRITE_BITMAPSET_FIELD(eclass_derive_indexes);
}
static void
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index be5f19dd7f6..70864fc1b29 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -434,6 +434,8 @@ _readRangeTblEntry(void)
READ_BOOL_FIELD(lateral);
READ_BOOL_FIELD(inFromCl);
READ_NODE_FIELD(securityQuals);
+ READ_BITMAPSET_FIELD(eclass_source_indexes);
+ READ_BITMAPSET_FIELD(eclass_derive_indexes);
READ_DONE();
}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index c36687aa4df..1ec10212eb8 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -5839,7 +5839,8 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
if (ec && ec->ec_has_const)
{
EquivalenceMember *em = fkinfo->fk_eclass_member[i];
- RestrictInfo *rinfo = find_derived_clause_for_ec_member(ec,
+ RestrictInfo *rinfo = find_derived_clause_for_ec_member(root,
+ ec,
em);
if (rinfo)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 25ce4dd2242..474231499e6 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -42,6 +42,10 @@ static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
Expr *expr, Relids relids,
JoinDomain *jdomain,
Oid datatype);
+static void add_eq_source(PlannerInfo *root, EquivalenceClass *ec,
+ RestrictInfo *rinfo);
+static void add_eq_derive(PlannerInfo *root, EquivalenceClass *ec,
+ RestrictInfo *rinfo);
static void generate_base_implied_equalities_const(PlannerInfo *root,
EquivalenceClass *ec);
static void generate_base_implied_equalities_no_const(PlannerInfo *root,
@@ -319,7 +323,6 @@ process_equivalence(PlannerInfo *root,
/* If case 1, nothing to do, except add to sources */
if (ec1 == ec2)
{
- ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -330,6 +333,8 @@ process_equivalence(PlannerInfo *root,
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
+
+ add_eq_source(root, ec1, restrictinfo);
return true;
}
@@ -350,8 +355,10 @@ process_equivalence(PlannerInfo *root,
* be found.
*/
ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
- ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
- ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
+ ec1->ec_source_indexes = bms_join(ec1->ec_source_indexes,
+ ec2->ec_source_indexes);
+ ec1->ec_derive_indexes = bms_join(ec1->ec_derive_indexes,
+ ec2->ec_derive_indexes);
ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
ec1->ec_has_const |= ec2->ec_has_const;
/* can't need to set has_volatile */
@@ -363,10 +370,9 @@ process_equivalence(PlannerInfo *root,
root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
/* just to avoid debugging confusion w/ dangling pointers: */
ec2->ec_members = NIL;
- ec2->ec_sources = NIL;
- ec2->ec_derives = NIL;
+ ec2->ec_source_indexes = NULL;
+ ec2->ec_derive_indexes = NULL;
ec2->ec_relids = NULL;
- ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -377,13 +383,14 @@ process_equivalence(PlannerInfo *root,
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
+
+ add_eq_source(root, ec1, restrictinfo);
}
else if (ec1)
{
/* Case 3: add item2 to ec1 */
em2 = add_eq_member(ec1, item2, item2_relids,
jdomain, item2_type);
- ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -394,13 +401,14 @@ process_equivalence(PlannerInfo *root,
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
+
+ add_eq_source(root, ec1, restrictinfo);
}
else if (ec2)
{
/* Case 3: add item1 to ec2 */
em1 = add_eq_member(ec2, item1, item1_relids,
jdomain, item1_type);
- ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
ec2->ec_min_security = Min(ec2->ec_min_security,
restrictinfo->security_level);
ec2->ec_max_security = Max(ec2->ec_max_security,
@@ -411,6 +419,8 @@ process_equivalence(PlannerInfo *root,
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
+
+ add_eq_source(root, ec2, restrictinfo);
}
else
{
@@ -420,8 +430,8 @@ process_equivalence(PlannerInfo *root,
ec->ec_opfamilies = opfamilies;
ec->ec_collation = collation;
ec->ec_members = NIL;
- ec->ec_sources = list_make1(restrictinfo);
- ec->ec_derives = NIL;
+ ec->ec_source_indexes = NULL;
+ ec->ec_derive_indexes = NULL;
ec->ec_relids = NULL;
ec->ec_has_const = false;
ec->ec_has_volatile = false;
@@ -443,6 +453,8 @@ process_equivalence(PlannerInfo *root,
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
+
+ add_eq_source(root, ec, restrictinfo);
}
return true;
@@ -584,6 +596,167 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
return em;
}
+/*
+ * add_eq_source - add 'rinfo' in eq_sources for this 'ec'
+ */
+static void
+add_eq_source(PlannerInfo *root, EquivalenceClass *ec, RestrictInfo *rinfo)
+{
+ int source_idx = list_length(root->eq_sources);
+ int i;
+
+ ec->ec_source_indexes = bms_add_member(ec->ec_source_indexes, source_idx);
+ root->eq_sources = lappend(root->eq_sources, rinfo);
+ Assert(rinfo->eq_sources_index == -1);
+ rinfo->eq_sources_index = source_idx;
+
+ i = -1;
+ while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rte->eclass_source_indexes = bms_add_member(rte->eclass_source_indexes,
+ source_idx);
+ }
+}
+
+/*
+ * add_eq_derive - add 'rinfo' in eq_derives for this 'ec'
+ */
+static void
+add_eq_derive(PlannerInfo *root, EquivalenceClass *ec, RestrictInfo *rinfo)
+{
+ int derive_idx = list_length(root->eq_derives);
+ int i;
+
+ ec->ec_derive_indexes = bms_add_member(ec->ec_derive_indexes, derive_idx);
+ root->eq_derives = lappend(root->eq_derives, rinfo);
+ Assert(rinfo->eq_derives_index == -1);
+ rinfo->eq_derives_index = derive_idx;
+
+ i = -1;
+ while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rte->eclass_derive_indexes = bms_add_member(rte->eclass_derive_indexes,
+ derive_idx);
+ }
+}
+
+/*
+ * update_clause_relids
+ * Update RestrictInfo->clause_relids with adjusting the relevant indexes.
+ * The clause_relids field must be updated through this function, not by
+ * setting the field directly.
+ */
+void
+update_clause_relids(PlannerInfo *root, RestrictInfo *rinfo,
+ Relids new_clause_relids)
+{
+ int i;
+ Relids removing_relids;
+ Relids adding_relids;
+#ifdef USE_ASSERT_CHECKING
+ Relids common_relids;
+#endif
+
+ /*
+ * If there is nothing to do, we return immediately after setting the
+ * clause_relids field.
+ */
+ if (rinfo->eq_sources_index == -1 && rinfo->eq_derives_index == -1)
+ {
+ rinfo->clause_relids = new_clause_relids;
+ return;
+ }
+
+ /*
+ * Remove any references between this RestrictInfo and RangeTblEntries
+ * that are no longer relevant.
+ */
+ removing_relids = bms_difference(rinfo->clause_relids, new_clause_relids);
+ i = -1;
+ while ((i = bms_next_member(removing_relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ if (rinfo->eq_sources_index != -1)
+ {
+ Assert(bms_is_member(rinfo->eq_sources_index,
+ rte->eclass_source_indexes));
+ rte->eclass_source_indexes =
+ bms_del_member(rte->eclass_source_indexes,
+ rinfo->eq_sources_index);
+ }
+ if (rinfo->eq_derives_index != -1)
+ {
+ Assert(bms_is_member(rinfo->eq_derives_index,
+ rte->eclass_derive_indexes));
+ rte->eclass_derive_indexes =
+ bms_del_member(rte->eclass_derive_indexes,
+ rinfo->eq_derives_index);
+ }
+ }
+ bms_free(removing_relids);
+
+ /*
+ * Add references between this RestrictInfo and RangeTblEntries that will
+ * be relevant.
+ */
+ adding_relids = bms_difference(new_clause_relids, rinfo->clause_relids);
+ i = -1;
+ while ((i = bms_next_member(adding_relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ if (rinfo->eq_sources_index != -1)
+ {
+ Assert(!bms_is_member(rinfo->eq_sources_index,
+ rte->eclass_source_indexes));
+ rte->eclass_source_indexes =
+ bms_add_member(rte->eclass_source_indexes,
+ rinfo->eq_sources_index);
+ }
+ if (rinfo->eq_derives_index != -1)
+ {
+ Assert(!bms_is_member(rinfo->eq_derives_index,
+ rte->eclass_derive_indexes));
+ rte->eclass_derive_indexes =
+ bms_add_member(rte->eclass_derive_indexes,
+ rinfo->eq_derives_index);
+ }
+ }
+ bms_free(adding_relids);
+
+#ifdef USE_ASSERT_CHECKING
+
+ /*
+ * Verify that all indexes are set for common Relids.
+ */
+ common_relids = bms_intersect(rinfo->clause_relids, new_clause_relids);
+ i = -1;
+ while ((i = bms_next_member(common_relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ if (rinfo->eq_sources_index != -1)
+ Assert(bms_is_member(rinfo->eq_sources_index,
+ rte->eclass_source_indexes));
+ if (rinfo->eq_derives_index != -1)
+ Assert(bms_is_member(rinfo->eq_derives_index,
+ rte->eclass_derive_indexes));
+ }
+ bms_free(common_relids);
+#endif
+
+ /*
+ * Since we have done everything to adjust the indexes, we can set the
+ * clause_relids field.
+ */
+ rinfo->clause_relids = new_clause_relids;
+}
+
/*
* get_eclass_for_sort_expr
@@ -729,8 +902,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
newec->ec_opfamilies = list_copy(opfamilies);
newec->ec_collation = collation;
newec->ec_members = NIL;
- newec->ec_sources = NIL;
- newec->ec_derives = NIL;
+ newec->ec_source_indexes = NULL;
+ newec->ec_derive_indexes = NULL;
newec->ec_relids = NULL;
newec->ec_has_const = false;
newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
@@ -1134,7 +1307,7 @@ relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel,
* scanning of the quals and before Path construction begins.
*
* We make no attempt to avoid generating duplicate RestrictInfos here: we
- * don't search ec_sources or ec_derives for matches. It doesn't really
+ * don't search eq_sources or eq_derives for matches. It doesn't really
* seem worth the trouble to do so.
*/
void
@@ -1227,6 +1400,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
{
EquivalenceMember *const_em = NULL;
ListCell *lc;
+ int i;
/*
* In the trivial case where we just had one "var = const" clause, push
@@ -1236,9 +1410,9 @@ generate_base_implied_equalities_const(PlannerInfo *root,
* equivalent to the old one.
*/
if (list_length(ec->ec_members) == 2 &&
- list_length(ec->ec_sources) == 1)
+ bms_get_singleton_member(ec->ec_source_indexes, &i))
{
- RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
+ RestrictInfo *restrictinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
distribute_restrictinfo_to_rels(root, restrictinfo);
return;
@@ -1296,9 +1470,9 @@ generate_base_implied_equalities_const(PlannerInfo *root,
/*
* If the clause didn't degenerate to a constant, fill in the correct
- * markings for a mergejoinable clause, and save it in ec_derives. (We
+ * markings for a mergejoinable clause, and save it in eq_derives. (We
* will not re-use such clauses directly, but selectivity estimation
- * may consult the list later. Note that this use of ec_derives does
+ * may consult the list later. Note that this use of eq_derives does
* not overlap with its use for join clauses, since we never generate
* join clauses from an ec_has_const eclass.)
*/
@@ -1308,7 +1482,8 @@ generate_base_implied_equalities_const(PlannerInfo *root,
rinfo->left_ec = rinfo->right_ec = ec;
rinfo->left_em = cur_em;
rinfo->right_em = const_em;
- ec->ec_derives = lappend(ec->ec_derives, rinfo);
+
+ add_eq_derive(root, ec, rinfo);
}
}
}
@@ -1374,7 +1549,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
/*
* If the clause didn't degenerate to a constant, fill in the
* correct markings for a mergejoinable clause. We don't put it
- * in ec_derives however; we don't currently need to re-find such
+ * in eq_derives however; we don't currently need to re-find such
* clauses, and we don't want to clutter that list with non-join
* clauses.
*/
@@ -1431,11 +1606,12 @@ static void
generate_base_implied_equalities_broken(PlannerInfo *root,
EquivalenceClass *ec)
{
- ListCell *lc;
+ int i = -1;
- foreach(lc, ec->ec_sources)
+ while ((i = bms_next_member(ec->ec_source_indexes, i)) >= 0)
{
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+ RestrictInfo *restrictinfo = list_nth_node(RestrictInfo,
+ root->eq_sources, i);
if (ec->ec_has_const ||
bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
@@ -1476,11 +1652,11 @@ generate_base_implied_equalities_broken(PlannerInfo *root,
* Because the same join clauses are likely to be needed multiple times as
* we consider different join paths, we avoid generating multiple copies:
* whenever we select a particular pair of EquivalenceMembers to join,
- * we check to see if the pair matches any original clause (in ec_sources)
- * or previously-built clause (in ec_derives). This saves memory and allows
- * re-use of information cached in RestrictInfos. We also avoid generating
- * commutative duplicates, i.e. if the algorithm selects "a.x = b.y" but
- * we already have "b.y = a.x", we return the existing clause.
+ * we check to see if the pair matches any original clause in root's
+ * eq_sources or previously-built clause (in root's eq_derives). This saves
+ * memory and allows re-use of information cached in RestrictInfos. We also
+ * avoid generating commutative duplicates, i.e. if the algorithm selects
+ * "a.x = b.y" but we already have "b.y = a.x", we return the existing clause.
*
* If we are considering an outer join, sjinfo is the associated OJ info,
* otherwise it can be NULL.
@@ -1870,12 +2046,16 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
Relids nominal_inner_relids,
RelOptInfo *inner_rel)
{
+ Bitmapset *matching_es;
List *result = NIL;
- ListCell *lc;
+ int i;
- foreach(lc, ec->ec_sources)
+ matching_es = get_ec_source_indexes(root, ec, nominal_join_relids);
+ i = -1;
+ while ((i = bms_next_member(matching_es, i)) >= 0)
{
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+ RestrictInfo *restrictinfo = list_nth_node(RestrictInfo,
+ root->eq_sources, i);
Relids clause_relids = restrictinfo->required_relids;
if (bms_is_subset(clause_relids, nominal_join_relids) &&
@@ -1887,12 +2067,12 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
/*
* If we have to translate, just brute-force apply adjust_appendrel_attrs
* to all the RestrictInfos at once. This will result in returning
- * RestrictInfos that are not listed in ec_derives, but there shouldn't be
+ * RestrictInfos that are not listed in eq_derives, but there shouldn't be
* any duplication, and it's a sufficiently narrow corner case that we
* shouldn't sweat too much over it anyway.
*
* Since inner_rel might be an indirect descendant of the baserel
- * mentioned in the ec_sources clauses, we have to be prepared to apply
+ * mentioned in the eq_sources clauses, we have to be prepared to apply
* multiple levels of Var translation.
*/
if (IS_OTHER_REL(inner_rel) && result != NIL)
@@ -1954,10 +2134,11 @@ create_join_clause(PlannerInfo *root,
EquivalenceMember *rightem,
EquivalenceClass *parent_ec)
{
+ Bitmapset *matches;
RestrictInfo *rinfo;
RestrictInfo *parent_rinfo = NULL;
- ListCell *lc;
MemoryContext oldcontext;
+ int i;
/*
* Search to see if we already built a RestrictInfo for this pair of
@@ -1968,9 +2149,12 @@ create_join_clause(PlannerInfo *root,
* it's not identical, it'd better have the same effects, or the operator
* families we're using are broken.
*/
- foreach(lc, ec->ec_sources)
+ matches = bms_int_members(get_ec_source_indexes_strict(root, ec, leftem->em_relids),
+ get_ec_source_indexes_strict(root, ec, rightem->em_relids));
+ i = -1;
+ while ((i = bms_next_member(matches, i)) >= 0)
{
- rinfo = (RestrictInfo *) lfirst(lc);
+ rinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
if (rinfo->left_em == leftem &&
rinfo->right_em == rightem &&
rinfo->parent_ec == parent_ec)
@@ -1981,9 +2165,13 @@ create_join_clause(PlannerInfo *root,
return rinfo;
}
- foreach(lc, ec->ec_derives)
+ matches = bms_int_members(get_ec_derive_indexes_strict(root, ec, leftem->em_relids),
+ get_ec_derive_indexes_strict(root, ec, rightem->em_relids));
+
+ i = -1;
+ while ((i = bms_next_member(matches, i)) >= 0)
{
- rinfo = (RestrictInfo *) lfirst(lc);
+ rinfo = list_nth_node(RestrictInfo, root->eq_derives, i);
if (rinfo->left_em == leftem &&
rinfo->right_em == rightem &&
rinfo->parent_ec == parent_ec)
@@ -2056,7 +2244,7 @@ create_join_clause(PlannerInfo *root,
rinfo->left_em = leftem;
rinfo->right_em = rightem;
/* and save it for possible re-use */
- ec->ec_derives = lappend(ec->ec_derives, rinfo);
+ add_eq_derive(root, ec, rinfo);
MemoryContextSwitchTo(oldcontext);
@@ -2782,16 +2970,19 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
* Returns NULL if no such clause can be found.
*/
RestrictInfo *
-find_derived_clause_for_ec_member(EquivalenceClass *ec,
+find_derived_clause_for_ec_member(PlannerInfo *root, EquivalenceClass *ec,
EquivalenceMember *em)
{
- ListCell *lc;
+ int i;
Assert(ec->ec_has_const);
Assert(!em->em_is_const);
- foreach(lc, ec->ec_derives)
+
+ i = -1;
+ while ((i = bms_next_member(ec->ec_derive_indexes, i)) >= 0)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
+ i);
/*
* generate_base_implied_equalities_const will have put non-const
@@ -3517,7 +3708,7 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
* surely be true if both of them overlap ec_relids.)
*
* Note we don't test ec_broken; if we did, we'd need a separate code
- * path to look through ec_sources. Checking the membership anyway is
+ * path to look through eq_sources. Checking the membership anyway is
* OK as a possibly-overoptimistic heuristic.
*
* We don't test ec_has_const either, even though a const eclass won't
@@ -3605,7 +3796,7 @@ eclass_useful_for_merging(PlannerInfo *root,
/*
* Note we don't test ec_broken; if we did, we'd need a separate code path
- * to look through ec_sources. Checking the members anyway is OK as a
+ * to look through eq_sources. Checking the members anyway is OK as a
* possibly-overoptimistic heuristic.
*/
@@ -3762,3 +3953,240 @@ get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
/* Calculate and return the common EC indexes, recycling the left input. */
return bms_int_members(rel1ecs, rel2ecs);
}
+
+/*
+ * get_ec_source_indexes
+ * Returns a Bitmapset with indexes into root->eq_sources for all
+ * RestrictInfos in 'ec' that have
+ * bms_overlap(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+{
+ Bitmapset *rel_esis = NULL;
+ int i = -1;
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rel_esis = bms_add_members(rel_esis, rte->eclass_source_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ i = -1;
+ while ((i = bms_next_member(rel_esis, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
+ i);
+
+ Assert(bms_overlap(relids, rinfo->clause_relids));
+ }
+#endif
+
+ /* bitwise-AND to leave only the ones for this EquivalenceClass */
+ return bms_int_members(rel_esis, ec->ec_source_indexes);
+}
+
+/*
+ * get_ec_source_indexes_strict
+ * Returns a Bitmapset with indexes into root->eq_sources for all
+ * RestrictInfos in 'ec' that have
+ * bms_is_subset(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
+ Relids relids)
+{
+ Bitmapset *esis = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ /*
+ * bms_intersect to the first relation to try to keep the resulting
+ * Bitmapset as small as possible. This saves having to make a
+ * complete bms_copy() of one of them. One may contain significantly
+ * more words than the other.
+ */
+ esis = bms_intersect(ec->ec_source_indexes,
+ rte->eclass_source_indexes);
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ rte = root->simple_rte_array[i];
+ esis = bms_int_members(esis, rte->eclass_source_indexes);
+ }
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ i = -1;
+ while ((i = bms_next_member(esis, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
+ i);
+
+ Assert(bms_is_subset(relids, rinfo->clause_relids));
+ }
+#endif
+
+ return esis;
+}
+
+/*
+ * get_ec_derive_indexes
+ * Returns a Bitmapset with indexes into root->eq_derives for all
+ * RestrictInfos in 'ec' that have
+ * bms_overlap(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ *
+ * XXX is this function even needed?
+ */
+Bitmapset *
+get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+{
+ Bitmapset *rel_edis = NULL;
+ int i = -1;
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rel_edis = bms_add_members(rel_edis, rte->eclass_derive_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ i = -1;
+ while ((i = bms_next_member(rel_edis, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
+ i);
+
+ Assert(bms_overlap(relids, rinfo->clause_relids));
+ }
+#endif
+
+ /* bitwise-AND to leave only the ones for this EquivalenceClass */
+ return bms_int_members(rel_edis, ec->ec_derive_indexes);
+}
+
+/*
+ * get_ec_derive_indexes_strict
+ * Returns a Bitmapset with indexes into root->eq_derives for all
+ * RestrictInfos in 'ec' that have
+ * bms_is_subset(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
+ Relids relids)
+{
+ Bitmapset *edis = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ /*
+ * bms_intersect to the first relation to try to keep the resulting
+ * Bitmapset as small as possible. This saves having to make a
+ * complete bms_copy() of one of them. One may contain significantly
+ * more words than the other.
+ */
+ edis = bms_intersect(ec->ec_derive_indexes,
+ rte->eclass_derive_indexes);
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ rte = root->simple_rte_array[i];
+ edis = bms_int_members(edis, rte->eclass_derive_indexes);
+ }
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ i = -1;
+ while ((i = bms_next_member(edis, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
+ i);
+
+ Assert(bms_is_subset(relids, rinfo->clause_relids));
+ }
+#endif
+
+ return edis;
+}
+
+#ifdef USE_ASSERT_CHECKING
+/*
+ * verify_eclass_indexes
+ * Verify that there are no missing references between RestrictInfos and
+ * EquivalenceMember's indexes, namely eclass_source_indexes and
+ * eclass_derive_indexes. If you modify these indexes, you should check
+ * them with this function.
+ */
+void
+verify_eclass_indexes(PlannerInfo *root, EquivalenceClass *ec)
+{
+ ListCell *lc;
+
+ /*
+ * All RestrictInfos in root->eq_sources must have references to
+ * eclass_source_indexes.
+ */
+ foreach(lc, root->eq_sources)
+ {
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
+ int index;
+ int k;
+
+ /* Deleted members are marked NULL */
+ if (rinfo == NULL)
+ continue;
+
+ index = list_cell_number(root->eq_sources, lc);
+ k = -1;
+ while ((k = bms_next_member(rinfo->clause_relids, k)) >= 0)
+ {
+ /* must have a reference */
+ Assert(bms_is_member(index, root->simple_rte_array[k]->eclass_source_indexes));
+ }
+ }
+
+ /*
+ * All RestrictInfos in root->eq_derives must have references to
+ * eclass_derive_indexes.
+ */
+ foreach(lc, root->eq_derives)
+ {
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
+ int index;
+ int k;
+
+ /* Deleted members are marked NULL */
+ if (rinfo == NULL)
+ continue;
+
+ index = list_cell_number(root->eq_derives, lc);
+ k = -1;
+ while ((k = bms_next_member(rinfo->clause_relids, k)) >= 0)
+ {
+ /* must have a reference */
+ Assert(bms_is_member(index, root->simple_rte_array[k]->eclass_derive_indexes));
+ }
+ }
+}
+#endif
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 5bc16c4bfc7..4449b8a22ee 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -36,9 +36,10 @@
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
static void remove_rel_from_query(PlannerInfo *root, int relid,
SpecialJoinInfo *sjinfo);
-static void remove_rel_from_restrictinfo(RestrictInfo *rinfo,
+static void remove_rel_from_restrictinfo(PlannerInfo *root,
+ RestrictInfo *rinfo,
int relid, int ojrelid);
-static void remove_rel_from_eclass(EquivalenceClass *ec,
+static void remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec,
int relid, int ojrelid);
static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
@@ -445,7 +446,7 @@ remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
* that any such PHV is safe (and updated its ph_eval_at), so we
* can just drop those references.
*/
- remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
+ remove_rel_from_restrictinfo(root, rinfo, relid, ojrelid);
/*
* Cross-check that the clause itself does not reference the
@@ -474,7 +475,7 @@ remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
if (bms_is_member(relid, ec->ec_relids) ||
bms_is_member(ojrelid, ec->ec_relids))
- remove_rel_from_eclass(ec, relid, ojrelid);
+ remove_rel_from_eclass(root, ec, relid, ojrelid);
}
/*
@@ -547,19 +548,28 @@ remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
* we have to also clean up the sub-clauses.
*/
static void
-remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
+remove_rel_from_restrictinfo(PlannerInfo *root, RestrictInfo *rinfo, int relid,
+ int ojrelid)
{
+ Relids new_clause_relids;
+
/*
* initsplan.c is fairly cavalier about allowing RestrictInfos to share
* relid sets with other RestrictInfos, and SpecialJoinInfos too. Make
* sure this RestrictInfo has its own relid sets before we modify them.
- * (In present usage, clause_relids is probably not shared, but
- * required_relids could be; let's not assume anything.)
+ * The 'new_clause_relids' passed to update_clause_relids() must be a
+ * different instance from the current rinfo->clause_relids, so we make a
+ * copy of it.
+ */
+ new_clause_relids = bms_copy(rinfo->clause_relids);
+ new_clause_relids = bms_del_member(new_clause_relids, relid);
+ new_clause_relids = bms_del_member(new_clause_relids, ojrelid);
+ update_clause_relids(root, rinfo, new_clause_relids);
+
+ /*
+ * In present usage, required_relids could be shared, so we make a copy of
+ * it.
*/
- rinfo->clause_relids = bms_copy(rinfo->clause_relids);
- rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
- rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
- /* Likewise for required_relids */
rinfo->required_relids = bms_copy(rinfo->required_relids);
rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
@@ -584,14 +594,14 @@ remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
{
RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);
- remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
+ remove_rel_from_restrictinfo(root, rinfo2, relid, ojrelid);
}
}
else
{
RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);
- remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
+ remove_rel_from_restrictinfo(root, rinfo2, relid, ojrelid);
}
}
}
@@ -607,9 +617,11 @@ remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
* level(s).
*/
static void
-remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
+remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec, int relid,
+ int ojrelid)
{
ListCell *lc;
+ int i;
/* Fix up the EC's overall relids */
ec->ec_relids = bms_del_member(ec->ec_relids, relid);
@@ -636,11 +648,12 @@ remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
}
/* Fix up the source clauses, in case we can re-use them later */
- foreach(lc, ec->ec_sources)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_source_indexes, i)) >= 0)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
- remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
+ remove_rel_from_restrictinfo(root, rinfo, relid, ojrelid);
}
/*
@@ -648,7 +661,7 @@ remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
* drop them. (At this point, any such clauses would be base restriction
* clauses, which we'd not need anymore anyway.)
*/
- ec->ec_derives = NIL;
+ ec->ec_derive_indexes = NULL;
}
/*
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index a0a2de7ee4b..32feb4c86ff 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -661,6 +661,8 @@ subquery_planner(PlannerGlobal *glob, Query *parse, PlannerInfo *parent_root,
root->multiexpr_params = NIL;
root->join_domains = NIL;
root->eq_classes = NIL;
+ root->eq_sources = NIL;
+ root->eq_derives = NIL;
root->ec_merging_done = false;
root->last_rinfo_serial = 0;
root->all_result_relids =
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 3fa4d78c3e0..e68ff37e042 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -1153,6 +1153,8 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
subroot->multiexpr_params = NIL;
subroot->join_domains = NIL;
subroot->eq_classes = NIL;
+ subroot->eq_sources = NIL;
+ subroot->eq_derives = NIL;
subroot->ec_merging_done = false;
subroot->last_rinfo_serial = 0;
subroot->all_result_relids = NULL;
diff --git a/src/backend/optimizer/util/appendinfo.c b/src/backend/optimizer/util/appendinfo.c
index 45e8b74f944..db88047f8b7 100644
--- a/src/backend/optimizer/util/appendinfo.c
+++ b/src/backend/optimizer/util/appendinfo.c
@@ -495,6 +495,8 @@ adjust_appendrel_attrs_mutator(Node *node,
newinfo->right_bucketsize = -1;
newinfo->left_mcvfreq = -1;
newinfo->right_mcvfreq = -1;
+ newinfo->eq_sources_index = -1;
+ newinfo->eq_derives_index = -1;
return (Node *) newinfo;
}
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index 3c2198ea5bd..b5d3984219e 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -492,6 +492,13 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
*/
childrte = makeNode(RangeTblEntry);
memcpy(childrte, parentrte, sizeof(RangeTblEntry));
+ /*
+ * We do not want to inherit the EquivalenceMember indexes of the parent
+ * to its child
+ */
+ childrte->eclass_source_indexes = NULL;
+ childrte->eclass_derive_indexes = NULL;
+
Assert(parentrte->rtekind == RTE_RELATION); /* else this is dubious */
childrte->relid = childOID;
childrte->relkind = childrel->rd_rel->relkind;
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index ca3e764c201..917d6b199cf 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -238,6 +238,9 @@ make_plain_restrictinfo(PlannerInfo *root,
restrictinfo->left_hasheqoperator = InvalidOid;
restrictinfo->right_hasheqoperator = InvalidOid;
+ restrictinfo->eq_sources_index = -1;
+ restrictinfo->eq_derives_index = -1;
+
return restrictinfo;
}
@@ -394,6 +397,8 @@ commute_restrictinfo(RestrictInfo *rinfo, Oid comm_op)
result->right_mcvfreq = rinfo->left_mcvfreq;
result->left_hasheqoperator = InvalidOid;
result->right_hasheqoperator = InvalidOid;
+ result->eq_sources_index = -1;
+ result->eq_derives_index = -1;
return result;
}
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 0f9462493e3..d28e2034d09 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -1247,6 +1247,12 @@ typedef struct RangeTblEntry
bool inFromCl pg_node_attr(query_jumble_ignore);
/* security barrier quals to apply, if any */
List *securityQuals pg_node_attr(query_jumble_ignore);
+ Bitmapset *eclass_source_indexes; /* Indexes in PlannerInfo's eq_sources
+ * list for RestrictInfos that mention
+ * this relation */
+ Bitmapset *eclass_derive_indexes; /* Indexes in PlannerInfo's eq_derives
+ * list for RestrictInfos that mention
+ * this relation */
} RangeTblEntry;
/*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index d351bc5fa85..47f213d4f38 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -321,6 +321,12 @@ struct PlannerInfo
/* list of active EquivalenceClasses */
List *eq_classes;
+ /* list of source RestrictInfos used to build EquivalenceClasses */
+ List *eq_sources;
+
+ /* list of RestrictInfos derived from EquivalenceClasses */
+ List *eq_derives;
+
/* set true once ECs are canonical */
bool ec_merging_done;
@@ -1401,6 +1407,24 @@ typedef struct JoinDomain
* its comment for usage. The approach to lookup child members quickly is
* described as iterate_child_rel_equivalences() comment.
*
+ * At various locations in the query planner, we must search for source and
+ * derived RestrictInfos regarding a given EquivalenceClass. For the common
+ * case, an EquivalenceClass does not have a large number of RestrictInfos,
+ * however, in cases such as planning queries to partitioned tables, the
+ * number of members can become large. To maintain planning performance, we
+ * make use of a bitmap index to allow us to quickly find RestrictInfos in a
+ * given EquivalenceClass belonging to a given relation or set of relations.
+ * This is done by storing a list of RestrictInfos belonging to all
+ * EquivalenceClasses in PlannerInfo and storing a Bitmapset for each
+ * RelOptInfo which has a bit set for each RestrictInfo in that list which
+ * relates to the given relation. We also store a Bitmapset to mark all of
+ * the indexes in the PlannerInfo's list of RestrictInfos in the
+ * EquivalenceClass. We can quickly find the interesting indexes into the
+ * PlannerInfo's list by performing a bit-wise AND on the RelOptInfo's
+ * Bitmapset and the EquivalenceClasses. RestrictInfos must be looked up in
+ * PlannerInfo by this technique using the ec_source_indexes and
+ * ec_derive_indexes Bitmapsets.
+ *
* NB: if ec_merged isn't NULL, this class has been merged into another, and
* should be ignored in favor of using the pointed-to class.
*
@@ -1419,8 +1443,10 @@ typedef struct EquivalenceClass
List *ec_opfamilies; /* btree operator family OIDs */
Oid ec_collation; /* collation, if datatypes are collatable */
List *ec_members; /* list of EquivalenceMembers */
- List *ec_sources; /* list of generating RestrictInfos */
- List *ec_derives; /* list of derived RestrictInfos */
+ Bitmapset *ec_source_indexes; /* indexes into PlannerInfo's eq_sources
+ * list of generating RestrictInfos */
+ Bitmapset *ec_derive_indexes; /* indexes into PlannerInfo's eq_derives
+ * list of derived RestrictInfos */
Relids ec_relids; /* all relids appearing in ec_members, except
* for child members (see below) */
bool ec_has_const; /* any pseudoconstants in ec_members? */
@@ -2661,7 +2687,12 @@ typedef struct RestrictInfo
/* number of base rels in clause_relids */
int num_base_rels pg_node_attr(equal_ignore);
- /* The relids (varnos+varnullingrels) actually referenced in the clause: */
+ /*
+ * The relids (varnos+varnullingrels) actually referenced in the clause.
+ *
+ * NOTE: This field must be updated through update_clause_relids(), not by
+ * setting the field directly.
+ */
Relids clause_relids pg_node_attr(equal_ignore);
/* The set of relids required to evaluate the clause: */
@@ -2779,6 +2810,10 @@ typedef struct RestrictInfo
/* hash equality operators used for memoize nodes, else InvalidOid */
Oid left_hasheqoperator pg_node_attr(equal_ignore);
Oid right_hasheqoperator pg_node_attr(equal_ignore);
+
+ /* the index within root->eq_sources and root->eq_derives */
+ int eq_sources_index pg_node_attr(equal_ignore);
+ int eq_derives_index pg_node_attr(equal_ignore);
} RestrictInfo;
/*
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 50812e3a5d8..a24a5801c55 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -129,6 +129,8 @@ extern Expr *canonicalize_ec_expression(Expr *expr,
Oid req_type, Oid req_collation);
extern void reconsider_outer_join_clauses(PlannerInfo *root);
extern void rebuild_eclass_attr_needed(PlannerInfo *root);
+extern void update_clause_relids(PlannerInfo *root, RestrictInfo *rinfo,
+ Relids new_clause_relids);
extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
Expr *expr,
List *opfamilies,
@@ -165,7 +167,8 @@ extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2,
extern EquivalenceClass *match_eclasses_to_foreign_key_col(PlannerInfo *root,
ForeignKeyOptInfo *fkinfo,
int colno);
-extern RestrictInfo *find_derived_clause_for_ec_member(EquivalenceClass *ec,
+extern RestrictInfo *find_derived_clause_for_ec_member(PlannerInfo *root,
+ EquivalenceClass *ec,
EquivalenceMember *em);
extern void add_child_rel_equivalences(PlannerInfo *root,
AppendRelInfo *appinfo,
@@ -204,6 +207,22 @@ extern bool eclass_useful_for_merging(PlannerInfo *root,
extern bool is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist);
extern bool is_redundant_with_indexclauses(RestrictInfo *rinfo,
List *indexclauses);
+extern Bitmapset *get_ec_source_indexes(PlannerInfo *root,
+ EquivalenceClass *ec,
+ Relids relids);
+extern Bitmapset *get_ec_source_indexes_strict(PlannerInfo *root,
+ EquivalenceClass *ec,
+ Relids relids);
+extern Bitmapset *get_ec_derive_indexes(PlannerInfo *root,
+ EquivalenceClass *ec,
+ Relids relids);
+extern Bitmapset *get_ec_derive_indexes_strict(PlannerInfo *root,
+ EquivalenceClass *ec,
+ Relids relids);
+#ifdef USE_ASSERT_CHECKING
+extern void verify_eclass_indexes(PlannerInfo *root,
+ EquivalenceClass *ec);
+#endif
/*
* pathkeys.c
--
2.45.2.windows.1
[application/octet-stream] v29-0003-Move-EquivalenceClass-indexes-to-PlannerInfo.patch (14.4K, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/5-v29-0003-Move-EquivalenceClass-indexes-to-PlannerInfo.patch)
download | inline diff:
From 80337bf565cba807a58fc6dc959e93dd94c96f96 Mon Sep 17 00:00:00 2001
From: Yuya Watari <[email protected]>
Date: Fri, 19 Jan 2024 11:43:29 +0900
Subject: [PATCH v29 3/8] Move EquivalenceClass indexes to PlannerInfo
In the previous commit, the indexes, namely ec_[source|derive]_indexes,
were in RestrictInfo. This was a workaround because RelOptInfo was the
best place but some RelOptInfos can be NULL and we cannot store indexes
for them.
This commit introduces a new struct, EquivalenceClassIndexes. This
struct exists in PlannerInfo and holds our indexes. This change prevents
a serialization problem with RestirctInfo in the previous commit.
---
src/backend/nodes/outfuncs.c | 2 -
src/backend/nodes/readfuncs.c | 2 -
src/backend/optimizer/path/equivclass.c | 83 ++++++++++++-------------
src/backend/optimizer/util/inherit.c | 7 ---
src/backend/optimizer/util/relnode.c | 6 ++
src/include/nodes/parsenodes.h | 6 --
src/include/nodes/pathnodes.h | 26 ++++++++
src/tools/pgindent/typedefs.list | 1 +
8 files changed, 74 insertions(+), 59 deletions(-)
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bd6a79b57a7..8a635a2a12b 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -573,8 +573,6 @@ _outRangeTblEntry(StringInfo str, const RangeTblEntry *node)
WRITE_BOOL_FIELD(lateral);
WRITE_BOOL_FIELD(inFromCl);
WRITE_NODE_FIELD(securityQuals);
- WRITE_BITMAPSET_FIELD(eclass_source_indexes);
- WRITE_BITMAPSET_FIELD(eclass_derive_indexes);
}
static void
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index 70864fc1b29..be5f19dd7f6 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -434,8 +434,6 @@ _readRangeTblEntry(void)
READ_BOOL_FIELD(lateral);
READ_BOOL_FIELD(inFromCl);
READ_NODE_FIELD(securityQuals);
- READ_BITMAPSET_FIELD(eclass_source_indexes);
- READ_BITMAPSET_FIELD(eclass_derive_indexes);
READ_DONE();
}
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 474231499e6..96869ea80e8 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -613,10 +613,10 @@ add_eq_source(PlannerInfo *root, EquivalenceClass *ec, RestrictInfo *rinfo)
i = -1;
while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
- rte->eclass_source_indexes = bms_add_member(rte->eclass_source_indexes,
- source_idx);
+ index->source_indexes = bms_add_member(index->source_indexes,
+ source_idx);
}
}
@@ -637,10 +637,10 @@ add_eq_derive(PlannerInfo *root, EquivalenceClass *ec, RestrictInfo *rinfo)
i = -1;
while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
- rte->eclass_derive_indexes = bms_add_member(rte->eclass_derive_indexes,
- derive_idx);
+ index->derive_indexes = bms_add_member(index->derive_indexes,
+ derive_idx);
}
}
@@ -679,22 +679,22 @@ update_clause_relids(PlannerInfo *root, RestrictInfo *rinfo,
i = -1;
while ((i = bms_next_member(removing_relids, i)) >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
if (rinfo->eq_sources_index != -1)
{
Assert(bms_is_member(rinfo->eq_sources_index,
- rte->eclass_source_indexes));
- rte->eclass_source_indexes =
- bms_del_member(rte->eclass_source_indexes,
+ index->source_indexes));
+ index->source_indexes =
+ bms_del_member(index->source_indexes,
rinfo->eq_sources_index);
}
if (rinfo->eq_derives_index != -1)
{
Assert(bms_is_member(rinfo->eq_derives_index,
- rte->eclass_derive_indexes));
- rte->eclass_derive_indexes =
- bms_del_member(rte->eclass_derive_indexes,
+ index->derive_indexes));
+ index->derive_indexes =
+ bms_del_member(index->derive_indexes,
rinfo->eq_derives_index);
}
}
@@ -708,22 +708,22 @@ update_clause_relids(PlannerInfo *root, RestrictInfo *rinfo,
i = -1;
while ((i = bms_next_member(adding_relids, i)) >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
if (rinfo->eq_sources_index != -1)
{
Assert(!bms_is_member(rinfo->eq_sources_index,
- rte->eclass_source_indexes));
- rte->eclass_source_indexes =
- bms_add_member(rte->eclass_source_indexes,
+ index->source_indexes));
+ index->source_indexes =
+ bms_add_member(index->source_indexes,
rinfo->eq_sources_index);
}
if (rinfo->eq_derives_index != -1)
{
Assert(!bms_is_member(rinfo->eq_derives_index,
- rte->eclass_derive_indexes));
- rte->eclass_derive_indexes =
- bms_add_member(rte->eclass_derive_indexes,
+ index->derive_indexes));
+ index->derive_indexes =
+ bms_add_member(index->derive_indexes,
rinfo->eq_derives_index);
}
}
@@ -738,14 +738,14 @@ update_clause_relids(PlannerInfo *root, RestrictInfo *rinfo,
i = -1;
while ((i = bms_next_member(common_relids, i)) >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
if (rinfo->eq_sources_index != -1)
Assert(bms_is_member(rinfo->eq_sources_index,
- rte->eclass_source_indexes));
+ index->source_indexes));
if (rinfo->eq_derives_index != -1)
Assert(bms_is_member(rinfo->eq_derives_index,
- rte->eclass_derive_indexes));
+ index->derive_indexes));
}
bms_free(common_relids);
#endif
@@ -3970,9 +3970,9 @@ get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
while ((i = bms_next_member(relids, i)) >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
- rel_esis = bms_add_members(rel_esis, rte->eclass_source_indexes);
+ rel_esis = bms_add_members(rel_esis, index->source_indexes);
}
#ifdef USE_ASSERT_CHECKING
@@ -4008,7 +4008,7 @@ get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
if (i >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
/*
* bms_intersect to the first relation to try to keep the resulting
@@ -4017,12 +4017,12 @@ get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
* more words than the other.
*/
esis = bms_intersect(ec->ec_source_indexes,
- rte->eclass_source_indexes);
+ index->source_indexes);
while ((i = bms_next_member(relids, i)) >= 0)
{
- rte = root->simple_rte_array[i];
- esis = bms_int_members(esis, rte->eclass_source_indexes);
+ index = &root->eclass_indexes_array[i];
+ esis = bms_int_members(esis, index->source_indexes);
}
}
@@ -4059,9 +4059,9 @@ get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
while ((i = bms_next_member(relids, i)) >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
- rel_edis = bms_add_members(rel_edis, rte->eclass_derive_indexes);
+ rel_edis = bms_add_members(rel_edis, index->derive_indexes);
}
#ifdef USE_ASSERT_CHECKING
@@ -4097,7 +4097,7 @@ get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
if (i >= 0)
{
- RangeTblEntry *rte = root->simple_rte_array[i];
+ EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
/*
* bms_intersect to the first relation to try to keep the resulting
@@ -4106,12 +4106,12 @@ get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
* more words than the other.
*/
edis = bms_intersect(ec->ec_derive_indexes,
- rte->eclass_derive_indexes);
+ index->derive_indexes);
while ((i = bms_next_member(relids, i)) >= 0)
{
- rte = root->simple_rte_array[i];
- edis = bms_int_members(edis, rte->eclass_derive_indexes);
+ index = &root->eclass_indexes_array[i];
+ edis = bms_int_members(edis, index->derive_indexes);
}
}
@@ -4134,9 +4134,8 @@ get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
/*
* verify_eclass_indexes
* Verify that there are no missing references between RestrictInfos and
- * EquivalenceMember's indexes, namely eclass_source_indexes and
- * eclass_derive_indexes. If you modify these indexes, you should check
- * them with this function.
+ * EquivalenceMember's indexes, namely source_indexes and derive_indexes.
+ * If you modify these indexes, you should check them with this function.
*/
void
verify_eclass_indexes(PlannerInfo *root, EquivalenceClass *ec)
@@ -4145,7 +4144,7 @@ verify_eclass_indexes(PlannerInfo *root, EquivalenceClass *ec)
/*
* All RestrictInfos in root->eq_sources must have references to
- * eclass_source_indexes.
+ * source_indexes.
*/
foreach(lc, root->eq_sources)
{
@@ -4162,13 +4161,13 @@ verify_eclass_indexes(PlannerInfo *root, EquivalenceClass *ec)
while ((k = bms_next_member(rinfo->clause_relids, k)) >= 0)
{
/* must have a reference */
- Assert(bms_is_member(index, root->simple_rte_array[k]->eclass_source_indexes));
+ Assert(bms_is_member(index, root->eclass_indexes_array[k].source_indexes));
}
}
/*
* All RestrictInfos in root->eq_derives must have references to
- * eclass_derive_indexes.
+ * derive_indexes.
*/
foreach(lc, root->eq_derives)
{
@@ -4185,7 +4184,7 @@ verify_eclass_indexes(PlannerInfo *root, EquivalenceClass *ec)
while ((k = bms_next_member(rinfo->clause_relids, k)) >= 0)
{
/* must have a reference */
- Assert(bms_is_member(index, root->simple_rte_array[k]->eclass_derive_indexes));
+ Assert(bms_is_member(index, root->eclass_indexes_array[k].derive_indexes));
}
}
}
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index b5d3984219e..3c2198ea5bd 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -492,13 +492,6 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
*/
childrte = makeNode(RangeTblEntry);
memcpy(childrte, parentrte, sizeof(RangeTblEntry));
- /*
- * We do not want to inherit the EquivalenceMember indexes of the parent
- * to its child
- */
- childrte->eclass_source_indexes = NULL;
- childrte->eclass_derive_indexes = NULL;
-
Assert(parentrte->rtekind == RTE_RELATION); /* else this is dubious */
childrte->relid = childOID;
childrte->relkind = childrel->rd_rel->relkind;
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index ce494364173..ca1d7e91bff 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -119,6 +119,9 @@ setup_simple_rel_arrays(PlannerInfo *root)
root->simple_rte_array[rti++] = rte;
}
+ root->eclass_indexes_array = (EquivalenceClassIndexes *)
+ palloc0(size * sizeof(EquivalenceClassIndexes));
+
/* append_rel_array is not needed if there are no AppendRelInfos */
if (root->append_rel_list == NIL)
{
@@ -218,6 +221,9 @@ expand_planner_arrays(PlannerInfo *root, int add_size)
root->top_parent_relid_array = NULL;
}
+ root->eclass_indexes_array =
+ repalloc0_array(root->eclass_indexes_array, EquivalenceClassIndexes, root->simple_rel_array_size, new_size);
+
root->simple_rel_array_size = new_size;
}
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index d28e2034d09..0f9462493e3 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -1247,12 +1247,6 @@ typedef struct RangeTblEntry
bool inFromCl pg_node_attr(query_jumble_ignore);
/* security barrier quals to apply, if any */
List *securityQuals pg_node_attr(query_jumble_ignore);
- Bitmapset *eclass_source_indexes; /* Indexes in PlannerInfo's eq_sources
- * list for RestrictInfos that mention
- * this relation */
- Bitmapset *eclass_derive_indexes; /* Indexes in PlannerInfo's eq_derives
- * list for RestrictInfos that mention
- * this relation */
} RangeTblEntry;
/*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 47f213d4f38..09cfd626a6a 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -192,6 +192,8 @@ typedef struct PlannerInfo PlannerInfo;
#define HAVE_PLANNERINFO_TYPEDEF 1
#endif
+struct EquivalenceClassIndexes;
+
struct PlannerInfo
{
pg_node_attr(no_copy_equal, no_read, no_query_jumble)
@@ -248,6 +250,13 @@ struct PlannerInfo
*/
struct AppendRelInfo **append_rel_array pg_node_attr(read_write_ignore);
+ /*
+ * eclass_indexes_array is the same length as simple_rel_array and holds
+ * the indexes of the corresponding rels for faster lookups of
+ * RestrictInfo. See the EquivalenceClass comment for more details.
+ */
+ struct EquivalenceClassIndexes *eclass_indexes_array pg_node_attr(read_write_ignore);
+
/*
* top_parent_relid_array is the same length as simple_rel_array and holds
* the top-level parent indexes of the corresponding rels within
@@ -1539,6 +1548,23 @@ typedef struct
List *ec_members; /* parent and child members */
} EquivalenceChildMemberIterator;
+/*
+ * EquivalenceClassIndexes
+ *
+ * As mentioned in the EquivalenceClass comment, we introduce a
+ * bitmapset-based indexing mechanism for faster lookups of RestrictInfo. This
+ * struct exists for each relation and holds the corresponding indexes.
+ */
+typedef struct EquivalenceClassIndexes
+{
+ Bitmapset *source_indexes; /* Indexes in PlannerInfo's eq_sources list
+ * for RestrictInfos that mention this
+ * relation */
+ Bitmapset *derive_indexes; /* Indexes in PlannerInfo's eq_derives list
+ * for RestrictInfos that mention this
+ * relation */
+} EquivalenceClassIndexes;
+
/*
* PathKeys
*
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 9673feef969..a1f308e2ac4 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -686,6 +686,7 @@ EphemeralNamedRelationMetadata
EphemeralNamedRelationMetadataData
EquivalenceChildMemberIterator
EquivalenceClass
+EquivalenceClassIndexes
EquivalenceMember
ErrorContextCallback
ErrorData
--
2.45.2.windows.1
[application/octet-stream] v29-0004-Rename-add_eq_member-to-add_parent_eq_member.patch (5.2K, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/6-v29-0004-Rename-add_eq_member-to-add_parent_eq_member.patch)
download | inline diff:
From 8c39e9822bc090c335ba4d1d29ebea23470bec29 Mon Sep 17 00:00:00 2001
From: Yuya Watari <[email protected]>
Date: Wed, 21 Aug 2024 13:54:59 +0900
Subject: [PATCH v29 4/8] Rename add_eq_member() to add_parent_eq_member()
After our changes, add_eq_member() no longer creates and adds child
EquivalenceMembers. This commit renames it to add_parent_eq_member() to
clarify that it only creates parent members, and that we need to use
make_eq_member() to handle child EquivalenceMembers.
---
src/backend/optimizer/path/equivclass.c | 54 ++++++++++++-------------
1 file changed, 27 insertions(+), 27 deletions(-)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 96869ea80e8..e30d931f19c 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -38,10 +38,10 @@ static EquivalenceMember *make_eq_member(EquivalenceClass *ec,
JoinDomain *jdomain,
EquivalenceMember *parent,
Oid datatype);
-static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
- Expr *expr, Relids relids,
- JoinDomain *jdomain,
- Oid datatype);
+static EquivalenceMember *add_parent_eq_member(EquivalenceClass *ec,
+ Expr *expr, Relids relids,
+ JoinDomain *jdomain,
+ Oid datatype);
static void add_eq_source(PlannerInfo *root, EquivalenceClass *ec,
RestrictInfo *rinfo);
static void add_eq_derive(PlannerInfo *root, EquivalenceClass *ec,
@@ -389,8 +389,8 @@ process_equivalence(PlannerInfo *root,
else if (ec1)
{
/* Case 3: add item2 to ec1 */
- em2 = add_eq_member(ec1, item2, item2_relids,
- jdomain, item2_type);
+ em2 = add_parent_eq_member(ec1, item2, item2_relids,
+ jdomain, item2_type);
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -407,8 +407,8 @@ process_equivalence(PlannerInfo *root,
else if (ec2)
{
/* Case 3: add item1 to ec2 */
- em1 = add_eq_member(ec2, item1, item1_relids,
- jdomain, item1_type);
+ em1 = add_parent_eq_member(ec2, item1, item1_relids,
+ jdomain, item1_type);
ec2->ec_min_security = Min(ec2->ec_min_security,
restrictinfo->security_level);
ec2->ec_max_security = Max(ec2->ec_max_security,
@@ -440,10 +440,10 @@ process_equivalence(PlannerInfo *root,
ec->ec_min_security = restrictinfo->security_level;
ec->ec_max_security = restrictinfo->security_level;
ec->ec_merged = NULL;
- em1 = add_eq_member(ec, item1, item1_relids,
- jdomain, item1_type);
- em2 = add_eq_member(ec, item2, item2_relids,
- jdomain, item2_type);
+ em1 = add_parent_eq_member(ec, item1, item1_relids,
+ jdomain, item1_type);
+ em2 = add_parent_eq_member(ec, item2, item2_relids,
+ jdomain, item2_type);
root->eq_classes = lappend(root->eq_classes, ec);
@@ -578,7 +578,7 @@ make_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
}
/*
- * add_eq_member - build a new parent EquivalenceMember and add it to an EC
+ * add_parent_eq_member - build a new parent EquivalenceMember and add it to an EC
*
* Note: We don't have a function to add a child member like
* add_child_eq_member() because how to do it depends on the relations they are
@@ -586,8 +586,8 @@ make_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
* add_child_join_rel_equivalences() to see how to add child members.
*/
static EquivalenceMember *
-add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
- JoinDomain *jdomain, Oid datatype)
+add_parent_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
+ JoinDomain *jdomain, Oid datatype)
{
EquivalenceMember *em = make_eq_member(ec, expr, relids, jdomain,
NULL, datatype);
@@ -921,14 +921,14 @@ get_eclass_for_sort_expr(PlannerInfo *root,
*/
expr_relids = pull_varnos(root, (Node *) expr);
- newem = add_eq_member(newec, copyObject(expr), expr_relids,
- jdomain, opcintype);
+ newem = add_parent_eq_member(newec, copyObject(expr), expr_relids,
+ jdomain, opcintype);
/*
- * add_eq_member doesn't check for volatile functions, set-returning
- * functions, aggregates, or window functions, but such could appear in
- * sort expressions; so we have to check whether its const-marking was
- * correct.
+ * add_parent_eq_member doesn't check for volatile functions,
+ * set-returning functions, aggregates, or window functions, but such
+ * could appear in sort expressions; so we have to check whether its
+ * const-marking was correct.
*/
if (newec->ec_has_const)
{
@@ -3305,12 +3305,12 @@ add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel,
* likewise, the JoinDomain can be that of the initial member of the
* Pathkey's EquivalenceClass.
*/
- add_eq_member(pk->pk_eclass,
- tle->expr,
- child_rel->relids,
- parent_em->em_jdomain,
- parent_em,
- exprType((Node *) tle->expr));
+ add_parent_eq_member(pk->pk_eclass,
+ tle->expr,
+ child_rel->relids,
+ parent_em->em_jdomain,
+ parent_em,
+ exprType((Node *) tle->expr));
lc2 = lnext(setop_pathkeys, lc2);
}
--
2.45.2.windows.1
[application/octet-stream] v29-0005-Resolve-conflict-with-commit-66c0185.patch (6.4K, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/7-v29-0005-Resolve-conflict-with-commit-66c0185.patch)
download | inline diff:
From a4e61b85297506ae3b94a92bf5ace5cdd067c4ef Mon Sep 17 00:00:00 2001
From: Yuya Watari <[email protected]>
Date: Tue, 27 Aug 2024 13:20:29 +0900
Subject: [PATCH v29 5/8] Resolve conflict with commit 66c0185
This commit resolves a conflict with 66c0185, which added
add_setop_child_rel_equivalences().
The function creates child EquivalenceMembers to efficiently implement
UNION queries. This commit adjusts our optimization to handle this type
of child EquivalenceMembers based on UNION parent-child relationships.
---
src/backend/optimizer/path/equivclass.c | 51 ++++++++++++++++++++++---
src/backend/optimizer/util/inherit.c | 8 +++-
src/backend/optimizer/util/relnode.c | 10 +++--
src/include/nodes/pathnodes.h | 2 +-
4 files changed, 59 insertions(+), 12 deletions(-)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index e30d931f19c..022f20020af 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -3288,7 +3288,9 @@ add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel,
{
TargetEntry *tle = lfirst_node(TargetEntry, lc);
EquivalenceMember *parent_em;
+ EquivalenceMember *child_em;
PathKey *pk;
+ Index parent_relid;
if (tle->resjunk)
continue;
@@ -3305,12 +3307,49 @@ add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel,
* likewise, the JoinDomain can be that of the initial member of the
* Pathkey's EquivalenceClass.
*/
- add_parent_eq_member(pk->pk_eclass,
- tle->expr,
- child_rel->relids,
- parent_em->em_jdomain,
- parent_em,
- exprType((Node *) tle->expr));
+ child_em = make_eq_member(pk->pk_eclass,
+ tle->expr,
+ child_rel->relids,
+ parent_em->em_jdomain,
+ parent_em,
+ exprType((Node *) tle->expr));
+ child_rel->eclass_child_members =
+ lappend(child_rel->eclass_child_members, child_em);
+
+ /*
+ * We save the knowledge that 'child_em' can be translated using
+ * 'child_rel'. This knowledge is useful for
+ * add_transformed_child_version() to find child members from the
+ * given Relids.
+ */
+ parent_em->em_child_relids =
+ bms_add_member(parent_em->em_child_relids, child_rel->relid);
+
+ /*
+ * Make an UNION parent-child relationship between parent_em and
+ * child_rel->relid. We record this relationship in
+ * root->top_parent_relid_array, which generally has AppendRelInfo
+ * relationships. We use the same array here to retrieve UNION child
+ * members.
+ *
+ * XXX Here we treat the first member of parent_em->em_relids as a
+ * parent of child_rel. Is this correct? What happens if
+ * parent_em->em_relids has two or more members?
+ */
+ parent_relid = bms_next_member(parent_em->em_relids, -1);
+ if (root->top_parent_relid_array == NULL)
+ {
+ /*
+ * If the array is NULL, allocate it here.
+ */
+ root->top_parent_relid_array = (Index *)
+ palloc(root->simple_rel_array_size * sizeof(Index));
+ MemSet(root->top_parent_relid_array, -1,
+ sizeof(Index) * root->simple_rel_array_size);
+ }
+ Assert(root->top_parent_relid_array[child_rel->relid] == -1 ||
+ root->top_parent_relid_array[child_rel->relid] == parent_relid);
+ root->top_parent_relid_array[child_rel->relid] = parent_relid;
lc2 = lnext(setop_pathkeys, lc2);
}
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index 3c2198ea5bd..7b2390687e0 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -582,9 +582,13 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
* Find a top parent rel's index and save it to top_parent_relid_array.
*/
if (root->top_parent_relid_array == NULL)
+ {
root->top_parent_relid_array =
- (Index *) palloc0(root->simple_rel_array_size * sizeof(Index));
- Assert(root->top_parent_relid_array[childRTindex] == 0);
+ (Index *) palloc(root->simple_rel_array_size * sizeof(Index));
+ MemSet(root->top_parent_relid_array, -1,
+ sizeof(Index) * root->simple_rel_array_size);
+ }
+ Assert(root->top_parent_relid_array[childRTindex] == -1);
topParentRTindex = parentRTindex;
while (root->append_rel_array[topParentRTindex] != NULL &&
root->append_rel_array[topParentRTindex]->parent_relid != 0)
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index ca1d7e91bff..fcd57c1f3e9 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -133,7 +133,9 @@ setup_simple_rel_arrays(PlannerInfo *root)
root->append_rel_array = (AppendRelInfo **)
palloc0(size * sizeof(AppendRelInfo *));
root->top_parent_relid_array = (Index *)
- palloc0(size * sizeof(Index));
+ palloc(size * sizeof(Index));
+ MemSet(root->top_parent_relid_array, -1,
+ sizeof(Index) * size);
/*
* append_rel_array is filled with any already-existing AppendRelInfos,
@@ -206,7 +208,9 @@ expand_planner_arrays(PlannerInfo *root, int add_size)
root->append_rel_array =
repalloc0_array(root->append_rel_array, AppendRelInfo *, root->simple_rel_array_size, new_size);
root->top_parent_relid_array =
- repalloc0_array(root->top_parent_relid_array, Index, root->simple_rel_array_size, new_size);
+ repalloc_array(root->top_parent_relid_array, Index, new_size);
+ MemSet(root->top_parent_relid_array + root->simple_rel_array_size, -1,
+ sizeof(Index) * add_size);
}
else
{
@@ -1608,7 +1612,7 @@ find_relids_top_parents_slow(PlannerInfo *root, Relids relids)
{
int top_parent_relid = (int) top_parent_relid_array[i];
- if (top_parent_relid == 0)
+ if (top_parent_relid == -1)
top_parent_relid = i; /* 'i' has no parents, so add itself */
else if (top_parent_relid != i)
is_top_parent = false;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 09cfd626a6a..7009cb0dd89 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -260,7 +260,7 @@ struct PlannerInfo
/*
* top_parent_relid_array is the same length as simple_rel_array and holds
* the top-level parent indexes of the corresponding rels within
- * simple_rel_array. The element can be zero if the rel has no parents,
+ * simple_rel_array. The element can be -1 if the rel has no parents,
* i.e., is itself in a top-level.
*/
Index *top_parent_relid_array pg_node_attr(read_write_ignore);
--
2.45.2.windows.1
[application/octet-stream] v29-0006-Don-t-use-likely-in-find_relids_top_parents.patch (955B, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/8-v29-0006-Don-t-use-likely-in-find_relids_top_parents.patch)
download | inline diff:
From 367a57f208413f2df08824610480d6325c20b08b Mon Sep 17 00:00:00 2001
From: Yuya Watari <[email protected]>
Date: Fri, 29 Nov 2024 14:49:42 +0900
Subject: [PATCH v29 6/8] Don't use likely in find_relids_top_parents
---
src/include/optimizer/pathnode.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 5e79cf1f63b..cf21ba29fe9 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -346,7 +346,7 @@ extern Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel);
* root->top_parent_relid_array is NULL.
*/
#define find_relids_top_parents(root, relids) \
- (likely((root)->top_parent_relid_array == NULL) \
+ ((root)->top_parent_relid_array == NULL \
? NULL : find_relids_top_parents_slow(root, relids))
extern Relids find_relids_top_parents_slow(PlannerInfo *root, Relids relids);
--
2.45.2.windows.1
[application/octet-stream] v29-0007-Don-t-use-unlikely-top_parent-NULL.patch (4.5K, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/9-v29-0007-Don-t-use-unlikely-top_parent-NULL.patch)
download | inline diff:
From 13e4f61743b99809ecbbcf3454cd6d11d90a4254 Mon Sep 17 00:00:00 2001
From: Yuya Watari <[email protected]>
Date: Fri, 29 Nov 2024 14:49:43 +0900
Subject: [PATCH v29 7/8] Don't use unlikely(top_parent != NULL)
---
contrib/postgres_fdw/postgres_fdw.c | 2 +-
src/backend/optimizer/path/equivclass.c | 10 +++++-----
src/backend/optimizer/path/indxpath.c | 2 +-
3 files changed, 7 insertions(+), 7 deletions(-)
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index e68c116164c..030fe741030 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7854,7 +7854,7 @@ find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
* If child EquivalenceMembers may match the request, we add and
* iterate over them by calling iterate_child_rel_equivalences().
*/
- if (unlikely(top_parent_rel_relids != NULL) && !em->em_is_child &&
+ if (top_parent_rel_relids != NULL && !em->em_is_child &&
bms_is_subset(em->em_relids, top_parent_rel_relids))
iterate_child_rel_equivalences(&it, root, ec, em, rel->relids);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 022f20020af..86057538c5c 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -861,7 +861,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
* If child EquivalenceMembers may match the request, we add and
* iterate over them by calling iterate_child_rel_equivalences().
*/
- if (unlikely(top_parent_rel != NULL) && !cur_em->em_is_child &&
+ if (top_parent_rel != NULL && !cur_em->em_is_child &&
bms_equal(cur_em->em_relids, top_parent_rel))
iterate_child_rel_equivalences(&it, root, cur_ec, cur_em, rel);
@@ -1034,7 +1034,7 @@ find_ec_member_matching_expr(PlannerInfo *root, EquivalenceClass *ec,
* If child EquivalenceMembers may match the request, we add and
* iterate over them by calling iterate_child_rel_equivalences().
*/
- if (unlikely(top_parent_relids != NULL) && !em->em_is_child &&
+ if (top_parent_relids != NULL && !em->em_is_child &&
bms_is_subset(em->em_relids, top_parent_relids))
iterate_child_rel_equivalences(&it, root, ec, em, relids);
@@ -1144,7 +1144,7 @@ find_computable_ec_member(PlannerInfo *root,
* If child EquivalenceMembers may match the request, we add and
* iterate over them by calling iterate_child_rel_equivalences().
*/
- if (unlikely(top_parent_relids != NULL) && !em->em_is_child &&
+ if (top_parent_relids != NULL && !em->em_is_child &&
bms_is_subset(em->em_relids, top_parent_relids))
iterate_child_rel_equivalences(&it, root, ec, em, relids);
@@ -1881,7 +1881,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
* If child EquivalenceMembers may match the request, we add and
* iterate over them by calling iterate_child_rel_equivalences().
*/
- if (unlikely(top_parent_join_relids != NULL) && !cur_em->em_is_child &&
+ if (top_parent_join_relids != NULL && !cur_em->em_is_child &&
bms_is_subset(cur_em->em_relids, top_parent_join_relids))
iterate_child_rel_equivalences(&it, root, ec, cur_em, join_relids);
@@ -3616,7 +3616,7 @@ generate_implied_equalities_for_column(PlannerInfo *root,
* If child EquivalenceMembers may match the request, we add and
* iterate over them by calling iterate_child_rel_equivalences().
*/
- if (unlikely(top_parent_rel_relids != NULL) && !cur_em->em_is_child &&
+ if (top_parent_rel_relids != NULL && !cur_em->em_is_child &&
bms_equal(cur_em->em_relids, top_parent_rel_relids))
iterate_child_rel_equivalences(&it, root, cur_ec, cur_em, rel->relids);
if (bms_equal(cur_em->em_relids, rel->relids) &&
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 4a42752486e..9b7d01a85d8 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3787,7 +3787,7 @@ match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index, List *pathkeys,
* If child EquivalenceMembers may match the request, we add and
* iterate over them by calling iterate_child_rel_equivalences().
*/
- if (unlikely(top_parent_index_relids != NULL) && !member->em_is_child &&
+ if (top_parent_index_relids != NULL && !member->em_is_child &&
bms_equal(member->em_relids, top_parent_index_relids))
iterate_child_rel_equivalences(&it, root, pathkey->pk_eclass, member,
index->rel->relids);
--
2.45.2.windows.1
[application/octet-stream] v29-0008-Introduce-RestrictInfoIterator-to-reduce-memory-.patch (17.2K, ../../CAJ2pMkb-5N5bHekr9NdX-vKkfOshQiUt22Qrffq48t0UmOe9Ug@mail.gmail.com/10-v29-0008-Introduce-RestrictInfoIterator-to-reduce-memory-.patch)
download | inline diff:
From 3e6392538153ffd46743bbedaf7f763afc13a2a6 Mon Sep 17 00:00:00 2001
From: Yuya Watari <[email protected]>
Date: Fri, 20 Dec 2024 12:01:35 +0900
Subject: [PATCH v29 8/8] Introduce RestrictInfoIterator to reduce memory
consumption
Originally, get_ec_[source|derive]_indexes[_strict]() functions created
temporal Bitmapsets each time they were called. This resulted in large
memory consumption.
This commit introduces a new iterator mechanism called
RestrictInfoIterator. This iterator iterates over RestrictInfos using
indexes without creating temporary Bitmapsets. Experimental results show
that this commit significantly reduces memory consumption.
---
src/backend/nodes/bitmapset.c | 3 +
src/backend/optimizer/path/equivclass.c | 313 +++++++++++-------------
src/include/nodes/pathnodes.h | 38 +++
src/include/optimizer/paths.h | 18 +-
src/tools/pgindent/typedefs.list | 1 +
5 files changed, 198 insertions(+), 175 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index cd05c642b04..67330467b6c 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1301,6 +1301,9 @@ bms_join(Bitmapset *a, Bitmapset *b)
* loop-not-started state (x == -1) from the loop-completed state (x == -2).
* It makes no difference in simple loop usage, but complex iteration logic
* might need such an ability.
+ *
+ * NOTE: The routine here is similar to eclass_rinfo_iterator_next(). If you
+ * change here, you should adjust the logic there.
*/
int
bms_next_member(const Bitmapset *a, int prevbit)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 86057538c5c..a890cc3507d 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2046,16 +2046,14 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
Relids nominal_inner_relids,
RelOptInfo *inner_rel)
{
- Bitmapset *matching_es;
List *result = NIL;
- int i;
+ RestrictInfo *restrictinfo;
+ RestrictInfoIterator iter;
- matching_es = get_ec_source_indexes(root, ec, nominal_join_relids);
- i = -1;
- while ((i = bms_next_member(matching_es, i)) >= 0)
+ setup_eclass_rinfo_iterator(&iter, root, ec, nominal_join_relids, true,
+ false);
+ while ((restrictinfo = eclass_rinfo_iterator_next(&iter)) != NULL)
{
- RestrictInfo *restrictinfo = list_nth_node(RestrictInfo,
- root->eq_sources, i);
Relids clause_relids = restrictinfo->required_relids;
if (bms_is_subset(clause_relids, nominal_join_relids) &&
@@ -2063,6 +2061,7 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
!bms_is_subset(clause_relids, nominal_inner_relids))
result = lappend(result, restrictinfo);
}
+ dispose_eclass_rinfo_iterator(&iter);
/*
* If we have to translate, just brute-force apply adjust_appendrel_attrs
@@ -2134,11 +2133,10 @@ create_join_clause(PlannerInfo *root,
EquivalenceMember *rightem,
EquivalenceClass *parent_ec)
{
- Bitmapset *matches;
RestrictInfo *rinfo;
RestrictInfo *parent_rinfo = NULL;
MemoryContext oldcontext;
- int i;
+ RestrictInfoIterator iter;
/*
* Search to see if we already built a RestrictInfo for this pair of
@@ -2149,12 +2147,11 @@ create_join_clause(PlannerInfo *root,
* it's not identical, it'd better have the same effects, or the operator
* families we're using are broken.
*/
- matches = bms_int_members(get_ec_source_indexes_strict(root, ec, leftem->em_relids),
- get_ec_source_indexes_strict(root, ec, rightem->em_relids));
- i = -1;
- while ((i = bms_next_member(matches, i)) >= 0)
+ setup_eclass_rinfo_iterator(&iter, root, ec,
+ bms_union(leftem->em_relids, rightem->em_relids),
+ true, true);
+ while ((rinfo = eclass_rinfo_iterator_next(&iter)) != NULL)
{
- rinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
if (rinfo->left_em == leftem &&
rinfo->right_em == rightem &&
rinfo->parent_ec == parent_ec)
@@ -2164,14 +2161,13 @@ create_join_clause(PlannerInfo *root,
rinfo->parent_ec == parent_ec)
return rinfo;
}
+ dispose_eclass_rinfo_iterator(&iter);
- matches = bms_int_members(get_ec_derive_indexes_strict(root, ec, leftem->em_relids),
- get_ec_derive_indexes_strict(root, ec, rightem->em_relids));
-
- i = -1;
- while ((i = bms_next_member(matches, i)) >= 0)
+ setup_eclass_rinfo_iterator(&iter, root, ec,
+ bms_union(leftem->em_relids, rightem->em_relids),
+ false, true);
+ while ((rinfo = eclass_rinfo_iterator_next(&iter)) != NULL)
{
- rinfo = list_nth_node(RestrictInfo, root->eq_derives, i);
if (rinfo->left_em == leftem &&
rinfo->right_em == rightem &&
rinfo->parent_ec == parent_ec)
@@ -2181,6 +2177,7 @@ create_join_clause(PlannerInfo *root,
rinfo->parent_ec == parent_ec)
return rinfo;
}
+ dispose_eclass_rinfo_iterator(&iter);
/*
* Not there, so build it, in planner context so we can re-use it. (Not
@@ -3994,179 +3991,167 @@ get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
}
/*
- * get_ec_source_indexes
- * Returns a Bitmapset with indexes into root->eq_sources for all
- * RestrictInfos in 'ec' that have
- * bms_overlap(relids, rinfo->clause_relids) as true.
+ * setup_eclass_rinfo_iterator
+ * Setup a RestrictInfoIterator 'iter' so that it can iterate over
+ * RestrictInfos. We iterate through root->eq_sources if 'is_source' is
+ * true, or root->eq_derives otherwise. The members must be from 'ec' and
+ * satisfy "bms_is_subset(relids, rinfo->clause_relids)" if 'is_strict' is
+ * true, or "bms_overlap(relids, rinfo->clause_relids)" otherwise.
*
- * Returns a newly allocated Bitmapset which the caller is free to modify.
+ * Once used, the caller should dispose of the iterator by calling
+ * dispose_eclass_rinfo_iterator().
*/
-Bitmapset *
-get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+void
+setup_eclass_rinfo_iterator(RestrictInfoIterator *iter, PlannerInfo *root,
+ EquivalenceClass *ec, Relids relids,
+ bool is_source, bool is_strict)
{
- Bitmapset *rel_esis = NULL;
- int i = -1;
-
- while ((i = bms_next_member(relids, i)) >= 0)
- {
- EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
-
- rel_esis = bms_add_members(rel_esis, index->source_indexes);
- }
-
-#ifdef USE_ASSERT_CHECKING
- /* verify the results look sane */
- i = -1;
- while ((i = bms_next_member(rel_esis, i)) >= 0)
- {
- RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
- i);
-
- Assert(bms_overlap(relids, rinfo->clause_relids));
- }
-#endif
-
- /* bitwise-AND to leave only the ones for this EquivalenceClass */
- return bms_int_members(rel_esis, ec->ec_source_indexes);
+ iter->root = root;
+ iter->ec = ec;
+ iter->relids = relids;
+ iter->is_source = is_source;
+ iter->is_strict = is_strict;
+ iter->last_word = 0;
+ iter->wordnum = -1;
+ iter->index = -1;
}
/*
- * get_ec_source_indexes_strict
- * Returns a Bitmapset with indexes into root->eq_sources for all
- * RestrictInfos in 'ec' that have
- * bms_is_subset(relids, rinfo->clause_relids) as true.
- *
- * Returns a newly allocated Bitmapset which the caller is free to modify.
+ * eclass_rinfo_iterator_next
+ * Get a next RestrictInfo from an RestrictInfoIterator 'iter' that was
+ * setup by setup_eclass_rinfo_iterator(). NULL is returned if there are no
+ * members left.
*/
-Bitmapset *
-get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
- Relids relids)
+RestrictInfo *
+eclass_rinfo_iterator_next(RestrictInfoIterator *iter)
{
- Bitmapset *esis = NULL;
- int i = bms_next_member(relids, -1);
+ RestrictInfo *rinfo;
+ bitmapword mask;
+ bitmapword w;
+ int bitnum;
- if (i >= 0)
- {
- EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
+ if (iter->index <= -2)
+ return NULL; /* Already finished iteration */
+ /*
+ * The routine in this function is similar to bms_next_member(). If you
+ * change its behavior, you should adjust the logic here.
+ */
+ ++(iter->index);
+ bitnum = iter->index % BITS_PER_BITMAPWORD;
+ mask = (~(bitmapword) 0) << bitnum;
+
+ /*
+ * Do we need to consume a new word?
+ */
+ if (bitnum == 0 || (iter->last_word & mask) == 0)
+ {
/*
- * bms_intersect to the first relation to try to keep the resulting
- * Bitmapset as small as possible. This saves having to make a
- * complete bms_copy() of one of them. One may contain significantly
- * more words than the other.
+ * Yes, we need a new word.
*/
- esis = bms_intersect(ec->ec_source_indexes,
- index->source_indexes);
-
- while ((i = bms_next_member(relids, i)) >= 0)
+ while (true)
{
- index = &root->eclass_indexes_array[i];
- esis = bms_int_members(esis, index->source_indexes);
- }
- }
+ Bitmapset *ec_members_index;
+ bitmapword word;
+ int i;
-#ifdef USE_ASSERT_CHECKING
- /* verify the results look sane */
- i = -1;
- while ((i = bms_next_member(esis, i)) >= 0)
- {
- RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
- i);
+ iter->wordnum++; /* Consume */
- Assert(bms_is_subset(relids, rinfo->clause_relids));
- }
-#endif
+ /*
+ * Are there still members in ec?
+ */
+ ec_members_index = iter->is_source ?
+ iter->ec->ec_source_indexes : iter->ec->ec_derive_indexes;
+ if (ec_members_index == NULL || iter->wordnum >= ec_members_index->nwords)
+ {
+ iter->index = -2;
+ return NULL; /* No words left */
+ }
- return esis;
-}
+ /*
+ * We intersect the corresponding Bitmapset indexes for the
+ * is_strict case or union them for the non-is_strict case.
+ */
+ word = iter->is_strict ? (~(bitmapword) 0) : 0;
-/*
- * get_ec_derive_indexes
- * Returns a Bitmapset with indexes into root->eq_derives for all
- * RestrictInfos in 'ec' that have
- * bms_overlap(relids, rinfo->clause_relids) as true.
- *
- * Returns a newly allocated Bitmapset which the caller is free to modify.
- *
- * XXX is this function even needed?
- */
-Bitmapset *
-get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
-{
- Bitmapset *rel_edis = NULL;
- int i = -1;
+ /*
+ * Loop over 'relids' to intersect or union all indexes.
+ */
+ i = -1;
+ while ((i = bms_next_member(iter->relids, i)) >= 0)
+ {
+ EquivalenceClassIndexes *ec_indexes =
+ &iter->root->eclass_indexes_array[i];
+ Bitmapset *index = iter->is_source ?
+ ec_indexes->source_indexes : ec_indexes->derive_indexes;
- while ((i = bms_next_member(relids, i)) >= 0)
- {
- EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
+ if (index == NULL || iter->wordnum >= index->nwords)
+ {
+ /* This word is zero. */
+ if (iter->is_strict)
+ {
+ word = 0;
+ break; /* We don't need to do anything. */
+ }
+ else
+ continue;
+ }
- rel_edis = bms_add_members(rel_edis, index->derive_indexes);
- }
+ if (iter->is_strict)
+ word &= index->words[iter->wordnum];
+ else
+ word |= index->words[iter->wordnum];
+ }
-#ifdef USE_ASSERT_CHECKING
- /* verify the results look sane */
- i = -1;
- while ((i = bms_next_member(rel_edis, i)) >= 0)
- {
- RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
- i);
+ /*
+ * Leave only the members for this EquivalenceClass.
+ */
+ word &= ec_members_index->words[iter->wordnum];
- Assert(bms_overlap(relids, rinfo->clause_relids));
+ /*
+ * Did we find new members?
+ */
+ if (word != 0)
+ {
+ /* Yes, we find new ones. */
+ iter->last_word = word;
+ mask = (~(bitmapword) 0);
+ break;
+ }
+ /* No, we need to consume more word */
+ }
}
+
+ /*
+ * Here, 'iter->last_word' must have a new member. We get it.
+ */
+ w = iter->last_word & mask;
+ Assert(w != 0);
+ iter->index =
+ iter->wordnum * BITS_PER_BITMAPWORD + bmw_rightmost_one_pos(w);
+ rinfo = list_nth_node(RestrictInfo,
+ iter->is_source ? iter->root->eq_sources : iter->root->eq_derives,
+ iter->index);
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the result look sane */
+ if (iter->is_strict)
+ Assert(bms_is_subset(iter->relids, rinfo->clause_relids));
+ else
+ Assert(bms_overlap(iter->relids, rinfo->clause_relids));
#endif
- /* bitwise-AND to leave only the ones for this EquivalenceClass */
- return bms_int_members(rel_edis, ec->ec_derive_indexes);
+ return rinfo;
}
/*
- * get_ec_derive_indexes_strict
- * Returns a Bitmapset with indexes into root->eq_derives for all
- * RestrictInfos in 'ec' that have
- * bms_is_subset(relids, rinfo->clause_relids) as true.
- *
- * Returns a newly allocated Bitmapset which the caller is free to modify.
+ * dispose_eclass_rinfo_iterator
+ * Free any memory allocated by the iterator.
*/
-Bitmapset *
-get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
- Relids relids)
+void
+dispose_eclass_rinfo_iterator(RestrictInfoIterator *iter)
{
- Bitmapset *edis = NULL;
- int i = bms_next_member(relids, -1);
-
- if (i >= 0)
- {
- EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
-
- /*
- * bms_intersect to the first relation to try to keep the resulting
- * Bitmapset as small as possible. This saves having to make a
- * complete bms_copy() of one of them. One may contain significantly
- * more words than the other.
- */
- edis = bms_intersect(ec->ec_derive_indexes,
- index->derive_indexes);
-
- while ((i = bms_next_member(relids, i)) >= 0)
- {
- index = &root->eclass_indexes_array[i];
- edis = bms_int_members(edis, index->derive_indexes);
- }
- }
-
-#ifdef USE_ASSERT_CHECKING
- /* verify the results look sane */
- i = -1;
- while ((i = bms_next_member(edis, i)) >= 0)
- {
- RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
- i);
-
- Assert(bms_is_subset(relids, rinfo->clause_relids));
- }
-#endif
-
- return edis;
+ /* Do nothing */
}
#ifdef USE_ASSERT_CHECKING
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 7009cb0dd89..3b4d4c9962f 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1548,6 +1548,44 @@ typedef struct
List *ec_members; /* parent and child members */
} EquivalenceChildMemberIterator;
+/*
+ * RestrictInfoIterator
+ *
+ * This iterator provides a way to iterate over RestrictInfos in an
+ * EquivalenceClass that satisfy a certain condition. You need to first
+ * initialize an iterator, and then use move next during the iteration. You
+ * can specify the condition during initialization. For more details, see the
+ * comment in setup_eclass_rinfo_iterator().
+ *
+ * The most common way to use this struct is as follows:
+ * -----
+ * PlannerInfo *root = given;
+ * EquivalenceClass *ec = given;
+ * Relids relids = given;
+ * RestrictInfoIterator iter;
+ * RestrictInfo *rinfo;
+ *
+ * setup_eclass_rinfo_iterator(&iter, root, ec, relids, true, true);
+ * while ((rinfo = eclass_rinfo_iterator_next(&iter)) != NULL)
+ * {
+ * use rinfo ...;
+ * }
+ * dispose_eclass_rinfo_iterator(&iter);
+ * -----
+ */
+typedef struct
+{
+ PlannerInfo *root;
+ EquivalenceClass *ec; /* EC where we are looking now */
+ Relids relids; /* Relids that we are checking */
+ bool is_source; /* Do we iterate over root->eq_sources? */
+ bool is_strict; /* Do we intersect the indexes? */
+ bitmapword last_word; /* Bitmapword at last iteration */
+ int wordnum; /* Wordnum at last iteration */
+ int index; /* The last RestrictInfo index we returned to
+ * the caller */
+} RestrictInfoIterator;
+
/*
* EquivalenceClassIndexes
*
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index a24a5801c55..e6aa4c715d9 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -207,18 +207,14 @@ extern bool eclass_useful_for_merging(PlannerInfo *root,
extern bool is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist);
extern bool is_redundant_with_indexclauses(RestrictInfo *rinfo,
List *indexclauses);
-extern Bitmapset *get_ec_source_indexes(PlannerInfo *root,
+extern void setup_eclass_rinfo_iterator(RestrictInfoIterator *iter,
+ PlannerInfo *root,
EquivalenceClass *ec,
- Relids relids);
-extern Bitmapset *get_ec_source_indexes_strict(PlannerInfo *root,
- EquivalenceClass *ec,
- Relids relids);
-extern Bitmapset *get_ec_derive_indexes(PlannerInfo *root,
- EquivalenceClass *ec,
- Relids relids);
-extern Bitmapset *get_ec_derive_indexes_strict(PlannerInfo *root,
- EquivalenceClass *ec,
- Relids relids);
+ Relids relids,
+ bool is_source,
+ bool is_strict);
+extern RestrictInfo *eclass_rinfo_iterator_next(RestrictInfoIterator *iter);
+extern void dispose_eclass_rinfo_iterator(RestrictInfoIterator *iter);
#ifdef USE_ASSERT_CHECKING
extern void verify_eclass_indexes(PlannerInfo *root,
EquivalenceClass *ec);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index a1f308e2ac4..0f4e0c48f4a 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2469,6 +2469,7 @@ ResourceReleasePriority
RestoreOptions
RestorePass
RestrictInfo
+RestrictInfoIterator
Result
ResultRelInfo
ResultState
--
2.45.2.windows.1
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2024-12-20 05:26 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2020-11-20 02:48 [PATCH 1/3] bootstrap: convert Typ to a List* Justin Pryzby <[email protected]>
2024-12-12 12:09 Re: [PoC] Reducing planning time when tables have many partitions Alvaro Herrera <[email protected]>
2024-12-13 08:44 ` Re: [PoC] Reducing planning time when tables have many partitions Yuya Watari <[email protected]>
2024-12-13 10:53 ` Re: [PoC] Reducing planning time when tables have many partitions Alvaro Herrera <[email protected]>
2024-12-20 05:26 ` Re: [PoC] Reducing planning time when tables have many partitions Yuya Watari <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox