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

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