eclass_member_speedup.patch

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index 048db542d3..0af3943e03 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7410,11 +7410,11 @@ conversion_error_callback(void *arg)
 EquivalenceMember *
 find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 {
-	ListCell   *lc;
+	int		i = -1;
 
-	foreach(lc, ec->ec_members)
+	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 		/*
 		 * Note we require !bms_is_empty, else we'd accept constant
@@ -7453,7 +7453,7 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 	{
 		Expr	   *expr = (Expr *) lfirst(lc1);
 		Index		sgref = get_pathtarget_sortgroupref(target, i);
-		ListCell   *lc2;
+		int			i;
 
 		/* Ignore non-sort expressions */
 		if (sgref == 0 ||
@@ -7469,9 +7469,10 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 			expr = ((RelabelType *) expr)->arg;
 
 		/* Locate an EquivalenceClass member matching this expr, if any */
-		foreach(lc2, ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 			Expr	   *em_expr;
 
 			/* Don't match constants */
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index a96f2ee8c6..2060b73686 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -430,7 +430,7 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
 
 	WRITE_NODE_FIELD(ec_opfamilies);
 	WRITE_OID_FIELD(ec_collation);
-	WRITE_NODE_FIELD(ec_members);
+	WRITE_BITMAPSET_FIELD(ec_member_indexes);
 	WRITE_NODE_FIELD(ec_sources);
 	WRITE_NODE_FIELD(ec_derives);
 	WRITE_BITMAPSET_FIELD(ec_relids);
diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c
index a5c44adc6c..5953b79fe8 100644
--- a/src/backend/nodes/print.c
+++ b/src/backend/nodes/print.c
@@ -423,16 +423,17 @@ print_expr(const Node *expr, const List *rtable)
  *	  pathkeys list of PathKeys
  */
 void
-print_pathkeys(const List *pathkeys, const List *rtable)
+print_pathkeys(const PlannerInfo *root, const List *pathkeys,
+			   const List *rtable)
 {
-	const ListCell *i;
+	const ListCell *lc;
 
 	printf("(");
-	foreach(i, pathkeys)
+	foreach(lc, pathkeys)
 	{
-		PathKey    *pathkey = (PathKey *) lfirst(i);
+		PathKey    *pathkey = (PathKey *) lfirst(lc);
 		EquivalenceClass *eclass;
-		ListCell   *k;
+		int			i;
 		bool		first = true;
 
 		eclass = pathkey->pk_eclass;
@@ -441,9 +442,10 @@ print_pathkeys(const List *pathkeys, const List *rtable)
 			eclass = eclass->ec_merged;
 
 		printf("(");
-		foreach(k, eclass->ec_members)
+		i = -1;
+		while ((i = bms_next_member(eclass->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *mem = (EquivalenceMember *) lfirst(k);
+			EquivalenceMember *mem = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 			if (first)
 				first = false;
@@ -452,7 +454,7 @@ print_pathkeys(const List *pathkeys, const List *rtable)
 			print_expr((Node *) mem->em_expr, rtable);
 		}
 		printf(")");
-		if (lnext(pathkeys, i))
+		if (lnext(pathkeys, lc))
 			printf(", ");
 	}
 	printf(")\n");
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 63f0f6b79c..caba68b839 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -4539,7 +4539,7 @@ print_path(PlannerInfo *root, Path *path, int indent)
 		for (i = 0; i < indent; i++)
 			printf("\t");
 		printf("  pathkeys: ");
-		print_pathkeys(path->pathkeys, root->parse->rtable);
+		print_pathkeys(root, path->pathkeys, root->parse->rtable);
 	}
 
 	if (join)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index fb28e6411a..1043b67aca 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1986,12 +1986,14 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 		double		nGroups,
 					correctedNGroups;
 		Cost		funcCost = 1.0;
+		int			first_em;
 
 		/*
 		 * We believe that equivalence members aren't very different, so, to
 		 * estimate cost we consider just the first member.
 		 */
-		em = (EquivalenceMember *) linitial(pathkey->pk_eclass->ec_members);
+		first_em = bms_next_member(pathkey->pk_eclass->ec_member_indexes, -1);
+		em = (EquivalenceMember *) list_nth(root->eq_members, first_em);
 
 		if (em->em_datatype != InvalidOid)
 		{
@@ -2326,8 +2328,9 @@ cost_incremental_sort(Path *path,
 	foreach(l, pathkeys)
 	{
 		PathKey    *key = (PathKey *) lfirst(l);
+		int			first_em = bms_next_member(key->pk_eclass->ec_member_indexes, -1);
 		EquivalenceMember *member = (EquivalenceMember *)
-		linitial(key->pk_eclass->ec_members);
+			list_nth(root->eq_members, first_em);
 
 		/*
 		 * Check if the expression contains Var with "varno 0" so that we
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 60c0e3f108..0e46c05287 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -32,7 +32,7 @@
 #include "utils/lsyscache.h"
 
 
-static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
+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);
@@ -139,6 +139,7 @@ process_equivalence(PlannerInfo *root,
 			   *em2;
 	ListCell   *lc1;
 	int			ec2_idx;
+	int			i;
 
 	/* Should not already be marked as having generated an eclass */
 	Assert(restrictinfo->left_ec == NULL);
@@ -265,7 +266,6 @@ process_equivalence(PlannerInfo *root,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		ListCell   *lc2;
 
 		/* Never match to a volatile EC */
 		if (cur_ec->ec_has_volatile)
@@ -286,9 +286,10 @@ process_equivalence(PlannerInfo *root,
 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
 			continue;
 
-		foreach(lc2, cur_ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 			Assert(!cur_em->em_is_child);	/* no children yet */
 
@@ -364,7 +365,7 @@ process_equivalence(PlannerInfo *root,
 		 * PathKeys.  We leave it behind with a link so that the merged EC can
 		 * be found.
 		 */
-		ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
+		ec1->ec_member_indexes = bms_add_members(ec1->ec_member_indexes, ec2->ec_member_indexes);
 		ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
 		ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
 		ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
@@ -378,7 +379,7 @@ process_equivalence(PlannerInfo *root,
 		ec2->ec_merged = ec1;
 		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_member_indexes = NULL;
 		ec2->ec_sources = NIL;
 		ec2->ec_derives = NIL;
 		ec2->ec_relids = NULL;
@@ -398,8 +399,8 @@ process_equivalence(PlannerInfo *root,
 	else if (ec1)
 	{
 		/* Case 3: add item2 to ec1 */
-		em2 = add_eq_member(ec1, item2, item2_relids, item2_nullable_relids,
-							false, item2_type);
+		em2 = add_eq_member(root, ec1, item2, item2_relids,
+							item2_nullable_relids, false, item2_type);
 		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 		ec1->ec_below_outer_join |= below_outer_join;
 		ec1->ec_min_security = Min(ec1->ec_min_security,
@@ -416,8 +417,8 @@ process_equivalence(PlannerInfo *root,
 	else if (ec2)
 	{
 		/* Case 3: add item1 to ec2 */
-		em1 = add_eq_member(ec2, item1, item1_relids, item1_nullable_relids,
-							false, item1_type);
+		em1 = add_eq_member(root, ec2, item1, item1_relids,
+							item1_nullable_relids, false, item1_type);
 		ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
 		ec2->ec_below_outer_join |= below_outer_join;
 		ec2->ec_min_security = Min(ec2->ec_min_security,
@@ -438,7 +439,7 @@ process_equivalence(PlannerInfo *root,
 
 		ec->ec_opfamilies = opfamilies;
 		ec->ec_collation = collation;
-		ec->ec_members = NIL;
+		ec->ec_member_indexes = NULL;
 		ec->ec_sources = list_make1(restrictinfo);
 		ec->ec_derives = NIL;
 		ec->ec_relids = NULL;
@@ -450,10 +451,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);
 
@@ -542,10 +543,13 @@ canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
  * 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);
+	int					em_index;
+	int					i;
 
 	em->em_expr = expr;
 	em->em_relids = relids;
@@ -573,7 +577,17 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 	{
 		ec->ec_relids = bms_add_members(ec->ec_relids, relids);
 	}
-	ec->ec_members = lappend(ec->ec_members, em);
+	em_index = list_length(root->eq_members);
+	ec->ec_member_indexes = bms_add_member(ec->ec_member_indexes, em_index);
+	root->eq_members = lappend(root->eq_members, em);
+
+	i = -1;
+	while ((i = bms_next_member(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;
 }
@@ -645,7 +659,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		ListCell   *lc2;
+		int			i;
 
 		/*
 		 * Never match to a volatile EC, except when we are looking at another
@@ -660,9 +674,10 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
 			continue;
 
-		foreach(lc2, cur_ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 			/*
 			 * Ignore child members unless they match the request.
@@ -710,7 +725,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	newec = makeNode(EquivalenceClass);
 	newec->ec_opfamilies = list_copy(opfamilies);
 	newec->ec_collation = collation;
-	newec->ec_members = NIL;
+	newec->ec_member_indexes = NULL;
 	newec->ec_sources = NIL;
 	newec->ec_derives = NIL;
 	newec->ec_relids = NULL;
@@ -732,7 +747,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	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);
 
 	/*
@@ -794,19 +809,21 @@ 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;
+	int			i;
 
 	/* We ignore binary-compatible relabeling on both ends */
 	while (expr && IsA(expr, RelabelType))
 		expr = ((RelabelType *) expr)->arg;
 
-	foreach(lc, ec->ec_members)
+	i = -1;
+	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 		Expr	   *emexpr;
 
 		/*
@@ -865,11 +882,11 @@ find_computable_ec_member(PlannerInfo *root,
 						  Relids relids,
 						  bool require_parallel_safe)
 {
-	ListCell   *lc;
+	int		i = -1;
 
-	foreach(lc, ec->ec_members)
+	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 		List	   *exprvars;
 		ListCell   *lc2;
 
@@ -976,7 +993,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;
 
@@ -1096,7 +1113,7 @@ generate_base_implied_equalities(PlannerInfo *root)
 		 * Single-member ECs won't generate any deductions, either here or at
 		 * the join level.
 		 */
-		if (list_length(ec->ec_members) > 1)
+		if (bms_membership(ec->ec_member_indexes) == BMS_MULTIPLE)
 		{
 			if (ec->ec_has_const)
 				generate_base_implied_equalities_const(root, ec);
@@ -1145,7 +1162,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 									   EquivalenceClass *ec)
 {
 	EquivalenceMember *const_em = NULL;
-	ListCell   *lc;
+	int		i;
 
 	/*
 	 * In the trivial case where we just had one "var = const" clause, push
@@ -1154,7 +1171,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 	 * re-build and re-analyze an equality clause that will be exactly
 	 * equivalent to the old one.
 	 */
-	if (list_length(ec->ec_members) == 2 &&
+	if (bms_num_members(ec->ec_member_indexes) == 2 &&
 		list_length(ec->ec_sources) == 1)
 	{
 		RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
@@ -1172,9 +1189,10 @@ 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_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 		if (cur_em->em_is_const)
 		{
@@ -1186,9 +1204,10 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 	Assert(const_em != NULL);
 
 	/* Generate a derived equality against each other member */
-	foreach(lc, ec->ec_members)
+	i = -1;
+	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 		Oid			eq_op;
 		RestrictInfo *rinfo;
 
@@ -1240,7 +1259,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 										  EquivalenceClass *ec)
 {
 	EquivalenceMember **prev_ems;
-	ListCell   *lc;
+	int			i;
 
 	/*
 	 * We scan the EC members once and track the last-seen member for each
@@ -1253,9 +1272,10 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 	prev_ems = (EquivalenceMember **)
 		palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *));
 
-	foreach(lc, ec->ec_members)
+	i = -1;
+	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 		int			relid;
 
 		Assert(!cur_em->em_is_child);	/* no children yet */
@@ -1315,9 +1335,10 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 	 * pre-analysis of which members we prefer to join, but it's no worse than
 	 * what happened in the pre-8.3 code.
 	 */
-	foreach(lc, ec->ec_members)
+	i = -1;
+	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 		List	   *vars = pull_var_clause((Node *) cur_em->em_expr,
 										   PVC_RECURSE_AGGREGATES |
 										   PVC_RECURSE_WINDOWFUNCS |
@@ -1445,7 +1466,7 @@ generate_join_implied_equalities(PlannerInfo *root,
 			continue;
 
 		/* Single-member ECs won't generate any deductions */
-		if (list_length(ec->ec_members) <= 1)
+		if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
 			continue;
 
 		/* Sanity check that this eclass overlaps the join */
@@ -1516,7 +1537,7 @@ generate_join_implied_equalities_for_ecs(PlannerInfo *root,
 			continue;
 
 		/* Single-member ECs won't generate any deductions */
-		if (list_length(ec->ec_members) <= 1)
+		if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
 			continue;
 
 		/* We can quickly ignore any that don't overlap the join, too */
@@ -1560,6 +1581,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 	List	   *outer_members = NIL;
 	List	   *inner_members = NIL;
 	ListCell   *lc1;
+	int			i;
 
 	/*
 	 * First, scan the EC to identify member values that are computable at the
@@ -1570,9 +1592,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)
+	i = -1;
+	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+		EquivalenceMember *cur_em = (EquivalenceMember *)list_nth(root->eq_members, i);
 
 		/*
 		 * We don't need to check explicitly for child EC members.  This test
@@ -2104,7 +2127,7 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 		bool		match;
-		ListCell   *lc2;
+		int			i;
 
 		/* Ignore EC unless it contains pseudoconstants */
 		if (!cur_ec->ec_has_const)
@@ -2119,9 +2142,10 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 			continue;
 		/* Does it contain a match to outervar? */
 		match = false;
-		foreach(lc2, cur_ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 			Assert(!cur_em->em_is_child);	/* no children yet */
 			if (equal(outervar, cur_em->em_expr))
@@ -2139,9 +2163,10 @@ 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_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 			Oid			eq_op;
 			RestrictInfo *newrinfo;
 
@@ -2223,8 +2248,8 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		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,9 +2277,10 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		 * the COALESCE arguments?
 		 */
 		match = false;
-		foreach(lc2, cur_ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
 		{
-			coal_em = (EquivalenceMember *) lfirst(lc2);
+			coal_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 			Assert(!coal_em->em_is_child);	/* no children yet */
 			if (IsA(coal_em->em_expr, CoalesceExpr))
 			{
@@ -2269,7 +2295,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;
 				}
@@ -2285,9 +2311,10 @@ 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_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 			Oid			eq_op;
 			RestrictInfo *newrinfo;
 
@@ -2336,7 +2363,24 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		 */
 		if (matchleft && matchright)
 		{
-			cur_ec->ec_members = list_delete_nth_cell(cur_ec->ec_members, coal_idx);
+			cur_ec->ec_member_indexes = bms_del_member(cur_ec->ec_member_indexes, coal_idx);
+
+			/* Remove the member from each of the relations */
+			/* XXX check this is right. Is there a neater way? */
+			i = -1;
+			while ((i = bms_next_member(left_relids, i)) > 0)
+			{
+				RelOptInfo *rel = root->simple_rel_array[i];
+				rel->eclass_member_indexes = bms_del_member(rel->eclass_member_indexes, i);
+			}
+
+			i = -1;
+			while ((i = bms_next_member(right_relids, i)) > 0)
+			{
+				RelOptInfo *rel = root->simple_rel_array[i];
+				rel->eclass_member_indexes = bms_del_member(rel->eclass_member_indexes, i);
+			}
+
 			return true;
 		}
 
@@ -2374,15 +2418,16 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
 		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
 		bool		item1member = false;
 		bool		item2member = false;
-		ListCell   *lc2;
+		int			i;
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
 			continue;
 
-		foreach(lc2, ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 			if (em->em_is_child)
 				continue;		/* ignore children here */
@@ -2445,16 +2490,16 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 															 i);
 		EquivalenceMember *item1_em = NULL;
 		EquivalenceMember *item2_em = NULL;
-		ListCell   *lc2;
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
 			continue;
 		/* Note: it seems okay to match to "broken" eclasses here */
 
-		foreach(lc2, ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 			Var		   *var;
 
 			if (em->em_is_child)
@@ -2568,6 +2613,7 @@ add_child_rel_equivalences(PlannerInfo *root,
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		int			num_members;
+		int			j;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2580,15 +2626,20 @@ add_child_rel_equivalences(PlannerInfo *root,
 		/* Sanity check eclass_indexes only contain ECs for parent_rel */
 		Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
 
+		/* Only loop over existing members, not the newly added ones */
 		/*
-		 * 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.
+		 * XXX this is ugly. Is there a better way? bms_copy()?
+		 * Use bms_prev_member(..., -1) to get the final member first and
+		 * abort the loop when we go beyond that?
 		 */
-		num_members = list_length(cur_ec->ec_members);
+		num_members = bms_num_members(cur_ec->ec_member_indexes);
+		j = -1;
 		for (int pos = 0; pos < num_members; pos++)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+			EquivalenceMember *cur_em;
+
+			j = bms_next_member(cur_ec->ec_member_indexes, j);
+			cur_em = (EquivalenceMember *) list_nth(root->eq_members, j);
 
 			if (cur_em->em_is_const)
 				continue;		/* ignore consts here */
@@ -2653,7 +2704,7 @@ add_child_rel_equivalences(PlannerInfo *root,
 														  child_relids);
 				}
 
-				(void) add_eq_member(cur_ec, child_expr,
+				(void) add_eq_member(root, cur_ec, child_expr,
 									 new_relids, new_nullable_relids,
 									 true, cur_em->em_datatype);
 
@@ -2706,6 +2757,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		int			num_members;
+		int			j;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2718,15 +2770,20 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 		/* Sanity check on get_eclass_indexes_for_relids result */
 		Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
 
+		/* Only loop over existing members, not the newly added ones */
 		/*
-		 * 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.
+		 * XXX this is ugly. Is there a better way? bms_copy()?
+		 * Use bms_prev_member(..., -1) to get the final member first and
+		 * abort the loop when we go beyond that?
 		 */
-		num_members = list_length(cur_ec->ec_members);
+		num_members = bms_num_members(cur_ec->ec_member_indexes);
+		j = -1;
 		for (int pos = 0; pos < num_members; pos++)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+			EquivalenceMember *cur_em;
+
+			j = bms_next_member(cur_ec->ec_member_indexes, j);
+			cur_em = (EquivalenceMember *) list_nth(root->eq_members, j);
 
 			if (cur_em->em_is_const)
 				continue;		/* ignore consts here */
@@ -2794,7 +2851,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 													   child_relids,
 													   top_parent_relids);
 
-				(void) add_eq_member(cur_ec, child_expr,
+				(void) add_eq_member(root, cur_ec, child_expr,
 									 new_relids, new_nullable_relids,
 									 true, cur_em->em_datatype);
 			}
@@ -2857,7 +2914,6 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		EquivalenceMember *cur_em;
-		ListCell   *lc2;
 
 		/* Sanity check eclass_indexes only contain ECs for rel */
 		Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
@@ -2866,7 +2922,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		 * Won't generate joinclauses if const or single-member (the latter
 		 * test covers the volatile case too)
 		 */
-		if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
+		if (cur_ec->ec_has_const ||
+			bms_membership(cur_ec->ec_member_indexes) != BMS_MULTIPLE)
 			continue;
 
 		/*
@@ -2880,9 +2937,11 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		 * match.  See also get_eclass_for_sort_expr.)
 		 */
 		cur_em = NULL;
-		foreach(lc2, cur_ec->ec_members)
+		i = -1;
+		while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
 		{
-			cur_em = (EquivalenceMember *) lfirst(lc2);
+			cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
+
 			if (bms_equal(cur_em->em_relids, rel->relids) &&
 				callback(root, rel, cur_ec, cur_em, callback_arg))
 				break;
@@ -2896,9 +2955,10 @@ 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)
+		i = -1;
+		while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *other_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 			Oid			eq_op;
 			RestrictInfo *rinfo;
 
@@ -2986,7 +3046,7 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
 		 * Won't generate joinclauses if single-member (this test covers the
 		 * volatile case too)
 		 */
-		if (list_length(ec->ec_members) <= 1)
+		if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
 			continue;
 
 		/*
@@ -3044,7 +3104,7 @@ has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
 		 * Won't generate joinclauses if single-member (this test covers the
 		 * volatile case too)
 		 */
-		if (list_length(ec->ec_members) <= 1)
+		if (bms_membership(ec->ec_member_indexes) != BMS_MULTIPLE)
 			continue;
 
 		/*
@@ -3075,7 +3135,7 @@ eclass_useful_for_merging(PlannerInfo *root,
 						  RelOptInfo *rel)
 {
 	Relids		relids;
-	ListCell   *lc;
+	int			i;
 
 	Assert(!eclass->ec_merged);
 
@@ -3083,7 +3143,8 @@ eclass_useful_for_merging(PlannerInfo *root,
 	 * Won't generate joinclauses if const or single-member (the latter test
 	 * covers the volatile case too)
 	 */
-	if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
+	if (eclass->ec_has_const ||
+		bms_membership(eclass->ec_member_indexes) != BMS_MULTIPLE)
 		return false;
 
 	/*
@@ -3106,9 +3167,10 @@ 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_member_indexes, i)) >= 0)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 		if (cur_em->em_is_child)
 			continue;			/* ignore children here */
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 7d176e7b00..4c18ada572 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);
@@ -998,7 +998,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)
@@ -3073,8 +3073,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;
@@ -3092,7 +3092,7 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 	{
 		PathKey    *pathkey = (PathKey *) lfirst(lc1);
 		bool		found = false;
-		ListCell   *lc2;
+		int			i;
 
 		/*
 		 * Note: for any failure to match, we just return NIL immediately.
@@ -3116,9 +3116,10 @@ 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)
+		i = -1;
+		while ((i = bms_next_member(pathkey->pk_eclass->ec_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *member = (EquivalenceMember *) list_nth(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 b5d6c977ee..e3e87f162c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1396,9 +1396,11 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 				/* We can represent this sub_pathkey */
 				EquivalenceMember *sub_member;
 				EquivalenceClass *outer_ec;
+				int		first_em;
 
-				Assert(list_length(sub_eclass->ec_members) == 1);
-				sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
+				Assert(bms_membership(sub_eclass->ec_member_indexes) == BMS_SINGLETON);
+				first_em = bms_next_member(sub_eclass->ec_member_indexes, -1);
+				sub_member = (EquivalenceMember *) list_nth(rel->subroot->eq_members, first_em);
 
 				/*
 				 * Note: it might look funny to be setting sortref = 0 for a
@@ -1453,11 +1455,11 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 			 * outer query.
 			 */
 			int			best_score = -1;
-			ListCell   *j;
+			int			i = -1;
 
-			foreach(j, sub_eclass->ec_members)
+			while ((i = bms_next_member(sub_eclass->ec_member_indexes, i)) >= 0)
 			{
-				EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
+				EquivalenceMember *sub_member = (EquivalenceMember *) list_nth(rel->subroot->eq_members, i);
 				Expr	   *sub_expr = sub_member->em_expr;
 				Oid			sub_expr_type = sub_member->em_datatype;
 				Oid			sub_expr_coll = sub_eclass->ec_collation;
@@ -1516,7 +1518,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 													  sub_pathkey->pk_strategy,
 													  sub_pathkey->pk_nulls_first);
 					/* score = # of equivalence peers */
-					score = list_length(outer_ec->ec_members) - 1;
+					score = bms_num_members(outer_ec->ec_member_indexes) - 1;
 					/* +1 if it matches the proper query_pathkeys item */
 					if (retvallen < outer_query_keys &&
 						list_nth(root->query_pathkeys, retvallen) == outer_pk)
@@ -1926,7 +1928,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);
@@ -1947,9 +1949,10 @@ 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_member_indexes, i)) >= 0)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
 			/* Potential future join partner? */
 			if (!em->em_is_const && !em->em_is_child &&
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index e37f2933eb..b8aeb2e84a 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);
@@ -1261,7 +1264,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,
@@ -1305,7 +1309,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,
@@ -1446,7 +1450,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,
@@ -1477,7 +1481,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,
@@ -1964,7 +1968,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,
@@ -2183,7 +2187,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);
 
@@ -2207,7 +2211,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,
@@ -2276,7 +2280,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);
 
@@ -4478,7 +4482,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);
 
@@ -4492,7 +4496,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);
 
@@ -6116,7 +6120,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,
@@ -6157,6 +6162,8 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
 
 		if (ec->ec_has_volatile)
 		{
+			int		first_em;
+
 			/*
 			 * If the pathkey's EquivalenceClass is volatile, then it must
 			 * have come from an ORDER BY clause, and we have to match it to
@@ -6166,8 +6173,9 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
 				elog(ERROR, "volatile EquivalenceClass has no sortref");
 			tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
 			Assert(tle);
-			Assert(list_length(ec->ec_members) == 1);
-			pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
+			Assert(bms_membership(ec->ec_member_indexes) == BMS_SINGLETON);
+			first_em = bms_next_member(ec->ec_member_indexes, -1);
+			pk_datatype = ((EquivalenceMember *) list_nth(root->eq_members, first_em))->em_datatype;
 		}
 		else if (reqColIdx != NULL)
 		{
@@ -6183,7 +6191,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 */
@@ -6214,7 +6222,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 */
@@ -6230,7 +6238,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;
@@ -6301,7 +6309,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;
@@ -6310,7 +6319,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,
@@ -6336,7 +6347,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;
@@ -6346,7 +6358,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,
@@ -6696,7 +6710,7 @@ 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;
@@ -6737,6 +6751,8 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
 
 		if (ec->ec_has_volatile)
 		{
+			int first_em;
+
 			/*
 			 * If the pathkey's EquivalenceClass is volatile, then it must
 			 * have come from an ORDER BY clause, and we have to match it to
@@ -6746,8 +6762,9 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
 				elog(ERROR, "volatile EquivalenceClass has no sortref");
 			tle = get_sortgroupref_tle(ec->ec_sortref, plan->targetlist);
 			Assert(tle);
-			Assert(list_length(ec->ec_members) == 1);
-			pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
+			Assert(bms_membership(ec->ec_member_indexes) == BMS_SINGLETON);
+			first_em = bms_next_member(ec->ec_member_indexes, -1);
+			pk_datatype = ((EquivalenceMember *) list_nth(root->eq_members, first_em))->em_datatype;
 		}
 		else
 		{
@@ -6759,7 +6776,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/planner.c b/src/backend/optimizer/plan/planner.c
index 06ad856eac..4a5be95875 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -618,6 +618,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root->cte_plan_ids = NIL;
 	root->multiexpr_params = NIL;
 	root->eq_classes = NIL;
+	root->eq_members = 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 0bd99acf83..f3e6c19fc7 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -998,6 +998,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->cte_plan_ids = NIL;
 	subroot->multiexpr_params = NIL;
 	subroot->eq_classes = NIL;
+	subroot->eq_members = 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 043181b586..0ec3736e52 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -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;
 
 	/*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index e2081db4ed..1b2b1fcf22 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -300,6 +300,9 @@ struct PlannerInfo
 	/* list of active EquivalenceClasses */
 	List	   *eq_classes;
 
+	/* list of each EquivalenceMember */
+	List	   *eq_members;
+
 	/* set true once ECs are canonical */
 	bool		ec_merging_done;
 
@@ -874,6 +877,12 @@ 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 memtion this rel
+	 */
+	Bitmapset  *eclass_member_indexes;
+
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	/* wanted number of parallel workers */
@@ -1262,7 +1271,7 @@ typedef struct EquivalenceClass
 
 	List	   *ec_opfamilies;	/* btree operator family OIDs */
 	Oid			ec_collation;	/* collation, if datatypes are collatable */
-	List	   *ec_members;		/* list of EquivalenceMembers */
+	Bitmapset  *ec_member_indexes; /* Indexes into PlannerInfo's eq_members */
 	List	   *ec_sources;		/* list of generating RestrictInfos */
 	List	   *ec_derives;		/* list of derived RestrictInfos */
 	Relids		ec_relids;		/* all relids appearing in ec_members, except
diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h
index be5e2287f3..526723a187 100644
--- a/src/include/nodes/print.h
+++ b/src/include/nodes/print.h
@@ -16,6 +16,7 @@
 
 #include "executor/tuptable.h"
 
+struct PlannerInfo;
 
 #define nodeDisplay(x)		pprint(x)
 
@@ -27,7 +28,9 @@ extern char *format_node_dump(const char *dump);
 extern char *pretty_format_node_dump(const char *dump);
 extern void print_rt(const List *rtable);
 extern void print_expr(const Node *expr, const List *rtable);
-extern void print_pathkeys(const List *pathkeys, const List *rtable);
+extern void print_pathkeys(const struct PlannerInfo *root,
+						   const List *pathkeys,
+						   const List *rtable);
 extern void print_tl(const List *tlist, const List *rtable);
 extern void print_slot(TupleTableSlot *slot);
 
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 54ab709c67..ba75d52107 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -136,7 +136,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,