v6-0001-Apply-eclass_member_speedup_v3.patch.patch
application/octet-stream
Filename: v6-0001-Apply-eclass_member_speedup_v3.patch.patch
Type: application/octet-stream
Part: 6
Patch
Same data as JSON:
GET /api/v1/attachments/:id/patch
the parsed metadata as JSON — format, series position, per-file stats; never the diff bytes.
API reference →
Format: format-patch
Series: patch v6-0001
Subject: Apply eclass_member_speedup_v3.patch
| File | + | − |
|---|---|---|
| contrib/postgres_fdw/postgres_fdw.c | 26 | 16 |
| src/backend/nodes/outfuncs.c | 5 | 3 |
| src/backend/nodes/print.c | 11 | 8 |
| src/backend/optimizer/path/allpaths.c | 1 | 1 |
| src/backend/optimizer/path/costsize.c | 9 | 4 |
| src/backend/optimizer/path/equivclass.c | 649 | 184 |
| src/backend/optimizer/path/indxpath.c | 14 | 8 |
| src/backend/optimizer/path/pathkeys.c | 21 | 21 |
| src/backend/optimizer/plan/createplan.c | 51 | 31 |
| src/backend/optimizer/plan/planner.c | 3 | 0 |
| src/backend/optimizer/prep/prepjointree.c | 3 | 0 |
| src/backend/optimizer/prep/prepunion.c | 1 | 0 |
| src/backend/optimizer/util/relnode.c | 12 | 0 |
| src/include/nodes/pathnodes.h | 38 | 3 |
| src/include/nodes/print.h | 4 | 1 |
| src/include/optimizer/paths.h | 26 | 2 |
| src/test/regress/expected/equivclass.out | 3 | 3 |
From e45c60ffb51f797c0e8bd4f88ee474fd6fbcaac7 Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Thu, 18 Aug 2022 14:26:42 +0900
Subject: [PATCH v6 1/3] Apply eclass_member_speedup_v3.patch
---
contrib/postgres_fdw/postgres_fdw.c | 42 +-
src/backend/nodes/outfuncs.c | 8 +-
src/backend/nodes/print.c | 19 +-
src/backend/optimizer/path/allpaths.c | 2 +-
src/backend/optimizer/path/costsize.c | 13 +-
src/backend/optimizer/path/equivclass.c | 833 +++++++++++++++++-----
src/backend/optimizer/path/indxpath.c | 22 +-
src/backend/optimizer/path/pathkeys.c | 42 +-
src/backend/optimizer/plan/createplan.c | 82 ++-
src/backend/optimizer/plan/planner.c | 3 +
src/backend/optimizer/prep/prepjointree.c | 3 +
src/backend/optimizer/prep/prepunion.c | 1 +
src/backend/optimizer/util/relnode.c | 12 +
src/include/nodes/pathnodes.h | 41 +-
src/include/nodes/print.h | 5 +-
src/include/optimizer/paths.h | 28 +-
src/test/regress/expected/equivclass.out | 6 +-
17 files changed, 877 insertions(+), 285 deletions(-)
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 60610e3a4b..e036420277 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 f486d42441..142568b80f 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
@@ -5820,7 +5824,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 799bdc91d0..2b04b67b14 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);
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_joinrel,
child_joinrel->top_parent);
- (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 63a8eef45c..9dc87b3553 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -185,8 +185,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)
@@ -3090,8 +3090,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;
@@ -3108,8 +3108,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.
@@ -3133,9 +3134,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 18f8870098..aeacc88d08 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1436,9 +1436,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
@@ -1493,18 +1497,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)
{
@@ -1556,7 +1561,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)
@@ -1967,8 +1972,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);
@@ -1988,19 +1994,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 cd8a3ef7cb..6d30a24990 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);
@@ -6111,7 +6115,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,
@@ -6152,6 +6157,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
@@ -6161,8 +6168,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)
{
@@ -6178,7 +6187,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 */
@@ -6209,7 +6218,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 */
@@ -6225,7 +6234,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;
@@ -6296,7 +6305,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;
@@ -6305,7 +6315,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,
@@ -6331,7 +6343,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;
@@ -6341,7 +6354,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,
@@ -6691,7 +6706,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;
@@ -6732,6 +6748,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
@@ -6741,8 +6759,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
{
@@ -6754,7 +6774,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 079bd0bfdf..7f3398572b 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 41c7066d90..3d322c353f 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 71052c841d..6da7f70922 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 edcdd0a360..7fc86aeb0d 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 */
@@ -643,6 +649,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;
@@ -829,6 +838,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 294cfe9c47..bf6389fee4 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;
@@ -889,6 +898,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 */
@@ -1285,9 +1312,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
--
2.35.3.windows.1