On Wed, 27 Jul 2022 at 18:07, Yuya Watari <watari.y...@gmail.com> wrote:
> I agree that introducing a Bitmapset field may solve this problem. I
> will try this approach in addition to previous ones.
I've attached a very half-done patch that might help you get started
on this. There are still 2 failing regression tests which seem to be
due to plan changes. I didn't expend any effort looking into why these
plans changed.
The attached does not contain any actual optimizations to find the
minimal set of EMs to loop through by masking the Bitmapsets that I
mentioned in my post last night. I just quickly put it together to
see if there's some hole in the idea. I don't think there is.
I've not really considered all of the places that we'll want to do the
bit twiddling to get the minimal set of EquivalenceMember. I did see
there's a couple more functions in postgres_fdw.c that could be
optimized.
One thing I've only partially thought about is what if you want to
also find EquivalenceMembers with a constant value. If there's a
Const, then you'll lose the bit for that when you mask the ec's
ec_member_indexes with the RelOptInfos. If there are some places
where we need to keep those then I think we'll need to add another
field to EquivalenceClass to mark the index into PlannerInfo's
eq_members for the EquivalenceMember with the Const. That bit would
have to be bms_add_member()ed back into the Bitmapset of matching
EquivalenceMembers after masking out RelOptInfo's ec_member_indexes.
When adding the optimizations to find the minimal set of EM bits to
search through, you should likely add some functions similar to the
get_eclass_indexes_for_relids() and get_common_eclass_indexes()
functions to help you find the minimal set of bits. You can also
probably get some other inspiration from [1], in general.
David
[1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=3373c715535
diff --git a/contrib/postgres_fdw/postgres_fdw.c
b/contrib/postgres_fdw/postgres_fdw.c
index 048db542d3..0af3943e03 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7410,11 +7410,11 @@ conversion_error_callback(void *arg)
EquivalenceMember *
find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
{
- ListCell *lc;
+ int i = -1;
- foreach(lc, ec->ec_members)
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *em = (EquivalenceMember *)
list_nth(root->eq_members, i);
/*
* Note we require !bms_is_empty, else we'd accept constant
@@ -7453,7 +7453,7 @@ find_em_for_rel_target(PlannerInfo *root,
EquivalenceClass *ec,
{
Expr *expr = (Expr *) lfirst(lc1);
Index sgref = get_pathtarget_sortgroupref(target, i);
- ListCell *lc2;
+ int i;
/* Ignore non-sort expressions */
if (sgref == 0 ||
@@ -7469,9 +7469,10 @@ find_em_for_rel_target(PlannerInfo *root,
EquivalenceClass *ec,
expr = ((RelabelType *) expr)->arg;
/* Locate an EquivalenceClass member matching this expr, if any
*/
- foreach(lc2, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Expr *em_expr;
/* Don't match constants */
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index a96f2ee8c6..2060b73686 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -430,7 +430,7 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass
*node)
WRITE_NODE_FIELD(ec_opfamilies);
WRITE_OID_FIELD(ec_collation);
- WRITE_NODE_FIELD(ec_members);
+ WRITE_BITMAPSET_FIELD(ec_member_indexes);
WRITE_NODE_FIELD(ec_sources);
WRITE_NODE_FIELD(ec_derives);
WRITE_BITMAPSET_FIELD(ec_relids);
diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c
index a5c44adc6c..5953b79fe8 100644
--- a/src/backend/nodes/print.c
+++ b/src/backend/nodes/print.c
@@ -423,16 +423,17 @@ print_expr(const Node *expr, const List *rtable)
* pathkeys list of PathKeys
*/
void
-print_pathkeys(const List *pathkeys, const List *rtable)
+print_pathkeys(const PlannerInfo *root, const List *pathkeys,
+ const List *rtable)
{
- const ListCell *i;
+ const ListCell *lc;
printf("(");
- foreach(i, pathkeys)
+ foreach(lc, pathkeys)
{
- PathKey *pathkey = (PathKey *) lfirst(i);
+ PathKey *pathkey = (PathKey *) lfirst(lc);
EquivalenceClass *eclass;
- ListCell *k;
+ int i;
bool first = true;
eclass = pathkey->pk_eclass;
@@ -441,9 +442,10 @@ print_pathkeys(const List *pathkeys, const List *rtable)
eclass = eclass->ec_merged;
printf("(");
- foreach(k, eclass->ec_members)
+ i = -1;
+ while ((i = bms_next_member(eclass->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *mem = (EquivalenceMember *)
lfirst(k);
+ EquivalenceMember *mem = (EquivalenceMember *)
list_nth(root->eq_members, i);
if (first)
first = false;
@@ -452,7 +454,7 @@ print_pathkeys(const List *pathkeys, const List *rtable)
print_expr((Node *) mem->em_expr, rtable);
}
printf(")");
- if (lnext(pathkeys, i))
+ if (lnext(pathkeys, lc))
printf(", ");
}
printf(")\n");
diff --git a/src/backend/optimizer/path/allpaths.c
b/src/backend/optimizer/path/allpaths.c
index 63f0f6b79c..caba68b839 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -4539,7 +4539,7 @@ print_path(PlannerInfo *root, Path *path, int indent)
for (i = 0; i < indent; i++)
printf("\t");
printf(" pathkeys: ");
- print_pathkeys(path->pathkeys, root->parse->rtable);
+ print_pathkeys(root, path->pathkeys, root->parse->rtable);
}
if (join)
diff --git a/src/backend/optimizer/path/costsize.c
b/src/backend/optimizer/path/costsize.c
index fb28e6411a..1043b67aca 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1986,12 +1986,14 @@ compute_cpu_sort_cost(PlannerInfo *root, List
*pathkeys, int nPresortedKeys,
double nGroups,
correctedNGroups;
Cost funcCost = 1.0;
+ int first_em;
/*
* We believe that equivalence members aren't very different,
so, to
* estimate cost we consider just the first member.
*/
- em = (EquivalenceMember *)
linitial(pathkey->pk_eclass->ec_members);
+ first_em =
bms_next_member(pathkey->pk_eclass->ec_member_indexes, -1);
+ em = (EquivalenceMember *) list_nth(root->eq_members, first_em);
if (em->em_datatype != InvalidOid)
{
@@ -2326,8 +2328,9 @@ cost_incremental_sort(Path *path,
foreach(l, pathkeys)
{
PathKey *key = (PathKey *) lfirst(l);
+ int first_em =
bms_next_member(key->pk_eclass->ec_member_indexes, -1);
EquivalenceMember *member = (EquivalenceMember *)
- linitial(key->pk_eclass->ec_members);
+ list_nth(root->eq_members, first_em);
/*
* Check if the expression contains Var with "varno 0" so that
we
diff --git a/src/backend/optimizer/path/equivclass.c
b/src/backend/optimizer/path/equivclass.c
index 60c0e3f108..0e46c05287 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -32,7 +32,7 @@
#include "utils/lsyscache.h"
-static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
+static EquivalenceMember *add_eq_member(PlannerInfo *root, EquivalenceClass
*ec,
Expr *expr, Relids relids, Relids nullable_relids,
bool is_child, Oid datatype);
static bool is_exprlist_member(Expr *node, List *exprs);
@@ -139,6 +139,7 @@ process_equivalence(PlannerInfo *root,
*em2;
ListCell *lc1;
int ec2_idx;
+ int i;
/* Should not already be marked as having generated an eclass */
Assert(restrictinfo->left_ec == NULL);
@@ -265,7 +266,6 @@ process_equivalence(PlannerInfo *root,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
- ListCell *lc2;
/* Never match to a volatile EC */
if (cur_ec->ec_has_volatile)
@@ -286,9 +286,10 @@ process_equivalence(PlannerInfo *root,
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Assert(!cur_em->em_is_child); /* no children yet */
@@ -364,7 +365,7 @@ process_equivalence(PlannerInfo *root,
* PathKeys. We leave it behind with a link so that the merged
EC can
* be found.
*/
- ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
+ ec1->ec_member_indexes =
bms_add_members(ec1->ec_member_indexes, ec2->ec_member_indexes);
ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
@@ -378,7 +379,7 @@ process_equivalence(PlannerInfo *root,
ec2->ec_merged = ec1;
root->eq_classes = list_delete_nth_cell(root->eq_classes,
ec2_idx);
/* just to avoid debugging confusion w/ dangling pointers: */
- ec2->ec_members = NIL;
+ ec2->ec_member_indexes = NULL;
ec2->ec_sources = NIL;
ec2->ec_derives = NIL;
ec2->ec_relids = NULL;
@@ -398,8 +399,8 @@ process_equivalence(PlannerInfo *root,
else if (ec1)
{
/* Case 3: add item2 to ec1 */
- em2 = add_eq_member(ec1, item2, item2_relids,
item2_nullable_relids,
- false, item2_type);
+ em2 = add_eq_member(root, ec1, item2, item2_relids,
+ item2_nullable_relids,
false, item2_type);
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_below_outer_join |= below_outer_join;
ec1->ec_min_security = Min(ec1->ec_min_security,
@@ -416,8 +417,8 @@ process_equivalence(PlannerInfo *root,
else if (ec2)
{
/* Case 3: add item1 to ec2 */
- em1 = add_eq_member(ec2, item1, item1_relids,
item1_nullable_relids,
- false, item1_type);
+ em1 = add_eq_member(root, ec2, item1, item1_relids,
+ item1_nullable_relids,
false, item1_type);
ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
ec2->ec_below_outer_join |= below_outer_join;
ec2->ec_min_security = Min(ec2->ec_min_security,
@@ -438,7 +439,7 @@ process_equivalence(PlannerInfo *root,
ec->ec_opfamilies = opfamilies;
ec->ec_collation = collation;
- ec->ec_members = NIL;
+ ec->ec_member_indexes = NULL;
ec->ec_sources = list_make1(restrictinfo);
ec->ec_derives = NIL;
ec->ec_relids = NULL;
@@ -450,10 +451,10 @@ process_equivalence(PlannerInfo *root,
ec->ec_min_security = restrictinfo->security_level;
ec->ec_max_security = restrictinfo->security_level;
ec->ec_merged = NULL;
- em1 = add_eq_member(ec, item1, item1_relids,
item1_nullable_relids,
- false, item1_type);
- em2 = add_eq_member(ec, item2, item2_relids,
item2_nullable_relids,
- false, item2_type);
+ em1 = add_eq_member(root, ec, item1, item1_relids,
+ item1_nullable_relids,
false, item1_type);
+ em2 = add_eq_member(root, ec, item2, item2_relids,
+ item2_nullable_relids,
false, item2_type);
root->eq_classes = lappend(root->eq_classes, ec);
@@ -542,10 +543,13 @@ canonicalize_ec_expression(Expr *expr, Oid req_type, Oid
req_collation)
* add_eq_member - build a new EquivalenceMember and add it to an EC
*/
static EquivalenceMember *
-add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
- Relids nullable_relids, bool is_child, Oid datatype)
+add_eq_member(PlannerInfo *root, EquivalenceClass *ec, Expr *expr,
+ Relids relids, Relids nullable_relids, bool is_child,
+ Oid datatype)
{
EquivalenceMember *em = makeNode(EquivalenceMember);
+ int em_index;
+ int i;
em->em_expr = expr;
em->em_relids = relids;
@@ -573,7 +577,17 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids
relids,
{
ec->ec_relids = bms_add_members(ec->ec_relids, relids);
}
- ec->ec_members = lappend(ec->ec_members, em);
+ em_index = list_length(root->eq_members);
+ ec->ec_member_indexes = bms_add_member(ec->ec_member_indexes, em_index);
+ root->eq_members = lappend(root->eq_members, em);
+
+ i = -1;
+ while ((i = bms_next_member(relids, i)) > 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+
+ rel->eclass_member_indexes =
bms_add_member(rel->eclass_member_indexes, em_index);
+ }
return em;
}
@@ -645,7 +659,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
- ListCell *lc2;
+ int i;
/*
* Never match to a volatile EC, except when we are looking at
another
@@ -660,9 +674,10 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
/*
* Ignore child members unless they match the request.
@@ -710,7 +725,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
newec = makeNode(EquivalenceClass);
newec->ec_opfamilies = list_copy(opfamilies);
newec->ec_collation = collation;
- newec->ec_members = NIL;
+ newec->ec_member_indexes = NULL;
newec->ec_sources = NIL;
newec->ec_derives = NIL;
newec->ec_relids = NULL;
@@ -732,7 +747,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
expr_relids = pull_varnos(root, (Node *) expr);
nullable_relids = bms_intersect(nullable_relids, expr_relids);
- newem = add_eq_member(newec, copyObject(expr), expr_relids,
+ newem = add_eq_member(root, newec, copyObject(expr), expr_relids,
nullable_relids, false,
opcintype);
/*
@@ -794,19 +809,21 @@ 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;
+ int i;
/* We ignore binary-compatible relabeling on both ends */
while (expr && IsA(expr, RelabelType))
expr = ((RelabelType *) expr)->arg;
- foreach(lc, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Expr *emexpr;
/*
@@ -865,11 +882,11 @@ find_computable_ec_member(PlannerInfo *root,
Relids relids,
bool require_parallel_safe)
{
- ListCell *lc;
+ int i = -1;
- foreach(lc, ec->ec_members)
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *em = (EquivalenceMember *)
list_nth(root->eq_members, i);
List *exprvars;
ListCell *lc2;
@@ -976,7 +993,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;
@@ -1096,7 +1113,7 @@ generate_base_implied_equalities(PlannerInfo *root)
* Single-member ECs won't generate any deductions, either here
or at
* the join level.
*/
- if (list_length(ec->ec_members) > 1)
+ if (bms_membership(ec->ec_member_indexes) == BMS_MULTIPLE)
{
if (ec->ec_has_const)
generate_base_implied_equalities_const(root,
ec);
@@ -1145,7 +1162,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
EquivalenceClass *ec)
{
EquivalenceMember *const_em = NULL;
- ListCell *lc;
+ int i;
/*
* In the trivial case where we just had one "var = const" clause, push
@@ -1154,7 +1171,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
* re-build and re-analyze an equality clause that will be exactly
* equivalent to the old one.
*/
- if (list_length(ec->ec_members) == 2 &&
+ if (bms_num_members(ec->ec_member_indexes) == 2 &&
list_length(ec->ec_sources) == 1)
{
RestrictInfo *restrictinfo = (RestrictInfo *)
linitial(ec->ec_sources);
@@ -1172,9 +1189,10 @@ 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_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
if (cur_em->em_is_const)
{
@@ -1186,9 +1204,10 @@ generate_base_implied_equalities_const(PlannerInfo *root,
Assert(const_em != NULL);
/* Generate a derived equality against each other member */
- foreach(lc, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Oid eq_op;
RestrictInfo *rinfo;
@@ -1240,7 +1259,7 @@ generate_base_implied_equalities_no_const(PlannerInfo
*root,
EquivalenceClass *ec)
{
EquivalenceMember **prev_ems;
- ListCell *lc;
+ int i;
/*
* We scan the EC members once and track the last-seen member for each
@@ -1253,9 +1272,10 @@ generate_base_implied_equalities_no_const(PlannerInfo
*root,
prev_ems = (EquivalenceMember **)
palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember
*));
- foreach(lc, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
int relid;
Assert(!cur_em->em_is_child); /* no children yet */
@@ -1315,9 +1335,10 @@ generate_base_implied_equalities_no_const(PlannerInfo
*root,
* pre-analysis of which members we prefer to join, but it's no worse
than
* what happened in the pre-8.3 code.
*/
- foreach(lc, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
List *vars = pull_var_clause((Node *) cur_em->em_expr,
PVC_RECURSE_AGGREGATES |
PVC_RECURSE_WINDOWFUNCS |
@@ -1445,7 +1466,7 @@ generate_join_implied_equalities(PlannerInfo *root,
continue;
/* Single-member ECs won't generate any deductions */
- if (list_length(ec->ec_members) <= 1)
+ if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
continue;
/* Sanity check that this eclass overlaps the join */
@@ -1516,7 +1537,7 @@ generate_join_implied_equalities_for_ecs(PlannerInfo
*root,
continue;
/* Single-member ECs won't generate any deductions */
- if (list_length(ec->ec_members) <= 1)
+ if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
continue;
/* We can quickly ignore any that don't overlap the join, too */
@@ -1560,6 +1581,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
List *outer_members = NIL;
List *inner_members = NIL;
ListCell *lc1;
+ int i;
/*
* First, scan the EC to identify member values that are computable at
the
@@ -1570,9 +1592,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)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+ EquivalenceMember *cur_em = (EquivalenceMember
*)list_nth(root->eq_members, i);
/*
* We don't need to check explicitly for child EC members.
This test
@@ -2104,7 +2127,7 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
bool match;
- ListCell *lc2;
+ int i;
/* Ignore EC unless it contains pseudoconstants */
if (!cur_ec->ec_has_const)
@@ -2119,9 +2142,10 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
continue;
/* Does it contain a match to outervar? */
match = false;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Assert(!cur_em->em_is_child); /* no children yet */
if (equal(outervar, cur_em->em_expr))
@@ -2139,9 +2163,10 @@ reconsider_outer_join_clause(PlannerInfo *root,
RestrictInfo *rinfo,
* constant before we can decide to throw away the outer-join
clause.
*/
match = false;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Oid eq_op;
RestrictInfo *newrinfo;
@@ -2223,8 +2248,8 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
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)
@@ -2252,9 +2277,10 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
* the COALESCE arguments?
*/
match = false;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- coal_em = (EquivalenceMember *) lfirst(lc2);
+ coal_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Assert(!coal_em->em_is_child); /* no children yet */
if (IsA(coal_em->em_expr, CoalesceExpr))
{
@@ -2269,7 +2295,7 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
if (equal(leftvar, cfirst) && equal(rightvar,
csecond))
{
- coal_idx = foreach_current_index(lc2);
+ coal_idx = i;
match = true;
break;
}
@@ -2285,9 +2311,10 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
* decide to throw away the outer-join clause.
*/
matchleft = matchright = false;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Oid eq_op;
RestrictInfo *newrinfo;
@@ -2336,7 +2363,24 @@ reconsider_full_join_clause(PlannerInfo *root,
RestrictInfo *rinfo)
*/
if (matchleft && matchright)
{
- cur_ec->ec_members =
list_delete_nth_cell(cur_ec->ec_members, coal_idx);
+ cur_ec->ec_member_indexes =
bms_del_member(cur_ec->ec_member_indexes, coal_idx);
+
+ /* Remove the member from each of the relations */
+ /* XXX check this is right. Is there a neater way? */
+ i = -1;
+ while ((i = bms_next_member(left_relids, i)) > 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+ rel->eclass_member_indexes =
bms_del_member(rel->eclass_member_indexes, i);
+ }
+
+ i = -1;
+ while ((i = bms_next_member(right_relids, i)) > 0)
+ {
+ RelOptInfo *rel = root->simple_rel_array[i];
+ rel->eclass_member_indexes =
bms_del_member(rel->eclass_member_indexes, i);
+ }
+
return true;
}
@@ -2374,15 +2418,16 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node
*item2)
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
bool item1member = false;
bool item2member = false;
- ListCell *lc2;
+ int i;
/* Never match to a volatile EC */
if (ec->ec_has_volatile)
continue;
- foreach(lc2, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *em = (EquivalenceMember *)
list_nth(root->eq_members, i);
if (em->em_is_child)
continue; /* ignore children here
*/
@@ -2445,16 +2490,16 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
i);
EquivalenceMember *item1_em = NULL;
EquivalenceMember *item2_em = NULL;
- ListCell *lc2;
/* Never match to a volatile EC */
if (ec->ec_has_volatile)
continue;
/* Note: it seems okay to match to "broken" eclasses here */
- foreach(lc2, ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Var *var;
if (em->em_is_child)
@@ -2568,6 +2613,7 @@ add_child_rel_equivalences(PlannerInfo *root,
{
EquivalenceClass *cur_ec = (EquivalenceClass *)
list_nth(root->eq_classes, i);
int num_members;
+ int j;
/*
* If this EC contains a volatile expression, then generating
child
@@ -2580,15 +2626,20 @@ add_child_rel_equivalences(PlannerInfo *root,
/* Sanity check eclass_indexes only contain ECs for parent_rel
*/
Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
+ /* Only loop over existing members, not the newly added ones */
/*
- * 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.
+ * XXX this is ugly. Is there a better way? bms_copy()?
+ * Use bms_prev_member(..., -1) to get the final member first
and
+ * abort the loop when we go beyond that?
*/
- num_members = list_length(cur_ec->ec_members);
+ num_members = bms_num_members(cur_ec->ec_member_indexes);
+ j = -1;
for (int pos = 0; pos < num_members; pos++)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(cur_ec->ec_members, pos);
+ EquivalenceMember *cur_em;
+
+ j = bms_next_member(cur_ec->ec_member_indexes, j);
+ cur_em = (EquivalenceMember *)
list_nth(root->eq_members, j);
if (cur_em->em_is_const)
continue; /* ignore consts here */
@@ -2653,7 +2704,7 @@ add_child_rel_equivalences(PlannerInfo *root,
child_relids);
}
- (void) add_eq_member(cur_ec, child_expr,
+ (void) add_eq_member(root, cur_ec, child_expr,
new_relids, new_nullable_relids,
true,
cur_em->em_datatype);
@@ -2706,6 +2757,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
{
EquivalenceClass *cur_ec = (EquivalenceClass *)
list_nth(root->eq_classes, i);
int num_members;
+ int j;
/*
* If this EC contains a volatile expression, then generating
child
@@ -2718,15 +2770,20 @@ add_child_join_rel_equivalences(PlannerInfo *root,
/* Sanity check on get_eclass_indexes_for_relids result */
Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
+ /* Only loop over existing members, not the newly added ones */
/*
- * 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.
+ * XXX this is ugly. Is there a better way? bms_copy()?
+ * Use bms_prev_member(..., -1) to get the final member first
and
+ * abort the loop when we go beyond that?
*/
- num_members = list_length(cur_ec->ec_members);
+ num_members = bms_num_members(cur_ec->ec_member_indexes);
+ j = -1;
for (int pos = 0; pos < num_members; pos++)
{
- EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(cur_ec->ec_members, pos);
+ EquivalenceMember *cur_em;
+
+ j = bms_next_member(cur_ec->ec_member_indexes, j);
+ cur_em = (EquivalenceMember *)
list_nth(root->eq_members, j);
if (cur_em->em_is_const)
continue; /* ignore consts here */
@@ -2794,7 +2851,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
child_relids,
top_parent_relids);
- (void) add_eq_member(cur_ec, child_expr,
+ (void) add_eq_member(root, cur_ec, child_expr,
new_relids, new_nullable_relids,
true,
cur_em->em_datatype);
}
@@ -2857,7 +2914,6 @@ generate_implied_equalities_for_column(PlannerInfo *root,
{
EquivalenceClass *cur_ec = (EquivalenceClass *)
list_nth(root->eq_classes, i);
EquivalenceMember *cur_em;
- ListCell *lc2;
/* Sanity check eclass_indexes only contain ECs for rel */
Assert(is_child_rel || bms_is_subset(rel->relids,
cur_ec->ec_relids));
@@ -2866,7 +2922,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
* Won't generate joinclauses if const or single-member (the
latter
* test covers the volatile case too)
*/
- if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <=
1)
+ if (cur_ec->ec_has_const ||
+ bms_membership(cur_ec->ec_member_indexes) !=
BMS_MULTIPLE)
continue;
/*
@@ -2880,9 +2937,11 @@ generate_implied_equalities_for_column(PlannerInfo *root,
* match. See also get_eclass_for_sort_expr.)
*/
cur_em = NULL;
- foreach(lc2, cur_ec->ec_members)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- cur_em = (EquivalenceMember *) lfirst(lc2);
+ cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
+
if (bms_equal(cur_em->em_relids, rel->relids) &&
callback(root, rel, cur_ec, cur_em,
callback_arg))
break;
@@ -2896,9 +2955,10 @@ 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)
+ i = -1;
+ while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *other_em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *other_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
Oid eq_op;
RestrictInfo *rinfo;
@@ -2986,7 +3046,7 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
* Won't generate joinclauses if single-member (this test
covers the
* volatile case too)
*/
- if (list_length(ec->ec_members) <= 1)
+ if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
continue;
/*
@@ -3044,7 +3104,7 @@ has_relevant_eclass_joinclause(PlannerInfo *root,
RelOptInfo *rel1)
* Won't generate joinclauses if single-member (this test
covers the
* volatile case too)
*/
- if (list_length(ec->ec_members) <= 1)
+ if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
continue;
/*
@@ -3075,7 +3135,7 @@ eclass_useful_for_merging(PlannerInfo *root,
RelOptInfo *rel)
{
Relids relids;
- ListCell *lc;
+ int i;
Assert(!eclass->ec_merged);
@@ -3083,7 +3143,8 @@ eclass_useful_for_merging(PlannerInfo *root,
* Won't generate joinclauses if const or single-member (the latter test
* covers the volatile case too)
*/
- if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
+ if (eclass->ec_has_const ||
+ bms_membership(eclass->ec_member_indexes) != BMS_MULTIPLE)
return false;
/*
@@ -3106,9 +3167,10 @@ 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_member_indexes, i)) >= 0)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+ EquivalenceMember *cur_em = (EquivalenceMember *)
list_nth(root->eq_members, i);
if (cur_em->em_is_child)
continue; /* ignore children here
*/
diff --git a/src/backend/optimizer/path/indxpath.c
b/src/backend/optimizer/path/indxpath.c
index 7d176e7b00..4c18ada572 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -184,8 +184,8 @@ static IndexClause *expand_indexqual_rowcompare(PlannerInfo
*root,
IndexOptInfo *index,
Oid expr_op,
bool var_on_left);
-static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
- List
**orderby_clauses_p,
+static void match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index,
+ List
*pathkeys, List **orderby_clauses_p,
List
**clause_columns_p);
static Expr *match_clause_to_ordering_op(IndexOptInfo *index,
int indexcol, Expr *clause, Oid pk_opfamily);
@@ -998,7 +998,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
else if (index->amcanorderbyop && pathkeys_possibly_useful)
{
/* see if we can generate ordering operators for query_pathkeys
*/
- match_pathkeys_to_index(index, root->query_pathkeys,
+ match_pathkeys_to_index(root, index, root->query_pathkeys,
&orderbyclauses,
&orderbyclausecols);
if (orderbyclauses)
@@ -3073,8 +3073,8 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* one-to-one with the requested pathkeys.
*/
static void
-match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
- List **orderby_clauses_p,
+match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index,
+ List *pathkeys, List
**orderby_clauses_p,
List **clause_columns_p)
{
List *orderby_clauses = NIL;
@@ -3092,7 +3092,7 @@ match_pathkeys_to_index(IndexOptInfo *index, List
*pathkeys,
{
PathKey *pathkey = (PathKey *) lfirst(lc1);
bool found = false;
- ListCell *lc2;
+ int i;
/*
* Note: for any failure to match, we just return NIL
immediately.
@@ -3116,9 +3116,10 @@ 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)
+ i = -1;
+ while ((i =
bms_next_member(pathkey->pk_eclass->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *member = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *member = (EquivalenceMember *)
list_nth(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 b5d6c977ee..e3e87f162c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1396,9 +1396,11 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo
*rel,
/* We can represent this sub_pathkey */
EquivalenceMember *sub_member;
EquivalenceClass *outer_ec;
+ int first_em;
- Assert(list_length(sub_eclass->ec_members) ==
1);
- sub_member = (EquivalenceMember *)
linitial(sub_eclass->ec_members);
+
Assert(bms_membership(sub_eclass->ec_member_indexes) == BMS_SINGLETON);
+ first_em =
bms_next_member(sub_eclass->ec_member_indexes, -1);
+ sub_member = (EquivalenceMember *)
list_nth(rel->subroot->eq_members, first_em);
/*
* Note: it might look funny to be setting
sortref = 0 for a
@@ -1453,11 +1455,11 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo
*rel,
* outer query.
*/
int best_score = -1;
- ListCell *j;
+ int i = -1;
- foreach(j, sub_eclass->ec_members)
+ while ((i =
bms_next_member(sub_eclass->ec_member_indexes, i)) >= 0)
{
- EquivalenceMember *sub_member =
(EquivalenceMember *) lfirst(j);
+ EquivalenceMember *sub_member =
(EquivalenceMember *) list_nth(rel->subroot->eq_members, i);
Expr *sub_expr = sub_member->em_expr;
Oid sub_expr_type =
sub_member->em_datatype;
Oid sub_expr_coll =
sub_eclass->ec_collation;
@@ -1516,7 +1518,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo
*rel,
sub_pathkey->pk_strategy,
sub_pathkey->pk_nulls_first);
/* score = # of equivalence peers */
- score =
list_length(outer_ec->ec_members) - 1;
+ score =
bms_num_members(outer_ec->ec_member_indexes) - 1;
/* +1 if it matches the proper
query_pathkeys item */
if (retvallen < outer_query_keys &&
list_nth(root->query_pathkeys,
retvallen) == outer_pk)
@@ -1926,7 +1928,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);
@@ -1947,9 +1949,10 @@ 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_member_indexes, i)) >=
0)
{
- EquivalenceMember *em = (EquivalenceMember *)
lfirst(lc2);
+ EquivalenceMember *em = (EquivalenceMember *)
list_nth(root->eq_members, i);
/* Potential future join partner? */
if (!em->em_is_const && !em->em_is_child &&
diff --git a/src/backend/optimizer/plan/createplan.c
b/src/backend/optimizer/plan/createplan.c
index e37f2933eb..b8aeb2e84a 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -260,8 +260,8 @@ static IncrementalSort *make_incrementalsort(Plan *lefttree,
int numCols, int nPresortedCols,
AttrNumber *sortColIdx, Oid *sortOperators,
Oid *collations, bool *nullsFirst);
-static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
-
Relids relids,
+static Plan *prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+
List *pathkeys, Relids relids,
const AttrNumber *reqColIdx,
bool adjust_tlist_in_place,
int *p_numsortkeys,
@@ -269,10 +269,13 @@ static Plan *prepare_sort_from_pathkeys(Plan *lefttree,
List *pathkeys,
Oid **p_sortOperators,
Oid **p_collations,
bool **p_nullsFirst);
-static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
- Relids
relids);
-static IncrementalSort *make_incrementalsort_from_pathkeys(Plan *lefttree,
-
List *pathkeys, Relids relids, int
nPresortedCols);
+static Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+ List
*pathkeys, Relids relids);
+static IncrementalSort *make_incrementalsort_from_pathkeys(PlannerInfo *root,
+
Plan *lefttree,
+
List *pathkeys,
+
Relids relids,
+
int nPresortedCols);
static Sort *make_sort_from_groupcols(List *groupcls,
AttrNumber *grpColIdx,
Plan
*lefttree);
@@ -293,7 +296,7 @@ static Group *make_group(List *tlist, List *qual, int
numGroupCols,
AttrNumber *grpColIdx, Oid
*grpOperators, Oid *grpCollations,
Plan *lefttree);
static Unique *make_unique_from_sortclauses(Plan *lefttree, List
*distinctList);
-static Unique *make_unique_from_pathkeys(Plan *lefttree,
+static Unique *make_unique_from_pathkeys(PlannerInfo *root, Plan *lefttree,
List *pathkeys, int numCols);
static Gather *make_gather(List *qptlist, List *qpqual,
int nworkers, int
rescan_param, bool single_copy, Plan *subplan);
@@ -1261,7 +1264,8 @@ create_append_plan(PlannerInfo *root, AppendPath
*best_path, int flags)
* function result; it must be the same plan node. However, we
then
* need to detect whether any tlist entries were added.
*/
- (void) prepare_sort_from_pathkeys((Plan *) plan, pathkeys,
+ (void) prepare_sort_from_pathkeys(root,
+
(Plan *) plan, pathkeys,
best_path->path.parent->relids,
NULL,
true,
@@ -1305,7 +1309,7 @@ create_append_plan(PlannerInfo *root, AppendPath
*best_path, int flags)
* don't need an explicit sort, to make sure they are
returning
* the same sort key columns the Append expects.
*/
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan,
pathkeys,
subpath->parent->relids,
nodeSortColIdx,
false,
@@ -1446,7 +1450,7 @@ create_merge_append_plan(PlannerInfo *root,
MergeAppendPath *best_path,
* function result; it must be the same plan node. However, we then
need
* to detect whether any tlist entries were added.
*/
- (void) prepare_sort_from_pathkeys(plan, pathkeys,
+ (void) prepare_sort_from_pathkeys(root, plan, pathkeys,
best_path->path.parent->relids,
NULL,
true,
@@ -1477,7 +1481,7 @@ create_merge_append_plan(PlannerInfo *root,
MergeAppendPath *best_path,
subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
/* Compute sort column info, and adjust subplan's tlist as
needed */
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
subpath->parent->relids,
node->sortColIdx,
false,
@@ -1964,7 +1968,7 @@ create_gather_merge_plan(PlannerInfo *root,
GatherMergePath *best_path)
Assert(pathkeys != NIL);
/* Compute sort column info, and adjust subplan's tlist as needed */
- subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+ subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
best_path->subpath->parent->relids,
gm_plan->sortColIdx,
false,
@@ -2183,7 +2187,7 @@ create_sort_plan(PlannerInfo *root, SortPath *best_path,
int flags)
* relids. Thus, if this sort path is based on a child relation, we must
* pass its relids.
*/
- plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys,
+ plan = make_sort_from_pathkeys(root, subplan, best_path->path.pathkeys,
IS_OTHER_REL(best_path->subpath->parent) ?
best_path->path.parent->relids : NULL);
@@ -2207,7 +2211,7 @@ create_incrementalsort_plan(PlannerInfo *root,
IncrementalSortPath *best_path,
/* See comments in create_sort_plan() above */
subplan = create_plan_recurse(root, best_path->spath.subpath,
flags |
CP_SMALL_TLIST);
- plan = make_incrementalsort_from_pathkeys(subplan,
+ plan = make_incrementalsort_from_pathkeys(root, subplan,
best_path->spath.path.pathkeys,
IS_OTHER_REL(best_path->spath.subpath->parent) ?
best_path->spath.path.parent->relids : NULL,
@@ -2276,7 +2280,7 @@ create_upper_unique_plan(PlannerInfo *root,
UpperUniquePath *best_path, int flag
subplan = create_plan_recurse(root, best_path->subpath,
flags |
CP_LABEL_TLIST);
- plan = make_unique_from_pathkeys(subplan,
+ plan = make_unique_from_pathkeys(root, subplan,
best_path->path.pathkeys,
best_path->numkeys);
@@ -4478,7 +4482,7 @@ create_mergejoin_plan(PlannerInfo *root,
if (best_path->outersortkeys)
{
Relids outer_relids = outer_path->parent->relids;
- Sort *sort = make_sort_from_pathkeys(outer_plan,
+ Sort *sort = make_sort_from_pathkeys(root, outer_plan,
best_path->outersortkeys,
outer_relids);
@@ -4492,7 +4496,7 @@ create_mergejoin_plan(PlannerInfo *root,
if (best_path->innersortkeys)
{
Relids inner_relids = inner_path->parent->relids;
- Sort *sort = make_sort_from_pathkeys(inner_plan,
+ Sort *sort = make_sort_from_pathkeys(root, inner_plan,
best_path->innersortkeys,
inner_relids);
@@ -6116,7 +6120,8 @@ make_incrementalsort(Plan *lefttree, int numCols, int
nPresortedCols,
* or a Result stacked atop lefttree).
*/
static Plan *
-prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
+prepare_sort_from_pathkeys(PlannerInfo *root,
+ Plan *lefttree, List
*pathkeys,
Relids relids,
const AttrNumber *reqColIdx,
bool adjust_tlist_in_place,
@@ -6157,6 +6162,8 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
if (ec->ec_has_volatile)
{
+ int first_em;
+
/*
* If the pathkey's EquivalenceClass is volatile, then
it must
* have come from an ORDER BY clause, and we have to
match it to
@@ -6166,8 +6173,9 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
elog(ERROR, "volatile EquivalenceClass has no
sortref");
tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
Assert(tle);
- Assert(list_length(ec->ec_members) == 1);
- pk_datatype = ((EquivalenceMember *)
linitial(ec->ec_members))->em_datatype;
+ Assert(bms_membership(ec->ec_member_indexes) ==
BMS_SINGLETON);
+ first_em = bms_next_member(ec->ec_member_indexes, -1);
+ pk_datatype = ((EquivalenceMember *)
list_nth(root->eq_members, first_em))->em_datatype;
}
else if (reqColIdx != NULL)
{
@@ -6183,7 +6191,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
tle = get_tle_by_resno(tlist, reqColIdx[numsortkeys]);
if (tle)
{
- em = find_ec_member_matching_expr(ec,
tle->expr, relids);
+ em = find_ec_member_matching_expr(root, ec,
tle->expr, relids);
if (em)
{
/* found expr at right place in tlist */
@@ -6214,7 +6222,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
foreach(j, tlist)
{
tle = (TargetEntry *) lfirst(j);
- em = find_ec_member_matching_expr(ec,
tle->expr, relids);
+ em = find_ec_member_matching_expr(root, ec,
tle->expr, relids);
if (em)
{
/* found expr already in tlist */
@@ -6230,7 +6238,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
/*
* No matching tlist item; look for a computable
expression.
*/
- em = find_computable_ec_member(NULL, ec, tlist, relids,
false);
+ em = find_computable_ec_member(root, ec, tlist, relids,
false);
if (!em)
elog(ERROR, "could not find pathkey item to
sort");
pk_datatype = em->em_datatype;
@@ -6301,7 +6309,8 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
* 'relids' is the set of relations required by
prepare_sort_from_pathkeys()
*/
static Sort *
-make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids)
+make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+ Relids relids)
{
int numsortkeys;
AttrNumber *sortColIdx;
@@ -6310,7 +6319,9 @@ make_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
Relids relids)
bool *nullsFirst;
/* Compute sort column info, and adjust lefttree as needed */
- lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys,
+ lefttree = prepare_sort_from_pathkeys(root,
+
lefttree,
+
pathkeys,
relids,
NULL,
false,
@@ -6336,7 +6347,8 @@ make_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
Relids relids)
* 'nPresortedCols' is the number of presorted columns in input tuples
*/
static IncrementalSort *
-make_incrementalsort_from_pathkeys(Plan *lefttree, List *pathkeys,
+make_incrementalsort_from_pathkeys(PlannerInfo *root,
+ Plan
*lefttree, List *pathkeys,
Relids
relids, int nPresortedCols)
{
int numsortkeys;
@@ -6346,7 +6358,9 @@ make_incrementalsort_from_pathkeys(Plan *lefttree, List
*pathkeys,
bool *nullsFirst;
/* Compute sort column info, and adjust lefttree as needed */
- lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys,
+ lefttree = prepare_sort_from_pathkeys(root,
+
lefttree,
+
pathkeys,
relids,
NULL,
false,
@@ -6696,7 +6710,7 @@ make_unique_from_sortclauses(Plan *lefttree, List
*distinctList)
* as above, but use pathkeys to identify the sort columns and semantics
*/
static Unique *
-make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
+make_unique_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
int numCols)
{
Unique *node = makeNode(Unique);
Plan *plan = &node->plan;
@@ -6737,6 +6751,8 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys,
int numCols)
if (ec->ec_has_volatile)
{
+ int first_em;
+
/*
* If the pathkey's EquivalenceClass is volatile, then
it must
* have come from an ORDER BY clause, and we have to
match it to
@@ -6746,8 +6762,9 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys,
int numCols)
elog(ERROR, "volatile EquivalenceClass has no
sortref");
tle = get_sortgroupref_tle(ec->ec_sortref,
plan->targetlist);
Assert(tle);
- Assert(list_length(ec->ec_members) == 1);
- pk_datatype = ((EquivalenceMember *)
linitial(ec->ec_members))->em_datatype;
+ Assert(bms_membership(ec->ec_member_indexes) ==
BMS_SINGLETON);
+ first_em = bms_next_member(ec->ec_member_indexes, -1);
+ pk_datatype = ((EquivalenceMember *)
list_nth(root->eq_members, first_em))->em_datatype;
}
else
{
@@ -6759,7 +6776,7 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys,
int numCols)
foreach(j, plan->targetlist)
{
tle = (TargetEntry *) lfirst(j);
- em = find_ec_member_matching_expr(ec,
tle->expr, NULL);
+ em = find_ec_member_matching_expr(root, ec,
tle->expr, NULL);
if (em)
{
/* found expr already in tlist */
diff --git a/src/backend/optimizer/plan/planner.c
b/src/backend/optimizer/plan/planner.c
index 06ad856eac..4a5be95875 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -618,6 +618,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
root->cte_plan_ids = NIL;
root->multiexpr_params = NIL;
root->eq_classes = NIL;
+ root->eq_members = NIL;
root->ec_merging_done = false;
root->all_result_relids =
parse->resultRelation ?
bms_make_singleton(parse->resultRelation) : NULL;
diff --git a/src/backend/optimizer/prep/prepjointree.c
b/src/backend/optimizer/prep/prepjointree.c
index 0bd99acf83..f3e6c19fc7 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -998,6 +998,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
RangeTblEntry *rte,
subroot->cte_plan_ids = NIL;
subroot->multiexpr_params = NIL;
subroot->eq_classes = NIL;
+ subroot->eq_members = NIL;
subroot->ec_merging_done = false;
subroot->all_result_relids = NULL;
subroot->leaf_result_relids = NULL;
diff --git a/src/backend/optimizer/prep/prepunion.c
b/src/backend/optimizer/prep/prepunion.c
index 043181b586..0ec3736e52 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -128,6 +128,7 @@ plan_set_operations(PlannerInfo *root)
* so that pathkeys.c won't complain.
*/
Assert(root->eq_classes == NIL);
+ Assert(root->eq_members == NIL);
root->ec_merging_done = true;
/*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index e2081db4ed..1b2b1fcf22 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -300,6 +300,9 @@ struct PlannerInfo
/* list of active EquivalenceClasses */
List *eq_classes;
+ /* list of each EquivalenceMember */
+ List *eq_members;
+
/* set true once ECs are canonical */
bool ec_merging_done;
@@ -874,6 +877,12 @@ typedef struct RelOptInfo
* Indexes in PlannerInfo's eq_classes list of ECs that mention this rel
*/
Bitmapset *eclass_indexes;
+
+ /*
+ * Indexes in PlannerInfo's eq_members list of EMs that memtion this rel
+ */
+ Bitmapset *eclass_member_indexes;
+
PlannerInfo *subroot; /* if subquery */
List *subplan_params; /* if subquery */
/* wanted number of parallel workers */
@@ -1262,7 +1271,7 @@ typedef struct EquivalenceClass
List *ec_opfamilies; /* btree operator family OIDs */
Oid ec_collation; /* collation, if datatypes are
collatable */
- List *ec_members; /* list of EquivalenceMembers */
+ Bitmapset *ec_member_indexes; /* Indexes into PlannerInfo's eq_members
*/
List *ec_sources; /* list of generating RestrictInfos */
List *ec_derives; /* list of derived RestrictInfos */
Relids ec_relids; /* all relids appearing in
ec_members, except
diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h
index be5e2287f3..526723a187 100644
--- a/src/include/nodes/print.h
+++ b/src/include/nodes/print.h
@@ -16,6 +16,7 @@
#include "executor/tuptable.h"
+struct PlannerInfo;
#define nodeDisplay(x) pprint(x)
@@ -27,7 +28,9 @@ extern char *format_node_dump(const char *dump);
extern char *pretty_format_node_dump(const char *dump);
extern void print_rt(const List *rtable);
extern void print_expr(const Node *expr, const List *rtable);
-extern void print_pathkeys(const List *pathkeys, const List *rtable);
+extern void print_pathkeys(const struct PlannerInfo *root,
+ const List *pathkeys,
+ const List *rtable);
extern void print_tl(const List *tlist, const List *rtable);
extern void print_slot(TupleTableSlot *slot);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 54ab709c67..ba75d52107 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -136,7 +136,8 @@ extern EquivalenceClass
*get_eclass_for_sort_expr(PlannerInfo *root,
Index sortref,
Relids rel,
bool create_it);
-extern EquivalenceMember *find_ec_member_matching_expr(EquivalenceClass *ec,
+extern EquivalenceMember *find_ec_member_matching_expr(PlannerInfo *root,
+
EquivalenceClass *ec,
Expr *expr,
Relids relids);
extern EquivalenceMember *find_computable_ec_member(PlannerInfo *root,
