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

Hi,

On Mon, 17 Aug 2026 at 08:57, 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.
>

Thanks for the clear example.

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?
>

Thanks for the patch! The motivation and the right-semi case make
sense to me. I wonder about the right-anti case when an additional filter
removes some unmatched rows.

I tried a case with 1000 unmatched hash tuples where the filter allowed
only one through. The executor examined all 1000 and reported "Rows
Removed by Filter: 999", while path->rows was one. The patch reduced the
cost by 9.99, exactly 999 * cpu_tuple_cost.

Could using path->rows therefore undercharge the rows that were examined
but filtered out? Would the unmatched-row count before that filter be a
better multiplier for cpu_tuple_cost, or am I misunderstanding its intended
meaning here?

Regards,
Ayush