eclass_indexes_v2.patch

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 61b5b119b0..dae7a842a1 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 void delete_eclass(PlannerInfo *root, EquivalenceClass *ec,
+			  int ec_index);
 
 
 /*
@@ -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);
@@ -254,11 +261,14 @@ 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++;
+
 		/* Never match to a volatile EC */
 		if (cur_ec->ec_has_volatile)
 			continue;
@@ -298,6 +308,7 @@ process_equivalence(PlannerInfo *root,
 			{
 				ec1 = cur_ec;
 				em1 = cur_em;
+				ec1idx = cur_ec_idx;
 				if (ec2)
 					break;
 			}
@@ -308,6 +319,7 @@ process_equivalence(PlannerInfo *root,
 			{
 				ec2 = cur_ec;
 				em2 = cur_em;
+				ec2idx = cur_ec_idx;
 				if (ec1)
 					break;
 			}
@@ -366,12 +378,10 @@ 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: */
-		ec2->ec_members = NIL;
-		ec2->ec_sources = NIL;
-		ec2->ec_derives = NIL;
-		ec2->ec_relids = NULL;
+
+		/* Do the deed */
+		delete_eclass(root, ec2, ec2idx);
+
 		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,
@@ -388,8 +398,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 +416,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 +450,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,10 +551,14 @@ 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);
 
@@ -568,9 +584,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);
 
@@ -720,7 +751,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);
 
 	/*
@@ -1096,7 +1128,10 @@ 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  *inner_ecs;
+	Bitmapset  *join_ecs;
+	Bitmapset  *matching_ecs;
+	int			i;
 
 	/* If inner rel is a child, extra setup work is needed */
 	if (IS_OTHER_REL(inner_rel))
@@ -1114,9 +1149,16 @@ generate_join_implied_equalities_for_ecs(PlannerInfo *root,
 		nominal_join_relids = join_relids;
 	}
 
-	foreach(lc, eclasses)
+	inner_ecs = get_eclass_indexes_for_relids(root, inner_relids);
+	join_ecs = get_eclass_indexes_for_relids(root, join_relids);
+
+	/* Determine all eclasses in common between inner rels and join rels */
+	matching_ecs = bms_int_members(inner_ecs, join_ecs);
+
+	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 */
@@ -1127,9 +1169,8 @@ generate_join_implied_equalities_for_ecs(PlannerInfo *root,
 		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;
+		/* Ensure 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,
@@ -2038,31 +2079,32 @@ 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;
 
 		/* 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)
@@ -2120,12 +2162,16 @@ add_child_rel_equivalences(PlannerInfo *root,
 						   RelOptInfo *child_rel)
 {
 	ListCell   *lc1;
+	int			i;
 
+	i = -1;
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 		ListCell   *lc2;
 
+		i++;
+
 		/*
 		 * If this EC contains a volatile expression, then generating child
 		 * EMs would be downright dangerous, so skip it.  We rely on a
@@ -2185,7 +2231,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 +2273,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,11 +2284,12 @@ 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
@@ -2252,12 +2299,11 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 			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 +2316,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 +2332,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,11 +2398,21 @@ bool
 have_relevant_eclass_joinclause(PlannerInfo *root,
 								RelOptInfo *rel1, RelOptInfo *rel2)
 {
-	ListCell   *lc1;
+	Bitmapset	   *rel1_ecs;
+	Bitmapset	   *rel2_ecs;
+	Bitmapset	   *matching_ecs;
+	int				i;
 
-	foreach(lc1, root->eq_classes)
+	rel1_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
+	rel2_ecs = get_eclass_indexes_for_relids(root, rel2->relids);
+	matching_ecs = bms_int_members(rel1_ecs, rel2_ecs);
+
+	/* XXX or can we just return bms_overlap(rel1_ecs, rel2_ecs) ? */
+
+	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
@@ -2384,10 +2440,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 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,11 +2467,18 @@ 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
@@ -2418,12 +2487,13 @@ has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
 		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;
 	}
 
@@ -2556,3 +2626,93 @@ 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;
+}
+
+/*
+ * delete_eclass
+ *		Remove ec from root's eq_classes list and nullify various properties
+ *		of the EquivalenceClass.  Does not free memory for ec.
+ *
+ * We also resequence each relation's eclass_indexes to remove reference to
+ * this EquivalenceClass and shift the indexes for higher index classes down
+ * one place.
+ *
+ * ec_index is the index that ec belongs to in root's eq_classes list.  We
+ * could look this up within, but the current caller just happens to know it,
+ * so passing it in saves looking it up here.
+ */
+static void
+delete_eclass(PlannerInfo *root, EquivalenceClass *ec, int ec_index)
+{
+	Index	i;
+
+	Assert(ec_index >= 0 && ec_index < list_length(root->eq_classes));
+	Assert(list_nth(root->eq_classes, ec_index) == ec);
+
+	/* Remove the eclass from the list */
+	root->eq_classes = list_delete_ptr(root->eq_classes, ec);
+
+	/*
+	 * Now we must update the eclass_indexes bitmapset for each relation to
+	 * remove mention of this eclass and move higher indexes down 1 bit.
+	 */
+	for (i = 1; i < root->simple_rel_array_size; i++)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+		Bitmapset *new_ec_indexes;
+		int			e;
+
+		if (rel == NULL)
+			continue;
+
+		/*
+		 * We can skip rels that don't have members in any eclass with an
+		 * index >= to ec_index.  If ec_index is 0 then this will just skip
+		 * rels with no eclasses.
+		 */
+		if (bms_next_member(rel->eclass_indexes, ec_index - 1) < 0)
+			continue;
+
+		/*
+		 * XXX is it worth adding a bms supporting function to shift right
+		 * bits from a given position?
+		 */
+		new_ec_indexes = NULL;
+		e = -1;
+		while ((e = bms_next_member(rel->eclass_indexes, e)) >= 0)
+		{
+			if (e < ec_index)
+				new_ec_indexes = bms_add_member(new_ec_indexes, e);
+			else if (e > ec_index)
+				new_ec_indexes = bms_add_member(new_ec_indexes, e - 1);
+		}
+
+		bms_free(rel->eclass_indexes);
+		rel->eclass_indexes = new_ec_indexes;
+	}
+
+	/* just to avoid debugging confusion w/ dangling pointers: */
+	ec->ec_members = NIL;
+	ec->ec_sources = NIL;
+	ec->ec_derives = NIL;
+	ec->ec_relids = NULL;
+}
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 253e0b7e48..911d0c46fa 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: */