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

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/