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

On Sun, Aug 16, 2026 at 8:27 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
>
> While working on the UniqueKeys patch, I was chasing an unexpected
> plan diff in the regression tests, and that led me to a costing bug
> for right-semi and right-anti hash joins.
>
> final_cost_hashjoin() charges a per-returned-row cost (cpu_tuple_cost)
> on hashjointuples, which is always taken from the outer side. But
> JOIN_RIGHT_SEMI and JOIN_RIGHT_ANTI emit inner rows rather than outer
> ones, so for them that count is too large by roughly the ratio of the
> outer side to the inner one. Those jointypes exist to hash the
> smaller input and scan the larger one, so the overestimate is worst in
> exactly the cases where they are the right choice.
>
> Here is an example:
>
> create table s (id int primary key, a int);
> create table r (b int, c int);
> insert into s select g, g from generate_series(1, 100) g;
> insert into r select (g % 500000) + 1, g
> from generate_series(1, 2000000) g;
> vacuum analyze s, r;
>
> set max_parallel_workers_per_gather = 0;
> set work_mem = '64MB';
>
> explain select s.a from s where exists
> (select 1 from r where r.b = s.id);
>
> On master this unique-ifies the RHS and hashes the result:
>
> Hash Join (cost=45210.32..45213.69 rows=100 width=4)
> Hash Cond: (s.id = r.b)
> -> Seq Scan on s (cost=0.00..2.00 rows=100 width=8)
> -> Hash (cost=38899.03..38899.03 rows=504903 width=4)
> -> HashAggregate (cost=33850.00..38899.03 rows=504903 width=4)
> Group Key: r.b
> -> Seq Scan on r (cost=0.00..28850.00 rows=2000000 width=4)
> (7 rows)
>
> Execution Time: 1152.471 ms
>
> The hash right semi join is considered but costs 56353.25, because
> hashjointuples comes out as 2000000 (the entire RHS) for a join whose
> own row estimate is 100. Dropping that error brings it to 36354.25,
> and it wins:
>
> Hash Right Semi Join (cost=3.25..36354.25 rows=100 width=4)
> Hash Cond: (r.b = s.id)
> -> Seq Scan on r (cost=0.00..28850.00 rows=2000000 width=4)
> -> Hash (cost=2.00..2.00 rows=100 width=8)
> -> Seq Scan on s (cost=0.00..2.00 rows=100 width=8)
> (5 rows)
>
> Execution Time: 395.206 ms
>
> And this runs about 3x faster than master.
>
> Attached fix charges cpu_tuple_cost on the path's own row estimate for
> these two jointypes. The qpquals are still evaluated once per tuple
> that gets through the hashjoin, so those stay on hashjointuples.
>
> Nestloop and mergejoin need no equivalent change: neither supports
> JOIN_RIGHT_SEMI, nestloop doesn't support JOIN_RIGHT_ANTI either, and
> final_cost_mergejoin() takes its count from approx_tuple_count(),
> which multiplies the two input sizes and so does not depend on which
> side is outer.
>
> Note that there is a plan diff for an existing query in
> select_parallel.sql. There the fix raises the estimate rather than
> lowering it: approx_tuple_count() gives 50 while path->rows is 5000.
> That row estimate is itself too high, but it is already wrong before
> final_cost_hashjoin() sees it, and every other consumer believes it.
> I verified that both plans run in the same time here, within noise, so
> this patch just updates the expected output for it.
>
> Any thoughts?
>
> - Richard

Hi Richard,

Thanks for looking into this. I spent some more time on your reproducer and
instrumented both final_cost_hashjoin() and the hash join executor.

I agree with the underlying problem you found: the attractive right-semi plan
is badly overcosted on master. But I think the source of the bad cost may be
a little earlier than the final cpu_tuple_cost multiplier.

In the SEMI/ANTI/inner_unique branch of final_cost_hashjoin(), we currently
derive hashjointuples using the equivalent of:

outer_path_rows * extra->semifactors.outer_match_frac

For an ordinary SEMI/ANTI path those two quantities describe the same
orientation.

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.

So we can end up multiplying the row count of one relation by a match fraction
describing the other relation.

On your reproducer I measured approximately:

actual hash-clause candidates 400
approx_tuple_count() ~400
current hashjointuples 2,000,000
final output rows 100

So in this case the existing Branch-A estimate is off by roughly 5000x.

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.

With this change I can leave the existing CPU costing formula unchanged:

(cpu_tuple_cost + qp_qual_cost.per_tuple) * hashjointuples

and your original example still switches to the desired Hash Right Semi Join.
On my setup master took about 169 ms with the HashAggregate-based plan, while
the patched right-semi plan took about 47 ms.

I see the same candidate-count problem for JOIN_RIGHT_ANTI; with the
corresponding
unique-build-side case the old estimate was again around 2,000,000 while both
approx_tuple_count() and the measured number of hash-clause candidates were
around 400.

One reason I prefer fixing hashjointuples at this point rather than changing
cpu_tuple_cost to use path->rows is the existing select_parallel.sql case you
mentioned.

There:

approx_tuple_count() = 50
path->rows = 5000

but that right-semi candidate has inner_unique = false, so it is already using
the general approx_tuple_count() branch. Those two values are estimating
different things: approx_tuple_count() is estimating the hash-clause
candidate-pair population, while path->rows is the final semijoin output
estimate.

With this alternative fix that test therefore remains unchanged from master;
there is no select_parallel.out change.

I also tried to stress the other direction. For the existing
inner_unique = false
branch, where hashjointuples is already obtained from approx_tuple_count(), I
could reproduce cases with an additional non-hash join qualification where
moving the cpu_tuple_cost contribution to path->rows makes a right-oriented
plan look cheaper and selects a measurably slower plan.
The clearer right-anti case was about 58 ms versus 48-50 ms for the ordinary
orientation. This patch leaves those Branch-B cases untouched.

Conversely, I tested the new Branch-A estimate with a deliberately extreme
right-semi case where the executor saw about 2,000,000 hash-clause candidates
but only 5 joinqual evaluations after the match-bit short circuit. The new
estimate is substantially higher there, as expected, but it did not change
the chosen plan and runtimes were indistinguishable from master and your v1
in my tests.

I’ve attached a standalone patch implementing this approach. It does not
depend on your patch. The regression tests cover both right-semi and
right-anti, including a sparse unique-build-side case intended to exercise
the orientation mismatch directly. I also checked the inner_unique = false
paths remain unchanged and ran the full regression schedule with assertions
enabled; 243/245 tests passed, with the two failures (int8 and numeric)
reproducing identically on an unpatched build in the same environment.

So my current thinking is that the overcosting you found is real, but the
narrower fix may be to correct the right-semi/right-anti candidate estimate
rather than reinterpret cpu_tuple_cost in terms of final output rows.

Does this match your understanding of what outer_match_frac is intended to
describe here?

Thanks,
Haibo