v23-0002-Introduce-indexes-for-RestrictInfo.patch

From f4f0c7ade55cc5f0d3fc2bc62934710b8e12fa8d Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Fri, 25 Aug 2023 10:44:25 +0900
Subject: [PATCH v23 2/6] Introduce indexes for RestrictInfo

This change was picked up from v19.

Author: David Rowley <dgrowley@gmail.com> and me
---
 src/backend/nodes/outfuncs.c              |   6 +-
 src/backend/nodes/readfuncs.c             |   2 +
 src/backend/optimizer/path/costsize.c     |   3 +-
 src/backend/optimizer/path/equivclass.c   | 338 +++++++++++++++++++---
 src/backend/optimizer/plan/analyzejoins.c |   8 +-
 src/backend/optimizer/plan/planner.c      |   2 +
 src/backend/optimizer/prep/prepjointree.c |   2 +
 src/backend/optimizer/util/inherit.c      |   7 +
 src/include/nodes/parsenodes.h            |   6 +
 src/include/nodes/pathnodes.h             |  47 ++-
 src/include/optimizer/paths.h             |  15 +-
 11 files changed, 383 insertions(+), 53 deletions(-)

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 97ab5d3770..98f824ac53 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -465,8 +465,8 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
 	WRITE_NODE_FIELD(ec_members);
 	WRITE_NODE_FIELD(ec_norel_members);
 	WRITE_NODE_FIELD(ec_rel_members);
-	WRITE_NODE_FIELD(ec_sources);
-	WRITE_NODE_FIELD(ec_derives);
+	WRITE_BITMAPSET_FIELD(ec_source_indexes);
+	WRITE_BITMAPSET_FIELD(ec_derive_indexes);
 	WRITE_BITMAPSET_FIELD(ec_relids);
 	WRITE_BOOL_FIELD(ec_has_const);
 	WRITE_BOOL_FIELD(ec_has_volatile);
@@ -569,6 +569,8 @@ _outRangeTblEntry(StringInfo str, const RangeTblEntry *node)
 	WRITE_BOOL_FIELD(inh);
 	WRITE_BOOL_FIELD(inFromCl);
 	WRITE_NODE_FIELD(securityQuals);
+	WRITE_BITMAPSET_FIELD(eclass_source_indexes);
+	WRITE_BITMAPSET_FIELD(eclass_derive_indexes);
 }
 
 static void
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index 1624b34581..deebfaf994 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -574,6 +574,8 @@ _readRangeTblEntry(void)
 	READ_BOOL_FIELD(inh);
 	READ_BOOL_FIELD(inFromCl);
 	READ_NODE_FIELD(securityQuals);
+	READ_BITMAPSET_FIELD(eclass_source_indexes);
+	READ_BITMAPSET_FIELD(eclass_derive_indexes);
 
 	READ_DONE();
 }
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 8b76e98529..ae64b169f8 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -5784,7 +5784,8 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
 				if (ec && ec->ec_has_const)
 				{
 					EquivalenceMember *em = fkinfo->fk_eclass_member[i];
-					RestrictInfo *rinfo = find_derived_clause_for_ec_member(ec,
+					RestrictInfo *rinfo = find_derived_clause_for_ec_member(root,
+																			ec,
 																			em);
 
 					if (rinfo)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index d9eb4610ce..d1019315ea 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -42,6 +42,10 @@ static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
 										Expr *expr, Relids relids,
 										JoinDomain *jdomain,
 										Oid datatype);
+static void add_eq_source(PlannerInfo *root, EquivalenceClass *ec,
+						  RestrictInfo *rinfo);
+static void add_eq_derive(PlannerInfo *root, EquivalenceClass *ec,
+						  RestrictInfo *rinfo);
 static bool is_exprlist_member(Expr *node, List *exprs);
 static void generate_base_implied_equalities_const(PlannerInfo *root,
 												   EquivalenceClass *ec);
@@ -321,7 +325,6 @@ process_equivalence(PlannerInfo *root,
 		/* If case 1, nothing to do, except add to sources */
 		if (ec1 == ec2)
 		{
-			ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 			ec1->ec_min_security = Min(ec1->ec_min_security,
 									   restrictinfo->security_level);
 			ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -332,6 +335,8 @@ process_equivalence(PlannerInfo *root,
 			/* mark the RI as usable with this pair of EMs */
 			restrictinfo->left_em = em1;
 			restrictinfo->right_em = em2;
+
+			add_eq_source(root, ec1, restrictinfo);
 			return true;
 		}
 
@@ -356,8 +361,10 @@ process_equivalence(PlannerInfo *root,
 											ec2->ec_norel_members);
 		ec1->ec_rel_members = list_concat(ec1->ec_rel_members,
 										  ec2->ec_rel_members);
-		ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
-		ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
+		ec1->ec_source_indexes = bms_join(ec1->ec_source_indexes,
+										  ec2->ec_source_indexes);
+		ec1->ec_derive_indexes = bms_join(ec1->ec_derive_indexes,
+										  ec2->ec_derive_indexes);
 		ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
 		ec1->ec_has_const |= ec2->ec_has_const;
 		/* can't need to set has_volatile */
@@ -371,10 +378,9 @@ process_equivalence(PlannerInfo *root,
 		ec2->ec_members = NIL;
 		ec2->ec_norel_members = NIL;
 		ec2->ec_rel_members = NIL;
-		ec2->ec_sources = NIL;
-		ec2->ec_derives = NIL;
+		ec2->ec_source_indexes = NULL;
+		ec2->ec_derive_indexes = NULL;
 		ec2->ec_relids = NULL;
-		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 		ec1->ec_min_security = Min(ec1->ec_min_security,
 								   restrictinfo->security_level);
 		ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -385,13 +391,14 @@ process_equivalence(PlannerInfo *root,
 		/* mark the RI as usable with this pair of EMs */
 		restrictinfo->left_em = em1;
 		restrictinfo->right_em = em2;
+
+		add_eq_source(root, ec1, restrictinfo);
 	}
 	else if (ec1)
 	{
 		/* Case 3: add item2 to ec1 */
 		em2 = add_eq_member(ec1, item2, item2_relids,
 							jdomain, item2_type);
-		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 		ec1->ec_min_security = Min(ec1->ec_min_security,
 								   restrictinfo->security_level);
 		ec1->ec_max_security = Max(ec1->ec_max_security,
@@ -402,13 +409,14 @@ process_equivalence(PlannerInfo *root,
 		/* mark the RI as usable with this pair of EMs */
 		restrictinfo->left_em = em1;
 		restrictinfo->right_em = em2;
+
+		add_eq_source(root, ec1, restrictinfo);
 	}
 	else if (ec2)
 	{
 		/* Case 3: add item1 to ec2 */
 		em1 = add_eq_member(ec2, item1, item1_relids,
 							jdomain, item1_type);
-		ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
 		ec2->ec_min_security = Min(ec2->ec_min_security,
 								   restrictinfo->security_level);
 		ec2->ec_max_security = Max(ec2->ec_max_security,
@@ -419,6 +427,8 @@ process_equivalence(PlannerInfo *root,
 		/* mark the RI as usable with this pair of EMs */
 		restrictinfo->left_em = em1;
 		restrictinfo->right_em = em2;
+
+		add_eq_source(root, ec2, restrictinfo);
 	}
 	else
 	{
@@ -430,8 +440,8 @@ process_equivalence(PlannerInfo *root,
 		ec->ec_members = NIL;
 		ec->ec_norel_members = NIL;
 		ec->ec_rel_members = NIL;
-		ec->ec_sources = list_make1(restrictinfo);
-		ec->ec_derives = NIL;
+		ec->ec_source_indexes = NULL;
+		ec->ec_derive_indexes = NULL;
 		ec->ec_relids = NULL;
 		ec->ec_has_const = false;
 		ec->ec_has_volatile = false;
@@ -453,6 +463,8 @@ process_equivalence(PlannerInfo *root,
 		/* mark the RI as usable with this pair of EMs */
 		restrictinfo->left_em = em1;
 		restrictinfo->right_em = em2;
+
+		add_eq_source(root, ec, restrictinfo);
 	}
 
 	return true;
@@ -600,6 +612,50 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 	return em;
 }
 
+/*
+ * add_eq_source - add 'rinfo' in eq_sources for this 'ec'
+ */
+static void
+add_eq_source(PlannerInfo *root, EquivalenceClass *ec, RestrictInfo *rinfo)
+{
+	int			source_idx = list_length(root->eq_sources);
+	int			i;
+
+	ec->ec_source_indexes = bms_add_member(ec->ec_source_indexes, source_idx);
+	root->eq_sources = lappend(root->eq_sources, rinfo);
+
+	i = -1;
+	while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
+	{
+		RangeTblEntry *rte = root->simple_rte_array[i];
+
+		rte->eclass_source_indexes = bms_add_member(rte->eclass_source_indexes,
+													source_idx);
+	}
+}
+
+/*
+ * add_eq_derive - add 'rinfo' in eq_derives for this 'ec'
+ */
+static void
+add_eq_derive(PlannerInfo *root, EquivalenceClass *ec, RestrictInfo *rinfo)
+{
+	int			derive_idx = list_length(root->eq_derives);
+	int			i;
+
+	ec->ec_derive_indexes = bms_add_member(ec->ec_derive_indexes, derive_idx);
+	root->eq_derives = lappend(root->eq_derives, rinfo);
+
+	i = -1;
+	while ((i = bms_next_member(rinfo->clause_relids, i)) >= 0)
+	{
+		RangeTblEntry *rte = root->simple_rte_array[i];
+
+		rte->eclass_derive_indexes = bms_add_member(rte->eclass_derive_indexes,
+													derive_idx);
+	}
+}
+
 
 /*
  * get_eclass_for_sort_expr
@@ -756,8 +812,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	newec->ec_members = NIL;
 	newec->ec_norel_members = NIL;
 	newec->ec_rel_members = NIL;
-	newec->ec_sources = NIL;
-	newec->ec_derives = NIL;
+	newec->ec_source_indexes = NULL;
+	newec->ec_derive_indexes = NULL;
 	newec->ec_relids = NULL;
 	newec->ec_has_const = false;
 	newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
@@ -1145,7 +1201,7 @@ relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel,
  * scanning of the quals and before Path construction begins.
  *
  * We make no attempt to avoid generating duplicate RestrictInfos here: we
- * don't search ec_sources or ec_derives for matches.  It doesn't really
+ * don't search eq_sources or eq_derives for matches.  It doesn't really
  * seem worth the trouble to do so.
  */
 void
@@ -1234,6 +1290,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 {
 	EquivalenceMember *const_em = NULL;
 	ListCell   *lc;
+	int			i;
 
 	/*
 	 * In the trivial case where we just had one "var = const" clause, push
@@ -1243,9 +1300,9 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 	 * equivalent to the old one.
 	 */
 	if (list_length(ec->ec_members) == 2 &&
-		list_length(ec->ec_sources) == 1)
+		bms_get_singleton_member(ec->ec_source_indexes, &i))
 	{
-		RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
+		RestrictInfo *restrictinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
 
 		distribute_restrictinfo_to_rels(root, restrictinfo);
 		return;
@@ -1303,9 +1360,9 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 
 		/*
 		 * If the clause didn't degenerate to a constant, fill in the correct
-		 * markings for a mergejoinable clause, and save it in ec_derives. (We
+		 * markings for a mergejoinable clause, and save it in eq_derives. (We
 		 * will not re-use such clauses directly, but selectivity estimation
-		 * may consult the list later.  Note that this use of ec_derives does
+		 * may consult the list later.  Note that this use of eq_derives does
 		 * not overlap with its use for join clauses, since we never generate
 		 * join clauses from an ec_has_const eclass.)
 		 */
@@ -1315,7 +1372,8 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 			rinfo->left_ec = rinfo->right_ec = ec;
 			rinfo->left_em = cur_em;
 			rinfo->right_em = const_em;
-			ec->ec_derives = lappend(ec->ec_derives, rinfo);
+
+			add_eq_derive(root, ec, rinfo);
 		}
 	}
 }
@@ -1381,7 +1439,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 			/*
 			 * If the clause didn't degenerate to a constant, fill in the
 			 * correct markings for a mergejoinable clause.  We don't put it
-			 * in ec_derives however; we don't currently need to re-find such
+			 * in eq_derives however; we don't currently need to re-find such
 			 * clauses, and we don't want to clutter that list with non-join
 			 * clauses.
 			 */
@@ -1437,11 +1495,12 @@ static void
 generate_base_implied_equalities_broken(PlannerInfo *root,
 										EquivalenceClass *ec)
 {
-	ListCell   *lc;
+	int			i = -1;
 
-	foreach(lc, ec->ec_sources)
+	while ((i = bms_next_member(ec->ec_source_indexes, i)) >= 0)
 	{
-		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+		RestrictInfo *restrictinfo = list_nth_node(RestrictInfo,
+												   root->eq_sources, i);
 
 		if (ec->ec_has_const ||
 			bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
@@ -1482,11 +1541,11 @@ generate_base_implied_equalities_broken(PlannerInfo *root,
  * Because the same join clauses are likely to be needed multiple times as
  * we consider different join paths, we avoid generating multiple copies:
  * whenever we select a particular pair of EquivalenceMembers to join,
- * we check to see if the pair matches any original clause (in ec_sources)
- * or previously-built clause (in ec_derives).  This saves memory and allows
- * re-use of information cached in RestrictInfos.  We also avoid generating
- * commutative duplicates, i.e. if the algorithm selects "a.x = b.y" but
- * we already have "b.y = a.x", we return the existing clause.
+ * we check to see if the pair matches any original clause in root's
+ * eq_sources or previously-built clause (in root's eq_derives).  This saves
+ * memory and allows re-use of information cached in RestrictInfos.  We also
+ * avoid generating commutative duplicates, i.e. if the algorithm selects
+ * "a.x = b.y" but we already have "b.y = a.x", we return the existing clause.
  *
  * If we are considering an outer join, sjinfo is the associated OJ info,
  * otherwise it can be NULL.
@@ -1871,12 +1930,16 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
 										Relids nominal_inner_relids,
 										RelOptInfo *inner_rel)
 {
+	Bitmapset  *matching_es;
 	List	   *result = NIL;
-	ListCell   *lc;
+	int			i;
 
-	foreach(lc, ec->ec_sources)
+	matching_es = get_ec_source_indexes(root, ec, nominal_join_relids);
+	i = -1;
+	while ((i = bms_next_member(matching_es, i)) >= 0)
 	{
-		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+		RestrictInfo *restrictinfo = list_nth_node(RestrictInfo,
+												   root->eq_sources, i);
 		Relids		clause_relids = restrictinfo->required_relids;
 
 		if (bms_is_subset(clause_relids, nominal_join_relids) &&
@@ -1888,12 +1951,12 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
 	/*
 	 * If we have to translate, just brute-force apply adjust_appendrel_attrs
 	 * to all the RestrictInfos at once.  This will result in returning
-	 * RestrictInfos that are not listed in ec_derives, but there shouldn't be
+	 * RestrictInfos that are not listed in eq_derives, but there shouldn't be
 	 * any duplication, and it's a sufficiently narrow corner case that we
 	 * shouldn't sweat too much over it anyway.
 	 *
 	 * Since inner_rel might be an indirect descendant of the baserel
-	 * mentioned in the ec_sources clauses, we have to be prepared to apply
+	 * mentioned in the eq_sources clauses, we have to be prepared to apply
 	 * multiple levels of Var translation.
 	 */
 	if (IS_OTHER_REL(inner_rel) && result != NIL)
@@ -1955,10 +2018,11 @@ create_join_clause(PlannerInfo *root,
 				   EquivalenceMember *rightem,
 				   EquivalenceClass *parent_ec)
 {
+	Bitmapset  *matches;
 	RestrictInfo *rinfo;
 	RestrictInfo *parent_rinfo = NULL;
-	ListCell   *lc;
 	MemoryContext oldcontext;
+	int			i;
 
 	/*
 	 * Search to see if we already built a RestrictInfo for this pair of
@@ -1969,9 +2033,12 @@ create_join_clause(PlannerInfo *root,
 	 * it's not identical, it'd better have the same effects, or the operator
 	 * families we're using are broken.
 	 */
-	foreach(lc, ec->ec_sources)
+	matches = bms_int_members(get_ec_source_indexes_strict(root, ec, leftem->em_relids),
+							  get_ec_source_indexes_strict(root, ec, rightem->em_relids));
+	i = -1;
+	while ((i = bms_next_member(matches, i)) >= 0)
 	{
-		rinfo = (RestrictInfo *) lfirst(lc);
+		rinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
 		if (rinfo->left_em == leftem &&
 			rinfo->right_em == rightem &&
 			rinfo->parent_ec == parent_ec)
@@ -1982,9 +2049,13 @@ create_join_clause(PlannerInfo *root,
 			return rinfo;
 	}
 
-	foreach(lc, ec->ec_derives)
+	matches = bms_int_members(get_ec_derive_indexes_strict(root, ec, leftem->em_relids),
+							  get_ec_derive_indexes_strict(root, ec, rightem->em_relids));
+
+	i = -1;
+	while ((i = bms_next_member(matches, i)) >= 0)
 	{
-		rinfo = (RestrictInfo *) lfirst(lc);
+		rinfo = list_nth_node(RestrictInfo, root->eq_derives, i);
 		if (rinfo->left_em == leftem &&
 			rinfo->right_em == rightem &&
 			rinfo->parent_ec == parent_ec)
@@ -2042,7 +2113,7 @@ create_join_clause(PlannerInfo *root,
 	rinfo->left_em = leftem;
 	rinfo->right_em = rightem;
 	/* and save it for possible re-use */
-	ec->ec_derives = lappend(ec->ec_derives, rinfo);
+	add_eq_derive(root, ec, rinfo);
 
 	MemoryContextSwitchTo(oldcontext);
 
@@ -2721,16 +2792,19 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
  * Returns NULL if no such clause can be found.
  */
 RestrictInfo *
-find_derived_clause_for_ec_member(EquivalenceClass *ec,
+find_derived_clause_for_ec_member(PlannerInfo *root, EquivalenceClass *ec,
 								  EquivalenceMember *em)
 {
-	ListCell   *lc;
+	int			i;
 
 	Assert(ec->ec_has_const);
 	Assert(!em->em_is_const);
-	foreach(lc, ec->ec_derives)
+
+	i = -1;
+	while ((i = bms_next_member(ec->ec_derive_indexes, i)) >= 0)
 	{
-		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
+											i);
 
 		/*
 		 * generate_base_implied_equalities_const will have put non-const
@@ -3335,7 +3409,7 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
 		 * surely be true if both of them overlap ec_relids.)
 		 *
 		 * Note we don't test ec_broken; if we did, we'd need a separate code
-		 * path to look through ec_sources.  Checking the membership anyway is
+		 * path to look through eq_sources.  Checking the membership anyway is
 		 * OK as a possibly-overoptimistic heuristic.
 		 *
 		 * We don't test ec_has_const either, even though a const eclass won't
@@ -3423,7 +3497,7 @@ eclass_useful_for_merging(PlannerInfo *root,
 
 	/*
 	 * Note we don't test ec_broken; if we did, we'd need a separate code path
-	 * to look through ec_sources.  Checking the members anyway is OK as a
+	 * to look through eq_sources.  Checking the members anyway is OK as a
 	 * possibly-overoptimistic heuristic.
 	 */
 
@@ -3576,3 +3650,179 @@ 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);
 }
+
+/*
+ * get_ec_source_indexes
+ *		Returns a Bitmapset with indexes into root->eq_sources for all
+ *		RestrictInfos in 'ec' that have
+ *		bms_overlap(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+{
+	Bitmapset  *rel_esis = NULL;
+	int			i = -1;
+
+	while ((i = bms_next_member(relids, i)) >= 0)
+	{
+		RangeTblEntry *rte = root->simple_rte_array[i];
+
+		rel_esis = bms_add_members(rel_esis, rte->eclass_source_indexes);
+	}
+
+#ifdef USE_ASSERT_CHECKING
+	/* verify the results look sane */
+	i = -1;
+	while ((i = bms_next_member(rel_esis, i)) >= 0)
+	{
+		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
+											i);
+
+		Assert(bms_overlap(relids, rinfo->clause_relids));
+	}
+#endif
+
+	/* bitwise-AND to leave only the ones for this EquivalenceClass */
+	return bms_int_members(rel_esis, ec->ec_source_indexes);
+}
+
+/*
+ * get_ec_source_indexes_strict
+ *		Returns a Bitmapset with indexes into root->eq_sources for all
+ *		RestrictInfos in 'ec' that have
+ *		bms_is_subset(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
+							 Relids relids)
+{
+	Bitmapset  *esis = NULL;
+	int			i = bms_next_member(relids, -1);
+
+	if (i >= 0)
+	{
+		RangeTblEntry *rte = root->simple_rte_array[i];
+
+		/*
+		 * bms_intersect to the first relation to try to keep the resulting
+		 * Bitmapset as small as possible.  This saves having to make a
+		 * complete bms_copy() of one of them.  One may contain significantly
+		 * more words than the other.
+		 */
+		esis = bms_intersect(ec->ec_source_indexes,
+							 rte->eclass_source_indexes);
+
+		while ((i = bms_next_member(relids, i)) >= 0)
+		{
+			rte = root->simple_rte_array[i];
+			esis = bms_int_members(esis, rte->eclass_source_indexes);
+		}
+	}
+
+#ifdef USE_ASSERT_CHECKING
+	/* verify the results look sane */
+	i = -1;
+	while ((i = bms_next_member(esis, i)) >= 0)
+	{
+		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
+											i);
+
+		Assert(bms_is_subset(relids, rinfo->clause_relids));
+	}
+#endif
+
+	return esis;
+}
+
+/*
+ * get_ec_derive_indexes
+ *		Returns a Bitmapset with indexes into root->eq_derives for all
+ *		RestrictInfos in 'ec' that have
+ *		bms_overlap(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ *
+ * XXX is this function even needed?
+ */
+Bitmapset *
+get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+{
+	Bitmapset  *rel_edis = NULL;
+	int			i = -1;
+
+	while ((i = bms_next_member(relids, i)) >= 0)
+	{
+		RangeTblEntry *rte = root->simple_rte_array[i];
+
+		rel_edis = bms_add_members(rel_edis, rte->eclass_derive_indexes);
+	}
+
+#ifdef USE_ASSERT_CHECKING
+	/* verify the results look sane */
+	i = -1;
+	while ((i = bms_next_member(rel_edis, i)) >= 0)
+	{
+		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
+											i);
+
+		Assert(bms_overlap(relids, rinfo->clause_relids));
+	}
+#endif
+
+	/* bitwise-AND to leave only the ones for this EquivalenceClass */
+	return bms_int_members(rel_edis, ec->ec_derive_indexes);
+}
+
+/*
+ * get_ec_derive_indexes_strict
+ *		Returns a Bitmapset with indexes into root->eq_derives for all
+ *		RestrictInfos in 'ec' that have
+ *		bms_is_subset(relids, rinfo->clause_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
+							 Relids relids)
+{
+	Bitmapset  *edis = NULL;
+	int			i = bms_next_member(relids, -1);
+
+	if (i >= 0)
+	{
+		RangeTblEntry *rte = root->simple_rte_array[i];
+
+		/*
+		 * bms_intersect to the first relation to try to keep the resulting
+		 * Bitmapset as small as possible.  This saves having to make a
+		 * complete bms_copy() of one of them.  One may contain significantly
+		 * more words than the other.
+		 */
+		edis = bms_intersect(ec->ec_derive_indexes,
+							 rte->eclass_derive_indexes);
+
+		while ((i = bms_next_member(relids, i)) >= 0)
+		{
+			rte = root->simple_rte_array[i];
+			edis = bms_int_members(edis, rte->eclass_derive_indexes);
+		}
+	}
+
+#ifdef USE_ASSERT_CHECKING
+	/* verify the results look sane */
+	i = -1;
+	while ((i = bms_next_member(edis, i)) >= 0)
+	{
+		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
+											i);
+
+		Assert(bms_is_subset(relids, rinfo->clause_relids));
+	}
+#endif
+
+	return edis;
+}
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index f0735f3c41..38328d945a 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -669,6 +669,7 @@ remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec, int relid,
 					   int ojrelid)
 {
 	ListCell   *lc;
+	int			i;
 
 	/* Fix up the EC's overall relids */
 	ec->ec_relids = bms_del_member(ec->ec_relids, relid);
@@ -702,9 +703,10 @@ remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec, int relid,
 	}
 
 	/* Fix up the source clauses, in case we can re-use them later */
-	foreach(lc, ec->ec_sources)
+	i = -1;
+	while ((i = bms_next_member(ec->ec_source_indexes, i)) >= 0)
 	{
-		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
 
 		remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
 	}
@@ -714,7 +716,7 @@ remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec, int relid,
 	 * drop them.  (At this point, any such clauses would be base restriction
 	 * clauses, which we'd not need anymore anyway.)
 	 */
-	ec->ec_derives = NIL;
+	ec->ec_derive_indexes = NULL;
 }
 
 /*
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 667723b675..9420259e4b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -646,6 +646,8 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root->multiexpr_params = NIL;
 	root->join_domains = NIL;
 	root->eq_classes = NIL;
+	root->eq_sources = NIL;
+	root->eq_derives = NIL;
 	root->ec_merging_done = false;
 	root->last_rinfo_serial = 0;
 	root->all_result_relids =
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index aa83dd3636..9fc0b69580 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -993,6 +993,8 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->multiexpr_params = NIL;
 	subroot->join_domains = NIL;
 	subroot->eq_classes = NIL;
+	subroot->eq_sources = NIL;
+	subroot->eq_derives = NIL;
 	subroot->ec_merging_done = false;
 	subroot->last_rinfo_serial = 0;
 	subroot->all_result_relids = NULL;
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index 3501fbbeed..a65a76ace9 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -483,6 +483,13 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
 	 */
 	childrte = makeNode(RangeTblEntry);
 	memcpy(childrte, parentrte, sizeof(RangeTblEntry));
+	/*
+	 * We do not want to inherit the EquivalenceMember indexes of the parent
+	 * to its child
+	 */
+	childrte->eclass_source_indexes = NULL;
+	childrte->eclass_derive_indexes = NULL;
+
 	Assert(parentrte->rtekind == RTE_RELATION); /* else this is dubious */
 	childrte->relid = childOID;
 	childrte->relkind = childrel->rd_rel->relkind;
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index b3181f34ae..d365bb5c72 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -1194,6 +1194,12 @@ typedef struct RangeTblEntry
 	bool		inh;			/* inheritance requested? */
 	bool		inFromCl;		/* present in FROM clause? */
 	List	   *securityQuals;	/* security barrier quals to apply, if any */
+	Bitmapset  *eclass_source_indexes;	/* Indexes in PlannerInfo's eq_sources
+										 * list for RestrictInfos that mention
+										 * this relation */
+	Bitmapset  *eclass_derive_indexes;	/* Indexes in PlannerInfo's eq_derives
+										 * list for RestrictInfos that mention
+										 * this relation */
 } RangeTblEntry;
 
 /*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 8c55a2bcf0..1c5d7bc0c1 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -318,6 +318,12 @@ struct PlannerInfo
 	/* list of active EquivalenceClasses */
 	List	   *eq_classes;
 
+	/* list of source RestrictInfos used to build EquivalenceClasses */
+	List	   *eq_sources;
+
+	/* list of RestrictInfos derived from EquivalenceClasses */
+	List	   *eq_derives;
+
 	/* set true once ECs are canonical */
 	bool		ec_merging_done;
 
@@ -1369,6 +1375,41 @@ typedef struct JoinDomain
  * entry: consider SELECT random() AS a, random() AS b ... ORDER BY b,a.
  * So we record the SortGroupRef of the originating sort clause.
  *
+ * TODO: We should update the following comments.
+ *
+ * At various locations in the query planner, we must search for
+ * EquivalenceMembers within a given EquivalenceClass.  For the common case,
+ * an EquivalenceClass does not have a large number of EquivalenceMembers,
+ * however, in cases such as planning queries to partitioned tables, the number
+ * of members can become large.  To maintain planning performance, we make use
+ * of a bitmap index to allow us to quickly find EquivalenceMembers in a given
+ * EquivalenceClass belonging to a given relation or set of relations.  This
+ * is done by storing a list of EquivalenceMembers belonging to all
+ * EquivalenceClasses in PlannerInfo and storing a Bitmapset for each
+ * RelOptInfo which has a bit set for each EquivalenceMember in that list
+ * which relates to the given relation.  We also store a Bitmapset to mark all
+ * of the indexes in the PlannerInfo's list of EquivalenceMembers in the
+ * EquivalenceClass.  We can quickly find the interesting indexes into the
+ * PlannerInfo's list by performing a bit-wise AND on the RelOptInfo's
+ * Bitmapset and the EquivalenceClasses.
+ *
+ * To further speed up the lookup of EquivalenceMembers we also record the
+ * non-child indexes.  This allows us to deal with fewer bits for searches
+ * that don't require "is_child" EquivalenceMembers.  We must also store the
+ * indexes into EquivalenceMembers which have no relids mentioned as some
+ * searches require that.
+ *
+ * Additionally, we also store the EquivalenceMembers of a given
+ * EquivalenceClass in the ec_members list.  Technically, we could obtain this
+ * from looking at the bits in ec_member_indexes, however, finding all members
+ * of a given EquivalenceClass is common enough that it pays to have fast
+ * access to a dense list containing all members.
+ *
+ * The source and derived RestrictInfos are indexed in a similar method,
+ * although we don't maintain a List in the EquivalenceClass for these.  These
+ * must be looked up in PlannerInfo using the ec_source_indexes and
+ * ec_derive_indexes Bitmapsets.
+ *
  * NB: if ec_merged isn't NULL, this class has been merged into another, and
  * should be ignored in favor of using the pointed-to class.
  *
@@ -1391,8 +1432,10 @@ typedef struct EquivalenceClass
 									 * em_relids is empty */
 	List	   *ec_rel_members;	/* list of EquivalenceMembers whose
 								 * em_relids is not empty */
-	List	   *ec_sources;		/* list of generating RestrictInfos */
-	List	   *ec_derives;		/* list of derived RestrictInfos */
+	Bitmapset  *ec_source_indexes;	/* indexes into PlannerInfo's eq_sources
+									 * list of generating RestrictInfos */
+	Bitmapset  *ec_derive_indexes;	/* indexes into PlannerInfo's eq_derives
+									 * list of derived RestrictInfos */
 	Relids		ec_relids;		/* all relids appearing in ec_members, except
 								 * for child members (see below) */
 	bool		ec_has_const;	/* any pseudoconstants in ec_members? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9bc0c36b93..d071f6d0fc 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -163,7 +163,8 @@ extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
 extern EquivalenceClass *match_eclasses_to_foreign_key_col(PlannerInfo *root,
 														   ForeignKeyOptInfo *fkinfo,
 														   int colno);
-extern RestrictInfo *find_derived_clause_for_ec_member(EquivalenceClass *ec,
+extern RestrictInfo *find_derived_clause_for_ec_member(PlannerInfo *root,
+													   EquivalenceClass *ec,
 													   EquivalenceMember *em);
 extern void add_child_rel_equivalences(PlannerInfo *root,
 									   AppendRelInfo *appinfo,
@@ -195,6 +196,18 @@ extern bool eclass_useful_for_merging(PlannerInfo *root,
 extern bool is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist);
 extern bool is_redundant_with_indexclauses(RestrictInfo *rinfo,
 										   List *indexclauses);
+extern Bitmapset *get_ec_source_indexes(PlannerInfo *root,
+										EquivalenceClass *ec,
+										Relids relids);
+extern Bitmapset *get_ec_source_indexes_strict(PlannerInfo *root,
+											   EquivalenceClass *ec,
+											   Relids relids);
+extern Bitmapset *get_ec_derive_indexes(PlannerInfo *root,
+										EquivalenceClass *ec,
+										Relids relids);
+extern Bitmapset *get_ec_derive_indexes_strict(PlannerInfo *root,
+											   EquivalenceClass *ec,
+											   Relids relids);
 
 /*
  * pathkeys.c
-- 
2.42.0.windows.2