esOn Tue, 9 Aug 2022 at 19:10, David Rowley <[email protected]> wrote:
> I've not had a chance to look at the 0003 patch yet.
I've looked at the 0003 patch now.
The performance numbers look quite impressive, however, there were a
few things about the patch that I struggled to figure what they were
done the way you did them:
+ root->eq_not_children_indexes = bms_add_member(root->eq_not_children_indexes,
Why is that in PlannerInfo rather than in the EquivalenceClass?
if (bms_equal(rel->relids, em->em_relids))
{
rel->eclass_member_indexes =
bms_add_member(rel->eclass_member_indexes, em_index);
}
Why are you only adding the eclass_member_index to the RelOptInfo when
the em_relids contain a singleton relation?
I ended up going and fixing the patch to be more how I imagined it.
I've ended up with 3 Bitmapset fields in EquivalenceClass;
ec_member_indexes, ec_nonchild_indexes, ec_norel_indexes. I also
trimmed the number of helper functions down for obtaining the minimal
set of matching EquivalenceMember indexes to just:
Bitmapset *
get_ecmember_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids,
bool with_children, bool with_norel_members)
Bitmapset *
get_ecmember_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
Relids relids, bool with_children,
bool with_norel_members)
I'm not so much a fan of the bool parameters, but it seemed better
than having 8 different functions with each combination of the bool
paramters instead of 2.
The "strict" version of the function takes the intersection of
eclass_member_indexes for each rel mentioned in relids, whereas the
non-strict version does a union of those. Each then intersect that
with all members in the 'ec', or just the non-child members when
'with_children' is false. They both then optionally bms_add_members()
the ec_norel_members if with_norel_members is true. I found it
difficult to figure out the best order to do the intersection. That
really depends on if the particular query has many EquivalenceClasses
with few EquivalenceMembers or few EquivalenceClasses with many
EquivalenceMembers. bms_int_members() always recycles the left input.
Ideally, that would always be the smallest Bitmapset. Maybe it's worth
inventing a new version of bms_int_members() that recycles the input
with the least nwords. That would give the subsequent
bms_next_member() calls an easier time. Right now they'll need to loop
over a bunch of 0 words at the end for many queries.
A few problems I ran into along the way:
1. generate_append_tlist() generates Vars with varno=0. That causes
problems when we add Exprs from those in add_eq_member() as there is
no element at root->simple_rel_array[0] to add eclass_member_indexes
to.
2. The existing comment for EquivalenceMember.em_relids claims "all
relids appearing in em_expr", but that's just not true when it comes
to em_is_child members.
So far, I fixed #1 by adding a hack to setup_simple_rel_arrays() to do
"root->simple_rel_array[0] = makeNode(RelOptInfo);" I'm not suggesting
that's the correct fix. It might be possible to set the varnos to the
varnos from the first Append child instead.
The fact that #2 is not true adds quite a bit of complexity to the
patch and I think the patch might even misbehave as a result. It seems
there are cases where a child em_relids can contain additional relids
that are not present in the em_expr. For example, when a UNION ALL
child has a Const in the targetlist, as explained in a comment in
add_child_rel_equivalences(). However, there also seem to be cases
where the opposite is true. I had to add the following code in
add_eq_member() to stop a regression test failing:
if (is_child)
expr_relids = bms_add_members(expr_relids, relids);
That's to make sure we add eclass_member_indexes to each RelOptInfo
mentioned in the em_expr.
After doing all that, I noticed that your benchmark was showing that
create_join_clause() was the new bottleneck. This was due to having to
loop so many times over the ec_sources to find an already built
RestrictInfo. I went off and added some new code to optimize the
lookup of those in a similar way by adding a new Bitmapset field in
RelOptInfo to index which ec_sources it mentioned, which meant having
to move ec_sources into PlannerInfo. I don't think this part of the
patch is quite right yet as the code I have relies on em_relids being
the same as the ones mentioned in the RestrictInfo. That seems not
true for em_is_child EMs, so I think we probably need to add a new
field to EquivalenceMember that truly is just pull_varnos from
em_expr, or else look into some way to make em_relids mean that (like
the comment claims).
Here are my results from running your benchmark on master (@f6c750d31)
with and without the attached patch.
npart master (ms) patched (ms) speedup
2 0.28 0.29 95.92%
4 0.37 0.38 96.75%
8 0.53 0.56 94.43%
16 0.92 0.91 100.36%
32 1.82 1.70 107.57%
64 4.05 3.26 124.32%
128 10.83 6.69 161.89%
256 42.63 19.46 219.12%
512 194.31 42.60 456.14%
1024 1104.02 98.37 1122.33%
This resulted in some good additional gains in planner performance.
The 1024 partition case is now about 11x faster on my machine instead
of 4x. The 2 partition does regress slightly. There might be a few
things we can do about that, for example, move ec_collation up 1 to
shrink EquivalenceClass back down closer to the size it was before.
[1] might be enough to make up for the remainder.
I've attached a draft patch with my revisions.
David
[1] https://commitfest.postgresql.org/39/3810/
diff --git a/contrib/postgres_fdw/postgres_fdw.c
b/contrib/postgres_fdw/postgres_fdw.c
index 16320170ce..e8996456be 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7412,19 +7412,23 @@ conversion_error_callback(void *arg)
EquivalenceMember *
find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
{
- ListCell *lc;
+ Bitmapset *matching_ems;
+ int i = -1;
+
+ matching_ems = get_ecmember_indexes(root, ec, rel->relids, true, false);
- foreach(lc, ec->ec_members)
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
root->eq_members, i);
/*
* Note we require !bms_is_empty, else we'd accept constant
* expressions which are not suitable for the purpose.
*/
- if (bms_is_subset(em->em_relids, rel->relids) &&
- !bms_is_empty(em->em_relids) &&
- is_foreign_expr(root, rel, em->em_expr))
+ Assert(bms_is_subset(em->em_relids, rel->relids));
+ Assert(!bms_is_empty(em->em_relids));
+
+ if (is_foreign_expr(root, rel, em->em_expr))
return em;
}
@@ -7455,7 +7459,9 @@ find_em_for_rel_target(PlannerInfo *root,
EquivalenceClass *ec,
{
Expr *expr = (Expr *) lfirst(lc1);
Index sgref = get_pathtarget_sortgroupref(target, i);
- ListCell *lc2;
+ Bitmapset *matching_ems;
+ Relids expr_relids;
+ int j;
/* Ignore non-sort expressions */
if (sgref == 0 ||
@@ -7470,19 +7476,22 @@ find_em_for_rel_target(PlannerInfo *root,
EquivalenceClass *ec,
while (expr && IsA(expr, RelabelType))
expr = ((RelabelType *) expr)->arg;
+ expr_relids = pull_varnos(root, (Node *) expr);
+ matching_ems = get_ecmember_indexes_strict(root, ec,
expr_relids,
+
false, false);
/* Locate an EquivalenceClass member matching this expr, if any
*/
- foreach(lc2, ec->ec_members)
+ j = -1;
+ while ((j = bms_next_member(matching_ems, j)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
+
root->eq_members, j);
Expr *em_expr;
- /* Don't match constants */
- if (em->em_is_const)
- continue;
+ /* don't expect constants */
+ Assert(!em->em_is_const);
- /* Ignore child members */
- if (em->em_is_child)
- continue;
+ /* don't expect child members */
+ Assert(!em->em_is_child);
/* Match if same expression (after stripping relabel) */
em_expr = em->em_expr;
@@ -7496,8 +7505,9 @@ find_em_for_rel_target(PlannerInfo *root,
EquivalenceClass *ec,
if (is_foreign_expr(root, rel, em->em_expr))
return em;
}
-
i++;
+ bms_free(expr_relids);
+ bms_free(matching_ems);
}
return NULL;
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index a96f2ee8c6..17a8c211c8 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -430,9 +430,11 @@ _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_member_indexes);
+ WRITE_BITMAPSET_FIELD(ec_nonchild_indexes);
+ WRITE_BITMAPSET_FIELD(ec_norel_indexes);
+ 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);
diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c
index a5c44adc6c..8eed1b22d1 100644
--- a/src/backend/nodes/print.c
+++ b/src/backend/nodes/print.c
@@ -423,16 +423,17 @@ print_expr(const Node *expr, const List *rtable)
* pathkeys list of PathKeys
*/
void
-print_pathkeys(const List *pathkeys, const List *rtable)
+print_pathkeys(const PlannerInfo *root, const List *pathkeys,
+ const List *rtable)
{
- const ListCell *i;
+ const ListCell *lc;
printf("(");
- foreach(i, pathkeys)
+ foreach(lc, pathkeys)
{
- PathKey *pathkey = (PathKey *) lfirst(i);
+ PathKey *pathkey = (PathKey *) lfirst(lc);
EquivalenceClass *eclass;
- ListCell *k;
+ int i;
bool first = true;
eclass = pathkey->pk_eclass;
@@ -441,9 +442,11 @@ print_pathkeys(const List *pathkeys, const List *rtable)
eclass = eclass->ec_merged;
printf("(");
- foreach(k, eclass->ec_members)
+ i = -1;
+ while ((i = bms_next_member(eclass->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *mem = (EquivalenceMember *)
lfirst(k);
+ EquivalenceMember *mem =
list_nth_node(EquivalenceMember,
+
root->eq_members, i);
if (first)
first = false;
@@ -452,7 +455,7 @@ print_pathkeys(const List *pathkeys, const List *rtable)
print_expr((Node *) mem->em_expr, rtable);
}
printf(")");
- if (lnext(pathkeys, i))
+ if (lnext(pathkeys, lc))
printf(", ");
}
printf(")\n");
diff --git a/src/backend/optimizer/path/allpaths.c
b/src/backend/optimizer/path/allpaths.c
index 8fc28007f5..9b6a5b08dc 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -4539,7 +4539,7 @@ print_path(PlannerInfo *root, Path *path, int indent)
for (i = 0; i < indent; i++)
printf("\t");
printf(" pathkeys: ");
- print_pathkeys(path->pathkeys, root->parse->rtable);
+ print_pathkeys(root, path->pathkeys, root->parse->rtable);
}
if (join)
diff --git a/src/backend/optimizer/path/costsize.c
b/src/backend/optimizer/path/costsize.c
index fb28e6411a..a8289ddde6 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1986,12 +1986,14 @@ compute_cpu_sort_cost(PlannerInfo *root, List
*pathkeys, int nPresortedKeys,
double nGroups,
correctedNGroups;
Cost funcCost = 1.0;
+ int first_em;
/*
* We believe that equivalence members aren't very different,
so, to
* estimate cost we consider just the first member.
*/
- em = (EquivalenceMember *)
linitial(pathkey->pk_eclass->ec_members);
+ first_em =
bms_next_member(pathkey->pk_eclass->ec_member_indexes, -1);
+ em = list_nth_node(EquivalenceMember, root->eq_members,
first_em);
if (em->em_datatype != InvalidOid)
{
@@ -2326,8 +2328,10 @@ cost_incremental_sort(Path *path,
foreach(l, pathkeys)
{
PathKey *key = (PathKey *) lfirst(l);
- EquivalenceMember *member = (EquivalenceMember *)
- linitial(key->pk_eclass->ec_members);
+ int first_em =
bms_next_member(key->pk_eclass->ec_member_indexes, -1);
+ EquivalenceMember *member = list_nth_node(EquivalenceMember,
+
root->eq_members,
+
first_em);
/*
* Check if the expression contains Var with "varno 0" so that
we
@@ -5821,7 +5825,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 7991295548..4e0a645c1a 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -31,9 +31,14 @@
#include "optimizer/restrictinfo.h"
#include "utils/lsyscache.h"
-
-static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
-
Expr *expr, Relids relids, Relids nullable_relids,
+static void add_eq_source(PlannerInfo *root, EquivalenceClass *ec,
+ RestrictInfo *rinfo);
+static void add_eq_derive(PlannerInfo *root, EquivalenceClass *ec,
+ RestrictInfo *rinfo);
+static EquivalenceMember *add_eq_member(PlannerInfo *root,
+
EquivalenceClass *ec,
+
Expr *expr, Relids relids,
+
Relids nullable_relids,
bool is_child, Oid datatype);
static bool is_exprlist_member(Expr *node, List *exprs);
static void generate_base_implied_equalities_const(PlannerInfo *root,
@@ -139,6 +144,7 @@ process_equivalence(PlannerInfo *root,
*em2;
ListCell *lc1;
int ec2_idx;
+ int i;
/* Should not already be marked as having generated an eclass */
Assert(restrictinfo->left_ec == NULL);
@@ -265,7 +271,6 @@ process_equivalence(PlannerInfo *root,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
- ListCell *lc2;
/* Never match to a volatile EC */
if (cur_ec->ec_has_volatile)
@@ -286,9 +291,11 @@ process_equivalence(PlannerInfo *root,
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em =
list_nth_node(EquivalenceMember,
+
root->eq_members, i);
Assert(!cur_em->em_is_child); /* no children yet */
@@ -333,7 +340,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_below_outer_join |= below_outer_join;
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
@@ -345,6 +351,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;
}
@@ -364,9 +372,16 @@ process_equivalence(PlannerInfo *root,
* PathKeys. We leave it behind with a link so that the merged
EC can
* 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_member_indexes = bms_add_members(ec1->ec_member_indexes,
+
ec2->ec_member_indexes);
+ ec1->ec_nonchild_indexes =
bms_add_members(ec1->ec_nonchild_indexes,
+
ec2->ec_nonchild_indexes);
+ ec1->ec_norel_indexes = bms_add_members(ec1->ec_norel_indexes,
+
ec2->ec_norel_indexes);
+ 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 */
@@ -378,11 +393,12 @@ process_equivalence(PlannerInfo *root,
ec2->ec_merged = ec1;
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_member_indexes = NULL;
+ ec2->ec_nonchild_indexes = NULL;
+ ec2->ec_norel_indexes = NULL;
+ ec2->ec_source_indexes = NULL;
+ ec2->ec_derive_indexes = NULL;
ec2->ec_relids = NULL;
- ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_below_outer_join |= below_outer_join;
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
@@ -394,13 +410,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,
item2_nullable_relids,
- false, item2_type);
- ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
+ em2 = add_eq_member(root, ec1, item2, item2_relids,
+ item2_nullable_relids,
false, item2_type);
ec1->ec_below_outer_join |= below_outer_join;
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
@@ -412,13 +429,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,
item1_nullable_relids,
- false, item1_type);
- ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
+ em1 = add_eq_member(root, ec2, item1, item1_relids,
+ item1_nullable_relids,
false, item1_type);
ec2->ec_below_outer_join |= below_outer_join;
ec2->ec_min_security = Min(ec2->ec_min_security,
restrictinfo->security_level);
@@ -430,6 +448,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
{
@@ -438,9 +458,11 @@ 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_member_indexes = NULL;
+ ec->ec_nonchild_indexes = NULL;
+ ec->ec_norel_indexes = NULL;
+ ec->ec_source_indexes = NULL;
+ ec->ec_derive_indexes = NULL;
ec->ec_relids = NULL;
ec->ec_has_const = false;
ec->ec_has_volatile = false;
@@ -450,10 +472,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,
item1_nullable_relids,
- false, item1_type);
- em2 = add_eq_member(ec, item2, item2_relids,
item2_nullable_relids,
- false, item2_type);
+ em1 = add_eq_member(root, ec, item1, item1_relids,
+ item1_nullable_relids,
false, item1_type);
+ em2 = add_eq_member(root, ec, item2, item2_relids,
+ item2_nullable_relids,
false, item2_type);
root->eq_classes = lappend(root->eq_classes, ec);
@@ -463,6 +485,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;
@@ -538,14 +562,61 @@ canonicalize_ec_expression(Expr *expr, Oid req_type, Oid
req_collation)
return expr;
}
+/*
+ * 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);
+
+ i = -1;
+ while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ rel->eclass_source_indexes =
bms_add_member(rel->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);
+
+ i = -1;
+ while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ rel->eclass_derive_indexes =
bms_add_member(rel->eclass_derive_indexes,
+
derive_idx);
+ }
+}
/*
* add_eq_member - build a new EquivalenceMember and add it to an EC
*/
static EquivalenceMember *
-add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
- Relids nullable_relids, bool is_child, Oid datatype)
+add_eq_member(PlannerInfo *root, EquivalenceClass *ec, Expr *expr,
+ Relids relids, Relids nullable_relids, bool is_child,
+ Oid datatype)
{
EquivalenceMember *em = makeNode(EquivalenceMember);
+ Relids expr_relids;
+ int em_index =
list_length(root->eq_members);
+ int i;
em->em_expr = expr;
em->em_relids = relids;
@@ -554,6 +625,20 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids
relids,
em->em_is_child = is_child;
em->em_datatype = datatype;
+ /*
+ * We must determine the exact set of relids in the expr for child
+ * EquivalenceMembers as what is given to us in 'relids' may differ from
+ * the relids mentioned in the expression. See
add_child_rel_equivalences
+ */
+ if (is_child)
+ expr_relids = pull_varnos(root, (Node *) expr);
+ else
+ {
+ expr_relids = relids;
+ /* We expect the relids to match for non-child members */
+ Assert(bms_equal(pull_varnos(root, (Node *) expr), relids));
+ }
+
if (bms_is_empty(relids))
{
/*
@@ -572,8 +657,25 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids
relids,
else if (!is_child) /* child members don't add to
ec_relids */
{
ec->ec_relids = bms_add_members(ec->ec_relids, relids);
+ ec->ec_nonchild_indexes =
bms_add_member(ec->ec_nonchild_indexes, em_index);
+ }
+ ec->ec_member_indexes = bms_add_member(ec->ec_member_indexes, em_index);
+ root->eq_members = lappend(root->eq_members, em);
+
+ /* record exprs with no relids */
+ if (bms_is_empty(expr_relids))
+ ec->ec_norel_indexes = bms_add_member(ec->ec_norel_indexes,
em_index);
+
+ if (is_child)
+ expr_relids = bms_add_members(expr_relids, relids);
+
+ i = -1;
+ while ((i = bms_next_member(expr_relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ rel->eclass_member_indexes =
bms_add_member(rel->eclass_member_indexes, em_index);
}
- ec->ec_members = lappend(ec->ec_members, em);
return em;
}
@@ -638,6 +740,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
* Ensure the expression exposes the correct type and collation.
*/
expr = canonicalize_ec_expression(expr, opcintype, collation);
+ expr_relids = pull_varnos(root, (Node *) expr);
/*
* Scan through the existing EquivalenceClasses for a match
@@ -645,7 +748,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
- ListCell *lc2;
+ Bitmapset *matching_ems;
+ int i;
/*
* Never match to a volatile EC, except when we are looking at
another
@@ -660,9 +764,14 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
- foreach(lc2, cur_ec->ec_members)
+ matching_ems = get_ecmember_indexes_strict(root, cur_ec,
expr_relids,
+
true, true);
+
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em =
list_nth_node(EquivalenceMember,
+
root->eq_members, i);
/*
* Ignore child members unless they match the request.
@@ -710,9 +819,11 @@ get_eclass_for_sort_expr(PlannerInfo *root,
newec = makeNode(EquivalenceClass);
newec->ec_opfamilies = list_copy(opfamilies);
newec->ec_collation = collation;
- newec->ec_members = NIL;
- newec->ec_sources = NIL;
- newec->ec_derives = NIL;
+ newec->ec_member_indexes = NULL;
+ newec->ec_nonchild_indexes = NULL;
+ newec->ec_norel_indexes = NULL;
+ 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);
@@ -729,10 +840,9 @@ get_eclass_for_sort_expr(PlannerInfo *root,
/*
* Get the precise set of nullable relids appearing in the expression.
*/
- expr_relids = pull_varnos(root, (Node *) expr);
nullable_relids = bms_intersect(nullable_relids, expr_relids);
- newem = add_eq_member(newec, copyObject(expr), expr_relids,
+ newem = add_eq_member(root, newec, copyObject(expr), expr_relids,
nullable_relids, false,
opcintype);
/*
@@ -764,7 +874,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
int ec_index =
list_length(root->eq_classes) - 1;
int i = -1;
- while ((i = bms_next_member(newec->ec_relids, i)) > 0)
+ while ((i = bms_next_member(newec->ec_relids, i)) >= 0)
{
RelOptInfo *rel = root->simple_rel_array[i];
@@ -794,19 +904,27 @@ 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;
+ Bitmapset *matching_ems;
+ Relids expr_relids;
+ int i;
/* We ignore binary-compatible relabeling on both ends */
while (expr && IsA(expr, RelabelType))
expr = ((RelabelType *) expr)->arg;
- foreach(lc, ec->ec_members)
+ expr_relids = pull_varnos(root, (Node *) expr);
+ matching_ems = get_ecmember_indexes_strict(root, ec, expr_relids, true,
true);
+
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
+
root->eq_members, i);
Expr *emexpr;
/*
@@ -865,11 +983,12 @@ find_computable_ec_member(PlannerInfo *root,
Relids relids,
bool require_parallel_safe)
{
- ListCell *lc;
+ int i = -1;
- foreach(lc, ec->ec_members)
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
+
root->eq_members, i);
List *exprvars;
ListCell *lc2;
@@ -976,7 +1095,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;
@@ -1063,7 +1182,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
@@ -1096,7 +1215,7 @@ generate_base_implied_equalities(PlannerInfo *root)
* Single-member ECs won't generate any deductions, either here
or at
* the join level.
*/
- if (list_length(ec->ec_members) > 1)
+ if (bms_membership(ec->ec_member_indexes) == BMS_MULTIPLE)
{
if (ec->ec_has_const)
generate_base_implied_equalities_const(root,
ec);
@@ -1120,7 +1239,7 @@ generate_base_implied_equalities(PlannerInfo *root)
* this is a cheap version of has_relevant_eclass_joinclause().
*/
i = -1;
- while ((i = bms_next_member(ec->ec_relids, i)) > 0)
+ while ((i = bms_next_member(ec->ec_relids, i)) >= 0)
{
RelOptInfo *rel = root->simple_rel_array[i];
@@ -1145,7 +1264,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
EquivalenceClass *ec)
{
EquivalenceMember *const_em = NULL;
- ListCell *lc;
+ int i;
/*
* In the trivial case where we just had one "var = const" clause, push
@@ -1154,10 +1273,10 @@ generate_base_implied_equalities_const(PlannerInfo
*root,
* re-build and re-analyze an equality clause that will be exactly
* equivalent to the old one.
*/
- if (list_length(ec->ec_members) == 2 &&
- list_length(ec->ec_sources) == 1)
+ if (bms_num_members(ec->ec_member_indexes) == 2 &&
+ 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);
if (bms_membership(restrictinfo->required_relids) !=
BMS_MULTIPLE)
{
@@ -1172,9 +1291,11 @@ generate_base_implied_equalities_const(PlannerInfo *root,
* machinery might be able to exclude relations on the basis of
generated
* "var = const" equalities, but "var = param" won't work for that.
*/
- foreach(lc, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_norel_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+
root->eq_members, i);
if (cur_em->em_is_const)
{
@@ -1186,9 +1307,11 @@ generate_base_implied_equalities_const(PlannerInfo *root,
Assert(const_em != NULL);
/* Generate a derived equality against each other member */
- foreach(lc, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+
root->eq_members, i);
Oid eq_op;
RestrictInfo *rinfo;
@@ -1215,9 +1338,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.)
*/
@@ -1227,7 +1350,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);
}
}
}
@@ -1240,7 +1364,8 @@ generate_base_implied_equalities_no_const(PlannerInfo
*root,
EquivalenceClass *ec)
{
EquivalenceMember **prev_ems;
- ListCell *lc;
+ Bitmapset *matching_ems;
+ int i;
/*
* We scan the EC members once and track the last-seen member for each
@@ -1253,9 +1378,12 @@ generate_base_implied_equalities_no_const(PlannerInfo
*root,
prev_ems = (EquivalenceMember **)
palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember
*));
- foreach(lc, ec->ec_members)
+ matching_ems = bms_difference(ec->ec_member_indexes,
ec->ec_norel_indexes);
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+
root->eq_members, i);
int relid;
Assert(!cur_em->em_is_child); /* no children yet */
@@ -1290,7 +1418,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.
*/
@@ -1313,11 +1441,15 @@ generate_base_implied_equalities_no_const(PlannerInfo
*root,
* For the moment we force all the Vars to be available at all join
nodes
* for this eclass. Perhaps this could be improved by doing some
* pre-analysis of which members we prefer to join, but it's no worse
than
- * what happened in the pre-8.3 code.
+ * what happened in the pre-8.3 code. We're able to make use of
+ * matching_ems from above. We're not going to find Vars in
+ * em_const_indexes.
*/
- foreach(lc, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+
root->eq_members, i);
List *vars = pull_var_clause((Node *) cur_em->em_expr,
PVC_RECURSE_AGGREGATES |
PVC_RECURSE_WINDOWFUNCS |
@@ -1326,6 +1458,7 @@ generate_base_implied_equalities_no_const(PlannerInfo
*root,
add_vars_to_targetlist(root, vars, ec->ec_relids, false);
list_free(vars);
}
+ bms_free(matching_ems);
}
/*
@@ -1346,11 +1479,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)
@@ -1391,9 +1525,9 @@ 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 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.
*
* join_relids should always equal bms_union(outer_relids, inner_rel->relids).
* We could simplify this function's API by computing it internally, but in
@@ -1445,7 +1579,7 @@ generate_join_implied_equalities(PlannerInfo *root,
continue;
/* Single-member ECs won't generate any deductions */
- if (list_length(ec->ec_members) <= 1)
+ if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
continue;
/* Sanity check that this eclass overlaps the join */
@@ -1516,7 +1650,7 @@ generate_join_implied_equalities_for_ecs(PlannerInfo
*root,
continue;
/* Single-member ECs won't generate any deductions */
- if (list_length(ec->ec_members) <= 1)
+ if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
continue;
/* We can quickly ignore any that don't overlap the join, too */
@@ -1559,7 +1693,9 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
List *new_members = NIL;
List *outer_members = NIL;
List *inner_members = NIL;
+ Bitmapset *matching_ems;
ListCell *lc1;
+ int i;
/*
* First, scan the EC to identify member values that are computable at
the
@@ -1570,9 +1706,13 @@ generate_join_implied_equalities_normal(PlannerInfo
*root,
* 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.
*/
- foreach(lc1, ec->ec_members)
+ matching_ems = get_ecmember_indexes(root, ec, join_relids, true, false);
+
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+ EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+
root->eq_members, i);
/*
* We don't need to check explicitly for child EC members.
This test
@@ -1732,12 +1872,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) &&
@@ -1749,12 +1893,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)
@@ -1815,9 +1959,10 @@ create_join_clause(PlannerInfo *root,
EquivalenceMember *rightem,
EquivalenceClass *parent_ec)
{
+ Bitmapset *matches;
RestrictInfo *rinfo;
- ListCell *lc;
MemoryContext oldcontext;
+ int i;
/*
* Search to see if we already built a RestrictInfo for this pair of
@@ -1825,9 +1970,12 @@ create_join_clause(PlannerInfo *root,
* previously-derived clauses. The check on opno is probably redundant,
* but be safe ...
*/
- 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 &&
@@ -1835,9 +1983,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 &&
@@ -1876,7 +2028,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);
@@ -2068,7 +2220,8 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
left_type,
right_type,
inner_datatype;
- Relids inner_relids,
+ Relids outer_relids,
+ inner_relids,
inner_nullable_relids;
ListCell *lc1;
@@ -2087,6 +2240,7 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
outervar = (Expr *) get_leftop(rinfo->clause);
innervar = (Expr *) get_rightop(rinfo->clause);
inner_datatype = right_type;
+ outer_relids = rinfo->left_relids;
inner_relids = rinfo->right_relids;
}
else
@@ -2094,6 +2248,7 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
outervar = (Expr *) get_rightop(rinfo->clause);
innervar = (Expr *) get_leftop(rinfo->clause);
inner_datatype = left_type;
+ outer_relids = rinfo->right_relids;
inner_relids = rinfo->left_relids;
}
inner_nullable_relids = bms_intersect(inner_relids,
@@ -2103,8 +2258,9 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
+ Bitmapset *matching_ems;
bool match;
- ListCell *lc2;
+ int i;
/* Ignore EC unless it contains pseudoconstants */
if (!cur_ec->ec_has_const)
@@ -2119,9 +2275,14 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
continue;
/* Does it contain a match to outervar? */
match = false;
- foreach(lc2, cur_ec->ec_members)
+ matching_ems = get_ecmember_indexes_strict(root, cur_ec,
+
outer_relids,
+
false, true);
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em =
list_nth_node(EquivalenceMember,
+
root->eq_members, i);
Assert(!cur_em->em_is_child); /* no children yet */
if (equal(outervar, cur_em->em_expr))
@@ -2139,9 +2300,11 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
* constant before we can decide to throw away the outer-join
clause.
*/
match = false;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_norel_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em =
list_nth_node(EquivalenceMember,
+
root->eq_members, i);
Oid eq_op;
RestrictInfo *newrinfo;
@@ -2220,11 +2383,12 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
EquivalenceMember *coal_em = NULL;
+ Bitmapset *matching_ems;
bool match;
bool matchleft;
bool matchright;
- ListCell *lc2;
int coal_idx = -1;
+ int i;
/* Ignore EC unless it contains pseudoconstants */
if (!cur_ec->ec_has_const)
@@ -2251,10 +2415,14 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
* the two column types). Is it OK to strip implicit coercions
from
* the COALESCE arguments?
*/
+ matching_ems = get_ecmember_indexes_strict(root, cur_ec,
+
rinfo->clause_relids, true,
+
false);
match = false;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- coal_em = (EquivalenceMember *) lfirst(lc2);
+ coal_em = list_nth_node(EquivalenceMember,
root->eq_members, i);
Assert(!coal_em->em_is_child); /* no children yet */
if (IsA(coal_em->em_expr, CoalesceExpr))
{
@@ -2269,7 +2437,7 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
if (equal(leftvar, cfirst) && equal(rightvar,
csecond))
{
- coal_idx = foreach_current_index(lc2);
+ coal_idx = i;
match = true;
break;
}
@@ -2285,9 +2453,11 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
* decide to throw away the outer-join clause.
*/
matchleft = matchright = false;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_norel_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em =
list_nth_node(EquivalenceMember,
+
root->eq_members, i);
Oid eq_op;
RestrictInfo *newrinfo;
@@ -2332,11 +2502,25 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
* we can throw away the full-join clause as redundant.
Moreover, we
* can remove the COALESCE entry from the EC, since the added
* restrictions ensure it will always have the expected value.
(We
- * don't bother trying to update ec_relids or ec_sources.)
+ * don't bother trying to update ec_relids or root's
eq_sources.)
*/
if (matchleft && matchright)
{
- cur_ec->ec_members =
list_delete_nth_cell(cur_ec->ec_members, coal_idx);
+ cur_ec->ec_member_indexes =
bms_del_member(cur_ec->ec_member_indexes,
+
coal_idx);
+ cur_ec->ec_nonchild_indexes =
bms_del_member(cur_ec->ec_nonchild_indexes,
+
coal_idx);
+ /* no need to adjust ec_norel_indexes */
+
+ /* Remove the member from each of the relations */
+ i = -1;
+ while ((i = bms_next_member(coal_em->em_relids, i)) >=
0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+ rel->eclass_member_indexes =
bms_del_member(rel->eclass_member_indexes,
+
coal_idx);
+ }
+
return true;
}
@@ -2368,21 +2552,28 @@ bool
exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
{
ListCell *lc1;
+ Relids item1_relids = pull_varnos(root, item1);
+ Relids item2_relids = pull_varnos(root, item2);
foreach(lc1, root->eq_classes)
{
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
bool item1member = false;
bool item2member = false;
- ListCell *lc2;
+ Bitmapset *matching_ems;
+ int i;
/* Never match to a volatile EC */
if (ec->ec_has_volatile)
continue;
- foreach(lc2, ec->ec_members)
+ matching_ems = bms_join(get_ecmember_indexes_strict(root, ec,
item1_relids, false, true),
+
get_ecmember_indexes_strict(root, ec, item2_relids, false, true));
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
+
root->eq_members, i);
if (em->em_is_child)
continue; /* ignore children here
*/
@@ -2445,16 +2636,21 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
i);
EquivalenceMember *item1_em = NULL;
EquivalenceMember *item2_em = NULL;
- ListCell *lc2;
+ Bitmapset *matching_ems;
+ int j;
/* Never match to a volatile EC */
if (ec->ec_has_volatile)
continue;
/* Note: it seems okay to match to "broken" eclasses here */
+ matching_ems = bms_join(get_ecmember_indexes_strict(root, ec,
rel1->relids, false, false),
+
get_ecmember_indexes_strict(root, ec, rel2->relids, false, false));
- foreach(lc2, ec->ec_members)
+ j = -1;
+ while ((j = bms_next_member(matching_ems, j)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
+
root->eq_members, j);
Var *var;
if (em->em_is_child)
@@ -2507,16 +2703,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
@@ -2567,7 +2766,8 @@ 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;
+ Bitmapset *matching_ems;
+ int j;
/*
* If this EC contains a volatile expression, then generating
child
@@ -2581,33 +2781,21 @@ add_child_rel_equivalences(PlannerInfo *root,
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.
+ * Looping over matching_ems means we only loop over existing
members,
+ * not any newly added ones.
*/
- num_members = list_length(cur_ec->ec_members);
- for (int pos = 0; pos < num_members; pos++)
- {
- EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(cur_ec->ec_members, pos);
+ matching_ems = get_ecmember_indexes(root, cur_ec,
top_parent_relids, false, false);
- if (cur_em->em_is_const)
- continue; /* ignore consts here */
+ j = -1;
+ while ((j = bms_next_member(matching_ems, j)) >= 0)
+ {
+ EquivalenceMember *cur_em =
list_nth_node(EquivalenceMember, root->eq_members, j);
- /*
- * We consider only original EC members here, not
- * already-transformed child members. Otherwise, if
some original
- * member expression references more than one
appendrel, we'd get
- * an O(N^2) explosion of useless derived expressions
for
- * 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
*/
+ Assert(!cur_em->em_is_const);
+ Assert(!cur_em->em_is_child);
+ Assert(bms_overlap(cur_em->em_relids,
top_parent_relids));
- /* Does this member reference child's topmost parent
rel? */
- if (bms_overlap(cur_em->em_relids, top_parent_relids))
- {
- /* Yes, generate transformed child version */
+ { /* XXX fix indentation */
Expr *child_expr;
Relids new_relids;
Relids new_nullable_relids;
@@ -2653,7 +2841,7 @@ add_child_rel_equivalences(PlannerInfo *root,
child_relids);
}
- (void) add_eq_member(cur_ec, child_expr,
+ (void) add_eq_member(root, cur_ec, child_expr,
new_relids, new_nullable_relids,
true,
cur_em->em_datatype);
@@ -2705,7 +2893,8 @@ 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;
+ Bitmapset *matching_ems;
+ int j;
/*
* If this EC contains a volatile expression, then generating
child
@@ -2719,24 +2908,19 @@ add_child_join_rel_equivalences(PlannerInfo *root,
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.
+ * Looping over matching_ems means we only loop over existing
members,
+ * not any newly added ones.
*/
- num_members = list_length(cur_ec->ec_members);
- for (int pos = 0; pos < num_members; pos++)
- {
- EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(cur_ec->ec_members, pos);
+ matching_ems = get_ecmember_indexes(root, cur_ec,
top_parent_relids, false, false);
- if (cur_em->em_is_const)
- continue; /* ignore consts here */
+ j = -1;
+ while ((j = bms_next_member(matching_ems, j)) >= 0)
+ {
+ EquivalenceMember *cur_em =
list_nth_node(EquivalenceMember, root->eq_members, j);
- /*
- * We consider only original EC members here, not
- * already-transformed child members.
- */
- if (cur_em->em_is_child)
- continue; /* ignore children here
*/
+ Assert(!cur_em->em_is_const);
+ Assert(!cur_em->em_is_child);
+ Assert(bms_overlap(cur_em->em_relids,
top_parent_relids));
/*
* We may ignore expressions that reference a single
baserel,
@@ -2745,10 +2929,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
continue;
- /* Does this member reference child's topmost parent
rel? */
- if (bms_overlap(cur_em->em_relids, top_parent_relids))
- {
- /* Yes, generate transformed child version */
+ { /* XXX fix indentation */
Expr *child_expr;
Relids new_relids;
Relids new_nullable_relids;
@@ -2794,7 +2975,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
child_relids,
top_parent_relids);
- (void) add_eq_member(cur_ec, child_expr,
+ (void) add_eq_member(root, cur_ec, child_expr,
new_relids, new_nullable_relids,
true,
cur_em->em_datatype);
}
@@ -2857,7 +3038,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
{
EquivalenceClass *cur_ec = (EquivalenceClass *)
list_nth(root->eq_classes, i);
EquivalenceMember *cur_em;
- ListCell *lc2;
+ Bitmapset *matching_ems;
+ int j;
/* Sanity check eclass_indexes only contain ECs for rel */
Assert(is_child_rel || bms_is_subset(rel->relids,
cur_ec->ec_relids));
@@ -2866,7 +3048,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
* Won't generate joinclauses if const or single-member (the
latter
* test covers the volatile case too)
*/
- if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <=
1)
+ if (cur_ec->ec_has_const ||
+ bms_membership(cur_ec->ec_member_indexes) !=
BMS_MULTIPLE)
continue;
/*
@@ -2879,10 +3062,13 @@ generate_implied_equalities_for_column(PlannerInfo
*root,
* corner cases, so for now we live with just reporting the
first
* match. See also get_eclass_for_sort_expr.)
*/
+ matching_ems = get_ecmember_indexes(root, cur_ec, rel->relids,
true, false);
cur_em = NULL;
- foreach(lc2, cur_ec->ec_members)
+ j = -1;
+ while ((j = bms_next_member(matching_ems, j)) >= 0)
{
- cur_em = (EquivalenceMember *) lfirst(lc2);
+ cur_em = list_nth_node(EquivalenceMember,
root->eq_members, j);
+
if (bms_equal(cur_em->em_relids, rel->relids) &&
callback(root, rel, cur_ec, cur_em,
callback_arg))
break;
@@ -2896,14 +3082,15 @@ generate_implied_equalities_for_column(PlannerInfo
*root,
* Found our match. Scan the other EC members and attempt to
generate
* joinclauses.
*/
- foreach(lc2, cur_ec->ec_members)
+ j = -1;
+ while ((j = bms_next_member(cur_ec->ec_nonchild_indexes, j)) >=
0)
{
- EquivalenceMember *other_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *other_em =
list_nth_node(EquivalenceMember,
+
root->eq_members, j);
Oid eq_op;
RestrictInfo *rinfo;
- if (other_em->em_is_child)
- continue; /* ignore children here
*/
+ Assert(!other_em->em_is_child);
/* Make sure it'll be a join to a different rel */
if (other_em == cur_em ||
@@ -2986,7 +3173,7 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
* Won't generate joinclauses if single-member (this test
covers the
* volatile case too)
*/
- if (list_length(ec->ec_members) <= 1)
+ if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
continue;
/*
@@ -3000,7 +3187,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
@@ -3044,7 +3231,7 @@ has_relevant_eclass_joinclause(PlannerInfo *root,
RelOptInfo *rel1)
* Won't generate joinclauses if single-member (this test
covers the
* volatile case too)
*/
- if (list_length(ec->ec_members) <= 1)
+ if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
continue;
/*
@@ -3074,8 +3261,8 @@ eclass_useful_for_merging(PlannerInfo *root,
EquivalenceClass *eclass,
RelOptInfo *rel)
{
+ Bitmapset *matching_ems;
Relids relids;
- ListCell *lc;
Assert(!eclass->ec_merged);
@@ -3083,12 +3270,13 @@ eclass_useful_for_merging(PlannerInfo *root,
* Won't generate joinclauses if const or single-member (the latter test
* covers the volatile case too)
*/
- if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
+ if (eclass->ec_has_const ||
+ bms_membership(eclass->ec_member_indexes) != BMS_MULTIPLE)
return false;
/*
* 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.
*/
@@ -3105,17 +3293,15 @@ eclass_useful_for_merging(PlannerInfo *root,
if (bms_is_subset(eclass->ec_relids, relids))
return false;
- /* To join, we need a member not in the given rel */
- foreach(lc, eclass->ec_members)
- {
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
-
- if (cur_em->em_is_child)
- continue; /* ignore children here
*/
+ /* Find the EquivalenceMember for relids */
+ matching_ems = get_ecmember_indexes(root, eclass, relids, false, false);
- if (!bms_overlap(cur_em->em_relids, relids))
- return true;
- }
+ /*
+ * If there are any other non-child members besides matching_ems then we
+ * have a chance at merging.
+ */
+ if (bms_nonempty_difference(eclass->ec_nonchild_indexes, matching_ems))
+ return true;
return false;
}
@@ -3199,7 +3385,7 @@ get_eclass_indexes_for_relids(PlannerInfo *root, Relids
relids)
/* Should be OK to rely on eclass_indexes */
Assert(root->ec_merging_done);
- while ((i = bms_next_member(relids, i)) > 0)
+ while ((i = bms_next_member(relids, i)) >= 0)
{
RelOptInfo *rel = root->simple_rel_array[i];
@@ -3235,3 +3421,282 @@ 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_ecmember_indexes
+ * Returns a Bitmapset with indexes into root->eq_members for all
+ * EquivalenceMembers in 'ec' that have
+ * bms_overlap(em->em_relids, relids) as true. The returned
indexes
+ * may reference EquivalenceMembers with em_relids containing
members
+ * not mentioned in 'relids'.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ecmember_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids,
+ bool with_children, bool
with_norel_members)
+{
+ Bitmapset *matching_ems;
+ Bitmapset *rel_ems = NULL;
+ int i;
+
+ if (!with_children)
+ matching_ems = bms_copy(ec->ec_nonchild_indexes);
+ else
+ matching_ems = bms_copy(ec->ec_member_indexes);
+
+ i = -1;
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ rel_ems = bms_add_members(rel_ems, rel->eclass_member_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* XXX should we keep this? */
+ i = -1;
+ while ((i = bms_next_member(rel_ems, i)) >= 0)
+ {
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
root->eq_members, i);
+
+ Assert(bms_overlap(em->em_relids, relids));
+ }
+#endif
+
+ /* remove EC members not mentioning the required rels */
+ matching_ems = bms_int_members(matching_ems, rel_ems);
+
+ /* now add any members with that are not mentioned by any relation */
+ if (with_norel_members)
+ matching_ems = bms_add_members(matching_ems,
ec->ec_norel_indexes);
+
+ return matching_ems;
+}
+
+/*
+ * get_ecmember_indexes_strict
+ * Returns a Bitmapset with indexes into root->eq_members for all
+ * EquivalenceMembers in 'ec' that have
+ * bms_is_subset(relids, em->em_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ecmember_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
+ Relids relids, bool
with_children,
+ bool with_norel_members)
+{
+ Bitmapset *matching_ems;
+ int i;
+
+ if (!with_children)
+ matching_ems = bms_copy(ec->ec_nonchild_indexes);
+ else
+ matching_ems = bms_copy(ec->ec_member_indexes);
+
+ i = -1;
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_ems = bms_int_members(matching_ems,
rel->eclass_member_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* XXX should we keep this? */
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
+ {
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
root->eq_members, i);
+
+ Assert(bms_is_subset(relids, em->em_relids));
+ }
+#endif
+
+ /* now add any members with that are not mentioned by any relation */
+ if (with_norel_members)
+ matching_ems = bms_add_members(matching_ems,
ec->ec_norel_indexes);
+
+ return matching_ems;
+}
+
+/*
+ * 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 *matching_es = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_es = bms_copy(rel->eclass_source_indexes);
+ }
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_es = bms_add_members(matching_es,
rel->eclass_source_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* XXX should we keep this? */
+ i = -1;
+ while ((i = bms_next_member(matching_es, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo,
root->eq_sources, i);
+
+ Assert(bms_overlap(relids, rinfo->clause_relids));
+ }
+#endif
+
+ /* leave only the sources belonging to this EquivalenceClass */
+ matching_es = bms_int_members(matching_es, ec->ec_source_indexes);
+
+ return matching_es;
+}
+
+/*
+ * 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 *matching_es = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_es = bms_copy(rel->eclass_source_indexes);
+ }
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_es = bms_int_members(matching_es,
rel->eclass_source_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* XXX should we keep this? */
+ i = -1;
+ while ((i = bms_next_member(matching_es, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo,
root->eq_sources, i);
+
+ Assert(bms_is_subset(relids, rinfo->clause_relids));
+ }
+#endif
+
+ /* leave only the sources belonging to this EquivalenceClass */
+ matching_es = bms_int_members(matching_es, ec->ec_source_indexes);
+
+ return matching_es;
+}
+
+/*
+ * 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.
+ */
+Bitmapset *
+get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+{
+ Bitmapset *matching_eds = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_eds = bms_copy(rel->eclass_derive_indexes);
+ }
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_eds = bms_add_members(matching_eds,
rel->eclass_derive_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* XXX should we keep this? */
+ i = -1;
+ while ((i = bms_next_member(matching_eds, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo,
root->eq_derives, i);
+
+ Assert(bms_overlap(relids, rinfo->clause_relids));
+ }
+#endif
+
+ /* leave only the derives belonging to this EquivalenceClass */
+ matching_eds = bms_int_members(matching_eds, ec->ec_derive_indexes);
+
+ return matching_eds;
+}
+
+/*
+ * 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 *matching_eds = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_eds = bms_copy(rel->eclass_derive_indexes);
+ }
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ matching_eds = bms_int_members(matching_eds,
rel->eclass_derive_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* XXX should we keep this? */
+ i = -1;
+ while ((i = bms_next_member(matching_eds, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo,
root->eq_derives, i);
+
+ Assert(bms_is_subset(relids, rinfo->clause_relids));
+ }
+#endif
+
+ /* leave only the derives belonging to this EquivalenceClass */
+ matching_eds = bms_int_members(matching_eds, ec->ec_derive_indexes);
+
+ return matching_eds;
+}
diff --git a/src/backend/optimizer/path/indxpath.c
b/src/backend/optimizer/path/indxpath.c
index 7d176e7b00..65d4ceccfd 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -184,8 +184,8 @@ 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,
- List
**orderby_clauses_p,
+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,
int indexcol, Expr *clause, Oid pk_opfamily);
@@ -998,7 +998,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
else if (index->amcanorderbyop && pathkeys_possibly_useful)
{
/* see if we can generate ordering operators for query_pathkeys
*/
- match_pathkeys_to_index(index, root->query_pathkeys,
+ match_pathkeys_to_index(root, index, root->query_pathkeys,
&orderbyclauses,
&orderbyclausecols);
if (orderbyclauses)
@@ -3073,8 +3073,8 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* one-to-one with the requested pathkeys.
*/
static void
-match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
- List **orderby_clauses_p,
+match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index,
+ List *pathkeys, List
**orderby_clauses_p,
List **clause_columns_p)
{
List *orderby_clauses = NIL;
@@ -3091,8 +3091,9 @@ match_pathkeys_to_index(IndexOptInfo *index, List
*pathkeys,
foreach(lc1, pathkeys)
{
PathKey *pathkey = (PathKey *) lfirst(lc1);
+ Bitmapset *matching_ems;
bool found = false;
- ListCell *lc2;
+ int i;
/*
* Note: for any failure to match, we just return NIL
immediately.
@@ -3116,9 +3117,14 @@ match_pathkeys_to_index(IndexOptInfo *index, List
*pathkeys,
* be considered to match more than one pathkey list, which is
OK
* here. See also get_eclass_for_sort_expr.)
*/
- foreach(lc2, pathkey->pk_eclass->ec_members)
+ matching_ems =
bms_intersect(pathkey->pk_eclass->ec_member_indexes,
+
index->rel->eclass_member_indexes);
+
+ i = -1;
+ while ((i = bms_next_member(matching_ems, i)) >= 0)
{
- EquivalenceMember *member = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *member =
list_nth_node(EquivalenceMember,
+
root->eq_members, i);
int indexcol;
/* No possibility of match if it references other
relations */
diff --git a/src/backend/optimizer/path/pathkeys.c
b/src/backend/optimizer/path/pathkeys.c
index 1fa7fc99b5..d1f68ecf64 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1431,9 +1431,13 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo
*rel,
/* We can represent this sub_pathkey */
EquivalenceMember *sub_member;
EquivalenceClass *outer_ec;
+ int first_em;
- Assert(list_length(sub_eclass->ec_members) ==
1);
- sub_member = (EquivalenceMember *)
linitial(sub_eclass->ec_members);
+
Assert(bms_membership(sub_eclass->ec_member_indexes) == BMS_SINGLETON);
+ first_em =
bms_next_member(sub_eclass->ec_member_indexes, -1);
+ sub_member = list_nth_node(EquivalenceMember,
+
rel->subroot->eq_members,
+
first_em);
/*
* Note: it might look funny to be setting
sortref = 0 for a
@@ -1488,18 +1492,19 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo
*rel,
* outer query.
*/
int best_score = -1;
- ListCell *j;
+ int j = -1;
- foreach(j, sub_eclass->ec_members)
+ while ((j =
bms_next_member(sub_eclass->ec_nonchild_indexes, j)) >= 0)
{
- EquivalenceMember *sub_member =
(EquivalenceMember *) lfirst(j);
+ EquivalenceMember *sub_member =
list_nth_node(EquivalenceMember,
+
rel->subroot->eq_members,
+
j);
Expr *sub_expr = sub_member->em_expr;
Oid sub_expr_type =
sub_member->em_datatype;
Oid sub_expr_coll =
sub_eclass->ec_collation;
ListCell *k;
- if (sub_member->em_is_child)
- continue; /* ignore children here
*/
+ Assert(!sub_member->em_is_child);
foreach(k, subquery_tlist)
{
@@ -1551,7 +1556,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo
*rel,
sub_pathkey->pk_strategy,
sub_pathkey->pk_nulls_first);
/* score = # of equivalence peers */
- score =
list_length(outer_ec->ec_members) - 1;
+ score =
bms_num_members(outer_ec->ec_member_indexes) - 1;
/* +1 if it matches the proper
query_pathkeys item */
if (retvallen < outer_query_keys &&
list_nth(root->query_pathkeys,
retvallen) == outer_pk)
@@ -1962,8 +1967,9 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
EquivalenceClass *oeclass;
- int score;
- ListCell *lc2;
+ Bitmapset *matching_ems;
+ Bitmapset *interesting_ems;
+ Bitmapset *other_parent_ems;
/* get the outer eclass */
update_mergeclause_eclasses(root, rinfo);
@@ -1983,19 +1989,13 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
continue;
/* compute score */
- score = 0;
- foreach(lc2, oeclass->ec_members)
- {
- EquivalenceMember *em = (EquivalenceMember *)
lfirst(lc2);
-
- /* Potential future join partner? */
- if (!em->em_is_const && !em->em_is_child &&
- !bms_overlap(em->em_relids, joinrel->relids))
- score++;
- }
+ matching_ems = get_ecmember_indexes(root, oeclass,
joinrel->relids, false, false);
+ other_parent_ems = bms_difference(oeclass->ec_nonchild_indexes,
oeclass->ec_norel_indexes);
+ interesting_ems = bms_difference(other_parent_ems,
matching_ems);
+ /* record results */
ecs[necs] = oeclass;
- scores[necs] = score;
+ scores[necs] = bms_num_members(interesting_ems);
necs++;
}
diff --git a/src/backend/optimizer/plan/createplan.c
b/src/backend/optimizer/plan/createplan.c
index e37f2933eb..d3b58abba6 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -260,8 +260,8 @@ 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,
-
Relids relids,
+static Plan *prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+
List *pathkeys, Relids relids,
const AttrNumber *reqColIdx,
bool adjust_tlist_in_place,
int *p_numsortkeys,
@@ -269,10 +269,13 @@ 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,
- Relids
relids);
-static IncrementalSort *make_incrementalsort_from_pathkeys(Plan *lefttree,
-
List *pathkeys, Relids relids, int
nPresortedCols);
+static Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+ List
*pathkeys, Relids relids);
+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,
Plan
*lefttree);
@@ -293,7 +296,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);
@@ -1261,7 +1264,8 @@ 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,
@@ -1305,7 +1309,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,
@@ -1446,7 +1450,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,
@@ -1477,7 +1481,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,
@@ -1964,7 +1968,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,
@@ -2183,7 +2187,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);
@@ -2207,7 +2211,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,
@@ -2276,7 +2280,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);
@@ -4478,7 +4482,7 @@ create_mergejoin_plan(PlannerInfo *root,
if (best_path->outersortkeys)
{
Relids outer_relids = outer_path->parent->relids;
- Sort *sort = make_sort_from_pathkeys(outer_plan,
+ Sort *sort = make_sort_from_pathkeys(root, outer_plan,
best_path->outersortkeys,
outer_relids);
@@ -4492,7 +4496,7 @@ create_mergejoin_plan(PlannerInfo *root,
if (best_path->innersortkeys)
{
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);
@@ -6116,7 +6120,8 @@ 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,
@@ -6157,6 +6162,8 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
if (ec->ec_has_volatile)
{
+ int first_em;
+
/*
* If the pathkey's EquivalenceClass is volatile, then
it must
* have come from an ORDER BY clause, and we have to
match it to
@@ -6166,8 +6173,10 @@ prepare_sort_from_pathkeys(Plan *lefttree, List
*pathkeys,
elog(ERROR, "volatile EquivalenceClass has no
sortref");
tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
Assert(tle);
- Assert(list_length(ec->ec_members) == 1);
- pk_datatype = ((EquivalenceMember *)
linitial(ec->ec_members))->em_datatype;
+ Assert(bms_membership(ec->ec_member_indexes) ==
BMS_SINGLETON);
+ first_em = bms_next_member(ec->ec_member_indexes, -1);
+ pk_datatype = list_nth_node(EquivalenceMember,
root->eq_members,
+
first_em)->em_datatype;
}
else if (reqColIdx != NULL)
{
@@ -6183,7 +6192,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 */
@@ -6214,7 +6223,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 */
@@ -6230,7 +6239,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;
@@ -6301,7 +6310,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;
@@ -6310,7 +6320,9 @@ 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,
@@ -6336,7 +6348,8 @@ 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,
+make_incrementalsort_from_pathkeys(PlannerInfo *root,
+ Plan
*lefttree, List *pathkeys,
Relids
relids, int nPresortedCols)
{
int numsortkeys;
@@ -6346,7 +6359,9 @@ 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,
@@ -6696,7 +6711,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;
@@ -6737,6 +6753,8 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys,
int numCols)
if (ec->ec_has_volatile)
{
+ int first_em;
+
/*
* If the pathkey's EquivalenceClass is volatile, then
it must
* have come from an ORDER BY clause, and we have to
match it to
@@ -6746,8 +6764,10 @@ make_unique_from_pathkeys(Plan *lefttree, List
*pathkeys, int numCols)
elog(ERROR, "volatile EquivalenceClass has no
sortref");
tle = get_sortgroupref_tle(ec->ec_sortref,
plan->targetlist);
Assert(tle);
- Assert(list_length(ec->ec_members) == 1);
- pk_datatype = ((EquivalenceMember *)
linitial(ec->ec_members))->em_datatype;
+ Assert(bms_membership(ec->ec_member_indexes) ==
BMS_SINGLETON);
+ first_em = bms_next_member(ec->ec_member_indexes, -1);
+ pk_datatype = list_nth_node(EquivalenceMember,
root->eq_members,
+
first_em)->em_datatype;
}
else
{
@@ -6759,7 +6779,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/plan/planner.c
b/src/backend/optimizer/plan/planner.c
index 64632db73c..9d39b8287f 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -619,6 +619,9 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
root->cte_plan_ids = NIL;
root->multiexpr_params = NIL;
root->eq_classes = NIL;
+ root->eq_members = NIL;
+ root->eq_sources = NIL;
+ root->eq_derives = NIL;
root->ec_merging_done = false;
root->all_result_relids =
parse->resultRelation ?
bms_make_singleton(parse->resultRelation) : NULL;
diff --git a/src/backend/optimizer/prep/prepjointree.c
b/src/backend/optimizer/prep/prepjointree.c
index 0bd99acf83..8dac986f42 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -998,6 +998,9 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
RangeTblEntry *rte,
subroot->cte_plan_ids = NIL;
subroot->multiexpr_params = NIL;
subroot->eq_classes = NIL;
+ subroot->eq_members = NIL;
+ subroot->eq_sources = NIL;
+ subroot->eq_derives = NIL;
subroot->ec_merging_done = false;
subroot->all_result_relids = NULL;
subroot->leaf_result_relids = NULL;
diff --git a/src/backend/optimizer/prep/prepunion.c
b/src/backend/optimizer/prep/prepunion.c
index 043181b586..0ec3736e52 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -128,6 +128,7 @@ plan_set_operations(PlannerInfo *root)
* so that pathkeys.c won't complain.
*/
Assert(root->eq_classes == NIL);
+ Assert(root->eq_members == NIL);
root->ec_merging_done = true;
/*
diff --git a/src/backend/optimizer/util/relnode.c
b/src/backend/optimizer/util/relnode.c
index 520409f4ba..08cc90d4b9 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -97,6 +97,9 @@ setup_simple_rel_arrays(PlannerInfo *root)
root->simple_rel_array = (RelOptInfo **)
palloc0(size * sizeof(RelOptInfo *));
+ /* HACK HACK HACK: Used to store ec_member_indexes for varno=0 Exprs */
+ root->simple_rel_array[0] = makeNode(RelOptInfo);
+
/* simple_rte_array is an array equivalent of the rtable list */
root->simple_rte_array = (RangeTblEntry **)
palloc0(size * sizeof(RangeTblEntry *));
@@ -231,6 +234,9 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo
*parent)
rel->tuples = 0;
rel->allvisfrac = 0;
rel->eclass_indexes = NULL;
+ rel->eclass_member_indexes = NULL;
+ rel->eclass_source_indexes = NULL;
+ rel->eclass_derive_indexes = NULL;
rel->subroot = NULL;
rel->subplan_params = NIL;
rel->rel_parallel_workers = -1; /* set up in get_relation_info */
@@ -645,6 +651,9 @@ build_join_rel(PlannerInfo *root,
joinrel->tuples = 0;
joinrel->allvisfrac = 0;
joinrel->eclass_indexes = NULL;
+ joinrel->eclass_member_indexes = NULL;
+ joinrel->eclass_source_indexes = NULL;
+ joinrel->eclass_derive_indexes = NULL;
joinrel->subroot = NULL;
joinrel->subplan_params = NIL;
joinrel->rel_parallel_workers = -1;
@@ -828,6 +837,9 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo
*outer_rel,
joinrel->tuples = 0;
joinrel->allvisfrac = 0;
joinrel->eclass_indexes = NULL;
+ joinrel->eclass_member_indexes = NULL;
+ joinrel->eclass_source_indexes = NULL;
+ joinrel->eclass_derive_indexes = NULL;
joinrel->subroot = NULL;
joinrel->subplan_params = NIL;
joinrel->amflags = 0;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 3b065139e6..c60fa7b98b 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -300,6 +300,15 @@ struct PlannerInfo
/* list of active EquivalenceClasses */
List *eq_classes;
+ /* list of each EquivalenceMember */
+ List *eq_members;
+
+ /* 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;
@@ -882,6 +891,24 @@ typedef struct RelOptInfo
* Indexes in PlannerInfo's eq_classes list of ECs that mention this rel
*/
Bitmapset *eclass_indexes;
+
+ /*
+ * Indexes in PlannerInfo's eq_members list of EMs that mention this rel
+ */
+ Bitmapset *eclass_member_indexes;
+
+ /*
+ * Indexes in PlannerInfo's eq_sources list for RestrictInfos that
mention
+ * this relation.
+ */
+ Bitmapset *eclass_source_indexes;
+
+ /*
+ * Indexes in PlannerInfo's eq_derives list for RestrictInfos that
mention
+ * this relation.
+ */
+ Bitmapset *eclass_derive_indexes;
+
PlannerInfo *subroot; /* if subquery */
List *subplan_params; /* if subquery */
/* wanted number of parallel workers */
@@ -1270,9 +1297,17 @@ 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_member_indexes; /* Indexes into all PlannerInfos
eq_members
+ * for
this EquivalenceClass */
+ Bitmapset *ec_nonchild_indexes; /* Indexes into PlannerInfo's
eq_members
+ *
with em_is_child == false */
+ Bitmapset *ec_norel_indexes; /* Indexes into PlannerInfo's eq_members
for
+ * members
where pull_varno on the em_expr
+ * is an
empty set */
+ 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? */
diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h
index be5e2287f3..526723a187 100644
--- a/src/include/nodes/print.h
+++ b/src/include/nodes/print.h
@@ -16,6 +16,7 @@
#include "executor/tuptable.h"
+struct PlannerInfo;
#define nodeDisplay(x) pprint(x)
@@ -27,7 +28,9 @@ extern char *format_node_dump(const char *dump);
extern char *pretty_format_node_dump(const char *dump);
extern void print_rt(const List *rtable);
extern void print_expr(const Node *expr, const List *rtable);
-extern void print_pathkeys(const List *pathkeys, const List *rtable);
+extern void print_pathkeys(const struct PlannerInfo *root,
+ const List *pathkeys,
+ const List *rtable);
extern void print_tl(const List *tlist, const List *rtable);
extern void print_slot(TupleTableSlot *slot);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index d11cdac7f8..f6835f80f5 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -136,7 +136,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,
@@ -161,7 +162,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,
@@ -187,6 +189,28 @@ 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_ecmember_indexes(PlannerInfo *root,
+
EquivalenceClass *ec,
+
Relids relids,
+
bool with_children,
+
bool with_norel_members);
+extern Bitmapset *get_ecmember_indexes_strict(PlannerInfo *root,
+
EquivalenceClass *ec,
+
Relids relids,
+
bool with_children,
+
bool with_norel_members);
+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);
/*
* pathkeys.c
diff --git a/src/test/regress/expected/equivclass.out
b/src/test/regress/expected/equivclass.out
index 126f7047fe..69eb778627 100644
--- a/src/test/regress/expected/equivclass.out
+++ b/src/test/regress/expected/equivclass.out
@@ -229,12 +229,12 @@ explain (costs off)
union all
select ff + 4 as x from ec1) as ss1
where ss1.x = ec1.f1 and ec1.ff = 42::int8 and ec1.ff = ec1.f1;
- QUERY PLAN
--------------------------------------------------------------------
+ QUERY PLAN
+-----------------------------------------------------------
Nested Loop
Join Filter: ((((ec1_1.ff + 2) + 1)) = ec1.f1)
-> Index Scan using ec1_pkey on ec1
- Index Cond: ((ff = '42'::bigint) AND (ff = '42'::bigint))
+ Index Cond: (ff = '42'::bigint)
Filter: (ff = f1)
-> Append
-> Index Scan using ec1_expr2 on ec1 ec1_1
