Dear David,
Thank you for your comments on my patch. I really apologize for my
late response.
On Thu, Mar 24, 2022 at 11:03 AM David Rowley <dgrowle...@gmail.com> wrote:
> I think a better way to solve this would be just to have a single hash
> table over all EquivalenceClasses that allows fast lookups of
> EquivalenceMember->em_expr. I think there's no reason that a given
> Expr should appear in more than one non-merged EquivalenceClass. The
> EquivalenceClass a given Expr belongs to would need to be updated
> during the merge process.
Thank you for your idea. However, I think building a hash table whose
key is EquivalenceMember->em_expr does not work for this case.
What I am trying to optimize in this patch is the following code.
=====
EquivalenceClass *ec = /* given */;
EquivalenceMember *em;
ListCell *lc;
foreach(lc, ec->ec_members)
{
em = (EquivalenceMember *) lfirst(lc);
/* predicate is bms_equal or bms_is_subset, etc */
if (!predicate(em))
continue;
/* The predicate satisfies */
do something...;
}
=====
>From my observation, the predicates above will be false in most cases
and the subsequent processes are not executed. My optimization is
based on this notion and utilizes hash tables to eliminate calls of
predicates.
If the predicate were "em->em_expr == something", the hash table whose
key is em_expr would be effective. However, the actual predicates are
not of this type but the following.
// Find EquivalenceMembers whose relids is equal to the given relids
(1) bms_equal(em->em_relids, relids)
// Find EquivalenceMembers whose relids is a subset of the given relids
(2) bms_is_subset(em->em_relids, relids)
Since these predicates perform a match search for not em_expr but
em_relids, we need to build a hash table with em_relids as key. If so,
we can drastically reduce the planning time for the pattern (1).
Besides, by enumerating all subsets of relids, pattern (2) can be
optimized. The detailed algorithm is described in the first email.
I show an example of the pattern (1). The next code is in
src/backend/optimizer/path/equivclass.c. As can be seen from this
code, the foreach loop tries to find an EquivalenceMember whose
cur_em->em_relids is equal to rel->relids. If found, subsequent
processing will be performed.
== Before patched ==
List *
generate_implied_equalities_for_column(PlannerInfo *root,
RelOptInfo *rel,
ec_matches_callback_type callback,
void *callback_arg,
Relids prohibited_rels)
{
...
EquivalenceClass *cur_ec = (EquivalenceClass *)
list_nth(root->eq_classes, i);
EquivalenceMember *cur_em;
ListCell *lc2;
cur_em = NULL;
foreach(lc2, cur_ec->ec_members)
{
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;
}
if (!cur_em)
continue;
...
}
===
My patch modifies this code as follows. The em_foreach_relids_equals
is a newly defined macro that finds EquivalenceMember satisfying the
bms_equal. The macro looks up a hash table using rel->relids as a key.
This type of optimization cannot be achieved without using hash tables
whose key is em->em_relids.
== After patched ==
List *
generate_implied_equalities_for_column(PlannerInfo *root,
RelOptInfo *rel,
ec_matches_callback_type callback,
void *callback_arg,
Relids prohibited_rels)
{
...
EquivalenceClass *cur_ec = (EquivalenceClass *)
list_nth(root->eq_classes, i);
EquivalenceMember *cur_em;
EquivalenceMember *other_em;
cur_em = NULL;
em_foreach_relids_equals(cur_em, cur_ec, rel->relids)
{
Assert(bms_equal(cur_em->em_relids, rel->relids));
if (callback(root, rel, cur_ec, cur_em, callback_arg))
break;
cur_em = NULL;
}
if (!cur_em)
continue;
...
}
===
> We might not want to build the hash table for all queries.
I agree with you. Building a lot of hash tables will consume much
memory. My idea for this problem is to let the hash table's key be a
pair of EquivalenceClass and Relids. However, this approach may lead
to increasing looking up time of the hash table.
==========
I noticed that the previous patch does not work with the current HEAD.
I attached the modified one to this email.
Additionally, I added my patch to the current commit fest [1].
[1] https://commitfest.postgresql.org/38/3701/
--
Best regards,
Yuya Watari
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index ce12915592..7faf634e9b 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2636,6 +2636,8 @@ _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_members_htab);
+ WRITE_NODE_FIELD(ec_not_child_members);
WRITE_NODE_FIELD(ec_sources);
WRITE_NODE_FIELD(ec_derives);
WRITE_BITMAPSET_FIELD(ec_relids);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 60c0e3f108..35271b75e9 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -31,6 +31,144 @@
#include "optimizer/restrictinfo.h"
#include "utils/lsyscache.h"
+/*
+ * Constant, state structs and enum for looping macros below.
+ */
+#define LOG_OF_MAX_NUM_SUBSETS_OF_RELIDS 16
+
+typedef struct
+{
+ const List *list;
+ int i;
+} EmForeachListState;
+
+typedef enum
+{
+ EM_FOREACH_NEXT_BIT, /* Proceed to next subset */
+ EM_FOREACH_NEXT_LIST_ENTRY, /* Proceed to next entry */
+ EM_FOREACH_LINEAR_SEARCH, /* Standard linear search */
+ EM_FOREACH_FINISHED /* Loop was done */
+} EmForeachBitStateStatus;
+
+typedef struct
+{
+ EmForeachBitStateStatus status;
+ EquivalenceClass *ec;
+ Relids relids;
+ int32 bit;
+ int num_members_in_relids;
+ int all_members_in_relids[LOG_OF_MAX_NUM_SUBSETS_OF_RELIDS];
+ Relids subset;
+ List *list;
+ int i;
+} EmForeachBitState;
+
+/*
+ * The following three em_foreach_* macros help enumerate
+ * EquivalenceClass::ec_members.
+ *
+ * See the comments below for further information.
+ */
+
+/*
+ * em_foreach_not_children
+ *
+ * Optimized version of
+ * =====
+ * ListCell *lc;
+ * foreach(lc, ec->ec_members)
+ * {
+ * EquivalenceMember *em = lfirst(lc);
+ *
+ * if (em->em_is_child)
+ * continue;
+ *
+ * content of loop...
+ * }
+ * =====
+ *
+ * Usage:
+ * =====
+ * EquivalenceClass *ec = ...;
+ *
+ * EquivalenceMember *em;
+ * em_foreach_not_children(em, ec)
+ * {
+ * content of loop...
+ * }
+ * =====
+ */
+#define em_foreach_not_children(em, ec) \
+ for (EmForeachListState em##__state = { (ec)->ec_not_child_members, -1 }; \
+ em_foreach_list_move_next(&em##__state, &em); )
+
+/*
+ * em_foreach_relids_equals
+ *
+ * Optimized version of
+ * =====
+ * ListCell *lc;
+ * foreach(lc, ec->ec_members)
+ * {
+ * EquivalenceMember *em = lfirst(lc);
+ *
+ * if (!bms_equal(em->em_relids, relids))
+ * continue;
+ *
+ * content of loop...
+ * }
+ * =====
+ *
+ * Usage:
+ * =====
+ * EquivalenceClass *ec = ...;
+ * Relids relids = ...;
+ *
+ * EquivalenceMember *em;
+ * em_foreach_relids_equals(em, ec)
+ * {
+ * content of loop...
+ * }
+ * =====
+ */
+#define em_foreach_relids_equals(em, ec, relids) \
+ for (EmForeachListState em##__state = \
+ { FindEcMembersMatchingRelids(ec, relids), -1 }; \
+ em_foreach_list_move_next(&em##__state, &em); )
+
+/*
+ * em_foreach_relids_subset
+ *
+ * Optimized version of
+ * =====
+ * ListCell *lc;
+ * foreach(lc, ec->ec_members)
+ * {
+ * EquivalenceMember *em = lfirst(lc);
+ *
+ * if (!bms_is_subset(em->em_relids, relids))
+ * continue;
+ *
+ * content of loop...
+ * }
+ * =====
+ *
+ * Usage:
+ * =====
+ * EquivalenceClass *ec = ...;
+ * Relids relids = ...;
+ *
+ * EmForeachBitState state;
+ * EquivalenceMember *em;
+ * initialize_EmForeachBitState(&state, ec, relids);
+ * em_foreach_relids_subset(state, em)
+ * {
+ * content of loop...
+ * }
+ * =====
+ */
+#define em_foreach_relids_subset(state, em) \
+ while (em_foreach_bit_move_next(&state, &em))
static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
Expr *expr, Relids relids, Relids nullable_relids,
@@ -69,6 +207,21 @@ static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root,
Relids relids);
static Bitmapset *get_common_eclass_indexes(PlannerInfo *root, Relids relids1,
Relids relids2);
+static inline bool em_foreach_list_move_next(
+ EmForeachListState *state, EquivalenceMember **em);
+static inline void initialize_EmForeachBitState(
+ EmForeachBitState *state, EquivalenceClass *ec, Relids relids);
+static inline bool em_foreach_bit_move_next(
+ EmForeachBitState *state, EquivalenceMember **em);
+static void InitializeEcMembersHtab(EquivalenceClass *ec);
+static void AppendEcMember(EquivalenceClass *ec,
+ EquivalenceMember *emem);
+static void ConcatEcMember(EquivalenceClass *ec1,
+ EquivalenceClass *ec2);
+static void DeleteNthEcMember(EquivalenceClass *ec,
+ int index);
+static List *FindEcMembersMatchingRelids(EquivalenceClass *ec,
+ Relids relids);
/*
@@ -364,7 +517,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);
+ ConcatEcMember(ec1, ec2);
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);
@@ -379,6 +532,8 @@ 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_members_htab = NULL;
+ ec2->ec_not_child_members = NIL;
ec2->ec_sources = NIL;
ec2->ec_derives = NIL;
ec2->ec_relids = NULL;
@@ -439,6 +594,8 @@ process_equivalence(PlannerInfo *root,
ec->ec_opfamilies = opfamilies;
ec->ec_collation = collation;
ec->ec_members = NIL;
+ ec->ec_members_htab = NULL;
+ ec->ec_not_child_members = NIL;
ec->ec_sources = list_make1(restrictinfo);
ec->ec_derives = NIL;
ec->ec_relids = NULL;
@@ -573,7 +730,7 @@ 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);
+ AppendEcMember(ec, em);
return em;
}
@@ -645,7 +802,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
- ListCell *lc2;
+ EquivalenceMember *cur_em = NULL;
/*
* Never match to a volatile EC, except when we are looking at another
@@ -660,17 +817,42 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
- foreach(lc2, cur_ec->ec_members)
+ /*
+ * Ignore child members unless they match the request.
+ */
+
+ em_foreach_not_children(cur_em, cur_ec)
{
- EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+ Assert(!cur_em->em_is_child || bms_equal(cur_em->em_relids, rel));
/*
- * Ignore child members unless they match the request.
+ * If below an outer join, don't match constants: they're not as
+ * constant as they look.
*/
- if (cur_em->em_is_child &&
- !bms_equal(cur_em->em_relids, rel))
+ if (cur_ec->ec_below_outer_join &&
+ cur_em->em_is_const)
continue;
+ if (opcintype == cur_em->em_datatype &&
+ equal(expr, cur_em->em_expr))
+ {
+ /*
+ * Match!
+ *
+ * Copy the sortref if it wasn't set yet. That may happen if the
+ * ec was constructed from WHERE clause, i.e. it doesn't have a
+ * target reference at all.
+ */
+ if (cur_ec->ec_sortref == 0 && sortref > 0)
+ cur_ec->ec_sortref = sortref;
+ return cur_ec;
+ }
+ }
+
+ em_foreach_relids_equals(cur_em, cur_ec, rel)
+ {
+ Assert(!cur_em->em_is_child || bms_equal(cur_em->em_relids, rel));
+
/*
* If below an outer join, don't match constants: they're not as
* constant as they look.
@@ -711,6 +893,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
newec->ec_opfamilies = list_copy(opfamilies);
newec->ec_collation = collation;
newec->ec_members = NIL;
+ newec->ec_members_htab = NULL;
+ newec->ec_not_child_members = NIL;
newec->ec_sources = NIL;
newec->ec_derives = NIL;
newec->ec_relids = NULL;
@@ -798,17 +982,23 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
Expr *expr,
Relids relids)
{
- ListCell *lc;
+ EquivalenceMember *em;
+ EmForeachBitState state;
/* We ignore binary-compatible relabeling on both ends */
while (expr && IsA(expr, RelabelType))
expr = ((RelabelType *) expr)->arg;
- foreach(lc, ec->ec_members)
+ /*
+ * Ignore child members unless they belong to the requested rel.
+ */
+
+ em_foreach_not_children(em, ec)
{
- EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
Expr *emexpr;
+ Assert(!em->em_is_child || bms_is_subset(em->em_relids, relids));
+
/*
* We shouldn't be trying to sort by an equivalence class that
* contains a constant, so no need to consider such cases any further.
@@ -817,10 +1007,28 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
continue;
/*
- * Ignore child members unless they belong to the requested rel.
+ * Match if same expression (after stripping relabel).
*/
- if (em->em_is_child &&
- !bms_is_subset(em->em_relids, relids))
+ emexpr = em->em_expr;
+ while (emexpr && IsA(emexpr, RelabelType))
+ emexpr = ((RelabelType *) emexpr)->arg;
+
+ if (equal(emexpr, expr))
+ return em;
+ }
+
+ initialize_EmForeachBitState(&state, ec, relids);
+ em_foreach_relids_subset(state, em)
+ {
+ Expr *emexpr;
+
+ Assert(!em->em_is_child || bms_is_subset(em->em_relids, relids));
+
+ /*
+ * We shouldn't be trying to sort by an equivalence class that
+ * contains a constant, so no need to consider such cases any further.
+ */
+ if (em->em_is_const)
continue;
/*
@@ -1560,6 +1768,8 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
List *outer_members = NIL;
List *inner_members = NIL;
ListCell *lc1;
+ EquivalenceMember *cur_em;
+ EmForeachBitState state;
/*
* First, scan the EC to identify member values that are computable at the
@@ -1570,17 +1780,16 @@ 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);
- /*
- * We don't need to check explicitly for child EC members. This test
- * against join_relids will cause them to be ignored except when
- * considering a child inner rel, which is what we want.
- */
- if (!bms_is_subset(cur_em->em_relids, join_relids))
- continue; /* not computable yet, or wrong child */
+ /*
+ * We don't need to check explicitly for child EC members. This test
+ * against join_relids will cause them to be ignored except when
+ * considering a child inner rel, which is what we want.
+ */
+ initialize_EmForeachBitState(&state, ec, join_relids);
+ em_foreach_relids_subset(state, cur_em)
+ {
+ Assert(bms_is_subset(cur_em->em_relids, join_relids));
if (bms_is_subset(cur_em->em_relids, outer_relids))
outer_members = lappend(outer_members, cur_em);
@@ -2336,7 +2545,7 @@ 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);
+ DeleteNthEcMember(cur_ec, coal_idx);
return true;
}
@@ -2857,7 +3066,7 @@ generate_implied_equalities_for_column(PlannerInfo *root,
{
EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
EquivalenceMember *cur_em;
- ListCell *lc2;
+ EquivalenceMember *other_em;
/* Sanity check eclass_indexes only contain ECs for rel */
Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
@@ -2880,11 +3089,10 @@ generate_implied_equalities_for_column(PlannerInfo *root,
* match. See also get_eclass_for_sort_expr.)
*/
cur_em = NULL;
- foreach(lc2, cur_ec->ec_members)
+ em_foreach_relids_equals(cur_em, cur_ec, rel->relids)
{
- cur_em = (EquivalenceMember *) lfirst(lc2);
- if (bms_equal(cur_em->em_relids, rel->relids) &&
- callback(root, rel, cur_ec, cur_em, callback_arg))
+ Assert(bms_equal(cur_em->em_relids, rel->relids));
+ if (callback(root, rel, cur_ec, cur_em, callback_arg))
break;
cur_em = NULL;
}
@@ -2896,14 +3104,12 @@ 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)
+ em_foreach_not_children(other_em, cur_ec)
{
- EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
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 ||
@@ -3235,3 +3441,407 @@ 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);
}
+
+/*
+ * em_foreach_list_move_next
+ * Update EmForeachListState so that it points to the next
+ * EquivalenceMember.
+ * Return true if the next element was found with assigning it to *em.
+ */
+static inline bool em_foreach_list_move_next(
+ EmForeachListState *state, EquivalenceMember **em)
+{
+ int length = list_length(state->list);
+
+ while (++(state->i) < length)
+ {
+ EquivalenceMemberListEntry *listEntry
+ = (EquivalenceMemberListEntry *) list_nth(state->list, state->i);
+
+ if (!listEntry->deleted)
+ {
+ *em = listEntry->emem;
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/*
+ * Helper functions for the em_foreach_relids_subset macro.
+ *
+ * em_foreach_relids_subset macro is based on enumeration of all possible
+ * subsets of the given relids. For each subset, we look up the hash table in
+ * EquivalenceClass and iterate over the corresponding EquivalenceMembers.
+ *
+ * This technique can be written like the next pasudo code.
+ * =====
+ * int num_members_in_relids = bms_num_members(relids);
+ * if (num_members_in_relids < LOG_OF_MAX_NUM_SUBSETS_OF_RELIDS)
+ * {
+ * // We will use the special optimization technique
+ * for (int bit = 0; bit < (1 << num_members_in_relids); bit++)
+ * {
+ * EquivalenceMember *em;
+ * ListCell *lc;
+ * Relids subset = construct subset from 'bit';
+ *
+ * foreach(lc, FindEcMembersMatchingRelids(ec, subset))
+ * {
+ * em = (EquivalenceMember *) lfirst(lc);
+ * content of loop...
+ * }
+ * }
+ * }
+ * else
+ * {
+ * // There are too many subsets, so we will use simple linear search
+ * ListCell *lc;
+ * foreach(lc, ec->ec_members)
+ * {
+ * EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ * if (bms_is_subset(em->em_relids, relids))
+ * {
+ * em = (EquivalenceMember *) lfirst(lc);
+ * content of loop...
+ * }
+ * }
+ * }
+ * =====
+ *
+ * EmForeachBitState and related functions provide the state machine for this
+ * algorithm.
+ */
+
+/*
+ * initialize_EmForeachBitState
+ * Initialize the given EmForeachBitState.
+ * This function must be called before using the
+ * em_foreach_relids_subset macro.
+ */
+static inline void initialize_EmForeachBitState(
+ EmForeachBitState *state, EquivalenceClass *ec, Relids relids)
+{
+ const int num_ec_members = list_length(ec->ec_members);
+ int num_members_in_relids = 0;
+ int i;
+
+ state->ec = ec;
+ state->relids = relids;
+
+ /*
+ * Enumerate all members in 'relids'
+ */
+ i = -1;
+ while ((i = bms_next_member(relids, i)) >= 0)
+ {
+ ++num_members_in_relids;
+
+ if ((num_members_in_relids >= LOG_OF_MAX_NUM_SUBSETS_OF_RELIDS)
+ || ((1 << num_members_in_relids) >= num_ec_members))
+ {
+ /*
+ * There are too many subsets, so we will use simple linear search
+ * instead of the special optimization technique.
+ */
+ state->status = EM_FOREACH_LINEAR_SEARCH;
+ state->i = -1;
+ return;
+ }
+
+ state->all_members_in_relids[num_members_in_relids - 1] = i;
+ }
+
+ /*
+ * Prepare for the special optimization
+ */
+ state->status = EM_FOREACH_NEXT_BIT;
+ state->bit = -1;
+ state->num_members_in_relids = num_members_in_relids;
+ state->subset = NULL;
+ return;
+}
+
+/*
+ * em_foreach_bit_move_next
+ * Update EmForeachBitState so that it points to the next
+ * EquivalenceMember.
+ * Return true if the next element was found with assigning it to *em.
+ */
+static inline bool em_foreach_bit_move_next(
+ EmForeachBitState *state, EquivalenceMember **em)
+{
+ switch (state->status)
+ {
+ case EM_FOREACH_NEXT_BIT:
+ CASE_EM_FOREACH_NEXT_BIT:
+ {
+ /*
+ * We need to proceed the next subset.
+ */
+ int i;
+ const int num_members_in_relids = state->num_members_in_relids;
+
+ if (++(state->bit) >= (1 << num_members_in_relids))
+ {
+ /* Reached end */
+ state->status = EM_FOREACH_FINISHED;
+ return false;
+ }
+
+ /* Clear Bitmapset */
+ if (state->subset != NULL)
+ {
+ for (i = 0; i < state->subset->nwords; i++)
+ {
+ state->subset->words[i] = 0;
+ }
+ }
+
+ /* Set flags */
+ for (i = 0; i < num_members_in_relids; i++)
+ {
+ if (state->bit & (1 << i))
+ {
+ state->subset =
+ bms_add_member(state->subset,
+ state->all_members_in_relids[i]);
+ }
+ }
+
+ /* Update state and begin iteration on this subset.*/
+ state->status = EM_FOREACH_NEXT_LIST_ENTRY;
+ state->list = FindEcMembersMatchingRelids(
+ state->ec, state->subset);
+ state->i = -1;
+ goto CASE_EM_FOREACH_NEXT_LIST_ENTRY;
+ }
+ case EM_FOREACH_NEXT_LIST_ENTRY:
+ CASE_EM_FOREACH_NEXT_LIST_ENTRY:
+ {
+ /*
+ * Iterate on the current subset.
+ */
+ const List *list = state->list;
+ const int length = list_length(list);
+ int i = state->i;
+
+ while (++i < length)
+ {
+ EquivalenceMemberListEntry *listEntry
+ = (EquivalenceMemberListEntry *) list_nth(list, i);
+
+ if (!listEntry->deleted)
+ {
+ /* Found */
+ *em = listEntry->emem;
+ state->i = i;
+ return true;
+ }
+ }
+
+ /*
+ * There are no more members in the current subset.
+ * We need to proceed next one.
+ */
+ state->status = EM_FOREACH_NEXT_BIT;
+ goto CASE_EM_FOREACH_NEXT_BIT;
+ }
+ case EM_FOREACH_LINEAR_SEARCH:
+ {
+ /*
+ * Simple linear search.
+ */
+ const List *ec_members = state->ec->ec_members;
+ const Relids relids = state->relids;
+ const int length = list_length(ec_members);
+ int i = state->i;
+
+ while (++i < length)
+ {
+ EquivalenceMember *member =
+ (EquivalenceMember *) list_nth(ec_members, i);
+
+ if (bms_is_subset(member->em_relids, relids))
+ {
+ /* Found */
+ *em = member;
+ state->i = i;
+ return true;
+ }
+ }
+
+ /*
+ * Reached end
+ */
+ state->status = EM_FOREACH_FINISHED;
+ return false;
+ }
+ case EM_FOREACH_FINISHED:
+ default:
+ break;
+ }
+
+ return false;
+}
+
+/*
+ * InitializeEcMembersHtab
+ * Initialize a hash table in the given EquivalenceClass.
+ */
+static void InitializeEcMembersHtab(EquivalenceClass *ec)
+{
+ HASHCTL hash_ctl;
+
+ if (ec->ec_members_htab != NULL)
+ {
+ return;
+ }
+
+ hash_ctl.keysize = sizeof(Relids);
+ hash_ctl.entrysize = sizeof(EquivalenceMemberHashEntry);
+ hash_ctl.hash = bitmap_hash;
+ hash_ctl.match = bitmap_match;
+ hash_ctl.hcxt = CurrentMemoryContext;
+ ec->ec_members_htab =
+ hash_create("EquivalenceMemberHashTable",
+ 256L,
+ &hash_ctl,
+ HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
+}
+
+/*
+ * AppendEcMember
+ * Append EquivalenceMember emem to the EquivalenceClass ec.
+ * This function modifies ec->ec_members, ec->ec_not_child_members,
+ * and ec->ec_members_htab.
+ */
+static void AppendEcMember(EquivalenceClass *ec,
+ EquivalenceMember *emem)
+{
+ EquivalenceMemberHashEntry *hashEntry;
+ EquivalenceMemberListEntry *listEntry;
+ bool found;
+
+ if (ec->ec_members_htab == NULL)
+ {
+ InitializeEcMembersHtab(ec);
+ }
+
+ listEntry = palloc(sizeof(EquivalenceMemberListEntry));
+ listEntry->emem = emem;
+ listEntry->deleted = false;
+
+ ec->ec_members = lappend(ec->ec_members, emem);
+ if (!emem->em_is_child)
+ {
+ ec->ec_not_child_members =
+ lappend(ec->ec_not_child_members, listEntry);
+ }
+
+ hashEntry = hash_search(ec->ec_members_htab, &(emem->em_relids),
+ HASH_ENTER, &found);
+ if (!found)
+ {
+ hashEntry->list = NIL;
+ }
+
+ hashEntry->list = lappend(hashEntry->list, listEntry);
+}
+
+/*
+ * ConcatEcMember
+ * Append all EquivalenceMembers in ec2 to ec1 while updating as in
+ * AppendEcMember.
+ */
+static void ConcatEcMember(EquivalenceClass *ec1,
+ EquivalenceClass *ec2)
+{
+ ListCell *lc;
+
+ if (ec1->ec_members_htab == NULL)
+ {
+ InitializeEcMembersHtab(ec1);
+ }
+
+ foreach(lc, ec2->ec_members)
+ {
+ AppendEcMember(ec1, lfirst_node(EquivalenceMember, lc));
+ }
+}
+
+/*
+ * DeleteNthEcMember
+ * Delete the EquivalenceMember whose index in ec->ec_members is the
+ * 'index' argument.
+ */
+static void DeleteNthEcMember(EquivalenceClass *ec,
+ int index)
+{
+ EquivalenceMemberHashEntry *hashEntry;
+ EquivalenceMemberListEntry *listEntry;
+ bool found;
+ EquivalenceMember *emem;
+ ListCell *lc;
+#ifdef USE_ASSERT_CHECKING
+ bool memberToBeDeletedWasFound = false;
+#endif
+
+ emem = list_nth(ec->ec_members, index);
+ ec->ec_members = list_delete_nth_cell(ec->ec_members, index);
+
+ Assert(ec->ec_members_htab != NULL);
+ hashEntry = hash_search(ec->ec_members_htab, &(emem->em_relids),
+ HASH_FIND, &found);
+ Assert(found);
+
+ /*
+ * We mark the corresponding EquivalenceMemberListEntry deleted
+ * instead of removing it from the list.
+ */
+ foreach(lc, hashEntry->list)
+ {
+ listEntry = (EquivalenceMemberListEntry *) lfirst(lc);
+
+ if (listEntry->emem == emem)
+ {
+ listEntry->deleted = true;
+#ifdef USE_ASSERT_CHECKING
+ memberToBeDeletedWasFound = true;
+#endif
+ break;
+ }
+ }
+#ifdef USE_ASSERT_CHECKING
+ Assert(memberToBeDeletedWasFound);
+#endif
+}
+
+/*
+ * FindEcMembersMatchingRelids
+ * Looks up the hash table in the EquivalenceClass and returns a list
+ * containing EquivalenceMemberHashEntry whose em_relids is equal to the
+ * 'relids' argument. If there are no members satisfying the condition,
+ * NIL will be returned.
+ *
+ * Note: Please confirm the 'deleted' flag in EquivalenceMemberHashEntry.
+ * Further information is available in EquivalenceMemberHashEntry's
+ * comment.
+ */
+static List *FindEcMembersMatchingRelids(EquivalenceClass *ec,
+ Relids relids)
+{
+ EquivalenceMemberHashEntry *entry;
+ bool found;
+
+ if (ec->ec_members_htab == NULL)
+ {
+ return NIL;
+ }
+
+ entry = hash_search(ec->ec_members_htab, &relids,
+ HASH_FIND, &found);
+
+ return found ? entry->list : NIL;
+}
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index a6e5db4eec..bdf85b042d 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -19,6 +19,7 @@
#include "nodes/params.h"
#include "nodes/parsenodes.h"
#include "storage/block.h"
+#include "utils/hsearch.h"
/*
@@ -989,6 +990,9 @@ typedef struct EquivalenceClass
List *ec_opfamilies; /* btree operator family OIDs */
Oid ec_collation; /* collation, if datatypes are collatable */
List *ec_members; /* list of EquivalenceMembers */
+ HTAB *ec_members_htab; /* Hash table for ec_members */
+ List *ec_not_child_members; /* list of EquivalenceMembers
+ which are not children */
List *ec_sources; /* list of generating RestrictInfos */
List *ec_derives; /* list of derived RestrictInfos */
Relids ec_relids; /* all relids appearing in ec_members, except
@@ -1044,6 +1048,34 @@ typedef struct EquivalenceMember
Oid em_datatype; /* the "nominal type" used by the opfamily */
} EquivalenceMember;
+/*
+ * EquivalenceMemberHashEntry
+ *
+ * Key and value of EquivalenceMember::ec_members_htab.
+ * The 'list' field contains EquivalenceMemberListEntries whose em_relids is
+ * equal to the key.
+ */
+typedef struct EquivalenceMemberHashEntry
+{
+ Relids em_relids; /* hash key --- MUST BE FIRST */
+ List *list; /* List of EquivalenceMemberListEntry */
+} EquivalenceMemberHashEntry;
+
+/*
+ * EquivalenceMemberListEntry
+ *
+ * Entry of EquivalenceMemberHashEntry::list.
+ *
+ * Note: Before accessing emem field, confirm that the 'deleted' flag is false.
+ * If the value is true, the corresponding EquivalenceMember no longer exists
+ * in EquivalenceClass::ec_members.
+ */
+typedef struct EquivalenceMemberListEntry
+{
+ EquivalenceMember *emem;
+ bool deleted;
+} EquivalenceMemberListEntry;
+
/*
* PathKeys
*
