v34-0004-Introduce-RestrictInfoIterator-to-reduce-memory-.patch

From e22c65332714758ab30541693b85fb76ea3b508e Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Fri, 20 Dec 2024 12:01:35 +0900
Subject: [PATCH v34 4/4] Introduce RestrictInfoIterator to reduce memory
 consumption

Originally, get_ec_[source|derive]_indexes[_strict]() functions created
temporary Bitmapsets each time they were called. This resulted in large
memory consumption.

This commit introduces a new iterator mechanism called
RestrictInfoIterator. This iterator iterates over RestrictInfos using
indexes without creating temporary Bitmapsets. Experimental results show
that this commit significantly reduces memory consumption.
---
 src/backend/nodes/bitmapset.c           |   3 +
 src/backend/optimizer/path/equivclass.c | 313 +++++++++++-------------
 src/include/nodes/pathnodes.h           |  38 +++
 src/include/optimizer/paths.h           |  20 +-
 src/tools/pgindent/typedefs.list        |   1 +
 5 files changed, 199 insertions(+), 176 deletions(-)

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index bf512cf806f..5aecf96cbb7 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1301,6 +1301,9 @@ bms_join(Bitmapset *a, Bitmapset *b)
  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
  * It makes no difference in simple loop usage, but complex iteration logic
  * might need such an ability.
+ *
+ * NOTE: The routine here is similar to eclass_rinfo_iterator_for_relids_next().
+ * If you change here, you should adjust the logic there.
  */
 int
 bms_next_member(const Bitmapset *a, int prevbit)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 1facf547bb9..c6ecfb874c8 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1953,16 +1953,14 @@ 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 iter;
 
-	matching_es = get_ec_source_indexes(root, ec, nominal_join_relids);
-	i = -1;
-	while ((i = bms_next_member(matching_es, i)) >= 0)
+	setup_eclass_rinfo_iterator_for_relids(&iter, root, ec, nominal_join_relids, true,
+										   false);
+	while ((restrictinfo = eclass_rinfo_iterator_for_relids_next(&iter)) != 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) &&
@@ -1970,6 +1968,7 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
 			!bms_is_subset(clause_relids, nominal_inner_relids))
 			result = lappend(result, restrictinfo);
 	}
+	dispose_eclass_rinfo_iterator_for_relids(&iter);
 
 	/*
 	 * If we have to translate, just brute-force apply adjust_appendrel_attrs
@@ -2041,11 +2040,10 @@ create_join_clause(PlannerInfo *root,
 				   EquivalenceMember *rightem,
 				   EquivalenceClass *parent_ec)
 {
-	Bitmapset  *matches;
 	RestrictInfo *rinfo;
 	RestrictInfo *parent_rinfo = NULL;
 	MemoryContext oldcontext;
-	int			i;
+	RestrictInfoIterator iter;
 
 	/*
 	 * Search to see if we already built a RestrictInfo for this pair of
@@ -2056,12 +2054,11 @@ create_join_clause(PlannerInfo *root,
 	 * it's not identical, it'd better have the same effects, or the operator
 	 * families we're using are broken.
 	 */
-	matches = bms_int_members(get_ec_source_indexes_strict(root, ec, leftem->em_relids),
-							  get_ec_source_indexes_strict(root, ec, rightem->em_relids));
-	i = -1;
-	while ((i = bms_next_member(matches, i)) >= 0)
+	setup_eclass_rinfo_iterator_for_relids(&iter, root, ec,
+										   bms_union(leftem->em_relids, rightem->em_relids),
+										   true, true);
+	while ((rinfo = eclass_rinfo_iterator_for_relids_next(&iter)) != NULL)
 	{
-		rinfo = list_nth_node(RestrictInfo, root->eq_sources, i);
 		if (rinfo->left_em == leftem &&
 			rinfo->right_em == rightem &&
 			rinfo->parent_ec == parent_ec)
@@ -2071,14 +2068,13 @@ create_join_clause(PlannerInfo *root,
 			rinfo->parent_ec == parent_ec)
 			return rinfo;
 	}
+	dispose_eclass_rinfo_iterator_for_relids(&iter);
 
-	matches = bms_int_members(get_ec_derive_indexes_strict(root, ec, leftem->em_relids),
-							  get_ec_derive_indexes_strict(root, ec, rightem->em_relids));
-
-	i = -1;
-	while ((i = bms_next_member(matches, i)) >= 0)
+	setup_eclass_rinfo_iterator_for_relids(&iter, root, ec,
+										   bms_union(leftem->em_relids, rightem->em_relids),
+										   false, true);
+	while ((rinfo = eclass_rinfo_iterator_for_relids_next(&iter)) != NULL)
 	{
-		rinfo = list_nth_node(RestrictInfo, root->eq_derives, i);
 		if (rinfo->left_em == leftem &&
 			rinfo->right_em == rightem &&
 			rinfo->parent_ec == parent_ec)
@@ -2088,6 +2084,7 @@ create_join_clause(PlannerInfo *root,
 			rinfo->parent_ec == parent_ec)
 			return rinfo;
 	}
+	dispose_eclass_rinfo_iterator_for_relids(&iter);
 
 	/*
 	 * Not there, so build it, in planner context so we can re-use it. (Not
@@ -3935,179 +3932,167 @@ get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
 }
 
 /*
- * get_ec_source_indexes
- *		Returns a Bitmapset with indexes into root->eq_sources for all
- *		RestrictInfos in 'ec' that have
- *		bms_overlap(relids, rinfo->clause_relids) as true.
+ * setup_eclass_rinfo_iterator_for_relids
+ *	  Setup a RestrictInfoIterator 'iter' to iterate over RestrictInfos
+ *	  associated with the given 'ec'. It iterates through root->eq_sources if
+ *	  'is_source' is true, or root->eq_derives otherwise. The members must be
+ *	  from 'ec' and satisfy "bms_is_subset(relids, rinfo->clause_relids)" if
+ *	  'is_strict' is true, or "bms_overlap(relids, rinfo->clause_relids)"
+ *	  otherwise.
  *
- * Returns a newly allocated Bitmapset which the caller is free to modify.
+ * Once used, the caller should dispose of the iterator by calling
+ * dispose_eclass_rinfo_iterator_for_relids().
  */
-Bitmapset *
-get_ec_source_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+void
+setup_eclass_rinfo_iterator_for_relids(RestrictInfoIterator *iter, PlannerInfo *root,
+									   EquivalenceClass *ec, Relids relids,
+									   bool is_source, bool is_strict)
 {
-	Bitmapset  *rel_esis = NULL;
-	int			i = -1;
-
-	while ((i = bms_next_member(relids, i)) >= 0)
-	{
-		EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
-
-		rel_esis = bms_add_members(rel_esis, index->source_indexes);
-	}
-
-#ifdef USE_ASSERT_CHECKING
-	/* verify the results look sane */
-	i = -1;
-	while ((i = bms_next_member(rel_esis, i)) >= 0)
-	{
-		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
-											i);
-
-		Assert(bms_overlap(relids, rinfo->clause_relids));
-	}
-#endif
-
-	/* bitwise-AND to leave only the ones for this EquivalenceClass */
-	return bms_int_members(rel_esis, ec->ec_source_indexes);
+	iter->root = root;
+	iter->ec = ec;
+	iter->relids = relids;
+	iter->is_source = is_source;
+	iter->is_strict = is_strict;
+	iter->last_word = 0;
+	iter->wordnum = -1;
+	iter->index = -1;
 }
 
 /*
- * get_ec_source_indexes_strict
- *		Returns a Bitmapset with indexes into root->eq_sources for all
- *		RestrictInfos in 'ec' that have
- *		bms_is_subset(relids, rinfo->clause_relids) as true.
- *
- * Returns a newly allocated Bitmapset which the caller is free to modify.
+ * eclass_rinfo_iterator_for_relids_next
+ *	  Get a next RestrictInfo from an RestrictInfoIterator 'iter' that was
+ *	  setup by setup_eclass_rinfo_iterator_for_relids(). NULL is returned if
+ *	  there are no members left.
  */
-Bitmapset *
-get_ec_source_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
-							 Relids relids)
+RestrictInfo *
+eclass_rinfo_iterator_for_relids_next(RestrictInfoIterator *iter)
 {
-	Bitmapset  *esis = NULL;
-	int			i = bms_next_member(relids, -1);
+	RestrictInfo *rinfo;
+	bitmapword	mask;
+	bitmapword	w;
+	int			bitnum;
 
-	if (i >= 0)
-	{
-		EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
+	if (iter->index <= -2)
+		return NULL;			/* Already finished iteration */
+
+	/*
+	 * The routine in this function is similar to bms_next_member(). If you
+	 * change its behavior, you should adjust the logic here.
+	 */
+	++(iter->index);
+	bitnum = iter->index % BITS_PER_BITMAPWORD;
+	mask = (~(bitmapword) 0) << bitnum;
+	w = iter->last_word & mask;
 
+	/*
+	 * Do we need to consume a new word?
+	 */
+	if (bitnum == 0 || w == 0)
+	{
 		/*
-		 * bms_intersect to the first relation to try to keep the resulting
-		 * Bitmapset as small as possible.  This saves having to make a
-		 * complete bms_copy() of one of them.  One may contain significantly
-		 * more words than the other.
+		 * Yes, we need a new word.
 		 */
-		esis = bms_intersect(ec->ec_source_indexes,
-							 index->source_indexes);
-
-		while ((i = bms_next_member(relids, i)) >= 0)
+		while (true)
 		{
-			index = &root->eclass_indexes_array[i];
-			esis = bms_int_members(esis, index->source_indexes);
-		}
-	}
+			Bitmapset  *ec_members_index;
+			bitmapword	word;
+			int			i;
 
-#ifdef USE_ASSERT_CHECKING
-	/* verify the results look sane */
-	i = -1;
-	while ((i = bms_next_member(esis, i)) >= 0)
-	{
-		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_sources,
-											i);
+			iter->wordnum++;	/* Consume */
 
-		Assert(bms_is_subset(relids, rinfo->clause_relids));
-	}
-#endif
+			/*
+			 * Are there still members in ec?
+			 */
+			ec_members_index = iter->is_source ?
+				iter->ec->ec_source_indexes : iter->ec->ec_derive_indexes;
+			if (ec_members_index == NULL || iter->wordnum >= ec_members_index->nwords)
+			{
+				iter->index = -2;
+				return NULL;	/* No words left */
+			}
 
-	return esis;
-}
+			/*
+			 * We intersect the corresponding Bitmapset indexes for the
+			 * is_strict case or union them for the non-is_strict case.
+			 */
+			word = iter->is_strict ? (~(bitmapword) 0) : 0;
 
-/*
- * get_ec_derive_indexes
- *		Returns a Bitmapset with indexes into root->eq_derives for all
- *		RestrictInfos in 'ec' that have
- *		bms_overlap(relids, rinfo->clause_relids) as true.
- *
- * Returns a newly allocated Bitmapset which the caller is free to modify.
- *
- * XXX is this function even needed?
- */
-Bitmapset *
-get_ec_derive_indexes(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
-{
-	Bitmapset  *rel_edis = NULL;
-	int			i = -1;
+			/*
+			 * Loop over 'relids' to intersect or union all indexes.
+			 */
+			i = -1;
+			while ((i = bms_next_member(iter->relids, i)) >= 0)
+			{
+				EquivalenceClassIndexes *ec_indexes =
+					&iter->root->eclass_indexes_array[i];
+				Bitmapset  *index = iter->is_source ?
+					ec_indexes->source_indexes : ec_indexes->derive_indexes;
 
-	while ((i = bms_next_member(relids, i)) >= 0)
-	{
-		EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
+				if (index == NULL || iter->wordnum >= index->nwords)
+				{
+					/* This word is zero. */
+					if (iter->is_strict)
+					{
+						word = 0;
+						break;	/* We don't need to do anything. */
+					}
+					else
+						continue;
+				}
 
-		rel_edis = bms_add_members(rel_edis, index->derive_indexes);
-	}
+				if (iter->is_strict)
+					word &= index->words[iter->wordnum];
+				else
+					word |= index->words[iter->wordnum];
+			}
 
-#ifdef USE_ASSERT_CHECKING
-	/* verify the results look sane */
-	i = -1;
-	while ((i = bms_next_member(rel_edis, i)) >= 0)
-	{
-		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
-											i);
+			/*
+			 * Leave only the members for this EquivalenceClass.
+			 */
+			word &= ec_members_index->words[iter->wordnum];
 
-		Assert(bms_overlap(relids, rinfo->clause_relids));
+			/*
+			 * Did we find new members?
+			 */
+			if (word != 0)
+			{
+				/* Yes, we find new ones. */
+				w = iter->last_word = word;
+				break;
+			}
+			/* No, we need to consume more word */
+		}
 	}
+
+	/*
+	 * Here, 'iter->last_word' or 'w' must have a new member. We get it.
+	 */
+	Assert(w != 0);
+	iter->index =
+		iter->wordnum * BITS_PER_BITMAPWORD + bmw_rightmost_one_pos(w);
+	rinfo = list_nth_node(RestrictInfo,
+						  iter->is_source ? iter->root->eq_sources : iter->root->eq_derives,
+						  iter->index);
+
+#ifdef USE_ASSERT_CHECKING
+	/* verify the result look sane */
+	if (iter->is_strict)
+		Assert(bms_is_subset(iter->relids, rinfo->clause_relids));
+	else
+		Assert(bms_overlap(iter->relids, rinfo->clause_relids));
 #endif
 
-	/* bitwise-AND to leave only the ones for this EquivalenceClass */
-	return bms_int_members(rel_edis, ec->ec_derive_indexes);
+	return rinfo;
 }
 
 /*
- * get_ec_derive_indexes_strict
- *		Returns a Bitmapset with indexes into root->eq_derives for all
- *		RestrictInfos in 'ec' that have
- *		bms_is_subset(relids, rinfo->clause_relids) as true.
- *
- * Returns a newly allocated Bitmapset which the caller is free to modify.
+ * dispose_eclass_rinfo_iterator_for_relids
+ *	  Free any memory allocated by the iterator.
  */
-Bitmapset *
-get_ec_derive_indexes_strict(PlannerInfo *root, EquivalenceClass *ec,
-							 Relids relids)
+void
+dispose_eclass_rinfo_iterator_for_relids(RestrictInfoIterator *iter)
 {
-	Bitmapset  *edis = NULL;
-	int			i = bms_next_member(relids, -1);
-
-	if (i >= 0)
-	{
-		EquivalenceClassIndexes *index = &root->eclass_indexes_array[i];
-
-		/*
-		 * bms_intersect to the first relation to try to keep the resulting
-		 * Bitmapset as small as possible.  This saves having to make a
-		 * complete bms_copy() of one of them.  One may contain significantly
-		 * more words than the other.
-		 */
-		edis = bms_intersect(ec->ec_derive_indexes,
-							 index->derive_indexes);
-
-		while ((i = bms_next_member(relids, i)) >= 0)
-		{
-			index = &root->eclass_indexes_array[i];
-			edis = bms_int_members(edis, index->derive_indexes);
-		}
-	}
-
-#ifdef USE_ASSERT_CHECKING
-	/* verify the results look sane */
-	i = -1;
-	while ((i = bms_next_member(edis, i)) >= 0)
-	{
-		RestrictInfo *rinfo = list_nth_node(RestrictInfo, root->eq_derives,
-											i);
-
-		Assert(bms_is_subset(relids, rinfo->clause_relids));
-	}
-#endif
-
-	return edis;
+	/* Do nothing */
 }
 
 #ifdef USE_ASSERT_CHECKING
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 093c40288fd..0abd8dd4d9b 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1566,6 +1566,44 @@ typedef struct
 	List	   *ec_members;		/* parent and child members */
 } EquivalenceAllMemberIterator;
 
+/*
+ * RestrictInfoIterator
+ *
+ * This iterator provides a way to iterate over RestrictInfos in an
+ * EquivalenceClass that satisfy a certain condition. You need to first
+ * initialize an iterator, and then use move next during the iteration. You
+ * can specify the condition during initialization. For more details, see the
+ * comment in setup_eclass_rinfo_iterator_for_relids().
+ *
+ * The most common way to use this struct is as follows:
+ * -----
+ * PlannerInfo		   *root = given;
+ * EquivalenceClass	   *ec = given;
+ * Relids				relids = given;
+ * RestrictInfoIterator iter;
+ * RestrictInfo		   *rinfo;
+ *
+ * setup_eclass_rinfo_iterator_for_relids(&iter, root, ec, relids, true, true);
+ * while ((rinfo = eclass_rinfo_iterator_for_relids_next(&iter)) != NULL)
+ * {
+ *     use rinfo ...;
+ * }
+ * dispose_eclass_rinfo_iterator_for_relids(&iter);
+ * -----
+ */
+typedef struct
+{
+	PlannerInfo *root;
+	EquivalenceClass *ec;		/* EC where we are looking now */
+	Relids		relids;			/* Relids that we are checking */
+	bool		is_source;		/* Do we iterate over root->eq_sources? */
+	bool		is_strict;		/* Do we intersect the indexes? */
+	bitmapword	last_word;		/* Bitmapword at last iteration */
+	int			wordnum;		/* Wordnum at last iteration */
+	int			index;			/* The last RestrictInfo index we returned to
+								 * the caller */
+} RestrictInfoIterator;
+
 /*
  * EquivalenceClassIndexes
  *
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 4b8dc7b1d6f..e8706b2774c 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -206,18 +206,14 @@ 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);
-extern Bitmapset *get_ec_source_indexes(PlannerInfo *root,
-										EquivalenceClass *ec,
-										Relids relids);
-extern Bitmapset *get_ec_source_indexes_strict(PlannerInfo *root,
-											   EquivalenceClass *ec,
-											   Relids relids);
-extern Bitmapset *get_ec_derive_indexes(PlannerInfo *root,
-										EquivalenceClass *ec,
-										Relids relids);
-extern Bitmapset *get_ec_derive_indexes_strict(PlannerInfo *root,
-											   EquivalenceClass *ec,
-											   Relids relids);
+extern void setup_eclass_rinfo_iterator_for_relids(RestrictInfoIterator *iter,
+												   PlannerInfo *root,
+												   EquivalenceClass *ec,
+												   Relids relids,
+												   bool is_source,
+												   bool is_strict);
+extern RestrictInfo *eclass_rinfo_iterator_for_relids_next(RestrictInfoIterator *iter);
+extern void dispose_eclass_rinfo_iterator_for_relids(RestrictInfoIterator *iter);
 #ifdef USE_ASSERT_CHECKING
 extern void verify_eclass_indexes(PlannerInfo *root,
 								  EquivalenceClass *ec);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 31ffc643916..51d45b6677c 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2504,6 +2504,7 @@ ResourceReleasePriority
 RestoreOptions
 RestorePass
 RestrictInfo
+RestrictInfoIterator
 Result
 ResultRelInfo
 ResultState
-- 
2.45.2.windows.1