v2-reducing-planning-time-when-tables-have-many-partitions.patch

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
  *