Re: Improve Hash/Merge Join estimate accuracy when all predicates are Hash/Merge clauses

Hi Xiangxin,

Thanks for the review.

On 9/27/26 17:44, Xiangxin Zeng wrote:
> I reviewed v3 and applied it locally. The basic idea looks reasonable, but I
> found a case where using path->jpath.path.rows is less accurate than the
> existing approx_tuple_count().
>
> Reproducer:
>
> create table p (k int primary key);
> insert into p select i from generate_series(1, 10000) i;
>
> create table f (id int primary key, k int references p(k));
>
> insert into f select i, null from generate_series(1, 5000) i;
> insert into f select 5000 + i, i from generate_series(1, 5000) i;
>
> create index f_k_idx on f(k);
> analyze p;
> analyze f;
>
> set enable_hashjoin = off;
> set enable_nestloop = off;
>
> explain (analyze, costs on, timing off, summary off)
> select count(*) from f join p on f.k = p.k;
>
> With the unpatched build I see:
>
> Merge Join (cost=0.57..688.57 rows=10000) (actual rows=5000)
>
> With v3:
>
> Merge Join (cost=0.57..738.57 rows=10000) (actual rows=5000)
>
> The 50-cost delta matches 5000 extra tuples at the default cpu_tuple_cost of
> 0.01. approx_tuple_count() accounts for the NULL fraction of f.k and estimates
> 5000 rows, while path.rows is inflated to 10000 by FK-based join selectivity.

+1. I get the same costs, and final_cost_mergejoin() shows path.rows =
10000 vs approx_tuple_count() = 5000. With the FK constraint dropped,
both are 5000 and the costs are identical.

> So I think JOIN_INNER plus:
>
> list_length(joinrestrictinfo) == list_length(merge/hashclauses)
>
> is not sufficient. path.rows may already include FK-specific selectivity.
>
> Possible directions:
>
> 1. Avoid the substitution when FK selectivity has influenced the joinrel row
> estimate.

That would also undo the multi-column FK case upthread, which is the
point of the patch.

> 2. Alternatively, fix FK selectivity to account for the referencing column's
> NULL fraction, though that seems like a separate change.

I went this way, since the wrong number comes from the FK estimate
itself: even on master, EXPLAIN shows rows=10000 for your query. v4 is
now a series:

0001 derates the FK-based selectivity by the fraction of referencing
rows with a NULL in the FK columns, which removes the XXX in
get_foreign_key_join_selectivity(). The two concerns from that comment
clause of the referencing rel are skipped, so their NULLs are not
counted twice. For multi-column FKs the largest per-column null fraction
is used, since the columns are typically NULL together.

> 3. Add regression coverage for FK joins with NULLs, forced merge/hash joins,
> and uniqueified semijoins.

Patches only change run costs, which costs-off EXPLAIN doesn't show, and
a test relying on a plan flip seems fragile; if you have a specific test
in mind, I'd be glad to add it.

> I also think the list-length check should have a comment explaining that
> merge/hashclauses are assumed to be a subset of joinrestrictinfo.

0002 is v3 plus the comment you asked for.

If you find more familiar examples with inaccurate costs, don't hesitate
to give them.

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/