v10-0003-Add-iterators-for-looping-over-EquivalenceMember.patch

From 332896bd0dafaed00fb1faad615f605121c07883 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Sat, 3 Dec 2022 18:02:28 +1300
Subject: [PATCH v10 3/3] Add iterators for looping over EquivalenceMembers

Here we introduce EquivalenceMemberIterator which can be used to search
for EquivalenceMembers matching a given search criteria.  This allows us
to switch between a linear search over all members in an EquivalenceClass
and a bitmap index search over the members.  The latter of these is used
when the number of members in the EquivalenceClass reaches a given
threshold, over which we assume that the index search will be faster.
Currently that threshold is set to 16.  This value may need to be refined
further.
---
 contrib/postgres_fdw/postgres_fdw.c     |  36 +--
 src/backend/optimizer/path/equivclass.c | 312 +++++++++++++++++++-----
 src/include/optimizer/paths.h           |  39 +++
 3 files changed, 307 insertions(+), 80 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index ff1ee9af89..9806802a6a 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7465,15 +7465,13 @@ conversion_error_callback(void *arg)
 EquivalenceMember *
 find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 {
-	Bitmapset *matching_ems;
-	int		i = -1;
+	EquivalenceMemberIterator iter;
+	EquivalenceMember *em;
 
-	matching_ems = get_ecmember_indexes(root, ec, rel->relids, true, false);
+	setup_eclass_member_iterator(&iter, root, ec, rel->relids, true, false);
 
-	while ((i = bms_next_member(matching_ems, i)) >= 0)
+	while ((em = eclass_member_iterator_next(&iter)) != 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.
@@ -7482,10 +7480,12 @@ find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel)
 
 		if (bms_is_subset(em->em_relids, rel->relids) &&
 			is_foreign_expr(root, rel, em->em_expr))
-			return em;
+			break;
 	}
 
-	return NULL;
+	eclass_member_iterator_dispose(&iter);
+
+	return em;
 }
 
 /*
@@ -7512,9 +7512,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;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *em;
 		Relids		expr_relids;
-		int			j;
 
 		/* Ignore non-sort expressions */
 		if (sgref == 0 ||
@@ -7530,14 +7530,12 @@ 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);
+		setup_eclass_member_strict_iterator(&iter, root, ec, expr_relids,
+											false, false);
+
 		/* Locate an EquivalenceClass member matching this expr, if any */
-		j = -1;
-		while ((j = bms_next_member(matching_ems, j)) >= 0)
+		while ((em = eclass_member_iterator_strict_next(&iter)) != NULL)
 		{
-			EquivalenceMember *em = list_nth_node(EquivalenceMember,
-												  root->eq_members, j);
 			Expr	   *em_expr;
 
 			/* don't expect constants */
@@ -7556,11 +7554,15 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec,
 
 			/* Check that expression (including relabels!) is shippable */
 			if (is_foreign_expr(root, rel, em->em_expr))
+			{
+				bms_free(expr_relids);
+				eclass_member_iterator_dispose(&iter);
 				return em;
+			}
 		}
 		i++;
 		bms_free(expr_relids);
-		bms_free(matching_ems);
+		eclass_member_iterator_dispose(&iter);
 	}
 
 	return NULL;
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index bf6ba3c6ec..aeb8f3324c 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -754,8 +754,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		Bitmapset		 *matching_ems;
-		int			i;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *cur_em;
 
 		/*
 		 * Never match to a volatile EC, except when we are looking at another
@@ -770,15 +770,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);
+		setup_eclass_member_strict_iterator(&iter, root, cur_ec, expr_relids,
+											true, true);
 
-		i = -1;
-		while ((i = bms_next_member(matching_ems, i)) >= 0)
+		while ((cur_em = eclass_member_iterator_strict_next(&iter)) != NULL)
 		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
-													  root->eq_members, i);
-
 			/*
 			 * Ignore child members unless they match the request.
 			 */
@@ -798,6 +794,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 				equal(expr, cur_em->em_expr))
 				return cur_ec;	/* Match! */
 		}
+
+		eclass_member_iterator_dispose(&iter);
 	}
 
 	/* No match; does caller want a NULL result? */
@@ -905,22 +903,20 @@ find_ec_member_matching_expr(PlannerInfo *root,
 							 Expr *expr,
 							 Relids relids)
 {
-	Bitmapset  *matching_ems;
+	EquivalenceMemberIterator iter;
 	Relids		expr_relids;
-	int			i;
+	EquivalenceMember *em;
 
 	/* 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);
+	setup_eclass_member_strict_iterator(&iter, root, ec, expr_relids, true,
+										true);
 
-	i = -1;
-	while ((i = bms_next_member(matching_ems, i)) >= 0)
+	while ((em = eclass_member_iterator_strict_next(&iter)) != NULL)
 	{
-		EquivalenceMember *em = list_nth_node(EquivalenceMember,
-											  root->eq_members, i);
 		Expr	   *emexpr;
 
 		/*
@@ -945,10 +941,13 @@ find_ec_member_matching_expr(PlannerInfo *root,
 			emexpr = ((RelabelType *) emexpr)->arg;
 
 		if (equal(emexpr, expr))
-			return em;
+			break;
 	}
 
-	return NULL;
+	bms_free(expr_relids);
+	eclass_member_iterator_dispose(&iter);
+
+	return em;
 }
 
 /*
@@ -1685,13 +1684,13 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 										Relids outer_relids,
 										Relids inner_relids)
 {
+	EquivalenceMemberIterator iter;
+	EquivalenceMember *cur_em;
 	List	   *result = NIL;
 	List	   *new_members = NIL;
 	List	   *outer_members = NIL;
 	List	   *inner_members = NIL;
-	Bitmapset  *matching_ems;
 	ListCell   *lc1;
-	int			i;
 
 	/*
 	 * First, scan the EC to identify member values that are computable at the
@@ -1702,14 +1701,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);
+	setup_eclass_member_iterator(&iter, root, ec, join_relids, true, false);
 
-	i = -1;
-	while ((i = bms_next_member(matching_ems, i)) >= 0)
+	while ((cur_em = eclass_member_iterator_next(&iter)) != 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
@@ -1726,6 +1721,8 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 			new_members = lappend(new_members, cur_em);
 	}
 
+	eclass_member_iterator_dispose(&iter);
+
 	/*
 	 * First, select the joinclause if needed.  We can equate any one outer
 	 * member to any one inner member, but we have to find a datatype
@@ -1823,7 +1820,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
 
 		foreach(lc1, new_members)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
+			cur_em = (EquivalenceMember *) lfirst(lc1);
 
 			if (prev_em != NULL)
 			{
@@ -2264,7 +2261,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		Bitmapset		 *matching_ems;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *cur_em;
 		bool		match;
 		int			i;
 
@@ -2281,15 +2279,12 @@ 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)
-		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
-													  root->eq_members, i);
 
+		setup_eclass_member_strict_iterator(&iter, root, cur_ec, outer_relids,
+											false, true);
+
+		while ((cur_em = eclass_member_iterator_strict_next(&iter)) != NULL)
+		{
 			Assert(!cur_em->em_is_child);	/* no children yet */
 			if (equal(outervar, cur_em->em_expr))
 			{
@@ -2297,6 +2292,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 				break;
 			}
 		}
+		eclass_member_iterator_dispose(&iter);
+
 		if (!match)
 			continue;			/* no match, so ignore this EC */
 
@@ -2309,11 +2306,11 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 		i = -1;
 		while ((i = bms_next_member(cur_ec->ec_norel_indexes, i)) >= 0)
 		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember,
-													  root->eq_members, i);
 			Oid			eq_op;
 			RestrictInfo *newrinfo;
 
+			cur_em = list_nth_node(EquivalenceMember, root->eq_members, i);
+
 			if (!cur_em->em_is_const)
 				continue;		/* ignore non-const members */
 			eq_op = select_equality_operator(cur_ec,
@@ -2774,8 +2771,8 @@ 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;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *cur_em;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2789,16 +2786,15 @@ add_child_rel_equivalences(PlannerInfo *root,
 		Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
 
 		/*
-		 * Looping over matching_ems means we only loop over existing members,
-		 * not any newly added ones.
+		 * Looping using the EquivalenceMemberIterator means we only loop over
+		 * the members which existed when we set up the iterator, not newly
+		 * added ones.
 		 */
-		matching_ems = get_ecmember_indexes(root, cur_ec, top_parent_relids, false, false);
+		setup_eclass_member_iterator(&iter, root, cur_ec, top_parent_relids,
+									 false, false);
 
-		j = -1;
-		while ((j = bms_next_member(matching_ems, j)) >= 0)
+		while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
 		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember, root->eq_members, j);
-
 			Assert(!cur_em->em_is_const);
 			Assert(!cur_em->em_is_child);
 			Assert(bms_overlap(cur_em->em_relids, top_parent_relids));
@@ -2857,6 +2853,7 @@ add_child_rel_equivalences(PlannerInfo *root,
 				child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
 			}
 		}
+		eclass_member_iterator_dispose(&iter);
 	}
 }
 
@@ -2901,8 +2898,8 @@ 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;
+		EquivalenceMemberIterator iter;
+		EquivalenceMember *cur_em;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2916,16 +2913,15 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 		Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
 
 		/*
-		 * Looping over matching_ems means we only loop over existing members,
-		 * not any newly added ones.
+		 * Looping using the EquivalenceMemberIterator means we only loop over
+		 * the members which existed when we set up the iterator, not newly
+		 * added ones.
 		 */
-		matching_ems = get_ecmember_indexes(root, cur_ec, top_parent_relids, false, false);
+		setup_eclass_member_iterator(&iter, root, cur_ec, top_parent_relids,
+									 false, false);
 
-		j = -1;
-		while ((j = bms_next_member(matching_ems, j)) >= 0)
+		while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
 		{
-			EquivalenceMember *cur_em = list_nth_node(EquivalenceMember, root->eq_members, j);
-
 			Assert(!cur_em->em_is_const);
 			Assert(!cur_em->em_is_child);
 			Assert(bms_overlap(cur_em->em_relids, top_parent_relids));
@@ -2988,6 +2984,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 									 true, cur_em->em_datatype);
 			}
 		}
+		eclass_member_iterator_dispose(&iter);
 	}
 
 	MemoryContextSwitchTo(oldcontext);
@@ -3046,7 +3043,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 iter;
 		int					j;
 
 		/* Sanity check eclass_indexes only contain ECs for rel */
@@ -3069,19 +3066,19 @@ 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)
-		{
-			cur_em = list_nth_node(EquivalenceMember, root->eq_members, j);
+		setup_eclass_member_iterator(&iter, root, cur_ec, rel->relids, true,
+									 false);
 
+		while ((cur_em = eclass_member_iterator_next(&iter)) != NULL)
+		{
 			if (bms_equal(cur_em->em_relids, rel->relids) &&
 				callback(root, rel, cur_ec, cur_em, callback_arg))
 				break;
 			cur_em = NULL;
 		}
 
+		eclass_member_iterator_dispose(&iter);
+
 		if (!cur_em)
 			continue;
 
@@ -3539,6 +3536,195 @@ get_ecmember_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
 	return matching_ems;
 }
 
+/*
+ * The threshold for the number of members that must be in an EquivalenceClass
+ * before we switch to searching for EquivalenceMember by using the Bitmapset
+ * indexes stored in EquivalenceClass and RelOptInfo.  We don't want to make
+ * this too low as the manipulation of Bitmapsets slows this down for
+ * EquivalenceClasses with just a few members.  The linear search becomes very
+ * slow when an EquivalenceClass has a large number of members, as can happen
+ * when planning queries to partitioned tables.
+ */
+#define ECMEMBER_INDEX_THRESHOLD 16
+
+/*
+ * setup_eclass_member_iterator
+ *		Setup 'iter' so it's ready for eclass_member_iterator_next to start
+ *		searching for EquivalenceMembers matching the specified parameters.
+ *
+ * Once used, the iterator must be disposed of using
+ * eclass_member_iterator_dispose.
+ */
+void
+setup_eclass_member_iterator(EquivalenceMemberIterator *iter,
+							 PlannerInfo *root, EquivalenceClass *ec,
+							 Relids relids, bool with_children,
+							 bool with_norel_members)
+{
+	iter->orig_length = list_length(ec->ec_members);
+	iter->use_index = iter->orig_length >= ECMEMBER_INDEX_THRESHOLD;
+	iter->with_children = with_children;
+	iter->with_norel_members = with_norel_members;
+	iter->with_relids = relids;
+	iter->root = root;
+	iter->eclass = ec;
+
+	if (iter->use_index)
+		iter->matching_ems = get_ecmember_indexes(root, ec, relids,
+												  with_children,
+												  with_norel_members);
+	else
+		iter->matching_ems = NULL;
+
+	iter->current_index = -1;
+}
+
+/*
+ * setup_eclass_member_strict_iterator
+ *		Setup 'iter' so it's ready for eclass_member_iterator_strict_next to
+ *		start searching for EquivalenceMembers matching the specified
+ *		parameters.
+ *
+ * Once used, the iterator must be disposed of using
+ * eclass_member_iterator_dispose.
+ */
+void
+setup_eclass_member_strict_iterator(EquivalenceMemberIterator *iter,
+									PlannerInfo *root, EquivalenceClass *ec,
+									Relids relids, bool with_children,
+									bool with_norel_members)
+{
+	iter->orig_length = list_length(ec->ec_members);
+	iter->use_index = iter->orig_length >= ECMEMBER_INDEX_THRESHOLD;
+	iter->with_children = with_children;
+	iter->with_norel_members = with_norel_members;
+	iter->with_relids = relids;
+	iter->root = root;
+	iter->eclass = ec;
+
+	if (iter->use_index)
+		iter->matching_ems = get_ecmember_indexes_strict(root, ec, relids,
+														 with_children,
+														 with_norel_members);
+	else
+		iter->matching_ems = NULL;
+
+	iter->current_index = -1;
+}
+
+/*
+ * eclass_member_iterator_next
+ *		Fetch the next EquivalenceMember from an EquivalenceMemberIterator
+ *		which was set up by setup_eclass_member_iterator().  Returns NULL when
+ *		there are no more matching EquivalenceMembers.
+ */
+EquivalenceMember *
+eclass_member_iterator_next(EquivalenceMemberIterator *iter)
+{
+	if (iter->use_index)
+	{
+		iter->current_index = bms_next_member(iter->matching_ems,
+											  iter->current_index);
+		if (iter->current_index >= 0)
+			return list_nth_node(EquivalenceMember, iter->root->eq_members,
+								 iter->current_index);
+		return NULL;
+	}
+	else
+	{
+		ListCell *lc;
+
+		for_each_from(lc, iter->eclass->ec_members, iter->current_index + 1)
+		{
+			EquivalenceMember *em = lfirst_node(EquivalenceMember, lc);
+
+			if (!iter->with_children && em->em_is_child)
+				continue;
+
+			if (!iter->with_norel_members && bms_is_empty(em->em_relids))
+				continue;
+
+			if (!bms_overlap(em->em_relids, iter->with_relids))
+				continue;
+
+			iter->current_index = foreach_current_index(lc);
+
+			/*
+			 * Some users of this iterator will be adding new
+			 * EquivalenceMember during the loop.  We must ensure we don't
+			 * return those, so here we return NULL when the loop index goes
+			 * beyond the original length of the ec_members list.
+			 */
+			if (iter->current_index >= iter->orig_length)
+				return NULL;
+			return em;
+		}
+		return NULL;
+	}
+}
+
+/*
+ * eclass_member_iterator_strict_next
+ *		Fetch the next EquivalenceMember from an EquivalenceMemberIterator
+ *		which was set up by setup_eclass_member_strict_iterator().  Returns
+ *		NULL when there are no more matching EquivalenceMembers.
+ */
+EquivalenceMember *
+eclass_member_iterator_strict_next(EquivalenceMemberIterator *iter)
+{
+	if (iter->use_index)
+	{
+		iter->current_index = bms_next_member(iter->matching_ems,
+											  iter->current_index);
+		if (iter->current_index >= 0)
+			return list_nth_node(EquivalenceMember, iter->root->eq_members,
+								 iter->current_index);
+		return NULL;
+	}
+	else
+	{
+		ListCell *lc;
+
+		for_each_from(lc, iter->eclass->ec_members, iter->current_index + 1)
+		{
+			EquivalenceMember *em = lfirst_node(EquivalenceMember, lc);
+
+			if (!iter->with_children && em->em_is_child)
+				continue;
+
+			if (!iter->with_norel_members && bms_is_empty(em->em_relids))
+				continue;
+
+			if (!bms_is_subset(iter->with_relids, em->em_relids))
+				continue;
+
+			iter->current_index = foreach_current_index(lc);
+
+			/*
+			 * Some users of this iterator will be adding new
+			 * EquivalenceMember during the loop.  We must ensure we don't
+			 * return those, so here we return NULL when the loop index goes
+			 * beyond the original length of the ec_members list.
+			 */
+			if (iter->current_index >= iter->orig_length)
+				return NULL;
+			return em;
+		}
+		return NULL;
+	}
+}
+
+/*
+ * eclass_member_iterator_dispose
+ *		Free any memory allocated by the iterator
+ */
+void
+eclass_member_iterator_dispose(EquivalenceMemberIterator *iter)
+{
+	bms_free(iter->matching_ems);
+}
+
+
 /*
  * get_ec_source_indexes
  *		Returns a Bitmapset with indexes into root->eq_sources for all
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 07f53744c2..3f6a0173d6 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -114,6 +114,31 @@ extern void mark_dummy_rel(RelOptInfo *rel);
  * equivclass.c
  *	  routines for managing EquivalenceClasses
  */
+
+/*
+ * EquivalenceMemberIterator
+ *		Data structure used for iteration over an EquivalenceClass's
+ *		EquivalenceMember in order to quickly find the members matching our
+ *		search pattern.
+ *
+ * Callers should assume all of the fields within this struct are internal.
+ *
+ * XXX where should this struct go? Not here.
+ */
+typedef struct EquivalenceMemberIterator
+{
+	bool		use_index;		/* use matching_ems index? */
+	bool		with_children;	/* include em_is_child members? */
+	bool		with_norel_members;	/* include members with empty em_relids */
+	int			current_index;	/* current iterator position, or -1. */
+	int			orig_length;	/* elements in eclass->ec_members at the start */
+	Relids		with_relids;	/* relids to match in em_relids */
+	PlannerInfo *root;		/* PlannerInfo the eclass belongs to */
+	EquivalenceClass *eclass;	/* the EquivalenceClass we're looking at */
+	Bitmapset  *matching_ems;	/* when use_index == true, these are the
+								 * matching indexes in root eq_members */
+} EquivalenceMemberIterator;
+
 typedef bool (*ec_matches_callback_type) (PlannerInfo *root,
 										  RelOptInfo *rel,
 										  EquivalenceClass *ec,
@@ -198,6 +223,20 @@ extern Bitmapset *get_ecmember_indexes_strict(PlannerInfo *root,
 											  Relids relids,
 											  bool with_children,
 											  bool with_norel_members);
+extern void setup_eclass_member_iterator(EquivalenceMemberIterator *iter,
+										 PlannerInfo *root,
+										 EquivalenceClass *ec, Relids relids,
+										 bool with_children,
+										 bool with_norel_members);
+extern void setup_eclass_member_strict_iterator(EquivalenceMemberIterator *iter,
+												PlannerInfo *root,
+												EquivalenceClass *ec,
+												Relids relids,
+												bool with_children,
+												bool with_norel_members);
+extern EquivalenceMember *eclass_member_iterator_next(EquivalenceMemberIterator *iter);
+extern EquivalenceMember *eclass_member_iterator_strict_next(EquivalenceMemberIterator *iter);
+extern void eclass_member_iterator_dispose(EquivalenceMemberIterator *iter);
 extern Bitmapset *get_ec_source_indexes(PlannerInfo *root,
 										EquivalenceClass *ec,
 										Relids relids);
-- 
2.35.1.windows.2