Hi hackers, This is v3 of the standalone re-post of 0001 from the series "[PATCH 0/2] Fix two hash join costing errors in final_cost_hashjoin()" (11 November): https://www.postgresql.org/message-id/[email protected]
It has no dependency on 0002, which I posted separately [1] (now at v2) and which is tracked as CommitFest entry 7658. I am splitting the series so that each fix can be reviewed on its own merits. Changes since v2: - Rebased onto master 8303f2e13c5c2fab539e11054073a58942cb0f30, the baseline used by the current CFBot run. The costing change in final_cost_hashjoin() itself is unchanged. - The stats_ext bucket-estimation test now uses 20,000 rows for sb_2 instead of 10,000. With equal table sizes the corrected hash join has two exactly equally priced directions, and the tie is broken differently by a plain regression run and by the streaming replication run in t/027_stream_regress.pl. Making sb_2 larger removes the tie and makes the chosen plan stable in both settings. The affected estimated-row counts in the expected output are updated accordingly. - The commit message is rewritten to state the reasoning more directly. Andrei Lepikhov observed that 0001 looks like the approach discussed earlier, which concluded with 6bb6a62f3. Let me state precisely what is new. 6bb6a62f3 added estimate_multivariate_bucketsize(), which answers only when a multivariate ndistinct statistics object exists. For every table without one -- the common case -- final_cost_hashjoin() still walks the hash clauses, keeps the smallest per-clause bucket fraction, and therefore divides by the largest single-column ndistinct. Meanwhile calc_joinrel_size_estimate() multiplies the selectivities of that same join to estimate its output rows. The cost table thus holds two contradictory beliefs about one join. This patch covers the path 6bb6a62f3 left uncovered, and it uses estimate_num_groups() on the remaining clauses rather than a bare product: the same estimator the row count is built on, and bounded by the number of input rows. On a 1M x 1M three-column join with 100 distinct values per column (one row per bucket), hash join is currently priced at 166,622,722 and is never chosen. With the corrected bucket size it costs 282,717 and runs in 1,946 ms, against 4,154 ms for the merge join the planner used to pick (-53%). SEMI and ANTI joins are deliberately excluded: their probe charge is already scaled by inner_scan_frac, and repricing them regressed a merge-semi-join query in the workload by 27%. A join whose inner side is merely unique is still corrected, since its bucket really does hold about one row per key. Two expected-output files move with this patch. In contrib/pg_stash_advice the join with two hash clauses now takes a hash join on both keys, hashed on the fact table and probed with the join of the two dimension tables, instead of a nested loop on top of a single-clause hash join. In stats_ext the row-count estimates change because sb_2 is larger. Both changes follow directly from the corrected costing and the stabilized test setup. Verification: - git apply --check against 8303f2e1 is clean. - make check-world with the CFBot configure flags (--enable-cassert --enable-tap-tests --enable-injection-points --enable-debug) passes in full, including t/027_stream_regress.pl. Comments welcome. [1] https://www.postgresql.org/message-id/CAC5HyryDtq_CaL5v4k%2Bt3vGMBYeJVUVoB5sC9vp4oceK0xfWgQ%40mail.gmail.com Regards, He Kuang
From 917260a008e7837fc298ef401fb64a23c603f7dc Mon Sep 17 00:00:00 2001 From: He Kuang <[email protected]> Date: Thu, 19 Nov 2026 21:44:33 +0800 Subject: [PATCH v3] 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. contrib/pg_stash_advice records the plan chosen for a join with two hash clauses, so the corrected bucket size changes the plan recorded there: it becomes a hash join on both keys, hashed on the fact table and probed with the join of the two dimension tables, instead of a nested loop on top of a single-clause hash join. Update that expected output accordingly. The stats_ext test that checks bucket estimation uses two tables of equal size. Once the hash join is correctly costed, the two join directions have exactly equal cost, so which side becomes the hash side is decided by a tiebreak that differs between a plain regression run and the streaming replication run of 027_stream_regress.pl. Make sb_2 twice as large so the costs are no longer tied and the chosen plan is stable in both settings; update the affected estimated-row counts accordingly. --- .../expected/pg_stash_advice.out | 46 +++++----- 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 | 31 +++---- src/test/regress/sql/stats_ext.sql | 10 +-- 6 files changed, 158 insertions(+), 94 deletions(-) diff --git a/contrib/pg_stash_advice/expected/pg_stash_advice.out b/contrib/pg_stash_advice/expected/pg_stash_advice.out index 8c24a21295e..2da5d1807e5 100644 --- a/contrib/pg_stash_advice/expected/pg_stash_advice.out +++ b/contrib/pg_stash_advice/expected/pg_stash_advice.out @@ -142,21 +142,20 @@ EXPLAIN (COSTS OFF) SELECT * FROM aa_fact f LEFT JOIN aa_dim1 d1 ON f.dim1_id = d1.id LEFT JOIN aa_dim2 d2 ON f.dim2_id = d2.id WHERE val1 = 1 AND val2 = 1; - QUERY PLAN ---------------------------------------------------- - Nested Loop - -> Hash Join - Hash Cond: (f.dim2_id = d2.id) + QUERY PLAN +------------------------------------------------------------ + Hash Join + Hash Cond: ((d1.id = f.dim1_id) AND (d2.id = f.dim2_id)) + -> Nested Loop + -> Seq Scan on aa_dim2 d2 + Filter: (val2 = 1) + -> Seq Scan on aa_dim1 d1 + Filter: (val1 = 1) + -> Hash -> Seq Scan on aa_fact f - -> Hash - -> Seq Scan on aa_dim2 d2 - Filter: (val2 = 1) - -> Index Scan using aa_dim1_pkey on aa_dim1 d1 - Index Cond: (id = f.dim1_id) - Filter: (val1 = 1) Supplied Plan Advice: NESTED_LOOP_PLAIN(d1) /* matched */ -(12 rows) +(11 rows) -- Add a useless extra entry to our test stash. Shouldn't change the result -- from the previous test. @@ -172,21 +171,20 @@ EXPLAIN (COSTS OFF) SELECT * FROM aa_fact f LEFT JOIN aa_dim1 d1 ON f.dim1_id = d1.id LEFT JOIN aa_dim2 d2 ON f.dim2_id = d2.id WHERE val1 = 1 AND val2 = 1; - QUERY PLAN ---------------------------------------------------- - Nested Loop - -> Hash Join - Hash Cond: (f.dim2_id = d2.id) + QUERY PLAN +------------------------------------------------------------ + Hash Join + Hash Cond: ((d1.id = f.dim1_id) AND (d2.id = f.dim2_id)) + -> Nested Loop + -> Seq Scan on aa_dim2 d2 + Filter: (val2 = 1) + -> Seq Scan on aa_dim1 d1 + Filter: (val1 = 1) + -> Hash -> Seq Scan on aa_fact f - -> Hash - -> Seq Scan on aa_dim2 d2 - Filter: (val2 = 1) - -> Index Scan using aa_dim1_pkey on aa_dim1 d1 - Index Cond: (id = f.dim1_id) - Filter: (val1 = 1) Supplied Plan Advice: NESTED_LOOP_PLAIN(d1) /* matched */ -(12 rows) +(11 rows) -- Try an empty stash to be sure it does nothing SELECT pg_create_advice_stash('regress_empty_stash'); diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index f760ef9aa3a..220da036953 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -4435,6 +4435,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. @@ -4469,6 +4520,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. */ @@ -4584,6 +4636,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 bdda7da68f0..af691d52863 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 526430a5ea0..fcfe0c0a0e7 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 42d6c2777ea..f8a33ed90dd 100644 --- a/src/test/regress/expected/stats_ext.out +++ b/src/test/regress/expected/stats_ext.out @@ -3653,25 +3653,22 @@ CREATE TABLE sb_1 AS FROM generate_series(1, 1e4) AS gs; CREATE TABLE sb_2 AS SELECT gs % 49 AS x, gs % 51 AS y, gs % 73 AS z, 'abc' || gs AS payload - FROM generate_series(1, 1e4) AS gs; + FROM generate_series(1, 2e4) AS gs; ANALYZE sb_1, sb_2; -- During hash join estimation, the number of distinct values on each column --- is calculated. The optimizer selects the smallest number of distinct values --- and the largest hash bucket size. The optimizer decides that the hash --- bucket size is quite big because there are possibly many correlations. -EXPLAIN (COSTS OFF) -- Choose merge join +-- is calculated. Without extended statistics covering the columns, the +-- bucket size now comes from the joint ndistinct of the hash key columns, +-- bounded by the input row count, so the bucket is no longer overpriced. +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; - 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. @@ -3720,7 +3717,7 @@ RESET enable_mergejoin; SELECT * FROM check_estimated_rows('SELECT * FROM sb_2 WHERE numeric_lt(y, 1.0)'); estimated | actual -----------+-------- - 3333 | 196 + 6667 | 392 (1 row) CREATE STATISTICS extstat_sb_2_small ON numeric_lt(y, 1.0) FROM sb_2; @@ -3728,7 +3725,7 @@ ANALYZE sb_2; SELECT * FROM check_estimated_rows('SELECT * FROM sb_2 WHERE numeric_lt(y, 1.0)'); estimated | actual -----------+-------- - 196 | 196 + 392 | 392 (1 row) -- Tidy up diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql index 6045cfa51e8..88637bc5e23 100644 --- a/src/test/regress/sql/stats_ext.sql +++ b/src/test/regress/sql/stats_ext.sql @@ -1887,14 +1887,14 @@ CREATE TABLE sb_1 AS FROM generate_series(1, 1e4) AS gs; CREATE TABLE sb_2 AS SELECT gs % 49 AS x, gs % 51 AS y, gs % 73 AS z, 'abc' || gs AS payload - FROM generate_series(1, 1e4) AS gs; + FROM generate_series(1, 2e4) AS gs; ANALYZE sb_1, sb_2; -- During hash join estimation, the number of distinct values on each column --- is calculated. The optimizer selects the smallest number of distinct values --- and the largest hash bucket size. The optimizer decides that the hash --- bucket size is quite big because there are possibly many correlations. -EXPLAIN (COSTS OFF) -- Choose merge join +-- is calculated. Without extended statistics covering the columns, the +-- bucket size now comes from the joint ndistinct of the hash key columns, +-- bounded by the input row count, so the bucket is no longer overpriced. +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; -- The ndistinct extended statistics on (x, y, z) provides more reliable value -- 2.53.0
