| From: | He Kuang <hekuang(dot)git(at)gmail(dot)com> |
|---|---|
| To: | pgsql-hackers(at)lists(dot)postgresql(dot)org |
| Cc: | Andrei Lepikhov <lepihov(at)gmail(dot)com>, Richard Guo <guofenglinux(at)gmail(dot)com> |
| Subject: | [PATCH v3] Estimate hash join bucket size from the joint ndistinct of the hash keys |
| Date: | 2026-11-19 14:34:47 |
| Message-ID: | CAC5Hyrw_MYaL1PGMEWC+3Wjc1Kja_brz08Pyd6wY7v9pDfkDUg@mail.gmail.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
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/20261111121207.322512-1-hekuang.git@gmail.com
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.
Regards,
He Kuang
| Attachment | Content-Type | Size |
|---|---|---|
| hash-join-bucket-size-joint-ndistinct-v3.patch | text/plain | 21.1 KB |
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Tomas Vondra | 2026-11-19 14:42:57 | Re: reconsider_full_join_clause fails to consider if COALESCE() arguments are NULL-preserving |
| Previous Message | Nathan Bossart | 2026-11-19 14:33:17 | Re: Logical Implication |