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

On 9/7/26 20:39, Ilia Evdokimov wrote:

> On 7/10/25 13:09, Ilia Evdokimov wrote:
>
>> The planner currently calls approx_tuple_count() to estimate
>> hashjointuples and mergejointuples. That makes sense when
>> joinrestrictinfo contains additional clauses beyond the hash/merge
>> equality list. But if all join restriction clauses are exactly those
>> hash/merge clauses, the estimate already computed in
>> path->jpath.path.rows is usually more accurate (and free).
>>
>> This patch reuses path->jpath.path.rows in that case and skips
>> approx_tuple_count().
>
> I went back and looked more closely at the twoi cases that got worse -
> select_parallel.sql and updatable_views.sql - and it turns out both
> are explained by the same root cause: neither query is a plain inner
> join.select_parallel.sql's case is a semi join, and
> updatable_views.sql's is a left/right join. In both cases
> path->jpath.rows is not the same quantity that
> mergejointuples/hashjointuples are supposed to present.
>
> calc_joinrel_size_estimate() computes rows differently depending on
> jointype. For JOIN_INNER it's outer_rows * inner_rows * selectivity -
> exactly the quantity approx_tuple_count() tries to approximate, just
> computed more accurately. So only for JOIN_INNER do
> path->jpath.path.rows and "tuples passing the merge/hash quals" coincide.
>
> The updated v2-patch restricts the substitution to
> path->jpath.jointype == JOIN_INNER.
>
> Looking forward to your feedback!
>
I've found example for explanation:

```
CREATE TABLE catalog_t (id INT, grp INT, PRIMARY KEY (id, grp));
CREATE TABLE events_t (id INT, grp INT, val INT, FOREIGN KEY (id, grp)
REFERENCES catalog_t (id, grp));
INSERT INTO catalog_t SELECT i, i % 5 FROM generate_series(1, 2000) i;
INSERT INTO events_t SELECT (i % 2000) + 1, ((i % 2000) + 1) % 5, i FROM
generate_series(1, 100000) i;
ANALYZE catalog_t, events_t;
SET enable_hashjoin = off;
SET enable_nestloop = off;

EXPLAIN
SELECT * FROM events_t e
JOIN catalog_t c ON e.id = c.id AND e.grp = c.grp;
```

Before patch:
```
                                           QUERY PLAN
-------------------------------------------------------------------------------------------------
 Merge Join  (cost=9846.17..*10864.02* rows=100000 width=20)
   Merge Cond: ((c.id = e.id) AND (c.grp = e.grp))
   ->  Index Only Scan using catalog_t_pkey on catalog_t c
(cost=0.28..58.28 rows=2000 width=8)
   ->  Sort  (cost=9845.82..10095.82 rows=100000 width=12)
         Sort Key: e.id, e.grp
         ->  Seq Scan on events_t e  (cost=0.00..1541.00 rows=100000
width=12)
(6 rows)
```

After patch:
```
                                           QUERY PLAN
-------------------------------------------------------------------------------------------------
 Merge Join  (cost=9846.17..*11664.02* rows=100000 width=20)
   Merge Cond: ((c.id = e.id) AND (c.grp = e.grp))
   ->  Index Only Scan using catalog_t_pkey on catalog_t c
(cost=0.28..58.28 rows=2000 width=8)
   ->  Sort  (cost=9845.82..10095.82 rows=100000 width=12)
         Sort Key: e.id, e.grp
         ->  Seq Scan on events_t e  (cost=0.00..1541.00 rows=100000
width=12)
(6 rows)
```

Note that estimated rows = 100k does not change - it was already correct
before the patch, since it's computed independently
by calc_joinrel_size_estimate() at the joinrel level. What changes is
the internal costing: cpu_per_tuple * mergejointuples. The delta 800 is
exactly (100k - 20k) * cpu_tuple_cost, where 100k and 20k are
mergejointuples before/after patch. EXPLAIN ANALYZE confirms actual rows
= 100000.00 => the corrected figure matches what the executor actually
produces, and the old one was off by 5x.

mergejointuples/hashjointuples are meant to estimate the number of
tuples of tuple pairs passing the merge/hash quals, computed with
JOIN_INNER semantics. Currently that's always obtained via
approx_tuple_count(), which estimates selectivity by calling
clause_selectivity() independently for each clause and multiplying the
results - i.e. is assumes the join clauses are statistically
independent. calc_joinrel_size_estimate() computes the same conceptual
quantity for a plan JOIN_INNER (outer_rows * inner_rows * selectivity),
but gets the selectivity from clauselist_selectivity() over the entire
clause list at once, which additionally calls
get_foreign_key_join_selectivity() to detect clauses matching a declared
FK constraint. In the example above (id, grp) is a real FK, so grp is
recognized as adding no extra selectivity once id is known - the
FK-aware estimate correctly comes out to 100k, while
independent-multiplication estimate divides it by ~5, landing to 20k.

Since path->jpath.path.rows already holds this better estimate whenever
joinrestrictinfo consists solely of the merge/hash clauses, we can just
reuse it instead of less accurate, computation via approx_tuple_count()

I attached v3-patch with additional comments.

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