[PATCH 1/2] Estimate hash join bucket size from the joint ndistinct of the hash keys

final_cost_hashjoin() needs to know how many inner rows share a hash key,
and prices a probe with that number. When the hash key has several
columns, the per-clause loop answers a different question: it estimates
each column separately, keeps the smallest fraction, and therefore divides
by the largest single-column ndistinct. A bucket is selected by the whole
compound key, so under the independence assumption that
calc_joinrel_size_estimate() already makes about this very join, there are
inner_rows / (nd1 * nd2 * ...) rows in it. The same cost table therefore
believes two contradictory things: output rows multiply the selectivities,
bucket size divides only by the largest one.

The cost matters because the probe term scales with the bucket: with 100
distinct values in each of two key columns, the per-clause estimate prices
every probe against a bucket of 10,000 rows, which the planner usually
cannot afford, so it sorts both inputs instead.

Commit 6bb6a62f3 added estimate_multivariate_bucketsize(), which answers
from a multivariate ndistinct statistics object when one exists; that
function is left alone. The clauses it does not answer -- any table
without such an object, which is the common case -- are estimated here
instead, with estimate_num_groups(): the same estimator the row count of
this join is built on, so bucket size and output size can no longer
disagree; and unlike a bare product it bounds the result by the number of
input rows.

The correction is deliberately not applied to semi or anti joins, in
either direction. On those paths the probe charge is already scaled by
inner_scan_frac, which describes the same duplicate factor, so the bucket
fraction is not what the executor pays; re-pricing it changes no work, it
only moves the path down the same cost table. A join whose inner side is
merely unique is still corrected: its bucket really does hold about one
row per key.
---
src/backend/optimizer/path/costsize.c | 85 +++++++++++++++++++
src/test/regress/expected/eager_aggregate.out | 51 ++++-------
src/test/regress/expected/join.out | 29 +++----
src/test/regress/expected/stats_ext.out | 17 ++--
4 files changed, 124 insertions(+), 58 deletions(-)

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 7bbddb8b..66c0ad9d 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4434,6 +4434,57 @@ initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace,
workspace->inner_rows_total = inner_path_rows_total;
}

+/*
+ * hash_join_joint_ndistinct
+ * Estimate the joint ndistinct of the inner-side hash key columns of a
+ * multi-clause hash join.
+ *
+ * The per-clause loop in final_cost_hashjoin() keeps the smallest bucket
+ * fraction seen for any one clause, i.e. the largest ndistinct of any single
+ * key column. For a compound hash key that answers the wrong question: a
+ * bucket holds the rows that match *all* the clauses, and under the same
+ * independence assumption that calc_joinrel_size_estimate() already makes
+ * there are inner_rows / (nd1 * nd2 * ...) of them. estimate_num_groups()
+ * implements exactly that estimate, and unlike a bare product it bounds the
+ * result by the number of input rows.
+ *
+ * Returns -1.0, which no valid ndistinct can match, when the estimate cannot
+ * be formed: fewer than two clauses, a clause whose inner-side operand is
+ * not a plain Var of the inner relation, or a non-OpExpr clause.
+ */
+static double
+hash_join_joint_ndistinct(PlannerInfo *root, RelOptInfo *innerrel,
+ List *hashclauses)
+{
+ List *exprs = NIL;
+ ListCell *lc;
+
+ if (list_length(hashclauses) < 2)
+ return -1.0;
+
+ foreach(lc, hashclauses)
+ {
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
+ Node *expr;
+
+ if (!IsA(rinfo->clause, OpExpr))
+ return -1.0;
+
+ if (bms_is_subset(rinfo->right_relids, innerrel->relids))
+ expr = get_rightop((OpExpr *) rinfo->clause);
+ else
+ expr = get_leftop((OpExpr *) rinfo->clause);
+
+ if (expr == NULL || !IsA(expr, Var) ||
+ !bms_is_member(((Var *) expr)->varno, innerrel->relids))
+ return -1.0;
+
+ exprs = lappend(exprs, expr);
+ }
+
+ return estimate_num_groups(root, exprs, innerrel->tuples, NULL, NULL);
+}
+
/*
* final_cost_hashjoin
* Final estimate of the cost and result size of a hashjoin path.
@@ -4468,6 +4519,7 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
double virtualbuckets;
Selectivity innerbucketsize;
Selectivity innermcvfreq;
+ double joint_ndistinct;
ListCell *hcl;

/* Set the number of disabled nodes. */
@@ -4583,6 +4635,39 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
if (thismcvfreq > 0.0 && innermcvfreq > thismcvfreq)
innermcvfreq = thismcvfreq;
}
+ /*
+ * Having more than one hash clause means the bucket is selected by the
+ * whole compound key, so the duplicate factor is the joint ndistinct,
+ * not the largest single-column one. Take whichever fraction is
+ * smaller; extended statistics, when they exist, have already had
+ * their say and only the clauses they did not cover are left here.
+ *
+ * Only for joins that look at the whole bucket, though. Semi and
+ * anti joins, in either direction, stop at the first match, and the
+ * probe charge below already says so through inner_scan_frac, so the
+ * bucket fraction is not what the executor pays for there;
+ * re-pricing it would not describe cheaper work, it would only move
+ * the path down the same cost table. A join whose inner side is
+ * merely unique still has to look
+ * at its bucket until the first row passes the join filter, and that
+ * bucket really does hold about one row per key, so the correction is
+ * applied there.
+ */
+ if (path->jpath.jointype == JOIN_SEMI ||
+ path->jpath.jointype == JOIN_ANTI ||
+ path->jpath.jointype == JOIN_RIGHT_SEMI ||
+ path->jpath.jointype == JOIN_RIGHT_ANTI)
+ joint_ndistinct = -1.0;
+ else
+ joint_ndistinct = hash_join_joint_ndistinct(root, inner_path->parent,
+ otherclauses);
+ if (joint_ndistinct > 0.0)
+ {
+ Selectivity joint_bucketsize = 1.0 / joint_ndistinct;
+
+ if (innerbucketsize > joint_bucketsize)
+ innerbucketsize = joint_bucketsize;
+ }
}

/*
diff --git a/src/test/regress/expected/eager_aggregate.out b/src/test/regress/expected/eager_aggregate.out
index bdda7da6..af691d52 100644
--- a/src/test/regress/expected/eager_aggregate.out
+++ b/src/test/regress/expected/eager_aggregate.out
@@ -1209,8 +1209,8 @@ SELECT t1.x, sum(t2.y)
LEFT JOIN eager_agg_tab1 t2 ON t1.x = t2.x AND t1.y = t2.y
JOIN eager_agg_tab1 t3 ON t1.x = t3.x AND COALESCE(t2.y, 0) < t3.y
GROUP BY t1.x ORDER BY t1.x;
- QUERY PLAN
----------------------------------------------------------------------------------------
+ QUERY PLAN
+--------------------------------------------------------------------------------------
Merge Append
Sort Key: t1.x
-> Finalize GroupAggregate
@@ -1223,21 +1223,16 @@ GROUP BY t1.x ORDER BY t1.x;
-> Partial GroupAggregate
Output: t1.x, t2.y, PARTIAL sum(t2.y)
Group Key: t1.x, t2.y
- -> Incremental Sort
+ -> Sort
Output: t1.x, t2.y
Sort Key: t1.x, t2.y
- Presorted Key: t1.x
- -> Merge Left Join
+ -> Hash Left Join
Output: t1.x, t2.y
- Merge Cond: ((t1.x = t2.x) AND (t1.y = t2.y))
- -> Sort
+ Hash Cond: ((t1.x = t2.x) AND (t1.y = t2.y))
+ -> Seq Scan on public.eager_agg_tab1_p1 t1
Output: t1.x, t1.y
- Sort Key: t1.x, t1.y
- -> Seq Scan on public.eager_agg_tab1_p1 t1
- Output: t1.x, t1.y
- -> Sort
+ -> Hash
Output: t2.y, t2.x
- Sort Key: t2.x, t2.y
-> Seq Scan on public.eager_agg_tab1_p1 t2
Output: t2.y, t2.x
-> Sort
@@ -1255,21 +1250,16 @@ GROUP BY t1.x ORDER BY t1.x;
-> Partial GroupAggregate
Output: t1_1.x, t2_1.y, PARTIAL sum(t2_1.y)
Group Key: t1_1.x, t2_1.y
- -> Incremental Sort
+ -> Sort
Output: t1_1.x, t2_1.y
Sort Key: t1_1.x, t2_1.y
- Presorted Key: t1_1.x
- -> Merge Left Join
+ -> Hash Left Join
Output: t1_1.x, t2_1.y
- Merge Cond: ((t1_1.x = t2_1.x) AND (t1_1.y = t2_1.y))
- -> Sort
+ Hash Cond: ((t1_1.x = t2_1.x) AND (t1_1.y = t2_1.y))
+ -> Seq Scan on public.eager_agg_tab1_p2 t1_1
Output: t1_1.x, t1_1.y
- Sort Key: t1_1.x, t1_1.y
- -> Seq Scan on public.eager_agg_tab1_p2 t1_1
- Output: t1_1.x, t1_1.y
- -> Sort
+ -> Hash
Output: t2_1.y, t2_1.x
- Sort Key: t2_1.x, t2_1.y
-> Seq Scan on public.eager_agg_tab1_p2 t2_1
Output: t2_1.y, t2_1.x
-> Sort
@@ -1287,21 +1277,16 @@ GROUP BY t1.x ORDER BY t1.x;
-> Partial GroupAggregate
Output: t1_2.x, t2_2.y, PARTIAL sum(t2_2.y)
Group Key: t1_2.x, t2_2.y
- -> Incremental Sort
+ -> Sort
Output: t1_2.x, t2_2.y
Sort Key: t1_2.x, t2_2.y
- Presorted Key: t1_2.x
- -> Merge Left Join
+ -> Hash Left Join
Output: t1_2.x, t2_2.y
- Merge Cond: ((t1_2.x = t2_2.x) AND (t1_2.y = t2_2.y))
- -> Sort
+ Hash Cond: ((t1_2.x = t2_2.x) AND (t1_2.y = t2_2.y))
+ -> Seq Scan on public.eager_agg_tab1_p3 t1_2
Output: t1_2.x, t1_2.y
- Sort Key: t1_2.x, t1_2.y
- -> Seq Scan on public.eager_agg_tab1_p3 t1_2
- Output: t1_2.x, t1_2.y
- -> Sort
+ -> Hash
Output: t2_2.y, t2_2.x
- Sort Key: t2_2.x, t2_2.y
-> Seq Scan on public.eager_agg_tab1_p3 t2_2
Output: t2_2.y, t2_2.x
-> Sort
@@ -1309,7 +1294,7 @@ GROUP BY t1.x ORDER BY t1.x;
Sort Key: t3_2.x
-> Seq Scan on public.eager_agg_tab1_p3 t3_2
Output: t3_2.x, t3_2.y
-(98 rows)
+(83 rows)

SELECT t1.x, sum(t2.y)
FROM eager_agg_tab1 t1
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 7773852e..9aecac74 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2756,17 +2756,16 @@ select * from
j1_tbl full join
(select * from j2_tbl order by j2_tbl.i desc, j2_tbl.k asc) j2_tbl
on j1_tbl.i = j2_tbl.i and j1_tbl.i = j2_tbl.k;
- QUERY PLAN
------------------------------------------------------------------
- Merge Full Join
- Merge Cond: ((j2_tbl.i = j1_tbl.i) AND (j2_tbl.k = j1_tbl.i))
+ QUERY PLAN
+----------------------------------------------------------------
+ Hash Full Join
+ Hash Cond: ((j2_tbl.i = j1_tbl.i) AND (j2_tbl.k = j1_tbl.i))
-> Sort
Sort Key: j2_tbl.i DESC, j2_tbl.k
-> Seq Scan on j2_tbl
- -> Sort
- Sort Key: j1_tbl.i DESC
+ -> Hash
-> Seq Scan on j1_tbl
-(8 rows)
+(7 rows)

select * from
j1_tbl full join
@@ -2776,23 +2775,23 @@ select * from
---+---+-------+---+----
| | | | 0
| | | |
- | 0 | zero | |
- | | null | |
- 8 | 8 | eight | |
- 7 | 7 | seven | |
- 6 | 6 | six | |
| | | 5 | -5
| | | 5 | -5
- 5 | 0 | five | |
- 4 | 1 | four | |
| | | 3 | -3
- 3 | 2 | three | |
2 | 3 | two | 2 | 2
| | | 2 | 4
| | | 1 | -1
| | | 0 |
+ 3 | 2 | three | |
+ 4 | 1 | four | |
1 | 4 | one | |
0 | | zero | |
+ 7 | 7 | seven | |
+ 8 | 8 | eight | |
+ 6 | 6 | six | |
+ 5 | 0 | five | |
+ | | null | |
+ | 0 | zero | |
(19 rows)

--
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 5b4bcfae..f2bb0d75 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -3661,17 +3661,14 @@ ANALYZE sb_1, sb_2;
-- bucket size is quite big because there are possibly many correlations.
EXPLAIN (COSTS OFF) -- Choose merge join
SELECT * FROM sb_1 a, sb_2 b WHERE a.x = b.x AND a.y = b.y AND a.z = b.z;
- QUERY PLAN
--------------------------------------------------------------
- Merge Join
- Merge Cond: ((a.z = b.z) AND (a.x = b.x) AND (a.y = b.y))
- -> Sort
- Sort Key: a.z, a.x, a.y
- -> Seq Scan on sb_1 a
- -> Sort
- Sort Key: b.z, b.x, b.y
+ QUERY PLAN
+------------------------------------------------------------
+ Hash Join
+ Hash Cond: ((a.x = b.x) AND (a.y = b.y) AND (a.z = b.z))
+ -> Seq Scan on sb_1 a
+ -> Hash
-> Seq Scan on sb_2 b
-(8 rows)
+(5 rows)

-- The ndistinct extended statistics on (x, y, z) provides more reliable value
-- of bucket size.
--
2.43.0