eclass_indexes_v5.patch

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 69179a0..4e8400d 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2190,6 +2190,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node)
 	WRITE_NODE_FIELD(cte_plan_ids);
 	WRITE_NODE_FIELD(multiexpr_params);
 	WRITE_NODE_FIELD(eq_classes);
+	WRITE_BOOL_FIELD(ec_merging_done);
 	WRITE_NODE_FIELD(canon_pathkeys);
 	WRITE_NODE_FIELD(left_join_clauses);
 	WRITE_NODE_FIELD(right_join_clauses);
@@ -2256,6 +2257,7 @@ _outRelOptInfo(StringInfo str, const RelOptInfo *node)
 	WRITE_UINT_FIELD(pages);
 	WRITE_FLOAT_FIELD(tuples, "%.0f");
 	WRITE_FLOAT_FIELD(allvisfrac, "%.6f");
+	WRITE_BITMAPSET_FIELD(eclass_indexes);
 	WRITE_NODE_FIELD(subroot);
 	WRITE_NODE_FIELD(subplan_params);
 	WRITE_INT_FIELD(rel_parallel_workers);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 61b5b11..804b211 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -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);
 
 
 /*
@@ -341,10 +345,11 @@ process_equivalence(PlannerInfo *root,
 
 		/*
 		 * Case 2: need to merge ec1 and ec2.  This should never happen after
-		 * we've built any canonical pathkeys; if it did, those pathkeys might
-		 * be rendered non-canonical by the merge.
+		 * the ECs have reached canonical state; otherwise, pathkeys could be
+		 * rendered non-canonical by the merge, and relation eclass indexes
+		 * would get broken by removal of an eq_classes list entry.
 		 */
-		if (root->canon_pathkeys != NIL)
+		if (root->ec_merging_done)
 			elog(ERROR, "too late to merge equivalence classes");
 
 		/*
@@ -743,6 +748,26 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 
 	root->eq_classes = lappend(root->eq_classes, newec);
 
+	/*
+	 * If EC merging is already complete, we have to mop up by adding the new
+	 * EC to the eclass_indexes of the relation(s) mentioned in it.
+	 */
+	if (root->ec_merging_done)
+	{
+		int			ec_index = list_length(root->eq_classes) - 1;
+		int			i = -1;
+
+		while ((i = bms_next_member(newec->ec_relids, i)) > 0)
+		{
+			RelOptInfo *rel = root->simple_rel_array[i];
+
+			Assert(rel->reloptkind == RELOPT_BASEREL);
+
+			rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
+												 ec_index);
+		}
+	}
+
 	MemoryContextSwitchTo(oldcontext);
 
 	return newec;
@@ -800,42 +825,71 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 void
 generate_base_implied_equalities(PlannerInfo *root)
 {
+	int			ec_index;
 	ListCell   *lc;
-	Index		rti;
 
+	/*
+	 * At this point, we're done absorbing knowledge of equivalences in the
+	 * query, so no further EC merging should happen, and ECs remaining in the
+	 * eq_classes list can be considered canonical.  (But note that it's still
+	 * possible for new single-member ECs to be added through
+	 * get_eclass_for_sort_expr().)
+	 */
+	root->ec_merging_done = true;
+
+	ec_index = 0;
 	foreach(lc, root->eq_classes)
 	{
 		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
+		bool		can_generate_joinclause = false;
+		int			i;
 
 		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 */
-		if (list_length(ec->ec_members) <= 1)
-			continue;
+		/*
+		 * Generate implied equalities that are restriction clauses.
+		 * Single-member ECs won't generate any deductions, either here or at
+		 * the join level.
+		 */
+		if (list_length(ec->ec_members) > 1)
+		{
+			if (ec->ec_has_const)
+				generate_base_implied_equalities_const(root, ec);
+			else
+				generate_base_implied_equalities_no_const(root, ec);
 
-		if (ec->ec_has_const)
-			generate_base_implied_equalities_const(root, ec);
-		else
-			generate_base_implied_equalities_no_const(root, ec);
+			/* Recover if we failed to generate required derived clauses */
+			if (ec->ec_broken)
+				generate_base_implied_equalities_broken(root, ec);
 
-		/* Recover if we failed to generate required derived clauses */
-		if (ec->ec_broken)
-			generate_base_implied_equalities_broken(root, ec);
-	}
+			/* Detect whether this EC might generate join clauses */
+			can_generate_joinclause =
+				(bms_membership(ec->ec_relids) == BMS_MULTIPLE);
+		}
 
-	/*
-	 * This is also a handy place to mark base rels (which should all exist by
-	 * now) with flags showing whether they have pending eclass joins.
-	 */
-	for (rti = 1; rti < root->simple_rel_array_size; rti++)
-	{
-		RelOptInfo *brel = root->simple_rel_array[rti];
+		/*
+		 * Mark the base rels cited in each eclass (which should all exist by
+		 * now) with the eq_classes indexes of all eclasses mentioning them.
+		 * This will let us avoid searching in subsequent lookups.  While
+		 * we're at it, we can mark base rels that have pending eclass joins;
+		 * this is a cheap version of has_relevant_eclass_joinclause().
+		 */
+		i = -1;
+		while ((i = bms_next_member(ec->ec_relids, i)) > 0)
+		{
+			RelOptInfo *rel = root->simple_rel_array[i];
 
-		if (brel == NULL)
-			continue;
+			Assert(rel->reloptkind == RELOPT_BASEREL);
+
+			rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
+												 ec_index);
+
+			if (can_generate_joinclause)
+				rel->has_eclass_joins = true;
+		}
 
-		brel->has_eclass_joins = has_relevant_eclass_joinclause(root, brel);
+		ec_index++;
 	}
 }
 
@@ -2037,12 +2091,23 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 	Index		var2varno = fkinfo->ref_relid;
 	AttrNumber	var2attno = fkinfo->confkey[colno];
 	Oid			eqop = fkinfo->conpfeqop[colno];
+	RelOptInfo *rel1 = root->simple_rel_array[var1varno];
+	RelOptInfo *rel2 = root->simple_rel_array[var2varno];
 	List	   *opfamilies = NIL;	/* compute only if needed */
-	ListCell   *lc1;
-
-	foreach(lc1, root->eq_classes)
+	Bitmapset  *matching_ecs;
+	int			i;
+
+	/* Consider only eclasses mentioning both relations */
+	Assert(root->ec_merging_done);
+	Assert(IS_SIMPLE_REL(rel1));
+	Assert(IS_SIMPLE_REL(rel2));
+	matching_ecs = bms_intersect(rel1->eclass_indexes,
+								 rel2->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;
@@ -2052,14 +2117,6 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 			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)
 		{
 			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
@@ -2119,11 +2176,19 @@ add_child_rel_equivalences(PlannerInfo *root,
 						   RelOptInfo *parent_rel,
 						   RelOptInfo *child_rel)
 {
-	ListCell   *lc1;
+	int			i;
 
-	foreach(lc1, root->eq_classes)
+	/*
+	 * EC merging should be complete already, so we can use the parent rel's
+	 * eclass_indexes to avoid searching all of root->eq_classes.
+	 */
+	Assert(root->ec_merging_done);
+	Assert(IS_SIMPLE_REL(parent_rel));
+
+	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;
 
 		/*
@@ -2134,14 +2199,6 @@ add_child_rel_equivalences(PlannerInfo *root,
 		if (cur_ec->ec_has_volatile)
 			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.
-		 */
-		if (parent_rel->reloptkind == RELOPT_BASEREL &&
-			!bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
-			continue;
-
 		foreach(lc2, cur_ec->ec_members)
 		{
 			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
@@ -2191,6 +2248,14 @@ add_child_rel_equivalences(PlannerInfo *root,
 			}
 		}
 	}
+
+	/*
+	 * The child is now mentioned in all the same eclasses as its parent ---
+	 * except for corner cases such as a volatile EC.  But it's okay if
+	 * eclass_indexes lists too many rels, so just borrow the parent's index
+	 * set rather than making a new one.
+	 */
+	child_rel->eclass_indexes = parent_rel->eclass_indexes;
 }
 
 
@@ -2227,7 +2292,10 @@ 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;
+
+	/* Should be OK to rely on eclass_indexes */
+	Assert(root->ec_merging_done);
 
 	/* Indexes are available only on base or "other" member relations. */
 	Assert(IS_SIMPLE_REL(rel));
@@ -2238,9 +2306,10 @@ 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;
 
@@ -2252,14 +2321,6 @@ 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).
-		 */
-		if (!is_child_rel &&
-			!bms_is_subset(rel->relids, cur_ec->ec_relids))
-			continue;
-
-		/*
 		 * Scan members, looking for a match to the target column.  Note that
 		 * child EC members are considered, but only when they belong to the
 		 * target relation.  (Unlike regular members, the same expression
@@ -2352,11 +2413,16 @@ bool
 have_relevant_eclass_joinclause(PlannerInfo *root,
 								RelOptInfo *rel1, RelOptInfo *rel2)
 {
-	ListCell   *lc1;
+	Bitmapset  *matching_ecs;
+	int			i;
 
-	foreach(lc1, root->eq_classes)
+	/* Examine only eclasses mentioning both 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
@@ -2384,6 +2450,10 @@ 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.
+		 *
+		 * The bms_overlap tests here are normally redundant, given the work
+		 * done by get_common_eclass_indexes, but we keep them in case either
+		 * rel's eclass_indexes contains extra entries.
 		 */
 		if (bms_overlap(rel1->relids, ec->ec_relids) &&
 			bms_overlap(rel2->relids, ec->ec_relids))
@@ -2405,11 +2475,16 @@ 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)
+	/* Examine only eclasses mentioning rel1 */
+	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
@@ -2556,3 +2631,54 @@ 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 mention any of these relids
+ */
+static Bitmapset *
+get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
+{
+	Bitmapset  *ec_indexes = NULL;
+	int			i = -1;
+
+	/* Should be OK to rely on eclass_indexes */
+	Assert(root->ec_merging_done);
+
+	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 mention rels in both
+ *		relids1 and relids2.
+ */
+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 relation's eclass_indexes directly
+	 * when 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/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 56d839b..c34380f 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -42,9 +42,7 @@ static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
  *	  entry if there's not one already.
  *
  * Note that this function must not be used until after we have completed
- * merging EquivalenceClasses.  (We don't try to enforce that here; instead,
- * equivclass.c will complain if a merge occurs after root->canon_pathkeys
- * has become nonempty.)
+ * merging EquivalenceClasses.
  */
 PathKey *
 make_canonical_pathkey(PlannerInfo *root,
@@ -55,6 +53,10 @@ make_canonical_pathkey(PlannerInfo *root,
 	ListCell   *lc;
 	MemoryContext oldcontext;
 
+	/* Can't make canonical pathkeys if the set of ECs might still change */
+	if (!root->ec_merging_done)
+		elog(ERROR, "too soon to build canonical pathkeys");
+
 	/* The passed eclass might be non-canonical, so chase up to the top */
 	while (eclass->ec_merged)
 		eclass = eclass->ec_merged;
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 3cedd01..9fc1b24 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -142,6 +142,12 @@ query_planner(PlannerInfo *root, List *tlist,
 				set_cheapest(final_rel);
 
 				/*
+				 * We don't need to run generate_base_implied_equalities, but
+				 * we do need to pretend that EC merging is complete.
+				 */
+				root->ec_merging_done = true;
+
+				/*
 				 * We still are required to call qp_callback, in case it's
 				 * something like "SELECT 2+2 ORDER BY 1".
 				 */
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index e408e77..0a0fc97 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -620,6 +620,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root->cte_plan_ids = NIL;
 	root->multiexpr_params = NIL;
 	root->eq_classes = NIL;
+	root->ec_merging_done = false;
 	root->append_rel_list = NIL;
 	root->rowMarks = NIL;
 	memset(root->upper_rels, 0, sizeof(root->upper_rels));
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index aebe162..5d4aa60 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -886,6 +886,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->cte_plan_ids = NIL;
 	subroot->multiexpr_params = NIL;
 	subroot->eq_classes = NIL;
+	subroot->ec_merging_done = false;
 	subroot->append_rel_list = NIL;
 	subroot->rowMarks = NIL;
 	memset(subroot->upper_rels, 0, sizeof(subroot->upper_rels));
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index eb815c2..3a5482b 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -121,6 +121,15 @@ plan_set_operations(PlannerInfo *root)
 	Assert(parse->distinctClause == NIL);
 
 	/*
+	 * In the outer query level, we won't have any true equivalences to deal
+	 * with; but we do want to be able to make pathkeys, which will require
+	 * single-member EquivalenceClasses.  Indicate that EC merging is complete
+	 * so that pathkeys.c won't complain.
+	 */
+	Assert(root->eq_classes == NIL);
+	root->ec_merging_done = true;
+
+	/*
 	 * We'll need to build RelOptInfos for each of the leaf subqueries, which
 	 * are RTE_SUBQUERY rangetable entries in this Query.  Prepare the index
 	 * arrays for that.
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 4130514..4a3a4e3 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -178,6 +178,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
 	rel->pages = 0;
 	rel->tuples = 0;
 	rel->allvisfrac = 0;
+	rel->eclass_indexes = NULL;
 	rel->subroot = NULL;
 	rel->subplan_params = NIL;
 	rel->rel_parallel_workers = -1; /* set up in get_relation_info */
@@ -600,6 +601,7 @@ build_join_rel(PlannerInfo *root,
 	joinrel->pages = 0;
 	joinrel->tuples = 0;
 	joinrel->allvisfrac = 0;
+	joinrel->eclass_indexes = NULL;
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->rel_parallel_workers = -1;
@@ -779,6 +781,7 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
 	joinrel->pages = 0;
 	joinrel->tuples = 0;
 	joinrel->allvisfrac = 0;
+	joinrel->eclass_indexes = NULL;
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->serverid = InvalidOid;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 253e0b7..bdf43ae 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -265,6 +265,8 @@ struct PlannerInfo
 
 	List	   *eq_classes;		/* list of active EquivalenceClasses */
 
+	bool		ec_merging_done;	/* set true once ECs are canonical */
+
 	List	   *canon_pathkeys; /* list of "canonical" PathKeys */
 
 	List	   *left_join_clauses;	/* list of RestrictInfos for mergejoinable
@@ -495,6 +497,8 @@ typedef struct PartitionSchemeData *PartitionScheme;
  *		pages - number of disk pages in relation (zero if not a table)
  *		tuples - number of tuples in relation (not considering restrictions)
  *		allvisfrac - fraction of disk pages that are marked all-visible
+ *		eclass_indexes - EquivalenceClasses that mention this rel (filled
+ *						 only after EC merging is complete)
  *		subroot - PlannerInfo for subquery (NULL if it's not a subquery)
  *		subplan_params - list of PlannerParamItems to be passed to subquery
  *
@@ -668,6 +672,8 @@ typedef struct RelOptInfo
 	BlockNumber pages;			/* size estimates derived from pg_class */
 	double		tuples;
 	double		allvisfrac;
+	Bitmapset  *eclass_indexes; /* Indexes in PlannerInfo's eq_classes list of
+								 * ECs that mention this rel */
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	int			rel_parallel_workers;	/* wanted number of parallel workers */