Hi, On Mon, 17 Aug 2026 at 08:57, Richard Guo <[email protected]> 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
