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

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!

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

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/

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.

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/

Hi Ilia,

Thanks for the v4.

I rebuilt it and found a simple case where 0001 can be less accurate than master.

CREATE TABLE p(k int PRIMARY KEY);
CREATE TABLE f(id int PRIMARY KEY, k int REFERENCES p(k), aux int);

INSERT INTO p SELECT i FROM generate_series(1, 10000) i;
INSERT INTO f SELECT i, i, 1 FROM generate_series(1, 10000) i;
INSERT INTO f SELECT 10000 + i, NULL, 2 FROM generate_series(1, 10000) i;
ANALYZE p;
ANALYZE f;

SET enable_hashjoin = off;
SET enable_nestloop = off;
EXPLAIN (COSTS ON)
SELECT count(*) FROM f JOIN p ON f.k = p.k WHERE f.aux = 1;
SELECT count(*) FROM f JOIN p ON f.k = p.k WHERE f.aux = 1;

The global nullfrac for f.k is 0.5, but after f.aux = 1 all remaining rows have non-NULL f.k. Master estimates 10000 rows, matching the actual result. v4 estimates 5000.

So using the global stanullfrac can still be inaccurate when NULLs are correlated with filters on other columns. I am not sure what the right fix should be: conditional nullfrac, extended statistics, or just documenting the limitation. I'd appreciate feedback from people more familiar with selfuncs.

For 0002, I do not have a new semantic counterexample. The JOIN_INNER and equal-list-length restriction still looks reasonable to me.

I would especially appreciate feedback from people more familiar with selfuncs and cost estimate.

Xiangxin

On Mon, Oct 19, 2026 at 4:08 PM zengxx <xiangxin_zeng@qq.com> wrote:

I rebuilt it and found a simple case where 0001 can be less accurate than master.

CREATE TABLE p(k int PRIMARY KEY);
CREATE TABLE f(id int PRIMARY KEY, k int REFERENCES p(k), aux int);

INSERT INTO p SELECT i FROM generate_series(1, 10000) i;
INSERT INTO f SELECT i, i, 1 FROM generate_series(1, 10000) i;
INSERT INTO f SELECT 10000 + i, NULL, 2 FROM generate_series(1, 10000) i;
ANALYZE p;
ANALYZE f;

SET enable_hashjoin = off;
SET enable_nestloop = off;
EXPLAIN (COSTS ON)
SELECT count(*) FROM f JOIN p ON f.k = p.k WHERE f.aux = 1;
SELECT count(*) FROM f JOIN p ON f.k = p.k WHERE f.aux = 1;

The global nullfrac for f.k is 0.5, but after f.aux = 1 all remaining rows have non-NULL f.k. Master estimates 10000 rows, matching the actual result. v4 estimates 5000.

So using the global stanullfrac can still be inaccurate when NULLs are correlated with filters on other columns. I am not sure what the right fix should be: conditional nullfrac, extended statistics, or just documenting the limitation. I'd appreciate feedback from people more familiar with selfuncs.

Thanks for the example. This illustrates a tradeoff in the patch.

Master effectively assumes that every referencing row surviving the
filters has a match, regardless of NULLs in the FK columns. This can
overestimate the join size when some of those rows have NULL FK
values.

The patch accounts for those NULLs, but uses the table-wide null
fraction, assuming that FK nullness is independent of filters on other
columns. This improves the estimate for an unfiltered referencing
table and for filters where that assumption holds. However, it can
underestimate when a filter preferentially selects non-NULL FK values,
as in your example. Conversely, if a filter selects mostly NULL FK
values, it can still overestimate.

Skipping the correction whenever there are filters would avoid your
regression, but would also lose the improvement for independent
filters. Estimating a conditional null fraction could address the
correlation, but would require additional work beyond the current
patch.

So the patch trades the current assumption that all surviving
referencing rows match for an independence assumption about FK
nullness and filters. I should make that limitation explicit in the
patch description and code comments.

I would especially appreciate feedback from people more familiar with selfuncs and cost estimate.

I also agree that feedback from someone more familiar with this part
of the selectivity estimator would be helpful, particularly on whether
this tradeoff is acceptable or whether the correction needs a more
conservative scope.

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