Subject: Re: [PoC] Reducing planning time when tables have many partitions

From: David Rowley <[email-masked]>
Date: Tue, 31 Jan 2023 01:14:28 +1300

isOn Mon, 30 Jan 2023 at 23:03, Yuya Watari <[email-masked]> wrote:
> 1. v13-0005
>
> The first bug is in eclass_member_iterator_strict_next(). As I
> mentioned in the commit message, the original code incorrectly missed
> EquivalenceMembers with empty em_relids when 'with_norel_members' is
> true.

Yeah, I was also looking at this today and found the same issues after
adding the verification code that checks we get the same members from
the index and via the looking method. I ended up making some changes
slightly different from what you had but wasn't quite ready to post
them yet.

I'm still a little unhappy with master's comments for the
EquivalenceMember.em_relids field. It claims to be the relids for the
em_expr, but that's not the case for em_is_child members. I've ended
up adding an additional field named em_norel_expr that gets set to
true when em_expr truly contains no Vars.  I then adjusted the
conditions in the iterator's loops to properly include members with no
Vars when we ask for those.

> 2. v13-0006
>
> The second bug exists in get_ecmember_indexes_strict(). As I described
> in the comment, if the empty relids is given, this function must
> return all members because their em_relids are always superset. I am
> concerned that this change may adversely affect performance.
> Currently, I have not seen any degradation.

I fixed this by adding a new field to the iterator struct named
relids_empty. It's just set to bms_is_empty(iter->with_relids).  The
loop condition then just becomes:

if (iter->relids_empty ||
    !bms_is_subset(iter->with_relids, em->em_relids))
    continue;

> 3. v13-0007
>
> The last one is in add_eq_member(). I am not sure why this change is
> working, but it is probably related to the concerns David mentioned in
> the previous mail. The v13-0007 may be wrong, so it should be
> reconsidered.

Unfortunately, we can't fix it that way.  At a glance, what you have
would only find var-less child members if you requested that the
iterator also gave you with_norel_members==true. I've not looked,
perhaps all current code locations request with_norel_members, so your
change likely just words by accident.

I've attached what I worked on today. I still want to do more
cross-checking to make sure all code locations which use these new
iterators get the same members as they used to get.

In the attached I also changed the code that added a RelOptInfo to
root->simple_rel_array[0] to allow the varno=0 Vars made in
generate_append_tlist() to be indexed. That's now done via a new
function (setup_append_rel_entry()) which is only called during
plan_set_operations().  This means we're no longer wastefully creating
that entry during the planning of normal queries. We could maybe
consider giving this a more valid varno and expand simple_rel_array to
make more room, but I'm not sure it's worth it or not. I'm happier
that this simple_rel_array[0] entry now only exists when planning set
operations, but I'd probably feel better if there was some other way
that felt less like we're faking up a RelOptInfo to store
EquivalenceMembers in.

I've also included a slightly edited version of your code which checks
that the members match when using and not using the new indexes. All
the cross-checking seems to pass.

David
From 177d013928d2bb5c0c4ee565a433bbf62481b18c Mon Sep 17 00:00:00 2001
From: David Rowley <[email-masked]>
Date: Thu, 1 Dec 2022 20:36:10 +1300
Subject: [PATCH v15 1/2] Adjust bms_int_members so that it shortens the left
 input

Prior to this change, if the left input to bms_int_members had fewer
Bitmapwords than the right input, the additional words in the left input
would be zeroed.  Doing things this why only really makes sense if we
expect to add additional words to the resulting bitmap set again later.
Seemingly, most of our use cases don't add to the resulting Bitmapset,
in fact, many cases are performing bms_int_members in a loop which is
likely to even further increase the amount of all zero words in the set.

Leaving these zero trailing words in place can cause inefficiencies in
functions such as bms_is_empty and loops which loop over a set using
bms_next_member when the set is left with a large number of trailing
words.

If there are use cases which need to add additional words again, then,
repalloc has to do very little processing when the requested allocation
size is <= the actual allocation size.  Both AllocSetRealloc and
GenerationRealloc simply just return the input pointer again.  If there
are any cases where we do increase the size of the set again, then this
just shifts the zeroing of the additional words until then.

We could give bms_del_members() and bms_difference similar treatment, but
that would require additional code to record the last non-zero word after
masking out the members being deleted.  That seems less worthwhile as it
will add cost when we're unable to trim down the number of words.
---
 src/backend/nodes/bitmapset.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 98660524ad..b13b4c378f 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -920,8 +920,16 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
 	shortlen = Min(a->nwords, b->nwords);
 	for (i = 0; i < shortlen; i++)
 		a->words[i] &= b->words[i];
-	for (; i < a->nwords; i++)
-		a->words[i] = 0;
+
+	/*
+	 * We simply shorten the left input to both remove the need to zero the
+	 * trailing words and also to reduce the required processing if this
+	 * function is being called in a loop.  If more words are required later
+	 * then AllocSetRealloc is likely not going to have to work very hard if
+	 * the new requested size is >= the actual size of the allocation.
+	 */
+	a->nwords = shortlen;
+
 	return a;
 }
 
-- 
2.39.0.windows.1

From ba89effb12c3547bf843bd0e991b454388cfb88e Mon Sep 17 00:00:00 2001
From: David Rowley <[email-masked]>
Date: Sun, 4 Dec 2022 11:09:21 +1300
Subject: [PATCH v15 2/2] Add Bitmapset indexes for faster lookup of
 EquivalenceMembers

For queries containing a large number of joins or for queries to
partitioned tables, the looking up of EquivalenceMembers in an
EquivalenceClass can become slow due to the large number of members.
Until now, the searching for EquivalenceMembers has been done using a
linear search over the EquivalenceClass's list of members. Here we
effectively add an index to allow faster lookups of these members.  This
is done by way of adding all members to all classes into a List in
PlannerInfo, then we have a Bitmapset in each EquivalenceClass with
members for each index in PlannerInfo's list which belong to this class.
Additionally, each RelOptInfo also maintains another Bitmapset which
stores each index in PlannerInfo's list of EquivalenceMember for all
members, in all classes, which mention this relation.  This allows us to
quickly find all EquivalenceMembers for a given RelOptInfo and a given
EquivalenceClass by intersecting these two lists.

When searching for members belonging to join rels, we must either
intersect or union all base RelOptInfo's member indexes then intersect the
result to the EquivalenceClass's indexes.  Whether we intersect or union
depends on if we need members that mention all relations or members that
mention any of the base relations making up the join relation.

This method of indexing can significantly speed up the planner when
querying a partitioned table with a large number of partitions when the
query contains a few joins.  Tests have shown around a x10 increase in
performance with 1000 partitions.
---
 contrib/postgres_fdw/postgres_fdw.c       |   50 +-
 src/backend/nodes/list.c                  |   16 +
 src/backend/nodes/outfuncs.c              |    7 +-
 src/backend/optimizer/path/costsize.c     |    3 +-
 src/backend/optimizer/path/equivclass.c   | 1295 +++++++++++++++++----
 src/backend/optimizer/path/indxpath.c     |   22 +-
 src/backend/optimizer/path/pathkeys.c     |   26 +-
 src/backend/optimizer/plan/createplan.c   |   66 +-
 src/backend/optimizer/plan/planagg.c      |    1 +
 src/backend/optimizer/plan/planner.c      |    3 +
 src/backend/optimizer/prep/prepjointree.c |    3 +
 src/backend/optimizer/prep/prepunion.c    |   25 +-
 src/backend/optimizer/util/relnode.c      |    9 +
 src/include/nodes/pathnodes.h             |   81 +-
 src/include/nodes/pg_list.h               |    1 +
 src/include/optimizer/paths.h             |   67 +-
 src/tools/pgindent/typedefs.list          |    1 +
 17 files changed, 1347 insertions(+), 329 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index 50d23f922c..b85c4a071e 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7619,6 +7619,10 @@ conversion_error_callback(void *arg)
 				varno = var->varno;
 				colno = var->varattno;
 			}
+			/*
+			 * XXX why don't we break here? Surely there can't be another
+			 * equal EquivalenceMember?
+			 */
 		}
 
 		if (varno > 0)
@@ -7677,23 +7681,27 @@ conversion_error_callback(void *arg)
 EquivalenceMember *
 find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 {
-	ListCell   *lc;
+	EquivalenceMemberIterator iter;
+	EquivalenceMember *em;
 
-	foreach(lc, ec->ec_members)
-	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+	setup_eclass_member_iterator(&iter, root, ec, rel->relids, true, false);
 
+	while ((em = eclass_member_iterator_next(&iter)) != NULL)
+	{
 		/*
 		 * Note we require !bms_is_empty, else we'd accept constant
 		 * expressions which are not suitable for the purpose.
 		 */
+		Assert(!bms_is_empty(em->em_relids));
+
 		if (bms_is_subset(em->em_relids, rel->relids) &&
-			!bms_is_empty(em->em_relids) &&
 			is_foreign_expr(root, rel, em->em_expr))
-			return em;
+			break;
 	}
 
-	return NULL;
+	eclass_member_iterator_dispose(&iter);
+
+	return em;
 }
 
 /*
@@ -7720,7 +7728,9 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 	{
 		Expr	   *expr = (Expr *) lfirst(lc1);
 		Index		sgref = get_pathtarget_sortgroupref(target, i);
-		ListCell   *lc2;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *em;
+		Relids		expr_relids;
 
 		/* Ignore non-sort expressions */
 		if (sgref == 0 ||
@@ -7735,19 +7745,20 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 		while (expr && IsA(expr, RelabelType))
 			expr = ((RelabelType *) expr)->arg;
 
+		expr_relids = pull_varnos(root, (Node *) expr);
+		setup_eclass_member_strict_iterator(&iter, root, ec, expr_relids,
+											false, false);
+
 		/* Locate an EquivalenceClass member matching this expr, if any */
-		foreach(lc2, ec->ec_members)
+		while ((em = eclass_member_iterator_strict_next(&iter)) != NULL)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
 			Expr	   *em_expr;
 
-			/* Don't match constants */
-			if (em->em_is_const)
-				continue;
+			/* don't expect constants */
+			Assert(!em->em_is_const);
 
-			/* Ignore child members */
-			if (em->em_is_child)
-				continue;
+			/* don't expect child members */
+			Assert(!em->em_is_child);
 
 			/* Match if same expression (after stripping relabel) */
 			em_expr = em->em_expr;
@@ -7759,10 +7770,15 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 
 			/* Check that expression (including relabels!) is shippable */
 			if (is_foreign_expr(root, rel, em->em_expr))
+			{
+				bms_free(expr_relids);
+				eclass_member_iterator_dispose(&iter);
 				return em;
+			}
 		}
-
 		i++;
+		bms_free(expr_relids);
+		eclass_member_iterator_dispose(&iter);
 	}
 
 	return NULL;
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index a709d23ef1..b8972bbe5a 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -1683,6 +1683,22 @@ list_sort(List *list, list_sort_comparator cmp)
 		qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
 }
 
+/*
+ * list_sort comparator for sorting a list into ascending ptr order.
+ */
+int
+list_ptr_cmp(const ListCell *p1, const ListCell *p2)
+{
+	void	   *v1 = lfirst(p1);
+	void	   *v2 = lfirst(p2);
+
+	if (v1 < v2)
+		return -1;
+	if (v1 > v2)
+		return 1;
+	return 0;
+}
+
 /*
  * list_sort comparator for sorting a list into ascending int order.
  */
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 6b368b08b2..98becac509 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -463,8 +463,11 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
 	WRITE_NODE_FIELD(ec_opfamilies);
 	WRITE_OID_FIELD(ec_collation);
 	WRITE_NODE_FIELD(ec_members);
-	WRITE_NODE_FIELD(ec_sources);
-	WRITE_NODE_FIELD(ec_derives);
+	WRITE_BITMAPSET_FIELD(ec_member_indexes);
+	WRITE_BITMAPSET_FIELD(ec_nonchild_indexes);
+	WRITE_BITMAPSET_FIELD(ec_norel_indexes);
+	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);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 29ae32d960..595aaf74f3 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -5501,7 +5501,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 7d7e6facdf..4277548193 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -31,9 +31,14 @@
 #include "optimizer/restrictinfo.h"
 #include "utils/lsyscache.h"
 
-
-static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
-										Expr *expr, Relids relids, Relids nullable_relids,
+static void add_eq_source(PlannerInfo *root, EquivalenceClass *ec,
+						  RestrictInfo *rinfo);
+static void add_eq_derive(PlannerInfo *root, EquivalenceClass *ec,
+						  RestrictInfo *rinfo);
+static EquivalenceMember *add_eq_member(PlannerInfo *root,
+										EquivalenceClass *ec,
+										Expr *expr, Relids relids,
+										Relids nullable_relids,
 										bool is_child, Oid datatype);
 static bool is_exprlist_member(Expr *node, List *exprs);
 static void generate_base_implied_equalities_const(PlannerInfo *root,
@@ -333,7 +338,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_below_outer_join |= below_outer_join;
 			ec1->ec_min_security = Min(ec1->ec_min_security,
 									   restrictinfo->security_level);
@@ -345,6 +349,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;
 		}
 
@@ -365,8 +371,16 @@ process_equivalence(PlannerInfo *root,
 		 * be found.
 		 */
 		ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_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_member_indexes = bms_add_members(ec1->ec_member_indexes,
+												 ec2->ec_member_indexes);
+		ec1->ec_nonchild_indexes = bms_add_members(ec1->ec_nonchild_indexes,
+												   ec2->ec_nonchild_indexes);
+		ec1->ec_norel_indexes = bms_add_members(ec1->ec_norel_indexes,
+												ec2->ec_norel_indexes);
+		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 */
@@ -379,10 +393,12 @@ process_equivalence(PlannerInfo *root,
 		root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
 		/* just to avoid debugging confusion w/ dangling pointers: */
 		ec2->ec_members = NIL;
-		ec2->ec_sources = NIL;
-		ec2->ec_derives = NIL;
+		ec2->ec_member_indexes = NULL;
+		ec2->ec_nonchild_indexes = NULL;
+		ec2->ec_norel_indexes = NULL;
+		ec2->ec_source_indexes = NULL;
+		ec2->ec_derive_indexes = NULL;
 		ec2->ec_relids = NULL;
-		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,
 								   restrictinfo->security_level);
@@ -394,13 +410,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, item2_nullable_relids,
-							false, item2_type);
-		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
+		em2 = add_eq_member(root, ec1, item2, item2_relids,
+							item2_nullable_relids, false, item2_type);
 		ec1->ec_below_outer_join |= below_outer_join;
 		ec1->ec_min_security = Min(ec1->ec_min_security,
 								   restrictinfo->security_level);
@@ -412,13 +429,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, item1_nullable_relids,
-							false, item1_type);
-		ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
+		em1 = add_eq_member(root, ec2, item1, item1_relids,
+							item1_nullable_relids, false, item1_type);
 		ec2->ec_below_outer_join |= below_outer_join;
 		ec2->ec_min_security = Min(ec2->ec_min_security,
 								   restrictinfo->security_level);
@@ -430,6 +448,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
 	{
@@ -439,8 +459,11 @@ process_equivalence(PlannerInfo *root,
 		ec->ec_opfamilies = opfamilies;
 		ec->ec_collation = collation;
 		ec->ec_members = NIL;
-		ec->ec_sources = list_make1(restrictinfo);
-		ec->ec_derives = NIL;
+		ec->ec_member_indexes = NULL;
+		ec->ec_nonchild_indexes = NULL;
+		ec->ec_norel_indexes = NULL;
+		ec->ec_source_indexes = NULL;
+		ec->ec_derive_indexes = NULL;
 		ec->ec_relids = NULL;
 		ec->ec_has_const = false;
 		ec->ec_has_volatile = false;
@@ -450,10 +473,10 @@ 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, item1, item1_relids,
+							item1_nullable_relids, false, item1_type);
+		em2 = add_eq_member(root, ec, item2, item2_relids,
+							item2_nullable_relids, false, item2_type);
 
 		root->eq_classes = lappend(root->eq_classes, ec);
 
@@ -463,6 +486,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;
@@ -538,14 +563,62 @@ canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
 	return expr;
 }
 
+/*
+ * 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)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		rel->eclass_source_indexes = bms_add_member(rel->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)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		rel->eclass_derive_indexes = bms_add_member(rel->eclass_derive_indexes,
+													derive_idx);
+	}
+}
+
 /*
  * add_eq_member - build a new EquivalenceMember and add it to an EC
  */
 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, Expr *expr,
+			  Relids relids, Relids nullable_relids, bool is_child,
+			  Oid datatype)
 {
 	EquivalenceMember *em = makeNode(EquivalenceMember);
+	Relids		expr_relids;
+	int			em_index = list_length(root->eq_members);
+	int			i;
 
 	em->em_expr = expr;
 	em->em_relids = relids;
@@ -554,6 +627,23 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 	em->em_is_child = is_child;
 	em->em_datatype = datatype;
 
+	/*
+	 * We must determine the exact set of relids in the expr for child
+	 * EquivalenceMembers as what is given to us in 'relids' may differ from
+	 * the relids mentioned in the expression.  See add_child_rel_equivalences
+	 */
+	if (is_child)
+		expr_relids = pull_varnos(root, (Node *) expr);
+	else
+	{
+		expr_relids = relids;
+		/* We expect the relids to match for non-child members */
+		Assert(bms_equal(pull_varnos(root, (Node *) expr), relids));
+	}
+
+	/* record the actual relids from 'expr' */
+	em->em_norel_expr = bms_is_empty(expr_relids);
+
 	if (bms_is_empty(relids))
 	{
 		/*
@@ -572,9 +662,31 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 	else if (!is_child)			/* child members don't add to ec_relids */
 	{
 		ec->ec_relids = bms_add_members(ec->ec_relids, relids);
+		ec->ec_nonchild_indexes = bms_add_member(ec->ec_nonchild_indexes, em_index);
 	}
+
+	/* add the new member to the list */
 	ec->ec_members = lappend(ec->ec_members, em);
 
+	/* and add it to the index and PlannerInfo's list */
+	ec->ec_member_indexes = bms_add_member(ec->ec_member_indexes, em_index);
+	root->eq_members = lappend(root->eq_members, em);
+
+	/* record exprs with no relids */
+	if (bms_is_empty(expr_relids))
+		ec->ec_norel_indexes = bms_add_member(ec->ec_norel_indexes, em_index);
+
+	if (is_child)
+		expr_relids = bms_add_members(expr_relids, relids);
+
+	i = -1;
+	while ((i = bms_next_member(expr_relids, i)) >= 0)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		rel->eclass_member_indexes = bms_add_member(rel->eclass_member_indexes, em_index);
+	}
+
 	return em;
 }
 
@@ -638,6 +750,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	 * Ensure the expression exposes the correct type and collation.
 	 */
 	expr = canonicalize_ec_expression(expr, opcintype, collation);
+	expr_relids = pull_varnos(root, (Node *) expr);
 
 	/*
 	 * Scan through the existing EquivalenceClasses for a match
@@ -645,7 +758,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		ListCell   *lc2;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *cur_em;
 
 		/*
 		 * Never match to a volatile EC, except when we are looking at another
@@ -660,10 +774,11 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
 			continue;
 
-		foreach(lc2, cur_ec->ec_members)
-		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+		setup_eclass_member_strict_iterator(&iter, root, cur_ec, expr_relids,
+											true, true);
 
+		while ((cur_em = eclass_member_iterator_strict_next(&iter)) != NULL)
+		{
 			/*
 			 * Ignore child members unless they match the request.
 			 */
@@ -683,6 +798,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 				equal(expr, cur_em->em_expr))
 				return cur_ec;	/* Match! */
 		}
+
+		eclass_member_iterator_dispose(&iter);
 	}
 
 	/* No match; does caller want a NULL result? */
@@ -700,8 +817,11 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	newec->ec_opfamilies = list_copy(opfamilies);
 	newec->ec_collation = collation;
 	newec->ec_members = NIL;
-	newec->ec_sources = NIL;
-	newec->ec_derives = NIL;
+	newec->ec_member_indexes = NULL;
+	newec->ec_nonchild_indexes = NULL;
+	newec->ec_norel_indexes = NULL;
+	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);
@@ -718,10 +838,9 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	/*
 	 * Get the precise set of nullable relids appearing in the expression.
 	 */
-	expr_relids = pull_varnos(root, (Node *) expr);
 	nullable_relids = bms_intersect(nullable_relids, expr_relids);
 
-	newem = add_eq_member(newec, copyObject(expr), expr_relids,
+	newem = add_eq_member(root, newec, copyObject(expr), expr_relids,
 						  nullable_relids, false, opcintype);
 
 	/*
@@ -753,7 +872,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		int			ec_index = list_length(root->eq_classes) - 1;
 		int			i = -1;
 
-		while ((i = bms_next_member(newec->ec_relids, i)) > 0)
+		while ((i = bms_next_member(newec->ec_relids, i)) >= 0)
 		{
 			RelOptInfo *rel = root->simple_rel_array[i];
 
@@ -783,19 +902,25 @@ get_eclass_for_sort_expr(PlannerInfo *root,
  * Child EC members are ignored unless they belong to given 'relids'.
  */
 EquivalenceMember *
-find_ec_member_matching_expr(EquivalenceClass *ec,
+find_ec_member_matching_expr(PlannerInfo *root,
+							 EquivalenceClass *ec,
 							 Expr *expr,
 							 Relids relids)
 {
-	ListCell   *lc;
+	EquivalenceMemberIterator iter;
+	Relids		expr_relids;
+	EquivalenceMember *em;
 
 	/* We ignore binary-compatible relabeling on both ends */
 	while (expr && IsA(expr, RelabelType))
 		expr = ((RelabelType *) expr)->arg;
 
-	foreach(lc, ec->ec_members)
+	expr_relids = pull_varnos(root, (Node *) expr);
+	setup_eclass_member_strict_iterator(&iter, root, ec, expr_relids, true,
+										true);
+
+	while ((em = eclass_member_iterator_strict_next(&iter)) != NULL)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
 		Expr	   *emexpr;
 
 		/*
@@ -820,10 +945,13 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
 			emexpr = ((RelabelType *) emexpr)->arg;
 
 		if (equal(emexpr, expr))
-			return em;
+			break;
 	}
 
-	return NULL;
+	bms_free(expr_relids);
+	eclass_member_iterator_dispose(&iter);
+
+	return em;
 }
 
 /*
@@ -965,7 +1093,7 @@ relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel,
 	{
 		Expr	   *targetexpr = (Expr *) lfirst(lc);
 
-		em = find_ec_member_matching_expr(ec, targetexpr, rel->relids);
+		em = find_ec_member_matching_expr(root, ec, targetexpr, rel->relids);
 		if (!em)
 			continue;
 
@@ -1052,7 +1180,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
@@ -1109,7 +1237,7 @@ generate_base_implied_equalities(PlannerInfo *root)
 		 * this is a cheap version of has_relevant_eclass_joinclause().
 		 */
 		i = -1;
-		while ((i = bms_next_member(ec->ec_relids, i)) > 0)
+		while ((i = bms_next_member(ec->ec_relids, i)) >= 0)
 		{
 			RelOptInfo *rel = root->simple_rel_array[i];
 
@@ -1135,6 +1263,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
@@ -1144,9 +1273,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);
 
 		if (bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
 		{
@@ -1161,9 +1290,11 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 	 * machinery might be able to exclude relations on the basis of generated
 	 * "var = const" equalities, but "var = param" won't work for that.
 	 */
-	foreach(lc, ec->ec_members)
+	i = -1;
+	while ((i = bms_next_member(ec->ec_norel_indexes, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+												  root->eq_members, i);
 
 		if (cur_em->em_is_const)
 		{
@@ -1204,9 +1335,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.)
 		 */
@@ -1216,7 +1347,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);
 		}
 	}
 }
@@ -1229,7 +1361,8 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 										  EquivalenceClass *ec)
 {
 	EquivalenceMember **prev_ems;
-	ListCell   *lc;
+	Bitmapset  *matching_ems;
+	int			i;
 
 	/*
 	 * We scan the EC members once and track the last-seen member for each
@@ -1242,9 +1375,12 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 	prev_ems = (EquivalenceMember **)
 		palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *));
 
-	foreach(lc, ec->ec_members)
+	matching_ems = bms_difference(ec->ec_member_indexes, ec->ec_norel_indexes);
+	i = -1;
+	while ((i = bms_next_member(matching_ems, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+												  root->eq_members, i);
 		int			relid;
 
 		Assert(!cur_em->em_is_child);	/* no children yet */
@@ -1279,7 +1415,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.
 			 */
@@ -1302,11 +1438,15 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 	 * For the moment we force all the Vars to be available at all join nodes
 	 * for this eclass.  Perhaps this could be improved by doing some
 	 * pre-analysis of which members we prefer to join, but it's no worse than
-	 * what happened in the pre-8.3 code.
+	 * what happened in the pre-8.3 code.  We're able to make use of
+	 * matching_ems from above.  We're not going to find Vars in
+	 * em_const_indexes.
 	 */
-	foreach(lc, ec->ec_members)
+	i = -1;
+	while ((i = bms_next_member(matching_ems, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+												  root->eq_members, i);
 		List	   *vars = pull_var_clause((Node *) cur_em->em_expr,
 										   PVC_RECURSE_AGGREGATES |
 										   PVC_RECURSE_WINDOWFUNCS |
@@ -1315,6 +1455,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 		add_vars_to_targetlist(root, vars, ec->ec_relids);
 		list_free(vars);
 	}
+	bms_free(matching_ems);
 }
 
 /*
@@ -1335,11 +1476,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)
@@ -1380,11 +1522,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.
  *
  * join_relids should always equal bms_union(outer_relids, inner_rel->relids).
  * We could simplify this function's API by computing it internally, but in
@@ -1546,6 +1688,8 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 										Relids outer_relids,
 										Relids inner_relids)
 {
+	EquivalenceMemberIterator iter;
+	EquivalenceMember *cur_em;
 	List	   *result = NIL;
 	List	   *new_members = NIL;
 	List	   *outer_members = NIL;
@@ -1561,10 +1705,10 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 	 * as well as to at least one input member, plus enforce at least one
 	 * outer-rel member equal to at least one inner-rel member.
 	 */
-	foreach(lc1, ec->ec_members)
-	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+	setup_eclass_member_iterator(&iter, root, ec, join_relids, true, false);
 
+	while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
+	{
 		/*
 		 * We don't need to check explicitly for child EC members.  This test
 		 * against join_relids will cause them to be ignored except when
@@ -1581,6 +1725,8 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 			new_members = lappend(new_members, cur_em);
 	}
 
+	eclass_member_iterator_dispose(&iter);
+
 	/*
 	 * First, select the joinclause if needed.  We can equate any one outer
 	 * member to any one inner member, but we have to find a datatype
@@ -1678,7 +1824,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 
 		foreach(lc1, new_members)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+			cur_em = (EquivalenceMember *) lfirst(lc1);
 
 			if (prev_em != NULL)
 			{
@@ -1723,12 +1869,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) &&
@@ -1740,12 +1890,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)
@@ -1807,9 +1957,10 @@ create_join_clause(PlannerInfo *root,
 				   EquivalenceMember *rightem,
 				   EquivalenceClass *parent_ec)
 {
+	Bitmapset  *matches;
 	RestrictInfo *rinfo;
-	ListCell   *lc;
 	MemoryContext oldcontext;
+	int			i;
 
 	/*
 	 * Search to see if we already built a RestrictInfo for this pair of
@@ -1820,9 +1971,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)
@@ -1833,9 +1987,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)
@@ -1877,7 +2035,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);
 
@@ -2069,7 +2227,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 				left_type,
 				right_type,
 				inner_datatype;
-	Relids		inner_relids,
+	Relids		outer_relids,
+				inner_relids,
 				inner_nullable_relids;
 	ListCell   *lc1;
 
@@ -2088,6 +2247,7 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 		outervar = (Expr *) get_leftop(rinfo->clause);
 		innervar = (Expr *) get_rightop(rinfo->clause);
 		inner_datatype = right_type;
+		outer_relids = rinfo->left_relids;
 		inner_relids = rinfo->right_relids;
 	}
 	else
@@ -2095,6 +2255,7 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 		outervar = (Expr *) get_rightop(rinfo->clause);
 		innervar = (Expr *) get_leftop(rinfo->clause);
 		inner_datatype = left_type;
+		outer_relids = rinfo->right_relids;
 		inner_relids = rinfo->left_relids;
 	}
 	inner_nullable_relids = bms_intersect(inner_relids,
@@ -2104,8 +2265,10 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *cur_em;
 		bool		match;
-		ListCell   *lc2;
+		int			i;
 
 		/* Ignore EC unless it contains pseudoconstants */
 		if (!cur_ec->ec_has_const)
@@ -2120,10 +2283,12 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 			continue;
 		/* Does it contain a match to outervar? */
 		match = false;
-		foreach(lc2, cur_ec->ec_members)
-		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 
+		setup_eclass_member_strict_iterator(&iter, root, cur_ec, outer_relids,
+											false, true);
+
+		while ((cur_em = eclass_member_iterator_strict_next(&iter)) != NULL)
+		{
 			Assert(!cur_em->em_is_child);	/* no children yet */
 			if (equal(outervar, cur_em->em_expr))
 			{
@@ -2131,6 +2296,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 				break;
 			}
 		}
+		eclass_member_iterator_dispose(&iter);
+
 		if (!match)
 			continue;			/* no match, so ignore this EC */
 
@@ -2140,12 +2307,14 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 		 * constant before we can decide to throw away the outer-join clause.
 		 */
 		match = false;
-		foreach(lc2, cur_ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(cur_ec->ec_norel_indexes, i)) >= 0)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 			Oid			eq_op;
 			RestrictInfo *newrinfo;
 
+			cur_em = list_nth_node(EquivalenceMember, root->eq_members, i);
+
 			if (!cur_em->em_is_const)
 				continue;		/* ignore non-const members */
 			eq_op = select_equality_operator(cur_ec,
@@ -2221,11 +2390,12 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 		EquivalenceMember *coal_em = NULL;
+		Bitmapset  *matching_ems;
 		bool		match;
 		bool		matchleft;
 		bool		matchright;
-		ListCell   *lc2;
 		int			coal_idx = -1;
+		int			i;
 
 		/* Ignore EC unless it contains pseudoconstants */
 		if (!cur_ec->ec_has_const)
@@ -2252,10 +2422,14 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		 * the two column types). Is it OK to strip implicit coercions from
 		 * the COALESCE arguments?
 		 */
+		matching_ems = get_ecmember_indexes_strict(root, cur_ec,
+												   rinfo->clause_relids, true,
+												   false);
 		match = false;
-		foreach(lc2, cur_ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
-			coal_em = (EquivalenceMember *) lfirst(lc2);
+			coal_em = list_nth_node(EquivalenceMember, root->eq_members, i);
 			Assert(!coal_em->em_is_child);	/* no children yet */
 			if (IsA(coal_em->em_expr, CoalesceExpr))
 			{
@@ -2270,7 +2444,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 
 				if (equal(leftvar, cfirst) && equal(rightvar, csecond))
 				{
-					coal_idx = foreach_current_index(lc2);
+					coal_idx = i;
 					match = true;
 					break;
 				}
@@ -2286,9 +2460,11 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		 * decide to throw away the outer-join clause.
 		 */
 		matchleft = matchright = false;
-		foreach(lc2, cur_ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(cur_ec->ec_norel_indexes, i)) >= 0)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
+													  root->eq_members, i);
 			Oid			eq_op;
 			RestrictInfo *newrinfo;
 
@@ -2333,11 +2509,28 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		 * we can throw away the full-join clause as redundant.  Moreover, we
 		 * can remove the COALESCE entry from the EC, since the added
 		 * restrictions ensure it will always have the expected value. (We
-		 * don't bother trying to update ec_relids or ec_sources.)
+		 * don't bother trying to update ec_relids or root's eq_sources.)
 		 */
 		if (matchleft && matchright)
 		{
-			cur_ec->ec_members = list_delete_nth_cell(cur_ec->ec_members, coal_idx);
+			/* XXX performance of list_delete()?? */
+			cur_ec->ec_members = list_delete(cur_ec->ec_members, coal_em);
+			cur_ec->ec_member_indexes = bms_del_member(cur_ec->ec_member_indexes,
+													   coal_idx);
+			cur_ec->ec_nonchild_indexes = bms_del_member(cur_ec->ec_nonchild_indexes,
+														 coal_idx);
+			/* no need to adjust ec_norel_indexes */
+
+			/* Remove the member from each of the relations */
+			i = -1;
+			while ((i = bms_next_member(coal_em->em_relids, i)) >= 0)
+			{
+				RelOptInfo *rel = root->simple_rel_array[i];
+
+				rel->eclass_member_indexes = bms_del_member(rel->eclass_member_indexes,
+															coal_idx);
+			}
+
 			return true;
 		}
 
@@ -2369,21 +2562,28 @@ bool
 exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
 {
 	ListCell   *lc1;
+	Relids		item1_relids = pull_varnos(root, item1);
+	Relids		item2_relids = pull_varnos(root, item2);
 
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
 		bool		item1member = false;
 		bool		item2member = false;
-		ListCell   *lc2;
+		Bitmapset  *matching_ems;
+		int			i;
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
 			continue;
 
-		foreach(lc2, ec->ec_members)
+		matching_ems = bms_join(get_ecmember_indexes_strict(root, ec, item1_relids, false, true),
+								get_ecmember_indexes_strict(root, ec, item2_relids, false, true));
+		i = -1;
+		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = list_nth_node(EquivalenceMember,
+												  root->eq_members, i);
 
 			if (em->em_is_child)
 				continue;		/* ignore children here */
@@ -2446,16 +2646,21 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 															 i);
 		EquivalenceMember *item1_em = NULL;
 		EquivalenceMember *item2_em = NULL;
-		ListCell   *lc2;
+		Bitmapset  *matching_ems;
+		int			j;
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
 			continue;
 		/* Note: it seems okay to match to "broken" eclasses here */
+		matching_ems = bms_join(get_ecmember_indexes_strict(root, ec, rel1->relids, false, false),
+								get_ecmember_indexes_strict(root, ec, rel2->relids, false, false));
 
-		foreach(lc2, ec->ec_members)
+		j = -1;
+		while ((j = bms_next_member(matching_ems, j)) >= 0)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = list_nth_node(EquivalenceMember,
+												  root->eq_members, j);
 			Var		   *var;
 
 			if (em->em_is_child)
@@ -2508,16 +2713,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
@@ -2568,7 +2776,8 @@ add_child_rel_equivalences(PlannerInfo *root,
 	while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
-		int			num_members;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *cur_em;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2582,86 +2791,72 @@ add_child_rel_equivalences(PlannerInfo *root,
 		Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
 
 		/*
-		 * We don't use foreach() here because there's no point in scanning
-		 * newly-added child members, so we can stop after the last
-		 * pre-existing EC member.
+		 * Looping using the EquivalenceMemberIterator means we only loop over
+		 * the members which existed when we set up the iterator, not newly
+		 * added ones.
 		 */
-		num_members = list_length(cur_ec->ec_members);
-		for (int pos = 0; pos < num_members; pos++)
+		setup_eclass_member_iterator(&iter, root, cur_ec, top_parent_relids,
+									 false, false);
+
+		while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+			Expr	   *child_expr;
+			Relids		new_relids;
+			Relids		new_nullable_relids;
 
-			if (cur_em->em_is_const)
-				continue;		/* ignore consts here */
+			Assert(!cur_em->em_is_const);
+			Assert(!cur_em->em_is_child);
+			Assert(bms_overlap(cur_em->em_relids, top_parent_relids));
+
+			if (parent_rel->reloptkind == RELOPT_BASEREL)
+			{
+				/* Simple single-level transformation */
+				child_expr = (Expr *)
+					adjust_appendrel_attrs(root,
+										   (Node *) cur_em->em_expr,
+										   1, &appinfo);
+			}
+			else
+			{
+				/* Must do multi-level transformation */
+				child_expr = (Expr *)
+					adjust_appendrel_attrs_multilevel(root,
+													  (Node *) cur_em->em_expr,
+													  child_rel,
+													  child_rel->top_parent);
+			}
 
 			/*
-			 * We consider only original EC members here, not
-			 * already-transformed child members.  Otherwise, if some original
-			 * member expression references more than one appendrel, we'd get
-			 * an O(N^2) explosion of useless derived expressions for
-			 * combinations of children.  (But add_child_join_rel_equivalences
-			 * may add targeted combinations for partitionwise-join purposes.)
+			 * Transform em_relids to match.  Note we do *not* do
+			 * pull_varnos(child_expr) here, as for example the transformation
+			 * might have substituted a constant, but we don't want the child
+			 * member to be marked as constant.
 			 */
-			if (cur_em->em_is_child)
-				continue;		/* ignore children here */
+			new_relids = bms_difference(cur_em->em_relids,
+										top_parent_relids);
+			new_relids = bms_add_members(new_relids, child_relids);
 
-			/* Does this member reference child's topmost parent rel? */
-			if (bms_overlap(cur_em->em_relids, top_parent_relids))
+			/*
+			 * And likewise for nullable_relids.  Note this code assumes
+			 * parent and child relids are singletons.
+			 */
+			new_nullable_relids = cur_em->em_nullable_relids;
+			if (bms_overlap(new_nullable_relids, top_parent_relids))
 			{
-				/* Yes, generate transformed child version */
-				Expr	   *child_expr;
-				Relids		new_relids;
-				Relids		new_nullable_relids;
-
-				if (parent_rel->reloptkind == RELOPT_BASEREL)
-				{
-					/* Simple single-level transformation */
-					child_expr = (Expr *)
-						adjust_appendrel_attrs(root,
-											   (Node *) cur_em->em_expr,
-											   1, &appinfo);
-				}
-				else
-				{
-					/* Must do multi-level transformation */
-					child_expr = (Expr *)
-						adjust_appendrel_attrs_multilevel(root,
-														  (Node *) cur_em->em_expr,
-														  child_rel,
-														  child_rel->top_parent);
-				}
-
-				/*
-				 * Transform em_relids to match.  Note we do *not* do
-				 * pull_varnos(child_expr) here, as for example the
-				 * transformation might have substituted a constant, but we
-				 * don't want the child member to be marked as constant.
-				 */
-				new_relids = bms_difference(cur_em->em_relids,
-											top_parent_relids);
-				new_relids = bms_add_members(new_relids, child_relids);
-
-				/*
-				 * And likewise for nullable_relids.  Note this code assumes
-				 * parent and child relids are singletons.
-				 */
-				new_nullable_relids = cur_em->em_nullable_relids;
-				if (bms_overlap(new_nullable_relids, top_parent_relids))
-				{
-					new_nullable_relids = bms_difference(new_nullable_relids,
-														 top_parent_relids);
-					new_nullable_relids = bms_add_members(new_nullable_relids,
-														  child_relids);
-				}
+				new_nullable_relids = bms_difference(new_nullable_relids,
+													 top_parent_relids);
+				new_nullable_relids = bms_add_members(new_nullable_relids,
+													  child_relids);
+			}
 
-				(void) add_eq_member(cur_ec, child_expr,
-									 new_relids, new_nullable_relids,
-									 true, cur_em->em_datatype);
+			(void) add_eq_member(root, cur_ec, child_expr,
+								 new_relids, new_nullable_relids,
+								 true, cur_em->em_datatype);
 
-				/* Record this EC index for the child rel */
-				child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
-			}
+			/* Record this EC index for the child rel */
+			child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
 		}
+		eclass_member_iterator_dispose(&iter);
 	}
 }
 
@@ -2706,7 +2901,8 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 	while ((i = bms_next_member(matching_ecs, i)) >= 0)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
-		int			num_members;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *cur_em;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2720,24 +2916,22 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 		Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
 
 		/*
-		 * We don't use foreach() here because there's no point in scanning
-		 * newly-added child members, so we can stop after the last
-		 * pre-existing EC member.
+		 * Looping using the EquivalenceMemberIterator means we only loop over
+		 * the members which existed when we set up the iterator, not newly
+		 * added ones.
 		 */
-		num_members = list_length(cur_ec->ec_members);
-		for (int pos = 0; pos < num_members; pos++)
-		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+		setup_eclass_member_iterator(&iter, root, cur_ec, top_parent_relids,
+									 false, false);
 
-			if (cur_em->em_is_const)
-				continue;		/* ignore consts here */
+		while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
+		{
+			Expr	   *child_expr;
+			Relids		new_relids;
+			Relids		new_nullable_relids;
 
-			/*
-			 * We consider only original EC members here, not
-			 * already-transformed child members.
-			 */
-			if (cur_em->em_is_child)
-				continue;		/* ignore children here */
+			Assert(!cur_em->em_is_const);
+			Assert(!cur_em->em_is_child);
+			Assert(bms_overlap(cur_em->em_relids, top_parent_relids));
 
 			/*
 			 * We may ignore expressions that reference a single baserel,
@@ -2746,60 +2940,52 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 			if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
 				continue;
 
-			/* Does this member reference child's topmost parent rel? */
-			if (bms_overlap(cur_em->em_relids, top_parent_relids))
+			if (parent_joinrel->reloptkind == RELOPT_JOINREL)
 			{
-				/* Yes, generate transformed child version */
-				Expr	   *child_expr;
-				Relids		new_relids;
-				Relids		new_nullable_relids;
-
-				if (parent_joinrel->reloptkind == RELOPT_JOINREL)
-				{
-					/* Simple single-level transformation */
-					child_expr = (Expr *)
-						adjust_appendrel_attrs(root,
-											   (Node *) cur_em->em_expr,
-											   nappinfos, appinfos);
-				}
-				else
-				{
-					/* Must do multi-level transformation */
-					Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
-					child_expr = (Expr *)
-						adjust_appendrel_attrs_multilevel(root,
-														  (Node *) cur_em->em_expr,
-														  child_joinrel,
-														  child_joinrel->top_parent);
-				}
+				/* Simple single-level transformation */
+				child_expr = (Expr *)
+					adjust_appendrel_attrs(root,
+										   (Node *) cur_em->em_expr,
+										   nappinfos, appinfos);
+			}
+			else
+			{
+				/* Must do multi-level transformation */
+				Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
+				child_expr = (Expr *)
+					adjust_appendrel_attrs_multilevel(root,
+													  (Node *) cur_em->em_expr,
+													  child_joinrel,
+													  child_joinrel->top_parent);
+			}
 
-				/*
-				 * Transform em_relids to match.  Note we do *not* do
-				 * pull_varnos(child_expr) here, as for example the
-				 * transformation might have substituted a constant, but we
-				 * don't want the child member to be marked as constant.
-				 */
-				new_relids = bms_difference(cur_em->em_relids,
-											top_parent_relids);
-				new_relids = bms_add_members(new_relids, child_relids);
+			/*
+			 * Transform em_relids to match.  Note we do *not* do
+			 * pull_varnos(child_expr) here, as for example the transformation
+			 * might have substituted a constant, but we don't want the child
+			 * member to be marked as constant.
+			 */
+			new_relids = bms_difference(cur_em->em_relids,
+										top_parent_relids);
+			new_relids = bms_add_members(new_relids, child_relids);
 
-				/*
-				 * For nullable_relids, we must selectively replace parent
-				 * nullable relids with child ones.
-				 */
-				new_nullable_relids = cur_em->em_nullable_relids;
-				if (bms_overlap(new_nullable_relids, top_parent_relids))
-					new_nullable_relids =
-						adjust_child_relids_multilevel(root,
-													   new_nullable_relids,
-													   child_joinrel,
-													   child_joinrel->top_parent);
-
-				(void) add_eq_member(cur_ec, child_expr,
-									 new_relids, new_nullable_relids,
-									 true, cur_em->em_datatype);
-			}
+			/*
+			 * For nullable_relids, we must selectively replace parent
+			 * nullable relids with child ones.
+			 */
+			new_nullable_relids = cur_em->em_nullable_relids;
+			if (bms_overlap(new_nullable_relids, top_parent_relids))
+				new_nullable_relids =
+					adjust_child_relids_multilevel(root,
+												   new_nullable_relids,
+												   child_joinrel,
+												   child_joinrel->top_parent);
+
+			(void) add_eq_member(root, cur_ec, child_expr,
+								 new_relids, new_nullable_relids,
+								 true, cur_em->em_datatype);
 		}
+		eclass_member_iterator_dispose(&iter);
 	}
 
 	MemoryContextSwitchTo(oldcontext);
@@ -2858,7 +3044,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		EquivalenceMember *cur_em;
-		ListCell   *lc2;
+		EquivalenceMemberIterator iter;
+		int			j;
 
 		/* Sanity check eclass_indexes only contain ECs for rel */
 		Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
@@ -2880,16 +3067,19 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		 * corner cases, so for now we live with just reporting the first
 		 * match.  See also get_eclass_for_sort_expr.)
 		 */
-		cur_em = NULL;
-		foreach(lc2, cur_ec->ec_members)
+		setup_eclass_member_iterator(&iter, root, cur_ec, rel->relids, true,
+									 false);
+
+		while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
 		{
-			cur_em = (EquivalenceMember *) lfirst(lc2);
 			if (bms_equal(cur_em->em_relids, rel->relids) &&
 				callback(root, rel, cur_ec, cur_em, callback_arg))
 				break;
 			cur_em = NULL;
 		}
 
+		eclass_member_iterator_dispose(&iter);
+
 		if (!cur_em)
 			continue;
 
@@ -2897,14 +3087,15 @@ 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)
+		j = -1;
+		while ((j = bms_next_member(cur_ec->ec_nonchild_indexes, j)) >= 0)
 		{
-			EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *other_em = list_nth_node(EquivalenceMember,
+														root->eq_members, j);
 			Oid			eq_op;
 			RestrictInfo *rinfo;
 
-			if (other_em->em_is_child)
-				continue;		/* ignore children here */
+			Assert(!other_em->em_is_child);
 
 			/* Make sure it'll be a join to a different rel */
 			if (other_em == cur_em ||
@@ -3001,7 +3192,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
@@ -3076,7 +3267,7 @@ eclass_useful_for_merging(PlannerInfo *root,
 						  RelOptInfo *rel)
 {
 	Relids		relids;
-	ListCell   *lc;
+	int			i;
 
 	Assert(!eclass->ec_merged);
 
@@ -3089,7 +3280,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.
 	 */
 
@@ -3107,12 +3298,14 @@ eclass_useful_for_merging(PlannerInfo *root,
 		return false;
 
 	/* To join, we need a member not in the given rel */
-	foreach(lc, eclass->ec_members)
+	i = -1;
+	while ((i = bms_next_member(eclass->ec_nonchild_indexes, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em =
+		list_nth_node(EquivalenceMember, root->eq_members, i);
 
-		if (cur_em->em_is_child)
-			continue;			/* ignore children here */
+		/* we don't expect child members here */
+		Assert(!cur_em->em_is_child);
 
 		if (!bms_overlap(cur_em->em_relids, relids))
 			return true;
@@ -3200,7 +3393,7 @@ get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
 	/* Should be OK to rely on eclass_indexes */
 	Assert(root->ec_merging_done);
 
-	while ((i = bms_next_member(relids, i)) > 0)
+	while ((i = bms_next_member(relids, i)) >= 0)
 	{
 		RelOptInfo *rel = root->simple_rel_array[i];
 
@@ -3236,3 +3429,595 @@ 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_ecmember_indexes
+ *		Returns a Bitmapset with indexes into root->eq_members for all
+ *		EquivalenceMembers in 'ec' that have
+ *		bms_overlap(em->em_relids, relids) as true.  The returned indexes
+ *		may reference EquivalenceMembers with em_relids containing members
+ *		not mentioned in 'relids'.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ecmember_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids,
+					 bool with_children, bool with_norel_members)
+{
+	Bitmapset  *matching_ems;
+	Bitmapset  *rel_ems = NULL;
+	int			i = -1;
+
+	while ((i = bms_next_member(relids, i)) >= 0)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		rel_ems = bms_add_members(rel_ems, rel->eclass_member_indexes);
+	}
+
+#ifdef USE_ASSERT_CHECKING
+	/* verify the results look sane */
+	i = -1;
+	while ((i = bms_next_member(rel_ems, i)) >= 0)
+	{
+		EquivalenceMember *em = list_nth_node(EquivalenceMember,
+											  root->eq_members, i);
+
+		Assert(bms_overlap(em->em_relids, relids));
+	}
+#endif
+
+	/* remove EC members not mentioning the required rels. */
+	if (!with_children)
+		matching_ems = bms_int_members(rel_ems, ec->ec_nonchild_indexes);
+	else
+		matching_ems = bms_int_members(rel_ems, ec->ec_member_indexes);
+
+	/* now add any members with that are not mentioned by any relation */
+	if (with_norel_members)
+		matching_ems = bms_add_members(matching_ems, ec->ec_norel_indexes);
+
+	return matching_ems;
+}
+
+/*
+ * get_ecmember_indexes_strict
+ *		Returns a Bitmapset with indexes into root->eq_members for all
+ *		EquivalenceMembers in 'ec' that have
+ *		bms_is_subset(relids, em->em_relids) as true.
+ *
+ * Returns a newly allocated Bitmapset which the caller is free to modify.
+ */
+Bitmapset *
+get_ecmember_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
+							Relids relids, bool with_children,
+							bool with_norel_members)
+{
+	Bitmapset  *matching_ems = NULL;
+	int			i = bms_next_member(relids, -1);
+
+	if (i >= 0)
+	{
+		RelOptInfo *rel = root->simple_rel_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.
+		 */
+		if (!with_children)
+			matching_ems = bms_intersect(rel->eclass_member_indexes,
+										 ec->ec_nonchild_indexes);
+		else
+			matching_ems = bms_intersect(rel->eclass_member_indexes,
+										 ec->ec_member_indexes);
+
+		while ((i = bms_next_member(relids, i)) >= 0)
+		{
+			rel = root->simple_rel_array[i];
+			matching_ems = bms_int_members(matching_ems,
+										   rel->eclass_member_indexes);
+		}
+	}
+
+#ifdef USE_ASSERT_CHECKING
+	/* verify the results look sane */
+	i = -1;
+	while ((i = bms_next_member(matching_ems, i)) >= 0)
+	{
+		EquivalenceMember *em = list_nth_node(EquivalenceMember,
+											  root->eq_members, i);
+
+		Assert(bms_is_subset(relids, em->em_relids));
+	}
+#endif
+
+	/* optionally add members with that are not mentioned by any relation */
+	if (with_norel_members)
+		matching_ems = bms_add_members(matching_ems, ec->ec_norel_indexes);
+
+	return matching_ems;
+}
+
+/*
+ * The threshold for the number of members that must be in an EquivalenceClass
+ * before we switch to searching for EquivalenceMember by using the Bitmapset
+ * indexes stored in EquivalenceClass and RelOptInfo.  We don't want to make
+ * this too low as the manipulation of Bitmapsets slows this down for
+ * EquivalenceClasses with just a few members.  The linear search becomes very
+ * slow when an EquivalenceClass has a large number of members, as can happen
+ * when planning queries to partitioned tables.
+ */
+#define ECMEMBER_INDEX_THRESHOLD 16
+
+/*
+ * setup_eclass_member_iterator
+ *		Setup 'iter' so it's ready for eclass_member_iterator_next to start
+ *		searching for EquivalenceMembers matching the specified parameters.
+ *
+ * Once used, the iterator must be disposed of using
+ * eclass_member_iterator_dispose.
+ */
+void
+setup_eclass_member_iterator(EquivalenceMemberIterator *iter,
+							 PlannerInfo *root, EquivalenceClass *ec,
+							 Relids relids, bool with_children,
+							 bool with_norel_members)
+{
+	iter->orig_length = list_length(ec->ec_members);
+	iter->use_index = iter->orig_length >= ECMEMBER_INDEX_THRESHOLD;
+	iter->with_children = with_children;
+	iter->with_norel_members = with_norel_members;
+	iter->relids_empty = bms_is_empty(relids);
+#ifdef USE_ASSERT_CHECKING
+	iter->isstrict = false;
+#endif
+	iter->with_relids = relids;
+	iter->root = root;
+	iter->eclass = ec;
+
+#ifdef USE_ASSERT_CHECKING
+	if (1)
+#else
+	if (iter->use_index)
+#endif
+		iter->matching_ems = get_ecmember_indexes(root, ec, relids,
+												  with_children,
+												  with_norel_members);
+	else
+		iter->matching_ems = NULL;
+
+	iter->current_index = -1;
+
+#ifdef USE_ASSERT_CHECKING
+
+	/*
+	 * Verify that an iterator that uses the index and one that does not both
+	 * return the same EquivalenceMembers
+	 */
+	{
+		EquivalenceMemberIterator idx_iter;
+		EquivalenceMemberIterator noidx_iter;
+		EquivalenceMember *em;
+		List	   *list1 = NIL;
+		List	   *list2 = NIL;
+		ListCell   *lc1,
+				   *lc2;
+
+		memcpy(&idx_iter, iter, sizeof(EquivalenceMemberIterator));
+		memcpy(&noidx_iter, iter, sizeof(EquivalenceMemberIterator));
+
+		idx_iter.use_index = true;
+		noidx_iter.use_index = false;
+
+		while ((em = eclass_member_iterator_next(&idx_iter)) != NULL)
+			list1 = lappend(list1, em);
+
+		while ((em = eclass_member_iterator_next(&noidx_iter)) != NULL)
+			list2 = lappend(list2, em);
+
+		list_sort(list1, list_ptr_cmp);
+		list_sort(list2, list_ptr_cmp);
+
+		Assert(list_length(list1) == list_length(list2));
+
+		forboth(lc1, list1, lc2, list2)
+			Assert(lfirst(lc1) == lfirst(lc2));
+	}
+#endif
+
+}
+
+/*
+ * setup_eclass_member_strict_iterator
+ *		Setup 'iter' so it's ready for eclass_member_iterator_strict_next to
+ *		start searching for EquivalenceMembers matching the specified
+ *		parameters.
+ *
+ * Once used, the iterator must be disposed of using
+ * eclass_member_iterator_dispose.
+ */
+void
+setup_eclass_member_strict_iterator(EquivalenceMemberIterator *iter,
+									PlannerInfo *root, EquivalenceClass *ec,
+									Relids relids, bool with_children,
+									bool with_norel_members)
+{
+	iter->orig_length = list_length(ec->ec_members);
+	iter->use_index = iter->orig_length >= ECMEMBER_INDEX_THRESHOLD;
+	iter->with_children = with_children;
+	iter->with_norel_members = with_norel_members;
+	iter->relids_empty = bms_is_empty(relids);
+#ifdef USE_ASSERT_CHECKING
+	iter->isstrict = true;
+#endif
+	iter->with_relids = relids;
+	iter->root = root;
+	iter->eclass = ec;
+
+#ifdef USE_ASSERT_CHECKING
+	if (1)
+#else
+	if (iter->use_index)
+#endif
+		iter->matching_ems = get_ecmember_indexes_strict(root, ec, relids,
+														 with_children,
+														 with_norel_members);
+	else
+		iter->matching_ems = NULL;
+
+	iter->current_index = -1;
+
+#ifdef USE_ASSERT_CHECKING
+
+	/*
+	 * Verify that an iterator that uses the index and one that does not both
+	 * return the same EquivalenceMembers
+	 */
+	{
+		EquivalenceMemberIterator idx_iter;
+		EquivalenceMemberIterator noidx_iter;
+		EquivalenceMember *em;
+		List	   *list1 = NIL;
+		List	   *list2 = NIL;
+		ListCell   *lc1,
+				   *lc2;
+
+		memcpy(&idx_iter, iter, sizeof(EquivalenceMemberIterator));
+		memcpy(&noidx_iter, iter, sizeof(EquivalenceMemberIterator));
+
+		idx_iter.use_index = true;
+		noidx_iter.use_index = false;
+
+		while ((em = eclass_member_iterator_strict_next(&idx_iter)) != NULL)
+			list1 = lappend(list1, em);
+
+		while ((em = eclass_member_iterator_strict_next(&noidx_iter)) != NULL)
+			list2 = lappend(list2, em);
+
+		list_sort(list1, list_ptr_cmp);
+		list_sort(list2, list_ptr_cmp);
+
+		Assert(list_length(list1) == list_length(list2));
+
+		forboth(lc1, list1, lc2, list2)
+			Assert(lfirst(lc1) == lfirst(lc2));
+	}
+#endif
+}
+
+/*
+ * eclass_member_iterator_next
+ *		Fetch the next EquivalenceMember from an EquivalenceMemberIterator
+ *		which was set up by setup_eclass_member_iterator().  Returns NULL when
+ *		there are no more matching EquivalenceMembers.
+ */
+EquivalenceMember *
+eclass_member_iterator_next(EquivalenceMemberIterator *iter)
+{
+	/* Fail if this was used instead of eclass_member_iterator_strict_next */
+	Assert(!iter->isstrict);
+
+	if (iter->use_index)
+	{
+		iter->current_index = bms_next_member(iter->matching_ems,
+											  iter->current_index);
+		if (iter->current_index >= 0)
+			return list_nth_node(EquivalenceMember, iter->root->eq_members,
+								 iter->current_index);
+		return NULL;
+	}
+	else
+	{
+		ListCell   *lc;
+
+		for_each_from(lc, iter->eclass->ec_members, iter->current_index + 1)
+		{
+			EquivalenceMember *em = lfirst_node(EquivalenceMember, lc);
+
+			iter->current_index = foreach_current_index(lc);
+
+			/*
+			 * Some users of this iterator will be adding new
+			 * EquivalenceMember during the loop.  We must ensure we don't
+			 * return those, so here we return NULL when the loop index goes
+			 * beyond the original length of the ec_members list.
+			 */
+			if (iter->current_index >= iter->orig_length)
+				return NULL;
+
+			/* don't return child members when with_children==false */
+			if (!iter->with_children && em->em_is_child)
+				continue;
+
+			/*
+			 * When with_norel_members==true, make sure we return all members
+			 * without Vars.
+			 */
+			if (iter->with_norel_members && em->em_norel_expr)
+				return em;
+
+			/*
+			 * Don't return members which have no common rels with with_relids
+			 */
+			if (!bms_overlap(em->em_relids, iter->with_relids))
+				continue;
+
+			return em;
+		}
+		return NULL;
+	}
+}
+
+/*
+ * eclass_member_iterator_strict_next
+ *		Fetch the next EquivalenceMember from an EquivalenceMemberIterator
+ *		which was set up by setup_eclass_member_strict_iterator().  Returns
+ *		NULL when there are no more matching EquivalenceMembers.
+ */
+EquivalenceMember *
+eclass_member_iterator_strict_next(EquivalenceMemberIterator *iter)
+{
+	/* Fail if this was used instead of eclass_member_iterator_next */
+	Assert(iter->isstrict);
+
+	if (iter->use_index)
+	{
+		iter->current_index = bms_next_member(iter->matching_ems,
+											  iter->current_index);
+		if (iter->current_index >= 0)
+			return list_nth_node(EquivalenceMember, iter->root->eq_members,
+								 iter->current_index);
+		return NULL;
+	}
+	else
+	{
+		ListCell   *lc;
+
+		for_each_from(lc, iter->eclass->ec_members, iter->current_index + 1)
+		{
+			EquivalenceMember *em = lfirst_node(EquivalenceMember, lc);
+
+			iter->current_index = foreach_current_index(lc);
+
+			/*
+			 * Some users of this iterator will be adding new
+			 * EquivalenceMember during the loop.  We must ensure we don't
+			 * return those, so here we return NULL when the loop index goes
+			 * beyond the original length of the ec_members list.
+			 */
+			if (iter->current_index >= iter->orig_length)
+				return NULL;
+
+			/* don't return child members when with_children==false */
+			if (!iter->with_children && em->em_is_child)
+				continue;
+
+			/*
+			 * When with_norel_members==true, make sure we return all members
+			 * without Vars.
+			 */
+			if (iter->with_norel_members && em->em_norel_expr)
+				return em;
+
+			/*
+			 * Don't match members where em_relids that don't contain all rels
+			 * mentioned in with_relids.
+			 */
+			if (iter->relids_empty ||
+				!bms_is_subset(iter->with_relids, em->em_relids))
+				continue;
+
+			return em;
+		}
+		return NULL;
+	}
+}
+
+/*
+ * eclass_member_iterator_dispose
+ *		Free any memory allocated by the iterator
+ */
+void
+eclass_member_iterator_dispose(EquivalenceMemberIterator *iter)
+{
+	bms_free(iter->matching_ems);
+}
+
+
+/*
+ * 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)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		rel_esis = bms_add_members(rel_esis, rel->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)
+	{
+		RelOptInfo *rel = root->simple_rel_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,
+							 rel->eclass_source_indexes);
+
+		while ((i = bms_next_member(relids, i)) >= 0)
+		{
+			rel = root->simple_rel_array[i];
+			esis = bms_int_members(esis, rel->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)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		rel_edis = bms_add_members(rel_edis, rel->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)
+	{
+		RelOptInfo *rel = root->simple_rel_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,
+							 rel->eclass_derive_indexes);
+
+		while ((i = bms_next_member(relids, i)) >= 0)
+		{
+			rel = root->simple_rel_array[i];
+			edis = bms_int_members(edis, rel->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/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index e13c8f1914..e1b736c0c0 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -184,8 +184,8 @@ static IndexClause *expand_indexqual_rowcompare(PlannerInfo *root,
 												IndexOptInfo *index,
 												Oid expr_op,
 												bool var_on_left);
-static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
-									List **orderby_clauses_p,
+static void match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index,
+									List *pathkeys, List **orderby_clauses_p,
 									List **clause_columns_p);
 static Expr *match_clause_to_ordering_op(IndexOptInfo *index,
 										 int indexcol, Expr *clause, Oid pk_opfamily);
@@ -978,7 +978,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
 	else if (index->amcanorderbyop && pathkeys_possibly_useful)
 	{
 		/* see if we can generate ordering operators for query_pathkeys */
-		match_pathkeys_to_index(index, root->query_pathkeys,
+		match_pathkeys_to_index(root, index, root->query_pathkeys,
 								&orderbyclauses,
 								&orderbyclausecols);
 		if (orderbyclauses)
@@ -3070,8 +3070,8 @@ expand_indexqual_rowcompare(PlannerInfo *root,
  * one-to-one with the requested pathkeys.
  */
 static void
-match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
-						List **orderby_clauses_p,
+match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index,
+						List *pathkeys, List **orderby_clauses_p,
 						List **clause_columns_p)
 {
 	List	   *orderby_clauses = NIL;
@@ -3088,8 +3088,9 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 	foreach(lc1, pathkeys)
 	{
 		PathKey    *pathkey = (PathKey *) lfirst(lc1);
+		Bitmapset  *matching_ems;
 		bool		found = false;
-		ListCell   *lc2;
+		int			i;
 
 		/*
 		 * Note: for any failure to match, we just return NIL immediately.
@@ -3113,9 +3114,14 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 		 * be considered to match more than one pathkey list, which is OK
 		 * here.  See also get_eclass_for_sort_expr.)
 		 */
-		foreach(lc2, pathkey->pk_eclass->ec_members)
+		matching_ems = bms_intersect(pathkey->pk_eclass->ec_member_indexes,
+									 index->rel->eclass_member_indexes);
+
+		i = -1;
+		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
-			EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *member = list_nth_node(EquivalenceMember,
+													  root->eq_members, i);
 			int			indexcol;
 
 			/* No possibility of match if it references other relations */
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index d2e241c983..e715d5135b 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -955,18 +955,19 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 			 * outer query.
 			 */
 			int			best_score = -1;
-			ListCell   *j;
+			int			j = -1;
 
-			foreach(j, sub_eclass->ec_members)
+			while ((j = bms_next_member(sub_eclass->ec_nonchild_indexes, j)) >= 0)
 			{
-				EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
+				EquivalenceMember *sub_member = list_nth_node(EquivalenceMember,
+															  rel->subroot->eq_members,
+															  j);
 				Expr	   *sub_expr = sub_member->em_expr;
 				Oid			sub_expr_type = sub_member->em_datatype;
 				Oid			sub_expr_coll = sub_eclass->ec_collation;
 				ListCell   *k;
 
-				if (sub_member->em_is_child)
-					continue;	/* ignore children here */
+				Assert(!sub_member->em_is_child);
 
 				foreach(k, subquery_tlist)
 				{
@@ -1476,7 +1477,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
 		EquivalenceClass *oeclass;
 		int			score;
-		ListCell   *lc2;
+		int			i;
 
 		/* get the outer eclass */
 		update_mergeclause_eclasses(root, rinfo);
@@ -1497,13 +1498,16 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 
 		/* compute score */
 		score = 0;
-		foreach(lc2, oeclass->ec_members)
+		i = -1;
+		while ((i = bms_next_member(oeclass->ec_nonchild_indexes, i)) >= 0)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = list_nth_node(EquivalenceMember,
+												  root->eq_members, i);
 
-			/* Potential future join partner? */
-			if (!em->em_is_const && !em->em_is_child &&
-				!bms_overlap(em->em_relids, joinrel->relids))
+			/* shouldn't be consts or child members in ec_nonchild_indexes */
+			Assert(!em->em_is_const && !em->em_is_child);
+
+			if (!bms_overlap(em->em_relids, joinrel->relids))
 				score++;
 		}
 
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index cd68942af0..d519b97dbf 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -260,8 +260,8 @@ static IncrementalSort *make_incrementalsort(Plan *lefttree,
 											 int numCols, int nPresortedCols,
 											 AttrNumber *sortColIdx, Oid *sortOperators,
 											 Oid *collations, bool *nullsFirst);
-static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
-										Relids relids,
+static Plan *prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+										List *pathkeys, Relids relids,
 										const AttrNumber *reqColIdx,
 										bool adjust_tlist_in_place,
 										int *p_numsortkeys,
@@ -269,10 +269,13 @@ static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
 										Oid **p_sortOperators,
 										Oid **p_collations,
 										bool **p_nullsFirst);
-static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
-									 Relids relids);
-static IncrementalSort *make_incrementalsort_from_pathkeys(Plan *lefttree,
-														   List *pathkeys, Relids relids, int nPresortedCols);
+static Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+									 List *pathkeys, Relids relids);
+static IncrementalSort *make_incrementalsort_from_pathkeys(PlannerInfo *root,
+														   Plan *lefttree,
+														   List *pathkeys,
+														   Relids relids,
+														   int nPresortedCols);
 static Sort *make_sort_from_groupcols(List *groupcls,
 									  AttrNumber *grpColIdx,
 									  Plan *lefttree);
@@ -293,7 +296,7 @@ static Group *make_group(List *tlist, List *qual, int numGroupCols,
 						 AttrNumber *grpColIdx, Oid *grpOperators, Oid *grpCollations,
 						 Plan *lefttree);
 static Unique *make_unique_from_sortclauses(Plan *lefttree, List *distinctList);
-static Unique *make_unique_from_pathkeys(Plan *lefttree,
+static Unique *make_unique_from_pathkeys(PlannerInfo *root, Plan *lefttree,
 										 List *pathkeys, int numCols);
 static Gather *make_gather(List *qptlist, List *qpqual,
 						   int nworkers, int rescan_param, bool single_copy, Plan *subplan);
@@ -1260,7 +1263,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
 		 * function result; it must be the same plan node.  However, we then
 		 * need to detect whether any tlist entries were added.
 		 */
-		(void) prepare_sort_from_pathkeys((Plan *) plan, pathkeys,
+		(void) prepare_sort_from_pathkeys(root,
+										  (Plan *) plan, pathkeys,
 										  best_path->path.parent->relids,
 										  NULL,
 										  true,
@@ -1304,7 +1308,7 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
 			 * don't need an explicit sort, to make sure they are returning
 			 * the same sort key columns the Append expects.
 			 */
-			subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+			subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
 												 subpath->parent->relids,
 												 nodeSortColIdx,
 												 false,
@@ -1445,7 +1449,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
 	 * function result; it must be the same plan node.  However, we then need
 	 * to detect whether any tlist entries were added.
 	 */
-	(void) prepare_sort_from_pathkeys(plan, pathkeys,
+	(void) prepare_sort_from_pathkeys(root, plan, pathkeys,
 									  best_path->path.parent->relids,
 									  NULL,
 									  true,
@@ -1476,7 +1480,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
 		subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
 
 		/* Compute sort column info, and adjust subplan's tlist as needed */
-		subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+		subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
 											 subpath->parent->relids,
 											 node->sortColIdx,
 											 false,
@@ -1966,7 +1970,7 @@ create_gather_merge_plan(PlannerInfo *root, GatherMergePath *best_path)
 	Assert(pathkeys != NIL);
 
 	/* Compute sort column info, and adjust subplan's tlist as needed */
-	subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+	subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
 										 best_path->subpath->parent->relids,
 										 gm_plan->sortColIdx,
 										 false,
@@ -2185,7 +2189,7 @@ create_sort_plan(PlannerInfo *root, SortPath *best_path, int flags)
 	 * relids. Thus, if this sort path is based on a child relation, we must
 	 * pass its relids.
 	 */
-	plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys,
+	plan = make_sort_from_pathkeys(root, subplan, best_path->path.pathkeys,
 								   IS_OTHER_REL(best_path->subpath->parent) ?
 								   best_path->path.parent->relids : NULL);
 
@@ -2209,7 +2213,7 @@ create_incrementalsort_plan(PlannerInfo *root, IncrementalSortPath *best_path,
 	/* See comments in create_sort_plan() above */
 	subplan = create_plan_recurse(root, best_path->spath.subpath,
 								  flags | CP_SMALL_TLIST);
-	plan = make_incrementalsort_from_pathkeys(subplan,
+	plan = make_incrementalsort_from_pathkeys(root, subplan,
 											  best_path->spath.path.pathkeys,
 											  IS_OTHER_REL(best_path->spath.subpath->parent) ?
 											  best_path->spath.path.parent->relids : NULL,
@@ -2278,7 +2282,7 @@ create_upper_unique_plan(PlannerInfo *root, UpperUniquePath *best_path, int flag
 	subplan = create_plan_recurse(root, best_path->subpath,
 								  flags | CP_LABEL_TLIST);
 
-	plan = make_unique_from_pathkeys(subplan,
+	plan = make_unique_from_pathkeys(root, subplan,
 									 best_path->path.pathkeys,
 									 best_path->numkeys);
 
@@ -4483,7 +4487,7 @@ create_mergejoin_plan(PlannerInfo *root,
 	if (best_path->outersortkeys)
 	{
 		Relids		outer_relids = outer_path->parent->relids;
-		Sort	   *sort = make_sort_from_pathkeys(outer_plan,
+		Sort	   *sort = make_sort_from_pathkeys(root, outer_plan,
 												   best_path->outersortkeys,
 												   outer_relids);
 
@@ -4497,7 +4501,7 @@ create_mergejoin_plan(PlannerInfo *root,
 	if (best_path->innersortkeys)
 	{
 		Relids		inner_relids = inner_path->parent->relids;
-		Sort	   *sort = make_sort_from_pathkeys(inner_plan,
+		Sort	   *sort = make_sort_from_pathkeys(root, inner_plan,
 												   best_path->innersortkeys,
 												   inner_relids);
 
@@ -6117,7 +6121,8 @@ make_incrementalsort(Plan *lefttree, int numCols, int nPresortedCols,
  * or a Result stacked atop lefttree).
  */
 static Plan *
-prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
+prepare_sort_from_pathkeys(PlannerInfo *root,
+						   Plan *lefttree, List *pathkeys,
 						   Relids relids,
 						   const AttrNumber *reqColIdx,
 						   bool adjust_tlist_in_place,
@@ -6184,7 +6189,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
 			tle = get_tle_by_resno(tlist, reqColIdx[numsortkeys]);
 			if (tle)
 			{
-				em = find_ec_member_matching_expr(ec, tle->expr, relids);
+				em = find_ec_member_matching_expr(root, ec, tle->expr, relids);
 				if (em)
 				{
 					/* found expr at right place in tlist */
@@ -6215,7 +6220,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
 			foreach(j, tlist)
 			{
 				tle = (TargetEntry *) lfirst(j);
-				em = find_ec_member_matching_expr(ec, tle->expr, relids);
+				em = find_ec_member_matching_expr(root, ec, tle->expr, relids);
 				if (em)
 				{
 					/* found expr already in tlist */
@@ -6231,7 +6236,7 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
 			/*
 			 * No matching tlist item; look for a computable expression.
 			 */
-			em = find_computable_ec_member(NULL, ec, tlist, relids, false);
+			em = find_computable_ec_member(root, ec, tlist, relids, false);
 			if (!em)
 				elog(ERROR, "could not find pathkey item to sort");
 			pk_datatype = em->em_datatype;
@@ -6302,7 +6307,8 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
  *	  'relids' is the set of relations required by prepare_sort_from_pathkeys()
  */
 static Sort *
-make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids)
+make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+						Relids relids)
 {
 	int			numsortkeys;
 	AttrNumber *sortColIdx;
@@ -6311,7 +6317,9 @@ make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids)
 	bool	   *nullsFirst;
 
 	/* Compute sort column info, and adjust lefttree as needed */
-	lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys,
+	lefttree = prepare_sort_from_pathkeys(root,
+										  lefttree,
+										  pathkeys,
 										  relids,
 										  NULL,
 										  false,
@@ -6337,7 +6345,8 @@ make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids)
  *	  'nPresortedCols' is the number of presorted columns in input tuples
  */
 static IncrementalSort *
-make_incrementalsort_from_pathkeys(Plan *lefttree, List *pathkeys,
+make_incrementalsort_from_pathkeys(PlannerInfo *root,
+								   Plan *lefttree, List *pathkeys,
 								   Relids relids, int nPresortedCols)
 {
 	int			numsortkeys;
@@ -6347,7 +6356,9 @@ make_incrementalsort_from_pathkeys(Plan *lefttree, List *pathkeys,
 	bool	   *nullsFirst;
 
 	/* Compute sort column info, and adjust lefttree as needed */
-	lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys,
+	lefttree = prepare_sort_from_pathkeys(root,
+										  lefttree,
+										  pathkeys,
 										  relids,
 										  NULL,
 										  false,
@@ -6697,7 +6708,8 @@ make_unique_from_sortclauses(Plan *lefttree, List *distinctList)
  * as above, but use pathkeys to identify the sort columns and semantics
  */
 static Unique *
-make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
+make_unique_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+						  int numCols)
 {
 	Unique	   *node = makeNode(Unique);
 	Plan	   *plan = &node->plan;
@@ -6760,7 +6772,7 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
 			foreach(j, plan->targetlist)
 			{
 				tle = (TargetEntry *) lfirst(j);
-				em = find_ec_member_matching_expr(ec, tle->expr, NULL);
+				em = find_ec_member_matching_expr(root, ec, tle->expr, NULL);
 				if (em)
 				{
 					/* found expr already in tlist */
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c
index d168620665..9f0fa42045 100644
--- a/src/backend/optimizer/plan/planagg.c
+++ b/src/backend/optimizer/plan/planagg.c
@@ -356,6 +356,7 @@ build_minmax_path(PlannerInfo *root, MinMaxAggInfo *mminfo,
 	Assert(subroot->join_info_list == NIL);
 	/* and we haven't made equivalence classes, either */
 	Assert(subroot->eq_classes == NIL);
+	Assert(root->eq_members == NIL);
 	/* and we haven't created PlaceHolderInfos, either */
 	Assert(subroot->placeholder_list == NIL);
 
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 05f44faf6e..f12f7fa83b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -626,6 +626,9 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root->cte_plan_ids = NIL;
 	root->multiexpr_params = NIL;
 	root->eq_classes = NIL;
+	root->eq_members = NIL;
+	root->eq_sources = NIL;
+	root->eq_derives = NIL;
 	root->ec_merging_done = false;
 	root->all_result_relids =
 		parse->resultRelation ? bms_make_singleton(parse->resultRelation) : NULL;
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 37a7af8c66..b7eaeb6163 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -1000,6 +1000,9 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->cte_plan_ids = NIL;
 	subroot->multiexpr_params = NIL;
 	subroot->eq_classes = NIL;
+	subroot->eq_members = NIL;
+	subroot->eq_sources = NIL;
+	subroot->eq_derives = NIL;
 	subroot->ec_merging_done = false;
 	subroot->all_result_relids = NULL;
 	subroot->leaf_result_relids = NULL;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 0c68ec011b..4c7d66311f 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -45,7 +45,7 @@
 #include "utils/selfuncs.h"
 #include "utils/syscache.h"
 
-
+static void setup_append_rel_entry(PlannerInfo *root);
 static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
 										  List *colTypes, List *colCollations,
 										  bool junkOK,
@@ -128,6 +128,7 @@ plan_set_operations(PlannerInfo *root)
 	 * so that pathkeys.c won't complain.
 	 */
 	Assert(root->eq_classes == NIL);
+	Assert(root->eq_members == NIL);
 	root->ec_merging_done = true;
 
 	/*
@@ -149,6 +150,8 @@ plan_set_operations(PlannerInfo *root)
 	leftmostQuery = leftmostRTE->subquery;
 	Assert(leftmostQuery != NULL);
 
+	setup_append_rel_entry(root);
+
 	/*
 	 * If the topmost node is a recursive union, it needs special processing.
 	 */
@@ -180,6 +183,26 @@ plan_set_operations(PlannerInfo *root)
 	return setop_rel;
 }
 
+/*
+ * setup_append_rel_entry
+ *		Add entry into root's simple_rel_array at element 0.  This is required
+ *		because generate_append_tlist() makes Vars with varno=0.  In
+ *		add_eq_member() we need to index EquivalenceMembers belonging to this
+ *		relation.
+ */
+static void
+setup_append_rel_entry(PlannerInfo *root)
+{
+	RelOptInfo *rel = makeNode(RelOptInfo);
+
+	memset(rel, 0, sizeof(RelOptInfo));
+	rel->eclass_member_indexes = NULL;
+
+	/* make sure nothing else has made use of this element */
+	Assert(root->simple_rel_array[0] == NULL);
+	root->simple_rel_array[0] = rel;
+}
+
 /*
  * recurse_set_operations
  *	  Recursively handle one step in a tree of set operations
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 0a5632699d..ace943c87d 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -219,6 +219,9 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
 	rel->tuples = 0;
 	rel->allvisfrac = 0;
 	rel->eclass_indexes = NULL;
+	rel->eclass_member_indexes = NULL;
+	rel->eclass_source_indexes = NULL;
+	rel->eclass_derive_indexes = NULL;
 	rel->subroot = NULL;
 	rel->subplan_params = NIL;
 	rel->rel_parallel_workers = -1; /* set up in get_relation_info */
@@ -648,6 +651,9 @@ build_join_rel(PlannerInfo *root,
 	joinrel->tuples = 0;
 	joinrel->allvisfrac = 0;
 	joinrel->eclass_indexes = NULL;
+	joinrel->eclass_member_indexes = NULL;
+	joinrel->eclass_source_indexes = NULL;
+	joinrel->eclass_derive_indexes = NULL;
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->rel_parallel_workers = -1;
@@ -834,6 +840,9 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
 	joinrel->tuples = 0;
 	joinrel->allvisfrac = 0;
 	joinrel->eclass_indexes = NULL;
+	joinrel->eclass_member_indexes = NULL;
+	joinrel->eclass_source_indexes = NULL;
+	joinrel->eclass_derive_indexes = NULL;
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->amflags = 0;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 2d1d8f4bcd..d888cd54d3 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -306,6 +306,15 @@ struct PlannerInfo
 	/* list of active EquivalenceClasses */
 	List	   *eq_classes;
 
+	/* list of each EquivalenceMember */
+	List	   *eq_members;
+
+	/* 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;
 
@@ -926,6 +935,24 @@ typedef struct RelOptInfo
 	 * Indexes in PlannerInfo's eq_classes list of ECs that mention this rel
 	 */
 	Bitmapset  *eclass_indexes;
+
+	/*
+	 * Indexes in PlannerInfo's eq_members list of EMs that mention this rel
+	 */
+	Bitmapset  *eclass_member_indexes;
+
+	/*
+	 * Indexes in PlannerInfo's eq_sources list for RestrictInfos that mention
+	 * this relation.
+	 */
+	Bitmapset  *eclass_source_indexes;
+
+	/*
+	 * Indexes in PlannerInfo's eq_derives list for RestrictInfos that mention
+	 * this relation.
+	 */
+	Bitmapset  *eclass_derive_indexes;
+
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	/* wanted number of parallel workers */
@@ -1305,6 +1332,39 @@ typedef struct StatisticExtInfo
  * the included values might be all NULL rather than all the same non-null
  * values.  See src/backend/optimizer/README for more on that point.
  *
+ * 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.
  *
@@ -1322,9 +1382,19 @@ 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_sources;		/* list of generating RestrictInfos */
-	List	   *ec_derives;		/* list of derived RestrictInfos */
+	List	   *ec_members;		/* list of EquivalenceMembers in the class */
+	Bitmapset  *ec_member_indexes;	/* Indexes into all PlannerInfos
+									 * eq_members for this EquivalenceClass */
+	Bitmapset  *ec_nonchild_indexes;	/* Indexes into PlannerInfo's
+										 * eq_members with em_is_child ==
+										 * false */
+	Bitmapset  *ec_norel_indexes;	/* Indexes into PlannerInfo's eq_members
+									 * for members where pull_varno on the
+									 * em_expr is an empty set */
+	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? */
@@ -1373,9 +1443,10 @@ typedef struct EquivalenceMember
 	NodeTag		type;
 
 	Expr	   *em_expr;		/* the expression represented */
-	Relids		em_relids;		/* all relids appearing in em_expr */
+	Relids		em_relids;		/* relids for this member */
 	Relids		em_nullable_relids; /* nullable by lower outer joins */
-	bool		em_is_const;	/* expression is pseudoconstant? */
+	bool		em_is_const;	/* is em_relids empty? */
+	bool		em_norel_expr;	/* true if em_expr contains no Vars */
 	bool		em_is_child;	/* derived version for a child relation? */
 	Oid			em_datatype;	/* the "nominal type" used by the opfamily */
 } EquivalenceMember;
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 529a382d28..77f26edf22 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -629,6 +629,7 @@ extern pg_nodiscard List *list_copy_deep(const List *oldlist);
 typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
 extern void list_sort(List *list, list_sort_comparator cmp);
 
+extern int	list_ptr_cmp(const ListCell *p1, const ListCell *p2);
 extern int	list_int_cmp(const ListCell *p1, const ListCell *p2);
 extern int	list_oid_cmp(const ListCell *p1, const ListCell *p2);
 
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9b38627efd..4d2221c2d0 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -114,6 +114,31 @@ extern void mark_dummy_rel(RelOptInfo *rel);
  * equivclass.c
  *	  routines for managing EquivalenceClasses
  */
+
+/*
+ * EquivalenceMemberIterator
+ *		Data structure used for iteration over an EquivalenceClass's
+ *		EquivalenceMember in order to quickly find the members matching our
+ *		search pattern.
+ */
+typedef struct EquivalenceMemberIterator
+{
+	bool		use_index;		/* use matching_ems index? */
+	bool		relids_empty;	/* is with_relids empty? */
+	bool		with_children;	/* include em_is_child members? */
+	bool		with_norel_members; /* include members with empty em_relids */
+#ifdef USE_ASSERT_CHECKING
+	bool		isstrict;		/* ensure the correct next function is used */
+#endif
+	int			orig_length;	/* elements in eclass->ec_members at the start */
+	int			current_index;	/* current iterator position, or -1. */
+	Relids		with_relids;	/* relids to match in em_relids */
+	PlannerInfo *root;			/* PlannerInfo the eclass belongs to */
+	EquivalenceClass *eclass;	/* the EquivalenceClass we're looking at */
+	Bitmapset  *matching_ems;	/* when use_index == true, these are the
+								 * matching indexes in root eq_members */
+} EquivalenceMemberIterator;
+
 typedef bool (*ec_matches_callback_type) (PlannerInfo *root,
 										  RelOptInfo *rel,
 										  EquivalenceClass *ec,
@@ -135,7 +160,8 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 												  Index sortref,
 												  Relids rel,
 												  bool create_it);
-extern EquivalenceMember *find_ec_member_matching_expr(EquivalenceClass *ec,
+extern EquivalenceMember *find_ec_member_matching_expr(PlannerInfo *root,
+													   EquivalenceClass *ec,
 													   Expr *expr,
 													   Relids relids);
 extern EquivalenceMember *find_computable_ec_member(PlannerInfo *root,
@@ -160,7 +186,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,
@@ -186,6 +213,42 @@ 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_ecmember_indexes(PlannerInfo *root,
+									   EquivalenceClass *ec,
+									   Relids relids,
+									   bool with_children,
+									   bool with_norel_members);
+extern Bitmapset *get_ecmember_indexes_strict(PlannerInfo *root,
+											  EquivalenceClass *ec,
+											  Relids relids,
+											  bool with_children,
+											  bool with_norel_members);
+extern void setup_eclass_member_iterator(EquivalenceMemberIterator *iter,
+										 PlannerInfo *root,
+										 EquivalenceClass *ec, Relids relids,
+										 bool with_children,
+										 bool with_norel_members);
+extern void setup_eclass_member_strict_iterator(EquivalenceMemberIterator *iter,
+												PlannerInfo *root,
+												EquivalenceClass *ec,
+												Relids relids,
+												bool with_children,
+												bool with_norel_members);
+extern EquivalenceMember *eclass_member_iterator_next(EquivalenceMemberIterator *iter);
+extern EquivalenceMember *eclass_member_iterator_strict_next(EquivalenceMemberIterator *iter);
+extern void eclass_member_iterator_dispose(EquivalenceMemberIterator *iter);
+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
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 51484ca7e2..2e9c6c530f 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -641,6 +641,7 @@ EphemeralNamedRelationMetadata
 EphemeralNamedRelationMetadataData
 EquivalenceClass
 EquivalenceMember
+EquivalenceMemberIterator
 ErrorContextCallback
 ErrorData
 ErrorSaveContext
-- 
2.39.0.windows.1

---

From: Yuya Watari <[email-masked]>
Date: Mon, 6 Feb 2023 10:47:33 +0900

Dear David,

On Mon, Jan 30, 2023 at 9:14 PM David Rowley <[email-masked]> wrote:
> I've attached what I worked on today.

I really appreciate your quick response and the v15 patches. The bug
fixes in the v15 look good to me.

After receiving your email, I realized that this version does not
apply to the current master. This conflict is caused by commits of
2489d76c49 [1] and related. I have attached the rebased version, v16,
to this email. Resolving many conflicts was a bit of hard work, so I
may have made some mistakes.

Unfortunately, the rebased version did not pass regression tests. This
failure is due to segmentation faults regarding a null reference to
RelOptInfo. I show the code snippet that leads to the segfault as
follows.

=====
@@ -572,9 +662,31 @@ add_eq_member(EquivalenceClass *ec, Expr *expr,
Relids relids,
+    i = -1;
+    while ((i = bms_next_member(expr_relids, i)) >= 0)
+    {
+        RelOptInfo *rel = root->simple_rel_array[i];
+
+        rel->eclass_member_indexes =
bms_add_member(rel->eclass_member_indexes, em_index);
+    }
=====

The segfault occurred because root->simple_rel_array[i] is sometimes
NULL. This issue is similar to the one regarding
root->simple_rel_array[0]. Before the commit of 2489d76c49, we only
had to consider the nullability of root->simple_rel_array[0]. We
overcame this problem by creating the RelOptInfo in the
setup_append_rel_entry() function. However, after the commit,
root->simple_rel_array[i] with non-zero 'i' can also be NULL. I'm not
confident with its cause, but is this because non-base relations
appear in the expr_relids? Seeing the commit, I found the following
change in pull_varnos_walker():

=====
@@ -153,7 +161,11 @@ pull_varnos_walker(Node *node,
pull_varnos_context *context)
        Var        *var = (Var *) node;

        if (var->varlevelsup == context->sublevels_up)
+       {
            context->varnos = bms_add_member(context->varnos, var->varno);
+           context->varnos = bms_add_members(context->varnos,
+                                             var->varnullingrels);
+       }
        return false;
    }
    if (IsA(node, CurrentOfExpr))
=====

We get the expr_relids by pull_varnos(). This commit adds
var->varnullingrels to its result. From my observations, indices 'i'
such that root->simple_rel_array[i] is null come from
var->varnullingrels. This change is probably related to the segfault.
I don't understand the commit well, so please let me know if I'm
wrong.

To address this problem, in v16-0003, I moved EquivalenceMember
indexes in RelOptInfo to PlannerInfo. This change allows us to store
indexes whose corresponding RelOptInfo is NULL.

> I'm happier

Of course, I'm not sure if my approach in v16-0003 is ideal, but it
may help solve your concern above. Since simple_rel_array[0] is no
longer necessary with my patch, I removed the setup_append_rel_entry()
function in v16-0004. However, to work the patch, I needed to change
some assertions in v16-0005. For more details, please see the commit
message of v16-0005. After these works, the attached patches passed
all regression tests in my environment.

Instead of my approach, imitating the following change to
get_eclass_indexes_for_relids() is also a possible solution. Ignoring
NULL RelOptInfos enables us to avoid the segfault, but we have to
adjust EquivalenceMemberIterator to match the result, and I'm not sure
if this idea is correct.

=====
@@ -3204,6 +3268,12 @@ get_eclass_indexes_for_relids(PlannerInfo
*root, Relids relids)
    {
        RelOptInfo *rel = root->simple_rel_array[i];

+       if (rel == NULL)        /* must be an outer join */
+       {
+           Assert(bms_is_member(i, root->outer_join_rels));
+           continue;
+       }
+
        ec_indexes = bms_add_members(ec_indexes, rel->eclass_indexes);
    }
    return ec_indexes;
=====

[1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=2489d76c4906f4461a364ca8ad7e0751ead8aa0d

-- 
Best regards,
Yuya Watari

---

From: Andrey Lepikhov <[email-masked]>
Date: Tue, 14 Feb 2023 15:01:41 +0500

> adjust EquivalenceMemberIterator to match the result, and I'm not sure
As I see, You moved the indexes from RelOptInfo to PlannerInfo. May be 
better to move them into RangeTblEntry instead?

-- 
Regards
Andrey Lepikhov
Postgres Professional