v7-0003-Implement-ECIndexCache.patch

From 5c755bfb9b9e218da55af3110d83e2f0c7566ade Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Wed, 21 Sep 2022 15:17:20 +0900
Subject: [PATCH v7 3/3] Implement ECIndexCache

---
 contrib/postgres_fdw/postgres_fdw.c       |   6 +-
 src/backend/nodes/gen_node_support.pl     |   4 +
 src/backend/optimizer/path/equivclass.c   | 189 ++++++++++++++++++----
 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, 255 insertions(+), 43 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index e8996456be..3acd4d011a 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,
+										INIT_AND_GET_EC_INDEX_CACHE(root, 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..f0947b53c9 100644
--- a/src/backend/nodes/gen_node_support.pl
+++ b/src/backend/nodes/gen_node_support.pl
@@ -168,6 +168,10 @@ my %manual_nodetag_number;
 # EquivalenceClasses are never moved, so just shallow-copy the pointer
 push @scalar_types, qw(EquivalenceClass* EquivalenceMember*);
 
+# ECIndexCache are never moved, so just shallow-copy the pointer
+# TODO: Is this correct?
+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 5f0d2bafd4..fc11b94d38 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,8 @@ 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 =
+			INIT_AND_GET_EC_INDEX_CACHE(root, rinfo->left_ec_index_cache);
 	}
 	else
 	{
@@ -2250,6 +2253,8 @@ 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 =
+			INIT_AND_GET_EC_INDEX_CACHE(root, rinfo->right_ec_index_cache);
 	}
 	inner_nullable_relids = bms_intersect(inner_relids,
 										  rinfo->nullable_relids);
@@ -2277,7 +2282,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 +2423,8 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		 */
 		matching_ems = get_ecmember_indexes_strict(root, cur_ec,
 												   rinfo->clause_relids, true,
-												   false);
+												   false,
+												   INIT_AND_GET_EC_INDEX_CACHE(root, rinfo->clause_ec_index_cache));
 		match = false;
 		i = -1;
 		while ((i = bms_next_member(matching_ems, i)) >= 0)
@@ -2567,8 +2574,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 +2650,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, INIT_AND_GET_EC_INDEX_CACHE(root, rel1->ec_index_cache)),
+								 get_ecmember_indexes_strict(root, ec, rel2->relids, false, false, INIT_AND_GET_EC_INDEX_CACHE(root, rel2->ec_index_cache)));
 
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -2784,7 +2791,9 @@ 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,
+											child_rel->top_parent ? INIT_AND_GET_EC_INDEX_CACHE(root, child_rel->top_parent->ec_index_cache) : NULL);
 
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -2911,7 +2920,9 @@ 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,
+											child_joinrel->top_parent ? INIT_AND_GET_EC_INDEX_CACHE(root, child_joinrel->top_parent->ec_index_cache) : NULL);
 
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -3062,7 +3073,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, INIT_AND_GET_EC_INDEX_CACHE(root, rel->ec_index_cache));
 		cur_em = NULL;
 		j = -1;
 		while ((j = bms_next_member(matching_ems, j)) >= 0)
@@ -3425,6 +3437,57 @@ 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, data, field)	\
+	do															\
+	{															\
+		Bitmapset  *cached_bitmapset;							\
+																\
+		if ((cache) == NULL)									\
+		{														\
+			(data) = NULL;										\
+			break;												\
+		}														\
+																\
+		/* Find the ECIndexCacheData corresponding to */		\
+		/* the 'eclass' */										\
+		(data) = (cache)->data;									\
+		while (true)											\
+		{														\
+			EquivalenceClass   *pointing_ec;					\
+																\
+			Assert((data) < (cache)->data + (cache)->size);		\
+			pointing_ec = (data)->ec;							\
+																\
+			if (pointing_ec == NULL)							\
+			{													\
+				(data)->ec = (eclass);							\
+				break;											\
+			}													\
+			else if (pointing_ec == (eclass))					\
+				break;											\
+			else												\
+				(data)++;										\
+		}														\
+																\
+		/* Try to read the cached value from ECIndexCacheData */\
+		cached_bitmapset = (data)->field;						\
+		if (cached_bitmapset != NULL)							\
+			return cached_bitmapset;							\
+	} while (false)
+
+/* Call this at the end of functions */
+#define STORE_RESULT_TO_CACHE(value, data, field)				\
+	do															\
+	{															\
+		if ((data) != NULL)										\
+			(data)->field = (value);							\
+	} while (false)
+
 /*
  * get_ecmember_indexes
  *		Returns a Bitmapset with indexes into root->eq_members for all
@@ -3437,12 +3500,22 @@ 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)
 {
+	ECIndexCacheData *data;
 	Bitmapset  *matching_ems;
-	Bitmapset  *rel_ems = NULL;
+	Bitmapset  *rel_ems;
 	int			i;
 
+	RETURN_CACHE_IF_AVAILABLE(
+		ec,
+		cache,
+		data,
+		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
@@ -3474,6 +3547,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,
+		data,
+		ecmember_indexes[GET_EC_INDEX_CACHE_ARRAY_INDEX(with_children, with_norel_members)]);
+
 	return matching_ems;
 }
 
@@ -3488,11 +3566,19 @@ 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)
 {
+	ECIndexCacheData *data;
 	Bitmapset  *matching_ems;
 	int			i;
 
+	RETURN_CACHE_IF_AVAILABLE(
+		ec,
+		cache,
+		data,
+		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
@@ -3521,6 +3607,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,
+		data,
+		ecmember_indexes_strict[GET_EC_INDEX_CACHE_ARRAY_INDEX(with_children, with_norel_members)]);
+
 	return matching_ems;
 }
 
@@ -3533,10 +3624,16 @@ 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);
+	ECIndexCacheData *data;
+	Bitmapset  *matching_es;
+	int			i;
+
+	RETURN_CACHE_IF_AVAILABLE(ec, cache, data, ec_source_indexes);
+
+	matching_es = NULL;
+	i = bms_next_member(relids, -1);
 
 	if (i >= 0)
 	{
@@ -3566,6 +3663,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, data, ec_source_indexes);
+
 	return matching_es;
 }
 
@@ -3578,10 +3677,16 @@ 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);
+	ECIndexCacheData *data;
+	Bitmapset  *matching_es;
+	int			i;
+
+	RETURN_CACHE_IF_AVAILABLE(ec, cache, data, ec_source_indexes_strict);
+
+	matching_es = NULL;
+	i = bms_next_member(relids, -1);
 
 	if (i >= 0)
 	{
@@ -3611,6 +3716,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, data, ec_source_indexes_strict);
+
 	return matching_es;
 }
 
@@ -3623,10 +3730,16 @@ 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);
+	ECIndexCacheData *data;
+	Bitmapset  *matching_eds;
+	int			i;
+
+	RETURN_CACHE_IF_AVAILABLE(ec, cache, data, ec_derive_indexes);
+
+	matching_eds = NULL;
+	i = bms_next_member(relids, -1);
 
 	if (i >= 0)
 	{
@@ -3656,6 +3769,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, data, ec_derive_indexes);
+
 	return matching_eds;
 }
 
@@ -3668,10 +3783,16 @@ 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);
+	ECIndexCacheData *data;
+	Bitmapset  *matching_eds;
+	int			i;
+
+	RETURN_CACHE_IF_AVAILABLE(ec, cache, data, ec_derive_indexes_strict);
+
+	matching_eds = NULL;
+	i = bms_next_member(relids, -1);
 
 	if (i >= 0)
 	{
@@ -3701,5 +3822,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, data, ec_derive_indexes_strict);
+
 	return matching_eds;
 }
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index aeacc88d08..dedbcc9a9c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1994,7 +1994,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,
+											INIT_AND_GET_EC_INDEX_CACHE(root, 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..1728c0c016 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;
+		newinfo->left_ec_index_cache = NULL;
+		newinfo->right_ec_index_cache = NULL;
+		newinfo->clause_ec_index_cache = NULL;
 		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..bf0095ab17 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;
+	rel->ec_index_cache = NULL;
 	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;
+	joinrel->ec_index_cache = NULL;
 	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;
+	joinrel->ec_index_cache = NULL;
 	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;
+	upperrel->ec_index_cache = NULL;
 
 	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..ab49747f83 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;
+	restrictinfo->left_ec_index_cache = NULL;
+	restrictinfo->right_ec_index_cache = NULL;
+	restrictinfo->clause_ec_index_cache = NULL;
 	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;
+	result->left_ec_index_cache = NULL;
+	result->right_ec_index_cache = NULL;
+	result->clause_ec_index_cache = NULL;
 	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..4e6d00bc4f 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 ECIndexCacheData
+{
+	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;
+} ECIndexCacheData;
+
+typedef struct ECIndexCache
+{
+	int					size;
+	ECIndexCacheData	data[FLEXIBLE_ARRAY_MEMBER];
+} ECIndexCache;
+
+static inline ECIndexCache *MakeECIndexCache(int size)
+{
+	ECIndexCache* cache =
+		palloc0(offsetof(ECIndexCache, data) + sizeof(ECIndexCacheData) * size);
+
+	cache->size = size;
+	return cache;
+}
+
+#define INIT_AND_GET_EC_INDEX_CACHE(root, cache) \
+	((cache) ? (cache) : ((cache) = MakeECIndexCache(list_length((root)->eq_classes))))
+
 /*----------
  * 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(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(read_write_ignore);
+	ECIndexCache *right_ec_index_cache pg_node_attr(read_write_ignore);
+	ECIndexCache *clause_ec_index_cache pg_node_attr(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