v6-0003-Implement-iterators.patch

From fcef5092a17e36fdd5798096ee362aff2b23f55c Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Wed, 14 Sep 2022 09:56:42 +0900
Subject: [PATCH v6 3/3] Implement iterators

---
 contrib/postgres_fdw/postgres_fdw.c     |  24 +-
 src/backend/optimizer/path/equivclass.c | 382 +++++++++++++++++++-----
 src/include/nodes/pathnodes.h           |  68 +++++
 src/include/optimizer/paths.h           | 150 +++++++++-
 4 files changed, 537 insertions(+), 87 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index e8996456be..e4f6aa33b1 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7412,15 +7412,13 @@ conversion_error_callback(void *arg)
 EquivalenceMember *
 find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 {
-	Bitmapset *matching_ems;
-	int		i = -1;
+	EquivalenceMember *em;
+	EquivalenceMemberIterator it;
 
-	matching_ems = get_ecmember_indexes(root, ec, rel->relids, true, false);
+	get_ecmember_indexes_iterator(&it, root, ec, rel->relids, true, false, false);
 
-	while ((i = bms_next_member(matching_ems, i)) >= 0)
+	while ((em = get_next_matching_member(root, &it)) != NULL)
 	{
-		EquivalenceMember *em = list_nth_node(EquivalenceMember, root->eq_members, i);
-
 		/*
 		 * Note we require !bms_is_empty, else we'd accept constant
 		 * expressions which are not suitable for the purpose.
@@ -7459,9 +7457,9 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 	{
 		Expr	   *expr = (Expr *) lfirst(lc1);
 		Index		sgref = get_pathtarget_sortgroupref(target, i);
-		Bitmapset  *matching_ems;
+		EquivalenceMember *em;
+		EquivalenceMemberStrictIterator it;
 		Relids		expr_relids;
-		int			j;
 
 		/* Ignore non-sort expressions */
 		if (sgref == 0 ||
@@ -7477,14 +7475,11 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 			expr = ((RelabelType *) expr)->arg;
 
 		expr_relids = pull_varnos(root, (Node *) expr);
-		matching_ems = get_ecmember_indexes_strict(root, ec, expr_relids,
-												   false, false);
+		get_ecmember_indexes_strict_iterator(&it, root, ec, expr_relids,
+											 false, false, false);
 		/* Locate an EquivalenceClass member matching this expr, if any */
-		j = -1;
-		while ((j = bms_next_member(matching_ems, j)) >= 0)
+		while ((em = get_next_matching_member_strict(root, &it)) != NULL)
 		{
-			EquivalenceMember *em = list_nth_node(EquivalenceMember,
-												  root->eq_members, j);
 			Expr	   *em_expr;
 
 			/* don't expect constants */
@@ -7507,7 +7502,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/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 5f0d2bafd4..3207c7e35a 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -663,7 +663,34 @@ add_eq_member(PlannerInfo *root, EquivalenceClass *ec, Expr *expr,
 	root->eq_members = lappend(root->eq_members, em);
 
 	/* record exprs with no relids */
-	if (bms_is_empty(expr_relids))
+	/*
+	 * TODO: I had to use relids instead of expr_relids to pass regression tests.
+	 * This is probably related to get_ecmember_indexes[_strict]_iterator
+	 * functions, which is quoted below.
+	 *
+	 * =====
+	 * void
+	 * get_ecmember_indexes_iterator(...)
+	 * {
+	 * 	...
+	 * 	else
+	 * 	{
+	 * 		Bitmapset *index;
+	 *
+	 * 		it->check_on_iterate = !caller_needs_recheck;
+	 *
+	 * 		index =
+	 * 			with_children ? ec->ec_member_indexes : ec->ec_nonchild_indexes;
+	 * 		if (!with_norel_members)
+	 * 			index = bms_difference(index, ec->ec_norel_indexes);
+	 * 			^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+	 *
+	 * 		it->index = index;
+	 * 	}
+	 * }
+	 * =====
+	 */
+	if (bms_is_empty(relids))
 		ec->ec_norel_indexes = bms_add_member(ec->ec_norel_indexes, em_index);
 
 	if (is_child)
@@ -748,8 +775,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		Bitmapset		 *matching_ems;
-		int			i;
+		EquivalenceMember *cur_em;
+		EquivalenceMemberStrictIterator it;
 
 		/*
 		 * Never match to a volatile EC, except when we are looking at another
@@ -764,15 +791,11 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
 			continue;
 
-		matching_ems = get_ecmember_indexes_strict(root, cur_ec, expr_relids,
-												   true, true);
+		get_ecmember_indexes_strict_iterator(&it, root, cur_ec, expr_relids,
+											 true, true, true);
 
-		i = -1;
-		while ((i = bms_next_member(matching_ems, i)) >= 0)
+		while ((cur_em = get_next_matching_member_strict(root, &it)) != NULL)
 		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
-													  root->eq_members, i);
-
 			/*
 			 * Ignore child members unless they match the request.
 			 */
@@ -909,22 +932,19 @@ find_ec_member_matching_expr(PlannerInfo *root,
 							 Expr *expr,
 							 Relids relids)
 {
-	Bitmapset  *matching_ems;
 	Relids		expr_relids;
-	int			i;
+	EquivalenceMember *em;
+	EquivalenceMemberStrictIterator it;
 
 	/* We ignore binary-compatible relabeling on both ends */
 	while (expr && IsA(expr, RelabelType))
 		expr = ((RelabelType *) expr)->arg;
 
 	expr_relids = pull_varnos(root, (Node *) expr);
-	matching_ems = get_ecmember_indexes_strict(root, ec, expr_relids, true, true);
+	get_ecmember_indexes_strict_iterator(&it, root, ec, expr_relids, true, true, true);
 
-	i = -1;
-	while ((i = bms_next_member(matching_ems, i)) >= 0)
+	while ((em = get_next_matching_member_strict(root, &it)) != NULL)
 	{
-		EquivalenceMember *em = list_nth_node(EquivalenceMember,
-											  root->eq_members, i);
 		Expr	   *emexpr;
 
 		/*
@@ -1693,9 +1713,9 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 	List	   *new_members = NIL;
 	List	   *outer_members = NIL;
 	List	   *inner_members = NIL;
-	Bitmapset  *matching_ems;
+	EquivalenceMember *cur_em;
+	EquivalenceMemberIterator it;
 	ListCell   *lc1;
-	int			i;
 
 	/*
 	 * First, scan the EC to identify member values that are computable at the
@@ -1706,14 +1726,10 @@ 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);
+	get_ecmember_indexes_iterator(&it, root, ec, join_relids, true, false, true);
 
-	i = -1;
-	while ((i = bms_next_member(matching_ems, i)) >= 0)
+	while ((cur_em = get_next_matching_member(root, &it)) != NULL)
 	{
-		EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
-												  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
@@ -1872,16 +1888,13 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
 										Relids nominal_inner_relids,
 										RelOptInfo *inner_rel)
 {
-	Bitmapset  *matching_es;
 	List	   *result = NIL;
-	int			i;
+	RestrictInfo *restrictinfo;
+	RestrictInfoIterator it;
 
-	matching_es = get_ec_source_indexes(root, ec, nominal_join_relids);
-	i = -1;
-	while ((i = bms_next_member(matching_es, i)) >= 0)
+	get_ec_source_indexes_iterator(&it, root, ec, nominal_join_relids, true);
+	while ((restrictinfo = get_next_matching_rinfo(root, &it)) != NULL)
 	{
-		RestrictInfo *restrictinfo = list_nth_node(RestrictInfo,
-												   root->eq_sources, i);
 		Relids		clause_relids = restrictinfo->required_relids;
 
 		if (bms_is_subset(clause_relids, nominal_join_relids) &&
@@ -2258,7 +2271,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		Bitmapset		 *matching_ems;
+		EquivalenceMember *cur_em;
+		EquivalenceMemberStrictIterator it;
 		bool		match;
 		int			i;
 
@@ -2275,15 +2289,11 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 			continue;
 		/* Does it contain a match to outervar? */
 		match = false;
-		matching_ems = get_ecmember_indexes_strict(root, cur_ec,
-												   outer_relids,
-												   false, true);
-		i = -1;
-		while ((i = bms_next_member(matching_ems, i)) >= 0)
+		get_ecmember_indexes_strict_iterator(&it, root, cur_ec,
+											 outer_relids,
+											 false, true, true);
+		while ((cur_em = get_next_matching_member_strict(root, &it)) != NULL)
 		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
-													  root->eq_members, i);
-
 			Assert(!cur_em->em_is_child);	/* no children yet */
 			if (equal(outervar, cur_em->em_expr))
 			{
@@ -2383,7 +2393,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 		EquivalenceMember *coal_em = NULL;
-		Bitmapset		  *matching_ems;
+		EquivalenceMemberStrictIterator it;
 		bool		match;
 		bool		matchleft;
 		bool		matchright;
@@ -2415,14 +2425,12 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 		 * the two column types). Is it OK to strip implicit coercions from
 		 * the COALESCE arguments?
 		 */
-		matching_ems = get_ecmember_indexes_strict(root, cur_ec,
-												   rinfo->clause_relids, true,
-												   false);
+		get_ecmember_indexes_strict_iterator(&it, root, cur_ec,
+											 rinfo->clause_relids, true,
+											 false, true);
 		match = false;
-		i = -1;
-		while ((i = bms_next_member(matching_ems, i)) >= 0)
+		while ((coal_em = get_next_matching_member_strict(root, &it)) != NULL)
 		{
-			coal_em = list_nth_node(EquivalenceMember, root->eq_members, i);
 			Assert(!coal_em->em_is_child);	/* no children yet */
 			if (IsA(coal_em->em_expr, CoalesceExpr))
 			{
@@ -2437,7 +2445,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 
 				if (equal(leftvar, cfirst) && equal(rightvar, csecond))
 				{
-					coal_idx = i;
+					coal_idx = it.position;
 					match = true;
 					break;
 				}
@@ -2766,8 +2774,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);
-		Bitmapset		 *matching_ems;
-		int			j;
+		EquivalenceMember *cur_em;
+		EquivalenceMemberIterator it;
+		int					final_member;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2784,13 +2793,18 @@ 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);
+		get_ecmember_indexes_iterator(&it, root, cur_ec, top_parent_relids, false, false, false);
 
-		j = -1;
-		while ((j = bms_next_member(matching_ems, j)) >= 0)
-		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember, root->eq_members, j);
+		/*
+		 * TODO: To skip newly added EMs, we get final member's index.
+		 * However, touching inside of EquivalenceMemberIterator is not ideal
+		 * solution.
+		 */
+		final_member = bms_prev_member(cur_ec->ec_member_indexes, -1);
 
+		while ((cur_em = get_next_matching_member(root, &it)) != NULL
+				&& it.position <= final_member)
+		{
 			Assert(!cur_em->em_is_const);
 			Assert(!cur_em->em_is_child);
 			Assert(bms_overlap(cur_em->em_relids, top_parent_relids));
@@ -2893,8 +2907,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);
-		Bitmapset		 *matching_ems;
-		int			j;
+		EquivalenceMember *cur_em;
+		EquivalenceMemberIterator it;
+		int					final_member;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2911,13 +2926,18 @@ 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);
+		get_ecmember_indexes_iterator(&it, root, cur_ec, top_parent_relids, false, false, false);
 
-		j = -1;
-		while ((j = bms_next_member(matching_ems, j)) >= 0)
-		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember, root->eq_members, j);
+		/*
+		 * TODO: To skip newly added EMs, we get final member's index.
+		 * However, touching inside of EquivalenceMemberIterator is not ideal
+		 * solution.
+		 */
+		final_member = bms_prev_member(cur_ec->ec_member_indexes, -1);
 
+		while ((cur_em = get_next_matching_member(root, &it)) != NULL
+				&& it.position <= final_member)
+		{
 			Assert(!cur_em->em_is_const);
 			Assert(!cur_em->em_is_child);
 			Assert(bms_overlap(cur_em->em_relids, top_parent_relids));
@@ -3038,7 +3058,7 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
 		EquivalenceMember *cur_em;
-		Bitmapset		  *matching_ems;
+		EquivalenceMemberIterator it;
 		int					j;
 
 		/* Sanity check eclass_indexes only contain ECs for rel */
@@ -3062,13 +3082,9 @@ 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);
-		cur_em = NULL;
-		j = -1;
-		while ((j = bms_next_member(matching_ems, j)) >= 0)
+		get_ecmember_indexes_iterator(&it, root, cur_ec, rel->relids, true, false, true);
+		while ((cur_em = get_next_matching_member(root, &it)) != NULL)
 		{
-			cur_em = list_nth_node(EquivalenceMember, root->eq_members, j);
-
 			if (bms_equal(cur_em->em_relids, rel->relids) &&
 				callback(root, rel, cur_ec, cur_em, callback_arg))
 				break;
@@ -3477,6 +3493,51 @@ get_ecmember_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids,
 	return matching_ems;
 }
 
+/*
+ * get_ecmember_indexes_iterator
+ *		Initializes an EquivalenceMemberIterator for the given arguments so
+ *		that the iterator enumerates the EquivalenceMembers obtained by
+ *		get_ecmember_indexes().
+ *		If the caller_needs_recheck is true, the EquivalenceMembers to be
+ *		iterated may have false positives, so the caller must check the
+ *		desired condition.
+ */
+void
+get_ecmember_indexes_iterator(EquivalenceMemberIterator *it,
+							  PlannerInfo *root,
+							  EquivalenceClass *ec,
+							  Relids relids,
+							  bool with_children,
+							  bool with_norel_members,
+							  bool caller_needs_recheck)
+{
+	it->relids = relids;
+	it->position = -1;
+
+	if (root->simple_rel_array_size > EC_MEMBER_ITERATOR_THRESHOLD)
+	{
+		/* We use index */
+		it->check_on_iterate = false;
+		it->index = get_ecmember_indexes(root, ec, relids,
+										 with_children,
+										 with_norel_members);
+	}
+	else
+	{
+		Bitmapset *index;
+
+		/* We don't use index, perform linear search instead */
+		it->check_on_iterate = !caller_needs_recheck;
+
+		index =
+			with_children ? ec->ec_member_indexes : ec->ec_nonchild_indexes;
+		if (!with_norel_members)
+			index = bms_difference(index, ec->ec_norel_indexes);
+
+		it->index = index;
+	}
+}
+
 /*
  * get_ecmember_indexes_strict
  *		Returns a Bitmapset with indexes into root->eq_members for all
@@ -3524,6 +3585,51 @@ get_ecmember_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
 	return matching_ems;
 }
 
+/*
+ * get_ecmember_indexes_strict_iterator
+ *		Initializes an EquivalenceMemberIterator for the given arguments so
+ *		that the iterator enumerates the EquivalenceMembers obtained by
+ *		get_ecmember_indexes_strict().
+ *		If the caller_needs_recheck is true, the EquivalenceMembers to be
+ *		iterated may have false positives, so the caller must check the
+ *		desired condition.
+ */
+void
+get_ecmember_indexes_strict_iterator(EquivalenceMemberStrictIterator *it,
+									 PlannerInfo *root,
+									 EquivalenceClass *ec,
+									 Relids relids,
+									 bool with_children,
+									 bool with_norel_members,
+									 bool caller_needs_recheck)
+{
+	it->relids = relids;
+	it->position = -1;
+
+	if (root->simple_rel_array_size > EC_MEMBER_ITERATOR_THRESHOLD)
+	{
+		/* We use index */
+		it->check_on_iterate = false;
+		it->index = get_ecmember_indexes_strict(root, ec, relids,
+												with_children,
+												with_norel_members);
+	}
+	else
+	{
+		Bitmapset *index;
+
+		/* We don't use index, perform linear search instead */
+		it->check_on_iterate = !caller_needs_recheck;
+
+		index =
+			with_children ? ec->ec_member_indexes : ec->ec_nonchild_indexes;
+		if (!with_norel_members)
+			index = bms_difference(index, ec->ec_norel_indexes);
+
+		it->index = index;
+	}
+}
+
 /*
  * get_ec_source_indexes
  *		Returns a Bitmapset with indexes into root->eq_sources for all
@@ -3569,6 +3675,40 @@ get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
 	return matching_es;
 }
 
+/*
+ * get_ec_source_indexes_iterator
+ *		Initializes an RestrictInfoIterator for the given arguments so
+ *		that the iterator enumerates the RestrictInfos obtained by
+ *		get_ec_source_indexes().
+ *		If the caller_needs_recheck is true, the RestrictInfos to be
+ *		iterated may have false positives, so the caller must check the
+ *		desired condition.
+ */
+void
+get_ec_source_indexes_iterator(RestrictInfoIterator *it,
+							   PlannerInfo *root,
+							   EquivalenceClass *ec,
+							   Relids relids,
+							   bool caller_needs_recheck)
+{
+	it->relids = relids;
+	it->position = -1;
+	it->members = root->eq_sources;
+
+	if (root->simple_rel_array_size > EC_MEMBER_ITERATOR_THRESHOLD)
+	{
+		/* We use index */
+		it->check_on_iterate = false;
+		it->indexes = get_ec_source_indexes(root, ec, relids);
+	}
+	else
+	{
+		/* We don't use index, perform linear search instead */
+		it->check_on_iterate = !caller_needs_recheck;
+		it->indexes = ec->ec_source_indexes;
+	}
+}
+
 /*
  * get_ec_source_indexes_strict
  *		Returns a Bitmapset with indexes into root->eq_sources for all
@@ -3614,6 +3754,40 @@ get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids rel
 	return matching_es;
 }
 
+/*
+ * get_ec_source_indexes_strict_iterator
+ *		Initializes an RestrictInfoIterator for the given arguments so
+ *		that the iterator enumerates the RestrictInfos obtained by
+ *		get_ec_source_indexes_strict().
+ *		If the caller_needs_recheck is true, the RestrictInfos to be
+ *		iterated may have false positives, so the caller must check the
+ *		desired condition.
+ */
+void
+get_ec_source_indexes_strict_iterator(RestrictInfoStrictIterator *it,
+									  PlannerInfo *root,
+									  EquivalenceClass *ec,
+									  Relids relids,
+									  bool caller_needs_recheck)
+{
+	it->relids = relids;
+	it->position = -1;
+	it->members = root->eq_sources;
+
+	if (root->simple_rel_array_size > EC_MEMBER_ITERATOR_THRESHOLD)
+	{
+		/* We use index */
+		it->check_on_iterate = false;
+		it->indexes = get_ec_source_indexes_strict(root, ec, relids);
+	}
+	else
+	{
+		/* We don't use index, perform linear search instead */
+		it->check_on_iterate = !caller_needs_recheck;
+		it->indexes = ec->ec_source_indexes;
+	}
+}
+
 /*
  * get_ec_derive_indexes
  *		Returns a Bitmapset with indexes into root->eq_derives for all
@@ -3659,6 +3833,40 @@ get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
 	return matching_eds;
 }
 
+/*
+ * get_ec_derive_indexes_iterator
+ *		Initializes an RestrictInfoIterator for the given arguments so
+ *		that the iterator enumerates the RestrictInfos obtained by
+ *		get_ec_derive_indexes().
+ *		If the caller_needs_recheck is true, the RestrictInfos to be
+ *		iterated may have false positives, so the caller must check the
+ *		desired condition.
+ */
+void
+get_ec_derive_indexes_iterator(RestrictInfoIterator *it,
+							   PlannerInfo *root,
+							   EquivalenceClass *ec,
+							   Relids relids,
+							   bool caller_needs_recheck)
+{
+	it->relids = relids;
+	it->position = -1;
+	it->members = root->eq_derives;
+
+	if (root->simple_rel_array_size > EC_MEMBER_ITERATOR_THRESHOLD)
+	{
+		/* We use index */
+		it->check_on_iterate = false;
+		it->indexes = get_ec_derive_indexes(root, ec, relids);
+	}
+	else
+	{
+		/* We don't use index, perform linear search instead */
+		it->check_on_iterate = !caller_needs_recheck;
+		it->indexes = ec->ec_derive_indexes;
+	}
+}
+
 /*
  * get_ec_derive_indexes_strict
  *		Returns a Bitmapset with indexes into root->eq_derives for all
@@ -3703,3 +3911,37 @@ get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec, Relids rel
 
 	return matching_eds;
 }
+
+/*
+ * get_ec_derive_indexes_strict_iterator
+ *		Initializes an RestrictInfoIterator for the given arguments so
+ *		that the iterator enumerates the RestrictInfos obtained by
+ *		get_ec_derive_indexes_strict().
+ *		If the caller_needs_recheck is true, the RestrictInfos to be
+ *		iterated may have false positives, so the caller must check the
+ *		desired condition.
+ */
+void
+get_ec_derive_indexes_strict_iterator(RestrictInfoStrictIterator *it,
+									  PlannerInfo *root,
+									  EquivalenceClass *ec,
+									  Relids relids,
+									  bool caller_needs_recheck)
+{
+	it->relids = relids;
+	it->position = -1;
+	it->members = root->eq_derives;
+
+	if (root->simple_rel_array_size > EC_MEMBER_ITERATOR_THRESHOLD)
+	{
+		/* We use index */
+		it->check_on_iterate = false;
+		it->indexes = get_ec_derive_indexes_strict(root, ec, relids);
+	}
+	else
+	{
+		/* We don't use index, perform linear search instead */
+		it->check_on_iterate = !caller_needs_recheck;
+		it->indexes = ec->ec_derive_indexes;
+	}
+}
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index bf6389fee4..64306990fa 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1378,6 +1378,38 @@ typedef struct EquivalenceMember
 	Oid			em_datatype;	/* the "nominal type" used by the opfamily */
 } EquivalenceMember;
 
+typedef struct EquivalenceMemberIterator
+{
+	/* Do we have to check the condition on iterate? */
+	bool		check_on_iterate;
+
+	/* Last found index of the Bitmapset 'index' or -1 */
+	int			position;
+
+	/* Relids for checking the condition */
+	Relids		relids;
+
+	/* Indexes of the EquivalenceMembers to be iterated */
+	Bitmapset  *index;
+} EquivalenceMemberIterator;
+
+typedef struct EquivalenceMemberStrictIterator
+{
+	/* Do we have to check the condition on iterate? */
+	bool		check_on_iterate;
+
+	/* Last found index of the Bitmapset 'index' or -1 */
+	int			position;
+
+	/* Relids for checking the condition */
+	Relids		relids;
+
+	/* Indexes of the EquivalenceMembers to be iterated */
+	Bitmapset  *index;
+} EquivalenceMemberStrictIterator;
+
+#define EC_MEMBER_ITERATOR_THRESHOLD 32
+
 /*
  * PathKeys
  *
@@ -2607,6 +2639,42 @@ typedef struct RestrictInfo
 	((rinfo)->is_pushed_down || \
 	 !bms_is_subset((rinfo)->required_relids, joinrelids))
 
+typedef struct RestrictInfoIterator
+{
+	/* Do we have to check the condition on iterate? */
+	bool		check_on_iterate;
+
+	/* Last found index of the Bitmapset 'index' or -1 */
+	int			position;
+
+	/* Relids for checking the condition */
+	Relids		relids;
+
+	/* Indexes of the RestrictInfos to be iterated */
+	Bitmapset  *indexes;
+
+	/* RestrictInfos that the 'indexes' point to */
+	List	   *members;
+} RestrictInfoIterator;
+
+typedef struct RestrictInfoStrictIterator
+{
+	/* Do we have to check the condition on iterate? */
+	bool		check_on_iterate;
+
+	/* Last found index of the Bitmapset 'index' or -1 */
+	int			position;
+
+	/* Relids for checking the condition */
+	Relids		relids;
+
+	/* Indexes of the RestrictInfos to be iterated */
+	Bitmapset  *indexes;
+
+	/* RestrictInfos that the 'indexes' point to */
+	List	   *members;
+} RestrictInfoStrictIterator;
+
 /*
  * Since mergejoinscansel() is a relatively expensive function, and would
  * otherwise be invoked many times while planning a large join tree,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f6835f80f5..d78dadb074 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -194,23 +194,169 @@ extern Bitmapset *get_ecmember_indexes(PlannerInfo *root,
 										   Relids relids,
 										   bool with_children,
 										   bool with_norel_members);
+extern void get_ecmember_indexes_iterator(EquivalenceMemberIterator *it,
+										  PlannerInfo *root,
+										  EquivalenceClass *ec,
+										  Relids relids,
+										  bool with_children,
+										  bool with_norel_members,
+										  bool caller_needs_recheck);
 extern Bitmapset *get_ecmember_indexes_strict(PlannerInfo *root,
 											  EquivalenceClass *ec,
 											  Relids relids,
 											  bool with_children,
 											  bool with_norel_members);
+extern void get_ecmember_indexes_strict_iterator(EquivalenceMemberStrictIterator *it,
+												 PlannerInfo *root,
+												 EquivalenceClass *ec,
+												 Relids relids,
+												 bool with_children,
+												 bool with_norel_members,
+												 bool caller_needs_recheck);
 extern Bitmapset *get_ec_source_indexes(PlannerInfo *root,
 										EquivalenceClass *ec,
 										Relids relids);
+extern void get_ec_source_indexes_iterator(RestrictInfoIterator *it,
+										   PlannerInfo *root,
+										   EquivalenceClass *ec,
+										   Relids relids,
+										   bool caller_needs_recheck);
 extern Bitmapset *get_ec_source_indexes_strict(PlannerInfo *root,
 											   EquivalenceClass *ec,
 											   Relids relids);
+extern void get_ec_source_indexes_strict_iterator(RestrictInfoStrictIterator *it,
+												  PlannerInfo *root,
+												  EquivalenceClass *ec,
+												  Relids relids,
+												  bool caller_needs_recheck);
 extern Bitmapset *get_ec_derive_indexes(PlannerInfo *root,
 										EquivalenceClass *ec,
 										Relids relids);
+extern void get_ec_derive_indexes_iterator(RestrictInfoIterator *it,
+										   PlannerInfo *root,
+										   EquivalenceClass *ec,
+										   Relids relids,
+										   bool caller_needs_recheck);
 extern Bitmapset *get_ec_derive_indexes_strict(PlannerInfo *root,
-										EquivalenceClass *ec,
-										Relids relids);
+											   EquivalenceClass *ec,
+											   Relids relids);
+extern void get_ec_derive_indexes_strict_iterator(RestrictInfoStrictIterator *it,
+												  PlannerInfo *root,
+												  EquivalenceClass *ec,
+												  Relids relids,
+												  bool caller_needs_recheck);
+
+/*
+ * Returns the next EquivalenceMember. If the iteration was done, returns NULL.
+ */
+static inline EquivalenceMember *
+get_next_matching_member(PlannerInfo *root, EquivalenceMemberIterator *it)
+{
+	if (!it->check_on_iterate)
+	{
+		if ((it->position = bms_next_member(it->index, it->position)) >= 0)
+			return list_nth_node(EquivalenceMember, root->eq_members, it->position);
+	}
+	else
+	{
+		while ((it->position = bms_next_member(it->index, it->position)) >= 0)
+		{
+			EquivalenceMember *member =
+				list_nth_node(EquivalenceMember, root->eq_members, it->position);
+
+			if (bms_overlap(it->relids, member->em_relids))
+			{
+				return member;
+			}
+		}
+	}
+
+	return NULL;
+}
+
+/*
+ * Returns the next EquivalenceMember. If the iteration was done, returns NULL.
+ */
+static inline EquivalenceMember *
+get_next_matching_member_strict(PlannerInfo *root, EquivalenceMemberStrictIterator *it)
+{
+	if (!it->check_on_iterate)
+	{
+		if ((it->position = bms_next_member(it->index, it->position)) >= 0)
+			return list_nth_node(EquivalenceMember, root->eq_members, it->position);
+	}
+	else
+	{
+		while ((it->position = bms_next_member(it->index, it->position)) >= 0)
+		{
+			EquivalenceMember *member =
+				list_nth_node(EquivalenceMember, root->eq_members, it->position);
+
+			if (bms_is_subset(it->relids, member->em_relids))
+			{
+				return member;
+			}
+		}
+	}
+
+	return NULL;
+}
+
+/*
+ * Returns the next RestrictInfo. If the iteration was done, returns NULL.
+ */
+static inline RestrictInfo *
+get_next_matching_rinfo(PlannerInfo *root, RestrictInfoIterator *it)
+{
+	if (!it->check_on_iterate)
+	{
+		if ((it->position = bms_next_member(it->indexes, it->position)) >= 0)
+			return list_nth_node(RestrictInfo, it->members, it->position);
+	}
+	else
+	{
+		while ((it->position = bms_next_member(it->indexes, it->position)) >= 0)
+		{
+			RestrictInfo *member =
+				list_nth_node(RestrictInfo, it->members, it->position);
+
+			if (bms_overlap(it->relids, member->clause_relids))
+			{
+				return member;
+			}
+		}
+	}
+
+	return NULL;
+}
+
+/*
+ * Returns the next RestrictInfo. If the iteration was done, returns NULL.
+ */
+static inline RestrictInfo *
+get_next_matching_rinfo_strict(PlannerInfo *root, RestrictInfoStrictIterator *it)
+{
+	if (!it->check_on_iterate)
+	{
+		if ((it->position = bms_next_member(it->indexes, it->position)) >= 0)
+			return list_nth_node(RestrictInfo, it->members, it->position);
+	}
+	else
+	{
+		while ((it->position = bms_next_member(it->indexes, it->position)) >= 0)
+		{
+			RestrictInfo *member =
+				list_nth_node(RestrictInfo, it->members, it->position);
+
+			if (bms_is_subset(it->relids, member->clause_relids))
+			{
+				return member;
+			}
+		}
+	}
+
+	return NULL;
+}
 
 /*
  * pathkeys.c
-- 
2.35.3.windows.1