v36-0002-Speed-up-searches-for-child-EquivalenceMembers.patch

From 91280a30af4f4b8fe98d21c669306176048c8cd0 Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Fri, 25 Aug 2023 10:43:36 +0900
Subject: [PATCH v36 2/2] Speed up searches for child EquivalenceMembers

Traditionally, child EquivalenceMembers were in the
EquivalenceClass->ec_members. When we wanted to find some child members
matching a request, we had to perform a linear search. This search
became heavy when tables had many partitions, leading to much planning
time.

After this commit, child EquivalenceMembers no longer exist in
ec_members. Instead, RelOptInfos have them. This change demonstrates a
significant performance improvement in planning time.
---
 contrib/postgres_fdw/postgres_fdw.c     |  15 +-
 src/backend/nodes/outfuncs.c            |   1 +
 src/backend/optimizer/path/equivclass.c | 353 +++++++++++++++++-------
 src/backend/optimizer/path/indxpath.c   |  15 +-
 src/backend/optimizer/path/pathkeys.c   |   9 +-
 src/include/nodes/pathnodes.h           |  51 ++++
 src/include/optimizer/paths.h           |   6 +
 src/tools/pgindent/typedefs.list        |   1 +
 8 files changed, 340 insertions(+), 111 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index ac14c06c715..90c7a212379 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7847,14 +7847,13 @@ conversion_error_callback(void *arg)
 EquivalenceMember *
 find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 {
-	ListCell   *lc;
-
 	PgFdwRelationInfo *fpinfo = (PgFdwRelationInfo *) rel->fdw_private;
+	EquivalenceMemberIterator it;
+	EquivalenceMember *em;
 
-	foreach(lc, ec->ec_members)
+	setup_eclass_member_iterator(root, &it, ec, rel->relids);
+	while ((em = eclass_member_iterator_next(&it)) != NULL)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
-
 		/*
 		 * Note we require !bms_is_empty, else we'd accept constant
 		 * expressions which are not suitable for the purpose.
@@ -7865,6 +7864,7 @@ find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 			is_foreign_expr(root, rel, em->em_expr))
 			return em;
 	}
+	dispose_eclass_member_iterator(&it);
 
 	return NULL;
 }
@@ -7918,9 +7918,8 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 			if (em->em_is_const)
 				continue;
 
-			/* Ignore child members */
-			if (em->em_is_child)
-				continue;
+			/* Child members should not exist in ec_members */
+			Assert(!em->em_is_child);
 
 			/* Match if same expression (after stripping relabel) */
 			em_expr = em->em_expr;
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bb9bdd67192..306df44f293 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -466,6 +466,7 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
 	WRITE_NODE_FIELD(ec_opfamilies);
 	WRITE_OID_FIELD(ec_collation);
 	WRITE_NODE_FIELD(ec_members);
+	/* XXX ec_childmembers? */
 	WRITE_NODE_FIELD(ec_sources);
 	WRITE_NODE_FIELD(ec_derives);
 	WRITE_BITMAPSET_FIELD(ec_relids);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 7fe7cdff468..9d36194fccf 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -33,11 +33,23 @@
 #include "utils/lsyscache.h"
 
 
+static EquivalenceMember *make_eq_member(EquivalenceClass *ec,
+										 Expr *expr, Relids relids,
+										 JoinDomain *jdomain,
+										 EquivalenceMember *parent,
+										 Oid datatype);
 static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
 										Expr *expr, Relids relids,
 										JoinDomain *jdomain,
-										EquivalenceMember *parent,
 										Oid datatype);
+static EquivalenceMember *add_child_eq_member(PlannerInfo *root,
+											  EquivalenceClass *ec,
+											  int ec_index, Expr *expr,
+											  Relids relids,
+											  JoinDomain *jdomain,
+											  EquivalenceMember *parent_em,
+											  Oid datatype,
+											  Relids child_relids);
 static void generate_base_implied_equalities_const(PlannerInfo *root,
 												   EquivalenceClass *ec);
 static void generate_base_implied_equalities_no_const(PlannerInfo *root,
@@ -268,7 +280,8 @@ process_equivalence(PlannerInfo *root,
 		{
 			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 
-			Assert(!cur_em->em_is_child);	/* no children yet */
+			/* Child members should not exist in ec_members */
+			Assert(!cur_em->em_is_child);
 
 			/*
 			 * Match constants only within the same JoinDomain (see
@@ -373,7 +386,7 @@ process_equivalence(PlannerInfo *root,
 	{
 		/* Case 3: add item2 to ec1 */
 		em2 = add_eq_member(ec1, item2, item2_relids,
-							jdomain, NULL, item2_type);
+							jdomain, item2_type);
 		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 		ec1->ec_min_security = Min(ec1->ec_min_security,
 								   restrictinfo->security_level);
@@ -390,7 +403,7 @@ process_equivalence(PlannerInfo *root,
 	{
 		/* Case 3: add item1 to ec2 */
 		em1 = add_eq_member(ec2, item1, item1_relids,
-							jdomain, NULL, item1_type);
+							jdomain, item1_type);
 		ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
 		ec2->ec_min_security = Min(ec2->ec_min_security,
 								   restrictinfo->security_level);
@@ -422,9 +435,9 @@ process_equivalence(PlannerInfo *root,
 		ec->ec_max_security = restrictinfo->security_level;
 		ec->ec_merged = NULL;
 		em1 = add_eq_member(ec, item1, item1_relids,
-							jdomain, NULL, item1_type);
+							jdomain, item1_type);
 		em2 = add_eq_member(ec, item2, item2_relids,
-							jdomain, NULL, item2_type);
+							jdomain, item2_type);
 
 		root->eq_classes = lappend(root->eq_classes, ec);
 
@@ -510,11 +523,16 @@ canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
 }
 
 /*
- * add_eq_member - build a new EquivalenceMember and add it to an EC
+ * make_eq_member
+ *
+ * Build a new EquivalenceMember without adding it to an EC. If 'parent'
+ * parameter is NULL, the result will be a parent member, otherwise a child
+ * member. Note that child EquivalenceMembers should not be added to its
+ * parent EquivalenceClass.
  */
 static EquivalenceMember *
-add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
-			  JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
+make_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
+			   JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
 {
 	EquivalenceMember *em = makeNode(EquivalenceMember);
 
@@ -541,11 +559,60 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 		ec->ec_has_const = true;
 		/* it can't affect ec_relids */
 	}
-	else if (!parent)			/* child members don't add to ec_relids */
+
+	return em;
+}
+
+/*
+ * add_eq_member - build a new non-child EquivalenceMember and add it to 'ec'.
+ */
+static EquivalenceMember *
+add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
+			  JoinDomain *jdomain, Oid datatype)
+{
+	EquivalenceMember *em = make_eq_member(ec, expr, relids, jdomain,
+										   NULL, datatype);
+
+	ec->ec_members = lappend(ec->ec_members, em);
+	ec->ec_relids = bms_add_members(ec->ec_relids, relids);
+	return em;
+}
+
+/*
+ * add_child_eq_member
+ *		Create an em_is_child=true EquivalenceMember and add it to 'ec'.
+ */
+static EquivalenceMember *
+add_child_eq_member(PlannerInfo *root, EquivalenceClass *ec, int ec_index,
+					Expr *expr, Relids relids, JoinDomain *jdomain,
+					EquivalenceMember *parent_em, Oid datatype,
+					Relids child_relids)
+{
+	EquivalenceMember *em;
+	int			relid;
+
+	Assert(parent_em != NULL);
+
+	if (ec->ec_childmembers == NULL)
+		ec->ec_childmembers = (List **) palloc0(root->simple_rel_array_size * sizeof(List *));
+
+	em = make_eq_member(ec, expr, relids, jdomain, parent_em, datatype);
+
+	relid = -1;
+	while ((relid = bms_next_member(child_relids, relid)) >= 0)
 	{
-		ec->ec_relids = bms_add_members(ec->ec_relids, relids);
+
+		ec->ec_childmembers[relid] = lappend(ec->ec_childmembers[relid], em);
+
+		/* Record this EC index for the child rel */
+		if (ec_index >= 0)
+		{
+			RelOptInfo *child_rel = root->simple_rel_array[relid];
+
+			child_rel->eclass_indexes =
+				bms_add_member(child_rel->eclass_indexes, ec_index);
+		}
 	}
-	ec->ec_members = lappend(ec->ec_members, em);
 
 	return em;
 }
@@ -616,7 +683,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		ListCell   *lc2;
+		EquivalenceMemberIterator it;
+		EquivalenceMember *cur_em;
 
 		/*
 		 * Never match to a volatile EC, except when we are looking at another
@@ -631,10 +699,9 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
 			continue;
 
-		foreach(lc2, cur_ec->ec_members)
+		setup_eclass_member_iterator(root, &it, cur_ec, rel);
+		while ((cur_em = eclass_member_iterator_next(&it)) != NULL)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
-
 			/*
 			 * Ignore child members unless they match the request.
 			 */
@@ -653,6 +720,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 				equal(expr, cur_em->em_expr))
 				return cur_ec;	/* Match! */
 		}
+		dispose_eclass_member_iterator(&it);
 	}
 
 	/* No match; does caller want a NULL result? */
@@ -690,7 +758,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	expr_relids = pull_varnos(root, (Node *) expr);
 
 	newem = add_eq_member(newec, copyObject(expr), expr_relids,
-						  jdomain, NULL, opcintype);
+						  jdomain, opcintype);
 
 	/*
 	 * add_eq_member doesn't check for volatile functions, set-returning
@@ -764,15 +832,16 @@ find_ec_member_matching_expr(PlannerInfo *root, EquivalenceClass *ec,
 							 Expr *expr,
 							 Relids relids)
 {
-	ListCell   *lc;
+	EquivalenceMemberIterator it;
+	EquivalenceMember *em;
 
 	/* We ignore binary-compatible relabeling on both ends */
 	while (expr && IsA(expr, RelabelType))
 		expr = ((RelabelType *) expr)->arg;
 
-	foreach(lc, ec->ec_members)
+	setup_eclass_member_iterator(root, &it, ec, relids);
+	while ((em = eclass_member_iterator_next(&it)) != NULL)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
 		Expr	   *emexpr;
 
 		/*
@@ -799,6 +868,7 @@ find_ec_member_matching_expr(PlannerInfo *root, EquivalenceClass *ec,
 		if (equal(emexpr, expr))
 			return em;
 	}
+	dispose_eclass_member_iterator(&it);
 
 	return NULL;
 }
@@ -841,7 +911,8 @@ find_computable_ec_member(PlannerInfo *root,
 						  bool require_parallel_safe)
 {
 	List	   *exprvars;
-	ListCell   *lc;
+	EquivalenceMemberIterator it;
+	EquivalenceMember *em;
 
 	/*
 	 * Pull out the Vars and quasi-Vars present in "exprs".  In the typical
@@ -855,9 +926,9 @@ find_computable_ec_member(PlannerInfo *root,
 							   PVC_INCLUDE_PLACEHOLDERS |
 							   PVC_INCLUDE_CONVERTROWTYPES);
 
-	foreach(lc, ec->ec_members)
+	setup_eclass_member_iterator(root, &it, ec, relids);
+	while ((em = eclass_member_iterator_next(&it)) != NULL)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
 		List	   *emvars;
 		ListCell   *lc2;
 
@@ -901,6 +972,7 @@ find_computable_ec_member(PlannerInfo *root,
 
 		return em;				/* found usable expression */
 	}
+	dispose_eclass_member_iterator(&it);
 
 	return NULL;
 }
@@ -1162,7 +1234,8 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 		Oid			eq_op;
 		RestrictInfo *rinfo;
 
-		Assert(!cur_em->em_is_child);	/* no children yet */
+		Assert(!cur_em->em_is_child);	/* Child members should not exist in
+										 * ec_members */
 		if (cur_em == const_em)
 			continue;
 		eq_op = select_equality_operator(ec,
@@ -1231,7 +1304,8 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 		int			relid;
 
-		Assert(!cur_em->em_is_child);	/* no children yet */
+		Assert(!cur_em->em_is_child);	/* Child members should not exist in
+										 * ec_members */
 		if (!bms_get_singleton_member(cur_em->em_relids, &relid))
 			continue;
 		Assert(relid < root->simple_rel_array_size);
@@ -1564,7 +1638,8 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 	List	   *new_members = NIL;
 	List	   *outer_members = NIL;
 	List	   *inner_members = NIL;
-	ListCell   *lc1;
+	EquivalenceMemberIterator it;
+	EquivalenceMember *cur_em;
 
 	/*
 	 * First, scan the EC to identify member values that are computable at the
@@ -1575,10 +1650,9 @@ 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)
+	setup_eclass_member_iterator(root, &it, ec, join_relids);
+	while ((cur_em = eclass_member_iterator_next(&it)) != NULL)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
-
 		/*
 		 * We don't need to check explicitly for child EC members.  This test
 		 * against join_relids will cause them to be ignored except when
@@ -1594,6 +1668,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 		else
 			new_members = lappend(new_members, cur_em);
 	}
+	dispose_eclass_member_iterator(&it);
 
 	/*
 	 * First, select the joinclause if needed.  We can equate any one outer
@@ -1611,6 +1686,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 		Oid			best_eq_op = InvalidOid;
 		int			best_score = -1;
 		RestrictInfo *rinfo;
+		ListCell   *lc1;
 
 		foreach(lc1, outer_members)
 		{
@@ -1685,6 +1761,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 		List	   *old_members = list_concat(outer_members, inner_members);
 		EquivalenceMember *prev_em = NULL;
 		RestrictInfo *rinfo;
+		ListCell   *lc1;
 
 		/* For now, arbitrarily take the first old_member as the one to use */
 		if (old_members)
@@ -1692,7 +1769,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)
 			{
@@ -2181,7 +2258,8 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
 		{
 			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 
-			Assert(!cur_em->em_is_child);	/* no children yet */
+			Assert(!cur_em->em_is_child);	/* Child members should not exist
+											 * in ec_members */
 			if (equal(outervar, cur_em->em_expr))
 			{
 				match = true;
@@ -2308,7 +2386,8 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
 		foreach(lc2, cur_ec->ec_members)
 		{
 			coal_em = (EquivalenceMember *) lfirst(lc2);
-			Assert(!coal_em->em_is_child);	/* no children yet */
+			Assert(!coal_em->em_is_child);	/* Child members should not exist
+											 * in ec_members */
 			if (IsA(coal_em->em_expr, CoalesceExpr))
 			{
 				CoalesceExpr *cexpr = (CoalesceExpr *) coal_em->em_expr;
@@ -2526,8 +2605,8 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2, Oid opfamily)
 		{
 			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
 
-			if (em->em_is_child)
-				continue;		/* ignore children here */
+			Assert(!em->em_is_child);	/* Child members should not exist in
+										 * ec_members */
 			if (equal(item1, em->em_expr))
 				item1member = true;
 			else if (equal(item2, em->em_expr))
@@ -2598,8 +2677,8 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
 			Var		   *var;
 
-			if (em->em_is_child)
-				continue;		/* ignore children here */
+			/* Child members should not exist in ec_members */
+			Assert(!em->em_is_child);
 
 			/* EM must be a Var, possibly with RelabelType */
 			var = (Var *) em->em_expr;
@@ -2696,6 +2775,7 @@ add_child_rel_equivalences(PlannerInfo *root,
 	Relids		top_parent_relids = child_rel->top_parent_relids;
 	Relids		child_relids = child_rel->relids;
 	int			i;
+	ListCell   *lc;
 
 	/*
 	 * EC merging should be complete already, so we can use the parent rel's
@@ -2708,7 +2788,6 @@ 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;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2721,29 +2800,15 @@ 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));
 
-		/*
-		 * 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.
-		 */
-		num_members = list_length(cur_ec->ec_members);
-		for (int pos = 0; pos < num_members; pos++)
+		foreach(lc, cur_ec->ec_members)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+			EquivalenceMember *cur_em = lfirst_node(EquivalenceMember, lc);
 
 			if (cur_em->em_is_const)
 				continue;		/* ignore consts here */
 
-			/*
-			 * 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.)
-			 */
-			if (cur_em->em_is_child)
-				continue;		/* ignore children here */
+			/* Child members should not exist in ec_members */
+			Assert(!cur_em->em_is_child);
 
 			/*
 			 * Consider only members that reference and can be computed at
@@ -2788,12 +2853,15 @@ add_child_rel_equivalences(PlannerInfo *root,
 											top_parent_relids);
 				new_relids = bms_add_members(new_relids, child_relids);
 
-				(void) add_eq_member(cur_ec, child_expr, new_relids,
-									 cur_em->em_jdomain,
-									 cur_em, cur_em->em_datatype);
-
-				/* Record this EC index for the child rel */
-				child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
+				add_child_eq_member(root,
+									cur_ec,
+									i,
+									child_expr,
+									new_relids,
+									cur_em->em_jdomain,
+									cur_em,
+									cur_em->em_datatype,
+									child_rel->relids);
 			}
 		}
 	}
@@ -2840,7 +2908,7 @@ 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;
+		ListCell   *lc;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2853,25 +2921,15 @@ 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));
 
-		/*
-		 * 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.
-		 */
-		num_members = list_length(cur_ec->ec_members);
-		for (int pos = 0; pos < num_members; pos++)
+		foreach(lc, cur_ec->ec_members)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
+			EquivalenceMember *cur_em = lfirst_node(EquivalenceMember, lc);
 
 			if (cur_em->em_is_const)
 				continue;		/* ignore consts here */
 
-			/*
-			 * We consider only original EC members here, not
-			 * already-transformed child members.
-			 */
-			if (cur_em->em_is_child)
-				continue;		/* ignore children here */
+			/* Child members should not exist in ec_members */
+			Assert(!cur_em->em_is_child);
 
 			/*
 			 * We may ignore expressions that reference a single baserel,
@@ -2916,9 +2974,15 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 											top_parent_relids);
 				new_relids = bms_add_members(new_relids, child_relids);
 
-				(void) add_eq_member(cur_ec, child_expr, new_relids,
-									 cur_em->em_jdomain,
-									 cur_em, cur_em->em_datatype);
+				add_child_eq_member(root,
+									cur_ec,
+									-1,
+									child_expr,
+									new_relids,
+									cur_em->em_jdomain,
+									cur_em,
+									cur_em->em_datatype,
+									child_joinrel->relids);
 			}
 		}
 	}
@@ -2965,14 +3029,18 @@ add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel,
 		 * We can safely pass the parent member as the first member in the
 		 * ec_members list as this is added first in generate_union_paths,
 		 * likewise, the JoinDomain can be that of the initial member of the
-		 * Pathkey's EquivalenceClass.
+		 * Pathkey's EquivalenceClass.  We pass -1 for ec_index since we
+		 * maintain the eclass_indexes for the child_rel after the loop.
 		 */
-		add_eq_member(pk->pk_eclass,
-					  tle->expr,
-					  child_rel->relids,
-					  parent_em->em_jdomain,
-					  parent_em,
-					  exprType((Node *) tle->expr));
+		add_child_eq_member(root,
+							pk->pk_eclass,
+							-1,
+							tle->expr,
+							child_rel->relids,
+							parent_em->em_jdomain,
+							parent_em,
+							exprType((Node *) tle->expr),
+							child_rel->relids);
 
 		lc2 = lnext(setop_pathkeys, lc2);
 	}
@@ -2987,6 +3055,103 @@ add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel,
 											  list_length(root->eq_classes) - 1);
 }
 
+/*
+ * setup_eclass_member_iterator
+ *	  Setup an EquivalenceMemberIterator 'it' to iterate over all parent
+ *	  EquivalenceMembers and child members associated with the given 'ec' that
+ *	  are relevant to the specified 'relids'.
+ *
+ * This iterator returns:
+ *	- All parent members stored directly in ec->ec_members.
+ *	- The child members whose em_relids is a subset of the given 'relids'.
+ *
+ * Note:
+ *	- The iterator may return false positives, i.e., child members whose
+ *	  em_relids is not a subset. So the caller must check that they satisfy
+ *	  the desired condition.
+ *	- Once used, the caller should dispose of the iterator by calling
+ *	  dispose_eclass_member_iterator().
+ *	- The given 'relids' must remain allocated and not be changed for the
+ *	  lifetime of the iterator.
+ *
+ * Parameters:
+ *	root - The PlannerInfo context.
+ *	it - A pointer to the iterator to set up.
+ *	ec - The EquivalenceClass from which to iterate members.
+ *	relids - The Relids used to filter for relevant child members.
+ */
+void
+setup_eclass_member_iterator(PlannerInfo *root, EquivalenceMemberIterator *it,
+							 EquivalenceClass *ec, Relids relids)
+{
+	it->root = root;
+	it->ec = ec;
+	it->relids = ec->ec_childmembers ? relids : NULL;
+	it->current_relid = -1;
+	it->current_list = ec->ec_members;
+	it->current_cell = list_head(it->current_list);
+}
+
+/*
+ * eclass_member_iterator_next
+ *	  Get a next EquivalenceMember from an EquivalenceMemberIterator 'it'
+ *	  that was setup by setup_eclass_member_iterator(). NULL is
+ *	  returned if there are no members left, in which case callers must not
+ *	  call eclass_member_iterator_next() again for the given iterator.
+ */
+EquivalenceMember *
+eclass_member_iterator_next(EquivalenceMemberIterator *it)
+{
+	EquivalenceMember *em = NULL;
+
+	while (it->current_list != NULL)
+	{
+nextcell:
+		while (it->current_cell != NULL)
+		{
+			em = lfirst_node(EquivalenceMember, it->current_cell);
+			it->current_cell = lnext(it->current_list, it->current_cell);
+			goto end;
+		}
+
+		/* Search for the next list to return members from */
+		while ((it->current_relid = bms_next_member(it->relids, it->current_relid)) > 0)
+		{
+			it->current_list = it->ec->ec_childmembers[it->current_relid];
+
+			/*
+			 * If there are members in this list, use it, this will exclude
+			 * RELOPT_BASERELs as ec_childmembers[] are not populated for
+			 * those.
+			 */
+			if (it->current_list != NIL)
+			{
+				/* point current_cell to the head of this list */
+				it->current_cell = list_head(it->current_list);
+				goto nextcell;
+			}
+		}
+
+		/*
+		 * XXX because we don't NULLify current_list here, the iterator is not
+		 * safe to call again after it returns NULL.  Is that worth doing?
+		 */
+		goto end;
+	}
+
+end:
+	return em;
+}
+
+/*
+ * dispose_eclass_member_iterator
+ *	  Free any memory allocated by the iterator.
+ */
+void
+dispose_eclass_member_iterator(EquivalenceMemberIterator *it)
+{
+}
+
 
 /*
  * generate_implied_equalities_for_column
@@ -3041,6 +3206,7 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		EquivalenceMember *cur_em;
 		ListCell   *lc2;
+		EquivalenceMemberIterator it;
 
 		/* Sanity check eclass_indexes only contain ECs for rel */
 		Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
@@ -3062,15 +3228,14 @@ 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(root, &it, cur_ec, rel->relids);
+		while ((cur_em = eclass_member_iterator_next(&it)) != 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;
 		}
+		dispose_eclass_member_iterator(&it);
 
 		if (!cur_em)
 			continue;
@@ -3085,8 +3250,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 			Oid			eq_op;
 			RestrictInfo *rinfo;
 
-			if (other_em->em_is_child)
-				continue;		/* ignore children here */
+			/* Child members should not exist in ec_members */
+			Assert(!other_em->em_is_child);
 
 			/* Make sure it'll be a join to a different rel */
 			if (other_em == cur_em ||
@@ -3304,8 +3469,8 @@ eclass_useful_for_merging(PlannerInfo *root,
 	{
 		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 
-		if (cur_em->em_is_child)
-			continue;			/* ignore children here */
+		/* Child members should not exist in ec_members */
+		Assert(!cur_em->em_is_child);
 
 		if (!bms_overlap(cur_em->em_relids, relids))
 			return true;
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 6386ce82253..275695b07c0 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -190,7 +190,7 @@ 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,
+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,
@@ -934,7 +934,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
 		 * query_pathkeys will allow an incremental sort to be considered on
 		 * the index's partially sorted results.
 		 */
-		match_pathkeys_to_index(index, root->query_pathkeys,
+		match_pathkeys_to_index(root, index, root->query_pathkeys,
 								&orderbyclauses,
 								&orderbyclausecols);
 		if (list_length(root->query_pathkeys) == list_length(orderbyclauses))
@@ -3796,7 +3796,7 @@ expand_indexqual_rowcompare(PlannerInfo *root,
  * item in the given 'pathkeys' list.
  */
 static void
-match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
+match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index, List *pathkeys,
 						List **orderby_clauses_p,
 						List **clause_columns_p)
 {
@@ -3813,7 +3813,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 	{
 		PathKey    *pathkey = (PathKey *) lfirst(lc1);
 		bool		found = false;
-		ListCell   *lc2;
+		EquivalenceMemberIterator it;
+		EquivalenceMember *member;
 
 
 		/* Pathkey must request default sort order for the target opfamily */
@@ -3833,9 +3834,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)
+		setup_eclass_member_iterator(root, &it, pathkey->pk_eclass,
+									 index->rel->relids);
+		while ((member = eclass_member_iterator_next(&it)) != NULL)
 		{
-			EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
 			int			indexcol;
 
 			/* No possibility of match if it references other relations */
@@ -3870,6 +3872,7 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 			if (found)			/* don't want to look at remaining members */
 				break;
 		}
+		dispose_eclass_member_iterator(&it);
 
 		/*
 		 * Return the matches found so far when this pathkey couldn't be
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 154eb505d75..a9419d37e2f 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1151,8 +1151,8 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 				Oid			sub_expr_coll = sub_eclass->ec_collation;
 				ListCell   *k;
 
-				if (sub_member->em_is_child)
-					continue;	/* ignore children here */
+				/* Child members should not exist in ec_members */
+				Assert(!sub_member->em_is_child);
 
 				foreach(k, subquery_tlist)
 				{
@@ -1709,8 +1709,11 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 		{
 			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
 
+			/* Child members should not exist in ec_members */
+			Assert(!em->em_is_child);
+
 			/* Potential future join partner? */
-			if (!em->em_is_const && !em->em_is_child &&
+			if (!em->em_is_const &&
 				!bms_overlap(em->em_relids, joinrel->relids))
 				score++;
 		}
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index ac3af528bc6..34b2510741b 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1402,6 +1402,12 @@ typedef struct JoinDomain
  * entry: consider SELECT random() AS a, random() AS b ... ORDER BY b,a.
  * So we record the SortGroupRef of the originating sort clause.
  *
+ * 'ec_members' is a List of all EquivalenceMembers belonging to
+ * RELOPT_BASERELs.  EquivalenceMembers for any RELOPT_OTHER_MEMBER_REL and
+ * RELOPT_OTHER_JOINREL relations are stored in the 'ec_childmembers' array in
+ * the index corresponding to the relid.  'ec_childmembers' may be NULL if the
+ * class has no child EquivalenceMembers.
+ *
  * 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.
  *
@@ -1420,6 +1426,8 @@ 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_childmembers;	/* array of Lists of child
+									 * EquivalenceMembers */
 	List	   *ec_sources;		/* list of generating RestrictInfos */
 	List	   *ec_derives;		/* list of derived RestrictInfos */
 	Relids		ec_relids;		/* all relids appearing in ec_members, except
@@ -1478,6 +1486,49 @@ typedef struct EquivalenceMember
 	struct EquivalenceMember *em_parent pg_node_attr(read_write_ignore);
 } EquivalenceMember;
 
+/*
+ * EquivalenceMemberIterator
+ *
+ * EquivalenceMemberIterator is designed to iterate over all parent
+ * EquivalenceMembers and child members associated with the given 'ec' that
+ * are relevant to the specified 'relids'. In particular, it iterates over:
+ *	- All parent members stored directly in ec->ec_members.
+ *	- The child members whose em_relids is a subset of the given 'relids'.
+ *
+ * Note:
+ *	- The iterator may return false positives, i.e., child members whose
+ *	  em_relids is not a subset. So the caller must check that they satisfy
+ *	  the desired condition.
+ *
+ * The most common way to use this iterator is as follows:
+ * -----
+ * PlannerInfo					   *root = given;
+ * EquivalenceMemberIterator		it;
+ * EquivalenceClass				   *ec = given;
+ * Relids							relids = given;
+ * EquivalenceMember			   *em;
+ *
+ * setup_eclass_member_iterator(root, &it, ec, relids);
+ * while ((em = eclass_member_iterator_next(&it)) != NULL)
+ * {
+ *     use em ...;
+ * }
+ * dispose_eclass_member_iterator(&it);
+ * -----
+ */
+typedef struct
+{
+	PlannerInfo *root;			/* The PlannerInfo where 'ec' belongs */
+	EquivalenceClass *ec;		/* The EquivalenceClass to iterate over */
+	int			current_relid;	/* Current relid position within 'relids'. -1
+								 * when still looping over ec_members and -2
+								 * at the end of iteration */
+	Relids		relids;			/* Relids of child relations of interest.
+								 * Non-child rels are ignored */
+	ListCell   *current_cell;	/* Next cell to return within current_list */
+	List	   *current_list;	/* Current list of members being returned */
+} EquivalenceMemberIterator;
+
 /*
  * PathKeys
  *
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 84a000a3ef1..82e51fef742 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -183,6 +183,12 @@ extern void add_setop_child_rel_equivalences(PlannerInfo *root,
 											 RelOptInfo *child_rel,
 											 List *child_tlist,
 											 List *setop_pathkeys);
+extern void setup_eclass_member_iterator(PlannerInfo *root,
+										 EquivalenceMemberIterator *it,
+										 EquivalenceClass *ec,
+										 Relids relids);
+extern EquivalenceMember *eclass_member_iterator_next(EquivalenceMemberIterator *it);
+extern void dispose_eclass_member_iterator(EquivalenceMemberIterator *it);
 extern List *generate_implied_equalities_for_column(PlannerInfo *root,
 													RelOptInfo *rel,
 													ec_matches_callback_type callback,
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 8f28d8ff28e..ba964a0d17d 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -709,6 +709,7 @@ EphemeralNamedRelationMetadata
 EphemeralNamedRelationMetadataData
 EquivalenceClass
 EquivalenceMember
+EquivalenceMemberIterator
 ErrorContextCallback
 ErrorData
 ErrorSaveContext
-- 
2.43.0