v19-rebased.txt
text/plain
Filename: v19-rebased.txt
Type: text/plain
Part: 6
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index b92e2a0fc9f..4d563c58bdc 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7770,6 +7770,10 @@ conversion_error_callback(void *arg)
varno = var->varno;
colno = var->varattno;
}
+ /*
+ * XXX why don't we break here? Surely there can't be another
+ * equal EquivalenceMember?
+ */
}
if (varno > 0)
@@ -7828,26 +7832,29 @@ conversion_error_callback(void *arg)
EquivalenceMember *
find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
{
- ListCell *lc;
-
+ EquivalenceMemberIterator iter;
+ EquivalenceMember *em;
PgFdwRelationInfo *fpinfo = (PgFdwRelationInfo *) rel->fdw_private;
- foreach(lc, ec->ec_members)
- {
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ setup_eclass_member_iterator(&iter, root, ec, rel->relids, true, false);
+ while ((em = eclass_member_iterator_next(&iter)) != NULL)
+ {
/*
* Note we require !bms_is_empty, else we'd accept constant
* expressions which are not suitable for the purpose.
*/
+ Assert(!bms_is_empty(em->em_relids));
+
if (bms_is_subset(em->em_relids, rel->relids) &&
- !bms_is_empty(em->em_relids) &&
bms_is_empty(bms_intersect(em->em_relids, fpinfo->hidden_subquery_rels)) &&
is_foreign_expr(root, rel, em->em_expr))
- return em;
+ break;
}
- return NULL;
+ eclass_member_iterator_dispose(&iter);
+
+ return em;
}
/*
@@ -7874,7 +7881,9 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
{
Expr *expr = (Expr *) lfirst(lc1);
Index sgref = get_pathtarget_sortgroupref(target, i);
- ListCell *lc2;
+ EquivalenceMemberIterator iter;
+ EquivalenceMember *em;
+ Relids expr_relids;
/* Ignore non-sort expressions */
if (sgref == 0 ||
@@ -7889,19 +7898,20 @@ 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);
+ setup_eclass_member_strict_iterator(&iter, root, ec, expr_relids,
+ false, false);
+
/* Locate an EquivalenceClass member matching this expr, if any */
- foreach(lc2, ec->ec_members)
+ while ((em = eclass_member_iterator_strict_next(&iter)) != NULL)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
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;
@@ -7913,10 +7923,15 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
/* Check that expression (including relabels!) is shippable */
if (is_foreign_expr(root, rel, em->em_expr))
+ {
+ bms_free(expr_relids);
+ eclass_member_iterator_dispose(&iter);
return em;
+ }
}
-
i++;
+ bms_free(expr_relids);
+ eclass_member_iterator_dispose(&iter);
}
return NULL;
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 1597b8e8127..d093871427d 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -1684,6 +1684,22 @@ list_sort(List *list, list_sort_comparator cmp)
qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
}
+/*
+ * list_sort comparator for sorting a list into ascending ptr order.
+ */
+int
+list_ptr_cmp(const ListCell *p1, const ListCell *p2)
+{
+ void *v1 = lfirst(p1);
+ void *v2 = lfirst(p2);
+
+ if (v1 < v2)
+ return -1;
+ if (v1 > v2)
+ return 1;
+ return 0;
+}
+
/*
* list_sort comparator for sorting a list into ascending int order.
*/
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bb9bdd67192..94ce706c6c9 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -466,8 +466,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);
@@ -573,6 +576,9 @@ _outRangeTblEntry(StringInfo str, const RangeTblEntry *node)
WRITE_BOOL_FIELD(lateral);
WRITE_BOOL_FIELD(inFromCl);
WRITE_NODE_FIELD(securityQuals);
+ WRITE_BITMAPSET_FIELD(eclass_member_indexes);
+ WRITE_BITMAPSET_FIELD(eclass_source_indexes);
+ WRITE_BITMAPSET_FIELD(eclass_derive_indexes);
}
static void
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index 64d3a09f765..78960e4f475 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -434,6 +434,9 @@ _readRangeTblEntry(void)
READ_BOOL_FIELD(lateral);
READ_BOOL_FIELD(inFromCl);
READ_NODE_FIELD(securityQuals);
+ READ_BITMAPSET_FIELD(eclass_member_indexes);
+ READ_BITMAPSET_FIELD(eclass_source_indexes);
+ READ_BITMAPSET_FIELD(eclass_derive_indexes);
READ_DONE();
}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index ec004ed9493..bac2252eb91 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -5839,7 +5839,8 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
if (ec && ec->ec_has_const)
{
EquivalenceMember *em = fkinfo->fk_eclass_member[i];
- RestrictInfo *rinfo = find_derived_clause_for_ec_member(ec,
+ RestrictInfo *rinfo = find_derived_clause_for_ec_member(root,
+ ec,
em);
if (rinfo)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 7cafaca33c5..ec4669c23bf 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -32,8 +32,12 @@
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"
-
-static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
+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,
JoinDomain *jdomain,
EquivalenceMember *parent,
@@ -310,7 +314,6 @@ process_equivalence(PlannerInfo *root,
/* If case 1, nothing to do, except add to sources */
if (ec1 == ec2)
{
- ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -321,6 +324,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;
}
@@ -341,8 +346,16 @@ process_equivalence(PlannerInfo *root,
* be found.
*/
ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
- ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
- ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
+ ec1->ec_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 */
@@ -354,10 +367,12 @@ process_equivalence(PlannerInfo *root,
root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
/* just to avoid debugging confusion w/ dangling pointers: */
ec2->ec_members = NIL;
- ec2->ec_sources = NIL;
- ec2->ec_derives = NIL;
+ ec2->ec_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_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -368,13 +383,14 @@ process_equivalence(PlannerInfo *root,
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
+
+ add_eq_source(root, ec1, restrictinfo);
}
else if (ec1)
{
/* Case 3: add item2 to ec1 */
- em2 = add_eq_member(ec1, item2, item2_relids,
+ em2 = add_eq_member(root, ec1, item2, item2_relids,
jdomain, NULL, item2_type);
- ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_min_security = Min(ec1->ec_min_security,
restrictinfo->security_level);
ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -385,13 +401,14 @@ process_equivalence(PlannerInfo *root,
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
+
+ add_eq_source(root, ec1, restrictinfo);
}
else if (ec2)
{
/* Case 3: add item1 to ec2 */
- em1 = add_eq_member(ec2, item1, item1_relids,
+ em1 = add_eq_member(root, ec2, item1, item1_relids,
jdomain, NULL, item1_type);
- ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
ec2->ec_min_security = Min(ec2->ec_min_security,
restrictinfo->security_level);
ec2->ec_max_security = Max(ec2->ec_max_security,
@@ -402,6 +419,8 @@ process_equivalence(PlannerInfo *root,
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
+
+ add_eq_source(root, ec2, restrictinfo);
}
else
{
@@ -411,8 +430,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;
@@ -421,9 +443,9 @@ 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,
+ em1 = add_eq_member(root, ec, item1, item1_relids,
jdomain, NULL, item1_type);
- em2 = add_eq_member(ec, item2, item2_relids,
+ em2 = add_eq_member(root, ec, item2, item2_relids,
jdomain, NULL, item2_type);
root->eq_classes = lappend(root->eq_classes, ec);
@@ -434,6 +456,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;
@@ -509,16 +533,64 @@ 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)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rte->eclass_source_indexes = bms_add_member(rte->eclass_source_indexes,
+ source_idx);
+ }
+}
+
+/*
+ * add_eq_derive - add 'rinfo' in eq_derives for this 'ec'
+ */
+static void
+add_eq_derive(PlannerInfo *root, EquivalenceClass *ec, RestrictInfo *rinfo)
+{
+ int derive_idx = list_length(root->eq_derives);
+ int i;
+
+ ec->ec_derive_indexes = bms_add_member(ec->ec_derive_indexes, derive_idx);
+ root->eq_derives = lappend(root->eq_derives, rinfo);
+
+ i = -1;
+ while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rte->eclass_derive_indexes = bms_add_member(rte->eclass_derive_indexes,
+ derive_idx);
+ }
+}
+
/*
* add_eq_member - build a new EquivalenceMember and add it to an EC
*/
static EquivalenceMember *
-add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
+add_eq_member(PlannerInfo *root, EquivalenceClass *ec, Expr *expr, Relids relids,
JoinDomain *jdomain, EquivalenceMember *parent, 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_index = em_index;
em->em_relids = relids;
em->em_is_const = false;
em->em_is_child = (parent != NULL);
@@ -526,6 +598,23 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
em->em_jdomain = jdomain;
em->em_parent = parent;
+ /*
+ * 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 (parent != NULL)
+ 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));
+ }
+
+ /* record the actual relids from 'expr' */
+ em->em_norel_expr = bms_is_empty(expr_relids);
+
if (bms_is_empty(relids))
{
/*
@@ -544,9 +633,32 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
else if (!parent) /* 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);
}
+
+ /* add the new member to the list */
ec->ec_members = lappend(ec->ec_members, em);
+ /* and add it to the index and PlannerInfo's list */
+ 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 (parent != NULL)
+ expr_relids = bms_add_members(expr_relids, relids);
+
+ i = -1;
+ while ((i = bms_next_member(expr_relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rte->eclass_member_indexes =
+ bms_add_member(rte->eclass_member_indexes, em_index);
+ }
+
return em;
}
@@ -603,6 +715,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);
/*
* Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
@@ -616,7 +729,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
- ListCell *lc2;
+ EquivalenceMemberIterator iter;
+ EquivalenceMember *cur_em;
/*
* Never match to a volatile EC, except when we are looking at another
@@ -631,10 +745,11 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
- foreach(lc2, cur_ec->ec_members)
- {
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+ setup_eclass_member_strict_iterator(&iter, root, cur_ec, expr_relids,
+ true, true);
+ while ((cur_em = eclass_member_iterator_strict_next(&iter)) != NULL)
+ {
/*
* Ignore child members unless they match the request.
*/
@@ -653,6 +768,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
equal(expr, cur_em->em_expr))
return cur_ec; /* Match! */
}
+
+ eclass_member_iterator_dispose(&iter);
}
/* No match; does caller want a NULL result? */
@@ -670,8 +787,11 @@ get_eclass_for_sort_expr(PlannerInfo *root,
newec->ec_opfamilies = list_copy(opfamilies);
newec->ec_collation = collation;
newec->ec_members = NIL;
- newec->ec_sources = NIL;
- newec->ec_derives = NIL;
+ newec->ec_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);
@@ -684,12 +804,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (newec->ec_has_volatile && sortref == 0) /* should not happen */
elog(ERROR, "volatile EquivalenceClass has no sortref");
- /*
- * Get the precise set of relids appearing in the expression.
- */
- expr_relids = pull_varnos(root, (Node *) expr);
-
- newem = add_eq_member(newec, copyObject(expr), expr_relids,
+ newem = add_eq_member(root, newec, copyObject(expr), expr_relids,
jdomain, NULL, opcintype);
/*
@@ -721,7 +836,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];
@@ -731,7 +846,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (rel == NULL) /* must be an outer join */
{
- Assert(bms_is_member(i, root->outer_join_rels));
+ Assert(i == 0 || bms_is_member(i, root->outer_join_rels));
continue;
}
@@ -760,19 +875,25 @@ 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;
+ EquivalenceMemberIterator iter;
+ Relids expr_relids;
+ EquivalenceMember *em;
/* 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);
+ setup_eclass_member_strict_iterator(&iter, root, ec, expr_relids, true,
+ true);
+
+ while ((em = eclass_member_iterator_strict_next(&iter)) != NULL)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
Expr *emexpr;
/*
@@ -797,10 +918,13 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
emexpr = ((RelabelType *) emexpr)->arg;
if (equal(emexpr, expr))
- return em;
+ break;
}
- return NULL;
+ bms_free(expr_relids);
+ eclass_member_iterator_dispose(&iter);
+
+ return em;
}
/*
@@ -938,7 +1062,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;
@@ -1025,7 +1149,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
@@ -1082,7 +1206,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];
@@ -1118,6 +1242,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
{
EquivalenceMember *const_em = NULL;
ListCell *lc;
+ int i;
/*
* In the trivial case where we just had one "var = const" clause, push
@@ -1127,9 +1252,9 @@ generate_base_implied_equalities_const(PlannerInfo *root,
* equivalent to the old one.
*/
if (list_length(ec->ec_members) == 2 &&
- list_length(ec->ec_sources) == 1)
+ bms_get_singleton_member(ec->ec_source_indexes, &i))
{
- RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
+ RestrictInfo *restrictinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
distribute_restrictinfo_to_rels(root, restrictinfo);
return;
@@ -1141,9 +1266,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)
{
@@ -1187,9 +1314,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.)
*/
@@ -1199,7 +1326,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);
}
}
}
@@ -1212,7 +1340,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
@@ -1225,9 +1354,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 */
@@ -1265,7 +1397,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.
*/
@@ -1289,11 +1421,15 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
* 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. (Note: rebuild_eclass_attr_needed
- * needs to match this code.)
+ * needs to match this 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 |
@@ -1302,6 +1438,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);
}
/*
@@ -1322,11 +1459,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)
@@ -1367,11 +1505,11 @@ generate_base_implied_equalities_broken(PlannerInfo *root,
* Because the same join clauses are likely to be needed multiple times as
* we consider different join paths, we avoid generating multiple copies:
* whenever we select a particular pair of EquivalenceMembers to join,
- * we check to see if the pair matches any original clause (in ec_sources)
- * or previously-built clause (in ec_derives). This saves memory and allows
- * re-use of information cached in RestrictInfos. We also avoid generating
- * commutative duplicates, i.e. if the algorithm selects "a.x = b.y" but
- * we already have "b.y = a.x", we return the existing clause.
+ * we check to see if the pair matches any original clause in root's
+ * eq_sources or previously-built clause (in root's eq_derives). This saves
+ * memory and allows re-use of information cached in RestrictInfos. We also
+ * avoid generating commutative duplicates, i.e. if the algorithm selects
+ * "a.x = b.y" but we already have "b.y = a.x", we return the existing clause.
*
* If we are considering an outer join, sjinfo is the associated OJ info,
* otherwise it can be NULL.
@@ -1559,6 +1697,8 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
Relids outer_relids,
Relids inner_relids)
{
+ EquivalenceMemberIterator iter;
+ EquivalenceMember *cur_em;
List *result = NIL;
List *new_members = NIL;
List *outer_members = NIL;
@@ -1574,10 +1714,10 @@ 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)
- {
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+ setup_eclass_member_iterator(&iter, root, ec, join_relids, true, false);
+ while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
+ {
/*
* We don't need to check explicitly for child EC members. This test
* against join_relids will cause them to be ignored except when
@@ -1594,6 +1734,8 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
new_members = lappend(new_members, cur_em);
}
+ eclass_member_iterator_dispose(&iter);
+
/*
* First, select the joinclause if needed. We can equate any one outer
* member to any one inner member, but we have to find a datatype
@@ -1691,7 +1833,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
foreach(lc1, new_members)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+ cur_em = (EquivalenceMember *) lfirst(lc1);
if (prev_em != NULL)
{
@@ -1736,12 +1878,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) &&
@@ -1753,12 +1899,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)
@@ -1820,10 +1966,11 @@ create_join_clause(PlannerInfo *root,
EquivalenceMember *rightem,
EquivalenceClass *parent_ec)
{
+ Bitmapset *matches;
RestrictInfo *rinfo;
RestrictInfo *parent_rinfo = NULL;
- ListCell *lc;
MemoryContext oldcontext;
+ int i;
/*
* Search to see if we already built a RestrictInfo for this pair of
@@ -1834,9 +1981,12 @@ create_join_clause(PlannerInfo *root,
* it's not identical, it'd better have the same effects, or the operator
* families we're using are broken.
*/
- foreach(lc, ec->ec_sources)
+ matches = bms_int_members(get_ec_source_indexes_strict(root, ec, leftem->em_relids),
+ get_ec_source_indexes_strict(root, ec, rightem->em_relids));
+ i = -1;
+ while ((i = bms_next_member(matches, i)) >= 0)
{
- rinfo = (RestrictInfo *) lfirst(lc);
+ rinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
if (rinfo->left_em == leftem &&
rinfo->right_em == rightem &&
rinfo->parent_ec == parent_ec)
@@ -1847,9 +1997,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)
@@ -1922,7 +2076,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);
@@ -2132,7 +2286,8 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
left_type,
right_type,
inner_datatype;
- Relids inner_relids;
+ Relids outer_relids,
+ inner_relids;
ListCell *lc1;
Assert(is_opclause(rinfo->clause));
@@ -2146,6 +2301,7 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
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
@@ -2153,6 +2309,7 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
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;
}
@@ -2160,8 +2317,10 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
+ EquivalenceMemberIterator iter;
+ EquivalenceMember *cur_em;
bool match;
- ListCell *lc2;
+ int i;
/* Ignore EC unless it contains pseudoconstants */
if (!cur_ec->ec_has_const)
@@ -2176,10 +2335,12 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
continue;
/* Does it contain a match to outervar? */
match = false;
- foreach(lc2, cur_ec->ec_members)
- {
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+ setup_eclass_member_strict_iterator(&iter, root, cur_ec, outer_relids,
+ false, true);
+
+ while ((cur_em = eclass_member_iterator_strict_next(&iter)) != NULL)
+ {
Assert(!cur_em->em_is_child); /* no children yet */
if (equal(outervar, cur_em->em_expr))
{
@@ -2187,6 +2348,8 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
break;
}
}
+ eclass_member_iterator_dispose(&iter);
+
if (!match)
continue; /* no match, so ignore this EC */
@@ -2196,13 +2359,15 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
* 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);
Oid eq_op;
RestrictInfo *newrinfo;
JoinDomain *jdomain;
+ cur_em = list_nth_node(EquivalenceMember, root->eq_members, i);
+
if (!cur_em->em_is_const)
continue; /* ignore non-const members */
eq_op = select_equality_operator(cur_ec,
@@ -2272,11 +2437,12 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
{
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)
@@ -2303,10 +2469,14 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
* 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))
{
@@ -2333,7 +2503,7 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
if (equal(leftvar, cfirst) && equal(rightvar, csecond))
{
- coal_idx = foreach_current_index(lc2);
+ coal_idx = i;
match = true;
break;
}
@@ -2349,9 +2519,11 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
* 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;
JoinDomain *jdomain;
@@ -2399,11 +2571,28 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
* 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);
+ /* XXX performance of list_delete()?? */
+ cur_ec->ec_members = list_delete(cur_ec->ec_members, coal_em);
+ 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)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rte->eclass_member_indexes =
+ bms_del_member(rte->eclass_member_indexes, coal_idx);
+ }
+
return true;
}
@@ -2498,13 +2687,16 @@ bool
exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2, Oid opfamily)
{
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)
@@ -2521,9 +2713,13 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2, Oid opfamily)
!list_member_oid(ec->ec_opfamilies, opfamily))
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 */
@@ -2585,16 +2781,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;
/* It's okay to consider "broken" ECs here, see exprs_known_equal */
+ 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)
@@ -2647,16 +2848,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
@@ -2707,7 +2911,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;
+ EquivalenceMemberIterator iter;
+ EquivalenceMember *cur_em;
/*
* If this EC contains a volatile expression, then generating child
@@ -2721,29 +2926,15 @@ 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 using the EquivalenceMemberIterator means we only loop over
+ * the members which existed when we set up the iterator, not 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);
-
- if (cur_em->em_is_const)
- continue; /* ignore consts here */
-
- /*
- * 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 */
+ setup_eclass_member_iterator(&iter, root, cur_ec, top_parent_relids,
+ false, false);
+ while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
+ {
/*
* Consider only members that reference and can be computed at
* child's topmost parent rel. In particular we want to exclude
@@ -2752,13 +2943,16 @@ add_child_rel_equivalences(PlannerInfo *root,
* simple Var; and in any case it wouldn't produce a member that
* has any use in creating plans for the child rel.
*/
- if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
- !bms_is_empty(cur_em->em_relids))
+ if (bms_is_subset(cur_em->em_relids, top_parent_relids))
{
/* OK, generate transformed child version */
Expr *child_expr;
Relids new_relids;
+ Assert(!cur_em->em_is_const);
+ Assert(!cur_em->em_is_child);
+ Assert(!bms_is_empty(cur_em->em_relids));
+
if (parent_rel->reloptkind == RELOPT_BASEREL)
{
/* Simple single-level transformation */
@@ -2787,7 +2981,7 @@ add_child_rel_equivalences(PlannerInfo *root,
top_parent_relids);
new_relids = bms_add_members(new_relids, child_relids);
- (void) add_eq_member(cur_ec, child_expr, new_relids,
+ (void) add_eq_member(root, cur_ec, child_expr, new_relids,
cur_em->em_jdomain,
cur_em, cur_em->em_datatype);
@@ -2795,6 +2989,7 @@ add_child_rel_equivalences(PlannerInfo *root,
child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
}
}
+ eclass_member_iterator_dispose(&iter);
}
}
@@ -2839,7 +3034,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;
+ EquivalenceMemberIterator iter;
+ EquivalenceMember *cur_em;
/*
* If this EC contains a volatile expression, then generating child
@@ -2853,24 +3049,21 @@ 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 using the EquivalenceMemberIterator means we only loop over
+ * the members which existed when we set up the iterator, not newly
+ * added ones.
*/
- num_members = list_length(cur_ec->ec_members);
- for (int pos = 0; pos < num_members; pos++)
+ setup_eclass_member_iterator(&iter, root, cur_ec, top_parent_relids,
+ false, false);
+
+ while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+ Expr *child_expr;
+ Relids new_relids;
- if (cur_em->em_is_const)
- continue; /* ignore consts here */
-
- /*
- * 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,
@@ -2879,47 +3072,40 @@ 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))
+ if (parent_joinrel->reloptkind == RELOPT_JOINREL)
{
- /* Yes, generate transformed child version */
- Expr *child_expr;
- Relids new_relids;
-
- if (parent_joinrel->reloptkind == RELOPT_JOINREL)
- {
- /* Simple single-level transformation */
- child_expr = (Expr *)
- adjust_appendrel_attrs(root,
- (Node *) cur_em->em_expr,
- nappinfos, appinfos);
- }
- else
- {
- /* Must do multi-level transformation */
- Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
- child_expr = (Expr *)
- adjust_appendrel_attrs_multilevel(root,
- (Node *) cur_em->em_expr,
- child_joinrel,
- child_joinrel->top_parent);
- }
+ /* Simple single-level transformation */
+ child_expr = (Expr *)
+ adjust_appendrel_attrs(root,
+ (Node *) cur_em->em_expr,
+ nappinfos, appinfos);
+ }
+ else
+ {
+ /* Must do multi-level transformation */
+ Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
+ child_expr = (Expr *)
+ adjust_appendrel_attrs_multilevel(root,
+ (Node *) cur_em->em_expr,
+ child_joinrel,
+ child_joinrel->top_parent);
+ }
- /*
- * Transform em_relids to match. Note we do *not* do
- * pull_varnos(child_expr) here, as for example the
- * transformation might have substituted a constant, but we
- * don't want the child member to be marked as constant.
- */
- new_relids = bms_difference(cur_em->em_relids,
- top_parent_relids);
- new_relids = bms_add_members(new_relids, child_relids);
+ /*
+ * Transform em_relids to match. Note we do *not* do
+ * pull_varnos(child_expr) here, as for example the
+ * transformation might have substituted a constant, but we
+ * don't want the child member to be marked as constant.
+ */
+ new_relids = bms_difference(cur_em->em_relids,
+ top_parent_relids);
+ new_relids = bms_add_members(new_relids, child_relids);
- (void) add_eq_member(cur_ec, child_expr, new_relids,
- cur_em->em_jdomain,
- cur_em, cur_em->em_datatype);
- }
+ (void) add_eq_member(root, cur_ec, child_expr, new_relids,
+ cur_em->em_jdomain,
+ cur_em, cur_em->em_datatype);
}
+ eclass_member_iterator_dispose(&iter);
}
MemoryContextSwitchTo(oldcontext);
@@ -2966,7 +3152,8 @@ add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel,
* likewise, the JoinDomain can be that of the initial member of the
* Pathkey's EquivalenceClass.
*/
- add_eq_member(pk->pk_eclass,
+ add_eq_member(root,
+ pk->pk_eclass,
tle->expr,
child_rel->relids,
parent_em->em_jdomain,
@@ -3039,7 +3226,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
{
EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
EquivalenceMember *cur_em;
- ListCell *lc2;
+ EquivalenceMemberIterator iter;
+ int j;
/* Sanity check eclass_indexes only contain ECs for rel */
Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
@@ -3061,16 +3249,19 @@ 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.)
*/
- cur_em = NULL;
- foreach(lc2, cur_ec->ec_members)
+ setup_eclass_member_iterator(&iter, root, cur_ec, rel->relids, true,
+ false);
+
+ while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
{
- cur_em = (EquivalenceMember *) lfirst(lc2);
if (bms_equal(cur_em->em_relids, rel->relids) &&
callback(root, rel, cur_ec, cur_em, callback_arg))
break;
cur_em = NULL;
}
+ eclass_member_iterator_dispose(&iter);
+
if (!cur_em)
continue;
@@ -3078,14 +3269,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 ||
@@ -3193,7 +3385,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
@@ -3268,7 +3460,7 @@ eclass_useful_for_merging(PlannerInfo *root,
RelOptInfo *rel)
{
Relids relids;
- ListCell *lc;
+ int i;
Assert(!eclass->ec_merged);
@@ -3281,7 +3473,7 @@ eclass_useful_for_merging(PlannerInfo *root,
/*
* Note we don't test ec_broken; if we did, we'd need a separate code path
- * to look through ec_sources. Checking the members anyway is OK as a
+ * to look through eq_sources. Checking the members anyway is OK as a
* possibly-overoptimistic heuristic.
*/
@@ -3299,12 +3491,14 @@ eclass_useful_for_merging(PlannerInfo *root,
return false;
/* To join, we need a member not in the given rel */
- foreach(lc, eclass->ec_members)
+ i = -1;
+ while ((i = bms_next_member(eclass->ec_nonchild_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_child)
- continue; /* ignore children here */
+ /* we don't expect child members here */
+ Assert(!cur_em->em_is_child);
if (!bms_overlap(cur_em->em_relids, relids))
return true;
@@ -3392,7 +3586,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];
@@ -3438,3 +3632,595 @@ 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 = -1;
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rel_ems = bms_add_members(rel_ems, rte->eclass_member_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ 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. */
+ if (!with_children)
+ matching_ems = bms_int_members(rel_ems, ec->ec_nonchild_indexes);
+ else
+ matching_ems = bms_int_members(rel_ems, ec->ec_member_indexes);
+
+ /* 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 = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ /*
+ * bms_intersect to the first relation to try to keep the resulting
+ * Bitmapset as small as possible. This saves having to make a
+ * complete bms_copy() of one of them. One may contain significantly
+ * more words than the other.
+ */
+ if (!with_children)
+ matching_ems = bms_intersect(rte->eclass_member_indexes,
+ ec->ec_nonchild_indexes);
+ else
+ matching_ems = bms_intersect(rte->eclass_member_indexes,
+ ec->ec_member_indexes);
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ rte = root->simple_rte_array[i];
+ matching_ems = bms_int_members(matching_ems,
+ rte->eclass_member_indexes);
+ }
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ 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
+
+ /* optionally add 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;
+}
+
+/*
+ * The threshold for the number of members that must be in an EquivalenceClass
+ * before we switch to searching for EquivalenceMember by using the Bitmapset
+ * indexes stored in EquivalenceClass and RelOptInfo. We don't want to make
+ * this too low as the manipulation of Bitmapsets slows this down for
+ * EquivalenceClasses with just a few members. The linear search becomes very
+ * slow when an EquivalenceClass has a large number of members, as can happen
+ * when planning queries to partitioned tables.
+ */
+#define ECMEMBER_INDEX_THRESHOLD 16
+
+/*
+ * setup_eclass_member_iterator
+ * Setup 'iter' so it's ready for eclass_member_iterator_next to start
+ * searching for EquivalenceMembers matching the specified parameters.
+ *
+ * Once used, the iterator must be disposed of using
+ * eclass_member_iterator_dispose.
+ */
+void
+setup_eclass_member_iterator(EquivalenceMemberIterator *iter,
+ PlannerInfo *root, EquivalenceClass *ec,
+ Relids relids, bool with_children,
+ bool with_norel_members)
+{
+ iter->orig_length = list_length(ec->ec_members);
+ iter->use_index = iter->orig_length >= ECMEMBER_INDEX_THRESHOLD;
+ iter->with_children = with_children;
+ iter->with_norel_members = with_norel_members;
+ iter->relids_empty = bms_is_empty(relids);
+#ifdef USE_ASSERT_CHECKING
+ iter->isstrict = false;
+#endif
+ iter->with_relids = relids;
+ iter->root = root;
+ iter->eclass = ec;
+
+#ifdef USE_ASSERT_CHECKING
+ if (1)
+#else
+ if (iter->use_index)
+#endif
+ iter->matching_ems = get_ecmember_indexes(root, ec, relids,
+ with_children,
+ with_norel_members);
+ else
+ iter->matching_ems = NULL;
+
+ iter->current_index = -1;
+
+#ifdef USE_ASSERT_CHECKING
+
+ /*
+ * Verify that an iterator that uses the index and one that does not both
+ * return the same EquivalenceMembers
+ */
+ {
+ EquivalenceMemberIterator idx_iter;
+ EquivalenceMemberIterator noidx_iter;
+ EquivalenceMember *em;
+ List *list1 = NIL;
+ List *list2 = NIL;
+ ListCell *lc1,
+ *lc2;
+
+ memcpy(&idx_iter, iter, sizeof(EquivalenceMemberIterator));
+ memcpy(&noidx_iter, iter, sizeof(EquivalenceMemberIterator));
+
+ idx_iter.use_index = true;
+ noidx_iter.use_index = false;
+
+ while ((em = eclass_member_iterator_next(&idx_iter)) != NULL)
+ list1 = lappend(list1, em);
+
+ while ((em = eclass_member_iterator_next(&noidx_iter)) != NULL)
+ list2 = lappend(list2, em);
+
+ list_sort(list1, list_ptr_cmp);
+ list_sort(list2, list_ptr_cmp);
+
+ Assert(list_length(list1) == list_length(list2));
+
+ forboth(lc1, list1, lc2, list2)
+ Assert(lfirst(lc1) == lfirst(lc2));
+ }
+#endif
+
+}
+
+/*
+ * setup_eclass_member_strict_iterator
+ * Setup 'iter' so it's ready for eclass_member_iterator_strict_next to
+ * start searching for EquivalenceMembers matching the specified
+ * parameters.
+ *
+ * Once used, the iterator must be disposed of using
+ * eclass_member_iterator_dispose.
+ */
+void
+setup_eclass_member_strict_iterator(EquivalenceMemberIterator *iter,
+ PlannerInfo *root, EquivalenceClass *ec,
+ Relids relids, bool with_children,
+ bool with_norel_members)
+{
+ iter->orig_length = list_length(ec->ec_members);
+ iter->use_index = iter->orig_length >= ECMEMBER_INDEX_THRESHOLD;
+ iter->with_children = with_children;
+ iter->with_norel_members = with_norel_members;
+ iter->relids_empty = bms_is_empty(relids);
+#ifdef USE_ASSERT_CHECKING
+ iter->isstrict = true;
+#endif
+ iter->with_relids = relids;
+ iter->root = root;
+ iter->eclass = ec;
+
+#ifdef USE_ASSERT_CHECKING
+ if (1)
+#else
+ if (iter->use_index)
+#endif
+ iter->matching_ems = get_ecmember_indexes_strict(root, ec, relids,
+ with_children,
+ with_norel_members);
+ else
+ iter->matching_ems = NULL;
+
+ iter->current_index = -1;
+
+#ifdef USE_ASSERT_CHECKING
+
+ /*
+ * Verify that an iterator that uses the index and one that does not both
+ * return the same EquivalenceMembers
+ */
+ {
+ EquivalenceMemberIterator idx_iter;
+ EquivalenceMemberIterator noidx_iter;
+ EquivalenceMember *em;
+ List *list1 = NIL;
+ List *list2 = NIL;
+ ListCell *lc1,
+ *lc2;
+
+ memcpy(&idx_iter, iter, sizeof(EquivalenceMemberIterator));
+ memcpy(&noidx_iter, iter, sizeof(EquivalenceMemberIterator));
+
+ idx_iter.use_index = true;
+ noidx_iter.use_index = false;
+
+ while ((em = eclass_member_iterator_strict_next(&idx_iter)) != NULL)
+ list1 = lappend(list1, em);
+
+ while ((em = eclass_member_iterator_strict_next(&noidx_iter)) != NULL)
+ list2 = lappend(list2, em);
+
+ list_sort(list1, list_ptr_cmp);
+ list_sort(list2, list_ptr_cmp);
+
+ Assert(list_length(list1) == list_length(list2));
+
+ forboth(lc1, list1, lc2, list2)
+ Assert(lfirst(lc1) == lfirst(lc2));
+ }
+#endif
+}
+
+/*
+ * eclass_member_iterator_next
+ * Fetch the next EquivalenceMember from an EquivalenceMemberIterator
+ * which was set up by setup_eclass_member_iterator(). Returns NULL when
+ * there are no more matching EquivalenceMembers.
+ */
+EquivalenceMember *
+eclass_member_iterator_next(EquivalenceMemberIterator *iter)
+{
+ /* Fail if this was used instead of eclass_member_iterator_strict_next */
+ Assert(!iter->isstrict);
+
+ if (iter->use_index)
+ {
+ iter->current_index = bms_next_member(iter->matching_ems,
+ iter->current_index);
+ if (iter->current_index >= 0)
+ return list_nth_node(EquivalenceMember, iter->root->eq_members,
+ iter->current_index);
+ return NULL;
+ }
+ else
+ {
+ ListCell *lc;
+
+ for_each_from(lc, iter->eclass->ec_members, iter->current_index + 1)
+ {
+ EquivalenceMember *em = lfirst_node(EquivalenceMember, lc);
+
+ iter->current_index = foreach_current_index(lc);
+
+ /*
+ * Some users of this iterator will be adding new
+ * EquivalenceMember during the loop. We must ensure we don't
+ * return those, so here we return NULL when the loop index goes
+ * beyond the original length of the ec_members list.
+ */
+ if (iter->current_index >= iter->orig_length)
+ return NULL;
+
+ /* don't return child members when with_children==false */
+ if (!iter->with_children && em->em_is_child)
+ continue;
+
+ /*
+ * When with_norel_members==true, make sure we return all members
+ * without Vars.
+ */
+ if (iter->with_norel_members && em->em_norel_expr)
+ return em;
+
+ /*
+ * Don't return members which have no common rels with with_relids
+ */
+ if (!bms_overlap(em->em_relids, iter->with_relids))
+ continue;
+
+ return em;
+ }
+ return NULL;
+ }
+}
+
+/*
+ * eclass_member_iterator_strict_next
+ * Fetch the next EquivalenceMember from an EquivalenceMemberIterator
+ * which was set up by setup_eclass_member_strict_iterator(). Returns
+ * NULL when there are no more matching EquivalenceMembers.
+ */
+EquivalenceMember *
+eclass_member_iterator_strict_next(EquivalenceMemberIterator *iter)
+{
+ /* Fail if this was used instead of eclass_member_iterator_next */
+ Assert(iter->isstrict);
+
+ if (iter->use_index)
+ {
+ iter->current_index = bms_next_member(iter->matching_ems,
+ iter->current_index);
+ if (iter->current_index >= 0)
+ return list_nth_node(EquivalenceMember, iter->root->eq_members,
+ iter->current_index);
+ return NULL;
+ }
+ else
+ {
+ ListCell *lc;
+
+ for_each_from(lc, iter->eclass->ec_members, iter->current_index + 1)
+ {
+ EquivalenceMember *em = lfirst_node(EquivalenceMember, lc);
+
+ iter->current_index = foreach_current_index(lc);
+
+ /*
+ * Some users of this iterator will be adding new
+ * EquivalenceMember during the loop. We must ensure we don't
+ * return those, so here we return NULL when the loop index goes
+ * beyond the original length of the ec_members list.
+ */
+ if (iter->current_index >= iter->orig_length)
+ return NULL;
+
+ /* don't return child members when with_children==false */
+ if (!iter->with_children && em->em_is_child)
+ continue;
+
+ /*
+ * When with_norel_members==true, make sure we return all members
+ * without Vars.
+ */
+ if (iter->with_norel_members && em->em_norel_expr)
+ return em;
+
+ /*
+ * Don't match members where em_relids that don't contain all rels
+ * mentioned in with_relids.
+ */
+ if (iter->relids_empty ||
+ !bms_is_subset(iter->with_relids, em->em_relids))
+ continue;
+
+ return em;
+ }
+ return NULL;
+ }
+}
+
+/*
+ * eclass_member_iterator_dispose
+ * Free any memory allocated by the iterator
+ */
+void
+eclass_member_iterator_dispose(EquivalenceMemberIterator *iter)
+{
+ bms_free(iter->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 *rel_esis = NULL;
+ int i = -1;
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rel_esis = bms_add_members(rel_esis, rte->eclass_source_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ i = -1;
+ while ((i = bms_next_member(rel_esis, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
+ i);
+
+ Assert(bms_overlap(relids, rinfo->clause_relids));
+ }
+#endif
+
+ /* bitwise-AND to leave only the ones for this EquivalenceClass */
+ return bms_int_members(rel_esis, ec->ec_source_indexes);
+}
+
+/*
+ * get_ec_source_indexes_strict
+ * Returns a Bitmapset with indexes into root->eq_sources for all
+ * RestrictInfos in 'ec' that have
+ * bms_is_subset(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
+ Relids relids)
+{
+ Bitmapset *esis = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ /*
+ * bms_intersect to the first relation to try to keep the resulting
+ * Bitmapset as small as possible. This saves having to make a
+ * complete bms_copy() of one of them. One may contain significantly
+ * more words than the other.
+ */
+ esis = bms_intersect(ec->ec_source_indexes,
+ rte->eclass_source_indexes);
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ rte = root->simple_rte_array[i];
+ esis = bms_int_members(esis, rte->eclass_source_indexes);
+ }
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ i = -1;
+ while ((i = bms_next_member(esis, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
+ i);
+
+ Assert(bms_is_subset(relids, rinfo->clause_relids));
+ }
+#endif
+
+ return esis;
+}
+
+/*
+ * get_ec_derive_indexes
+ * Returns a Bitmapset with indexes into root->eq_derives for all
+ * RestrictInfos in 'ec' that have
+ * bms_overlap(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ *
+ * XXX is this function even needed?
+ */
+Bitmapset *
+get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+{
+ Bitmapset *rel_edis = NULL;
+ int i = -1;
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ rel_edis = bms_add_members(rel_edis, rte->eclass_derive_indexes);
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ i = -1;
+ while ((i = bms_next_member(rel_edis, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
+ i);
+
+ Assert(bms_overlap(relids, rinfo->clause_relids));
+ }
+#endif
+
+ /* bitwise-AND to leave only the ones for this EquivalenceClass */
+ return bms_int_members(rel_edis, ec->ec_derive_indexes);
+}
+
+/*
+ * get_ec_derive_indexes_strict
+ * Returns a Bitmapset with indexes into root->eq_derives for all
+ * RestrictInfos in 'ec' that have
+ * bms_is_subset(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
+ Relids relids)
+{
+ Bitmapset *edis = NULL;
+ int i = bms_next_member(relids, -1);
+
+ if (i >= 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[i];
+
+ /*
+ * bms_intersect to the first relation to try to keep the resulting
+ * Bitmapset as small as possible. This saves having to make a
+ * complete bms_copy() of one of them. One may contain significantly
+ * more words than the other.
+ */
+ edis = bms_intersect(ec->ec_derive_indexes,
+ rte->eclass_derive_indexes);
+
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ rte = root->simple_rte_array[i];
+ edis = bms_int_members(edis, rte->eclass_derive_indexes);
+ }
+ }
+
+#ifdef USE_ASSERT_CHECKING
+ /* verify the results look sane */
+ i = -1;
+ while ((i = bms_next_member(edis, i)) >= 0)
+ {
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
+ i);
+
+ Assert(bms_is_subset(relids, rinfo->clause_relids));
+ }
+#endif
+
+ return edis;
+}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 5f428e835b0..f658041f6b0 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -190,8 +190,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);
@@ -934,7 +934,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
* query_pathkeys will allow an incremental sort to be considered on
* the index's partially sorted results.
*/
- match_pathkeys_to_index(index, root->query_pathkeys,
+ match_pathkeys_to_index(root, index, root->query_pathkeys,
&orderbyclauses,
&orderbyclausecols);
if (list_length(root->query_pathkeys) == list_length(orderbyclauses))
@@ -3726,8 +3726,8 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* item in the given 'pathkeys' list.
*/
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)
{
ListCell *lc1;
@@ -3742,8 +3742,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;
/* Pathkey must request default sort order for the target opfamily */
@@ -3763,9 +3764,16 @@ 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,
+ root->simple_rte_array[index->rel->relid]
+ ->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 154eb505d75..59e3f8c136d 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1141,18 +1141,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)
{
@@ -1684,7 +1685,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
EquivalenceClass *oeclass;
int score;
- ListCell *lc2;
+ int i;
/* get the outer eclass */
update_mergeclause_eclasses(root, rinfo);
@@ -1705,13 +1706,16 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
/* compute score */
score = 0;
- foreach(lc2, oeclass->ec_members)
+ i = -1;
+ while ((i = bms_next_member(oeclass->ec_nonchild_indexes, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+ EquivalenceMember *em = list_nth_node(EquivalenceMember,
+ root->eq_members, i);
- /* Potential future join partner? */
- if (!em->em_is_const && !em->em_is_child &&
- !bms_overlap(em->em_relids, joinrel->relids))
+ /* shouldn't be consts or child members in ec_nonchild_indexes */
+ Assert(!em->em_is_const && !em->em_is_child);
+
+ if (!bms_overlap(em->em_relids, joinrel->relids))
score++;
}
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index b33fc671775..fa5eb40d34d 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -38,7 +38,7 @@ static void remove_rel_from_query(PlannerInfo *root, int relid,
SpecialJoinInfo *sjinfo);
static void remove_rel_from_restrictinfo(RestrictInfo *rinfo,
int relid, int ojrelid);
-static void remove_rel_from_eclass(EquivalenceClass *ec,
+static void remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec,
int relid, int ojrelid);
static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
@@ -474,7 +474,7 @@ remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
if (bms_is_member(relid, ec->ec_relids) ||
bms_is_member(ojrelid, ec->ec_relids))
- remove_rel_from_eclass(ec, relid, ojrelid);
+ remove_rel_from_eclass(root, ec, relid, ojrelid);
}
/*
@@ -607,9 +607,11 @@ remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
* level(s).
*/
static void
-remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
+remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec, int relid,
+ int ojrelid)
{
ListCell *lc;
+ int i;
/* Fix up the EC's overall relids */
ec->ec_relids = bms_del_member(ec->ec_relids, relid);
@@ -627,18 +629,41 @@ remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
if (bms_is_member(relid, cur_em->em_relids) ||
bms_is_member(ojrelid, cur_em->em_relids))
{
+ RangeTblEntry *rte;
+
Assert(!cur_em->em_is_const);
+
+ /* Delete 'relid' from em_relids */
cur_em->em_relids = bms_del_member(cur_em->em_relids, relid);
+ rte = root->simple_rte_array[relid];
+ rte->eclass_member_indexes =
+ bms_del_member(rte->eclass_member_indexes, cur_em->em_index);
+
+ /* Delete 'ojrelid' from em_relids */
cur_em->em_relids = bms_del_member(cur_em->em_relids, ojrelid);
+ rte = root->simple_rte_array[ojrelid];
+ rte->eclass_member_indexes =
+ bms_del_member(rte->eclass_member_indexes, cur_em->em_index);
+
if (bms_is_empty(cur_em->em_relids))
+ {
+ /* Delete this EquivalenceMember with updating indexes */
ec->ec_members = foreach_delete_current(ec->ec_members, lc);
+ ec->ec_member_indexes =
+ bms_del_member(ec->ec_member_indexes, cur_em->em_index);
+ ec->ec_nonchild_indexes =
+ bms_del_member(ec->ec_nonchild_indexes, cur_em->em_index);
+ ec->ec_norel_indexes =
+ bms_del_member(ec->ec_norel_indexes, cur_em->em_index);
+ }
}
}
/* Fix up the source clauses, in case we can re-use them later */
- foreach(lc, ec->ec_sources)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_source_indexes, i)) >= 0)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
}
@@ -648,7 +673,7 @@ remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
* drop them. (At this point, any such clauses would be base restriction
* clauses, which we'd not need anymore anyway.)
*/
- ec->ec_derives = NIL;
+ ec->ec_derive_indexes = NULL;
}
/*
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 1caad5f3a61..2023f8d280e 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -264,8 +264,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,
@@ -273,10 +273,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);
@@ -297,7 +300,7 @@ static Group *make_group(List *tlist, List *qual, int numGroupCols,
AttrNumber *grpColIdx, Oid *grpOperators, Oid *grpCollations,
Plan *lefttree);
static Unique *make_unique_from_sortclauses(Plan *lefttree, List *distinctList);
-static Unique *make_unique_from_pathkeys(Plan *lefttree,
+static Unique *make_unique_from_pathkeys(PlannerInfo *root, Plan *lefttree,
List *pathkeys, int numCols);
static Gather *make_gather(List *qptlist, List *qpqual,
int nworkers, int rescan_param, bool single_copy, Plan *subplan);
@@ -1285,7 +1288,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,
@@ -1329,7 +1333,7 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
* don't need an explicit sort, to make sure they are returning
* the same sort key columns the Append expects.
*/
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
subpath->parent->relids,
nodeSortColIdx,
false,
@@ -1470,7 +1474,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
* function result; it must be the same plan node. However, we then need
* to detect whether any tlist entries were added.
*/
- (void) prepare_sort_from_pathkeys(plan, pathkeys,
+ (void) prepare_sort_from_pathkeys(root, plan, pathkeys,
best_path->path.parent->relids,
NULL,
true,
@@ -1501,7 +1505,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
/* Compute sort column info, and adjust subplan's tlist as needed */
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
subpath->parent->relids,
node->sortColIdx,
false,
@@ -1981,7 +1985,7 @@ create_gather_merge_plan(PlannerInfo *root, GatherMergePath *best_path)
Assert(pathkeys != NIL);
/* Compute sort column info, and adjust subplan's tlist as needed */
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
best_path->subpath->parent->relids,
gm_plan->sortColIdx,
false,
@@ -2195,7 +2199,7 @@ create_sort_plan(PlannerInfo *root, SortPath *best_path, int flags)
* relids. Thus, if this sort path is based on a child relation, we must
* pass its relids.
*/
- plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys,
+ plan = make_sort_from_pathkeys(root, subplan, best_path->path.pathkeys,
IS_OTHER_REL(best_path->subpath->parent) ?
best_path->path.parent->relids : NULL);
@@ -2219,7 +2223,7 @@ create_incrementalsort_plan(PlannerInfo *root, IncrementalSortPath *best_path,
/* See comments in create_sort_plan() above */
subplan = create_plan_recurse(root, best_path->spath.subpath,
flags | CP_SMALL_TLIST);
- plan = make_incrementalsort_from_pathkeys(subplan,
+ plan = make_incrementalsort_from_pathkeys(root, subplan,
best_path->spath.path.pathkeys,
IS_OTHER_REL(best_path->spath.subpath->parent) ?
best_path->spath.path.parent->relids : NULL,
@@ -2288,7 +2292,7 @@ create_upper_unique_plan(PlannerInfo *root, UpperUniquePath *best_path, int flag
subplan = create_plan_recurse(root, best_path->subpath,
flags | CP_LABEL_TLIST);
- plan = make_unique_from_pathkeys(subplan,
+ plan = make_unique_from_pathkeys(root, subplan,
best_path->path.pathkeys,
best_path->numkeys);
@@ -4554,7 +4558,8 @@ create_mergejoin_plan(PlannerInfo *root,
if (!use_incremental_sort)
{
sort_plan = (Plan *)
- make_sort_from_pathkeys(outer_plan,
+ make_sort_from_pathkeys(root,
+ outer_plan,
best_path->outersortkeys,
outer_relids);
@@ -4563,7 +4568,8 @@ create_mergejoin_plan(PlannerInfo *root,
else
{
sort_plan = (Plan *)
- make_incrementalsort_from_pathkeys(outer_plan,
+ make_incrementalsort_from_pathkeys(root,
+ outer_plan,
best_path->outersortkeys,
outer_relids,
presorted_keys);
@@ -4588,7 +4594,7 @@ create_mergejoin_plan(PlannerInfo *root,
*/
Relids inner_relids = inner_path->parent->relids;
- Sort *sort = make_sort_from_pathkeys(inner_plan,
+ Sort *sort = make_sort_from_pathkeys(root, inner_plan,
best_path->innersortkeys,
inner_relids);
@@ -6238,7 +6244,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,
@@ -6305,7 +6312,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 */
@@ -6333,7 +6340,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 */
@@ -6349,7 +6356,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;
@@ -6420,7 +6427,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;
@@ -6429,7 +6437,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,
@@ -6455,7 +6465,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;
@@ -6465,7 +6476,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,
@@ -6824,7 +6837,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;
@@ -6887,7 +6901,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/planagg.c b/src/backend/optimizer/plan/planagg.c
index 64605be3178..ca5cb79a680 100644
--- a/src/backend/optimizer/plan/planagg.c
+++ b/src/backend/optimizer/plan/planagg.c
@@ -356,6 +356,7 @@ build_minmax_path(PlannerInfo *root, MinMaxAggInfo *mminfo,
Assert(subroot->join_info_list == NIL);
/* and we haven't made equivalence classes, either */
Assert(subroot->eq_classes == NIL);
+ Assert(root->eq_members == NIL);
/* and we haven't created PlaceHolderInfos, either */
Assert(subroot->placeholder_list == NIL);
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index e92e108b6b6..f25a6ece2fc 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -661,6 +661,9 @@ subquery_planner(PlannerGlobal *glob, Query *parse, PlannerInfo *parent_root,
root->multiexpr_params = NIL;
root->join_domains = NIL;
root->eq_classes = NIL;
+ root->eq_members = NIL;
+ root->eq_sources = NIL;
+ root->eq_derives = NIL;
root->ec_merging_done = false;
root->last_rinfo_serial = 0;
root->all_result_relids =
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 82775a3dd51..3bbace3329d 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -1153,6 +1153,9 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
subroot->multiexpr_params = NIL;
subroot->join_domains = NIL;
subroot->eq_classes = NIL;
+ subroot->eq_members = NIL;
+ subroot->eq_sources = NIL;
+ subroot->eq_derives = NIL;
subroot->ec_merging_done = false;
subroot->last_rinfo_serial = 0;
subroot->all_result_relids = NULL;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 7c27dc24e21..8d6678e9922 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -37,7 +37,7 @@
#include "parser/parse_coerce.h"
#include "utils/selfuncs.h"
-
+static void setup_append_rel_entry(PlannerInfo *root);
static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
SetOperationStmt *parentOp,
List *colTypes, List *colCollations,
@@ -117,6 +117,7 @@ plan_set_operations(PlannerInfo *root)
* merging. Mark that merging is complete to allow us to make pathkeys.
*/
Assert(root->eq_classes == NIL);
+ Assert(root->eq_members == NIL);
root->ec_merging_done = true;
/*
@@ -138,6 +139,8 @@ plan_set_operations(PlannerInfo *root)
leftmostQuery = leftmostRTE->subquery;
Assert(leftmostQuery != NULL);
+ setup_append_rel_entry(root);
+
/*
* If the topmost node is a recursive union, it needs special processing.
*/
@@ -170,6 +173,26 @@ plan_set_operations(PlannerInfo *root)
return setop_rel;
}
+/*
+ * setup_append_rel_entry
+ * Add entry into root's simple_rte_array at element 0. This is required
+ * because generate_append_tlist() makes Vars with varno=0. In
+ * add_eq_member() we need to index EquivalenceMembers belonging to this
+ * relation.
+ */
+static void
+setup_append_rel_entry(PlannerInfo *root)
+{
+ RangeTblEntry *rte = makeNode(RangeTblEntry);
+
+ memset(rte, 0, sizeof(RangeTblEntry));
+ rte->eclass_member_indexes = NULL;
+
+ /* make sure nothing else has made use of this element */
+ Assert(root->simple_rte_array[0] == NULL);
+ root->simple_rte_array[0] = rte;
+}
+
/*
* recurse_set_operations
* Recursively handle one step in a tree of set operations
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index 17e51cd75d7..a5d9357bc68 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -491,6 +491,14 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
*/
childrte = makeNode(RangeTblEntry);
memcpy(childrte, parentrte, sizeof(RangeTblEntry));
+ /*
+ * We do not want to inherit the EquivalenceMember indexes of the parent
+ * to its child
+ */
+ childrte->eclass_member_indexes = NULL;
+ childrte->eclass_source_indexes = NULL;
+ childrte->eclass_derive_indexes = NULL;
+
Assert(parentrte->rtekind == RTE_RELATION); /* else this is dubious */
childrte->relid = childOID;
childrte->relkind = childrel->rd_rel->relkind;
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 38d6ad7dcbd..2be219ff36b 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -1247,6 +1247,15 @@ typedef struct RangeTblEntry
bool inFromCl pg_node_attr(query_jumble_ignore);
/* security barrier quals to apply, if any */
List *securityQuals pg_node_attr(query_jumble_ignore);
+ Bitmapset *eclass_member_indexes; /* Indexes in PlannerInfo's eq_members
+ * list of EquivalenceMembers that
+ * mention this relation */
+ Bitmapset *eclass_source_indexes; /* Indexes in PlannerInfo's eq_sources
+ * list for RestrictInfos that mention
+ * this relation */
+ Bitmapset *eclass_derive_indexes; /* Indexes in PlannerInfo's eq_derives
+ * list for RestrictInfos that mention
+ * this relation */
} RangeTblEntry;
/*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 54ee17697e5..8be0b00df15 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -313,6 +313,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;
@@ -950,6 +959,7 @@ typedef struct RelOptInfo
double allvisfrac;
/* indexes in PlannerInfo's eq_classes list of ECs that mention this rel */
Bitmapset *eclass_indexes;
+
PlannerInfo *subroot; /* if subquery */
List *subplan_params; /* if subquery */
/* wanted number of parallel workers */
@@ -1376,6 +1386,39 @@ typedef struct JoinDomain
* entry: consider SELECT random() AS a, random() AS b ... ORDER BY b,a.
* So we record the SortGroupRef of the originating sort clause.
*
+ * At various locations in the query planner, we must search for
+ * EquivalenceMembers within a given EquivalenceClass. For the common case,
+ * an EquivalenceClass does not have a large number of EquivalenceMembers,
+ * however, in cases such as planning queries to partitioned tables, the number
+ * of members can become large. To maintain planning performance, we make use
+ * of a bitmap index to allow us to quickly find EquivalenceMembers in a given
+ * EquivalenceClass belonging to a given relation or set of relations. This
+ * is done by storing a list of EquivalenceMembers belonging to all
+ * EquivalenceClasses in PlannerInfo and storing a Bitmapset for each
+ * RelOptInfo which has a bit set for each EquivalenceMember in that list
+ * which relates to the given relation. We also store a Bitmapset to mark all
+ * of the indexes in the PlannerInfo's list of EquivalenceMembers in the
+ * EquivalenceClass. We can quickly find the interesting indexes into the
+ * PlannerInfo's list by performing a bit-wise AND on the RelOptInfo's
+ * Bitmapset and the EquivalenceClasses.
+ *
+ * To further speed up the lookup of EquivalenceMembers we also record the
+ * non-child indexes. This allows us to deal with fewer bits for searches
+ * that don't require "is_child" EquivalenceMembers. We must also store the
+ * indexes into EquivalenceMembers which have no relids mentioned as some
+ * searches require that.
+ *
+ * Additionally, we also store the EquivalenceMembers of a given
+ * EquivalenceClass in the ec_members list. Technically, we could obtain this
+ * from looking at the bits in ec_member_indexes, however, finding all members
+ * of a given EquivalenceClass is common enough that it pays to have fast
+ * access to a dense list containing all members.
+ *
+ * The source and derived RestrictInfos are indexed in a similar method,
+ * although we don't maintain a List in the EquivalenceClass for these. These
+ * must be looked up in PlannerInfo using the ec_source_indexes and
+ * ec_derive_indexes Bitmapsets.
+ *
* NB: if ec_merged isn't NULL, this class has been merged into another, and
* should be ignored in favor of using the pointed-to class.
*
@@ -1393,9 +1436,19 @@ 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 */
+ List *ec_members; /* list of EquivalenceMembers in the class */
+ 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? */
@@ -1443,8 +1496,10 @@ typedef struct EquivalenceMember
NodeTag type;
Expr *em_expr; /* the expression represented */
- Relids em_relids; /* all relids appearing in em_expr */
- bool em_is_const; /* expression is pseudoconstant? */
+ int em_index; /* index in root->eq_members */
+ Relids em_relids; /* relids for this member */
+ bool em_is_const; /* is em_relids empty? */
+ bool em_norel_expr; /* true if em_expr contains no Vars */
bool em_is_child; /* derived version for a child relation? */
Oid em_datatype; /* the "nominal type" used by the opfamily */
JoinDomain *em_jdomain; /* join domain containing the source clause */
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index a872fc501e0..7bc29752b85 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -680,6 +680,7 @@ extern pg_nodiscard List *list_copy_deep(const List *oldlist);
typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
extern void list_sort(List *list, list_sort_comparator cmp);
+extern int list_ptr_cmp(const ListCell *p1, const ListCell *p2);
extern int list_int_cmp(const ListCell *p1, const ListCell *p2);
extern int list_oid_cmp(const ListCell *p1, const ListCell *p2);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 46955d128f0..140027ab21f 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -116,6 +116,31 @@ extern void init_dummy_sjinfo(SpecialJoinInfo *sjinfo, Relids left_relids,
* equivclass.c
* routines for managing EquivalenceClasses
*/
+
+/*
+ * EquivalenceMemberIterator
+ * Data structure used for iteration over an EquivalenceClass's
+ * EquivalenceMember in order to quickly find the members matching our
+ * search pattern.
+ */
+typedef struct EquivalenceMemberIterator
+{
+ bool use_index; /* use matching_ems index? */
+ bool relids_empty; /* is with_relids empty? */
+ bool with_children; /* include em_is_child members? */
+ bool with_norel_members; /* include members with empty em_relids */
+#ifdef USE_ASSERT_CHECKING
+ bool isstrict; /* ensure the correct next function is used */
+#endif
+ int orig_length; /* elements in eclass->ec_members at the start */
+ int current_index; /* current iterator position, or -1. */
+ Relids with_relids; /* relids to match in em_relids */
+ PlannerInfo *root; /* PlannerInfo the eclass belongs to */
+ EquivalenceClass *eclass; /* the EquivalenceClass we're looking at */
+ Bitmapset *matching_ems; /* when use_index == true, these are the
+ * matching indexes in root eq_members */
+} EquivalenceMemberIterator;
+
typedef bool (*ec_matches_callback_type) (PlannerInfo *root,
RelOptInfo *rel,
EquivalenceClass *ec,
@@ -137,7 +162,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,
@@ -164,7 +190,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,
@@ -194,6 +221,42 @@ 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 void setup_eclass_member_iterator(EquivalenceMemberIterator *iter,
+ PlannerInfo *root,
+ EquivalenceClass *ec, Relids relids,
+ bool with_children,
+ bool with_norel_members);
+extern void setup_eclass_member_strict_iterator(EquivalenceMemberIterator *iter,
+ PlannerInfo *root,
+ EquivalenceClass *ec,
+ Relids relids,
+ bool with_children,
+ bool with_norel_members);
+extern EquivalenceMember *eclass_member_iterator_next(EquivalenceMemberIterator *iter);
+extern EquivalenceMember *eclass_member_iterator_strict_next(EquivalenceMemberIterator *iter);
+extern void eclass_member_iterator_dispose(EquivalenceMemberIterator *iter);
+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/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index e1c4f913f84..f44ab1c2140 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -687,6 +687,7 @@ EphemeralNamedRelationMetadata
EphemeralNamedRelationMetadataData
EquivalenceClass
EquivalenceMember
+EquivalenceMemberIterator
ErrorContextCallback
ErrorData
ErrorSaveContext