Re: Improve Hash/Merge Join estimate accuracy when all predicates are Hash/Merge clauses - Mailing list pgsql-hackers

The following review has been posted through the commitfest application:
make installcheck-world:  tested, failed
Implements feature:       tested, failed
Spec compliant:           tested, failed
Documentation:            tested, failed

Hi Ilia,

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.

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.
2. Alternatively, fix FK selectivity to account for the referencing column's
   NULL fraction, though that seems like a separate change.
3. Add regression coverage for FK joins with NULLs, forced merge/hash joins,
   and uniqueified semijoins.

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

Thanks for working on this.  I think the direction has value, but I would not
commit v3 as-is without covering the FK NULL case.