v4-0002-Implement-ECIndexCache.patch

From e9921a25ddbac48887344330edaea792eae7fa56 Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Tue, 23 Aug 2022 18:16:13 +0900
Subject: [PATCH v4 2/2] Implement ECIndexCache

---
 contrib/postgres_fdw/postgres_fdw.c       |   6 +-
 src/backend/nodes/gen_node_support.pl     |   3 +
 src/backend/optimizer/path/equivclass.c   | 179 ++++++++++++++++++----
 src/backend/optimizer/path/pathkeys.c     |   4 +-
 src/backend/optimizer/util/appendinfo.c   |   3 +
 src/backend/optimizer/util/relnode.c      |   4 +
 src/backend/optimizer/util/restrictinfo.c |   6 +
 src/include/nodes/pathnodes.h             |  58 +++++++
 src/include/optimizer/paths.h             |  24 ++-
 9 files changed, 243 insertions(+), 44 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index e8996456be..ec5a98cd87 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7415,7 +7415,8 @@ find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 	Bitmapset *matching_ems;
 	int		i = -1;
 
-	matching_ems = get_ecmember_indexes(root, ec, rel->relids, true, false);
+	matching_ems = get_ecmember_indexes(root, ec, rel->relids, true, false,
+										&rel->ec_index_cache);
 
 	while ((i = bms_next_member(matching_ems, i)) >= 0)
 	{
@@ -7478,7 +7479,7 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 
 		expr_relids = pull_varnos(root, (Node *) expr);
 		matching_ems = get_ecmember_indexes_strict(root, ec, expr_relids,
-												   false, false);
+												   false, false, NULL);
 		/* Locate an EquivalenceClass member matching this expr, if any */
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -7507,7 +7508,6 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 		}
 		i++;
 		bms_free(expr_relids);
-		bms_free(matching_ems);
 	}
 
 	return NULL;
diff --git a/src/backend/nodes/gen_node_support.pl b/src/backend/nodes/gen_node_support.pl
index b707a09f56..0a27831ed3 100644
--- a/src/backend/nodes/gen_node_support.pl
+++ b/src/backend/nodes/gen_node_support.pl
@@ -168,6 +168,9 @@ my %manual_nodetag_number;
 # EquivalenceClasses are never moved, so just shallow-copy the pointer
 push @scalar_types, qw(EquivalenceClass* EquivalenceMember*);
 
+# TODO: This is probably wrong
+push @scalar_types, qw(ECIndexCache);
+
 # This is a struct, so we can copy it by assignment.  Equal support is
 # currently not required.
 push @scalar_types, qw(QualCost);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 2b04b67b14..9b0754b764 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -765,7 +765,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 			continue;
 
 		matching_ems = get_ecmember_indexes_strict(root, cur_ec, expr_relids,
-												   true, true);
+												   true, true, NULL);
 
 		i = -1;
 		while ((i = bms_next_member(matching_ems, i)) >= 0)
@@ -918,7 +918,8 @@ find_ec_member_matching_expr(PlannerInfo *root,
 		expr = ((RelabelType *) expr)->arg;
 
 	expr_relids = pull_varnos(root, (Node *) expr);
-	matching_ems = get_ecmember_indexes_strict(root, ec, expr_relids, true, true);
+	matching_ems = get_ecmember_indexes_strict(root, ec, expr_relids,
+											   true, true, NULL);
 
 	i = -1;
 	while ((i = bms_next_member(matching_ems, i)) >= 0)
@@ -1458,7 +1459,6 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 		add_vars_to_targetlist(root, vars, ec->ec_relids);
 		list_free(vars);
 	}
-	bms_free(matching_ems);
 }
 
 /*
@@ -1706,7 +1706,7 @@ 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.
 	 */
-	matching_ems = get_ecmember_indexes(root, ec, join_relids, true, false);
+	matching_ems = get_ecmember_indexes(root, ec, join_relids, true, false, NULL);
 
 	i = -1;
 	while ((i = bms_next_member(matching_ems, i)) >= 0)
@@ -1876,7 +1876,7 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
 	List	   *result = NIL;
 	int			i;
 
-	matching_es = get_ec_source_indexes(root, ec, nominal_join_relids);
+	matching_es = get_ec_source_indexes(root, ec, nominal_join_relids, NULL);
 	i = -1;
 	while ((i = bms_next_member(matching_es, i)) >= 0)
 	{
@@ -1970,8 +1970,8 @@ create_join_clause(PlannerInfo *root,
 	 * previously-derived clauses.  The check on opno is probably redundant,
 	 * but be safe ...
 	 */
-	matches = bms_int_members(get_ec_source_indexes_strict(root, ec, leftem->em_relids),
-							  get_ec_source_indexes_strict(root, ec, rightem->em_relids));
+	matches = bms_intersect(get_ec_source_indexes_strict(root, ec, leftem->em_relids, NULL),
+							get_ec_source_indexes_strict(root, ec, rightem->em_relids, NULL));
 	i = -1;
 	while ((i = bms_next_member(matches, i)) >= 0)
 	{
@@ -1983,8 +1983,8 @@ create_join_clause(PlannerInfo *root,
 			return rinfo;
 	}
 
-	matches = bms_int_members(get_ec_derive_indexes_strict(root, ec, leftem->em_relids),
-							  get_ec_derive_indexes_strict(root, ec, rightem->em_relids));
+	matches = bms_intersect(get_ec_derive_indexes_strict(root, ec, leftem->em_relids, NULL),
+							get_ec_derive_indexes_strict(root, ec, rightem->em_relids, NULL));
 
 	i = -1;
 	while ((i = bms_next_member(matches, i)) >= 0)
@@ -2223,6 +2223,7 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 	Relids		outer_relids,
 				inner_relids,
 				inner_nullable_relids;
+	ECIndexCache *outer_ec_index_cache;
 	ListCell   *lc1;
 
 	Assert(is_opclause(rinfo->clause));
@@ -2242,6 +2243,7 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 		inner_datatype = right_type;
 		outer_relids = rinfo->left_relids;
 		inner_relids = rinfo->right_relids;
+		outer_ec_index_cache = &rinfo->left_ec_index_cache;
 	}
 	else
 	{
@@ -2250,6 +2252,7 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 		inner_datatype = left_type;
 		outer_relids = rinfo->right_relids;
 		inner_relids = rinfo->left_relids;
+		outer_ec_index_cache = &rinfo->right_ec_index_cache;
 	}
 	inner_nullable_relids = bms_intersect(inner_relids,
 										  rinfo->nullable_relids);
@@ -2277,7 +2280,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 		match = false;
 		matching_ems = get_ecmember_indexes_strict(root, cur_ec,
 												   outer_relids,
-												   false, true);
+												   false, true,
+												   outer_ec_index_cache);
 		i = -1;
 		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
@@ -2417,7 +2421,8 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		 */
 		matching_ems = get_ecmember_indexes_strict(root, cur_ec,
 												   rinfo->clause_relids, true,
-												   false);
+												   false,
+												   &rinfo->clause_ec_index_cache);
 		match = false;
 		i = -1;
 		while ((i = bms_next_member(matching_ems, i)) >= 0)
@@ -2567,8 +2572,8 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
 		if (ec->ec_has_volatile)
 			continue;
 
-		matching_ems = bms_join(get_ecmember_indexes_strict(root, ec, item1_relids, false, true),
-								get_ecmember_indexes_strict(root, ec, item2_relids, false, true));
+		matching_ems = bms_union(get_ecmember_indexes_strict(root, ec, item1_relids, false, true, NULL),
+								 get_ecmember_indexes_strict(root, ec, item2_relids, false, true, NULL));
 		i = -1;
 		while ((i = bms_next_member(matching_ems, i)) >= 0)
 		{
@@ -2643,8 +2648,8 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 		if (ec->ec_has_volatile)
 			continue;
 		/* Note: it seems okay to match to "broken" eclasses here */
-		matching_ems = bms_join(get_ecmember_indexes_strict(root, ec, rel1->relids, false, false),
-								get_ecmember_indexes_strict(root, ec, rel2->relids, false, false));
+		matching_ems = bms_union(get_ecmember_indexes_strict(root, ec, rel1->relids, false, false, &rel1->ec_index_cache),
+								 get_ecmember_indexes_strict(root, ec, rel2->relids, false, false, &rel2->ec_index_cache));
 
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -2784,7 +2789,8 @@ add_child_rel_equivalences(PlannerInfo *root,
 		 * Looping over matching_ems means we only loop over existing members,
 		 * not any newly added ones.
 		 */
-		matching_ems = get_ecmember_indexes(root, cur_ec, top_parent_relids, false, false);
+		matching_ems = get_ecmember_indexes(root, cur_ec, top_parent_relids,
+											false, false, NULL);
 
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -2911,7 +2917,8 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 		 * Looping over matching_ems means we only loop over existing members,
 		 * not any newly added ones.
 		 */
-		matching_ems = get_ecmember_indexes(root, cur_ec, top_parent_relids, false, false);
+		matching_ems = get_ecmember_indexes(root, cur_ec, top_parent_relids,
+											false, false, NULL);
 
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -3062,7 +3069,8 @@ 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.)
 		 */
-		matching_ems = get_ecmember_indexes(root, cur_ec, rel->relids, true, false);
+		matching_ems = get_ecmember_indexes(root, cur_ec, rel->relids,
+											true, false, &rel->ec_index_cache);
 		cur_em = NULL;
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -3263,6 +3271,7 @@ eclass_useful_for_merging(PlannerInfo *root,
 {
 	Bitmapset  *matching_ems;
 	Relids		relids;
+	ECIndexCache *ec_index_cache;
 
 	Assert(!eclass->ec_merged);
 
@@ -3285,16 +3294,21 @@ eclass_useful_for_merging(PlannerInfo *root,
 	{
 		Assert(!bms_is_empty(rel->top_parent_relids));
 		relids = rel->top_parent_relids;
+		ec_index_cache = NULL;
 	}
 	else
+	{
 		relids = rel->relids;
+		ec_index_cache = &rel->ec_index_cache;
+	}
 
 	/* If rel already includes all members of eclass, no point in searching */
 	if (bms_is_subset(eclass->ec_relids, relids))
 		return false;
 
 	/* Find the EquivalenceMember for relids */
-	matching_ems = get_ecmember_indexes(root, eclass, relids, false, false);
+	matching_ems = get_ecmember_indexes(root, eclass, relids,
+										false, false, ec_index_cache);
 
 	/*
 	 * If there are any other non-child members besides matching_ems then we
@@ -3422,6 +3436,51 @@ get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
 	return bms_int_members(rel1ecs, rel2ecs);
 }
 
+/*
+ * Helper macros for caching the result of get_ec**_indexes**().
+ */
+
+/* Call this at the entry of functions */
+#define RETURN_CACHE_IF_AVAILABLE(eclass, cache, field)					\
+	do																	\
+	{																	\
+		if ((cache) != NULL)											\
+		{																\
+			/* The EC that the cache is pointing to */					\
+			EquivalenceClass   *pointing_ec;							\
+			Bitmapset		   *cached_bitmapset;						\
+																		\
+			pointing_ec = (cache)->ec;									\
+																		\
+			if (pointing_ec == NULL)									\
+			{															\
+				/* This is the first time of using this cache. */		\
+				/* We can use it. */									\
+				(cache)->ec = (eclass);									\
+			}															\
+			else if (pointing_ec != (eclass))							\
+			{															\
+				/* This cache is not available */						\
+				/* because it is pointing to another EC. */				\
+				(cache) = NULL;	/* Tell that to outside of this macro */\
+				break;													\
+			}															\
+																		\
+			/* Here, this cache is available */							\
+			cached_bitmapset = (cache)->field;							\
+			if (cached_bitmapset != NULL)								\
+				return cached_bitmapset;								\
+		}																\
+	} while (false)
+
+/* Call this at the end of functions */
+#define STORE_RESULT_TO_CACHE(value, cache, field)						\
+	do																	\
+	{																	\
+		if ((cache) != NULL)											\
+			(cache)->field = (value);									\
+	} while (false)
+
 /*
  * get_ecmember_indexes
  *		Returns a Bitmapset with indexes into root->eq_members for all
@@ -3434,12 +3493,20 @@ get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
  */
 Bitmapset *
 get_ecmember_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids,
-					 bool with_children, bool with_norel_members)
+					 bool with_children, bool with_norel_members,
+					 ECIndexCache *cache)
 {
 	Bitmapset  *matching_ems;
-	Bitmapset  *rel_ems = NULL;
+	Bitmapset  *rel_ems;
 	int			i;
 
+	RETURN_CACHE_IF_AVAILABLE(
+		ec,
+		cache,
+		ecmember_indexes[GET_EC_INDEX_CACHE_ARRAY_INDEX(with_children, with_norel_members)]);
+
+	rel_ems = NULL;
+
 	if (!with_children)
 		matching_ems = bms_copy(ec->ec_nonchild_indexes);
 	else
@@ -3471,6 +3538,11 @@ get_ecmember_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids,
 	if (with_norel_members)
 		matching_ems = bms_add_members(matching_ems, ec->ec_norel_indexes);
 
+	STORE_RESULT_TO_CACHE(
+		matching_ems,
+		cache,
+		ecmember_indexes[GET_EC_INDEX_CACHE_ARRAY_INDEX(with_children, with_norel_members)]);
+
 	return matching_ems;
 }
 
@@ -3485,11 +3557,17 @@ get_ecmember_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids,
 Bitmapset *
 get_ecmember_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
 							Relids relids, bool with_children,
-							bool with_norel_members)
+							bool with_norel_members,
+							ECIndexCache *cache)
 {
 	Bitmapset  *matching_ems;
 	int			i;
 
+	RETURN_CACHE_IF_AVAILABLE(
+		ec,
+		cache,
+		ecmember_indexes_strict[GET_EC_INDEX_CACHE_ARRAY_INDEX(with_children, with_norel_members)]);
+
 	if (!with_children)
 		matching_ems = bms_copy(ec->ec_nonchild_indexes);
 	else
@@ -3518,6 +3596,11 @@ get_ecmember_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
 	if (with_norel_members)
 		matching_ems = bms_add_members(matching_ems, ec->ec_norel_indexes);
 
+	STORE_RESULT_TO_CACHE(
+		matching_ems,
+		cache,
+		ecmember_indexes_strict[GET_EC_INDEX_CACHE_ARRAY_INDEX(with_children, with_norel_members)]);
+
 	return matching_ems;
 }
 
@@ -3530,10 +3613,15 @@ get_ecmember_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
  * Returns a newly allocated Bitmapset which the caller is free to modify.
  */
 Bitmapset *
-get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids, ECIndexCache *cache)
 {
-	Bitmapset  *matching_es = NULL;
-	int			i = bms_next_member(relids, -1);
+	Bitmapset  *matching_es;
+	int			i;
+
+	RETURN_CACHE_IF_AVAILABLE(ec, cache, ec_source_indexes);
+
+	matching_es = NULL;
+	i = bms_next_member(relids, -1);
 
 	if (i >= 0)
 	{
@@ -3563,6 +3651,8 @@ get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
 	/* leave only the sources belonging to this EquivalenceClass */
 	matching_es = bms_int_members(matching_es, ec->ec_source_indexes);
 
+	STORE_RESULT_TO_CACHE(matching_es, cache, ec_source_indexes);
+
 	return matching_es;
 }
 
@@ -3575,10 +3665,15 @@ get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
  * Returns a newly allocated Bitmapset which the caller is free to modify.
  */
 Bitmapset *
-get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids relids, ECIndexCache *cache)
 {
-	Bitmapset  *matching_es = NULL;
-	int			i = bms_next_member(relids, -1);
+	Bitmapset  *matching_es;
+	int			i;
+
+	RETURN_CACHE_IF_AVAILABLE(ec, cache, ec_source_indexes_strict);
+
+	matching_es = NULL;
+	i = bms_next_member(relids, -1);
 
 	if (i >= 0)
 	{
@@ -3608,6 +3703,8 @@ get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids rel
 	/* leave only the sources belonging to this EquivalenceClass */
 	matching_es = bms_int_members(matching_es, ec->ec_source_indexes);
 
+	STORE_RESULT_TO_CACHE(matching_es, cache, ec_source_indexes_strict);
+
 	return matching_es;
 }
 
@@ -3620,10 +3717,15 @@ get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids rel
  * Returns a newly allocated Bitmapset which the caller is free to modify.
  */
 Bitmapset *
-get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids, ECIndexCache *cache)
 {
-	Bitmapset  *matching_eds = NULL;
-	int			i = bms_next_member(relids, -1);
+	Bitmapset  *matching_eds;
+	int			i;
+
+	RETURN_CACHE_IF_AVAILABLE(ec, cache, ec_derive_indexes);
+
+	matching_eds = NULL;
+	i = bms_next_member(relids, -1);
 
 	if (i >= 0)
 	{
@@ -3653,6 +3755,8 @@ get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
 	/* leave only the derives belonging to this EquivalenceClass */
 	matching_eds = bms_int_members(matching_eds, ec->ec_derive_indexes);
 
+	STORE_RESULT_TO_CACHE(matching_eds, cache, ec_derive_indexes);
+
 	return matching_eds;
 }
 
@@ -3665,10 +3769,15 @@ get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
  * Returns a newly allocated Bitmapset which the caller is free to modify.
  */
 Bitmapset *
-get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids relids, ECIndexCache *cache)
 {
-	Bitmapset  *matching_eds = NULL;
-	int			i = bms_next_member(relids, -1);
+	Bitmapset  *matching_eds;
+	int			i;
+
+	RETURN_CACHE_IF_AVAILABLE(ec, cache, ec_derive_indexes_strict);
+
+	matching_eds = NULL;
+	i = bms_next_member(relids, -1);
 
 	if (i >= 0)
 	{
@@ -3698,5 +3807,7 @@ get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids rel
 	/* leave only the derives belonging to this EquivalenceClass */
 	matching_eds = bms_int_members(matching_eds, ec->ec_derive_indexes);
 
+	STORE_RESULT_TO_CACHE(matching_eds, cache, ec_derive_indexes_strict);
+
 	return matching_eds;
 }
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index d1f68ecf64..0604bf2699 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1989,7 +1989,9 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 			continue;
 
 		/* compute score */
-		matching_ems = get_ecmember_indexes(root, oeclass, joinrel->relids, false, false);
+		matching_ems = get_ecmember_indexes(root, oeclass, joinrel->relids,
+											false, false,
+											&joinrel->ec_index_cache);
 		other_parent_ems = bms_difference(oeclass->ec_nonchild_indexes, oeclass->ec_norel_indexes);
 		interesting_ems = bms_difference(other_parent_ems, matching_ems);
 
diff --git a/src/backend/optimizer/util/appendinfo.c b/src/backend/optimizer/util/appendinfo.c
index 62cccf9d87..d1a549d377 100644
--- a/src/backend/optimizer/util/appendinfo.c
+++ b/src/backend/optimizer/util/appendinfo.c
@@ -454,6 +454,9 @@ adjust_appendrel_attrs_mutator(Node *node,
 		newinfo->outer_selec = -1;
 		newinfo->left_em = NULL;
 		newinfo->right_em = NULL;
+		InitECIndexCache(&newinfo->left_ec_index_cache);
+		InitECIndexCache(&newinfo->right_ec_index_cache);
+		InitECIndexCache(&newinfo->clause_ec_index_cache);
 		newinfo->scansel_cache = NIL;
 		newinfo->left_bucketsize = -1;
 		newinfo->right_bucketsize = -1;
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 7fc86aeb0d..a4b2f8fa17 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -237,6 +237,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
 	rel->eclass_member_indexes = NULL;
 	rel->eclass_source_indexes = NULL;
 	rel->eclass_derive_indexes = NULL;
+	InitECIndexCache(&rel->ec_index_cache);
 	rel->subroot = NULL;
 	rel->subplan_params = NIL;
 	rel->rel_parallel_workers = -1; /* set up in get_relation_info */
@@ -652,6 +653,7 @@ build_join_rel(PlannerInfo *root,
 	joinrel->eclass_member_indexes = NULL;
 	joinrel->eclass_source_indexes = NULL;
 	joinrel->eclass_derive_indexes = NULL;
+	InitECIndexCache(&joinrel->ec_index_cache);
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->rel_parallel_workers = -1;
@@ -841,6 +843,7 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
 	joinrel->eclass_member_indexes = NULL;
 	joinrel->eclass_source_indexes = NULL;
 	joinrel->eclass_derive_indexes = NULL;
+	InitECIndexCache(&joinrel->ec_index_cache);
 	joinrel->subroot = NULL;
 	joinrel->subplan_params = NIL;
 	joinrel->amflags = 0;
@@ -1268,6 +1271,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;
+	InitECIndexCache(&upperrel->ec_index_cache);
 
 	root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
 
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index ef8df3d098..3eb1fd81c2 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -206,6 +206,9 @@ make_restrictinfo_internal(PlannerInfo *root,
 	restrictinfo->right_ec = NULL;
 	restrictinfo->left_em = NULL;
 	restrictinfo->right_em = NULL;
+	InitECIndexCache(&restrictinfo->left_ec_index_cache);
+	InitECIndexCache(&restrictinfo->right_ec_index_cache);
+	InitECIndexCache(&restrictinfo->clause_ec_index_cache);
 	restrictinfo->scansel_cache = NIL;
 
 	restrictinfo->outer_is_left = false;
@@ -360,6 +363,9 @@ commute_restrictinfo(RestrictInfo *rinfo, Oid comm_op)
 	result->right_ec = rinfo->left_ec;
 	result->left_em = rinfo->right_em;
 	result->right_em = rinfo->left_em;
+	InitECIndexCache(&result->left_ec_index_cache);
+	InitECIndexCache(&result->right_ec_index_cache);
+	InitECIndexCache(&result->clause_ec_index_cache);
 	result->scansel_cache = NIL;	/* not worth updating this */
 	if (rinfo->hashjoinoperator == clause->opno)
 		result->hashjoinoperator = comm_op;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index bf6389fee4..34c1ea03e8 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -556,6 +556,49 @@ typedef struct PartitionSchemeData
 
 typedef struct PartitionSchemeData *PartitionScheme;
 
+/*
+ * ECIndexCache
+ *
+ * Storage where we cache the result of get_ecmember_indexes and other similar
+ * functions. See comments above the function for details.
+ *
+ * TODO: Is this good place of this struct?
+ */
+
+#define GET_EC_INDEX_CACHE_ARRAY_INDEX(with_children, with_norel_members) \
+	((with_children) << 1 | (with_norel_members))
+
+struct EquivalenceClass;
+
+typedef struct ECIndexCache
+{
+	struct EquivalenceClass *ec;
+	Bitmapset  *ecmember_indexes[4];
+	Bitmapset  *ecmember_indexes_strict[4];
+	Bitmapset  *ec_source_indexes;
+	Bitmapset  *ec_source_indexes_strict;
+	Bitmapset  *ec_derive_indexes;
+	Bitmapset  *ec_derive_indexes_strict;
+} ECIndexCache;
+
+static inline void InitECIndexCache(ECIndexCache *cache)
+{
+	/* TODO */
+	cache->ec = NULL;
+	cache->ecmember_indexes[0] = NULL;
+	cache->ecmember_indexes[1] = NULL;
+	cache->ecmember_indexes[2] = NULL;
+	cache->ecmember_indexes[3] = NULL;
+	cache->ecmember_indexes_strict[0] = NULL;
+	cache->ecmember_indexes_strict[1] = NULL;
+	cache->ecmember_indexes_strict[2] = NULL;
+	cache->ecmember_indexes_strict[3] = NULL;
+	cache->ec_source_indexes = NULL;
+	cache->ec_source_indexes_strict = NULL;
+	cache->ec_derive_indexes = NULL;
+	cache->ec_derive_indexes_strict = NULL;
+}
+
 /*----------
  * RelOptInfo
  *		Per-relation information for planning/optimization
@@ -916,6 +959,12 @@ typedef struct RelOptInfo
 	 */
 	Bitmapset  *eclass_derive_indexes;
 
+	/*
+	 * ECIndexCache corresponding to this rel's relids.
+	 * TODO: The following usage of pg_node_attr is wrong.
+	 */
+	ECIndexCache	ec_index_cache pg_node_attr(equal_ignore, read_write_ignore);
+
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	/* wanted number of parallel workers */
@@ -2557,6 +2606,15 @@ typedef struct RestrictInfo
 	/* EquivalenceMember for righthand */
 	EquivalenceMember *right_em pg_node_attr(equal_ignore);
 
+	/*
+	 * ECIndexCaches corresponding to this rinfo's left_relids, right_relids,
+	 * and clause_relids.
+	 * TODO: The following usage of pg_node_attr is wrong.
+	 */
+	ECIndexCache left_ec_index_cache pg_node_attr(equal_ignore, read_write_ignore);
+	ECIndexCache right_ec_index_cache pg_node_attr(equal_ignore, read_write_ignore);
+	ECIndexCache clause_ec_index_cache pg_node_attr(equal_ignore, read_write_ignore);
+
 	/*
 	 * List of MergeScanSelCache structs.  Those aren't Nodes, so hard to
 	 * copy; instead replace with NIL.  That has the effect that copying will
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f6835f80f5..0051cf9dcf 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -189,28 +189,40 @@ extern bool eclass_useful_for_merging(PlannerInfo *root,
 extern bool is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist);
 extern bool is_redundant_with_indexclauses(RestrictInfo *rinfo,
 										   List *indexclauses);
+/*
+ * TODO: Callers of the following function must not modify the returned value
+ * because they are cached. I think we should mark them 'const Bitmapset *'.
+ * Currently, I have not do that because we have to change the declarations of
+ * 'macthing_ems', where we store the returned Bitmapset.
+ */
 extern Bitmapset *get_ecmember_indexes(PlannerInfo *root,
 										   EquivalenceClass *ec,
 										   Relids relids,
 										   bool with_children,
-										   bool with_norel_members);
+										   bool with_norel_members,
+										   ECIndexCache *cache);
 extern Bitmapset *get_ecmember_indexes_strict(PlannerInfo *root,
 											  EquivalenceClass *ec,
 											  Relids relids,
 											  bool with_children,
-											  bool with_norel_members);
+											  bool with_norel_members,
+											  ECIndexCache *cache);
 extern Bitmapset *get_ec_source_indexes(PlannerInfo *root,
 										EquivalenceClass *ec,
-										Relids relids);
+										Relids relids,
+										ECIndexCache *cache);
 extern Bitmapset *get_ec_source_indexes_strict(PlannerInfo *root,
 											   EquivalenceClass *ec,
-											   Relids relids);
+											   Relids relids,
+											   ECIndexCache *cache);
 extern Bitmapset *get_ec_derive_indexes(PlannerInfo *root,
 										EquivalenceClass *ec,
-										Relids relids);
+										Relids relids,
+										ECIndexCache *cache);
 extern Bitmapset *get_ec_derive_indexes_strict(PlannerInfo *root,
 										EquivalenceClass *ec,
-										Relids relids);
+										Relids relids,
+										ECIndexCache *cache);
 
 /*
  * pathkeys.c
-- 
2.35.3.windows.1