Re: Fix CPU cost of right-semi and right-anti hash joins - Mailing list pgsql-hackers

On Wed, Aug 19, 2026 at 4:24 PM Haibo Yan <tristan.yim@gmail.com> wrote:
> For JOIN_RIGHT_SEMI and JOIN_RIGHT_ANTI, however, the physical outer and inner
> paths have been swapped.  outer_path_rows therefore belongs to the physically
> swapped probe side, while outer_match_frac was computed by
> compute_semi_anti_join_factors() for the canonical semi/anti orientation.

I agree with this diagnosis.  The problem is hashjointuples itself,
not just the cpu_tuple_cost multiplier.

> I tried fixing that estimate directly instead of changing the population used
> by cpu_tuple_cost:
>
>   if (path->jpath.jointype == JOIN_RIGHT_SEMI ||
>       path->jpath.jointype == JOIN_RIGHT_ANTI)
>       hashjointuples =
>           approx_tuple_count(root, &path->jpath, hashclauses);
>   else if (path->jpath.jointype == JOIN_ANTI)
>       hashjointuples = outer_path_rows - outer_matched_rows;
>   else
>       hashjointuples = outer_matched_rows;
>
> approx_tuple_count() is already used by the other branch of
> final_cost_hashjoin() to estimate the hash-clause candidate-pair population.
> Its pair-count formula is  symmetric under swapping the two input row counts,
> so it does not have the orientation mismatch above.

I don't think this is correct.  approx_tuple_count() estimates the
number of matching pairs under inner-join semantics.  A right-semi
join emits each matched inner row once, so the matching pair count
overestimates whenever inner rows match more than one outer row on
average, which is exactly the situation these join types are for, a
small hashed input probed by a large one.

For right-anti it's not even close to the right answer.  The join
emits the unmatched inner rows, and the matching pair count says
nothing about that.  If anything, the two move in opposite directions.
A mostly-unmatched inner side has pairs ~ 0 while the output is nearly
the whole inner side; a mostly-matched one can have a huge pair count
while the output is nearly empty.

The orientation-independence you point out is the right requirement,
though, and outer_match_frac already has it, as it always describes
the semijoin's LHS.  So we can compute hashjointuples leveraging that,
inner_path_rows * outer_match_frac for right-semi and inner_path_rows
* (1 - outer_match_frac) for right-anti.

Where approx_tuple_count() is the right tool is when we compute
outer_matched_rows in the inner_unique branch.  This is because each
outer row has at most one match there, so the matched outer rows are
exactly the matching pairs.

- Richard

Hi Richard,

I spent some more time on the qp_qual_cost side of this.

First, I think your v3 treatment of hashjointuples is the right one. My earlier
suggestion of using approx_tuple_count() there was mixing up two different
populations: matching pairs versus matched/unmatched inner rows. So I agree
that for right-semi/right-anti the latter is what hashjointuples should
represent.

There is still a separate issue with using the same population for the non-hash
qual cost, though.

For right-anti this is fairly clear from the executor. The right-anti handling
happens after

  ExecQual(joinqual, econtext)

so every hash-clause candidate reaching that point evaluates the joinqual.
There is no right-semi-style match-bit shortcut before it.

For example, in one test I measured:

  hash-clause candidate pairs:  1,000,000
  joinqual evaluations:         1,000,000
  v3 hashjointuples:            667

So 667 can be a reasonable estimate of the unmatched inner rows while being a
very different population from the one on which the joinqual is actually evaluated.

Right-semi is much harder because its match-bit test occurs before
ExecQual(joinqual). Once an inner tuple has found its first successful match,
later hash candidates for that tuple don’t evaluate the joinqual at all.

I tried to see whether the existing semi/hash costing information was enough
to estimate that population, in particular match_count, inner_scan_frac,
innerbucketsize, and innermcvfreq.

I don’t think it is.
For example, I have these two cases:

                           R_est          J             H
  uniform case               333       500,500      1,000,000
  5/1000 keys covered          5             5      2,000,000

where R_est is the v3 matched-inner estimate, J is the measured number of
joinqual evaluations, and H is the hash-clause candidate-pair count.

So using R_est can underestimate J by about 1500x, while using H can
overestimate it by about 400,000x.

I also tried reusing the existing

  inner_scan_frac = 2.0 / (match_count + 1.0)

model, including H * inner_scan_frac, but it does not survive the skewed cases.
The underlying problem seems to be that the executor behavior depends on how
the probe-side values are distributed across individual inner tuples, not just
on the total candidate-pair count.

innerbucketsize and innermcvfreq don’t recover that information either. They
are derived from the inner relation’s own hash-key statistics. In tests where
the fraction of inner keys receiving any candidate varied from 0.005 to 0.901,
both values remained identical because the inner relation itself had the same
uniform key distribution.

So at this point I don’t have a right-semi replacement for the qp_qual_cost
multiplier that I would be comfortable proposing. It appears to require
information about the cross-relation candidate distribution that the existing
costing state doesn’t retain.

One correction to my earlier comments: I also rechecked the tenk1 case where
v3 changes the plan. The joinqual-population error does not explain that plan
change. Even replacing the current multiplier with the measured/estimated
joinqual population changes the cost by too little to account for the plan
choice. So I don’t think that case is evidence against the v3 hashjointuples change.

There is one additional complication for a general right-anti fix: the non-hash
restriction cost computed here can include clauses that later become Join.joinqual
as well as pushed-down clauses that become Plan.qual, and those are evaluated on
different populations. So simply replacing the multiplier for the combined
qp_qual_cost would not be completely general either.

My current conclusion is therefore:

  * I agree with the v3 hashjointuples fix;
  * there is a separate qual-evaluation population issue;
  * the right-anti executor behavior makes that mismatch particularly clear;
  * right-semi also has the mismatch, but I don’t see a robust fix using the existing planner estimates;
  * I don’t think we should complicate this patch with a speculative right-semi estimator.

Thnks,

Haibo