v22-0001-Speed-up-searches-for-child-EquivalenceMembers.patch

From 03b82c4f3964ead680b60cdc53905ae4cd8c3309 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 v22 1/4] 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       |  29 +-
 src/backend/nodes/outfuncs.c              |   2 +
 src/backend/optimizer/path/equivclass.c   | 414 ++++++++++++++++++----
 src/backend/optimizer/path/indxpath.c     |  40 ++-
 src/backend/optimizer/path/pathkeys.c     |   9 +-
 src/backend/optimizer/plan/analyzejoins.c |  14 +-
 src/backend/optimizer/plan/createplan.c   |  57 +--
 src/backend/optimizer/util/inherit.c      |  14 +
 src/backend/optimizer/util/relnode.c      |  88 +++++
 src/include/nodes/pathnodes.h             |  26 ++
 src/include/optimizer/pathnode.h          |  18 +
 src/include/optimizer/paths.h             |   9 +-
 12 files changed, 603 insertions(+), 117 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index e9144beb62..3c3b2cdb34 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7773,13 +7773,27 @@ conversion_error_callback(void *arg)
 EquivalenceMember *
 find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 {
-	ListCell   *lc;
-
 	PgFdwRelationInfo *fpinfo = (PgFdwRelationInfo *) rel->fdw_private;
+	Relids		top_parent_rel_relids;
+	List	   *members;
+	bool		modified;
+	int			i;
 
-	foreach(lc, ec->ec_members)
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	top_parent_rel_relids = find_relids_top_parents(root, rel->relids);
+
+	members = ec->ec_members;
+	modified = false;
+	for (i = 0; i < list_length(members); i++)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *em = list_nth_node(EquivalenceMember, members, i);
+
+		/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+		if (unlikely(top_parent_rel_relids != NULL) && !em->em_is_child &&
+			bms_is_subset(em->em_relids, top_parent_rel_relids))
+			add_child_rel_equivalences_to_list(root, ec, em,
+											   rel->relids,
+											   &members, &modified);
 
 		/*
 		 * Note we require !bms_is_empty, else we'd accept constant
@@ -7791,6 +7805,8 @@ find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 			is_foreign_expr(root, rel, em->em_expr))
 			return em;
 	}
+	if (unlikely(modified))
+		list_free(members);
 
 	return NULL;
 }
@@ -7844,9 +7860,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 e66a99247e..8318c71035 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -463,6 +463,8 @@ _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_norel_members);
+	WRITE_NODE_FIELD(ec_rel_members);
 	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 7fa502d6e2..7873548b25 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -33,10 +33,14 @@
 #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 bool is_exprlist_member(Expr *node, List *exprs);
 static void generate_base_implied_equalities_const(PlannerInfo *root,
@@ -69,6 +73,12 @@ static bool reconsider_outer_join_clause(PlannerInfo *root,
 static bool reconsider_full_join_clause(PlannerInfo *root,
 										OuterJoinClauseInfo *ojcinfo);
 static JoinDomain *find_join_domain(PlannerInfo *root, Relids relids);
+static void add_transformed_child_version(PlannerInfo *root,
+										  EquivalenceClass *ec,
+										  EquivalenceMember *parent_em,
+										  RelOptInfo *child_rel,
+										  List **list,
+										  bool *modified);
 static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root,
 												Relids relids);
 static Bitmapset *get_common_eclass_indexes(PlannerInfo *root, Relids relids1,
@@ -342,6 +352,10 @@ process_equivalence(PlannerInfo *root,
 		 * be found.
 		 */
 		ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
+		ec1->ec_norel_members = list_concat(ec1->ec_norel_members,
+											ec2->ec_norel_members);
+		ec1->ec_rel_members = list_concat(ec1->ec_rel_members,
+										  ec2->ec_rel_members);
 		ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
 		ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
 		ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
@@ -355,6 +369,8 @@ 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_norel_members = NIL;
+		ec2->ec_rel_members = NIL;
 		ec2->ec_sources = NIL;
 		ec2->ec_derives = NIL;
 		ec2->ec_relids = NULL;
@@ -374,7 +390,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);
@@ -391,7 +407,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);
@@ -412,6 +428,8 @@ process_equivalence(PlannerInfo *root,
 		ec->ec_opfamilies = opfamilies;
 		ec->ec_collation = collation;
 		ec->ec_members = NIL;
+		ec->ec_norel_members = NIL;
+		ec->ec_rel_members = NIL;
 		ec->ec_sources = list_make1(restrictinfo);
 		ec->ec_derives = NIL;
 		ec->ec_relids = NULL;
@@ -423,9 +441,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);
 
@@ -511,11 +529,14 @@ 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. 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);
 
@@ -526,6 +547,8 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 	em->em_datatype = datatype;
 	em->em_jdomain = jdomain;
 	em->em_parent = parent;
+	em->em_child_relids = NULL;
+	em->em_child_joinrel_relids = NULL;
 
 	if (bms_is_empty(relids))
 	{
@@ -546,8 +569,34 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 	{
 		ec->ec_relids = bms_add_members(ec->ec_relids, relids);
 	}
+
+	return em;
+}
+
+/*
+ * add_eq_member - build a new EquivalenceMember and add it to an 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);
 
+	/*
+	 * The exact set of relids in the expr for non-child EquivalenceMembers
+	 * as what is given to us in 'relids' should be the same as the relids
+	 * mentioned in the expression.  See add_child_rel_equivalences.
+	 */
+	/* XXX We need PlannerInfo to use the following assertion */
+	/* Assert(bms_equal(pull_varnos(root, (Node *) expr), relids)); */
+	if (bms_is_empty(relids))
+		ec->ec_norel_members = lappend(ec->ec_norel_members, em);
+	else
+		ec->ec_rel_members = lappend(ec->ec_rel_members, em);
+
 	return em;
 }
 
@@ -599,6 +648,17 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	EquivalenceMember *newem;
 	ListCell   *lc1;
 	MemoryContext oldcontext;
+	Relids		top_parent_rel;
+
+	/*
+	 * First, we translate the given Relids to their top-level parents. This is
+	 * required because an EquivalenceClass contains only parent
+	 * EquivalenceMembers, and we have to translate top-level ones to get child
+	 * members. We can skip such translations if we now see top-level ones,
+	 * i.e., when top_parent_rel is NULL. See the find_relids_top_parents()'s
+	 * definition for more details.
+	 */
+	top_parent_rel = find_relids_top_parents(root, rel);
 
 	/*
 	 * Ensure the expression exposes the correct type and collation.
@@ -617,7 +677,9 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		ListCell   *lc2;
+		List	   *members;
+		bool		modified;
+		int			i;
 
 		/*
 		 * Never match to a volatile EC, except when we are looking at another
@@ -632,16 +694,35 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
 			continue;
 
-		foreach(lc2, cur_ec->ec_members)
+		/*
+		 * When we have to see child EquivalenceMembers, we get and add them to
+		 * 'members'. We cannot use foreach() because the 'members' may be
+		 * modified during iteration.
+		 */
+		members = cur_ec->ec_members;
+		modified = false;
+		for (i = 0; i < list_length(members); i++)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember, members, i);
+
+			/*
+			 * If child EquivalenceMembers may match the request, we add and
+			 * iterate over them.
+			 */
+			if (unlikely(top_parent_rel != NULL) && !cur_em->em_is_child &&
+				bms_equal(cur_em->em_relids, top_parent_rel))
+				add_child_rel_equivalences_to_list(root, cur_ec, cur_em, rel,
+												   &members, &modified);
 
 			/*
 			 * Ignore child members unless they match the request.
 			 */
-			if (cur_em->em_is_child &&
-				!bms_equal(cur_em->em_relids, rel))
-				continue;
+			/*
+			 * If this EquivalenceMember is a child, i.e., translated above,
+			 * it should match the request. We cannot assert this if a request
+			 * is bms_is_subset().
+			 */
+			Assert(!cur_em->em_is_child || bms_equal(cur_em->em_relids, rel));
 
 			/*
 			 * Match constants only within the same JoinDomain (see
@@ -654,6 +735,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 				equal(expr, cur_em->em_expr))
 				return cur_ec;	/* Match! */
 		}
+		if (unlikely(modified))
+			list_free(members);
 	}
 
 	/* No match; does caller want a NULL result? */
@@ -671,6 +754,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	newec->ec_opfamilies = list_copy(opfamilies);
 	newec->ec_collation = collation;
 	newec->ec_members = NIL;
+	newec->ec_norel_members = NIL;
+	newec->ec_rel_members = NIL;
 	newec->ec_sources = NIL;
 	newec->ec_derives = NIL;
 	newec->ec_relids = NULL;
@@ -691,7 +776,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
@@ -757,19 +842,28 @@ 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;
+	Relids		top_parent_relids;
+	List	   *members;
+	bool		modified;
+	int			i;
+
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	top_parent_relids = find_relids_top_parents(root, relids);
 
 	/* We ignore binary-compatible relabeling on both ends */
 	while (expr && IsA(expr, RelabelType))
 		expr = ((RelabelType *) expr)->arg;
 
-	foreach(lc, ec->ec_members)
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	members = ec->ec_members;
+	modified = false;
+	for (i = 0; i < list_length(members); i++)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *em = list_nth_node(EquivalenceMember, members, i);
 		Expr	   *emexpr;
 
 		/*
@@ -779,6 +873,12 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
 		if (em->em_is_const)
 			continue;
 
+		/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+		if (unlikely(top_parent_relids != NULL) && !em->em_is_child &&
+			bms_is_subset(em->em_relids, top_parent_relids))
+			add_child_rel_equivalences_to_list(root, ec, em, relids,
+											   &members, &modified);
+
 		/*
 		 * Ignore child members unless they belong to the requested rel.
 		 */
@@ -796,6 +896,8 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
 		if (equal(emexpr, expr))
 			return em;
 	}
+	if (unlikely(modified))
+		list_free(members);
 
 	return NULL;
 }
@@ -828,11 +930,20 @@ find_computable_ec_member(PlannerInfo *root,
 						  Relids relids,
 						  bool require_parallel_safe)
 {
-	ListCell   *lc;
+	Relids		top_parent_relids;
+	List	   *members;
+	bool		modified;
+	int			i;
 
-	foreach(lc, ec->ec_members)
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	top_parent_relids = find_relids_top_parents(root, relids);
+
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	members = ec->ec_members;
+	modified = false;
+	for (i = 0; i < list_length(members); i++)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+		EquivalenceMember *em = list_nth_node(EquivalenceMember, members, i);
 		List	   *exprvars;
 		ListCell   *lc2;
 
@@ -843,6 +954,12 @@ find_computable_ec_member(PlannerInfo *root,
 		if (em->em_is_const)
 			continue;
 
+		/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+		if (unlikely(top_parent_relids != NULL) && !em->em_is_child &&
+			bms_is_subset(em->em_relids, top_parent_relids))
+			add_child_rel_equivalences_to_list(root, ec, em, relids,
+											   &members, &modified);
+
 		/*
 		 * Ignore child members unless they belong to the requested rel.
 		 */
@@ -876,6 +993,8 @@ find_computable_ec_member(PlannerInfo *root,
 
 		return em;				/* found usable expression */
 	}
+	if (unlikely(modified))
+		list_free(members);
 
 	return NULL;
 }
@@ -939,7 +1058,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;
 
@@ -1138,7 +1257,7 @@ 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)
+	foreach(lc, ec->ec_norel_members)
 	{
 		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 
@@ -1222,7 +1341,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 	prev_ems = (EquivalenceMember **)
 		palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *));
 
-	foreach(lc, ec->ec_members)
+	foreach(lc, ec->ec_rel_members)
 	{
 		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 		int			relid;
@@ -1559,7 +1678,13 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 	List	   *new_members = NIL;
 	List	   *outer_members = NIL;
 	List	   *inner_members = NIL;
-	ListCell   *lc1;
+	Relids		top_parent_join_relids;
+	List	   *members;
+	bool		modified;
+	int			i;
+
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	top_parent_join_relids = find_relids_top_parents(root, join_relids);
 
 	/*
 	 * First, scan the EC to identify member values that are computable at the
@@ -1570,9 +1695,19 @@ 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)
+
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	members = ec->ec_rel_members;
+	modified = false;
+	for (i = 0; i < list_length(members); i++)
 	{
-		EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+		EquivalenceMember *cur_em = list_nth_node(EquivalenceMember, members, i);
+
+		/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+		if (unlikely(top_parent_join_relids != NULL) && !cur_em->em_is_child &&
+			bms_is_subset(cur_em->em_relids, top_parent_join_relids))
+			add_child_rel_equivalences_to_list(root, ec, cur_em, join_relids,
+											   &members, &modified);
 
 		/*
 		 * We don't need to check explicitly for child EC members.  This test
@@ -1589,6 +1724,8 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 		else
 			new_members = lappend(new_members, cur_em);
 	}
+	if (unlikely(modified))
+		list_free(members);
 
 	/*
 	 * First, select the joinclause if needed.  We can equate any one outer
@@ -1606,6 +1743,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)
 		{
@@ -1680,6 +1818,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)
@@ -2177,7 +2316,7 @@ reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
 		 * constant before we can decide to throw away the outer-join clause.
 		 */
 		match = false;
-		foreach(lc2, cur_ec->ec_members)
+		foreach(lc2, cur_ec->ec_norel_members)
 		{
 			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 			Oid			eq_op;
@@ -2285,7 +2424,7 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
 		 * the COALESCE arguments?
 		 */
 		match = false;
-		foreach(lc2, cur_ec->ec_members)
+		foreach(lc2, cur_ec->ec_rel_members)
 		{
 			coal_em = (EquivalenceMember *) lfirst(lc2);
 			Assert(!coal_em->em_is_child);	/* no children yet */
@@ -2330,7 +2469,7 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
 		 * decide to throw away the outer-join clause.
 		 */
 		matchleft = matchright = false;
-		foreach(lc2, cur_ec->ec_members)
+		foreach(lc2, cur_ec->ec_norel_members)
 		{
 			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 			Oid			eq_op;
@@ -2385,6 +2524,10 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
 		if (matchleft && matchright)
 		{
 			cur_ec->ec_members = list_delete_nth_cell(cur_ec->ec_members, coal_idx);
+			Assert(!bms_is_empty(coal_em->em_relids));
+			/* XXX performance of list_delete_ptr()?? */
+			cur_ec->ec_rel_members = list_delete_ptr(cur_ec->ec_rel_members,
+													 coal_em);
 			return true;
 		}
 
@@ -2455,8 +2598,8 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
 		{
 			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
 
-			if (em->em_is_child)
-				continue;		/* ignore children here */
+			/* Child members should not exist in ec_members */
+			Assert(!em->em_is_child);
 			if (equal(item1, em->em_expr))
 				item1member = true;
 			else if (equal(item2, em->em_expr))
@@ -2523,13 +2666,13 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 			continue;
 		/* Note: it seems okay to match to "broken" eclasses here */
 
-		foreach(lc2, ec->ec_members)
+		foreach(lc2, ec->ec_rel_members)
 		{
 			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;
@@ -2626,6 +2769,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
@@ -2638,7 +2782,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
@@ -2651,15 +2794,9 @@ 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_rel_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 */
@@ -2672,8 +2809,8 @@ add_child_rel_equivalences(PlannerInfo *root,
 			 * 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
@@ -2689,6 +2826,7 @@ add_child_rel_equivalences(PlannerInfo *root,
 				/* OK, generate transformed child version */
 				Expr	   *child_expr;
 				Relids		new_relids;
+				EquivalenceMember *child_em;
 
 				if (parent_rel->reloptkind == RELOPT_BASEREL)
 				{
@@ -2718,9 +2856,20 @@ 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);
+				child_em = make_eq_member(cur_ec, child_expr, new_relids,
+										  cur_em->em_jdomain,
+										  cur_em, cur_em->em_datatype);
+				child_rel->eclass_child_members = lappend(child_rel->eclass_child_members,
+														  child_em);
+
+				/*
+				 * We save the knowledge that 'child_em' can be translated from
+				 * 'child_rel'. This knowledge is useful for
+				 * add_transformed_child_version() to find child members from the
+				 * given Relids.
+				 */
+				cur_em->em_child_relids = bms_add_member(cur_em->em_child_relids,
+													 child_rel->relid);
 
 				/* Record this EC index for the child rel */
 				child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
@@ -2749,6 +2898,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 	Relids		child_relids = child_joinrel->relids;
 	Bitmapset  *matching_ecs;
 	MemoryContext oldcontext;
+	ListCell   *lc;
 	int			i;
 
 	Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
@@ -2770,7 +2920,6 @@ 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;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2783,15 +2932,9 @@ 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_rel_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 */
@@ -2800,8 +2943,8 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 			 * 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,
@@ -2816,6 +2959,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 				/* Yes, generate transformed child version */
 				Expr	   *child_expr;
 				Relids		new_relids;
+				EquivalenceMember *child_em;
 
 				if (parent_joinrel->reloptkind == RELOPT_JOINREL)
 				{
@@ -2846,9 +2990,21 @@ 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);
+				child_em = make_eq_member(cur_ec, child_expr, new_relids,
+										  cur_em->em_jdomain,
+										  cur_em, cur_em->em_datatype);
+				child_joinrel->eclass_child_members =
+					lappend(child_joinrel->eclass_child_members, child_em);
+
+				/*
+				 * We save the knowledge that 'child_em' can be translated from
+				 * 'child_joinrel'. This knowledge is useful for
+				 * add_transformed_child_version() to find child members from the
+				 * given Relids.
+				 */
+				cur_em->em_child_joinrel_relids =
+					bms_add_member(cur_em->em_child_joinrel_relids,
+								   child_joinrel->join_rel_list_index);
 			}
 		}
 	}
@@ -2856,6 +3012,106 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 	MemoryContextSwitchTo(oldcontext);
 }
 
+/*
+ * add_transformed_child_version
+ *	  Add a transformed EquivalenceMember referencing the given child_rel to
+ *	  the list.
+ *
+ * This function is expected to be called only from
+ * add_child_rel_equivalences_to_list().
+ */
+static void
+add_transformed_child_version(PlannerInfo *root,
+							  EquivalenceClass *ec,
+							  EquivalenceMember *parent_em,
+							  RelOptInfo *child_rel,
+							  List **list,
+							  bool *modified)
+{
+	ListCell   *lc;
+
+	foreach(lc, child_rel->eclass_child_members)
+	{
+		EquivalenceMember *child_em = lfirst_node(EquivalenceMember, lc);
+
+		/* Skip unwanted EquivalenceMembers */
+		if (child_em->em_parent != parent_em)
+			continue;
+
+		/*
+		 * If this is the first time the given list has been modified, we need to
+		 * make a copy of it.
+		 */
+		if (!*modified)
+		{
+			*list = list_copy(*list);
+			*modified = true;
+		}
+
+		/* Add this child EquivalenceMember to the list */
+		*list = lappend(*list, child_em);
+	}
+}
+
+/*
+ * add_child_rel_equivalences_to_list
+ *	  Add transformed EquivalenceMembers referencing child rels in the given
+ *	  child_relids to the list.
+ *
+ * The transformation is done in add_transformed_child_version().
+ *
+ * This function will not change the original *list but will always make a copy
+ * of it when we need to add transformed members. *modified will be true if the
+ * *list is replaced with a newly allocated one. In such a case, the caller can
+ * (or must) free the *list.
+ */
+void
+add_child_rel_equivalences_to_list(PlannerInfo *root,
+								   EquivalenceClass *ec,
+								   EquivalenceMember *parent_em,
+								   Relids child_relids,
+								   List **list,
+								   bool *modified)
+{
+	int		i;
+	Relids	matching_relids;
+
+	/* The given EquivalenceMember should be parent */
+	Assert(!parent_em->em_is_child);
+
+	/*
+	 * First, we translate simple rels.
+	 */
+	matching_relids = bms_intersect(parent_em->em_child_relids,
+									child_relids);
+	i = -1;
+	while ((i = bms_next_member(matching_relids, i)) >= 0)
+	{
+		/* Add transformed child version for this child rel */
+		RelOptInfo *child_rel = root->simple_rel_array[i];
+
+		Assert(child_rel != NULL);
+		add_transformed_child_version(root, ec, parent_em, child_rel,
+									  list, modified);
+	}
+	bms_free(matching_relids);
+
+	/*
+	 * Next, we try to translate join rels.
+	 */
+	i = -1;
+	while ((i = bms_next_member(parent_em->em_child_joinrel_relids, i)) >= 0)
+	{
+		/* Add transformed child version for this child join rel */
+		RelOptInfo *child_joinrel =
+			list_nth_node(RelOptInfo, root->join_rel_list, i);
+
+		Assert(child_joinrel != NULL);
+		add_transformed_child_version(root, ec, parent_em, child_joinrel,
+									  list, modified);
+	}
+}
+
 
 /*
  * generate_implied_equalities_for_column
@@ -2889,7 +3145,7 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 {
 	List	   *result = NIL;
 	bool		is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
-	Relids		parent_relids;
+	Relids		parent_relids, top_parent_rel_relids;
 	int			i;
 
 	/* Should be OK to rely on eclass_indexes */
@@ -2898,6 +3154,9 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 	/* Indexes are available only on base or "other" member relations. */
 	Assert(IS_SIMPLE_REL(rel));
 
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	top_parent_rel_relids = find_relids_top_parents(root, rel->relids);
+
 	/* If it's a child rel, we'll need to know what its parent(s) are */
 	if (is_child_rel)
 		parent_relids = find_childrel_parents(root, rel);
@@ -2910,6 +3169,9 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		EquivalenceMember *cur_em;
 		ListCell   *lc2;
+		List	   *members;
+		bool		modified;
+		int			j;
 
 		/* Sanity check eclass_indexes only contain ECs for rel */
 		Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
@@ -2931,15 +3193,25 @@ 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.)
 		 */
+		/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+		members = cur_ec->ec_rel_members;
+		modified = false;
 		cur_em = NULL;
-		foreach(lc2, cur_ec->ec_members)
+		for (j = 0; j < list_length(members); j++)
 		{
-			cur_em = (EquivalenceMember *) lfirst(lc2);
+			cur_em = list_nth_node(EquivalenceMember, members, j);
+			/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+			if (unlikely(top_parent_rel_relids != NULL) && !cur_em->em_is_child &&
+				bms_equal(cur_em->em_relids, top_parent_rel_relids))
+				add_child_rel_equivalences_to_list(root, cur_ec, cur_em, rel->relids,
+												   &members, &modified);
 			if (bms_equal(cur_em->em_relids, rel->relids) &&
 				callback(root, rel, cur_ec, cur_em, callback_arg))
 				break;
 			cur_em = NULL;
 		}
+		if (unlikely(modified))
+			list_free(members);
 
 		if (!cur_em)
 			continue;
@@ -2954,8 +3226,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 ||
@@ -3173,8 +3445,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 03a5fbdc6d..9fa99e3292 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -184,7 +184,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,
@@ -980,7 +980,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))
@@ -3071,12 +3071,16 @@ 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)
 {
+	Relids		top_parent_index_relids;
 	ListCell   *lc1;
 
+	/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+	top_parent_index_relids = find_relids_top_parents(root, index->rel->relids);
+
 	*orderby_clauses_p = NIL;	/* set default results */
 	*clause_columns_p = NIL;
 
@@ -3088,7 +3092,9 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 	{
 		PathKey    *pathkey = (PathKey *) lfirst(lc1);
 		bool		found = false;
-		ListCell   *lc2;
+		List	   *members;
+		bool		modified;
+		int			i;
 
 
 		/* Pathkey must request default sort order for the target opfamily */
@@ -3108,15 +3114,33 @@ 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)
+		/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+		members = pathkey->pk_eclass->ec_members;
+		modified = false;
+		for (i = 0; i < list_length(members); i++)
 		{
-			EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *member = list_nth_node(EquivalenceMember, members, i);
 			int			indexcol;
 
+			/* See the comments in get_eclass_for_sort_expr() to see how this works. */
+			if (unlikely(top_parent_index_relids != NULL) && !member->em_is_child &&
+				bms_equal(member->em_relids, top_parent_index_relids))
+				add_child_rel_equivalences_to_list(root, pathkey->pk_eclass, member,
+												   index->rel->relids,
+												   &members, &modified);
+
 			/* No possibility of match if it references other relations */
-			if (!bms_equal(member->em_relids, index->rel->relids))
+			if (member->em_is_child ||
+				!bms_equal(member->em_relids, index->rel->relids))
 				continue;
 
+			/*
+			 * If this EquivalenceMember is a child, i.e., translated above,
+			 * it should match the request. We cannot assert this if a request
+			 * is bms_is_subset().
+			 */
+			Assert(bms_equal(member->em_relids, index->rel->relids));
+
 			/*
 			 * We allow any column of the index to match each pathkey; they
 			 * don't have to match left-to-right as you might expect.  This is
@@ -3145,6 +3169,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 			if (found)			/* don't want to look at remaining members */
 				break;
 		}
+		if (unlikely(modified))
+			list_free(members);
 
 		/*
 		 * 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 fdb60aaa8d..cd1be06b5c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -952,8 +952,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)
 				{
@@ -1479,8 +1479,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/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index b9be19a687..bb4ad60084 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -61,7 +61,7 @@ static void remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
 										  SpecialJoinInfo *sjinfo);
 static void remove_rel_from_restrictinfo(RestrictInfo *rinfo,
 										 int relid, int ojrelid);
-static void remove_rel_from_eclass(EquivalenceClass *ec,
+static void remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec,
 								   int relid, int ojrelid);
 static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
 static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
@@ -578,7 +578,7 @@ remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
 
 		if (bms_is_member(relid, ec->ec_relids) ||
 			bms_is_member(ojrelid, ec->ec_relids))
-			remove_rel_from_eclass(ec, relid, ojrelid);
+			remove_rel_from_eclass(root, ec, relid, ojrelid);
 	}
 
 	/*
@@ -663,7 +663,8 @@ remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
  * level(s).
  */
 static void
-remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
+remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec, int relid,
+					   int ojrelid)
 {
 	ListCell   *lc;
 
@@ -687,7 +688,14 @@ remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
 			cur_em->em_relids = bms_del_member(cur_em->em_relids, relid);
 			cur_em->em_relids = bms_del_member(cur_em->em_relids, ojrelid);
 			if (bms_is_empty(cur_em->em_relids))
+			{
 				ec->ec_members = foreach_delete_current(ec->ec_members, lc);
+				/* XXX performance of list_delete_ptr()?? */
+				ec->ec_norel_members = list_delete_ptr(ec->ec_norel_members,
+													   cur_em);
+				ec->ec_rel_members = list_delete_ptr(ec->ec_rel_members,
+													 cur_em);
+			}
 		}
 	}
 
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 34ca6d4ac2..d67d549b1c 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -260,7 +260,9 @@ 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,
+static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
+										Plan *lefttree,
+										List *pathkeys,
 										Relids relids,
 										const AttrNumber *reqColIdx,
 										bool adjust_tlist_in_place,
@@ -269,9 +271,11 @@ 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,
+static Sort *make_sort_from_pathkeys(PlannerInfo *root,
+									 Plan *lefttree,
+									 List *pathkeys,
 									 Relids relids);
-static IncrementalSort *make_incrementalsort_from_pathkeys(Plan *lefttree,
+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,
@@ -293,7 +297,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);
@@ -1280,7 +1284,7 @@ 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,
@@ -1324,7 +1328,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,
@@ -1465,7 +1469,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,
@@ -1496,7 +1500,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,
@@ -1975,7 +1979,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,
@@ -2194,7 +2198,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);
 
@@ -2218,7 +2222,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,
@@ -2287,7 +2291,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);
 
@@ -4498,7 +4502,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);
 
@@ -4512,7 +4516,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);
 
@@ -6133,7 +6137,7 @@ 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,
@@ -6200,7 +6204,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 */
@@ -6228,7 +6232,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 */
@@ -6244,7 +6248,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;
@@ -6315,7 +6319,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;
@@ -6324,7 +6329,7 @@ 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,
@@ -6350,8 +6355,9 @@ 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,
-								   Relids relids, int nPresortedCols)
+make_incrementalsort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+								   List *pathkeys, Relids relids,
+								   int nPresortedCols)
 {
 	int			numsortkeys;
 	AttrNumber *sortColIdx;
@@ -6360,7 +6366,7 @@ 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,
@@ -6717,7 +6723,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;
@@ -6780,7 +6787,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/util/inherit.c b/src/backend/optimizer/util/inherit.c
index f9d3ff1e7a..d826f072c7 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -461,6 +461,7 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
 		RelationGetRelid(parentrel);
 	Oid			childOID = RelationGetRelid(childrel);
 	RangeTblEntry *childrte;
+	Index		topParentRTindex;
 	Index		childRTindex;
 	AppendRelInfo *appinfo;
 	TupleDesc	child_tupdesc;
@@ -568,6 +569,19 @@ expand_single_inheritance_child(PlannerInfo *root, RangeTblEntry *parentrte,
 	Assert(root->append_rel_array[childRTindex] == NULL);
 	root->append_rel_array[childRTindex] = appinfo;
 
+	/*
+	 * Find a top parent rel's index and save it to top_parent_relid_array.
+	 */
+	if (root->top_parent_relid_array == NULL)
+		root->top_parent_relid_array =
+			(Index *) palloc0(root->simple_rel_array_size * sizeof(Index));
+	Assert(root->top_parent_relid_array[childRTindex] == 0);
+	topParentRTindex = parentRTindex;
+	while (root->append_rel_array[topParentRTindex] != NULL &&
+		   root->append_rel_array[topParentRTindex]->parent_relid != 0)
+		topParentRTindex = root->append_rel_array[topParentRTindex]->parent_relid;
+	root->top_parent_relid_array[childRTindex] = topParentRTindex;
+
 	/*
 	 * Build a PlanRowMark if parent is marked FOR UPDATE/SHARE.
 	 */
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 5d83f60eb9..698ddfd67c 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -122,11 +122,14 @@ setup_simple_rel_arrays(PlannerInfo *root)
 	if (root->append_rel_list == NIL)
 	{
 		root->append_rel_array = NULL;
+		root->top_parent_relid_array = NULL;
 		return;
 	}
 
 	root->append_rel_array = (AppendRelInfo **)
 		palloc0(size * sizeof(AppendRelInfo *));
+	root->top_parent_relid_array = (Index *)
+		palloc0(size * sizeof(Index));
 
 	/*
 	 * append_rel_array is filled with any already-existing AppendRelInfos,
@@ -147,6 +150,27 @@ setup_simple_rel_arrays(PlannerInfo *root)
 
 		root->append_rel_array[child_relid] = appinfo;
 	}
+
+	/*
+	 * Find a top parent rel's relid for each AppendRelInfo. We cannot do this
+	 * in the last foreach loop because there may be multi-level parent-child
+	 * relations.
+	 */
+	for (int i = 0; i < size; i++)
+	{
+		int top_parent_relid;
+
+		if (root->append_rel_array[i] == NULL)
+			continue;
+
+		top_parent_relid = root->append_rel_array[i]->parent_relid;
+
+		while (root->append_rel_array[top_parent_relid] != NULL &&
+			   root->append_rel_array[top_parent_relid]->parent_relid != 0)
+			top_parent_relid = root->append_rel_array[top_parent_relid]->parent_relid;
+
+		root->top_parent_relid_array[i] = top_parent_relid;
+	}
 }
 
 /*
@@ -174,11 +198,23 @@ expand_planner_arrays(PlannerInfo *root, int add_size)
 		repalloc0_array(root->simple_rte_array, RangeTblEntry *, root->simple_rel_array_size, new_size);
 
 	if (root->append_rel_array)
+	{
 		root->append_rel_array =
 			repalloc0_array(root->append_rel_array, AppendRelInfo *, root->simple_rel_array_size, new_size);
+		root->top_parent_relid_array =
+			repalloc0_array(root->top_parent_relid_array, Index, root->simple_rel_array_size, new_size);
+	}
 	else
+	{
 		root->append_rel_array =
 			palloc0_array(AppendRelInfo *, new_size);
+		/*
+		 * We do not allocate top_parent_relid_array here so that
+		 * find_relids_top_parents() can early find all of the given Relids are
+		 * top-level.
+		 */
+		root->top_parent_relid_array = NULL;
+	}
 
 	root->simple_rel_array_size = new_size;
 }
@@ -232,6 +268,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
 	rel->subplan_params = NIL;
 	rel->rel_parallel_workers = -1; /* set up in get_relation_info */
 	rel->amflags = 0;
+	rel->eclass_child_members = NIL;
 	rel->serverid = InvalidOid;
 	if (rte->rtekind == RTE_RELATION)
 	{
@@ -607,6 +644,12 @@ add_join_rel(PlannerInfo *root, RelOptInfo *joinrel)
 	/* GEQO requires us to append the new joinrel to the end of the list! */
 	root->join_rel_list = lappend(root->join_rel_list, joinrel);
 
+	/*
+	 * Store the index of this joinrel to use in
+	 * add_child_join_rel_equivalences().
+	 */
+	joinrel->join_rel_list_index = list_length(root->join_rel_list) - 1;
+
 	/* store it into the auxiliary hashtable if there is one. */
 	if (root->join_rel_hash)
 	{
@@ -718,6 +761,7 @@ build_join_rel(PlannerInfo *root,
 	joinrel->subplan_params = NIL;
 	joinrel->rel_parallel_workers = -1;
 	joinrel->amflags = 0;
+	joinrel->eclass_child_members = NIL;
 	joinrel->serverid = InvalidOid;
 	joinrel->userid = InvalidOid;
 	joinrel->useridiscurrent = false;
@@ -914,6 +958,7 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->amflags = 0;
+	joinrel->eclass_child_members = NIL;
 	joinrel->serverid = InvalidOid;
 	joinrel->userid = InvalidOid;
 	joinrel->useridiscurrent = false;
@@ -1475,6 +1520,7 @@ fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
 	upperrel->cheapest_total_path = NULL;
 	upperrel->cheapest_unique_path = NULL;
 	upperrel->cheapest_parameterized_paths = NIL;
+	upperrel->eclass_child_members = NIL;	/* XXX Is this required? */
 
 	root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
 
@@ -1515,6 +1561,48 @@ find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
 }
 
 
+/*
+ * find_relids_top_parents_slow
+ *	  Slow path of find_relids_top_parents() macro.
+ *
+ * Do not call this directly; use the macro instead. See the macro comment for
+ * more details.
+ */
+Relids
+find_relids_top_parents_slow(PlannerInfo *root, Relids relids)
+{
+	Index  *top_parent_relid_array = root->top_parent_relid_array;
+	Relids	result;
+	bool	is_top_parent;
+	int		i;
+
+	/* This function should be called in the slow path */
+	Assert(top_parent_relid_array != NULL);
+
+	result = NULL;
+	is_top_parent = true;
+	i = -1;
+	while ((i = bms_next_member(relids, i)) >= 0)
+	{
+		int		top_parent_relid = (int) top_parent_relid_array[i];
+
+		if (top_parent_relid == 0)
+			top_parent_relid = i;	/* 'i' has no parents, so add itself */
+		else if (top_parent_relid != i)
+			is_top_parent = false;
+		result = bms_add_member(result, top_parent_relid);
+	}
+
+	if (is_top_parent)
+	{
+		bms_free(result);
+		return NULL;
+	}
+
+	return result;
+}
+
+
 /*
  * get_baserel_parampathinfo
  *		Get the ParamPathInfo for a parameterized path for a base relation,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index ed85dc7414..bc3e1562fc 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -245,6 +245,14 @@ struct PlannerInfo
 	 */
 	struct AppendRelInfo **append_rel_array pg_node_attr(read_write_ignore);
 
+	/*
+	 * append_rel_array is the same length as simple_rel_array and holds the
+	 * top-level parent indexes of the corresponding rels within
+	 * simple_rel_array. The element can be zero if the rel has no parents,
+	 * i.e., is itself in a top-level.
+	 */
+	Index	   *top_parent_relid_array pg_node_attr(read_write_ignore);
+
 	/*
 	 * all_baserels is a Relids set of all base relids (but not joins or
 	 * "other" rels) in the query.  This is computed in deconstruct_jointree.
@@ -936,6 +944,17 @@ typedef struct RelOptInfo
 	/* Bitmask of optional features supported by the table AM */
 	uint32		amflags;
 
+	/*
+	 * information about a join rel
+	 */
+	/* index in root->join_rel_list of this rel */
+	Index		join_rel_list_index;
+
+	/*
+	 * EquivalenceMembers referencing this rel
+	 */
+	List	   *eclass_child_members;
+
 	/*
 	 * Information about foreign tables and foreign joins
 	 */
@@ -1368,6 +1387,10 @@ 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_norel_members;	/* list of EquivalenceMembers whose
+									 * em_relids is empty */
+	List	   *ec_rel_members;	/* list of EquivalenceMembers whose
+								 * em_relids is not empty */
 	List	   *ec_sources;		/* list of generating RestrictInfos */
 	List	   *ec_derives;		/* list of derived RestrictInfos */
 	Relids		ec_relids;		/* all relids appearing in ec_members, except
@@ -1422,6 +1445,9 @@ typedef struct EquivalenceMember
 	bool		em_is_child;	/* derived version for a child relation? */
 	Oid			em_datatype;	/* the "nominal type" used by the opfamily */
 	JoinDomain *em_jdomain;		/* join domain containing the source clause */
+	Relids		em_child_relids;	/* all relids of child rels */
+	Bitmapset  *em_child_joinrel_relids;	/* indexes in root->join_rel_list of
+											   join rel children */
 	/* if em_is_child is true, this links to corresponding EM for top parent */
 	struct EquivalenceMember *em_parent pg_node_attr(read_write_ignore);
 } EquivalenceMember;
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 6e557bebc4..cae4570823 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -323,6 +323,24 @@ extern Relids min_join_parameterization(PlannerInfo *root,
 extern RelOptInfo *fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind,
 								   Relids relids);
 extern Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel);
+
+/*
+ * find_relids_top_parents
+ *	  Compute the set of top-parent relids of rel.
+ *
+ * Replaces all Relids appearing in the given 'relids' as their top-level
+ * parents. The result will be NULL if and only if all of the given relids are
+ * top-level.
+ *
+ * The motivation for having this feature as a macro rather than a function is
+ * that Relids are top-level in most cases. We can quickly determine when
+ * root->top_parent_relid_array is NULL.
+ */
+#define find_relids_top_parents(root, relids) \
+	(likely((root)->top_parent_relid_array == NULL) \
+	 ? NULL : find_relids_top_parents_slow(root, relids))
+extern Relids find_relids_top_parents_slow(PlannerInfo *root, Relids relids);
+
 extern ParamPathInfo *get_baserel_parampathinfo(PlannerInfo *root,
 												RelOptInfo *baserel,
 												Relids required_outer);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9e7408c7ec..5953a0cc26 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,
@@ -173,6 +174,12 @@ extern void add_child_join_rel_equivalences(PlannerInfo *root,
 											AppendRelInfo **appinfos,
 											RelOptInfo *parent_joinrel,
 											RelOptInfo *child_joinrel);
+extern void add_child_rel_equivalences_to_list(PlannerInfo *root,
+											   EquivalenceClass *ec,
+											   EquivalenceMember *parent_em,
+											   Relids child_relids,
+											   List **list,
+											   bool *modified);
 extern List *generate_implied_equalities_for_column(PlannerInfo *root,
 													RelOptInfo *rel,
 													ec_matches_callback_type callback,
-- 
2.42.0.windows.2