v0-0001-Be-more-conventional-in-estimating-hash-join-buck.patch

From 2df9c47f188ed1a8ae8b70865c6a5ddff6dbe766 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <lepihov@gmail.com>
Date: Thu, 10 Apr 2025 14:16:44 +0200
Subject: [PATCH v0] Be more conventional in estimating hash join bucket size.

Implementing estimation of hash join bucket size by extended statistics, we
wanted to avoid the use of add_unique_group_var because its logic greatly
depends on the group's number estimation code. But we forgot that this routine
also does over stuff, like duplicate removal from the list of estimated
clauses.
With this commit, we make add_unique_group_var a little more general, which
allows us to use it during the bucket estimation. At first, it doesn't need
vardata receiving RelOptInfo reference, ndistinct and isdefault values
directly. Also, GroupVarInfo tracks original restriction - it is a palliative
that simplifies the detection of clauses that have not yet been estimated.
---
 src/backend/utils/adt/selfuncs.c        | 77 +++++++++++--------------
 src/test/regress/expected/stats_ext.out | 28 +++++++++
 src/test/regress/sql/stats_ext.sql      | 11 ++++
 3 files changed, 72 insertions(+), 44 deletions(-)

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 588d991fa57..b88a6bf5822 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3310,19 +3310,17 @@ typedef struct
 	RelOptInfo *rel;			/* relation it belongs to */
 	double		ndistinct;		/* # distinct values */
 	bool		isdefault;		/* true if DEFAULT_NUM_DISTINCT was used */
+	RestrictInfo *source;		/* Source restriction to surely identification */
 } GroupVarInfo;
 
 static List *
-add_unique_group_var(PlannerInfo *root, List *varinfos,
-					 Node *var, VariableStatData *vardata)
+add_unique_group_var(PlannerInfo *root, List *varinfos, Node *var,
+					 RelOptInfo *rel, double ndistinct, bool isdefault,
+					 RestrictInfo *source)
 {
 	GroupVarInfo *varinfo;
-	double		ndistinct;
-	bool		isdefault;
 	ListCell   *lc;
 
-	ndistinct = get_variable_numdistinct(vardata, &isdefault);
-
 	/*
 	 * The nullingrels bits within the var could cause the same var to be
 	 * counted multiple times if it's marked with different nullingrels.  They
@@ -3345,7 +3343,7 @@ add_unique_group_var(PlannerInfo *root, List *varinfos,
 		 * relations (see comments for estimate_num_groups).  We aren't too
 		 * fussy about the semantics of "equal" here.
 		 */
-		if (vardata->rel != varinfo->rel &&
+		if (rel != varinfo->rel &&
 			exprs_known_equal(root, var, varinfo->var, InvalidOid))
 		{
 			if (varinfo->ndistinct <= ndistinct)
@@ -3364,9 +3362,10 @@ add_unique_group_var(PlannerInfo *root, List *varinfos,
 	varinfo = (GroupVarInfo *) palloc(sizeof(GroupVarInfo));
 
 	varinfo->var = var;
-	varinfo->rel = vardata->rel;
+	varinfo->rel = rel;
 	varinfo->ndistinct = ndistinct;
 	varinfo->isdefault = isdefault;
+	varinfo->source = source;
 	varinfos = lappend(varinfos, varinfo);
 	return varinfos;
 }
@@ -3532,8 +3531,13 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
 		examine_variable(root, groupexpr, 0, &vardata);
 		if (HeapTupleIsValid(vardata.statsTuple) || vardata.isunique)
 		{
-			varinfos = add_unique_group_var(root, varinfos,
-											groupexpr, &vardata);
+			double	ndistinct;
+			bool	isdefault;
+
+			ndistinct = get_variable_numdistinct(&vardata, &isdefault);
+			varinfos = add_unique_group_var(root, varinfos, groupexpr,
+											vardata.rel, ndistinct, isdefault,
+											NULL);
 			ReleaseVariableStats(vardata);
 			continue;
 		}
@@ -3569,9 +3573,13 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
 		foreach(l2, varshere)
 		{
 			Node	   *var = (Node *) lfirst(l2);
+			double		ndistinct;
+			bool		isdefault;
 
 			examine_variable(root, var, 0, &vardata);
-			varinfos = add_unique_group_var(root, varinfos, var, &vardata);
+			ndistinct = get_variable_numdistinct(&vardata, &isdefault);
+			varinfos = add_unique_group_var(root, varinfos, var, vardata.rel,
+											ndistinct, isdefault, NULL);
 			ReleaseVariableStats(vardata);
 		}
 	}
@@ -3816,13 +3824,9 @@ estimate_multivariate_bucketsize(PlannerInfo *root, RelOptInfo *inner,
 		ListCell   *lc;
 		int			relid = -1;
 		List	   *varinfos = NIL;
-		List	   *origin_rinfos = NIL;
 		double		mvndistinct;
-		List	   *origin_varinfos;
 		int			group_relid = -1;
 		RelOptInfo *group_rel = NULL;
-		ListCell   *lc1,
-				   *lc2;
 
 		/*
 		 * Find clauses, referencing the same single base relation and try to
@@ -3835,7 +3839,6 @@ estimate_multivariate_bucketsize(PlannerInfo *root, RelOptInfo *inner,
 			RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
 			Node	   *expr;
 			Relids		relids;
-			GroupVarInfo *varinfo;
 
 			/*
 			 * Find the inner side of the join, which we need to estimate the
@@ -3880,18 +3883,9 @@ estimate_multivariate_bucketsize(PlannerInfo *root, RelOptInfo *inner,
 					 */
 					continue;
 
-				varinfo = (GroupVarInfo *) palloc(sizeof(GroupVarInfo));
-				varinfo->var = expr;
-				varinfo->rel = root->simple_rel_array[relid];
-				varinfo->ndistinct = 0.0;
-				varinfo->isdefault = false;
-				varinfos = lappend(varinfos, varinfo);
-
-				/*
-				 * Remember the link to RestrictInfo for the case the clause
-				 * is failed to be estimated.
-				 */
-				origin_rinfos = lappend(origin_rinfos, rinfo);
+				varinfos = add_unique_group_var(root, varinfos, expr,
+												root->simple_rel_array[relid],
+												0.0, false, rinfo);
 			}
 			else
 				/* This clause can't be estimated with extended statistics */
@@ -3906,22 +3900,23 @@ estimate_multivariate_bucketsize(PlannerInfo *root, RelOptInfo *inner,
 			 * Multivariate statistics doesn't apply to single columns except
 			 * for expressions, but it has not been implemented yet.
 			 */
-			otherclauses = list_concat(otherclauses, origin_rinfos);
+
+			if (varinfos != NULL)
+				otherclauses = lappend(otherclauses,
+								((GroupVarInfo *) linitial(varinfos))->source);
 			list_free_deep(varinfos);
-			list_free(origin_rinfos);
 			continue;
 		}
 
 		Assert(group_rel != NULL);
 
 		/* Employ the extended statistics. */
-		origin_varinfos = varinfos;
 		for (;;)
 		{
-			bool		estimated = estimate_multivariate_ndistinct(root,
-																	group_rel,
-																	&varinfos,
-																	&mvndistinct);
+			bool	estimated = estimate_multivariate_ndistinct(root,
+																group_rel,
+																&varinfos,
+																&mvndistinct);
 
 			if (!estimated)
 				break;
@@ -3936,19 +3931,13 @@ estimate_multivariate_bucketsize(PlannerInfo *root, RelOptInfo *inner,
 			Assert(ndistinct >= 1.0);
 		}
 
-		Assert(list_length(origin_varinfos) == list_length(origin_rinfos));
-
 		/* Collect unmatched clauses as otherclauses. */
-		forboth(lc1, origin_varinfos, lc2, origin_rinfos)
+		foreach(lc, varinfos)
 		{
-			GroupVarInfo *vinfo = lfirst(lc1);
-
-			if (!list_member_ptr(varinfos, vinfo))
-				/* Already estimated */
-				continue;
+			GroupVarInfo *varinfo = lfirst(lc);
 
 			/* Can't be estimated here - push to the returning list */
-			otherclauses = lappend(otherclauses, lfirst(lc2));
+			otherclauses = lappend(otherclauses, varinfo->source);
 		}
 	}
 
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 686d8c93aa8..6359e5fb689 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -3427,4 +3427,32 @@ SELECT * FROM sb_1 a, sb_2 b WHERE a.x = b.x AND a.y = b.y AND a.z = b.z;
          ->  Seq Scan on sb_2 b
 (5 rows)
 
+-- Check that the Hash Join bucket size estimator detects equal clauses correctly.
+SET enable_nestloop = 'off';
+SET enable_mergejoin = 'off';
+EXPLAIN (COSTS OFF)
+SELECT FROM sb_1 LEFT JOIN sb_2 ON (sb_2.x=sb_1.x) AND (sb_1.x=sb_2.x);
+                       QUERY PLAN                       
+--------------------------------------------------------
+ Hash Left Join
+   Hash Cond: ((sb_1.x = sb_2.x) AND (sb_1.x = sb_2.x))
+   ->  Seq Scan on sb_1
+   ->  Hash
+         ->  Seq Scan on sb_2
+(5 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT FROM sb_1 LEFT JOIN sb_2
+   ON (sb_2.x=sb_1.x) AND (sb_1.x=sb_2.x) AND (sb_1.y=sb_2.y);
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Hash Left Join
+   Hash Cond: ((sb_1.x = sb_2.x) AND (sb_1.y = sb_2.y) AND (sb_1.x = sb_2.x))
+   ->  Seq Scan on sb_1
+   ->  Hash
+         ->  Seq Scan on sb_2
+(5 rows)
+
+RESET enable_nestloop;
+RESET enable_mergejoin;
 DROP TABLE sb_1, sb_2 CASCADE;
diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql
index b71a6cd089f..da4f2fe9c93 100644
--- a/src/test/regress/sql/stats_ext.sql
+++ b/src/test/regress/sql/stats_ext.sql
@@ -1747,4 +1747,15 @@ ANALYZE sb_2;
 EXPLAIN (COSTS OFF) -- Choose hash join
 SELECT * FROM sb_1 a, sb_2 b WHERE a.x = b.x AND a.y = b.y AND a.z = b.z;
 
+-- Check that the Hash Join bucket size estimator detects equal clauses correctly.
+SET enable_nestloop = 'off';
+SET enable_mergejoin = 'off';
+EXPLAIN (COSTS OFF)
+SELECT FROM sb_1 LEFT JOIN sb_2 ON (sb_2.x=sb_1.x) AND (sb_1.x=sb_2.x);
+EXPLAIN (COSTS OFF)
+SELECT FROM sb_1 LEFT JOIN sb_2
+   ON (sb_2.x=sb_1.x) AND (sb_1.x=sb_2.x) AND (sb_1.y=sb_2.y);
+RESET enable_nestloop;
+RESET enable_mergejoin;
+
 DROP TABLE sb_1, sb_2 CASCADE;
-- 
2.39.5