0003-Implement-optimizations-based-on-Bitmapset.patch

From eb6e080b3053c4b45d97989f420e08e310b362c1 Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Mon, 8 Aug 2022 15:51:36 +0900
Subject: [PATCH 3/3] Implement optimizations based on Bitmapset

---
 contrib/postgres_fdw/postgres_fdw.c       |  17 +-
 src/backend/optimizer/path/allpaths.c     |   2 +-
 src/backend/optimizer/path/equivclass.c   | 200 +++++++++++++---------
 src/backend/optimizer/path/indxpath.c     |  10 +-
 src/backend/optimizer/path/pathkeys.c     |  27 +--
 src/backend/optimizer/plan/planner.c      |   2 +
 src/backend/optimizer/prep/prepjointree.c |   2 +
 src/backend/optimizer/util/relnode.c      |   8 +
 src/include/nodes/pathnodes.h             |  12 ++
 src/include/optimizer/paths.h             | 152 +++++++++++++++-
 10 files changed, 329 insertions(+), 103 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index 6bbf10d679..d2b69a4171 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7413,17 +7413,19 @@ EquivalenceMember *
 find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 {
 	int		i = -1;
+	Bitmapset *matching_ems =
+		get_eclass_members_indexes_for_subsets_of_relids(root, ec, rel->relids);
 
-	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
+	while ((i = bms_next_member(matching_ems, i)) >= 0)
 	{
 		EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
+		Assert(bms_is_subset(em->em_relids, rel->relids));
 
 		/*
 		 * Note we require !bms_is_empty, else we'd accept constant
 		 * expressions which are not suitable for the purpose.
 		 */
-		if (bms_is_subset(em->em_relids, rel->relids) &&
-			!bms_is_empty(em->em_relids) &&
+		if (!bms_is_empty(em->em_relids) &&
 			is_foreign_expr(root, rel, em->em_expr))
 			return em;
 	}
@@ -7456,6 +7458,7 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 		Expr	   *expr = (Expr *) lfirst(lc1);
 		Index		sgref = get_pathtarget_sortgroupref(target, i);
 		int			j;
+		Bitmapset  *matching_ems;
 
 		/* Ignore non-sort expressions */
 		if (sgref == 0 ||
@@ -7472,7 +7475,9 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 
 		/* Locate an EquivalenceClass member matching this expr, if any */
 		j = -1;
-		while ((j = bms_next_member(ec->ec_member_indexes, j)) >= 0)
+		/* Ignore child members */
+		matching_ems = get_eclass_members_indexes_for_not_children(root, ec);
+		while ((j = bms_next_member(matching_ems, j)) >= 0)
 		{
 			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, j);
 			Expr	   *em_expr;
@@ -7481,9 +7486,7 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 			if (em->em_is_const)
 				continue;
 
-			/* Ignore child members */
-			if (em->em_is_child)
-				continue;
+			Assert(!em->em_is_child);
 
 			/* Match if same expression (after stripping relabel) */
 			em_expr = em->em_expr;
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 9b6a5b08dc..394ae1483f 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2755,7 +2755,7 @@ set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 												(Expr *) var,
 												NULL,	/* below outer joins */
 												Int8LessOperator,
-												rel->relids,
+												rel,
 												false);
 	}
 
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 90c96de7d8..44505c0c36 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -378,19 +378,30 @@ process_equivalence(PlannerInfo *root,
 			EquivalenceMember  *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 			int					em_index = list_length(root->eq_members);
 			int					j;
+			bool				relids_is_empty;
 
 			ec1->ec_member_indexes = bms_add_member(ec1->ec_member_indexes, em_index);
 			root->eq_members = lappend(root->eq_members, em);
 
 			j = -1;
+			relids_is_empty = true;
 			while ((j = bms_next_member(em->em_relids, j)) > 0)
 			{
 				RelOptInfo *rel = root->simple_rel_array[j];
+
+				relids_is_empty = false;
+				rel->eclass_referencing_member_indexes =
+					bms_add_member(rel->eclass_referencing_member_indexes, em_index);
 				if (bms_equal(rel->relids, em->em_relids))
 				{
 					rel->eclass_member_indexes = bms_add_member(rel->eclass_member_indexes, em_index);
 				}
 			}
+
+			if (relids_is_empty)
+			{
+				root->eq_empty_relids_indexes = bms_add_member(root->eq_empty_relids_indexes, em_index);
+			}
 		}
 		ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
 		ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
@@ -576,6 +587,7 @@ add_eq_member(PlannerInfo *root, EquivalenceClass *ec, Expr *expr,
 	EquivalenceMember *em = makeNode(EquivalenceMember);
 	int					em_index;
 	int					i;
+	bool				relids_is_empty;
 
 	em->em_expr = expr;
 	em->em_relids = relids;
@@ -606,17 +618,32 @@ add_eq_member(PlannerInfo *root, EquivalenceClass *ec, Expr *expr,
 	em_index = list_length(root->eq_members);
 	ec->ec_member_indexes = bms_add_member(ec->ec_member_indexes, em_index);
 	root->eq_members = lappend(root->eq_members, em);
+	if (!is_child)
+	{
+		root->eq_not_children_indexes = bms_add_member(root->eq_not_children_indexes,
+													   em_index);
+	}
 
 	i = -1;
+	relids_is_empty = true;
 	while ((i = bms_next_member(relids, i)) > 0)
 	{
 		RelOptInfo *rel = root->simple_rel_array[i];
+
+		relids_is_empty = false;
+		rel->eclass_referencing_member_indexes =
+			bms_add_member(rel->eclass_referencing_member_indexes, em_index);
 		if (bms_equal(rel->relids, relids))
 		{
 			rel->eclass_member_indexes = bms_add_member(rel->eclass_member_indexes, em_index);
 		}
 	}
 
+	if (relids_is_empty)
+	{
+		root->eq_empty_relids_indexes = bms_add_member(root->eq_empty_relids_indexes, em_index);
+	}
+
 	return em;
 }
 
@@ -667,7 +694,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 						 Oid opcintype,
 						 Oid collation,
 						 Index sortref,
-						 Relids rel,
+						 RelOptInfo *rel,
 						 bool create_it)
 {
 	Relids		expr_relids;
@@ -688,6 +715,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 		int			i;
+		Bitmapset  *matching_ems;
 
 		/*
 		 * Never match to a volatile EC, except when we are looking at another
@@ -702,17 +730,16 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
 			continue;
 
+		/*
+		 * Ignore child members unless they match the request.
+		 */
+		matching_ems =
+			get_eclass_members_indexes_for_relids_or_not_children(root, cur_ec, rel);
 		i = -1;
-		while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0)
+		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
 			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
-
-			/*
-			 * Ignore child members unless they match the request.
-			 */
-			if (cur_em->em_is_child &&
-				!bms_equal(cur_em->em_relids, rel))
-				continue;
+			Assert(!cur_em->em_is_child || bms_equal(cur_em->em_relids, rel->relids));
 
 			/*
 			 * If below an outer join, don't match constants: they're not as
@@ -809,13 +836,13 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 
 		while ((i = bms_next_member(newec->ec_relids, i)) > 0)
 		{
-			RelOptInfo *rel = root->simple_rel_array[i];
+			RelOptInfo *rel2 = root->simple_rel_array[i];
 
-			Assert(rel->reloptkind == RELOPT_BASEREL ||
-				   rel->reloptkind == RELOPT_DEADREL);
+			Assert(rel2->reloptkind == RELOPT_BASEREL ||
+				   rel2->reloptkind == RELOPT_DEADREL);
 
-			rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
-												 ec_index);
+			rel2->eclass_indexes = bms_add_member(rel2->eclass_indexes,
+												  ec_index);
 		}
 	}
 
@@ -843,13 +870,19 @@ find_ec_member_matching_expr(PlannerInfo *root,
 							 Relids relids)
 {
 	int			i;
+	Bitmapset  *matching_ems;
 
 	/* We ignore binary-compatible relabeling on both ends */
 	while (expr && IsA(expr, RelabelType))
 		expr = ((RelabelType *) expr)->arg;
 
+	/*
+	 * Ignore child members unless they belong to the requested rel.
+	 */
+	matching_ems =
+		get_eclass_members_indexes_for_subsets_of_relids_or_not_children(root, ec, relids);
 	i = -1;
-	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
+	while ((i = bms_next_member(matching_ems, i)) >= 0)
 	{
 		EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 		Expr	   *emexpr;
@@ -861,12 +894,7 @@ find_ec_member_matching_expr(PlannerInfo *root,
 		if (em->em_is_const)
 			continue;
 
-		/*
-		 * Ignore child members unless they belong to the requested rel.
-		 */
-		if (em->em_is_child &&
-			!bms_is_subset(em->em_relids, relids))
-			continue;
+		Assert(!em->em_is_child || bms_is_subset(em->em_relids, relids));
 
 		/*
 		 * Match if same expression (after stripping relabel).
@@ -912,7 +940,13 @@ find_computable_ec_member(PlannerInfo *root,
 {
 	int		i = -1;
 
-	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
+	/*
+	 * Ignore child members unless they belong to the requested rel.
+	 */
+	Bitmapset *matching_ems =
+		get_eclass_members_indexes_for_subsets_of_relids_or_not_children(root, ec, relids);
+
+	while ((i = bms_next_member(matching_ems, i)) >= 0)
 	{
 		EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
 		List	   *exprvars;
@@ -925,12 +959,7 @@ find_computable_ec_member(PlannerInfo *root,
 		if (em->em_is_const)
 			continue;
 
-		/*
-		 * Ignore child members unless they belong to the requested rel.
-		 */
-		if (em->em_is_child &&
-			!bms_is_subset(em->em_relids, relids))
-			continue;
+		Assert(!em->em_is_child || bms_is_subset(em->em_relids, relids));
 
 		/*
 		 * Match if all Vars and quasi-Vars are available in "exprs".
@@ -1610,6 +1639,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 	List	   *inner_members = NIL;
 	ListCell   *lc1;
 	int			i;
+	Bitmapset  *matching_ems;
 
 	/*
 	 * First, scan the EC to identify member values that are computable at the
@@ -1620,18 +1650,17 @@ 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.
 	 */
+	/*
+	 * We don't need to check explicitly for child EC members.  This test
+	 * against join_relids will cause them to be ignored except when
+	 * considering a child inner rel, which is what we want.
+	 */
+	matching_ems = get_eclass_members_indexes_for_subsets_of_relids(root, ec, join_relids);
 	i = -1;
-	while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
+	while ((i = bms_next_member(matching_ems, i)) >= 0)
 	{
 		EquivalenceMember *cur_em = (EquivalenceMember *)list_nth(root->eq_members, i);
-
-		/*
-		 * We don't need to check explicitly for child EC members.  This test
-		 * against join_relids will cause them to be ignored except when
-		 * considering a child inner rel, which is what we want.
-		 */
-		if (!bms_is_subset(cur_em->em_relids, join_relids))
-			continue;			/* not computable yet, or wrong child */
+		Assert(bms_is_subset(cur_em->em_relids, join_relids));
 
 		if (bms_is_subset(cur_em->em_relids, outer_relids))
 			outer_members = lappend(outer_members, cur_em);
@@ -2392,12 +2421,16 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		if (matchleft && matchright)
 		{
 			cur_ec->ec_member_indexes = bms_del_member(cur_ec->ec_member_indexes, coal_idx);
+			root->eq_not_children_indexes = bms_del_member(root->eq_not_children_indexes,
+														   coal_idx);
 
 			/* Remove the member from each of the relations */
 			i = -1;
 			while ((i = bms_next_member(coal_em->em_relids, i)) > 0)
 			{
 				RelOptInfo *rel = root->simple_rel_array[i];
+				rel->eclass_referencing_member_indexes =
+					bms_del_member(rel->eclass_referencing_member_indexes, coal_idx);
 				if (bms_equal(rel->relids, coal_em->em_relids))
 				{
 					rel->eclass_member_indexes = bms_del_member(rel->eclass_member_indexes, coal_idx);
@@ -2442,18 +2475,20 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
 		bool		item1member = false;
 		bool		item2member = false;
 		int			i;
+		Bitmapset  *matching_ems;
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
 			continue;
 
 		i = -1;
-		while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0)
+		/* ignore children here */
+		matching_ems = get_eclass_members_indexes_for_not_children(root, ec);
+		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
 			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
+			Assert(!em->em_is_child);
 
-			if (em->em_is_child)
-				continue;		/* ignore children here */
 			if (equal(item1, em->em_expr))
 				item1member = true;
 			else if (equal(item2, em->em_expr))
@@ -2514,6 +2549,7 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 		EquivalenceMember *item1_em = NULL;
 		EquivalenceMember *item2_em = NULL;
 		int					j;
+		Bitmapset		   *matching_ems;
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
@@ -2521,13 +2557,14 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 		/* Note: it seems okay to match to "broken" eclasses here */
 
 		j = -1;
-		while ((j = bms_next_member(ec->ec_member_indexes, j)) >= 0)
+		/* ignore children here */
+		matching_ems = get_eclass_members_indexes_for_not_children(root, ec);
+		while ((j = bms_next_member(matching_ems, j)) >= 0)
 		{
 			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, j);
 			Var		   *var;
 
-			if (em->em_is_child)
-				continue;		/* ignore children here */
+			Assert(!em->em_is_child);
 
 			/* EM must be a Var, possibly with RelabelType */
 			var = (Var *) em->em_expr;
@@ -2636,8 +2673,9 @@ 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;
+		int			final_member;
 		int			j;
+		Bitmapset  *matching_ems;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2656,28 +2694,28 @@ add_child_rel_equivalences(PlannerInfo *root,
 		 * Use bms_prev_member(..., -1) to get the final member first and
 		 * abort the loop when we go beyond that?
 		 */
-		num_members = bms_num_members(cur_ec->ec_member_indexes);
+		final_member = bms_prev_member(cur_ec->ec_member_indexes, -1);
+
+		/*
+		 * 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.)
+		 */
+		/* ignore children here */
+		matching_ems = get_eclass_members_indexes_for_not_children(root, cur_ec);
 		j = -1;
-		for (int pos = 0; pos < num_members; pos++)
+		while ((j = bms_next_member(matching_ems, j)) >= 0 && j <= final_member)
 		{
 			EquivalenceMember *cur_em;
-
-			j = bms_next_member(cur_ec->ec_member_indexes, j);
 			cur_em = (EquivalenceMember *) list_nth(root->eq_members, j);
 
 			if (cur_em->em_is_const)
 				continue;		/* ignore consts here */
 
-			/*
-			 * 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 */
+			Assert(!cur_em->em_is_child);
 
 			/* Does this member reference child's topmost parent rel? */
 			if (bms_overlap(cur_em->em_relids, top_parent_relids))
@@ -2780,8 +2818,9 @@ 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;
+		int			final_member;
 		int			j;
+		Bitmapset  *matching_ems;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2800,24 +2839,24 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 		 * Use bms_prev_member(..., -1) to get the final member first and
 		 * abort the loop when we go beyond that?
 		 */
-		num_members = bms_num_members(cur_ec->ec_member_indexes);
+		final_member = bms_prev_member(cur_ec->ec_member_indexes, -1);
+
+		/*
+		 * We consider only original EC members here, not
+		 * already-transformed child members.
+		 */
+		/* ignore children here */
+		matching_ems = get_eclass_members_indexes_for_not_children(root, cur_ec);
 		j = -1;
-		for (int pos = 0; pos < num_members; pos++)
+		while ((j = bms_next_member(matching_ems, j)) >= 0 && j <= final_member)
 		{
 			EquivalenceMember *cur_em;
-
-			j = bms_next_member(cur_ec->ec_member_indexes, j);
 			cur_em = (EquivalenceMember *) list_nth(root->eq_members, j);
 
 			if (cur_em->em_is_const)
 				continue;		/* ignore consts here */
 
-			/*
-			 * We consider only original EC members here, not
-			 * already-transformed child members.
-			 */
-			if (cur_em->em_is_child)
-				continue;		/* ignore children here */
+			Assert(!cur_em->em_is_child);
 
 			/*
 			 * We may ignore expressions that reference a single baserel,
@@ -2939,6 +2978,7 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		EquivalenceMember *cur_em;
 		int					j;
+		Bitmapset		   *matching_ems;
 
 		/* Sanity check eclass_indexes only contain ECs for rel */
 		Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
@@ -2962,13 +3002,14 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		 * match.  See also get_eclass_for_sort_expr.)
 		 */
 		cur_em = NULL;
+		matching_ems = get_eclass_members_indexes_for_relids(root, cur_ec, rel);
 		j = -1;
-		while ((j = bms_next_member(cur_ec->ec_member_indexes, j)) >= 0)
+		while ((j = bms_next_member(matching_ems, j)) >= 0)
 		{
 			cur_em = (EquivalenceMember *) list_nth(root->eq_members, j);
 
-			if (bms_equal(cur_em->em_relids, rel->relids) &&
-				callback(root, rel, cur_ec, cur_em, callback_arg))
+			Assert(bms_equal(cur_em->em_relids, rel->relids));
+			if (callback(root, rel, cur_ec, cur_em, callback_arg))
 				break;
 			cur_em = NULL;
 		}
@@ -2981,14 +3022,15 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		 * joinclauses.
 		 */
 		j = -1;
-		while ((j = bms_next_member(cur_ec->ec_member_indexes, j)) >= 0)
+		/* ignore children here */
+		matching_ems = get_eclass_members_indexes_for_not_children(root, cur_ec);
+		while ((j = bms_next_member(matching_ems, j)) >= 0)
 		{
 			EquivalenceMember *other_em = (EquivalenceMember *) list_nth(root->eq_members, j);
 			Oid			eq_op;
 			RestrictInfo *rinfo;
 
-			if (other_em->em_is_child)
-				continue;		/* ignore children here */
+			Assert(!other_em->em_is_child);
 
 			/* Make sure it'll be a join to a different rel */
 			if (other_em == cur_em ||
@@ -3161,6 +3203,7 @@ eclass_useful_for_merging(PlannerInfo *root,
 {
 	Relids		relids;
 	int			i;
+	Bitmapset  *matching_ems;
 
 	Assert(!eclass->ec_merged);
 
@@ -3192,13 +3235,14 @@ eclass_useful_for_merging(PlannerInfo *root,
 		return false;
 
 	/* To join, we need a member not in the given rel */
+	/* ignore children here */
+	matching_ems = get_eclass_members_indexes_for_not_children(root, eclass);
 	i = -1;
-	while ((i = bms_next_member(eclass->ec_member_indexes, i)) >= 0)
+	while ((i = bms_next_member(matching_ems, i)) >= 0)
 	{
 		EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i);
 
-		if (cur_em->em_is_child)
-			continue;			/* ignore children here */
+		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 4c18ada572..843b7c7be3 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3093,6 +3093,7 @@ match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index,
 		PathKey    *pathkey = (PathKey *) lfirst(lc1);
 		bool		found = false;
 		int			i;
+		Bitmapset  *matching_ems;
 
 		/*
 		 * Note: for any failure to match, we just return NIL immediately.
@@ -3117,14 +3118,15 @@ match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index,
 		 * here.  See also get_eclass_for_sort_expr.)
 		 */
 		i = -1;
-		while ((i = bms_next_member(pathkey->pk_eclass->ec_member_indexes, i)) >= 0)
+		/* No possibility of match if it references other relations */
+		matching_ems =
+			get_eclass_members_indexes_for_relids(root, pathkey->pk_eclass, index->rel);
+		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
 			EquivalenceMember *member = (EquivalenceMember *) list_nth(root->eq_members, i);
 			int			indexcol;
 
-			/* No possibility of match if it references other relations */
-			if (!bms_equal(member->em_relids, index->rel->relids))
-				continue;
+			Assert(bms_equal(member->em_relids, index->rel->relids));
 
 			/*
 			 * We allow any column of the index to match each pathkey; they
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index de864023b2..6fcf0ccb01 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -212,7 +212,7 @@ make_pathkey_from_sortinfo(PlannerInfo *root,
 						   bool reverse_sort,
 						   bool nulls_first,
 						   Index sortref,
-						   Relids rel,
+						   RelOptInfo *rel,
 						   bool create_it)
 {
 	int16		strategy;
@@ -1134,7 +1134,7 @@ build_index_pathkeys(PlannerInfo *root,
 											  reverse_sort,
 											  nulls_first,
 											  0,
-											  index->rel->relids,
+											  index->rel,
 											  false);
 
 		if (cpathkey)
@@ -1290,7 +1290,7 @@ build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
 											  ScanDirectionIsBackward(scandir),
 											  ScanDirectionIsBackward(scandir),
 											  0,
-											  partrel->relids,
+											  partrel,
 											  false);
 
 
@@ -1343,7 +1343,7 @@ build_expression_pathkey(PlannerInfo *root,
 						 Expr *expr,
 						 Relids nullable_relids,
 						 Oid opno,
-						 Relids rel,
+						 RelOptInfo *rel,
 						 bool create_it)
 {
 	List	   *pathkeys;
@@ -1455,7 +1455,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 											 sub_member->em_datatype,
 											 sub_eclass->ec_collation,
 											 0,
-											 rel->relids,
+											 rel,
 											 false);
 
 				/*
@@ -1491,8 +1491,11 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 			 */
 			int			best_score = -1;
 			int			j = -1;
+			/* ignore children here */
+			Bitmapset  *matching_ems =
+				get_eclass_members_indexes_for_not_children(rel->subroot, sub_eclass);
 
-			while ((j = bms_next_member(sub_eclass->ec_member_indexes, j)) >= 0)
+			while ((j = bms_next_member(matching_ems, j)) >= 0)
 			{
 				EquivalenceMember *sub_member = (EquivalenceMember *) list_nth(rel->subroot->eq_members, j);
 				Expr	   *sub_expr = sub_member->em_expr;
@@ -1500,8 +1503,7 @@ 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 */
+				Assert(!sub_member->em_is_child);
 
 				foreach(k, subquery_tlist)
 				{
@@ -1537,7 +1539,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 														sub_expr_type,
 														sub_expr_coll,
 														0,
-														rel->relids,
+														rel,
 														false);
 
 					/*
@@ -1966,6 +1968,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 		EquivalenceClass *oeclass;
 		int			score;
 		int			i;
+		Bitmapset  *matching_ems;
 
 		/* get the outer eclass */
 		update_mergeclause_eclasses(root, rinfo);
@@ -1987,12 +1990,14 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 		/* compute score */
 		score = 0;
 		i = -1;
-		while ((i = bms_next_member(oeclass->ec_member_indexes, i)) >= 0)
+		matching_ems = get_eclass_members_indexes_for_not_children(root, oeclass);
+		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
 			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i);
+			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/planner.c b/src/backend/optimizer/plan/planner.c
index d0bc9a467d..e71f115fd6 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -620,6 +620,8 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root->multiexpr_params = NIL;
 	root->eq_classes = NIL;
 	root->eq_members = NIL;
+	root->eq_not_children_indexes = NULL;
+	root->eq_empty_relids_indexes = NULL;
 	root->ec_merging_done = false;
 	root->all_result_relids =
 		parse->resultRelation ? bms_make_singleton(parse->resultRelation) : NULL;
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index f3e6c19fc7..90a5dcae72 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -999,6 +999,8 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->multiexpr_params = NIL;
 	subroot->eq_classes = NIL;
 	subroot->eq_members = NIL;
+	subroot->eq_not_children_indexes = NULL;
+	subroot->eq_empty_relids_indexes = NULL;
 	subroot->ec_merging_done = false;
 	subroot->all_result_relids = NULL;
 	subroot->leaf_result_relids = NULL;
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 520409f4ba..101742959a 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -231,6 +231,8 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
 	rel->tuples = 0;
 	rel->allvisfrac = 0;
 	rel->eclass_indexes = NULL;
+	rel->eclass_member_indexes = NULL;
+	rel->eclass_referencing_member_indexes = NULL;
 	rel->subroot = NULL;
 	rel->subplan_params = NIL;
 	rel->rel_parallel_workers = -1; /* set up in get_relation_info */
@@ -645,6 +647,8 @@ build_join_rel(PlannerInfo *root,
 	joinrel->tuples = 0;
 	joinrel->allvisfrac = 0;
 	joinrel->eclass_indexes = NULL;
+	joinrel->eclass_member_indexes = NULL;
+	joinrel->eclass_referencing_member_indexes = NULL;
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->rel_parallel_workers = -1;
@@ -828,6 +832,8 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
 	joinrel->tuples = 0;
 	joinrel->allvisfrac = 0;
 	joinrel->eclass_indexes = NULL;
+	joinrel->eclass_member_indexes = NULL;
+	joinrel->eclass_referencing_member_indexes = NULL;
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->amflags = 0;
@@ -1242,6 +1248,8 @@ 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_member_indexes = NULL;	/* TODO: Is this necessary? */
+	upperrel->eclass_referencing_member_indexes = NULL;	/* TODO: Is this necessary? */
 
 	root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
 
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 34f2f39012..1cc23eec09 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -303,6 +303,12 @@ struct PlannerInfo
 	/* list of each EquivalenceMember */
 	List	   *eq_members;
 
+	/* indexes of EquivalenceMembers which are not children */
+	Bitmapset  *eq_not_children_indexes;
+
+	/* indexes of EquivalenceMembers whose relids are empty */
+	Bitmapset  *eq_empty_relids_indexes;
+
 	/* set true once ECs are canonical */
 	bool		ec_merging_done;
 
@@ -891,6 +897,12 @@ typedef struct RelOptInfo
 	 */
 	Bitmapset  *eclass_member_indexes;
 
+	/*
+	 * Indexes in PlannerInfo's eq_members list of EMs that reference this rel
+	 * TODO: Its variable name should be more refined.
+	 */
+	Bitmapset  *eclass_referencing_member_indexes;
+
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	/* wanted number of parallel workers */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index c9482f86cb..d9dff21c1e 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -134,7 +134,7 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 												  Oid opcintype,
 												  Oid collation,
 												  Index sortref,
-												  Relids rel,
+												  RelOptInfo *rel,
 												  bool create_it);
 extern EquivalenceMember *find_ec_member_matching_expr(PlannerInfo *root,
 													   EquivalenceClass *ec,
@@ -189,6 +189,154 @@ extern bool is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist);
 extern bool is_redundant_with_indexclauses(RestrictInfo *rinfo,
 										   List *indexclauses);
 
+/*
+ * TODO: The following helper functions are placed in this header file to help
+ * compiler inline them.
+ */
+
+/*
+ * get_eclass_members_indexes_for_relids
+ *		Build and return a Bitmapset containing the indexes into root's
+ *		eq_members list for all EquivalenceMembers whose em_relids is equal to
+ *		the given RelOptInfo's relids
+ */
+static inline Bitmapset *
+get_eclass_members_indexes_for_relids(PlannerInfo *root,
+									  EquivalenceClass *ec,
+									  RelOptInfo *rel)
+{
+	if (rel == NULL)
+		return bms_intersect(ec->ec_member_indexes, root->eq_empty_relids_indexes);
+	else
+		return bms_intersect(ec->ec_member_indexes, rel->eclass_member_indexes);
+}
+
+/*
+ * get_eclass_members_indexes_for_not_children
+ *		Build and return a Bitmapset containing the indexes into root's
+ *		eq_members list for all EquivalenceMembers whose em_is_child is false
+ */
+static inline Bitmapset *
+get_eclass_members_indexes_for_not_children(PlannerInfo *root, EquivalenceClass *ec)
+{
+	return bms_intersect(ec->ec_member_indexes, root->eq_not_children_indexes);
+}
+
+/*
+ * get_eclass_members_indexes_for_relids_or_not_children
+ *		Build and return a Bitmapset containing the indexes into root's
+ *		eq_members list for all EquivalenceMembers whose em_relids is equal to
+ *		the given RelOptInfo's relids, or em_is_child is false
+ */
+static inline Bitmapset *
+get_eclass_members_indexes_for_relids_or_not_children(PlannerInfo *root,
+													  EquivalenceClass *ec,
+													  RelOptInfo *rel)
+{
+	Bitmapset  *em_indexes;
+
+	if (rel == NULL)
+		em_indexes = bms_union(root->eq_not_children_indexes, root->eq_empty_relids_indexes);
+	else
+		em_indexes = bms_union(root->eq_not_children_indexes, rel->eclass_member_indexes);
+
+	em_indexes = bms_int_members(em_indexes, ec->ec_member_indexes);
+
+	return em_indexes;
+}
+
+/*
+ * get_eclass_members_indexes_for_subsets_of_relids
+ *		Build and return a Bitmapset containing the indexes into root's
+ *		eq_members list for all EquivalenceMembers whose em_relids is a subset
+ *		of the given relids
+ */
+static inline Bitmapset *
+get_eclass_members_indexes_for_subsets_of_relids(PlannerInfo *root,
+												 EquivalenceClass *ec,
+												 Relids relids)
+{
+	Bitmapset  *em_indexes;
+	int			i;
+
+	if (relids == NULL)
+		return bms_intersect(ec->ec_member_indexes, root->eq_empty_relids_indexes);
+
+	em_indexes = NULL;
+	i = -1;
+	while ((i = bms_next_member(relids, i)) >= 0)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		/* Retrieve candidates that we want to get */
+		Bitmapset  *em_candidates = bms_intersect(ec->ec_member_indexes,
+												  rel->eclass_referencing_member_indexes);
+		int			j;
+
+		/* Check if the candidates satisfy the condition */
+		j = -1;
+		while ((j = bms_next_member(em_candidates, j)) >= 0)
+		{
+			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, j);
+
+			if (bms_is_subset(em->em_relids, relids))
+			{
+				/* Satisfies, so add it to the result Bitmapset */
+				em_indexes = bms_add_member(em_indexes, j);
+			}
+		}
+	}
+
+	return em_indexes;
+}
+
+/*
+ * get_eclass_members_indexes_for_subsets_of_relids_or_not_children
+ *		Build and return a Bitmapset containing the indexes into root's
+ *		eq_members list for all EquivalenceMembers whose em_relids is a subset
+ *		of the given relids, or em_is_child is false
+ */
+static inline Bitmapset *
+get_eclass_members_indexes_for_subsets_of_relids_or_not_children(PlannerInfo *root,
+																 EquivalenceClass *ec,
+																 Relids relids)
+{
+	Bitmapset  *em_indexes;
+	int			i;
+
+	if (relids == NULL)
+		return bms_int_members(bms_union(root->eq_empty_relids_indexes,
+										 root->eq_not_children_indexes),
+							   ec->ec_member_indexes);
+
+	em_indexes = bms_intersect(ec->ec_member_indexes, root->eq_not_children_indexes);
+	i = -1;
+	while ((i = bms_next_member(relids, i)) >= 0)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		/* Retrieve candidates that we want to get */
+		Bitmapset  *em_candidates = bms_intersect(ec->ec_member_indexes,
+												  rel->eclass_referencing_member_indexes);
+		int			j;
+
+		/* Check if the candidates satisfy the condition */
+		j = -1;
+		while ((j = bms_next_member(em_candidates, j)) >= 0)
+		{
+			EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, j);
+
+			if (bms_is_subset(em->em_relids, relids))
+			{
+				/* Satisfies, so add it to the result Bitmapset */
+				em_indexes = bms_add_member(em_indexes, j);
+			}
+		}
+	}
+
+	return em_indexes;
+}
+
 /*
  * pathkeys.c
  *	  utilities for matching and building path keys
@@ -226,7 +374,7 @@ extern List *build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
 									  ScanDirection scandir, bool *partialkeys);
 extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
 									  Relids nullable_relids, Oid opno,
-									  Relids rel, bool create_it);
+									  RelOptInfo *rel, bool create_it);
 extern List *convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 									   List *subquery_pathkeys,
 									   List *subquery_tlist);
-- 
2.35.3.windows.1