Re: Fix CPU cost of right-semi and right-anti hash joins

On Wed, Aug 19, 2026 at 11:59 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> On Wed, Aug 19, 2026 at 4:24 PM Haibo Yan <tristan(dot)yim(at)gmail(dot)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