[PATCH v2] Estimate hash join bucket size from the joint ndistinct of the hash keys

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 v2] Estimate hash join bucket size from the joint ndistinct of the hash keys
Date: 2026-11-18 14:50:36
Message-ID: CAC5Hyrw7OD3w0V3NuC4TwnqfG6pD79Ua0bmcBTyzT5WJKXvqWw@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi,

This is v2 of the first patch of the series posted here [1], now split
into its own thread so it can be tracked on the commitfest
independently. It is rebased onto master (as of 45047c51aab), and the
patch file is attached.

Andrei asked in [2] whether this patch carries new arguments for
re-visiting the line drawn by the earlier bucket-size discussion [3],
which concluded with 6bb6a62f3. The short answer is yes; the full
answer is in the commit message of the attached patch. In brief:

- Mechanically, the patch does not touch 6bb6a62f3's decision.
estimate_multivariate_bucketsize() keeps priority, the new joint
estimate runs only on the clauses it returns uncovered, and the
final min() can only shrink the estimated bucket, never enlarge it,
so extended statistics still have the final say wherever they exist.

- For the uncovered clauses -- tables without such statistics, the
common case -- the patch deliberately re-visits the conservative
line. The arguments: the same cost table currently prices this
join's output rows under the independence assumption while pricing
the bucket by the largest single-column ndistinct, which is
self-contradictory; estimate_num_groups() is not the bare product
rejected in [3] -- it uses sampled per-column ndistinct, applies
functional dependencies, and is bounded by the input rows; and
semi/anti joins are excluded, where keeping them regressed a
merge-semi-join query in the workload by 27%.

- The exposure we do not claim to have solved is a fully correlated
inner side without statistics, where the estimate stays optimistic
by roughly the per-column product. Consistency with the rows
estimator is the bet, since the planner already takes it for the
join's row count. A shape where this clearly misleads plan choice
would make an excellent test case, and I will happily add one.

Changes since the series version: rebased; the joint estimate is now
computed once after the per-clause loop instead of once per clause;
the stale "-- Choose merge join" comments in the stats_ext case now
describe the new behavior (choose hash join); and the plan recorded
by contrib/pg_stash_advice for the two-key join changes, so its
expected file is updated accordingly. Costing logic and the measured
results are unchanged: on the motivating query the corrected estimate
turns a never-chosen hash join (cost 166,622,722) into the winning
plan (cost 282,717; 1,946 ms vs 4,154 ms for the merge join it used
to pick), and workload runs with and without the patch stayed within
the +/-2% run-to-run noise band.

I will register this on the commitfest once the thread is archived.

Thanks,
He Kuang

[1] https://www.postgresql.org/message-id/20261111121207.322512-1-hekuang.git@gmail.com
[2] https://www.postgresql.org/message-id/f451ecb0-eccc-4c71-b806-6fce8fb543ab@gmail.com
[3] https://www.postgresql.org/message-id/1de52b5f-e4a6-5729-eeef-51d524534665@enterprisedb.com

Attachment Content-Type Size
hash-join-bucket-size-joint-ndistinct-v2.patch text/plain 20.8 KB

Browse pgsql-hackers by date

  From Date Subject
Next Message cca5507 2026-11-18 14:56:45 Avoid copying MinimalTuple twice in ExecHashSkewTableInsert()
Previous Message Nikhil Sontakke 2026-11-18 14:27:51 Re: Dropping a composite attribute causes data integrity violations