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