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

From: Richard Guo <guofenglinux(at)gmail(dot)com>
To: Pg Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Fix CPU cost of right-semi and right-anti hash joins
Date: 2026-08-17 03:26:59
Message-ID: CAMbWs49XwhSC=e8_yeEaGKmKNyWR3DHH0p+e4k-bR_pgRiN8nQ@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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

Attachment Content-Type Size
v1-0001-Fix-CPU-cost-of-right-semi-and-right-anti-hash-jo.patch application/octet-stream 9.3 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Rui Zhao 2026-08-17 03:30:10 Re: Prove a NOT IN's left-hand expressions non-nullable from quals
Previous Message Bharath Rupireddy 2026-08-17 03:15:00 Re: Tighten ACL check in repack_is_permitted_for_relation()