eclass_indexes_v4.patch

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 61b5b119b0..3c37665d18 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -31,8 +31,8 @@
 #include "optimizer/restrictinfo.h"
 #include "utils/lsyscache.h"
 
-
-static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
+static EquivalenceMember *add_eq_member(PlannerInfo *root,
+			  EquivalenceClass *ec, int ec_index,
 			  Expr *expr, Relids relids, Relids nullable_relids,
 			  bool is_child, Oid datatype);
 static void generate_base_implied_equalities_const(PlannerInfo *root,
@@ -64,6 +64,10 @@ static bool reconsider_outer_join_clause(PlannerInfo *root,
 							 bool outer_on_left);
 static bool reconsider_full_join_clause(PlannerInfo *root,
 							RestrictInfo *rinfo);
+static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root,
+							  Relids relids);
+static Bitmapset *get_common_eclass_indexes(PlannerInfo *root, Relids relids1,
+						  Relids relids2);
 
 
 /*
@@ -133,6 +137,9 @@ process_equivalence(PlannerInfo *root,
 	EquivalenceMember *em1,
 			   *em2;
 	ListCell   *lc1;
+	int			ec1idx,
+				ec2idx,
+				cur_ec_idx;
 
 	/* Should not already be marked as having generated an eclass */
 	Assert(restrictinfo->left_ec == NULL);
@@ -150,6 +157,8 @@ process_equivalence(PlannerInfo *root,
 	item2 = (Expr *) get_rightop(clause);
 	item1_relids = restrictinfo->left_relids;
 	item2_relids = restrictinfo->right_relids;
+	ec1idx = -1;
+	ec2idx = -1;
 
 	/*
 	 * Ensure both input expressions expose the desired collation (their types
@@ -254,11 +263,18 @@ process_equivalence(PlannerInfo *root,
 	 */
 	ec1 = ec2 = NULL;
 	em1 = em2 = NULL;
+	cur_ec_idx = -1;
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 		ListCell   *lc2;
 
+		cur_ec_idx++;
+
+		/* skip deleted ECs */
+		if (cur_ec->ec_members == NIL)
+			continue;
+
 		/* Never match to a volatile EC */
 		if (cur_ec->ec_has_volatile)
 			continue;
@@ -298,6 +314,7 @@ process_equivalence(PlannerInfo *root,
 			{
 				ec1 = cur_ec;
 				em1 = cur_em;
+				ec1idx = cur_ec_idx;
 				if (ec2)
 					break;
 			}
@@ -308,6 +325,7 @@ process_equivalence(PlannerInfo *root,
 			{
 				ec2 = cur_ec;
 				em2 = cur_em;
+				ec2idx = cur_ec_idx;
 				if (ec1)
 					break;
 			}
@@ -349,10 +367,11 @@ process_equivalence(PlannerInfo *root,
 
 		/*
 		 * We add ec2's items to ec1, then set ec2's ec_merged link to point
-		 * to ec1 and remove ec2 from the eq_classes list.  We cannot simply
-		 * delete ec2 because that could leave dangling pointers in existing
-		 * PathKeys.  We leave it behind with a link so that the merged EC can
-		 * be found.
+		 * to ec1.  We cannot simply delete ec2 because that could leave
+		 * dangling pointers in existing PathKeys.  We leave it behind with a
+		 * link so that the merged EC can be found.  We don't remove the EC
+		 * from the eq_classes list either, instead, we nullify the ec_members
+		 * list to mark it deleted.
 		 */
 		ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
 		ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
@@ -366,8 +385,12 @@ process_equivalence(PlannerInfo *root,
 		ec1->ec_max_security = Max(ec1->ec_max_security,
 								   ec2->ec_max_security);
 		ec2->ec_merged = ec1;
-		root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
-		/* just to avoid debugging confusion w/ dangling pointers: */
+
+		/*
+		 * Nullify ec_members to mark the EC as deleted.  Also set some other
+		 * fields to null just to avoid debugging confusion w/ dangling
+		 * pointers:
+		 */
 		ec2->ec_members = NIL;
 		ec2->ec_sources = NIL;
 		ec2->ec_derives = NIL;
@@ -388,8 +411,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, ec1idx, 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,
@@ -406,8 +429,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, ec2idx, 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,
@@ -440,10 +463,12 @@ 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, list_length(root->eq_classes), item1,
+							item1_relids, item1_nullable_relids, false,
+							item1_type);
+		em2 = add_eq_member(root, ec, list_length(root->eq_classes), item2,
+							item2_relids, item2_nullable_relids, false,
+							item2_type);
 
 		root->eq_classes = lappend(root->eq_classes, ec);
 
@@ -539,13 +564,19 @@ canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
 
 /*
  * add_eq_member - build a new EquivalenceMember and add it to an EC
+ *
+ * ec_index must be the list index that this ec is, or will be stored in
+ * root's eq_classes.
  */
 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, int ec_index,
+			  Expr *expr, Relids relids, Relids nullable_relids,
+			  bool is_child, Oid datatype)
 {
 	EquivalenceMember *em = makeNode(EquivalenceMember);
 
+	Assert(ec_index >= 0);
+
 	em->em_expr = expr;
 	em->em_relids = relids;
 	em->em_nullable_relids = nullable_relids;
@@ -568,9 +599,24 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 		ec->ec_has_const = true;
 		/* it can't affect ec_relids */
 	}
-	else if (!is_child)			/* child members don't add to ec_relids */
+	else
 	{
-		ec->ec_relids = bms_add_members(ec->ec_relids, relids);
+		int			i;
+
+		/* Record this eclass in each rel's eclass_indexes set */
+		i = -1;
+		while ((i = bms_next_member(relids, i)) > 0)
+		{
+			RelOptInfo *rel = root->simple_rel_array[i];
+
+			rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
+												 ec_index);
+		}
+
+		if (!is_child)			/* child members don't add to ec_relids */
+		{
+			ec->ec_relids = bms_add_members(ec->ec_relids, relids);
+		}
 	}
 	ec->ec_members = lappend(ec->ec_members, em);
 
@@ -652,6 +698,10 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 		ListCell   *lc2;
 
+		/* skip deleted ECs */
+		if (cur_ec->ec_members == NIL)
+			continue;
+
 		/*
 		 * Never match to a volatile EC, except when we are looking at another
 		 * reference to the same volatile SortGroupClause.
@@ -720,7 +770,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	if (newec->ec_has_volatile && sortref == 0) /* should not happen */
 		elog(ERROR, "volatile EquivalenceClass has no sortref");
 
-	newem = add_eq_member(newec, copyObject(expr), expr_relids,
+	newem = add_eq_member(root, newec, list_length(root->eq_classes),
+						  copyObject(expr), expr_relids,
 						  nullable_relids, false, opcintype);
 
 	/*
@@ -807,10 +858,9 @@ generate_base_implied_equalities(PlannerInfo *root)
 	{
 		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
 
-		Assert(ec->ec_merged == NULL);	/* else shouldn't be in list */
 		Assert(!ec->ec_broken); /* not yet anyway... */
 
-		/* Single-member ECs won't generate any deductions */
+		/* Zero or single-member ECs won't generate any deductions */
 		if (list_length(ec->ec_members) <= 1)
 			continue;
 
@@ -1096,7 +1146,8 @@ generate_join_implied_equalities_for_ecs(PlannerInfo *root,
 	Relids		inner_relids = inner_rel->relids;
 	Relids		nominal_inner_relids;
 	Relids		nominal_join_relids;
-	ListCell   *lc;
+	Bitmapset  *matching_ecs;
+	int			i;
 
 	/* If inner rel is a child, extra setup work is needed */
 	if (IS_OTHER_REL(inner_rel))
@@ -1114,22 +1165,25 @@ generate_join_implied_equalities_for_ecs(PlannerInfo *root,
 		nominal_join_relids = join_relids;
 	}
 
-	foreach(lc, eclasses)
+	/* Get all eclasses in common between inner_relids and join_relids */
+	matching_ecs = get_common_eclass_indexes(root, inner_relids, join_relids);
+
+	i = -1;
+	while ((i = bms_next_member(matching_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
+		EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		List	   *sublist = NIL;
 
 		/* ECs containing consts do not need any further enforcement */
 		if (ec->ec_has_const)
 			continue;
 
-		/* Single-member ECs won't generate any deductions */
+		/* Zero or single-member ECs won't generate any deductions */
 		if (list_length(ec->ec_members) <= 1)
 			continue;
 
-		/* We can quickly ignore any that don't overlap the join, too */
-		if (!bms_overlap(ec->ec_relids, nominal_join_relids))
-			continue;
+		/* Sanity check that this eclass overlaps the join */
+		Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
 
 		if (!ec->ec_broken)
 			sublist = generate_join_implied_equalities_normal(root,
@@ -1727,6 +1781,9 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 		bool		match;
 		ListCell   *lc2;
 
+		/* skip deleted ECs */
+		if (cur_ec->ec_members == NIL)
+			continue;
 		/* Ignore EC unless it contains pseudoconstants */
 		if (!cur_ec->ec_has_const)
 			continue;
@@ -1845,6 +1902,9 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		bool		matchright;
 		ListCell   *lc2;
 
+		/* skip deleted ECs */
+		if (cur_ec->ec_members == NIL)
+			continue;
 		/* Ignore EC unless it contains pseudoconstants */
 		if (!cur_ec->ec_has_const)
 			continue;
@@ -1992,6 +2052,9 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
 		bool		item2member = false;
 		ListCell   *lc2;
 
+		/* skip deleted ECs */
+		if (ec->ec_members == NIL)
+			continue;
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
 			continue;
@@ -2038,31 +2101,36 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 	AttrNumber	var2attno = fkinfo->confkey[colno];
 	Oid			eqop = fkinfo->conpfeqop[colno];
 	List	   *opfamilies = NIL;	/* compute only if needed */
-	ListCell   *lc1;
+	Bitmapset  *matching_ecs;
+	int			i;
 
-	foreach(lc1, root->eq_classes)
+	/* Determine which eclasses contain members for both of the relations */
+	matching_ecs = bms_intersect(root->simple_rel_array[var1varno]->eclass_indexes,
+								 root->simple_rel_array[var2varno]->eclass_indexes);
+
+	i = -1;
+	while ((i = bms_next_member(matching_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
+		EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		bool		item1member = false;
 		bool		item2member = false;
-		ListCell   *lc2;
+		ListCell   *lc;
+
+		/* skip deleted ECs */
+		if (ec->ec_members == NIL)
+			continue;
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
 			continue;
 		/* Note: it seems okay to match to "broken" eclasses here */
 
-		/*
-		 * If eclass visibly doesn't have members for both rels, there's no
-		 * need to grovel through the members.
-		 */
-		if (!bms_is_member(var1varno, ec->ec_relids) ||
-			!bms_is_member(var2varno, ec->ec_relids))
-			continue;
-
-		foreach(lc2, ec->ec_members)
+		/* Ensure no corruption of eclass_indexes */
+		Assert(bms_is_member(var1varno, ec->ec_relids));
+		Assert(bms_is_member(var2varno, ec->ec_relids));
+		foreach(lc, ec->ec_members)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
 			Var		   *var;
 
 			if (em->em_is_child)
@@ -2119,13 +2187,18 @@ add_child_rel_equivalences(PlannerInfo *root,
 						   RelOptInfo *parent_rel,
 						   RelOptInfo *child_rel)
 {
-	ListCell   *lc1;
+	int			i;
 
-	foreach(lc1, root->eq_classes)
+	i = -1;
+	while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
 	{
-		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
+		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		ListCell   *lc2;
 
+		/* skip deleted ECs */
+		if (cur_ec->ec_members == NIL)
+			continue;
+
 		/*
 		 * If this EC contains a volatile expression, then generating child
 		 * EMs would be downright dangerous, so skip it.  We rely on a
@@ -2135,12 +2208,11 @@ add_child_rel_equivalences(PlannerInfo *root,
 			continue;
 
 		/*
-		 * No point in searching if parent rel not mentioned in eclass; but we
-		 * can't tell that for sure if parent rel is itself a child.
+		 * Sanity check that eclass_indexes only contains indexes of ECs for
+		 * this parent_rel.  If it's not a baserel then ec_relids are not set.
 		 */
-		if (parent_rel->reloptkind == RELOPT_BASEREL &&
-			!bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
-			continue;
+		Assert(parent_rel->reloptkind != RELOPT_BASEREL ||
+			   bms_is_subset(parent_rel->relids, cur_ec->ec_relids));
 
 		foreach(lc2, cur_ec->ec_members)
 		{
@@ -2185,7 +2257,7 @@ add_child_rel_equivalences(PlannerInfo *root,
 														  child_rel->relids);
 				}
 
-				(void) add_eq_member(cur_ec, child_expr,
+				(void) add_eq_member(root, cur_ec, i, child_expr,
 									 new_relids, new_nullable_relids,
 									 true, cur_em->em_datatype);
 			}
@@ -2227,7 +2299,7 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 	List	   *result = NIL;
 	bool		is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
 	Relids		parent_relids;
-	ListCell   *lc1;
+	int			i;
 
 	/* Indexes are available only on base or "other" member relations. */
 	Assert(IS_SIMPLE_REL(rel));
@@ -2238,26 +2310,26 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 	else
 		parent_relids = NULL;	/* not used, but keep compiler quiet */
 
-	foreach(lc1, root->eq_classes)
+	i = -1;
+	while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
 	{
-		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
+		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		EquivalenceMember *cur_em;
-		ListCell   *lc2;
+		ListCell   *lc;
 
 		/*
-		 * Won't generate joinclauses if const or single-member (the latter
-		 * test covers the volatile case too)
+		 * Won't generate joinclauses if const, zero or single-member (the
+		 * latter test covers the volatile case too)
 		 */
 		if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
 			continue;
 
 		/*
-		 * No point in searching if rel not mentioned in eclass (but we can't
-		 * tell that for a child rel).
+		 * Ensure that these relids are mentioned in the eclass.  Child rels
+		 * won't be mentioned in ec_relids, so skip the check for those
 		 */
-		if (!is_child_rel &&
-			!bms_is_subset(rel->relids, cur_ec->ec_relids))
-			continue;
+		Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
+
 
 		/*
 		 * Scan members, looking for a match to the target column.  Note that
@@ -2270,9 +2342,9 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		 * match.  See also get_eclass_for_sort_expr.)
 		 */
 		cur_em = NULL;
-		foreach(lc2, cur_ec->ec_members)
+		foreach(lc, cur_ec->ec_members)
 		{
-			cur_em = (EquivalenceMember *) lfirst(lc2);
+			cur_em = (EquivalenceMember *) lfirst(lc);
 			if (bms_equal(cur_em->em_relids, rel->relids) &&
 				callback(root, rel, cur_ec, cur_em, callback_arg))
 				break;
@@ -2286,9 +2358,9 @@ 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)
+		foreach(lc, cur_ec->ec_members)
 		{
-			EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc);
 			Oid			eq_op;
 			RestrictInfo *rinfo;
 
@@ -2352,15 +2424,20 @@ bool
 have_relevant_eclass_joinclause(PlannerInfo *root,
 								RelOptInfo *rel1, RelOptInfo *rel2)
 {
-	ListCell   *lc1;
+	Bitmapset  *matching_ecs;
+	int			i;
 
-	foreach(lc1, root->eq_classes)
+	/* Get all eclasses in common between rel1 and rel2 */
+	matching_ecs = get_common_eclass_indexes(root, rel1->relids, rel2->relids);
+
+	i = -1;
+	while ((i = bms_next_member(matching_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
+		EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 
 		/*
-		 * Won't generate joinclauses if single-member (this test covers the
-		 * volatile case too)
+		 * Won't generate joinclauses for zero or single-member ECs (this test
+		 * covers the volatile case too)
 		 */
 		if (list_length(ec->ec_members) <= 1)
 			continue;
@@ -2384,10 +2461,16 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
 		 * b.y and a.x = 42", it is worth considering a join between a and b,
 		 * since the join result is likely to be small even though it'll end
 		 * up being an unqualified nestloop.
+		 *
+		 * Since matching_ecs only contains eclasses common to both relations
+		 * and since we skipped zero and single member eclasses above, we can
+		 * simply return true.
 		 */
-		if (bms_overlap(rel1->relids, ec->ec_relids) &&
-			bms_overlap(rel2->relids, ec->ec_relids))
-			return true;
+
+		Assert(bms_overlap(rel1->relids, ec->ec_relids));
+		Assert(bms_overlap(rel2->relids, ec->ec_relids));
+
+		return true;
 	}
 
 	return false;
@@ -2405,25 +2488,33 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
 bool
 has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
 {
-	ListCell   *lc1;
+	Bitmapset  *matched_ecs;
+	int			i;
 
-	foreach(lc1, root->eq_classes)
+	if (IS_SIMPLE_REL(rel1))
+		matched_ecs = rel1->eclass_indexes;
+	else
+		matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
+
+	i = -1;
+	while ((i = bms_next_member(matched_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
+		EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 
 		/*
-		 * Won't generate joinclauses if single-member (this test covers the
-		 * volatile case too)
+		 * Won't generate joinclauses for zero or single-member ECs (this test
+		 * covers the volatile case too)
 		 */
 		if (list_length(ec->ec_members) <= 1)
 			continue;
 
+		Assert(bms_overlap(rel1->relids, ec->ec_relids));
+
 		/*
 		 * Per the comment in have_relevant_eclass_joinclause, it's sufficient
 		 * to find an EC that mentions both this rel and some other rel.
 		 */
-		if (bms_overlap(rel1->relids, ec->ec_relids) &&
-			!bms_is_subset(ec->ec_relids, rel1->relids))
+		if (!bms_is_subset(ec->ec_relids, rel1->relids))
 			return true;
 	}
 
@@ -2449,11 +2540,9 @@ eclass_useful_for_merging(PlannerInfo *root,
 	Relids		relids;
 	ListCell   *lc;
 
-	Assert(!eclass->ec_merged);
-
 	/*
-	 * Won't generate joinclauses if const or single-member (the latter test
-	 * covers the volatile case too)
+	 * Won't generate joinclauses if const, zero or single-member (the latter
+	 * test covers the volatile case too)
 	 */
 	if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
 		return false;
@@ -2556,3 +2645,51 @@ is_redundant_with_indexclauses(RestrictInfo *rinfo, List *indexclauses)
 
 	return false;
 }
+
+/*
+ * get_eclass_indexes_for_relids
+ *		Build and return a Bitmapset containing the indexes into root's
+ *		eq_classes list for all eclasses that have members for these relids
+ */
+static Bitmapset *
+get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
+{
+	Bitmapset  *ec_indexes = NULL;
+	int			i = -1;
+
+	while ((i = bms_next_member(relids, i)) > 0)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		ec_indexes = bms_add_members(ec_indexes, rel->eclass_indexes);
+	}
+	return ec_indexes;
+}
+
+/*
+ * get_common_eclass_indexes
+ *		Build and return a Bitmapset containing the indexes into root's
+ *		eq_classes list for all eclasses that relids1 and relids2 have in
+ *		common.
+ */
+static Bitmapset *
+get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
+{
+	Bitmapset  *rel1ecs;
+	Bitmapset  *rel2ecs;
+	int			relid;
+
+	rel1ecs = get_eclass_indexes_for_relids(root, relids1);
+
+	/*
+	 * We can get away with just using the eclass_indexes directly if relids2
+	 * is a singleton set.
+	 */
+	if (bms_get_singleton_member(relids2, &relid))
+		rel2ecs = root->simple_rel_array[relid]->eclass_indexes;
+	else
+		rel2ecs = get_eclass_indexes_for_relids(root, relids2);
+
+	/* Calculate and return the common EC indexes recycling the left input. */
+	return bms_int_members(rel1ecs, rel2ecs);
+}
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 253e0b7e48..9542633d19 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -692,6 +692,8 @@ typedef struct RelOptInfo
 											 * baserestrictinfo */
 	List	   *joininfo;		/* RestrictInfo structures for join clauses
 								 * involving this rel */
+	Bitmapset  *eclass_indexes;	/* Indexes into PlannerInfo's eq_classes that
+								 * know about this relation. */
 	bool		has_eclass_joins;	/* T means joininfo is incomplete */
 
 	/* used by partitionwise joins: */
@@ -917,7 +919,8 @@ typedef struct EquivalenceClass
 
 	List	   *ec_opfamilies;	/* btree operator family OIDs */
 	Oid			ec_collation;	/* collation, if datatypes are collatable */
-	List	   *ec_members;		/* list of EquivalenceMembers */
+	List	   *ec_members;		/* list of EquivalenceMembers, or NIL if EC
+								 * has been deleted and should be ignored */
 	List	   *ec_sources;		/* list of generating RestrictInfos */
 	List	   *ec_derives;		/* list of derived RestrictInfos */
 	Relids		ec_relids;		/* all relids appearing in ec_members, except