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/
From 4fa968ab5f7b9163563a1de16e123b0675fd454d Mon Sep 17 00:00:00 2001
From: Evdokimov Ilia <[email protected]>
Date: Mon, 28 Sep 2026 15:49:36 +0500
Subject: [PATCH v4 2/2] Use exact join size estimate for plain inner
merge/hash joins
For a plain inner join whose only join clauses are the merge/hash
clauses, path->jpath.path.rows is the number of tuples passing those
clauses, so final_cost_mergejoin()/final_cost_hashjoin() can use it
instead of recomputing an approximation via approx_tuple_count(). The
joinrel estimate is better when the clauses match a multi-column FK
constraint, since approx_tuple_count() treats them as independent.
For SEMI/LEFT/FULL joins path->jpath.path.rows is a different quantity,
so keep the substitution JOIN_INNER-only.
---
src/backend/optimizer/path/costsize.c | 24 ++++++++++++++++++++++--
1 file changed, 22 insertions(+), 2 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index cd494d29cbb..ea300beaa2e 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4062,8 +4062,20 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
/*
* Get approx # tuples passing the mergequals. We use approx_tuple_count
* here because we need an estimate done with JOIN_INNER semantics.
+ * However, for a plain inner join with no restriction clauses beyond the
+ * mergeclauses, path->jpath.path.rows already gives an equally (or more)
+ * accurate figure computed with JOIN_INNER semantics, so we reuse it and
+ * skip the extra call. (The mergeclauses are a subset of
+ * joinrestrictinfo, so equal list lengths mean they are the same
+ * clauses.) For any other jointype, path->jpath.path.rows reflects that
+ * jointype's own semantics (e.g. clamped to the outer/inner size for
+ * LEFT/FULL joins), not JOIN_INNER, so it can't be substituted.
*/
- mergejointuples = approx_tuple_count(root, &path->jpath, mergeclauses);
+ if (path->jpath.jointype == JOIN_INNER &&
+ list_length(path->jpath.joinrestrictinfo) == list_length(mergeclauses))
+ mergejointuples = path->jpath.path.rows;
+ else
+ mergejointuples = approx_tuple_count(root, &path->jpath, mergeclauses);
/*
* When there are equal merge keys in the outer relation, the mergejoin
@@ -4704,7 +4716,12 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
* inner_unique joins that is the matched outer rows, and for ANTI the
* unmatched ones, both available from outer_matched_rows computed above.
* For plain joins, use approx_tuple_count(), which gives an estimate done
- * with JOIN_INNER semantics.
+ * with JOIN_INNER semantics -- except for a plain inner join with no
+ * restriction clauses beyond the hashclauses, where path->jpath.path.rows
+ * already gives an equally (or more) accurate JOIN_INNER-semantics figure
+ * for free, and calling approx_tuple_count() again would be redundant.
+ * (As in final_cost_mergejoin(), the hashclauses are a subset of
+ * joinrestrictinfo, so equal list lengths mean they are the same.)
*/
if (path->jpath.jointype == JOIN_RIGHT_SEMI)
hashjointuples = clamp_row_est(inner_path_rows *
@@ -4716,6 +4733,9 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
hashjointuples = outer_path_rows - outer_matched_rows;
else if (path->jpath.jointype == JOIN_SEMI || extra->inner_unique)
hashjointuples = outer_matched_rows;
+ else if (path->jpath.jointype == JOIN_INNER &&
+ list_length(path->jpath.joinrestrictinfo) == list_length(hashclauses))
+ hashjointuples = path->jpath.path.rows;
else
hashjointuples = approx_tuple_count(root, &path->jpath, hashclauses);
--
2.43.0
From 694c64bc50cd11f1e41eb110b3bcf0997edb50be Mon Sep 17 00:00:00 2001
From: Evdokimov Ilia <[email protected]>
Date: Mon, 28 Sep 2026 15:49:01 +0500
Subject: [PATCH v4 1/2] Account for NULLs in FK-based join selectivity
get_foreign_key_join_selectivity() assumes that each referencing row
matches exactly one row in the referenced table. That's not true for
rows having a NULL in any of the referencing columns, which match
nothing, so the join size could be overestimated considerably: by 2x
when half of the referencing values are NULL. The regular clause-based
estimate in eqjoinsel() does take the null fraction into account.
Derate the FK-based selectivity by the fraction of referencing rows with
a NULL in some FK column. The XXX comment there gave two reasons for
not doing so, which are handled as follows. Columns constrained by a
strict restriction clause of the referencing rel are skipped, since
their NULLs are already excluded from its row count. For multi-column
FKs, take the largest per-column null fraction: that's exact when the
columns are NULL together, as is typical, and a lower bound otherwise.
---
src/backend/optimizer/path/costsize.c | 70 +++++++++++++++++++++++----
1 file changed, 61 insertions(+), 9 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 7bbddb8bee4..cd494d29cbb 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -88,12 +88,14 @@
#include "access/amapi.h"
#include "access/htup_details.h"
#include "access/tsmapi.h"
+#include "catalog/pg_statistic.h"
#include "executor/executor.h"
#include "executor/nodeAgg.h"
#include "executor/nodeHash.h"
#include "executor/nodeMemoize.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
+#include "nodes/multibitmapset.h"
#include "nodes/nodeFuncs.h"
#include "nodes/tidbitmap.h"
#include "optimizer/clauses.h"
@@ -108,6 +110,7 @@
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
#include "utils/spccache.h"
+#include "utils/syscache.h"
#include "utils/tuplesort.h"
@@ -198,6 +201,8 @@ static Selectivity get_foreign_key_join_selectivity(PlannerInfo *root,
Relids inner_relids,
SpecialJoinInfo *sjinfo,
List **restrictlist);
+static Selectivity fkey_referencing_nullfrac(PlannerInfo *root,
+ ForeignKeyOptInfo *fkinfo);
static Cost append_nonpartial_cost(List *subpaths, int numpaths,
int parallel_workers);
static void set_rel_width(PlannerInfo *root, RelOptInfo *rel);
@@ -6051,15 +6056,9 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
/*
* Finally we get to the payoff: estimate selectivity using the
* knowledge that each referencing row will match exactly one row in
- * the referenced table.
- *
- * XXX that's not true in the presence of nulls in the referencing
- * column(s), so in principle we should derate the estimate for those.
- * However (1) if there are any strict restriction clauses for the
- * referencing column(s) elsewhere in the query, derating here would
- * be double-counting the null fraction, and (2) it's not very clear
- * how to combine null fractions for multiple referencing columns. So
- * we do nothing for now about correcting for nulls.
+ * the referenced table. That's not true for referencing rows with
+ * nulls in the FK columns, which match nothing; we derate the
+ * estimate for those below.
*
* XXX another point here is that if either side of an FK constraint
* is an inheritance parent, we estimate as though the constraint
@@ -6102,6 +6101,9 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
fkselec *= 1.0 / ref_tuples;
}
+ /* Referencing rows with nulls in the FK columns have no match */
+ fkselec *= 1.0 - fkey_referencing_nullfrac(root, fkinfo);
+
/*
* If any of the FK columns participated in ec_has_const ECs, then
* equivclass.c will have generated "var = const" restrictions for
@@ -6147,6 +6149,56 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
return fkselec;
}
+/*
+ * fkey_referencing_nullfrac
+ * Estimate the fraction of the referencing rel's rows that have a null
+ * in at least one of the FK columns.
+ *
+ * Columns constrained by a strict restriction clause of the referencing rel
+ * are skipped: their nulls are already excluded from the rel's row count, so
+ * counting them again here would underestimate the join size. For the
+ * remaining columns we take the largest null fraction. That's exact when
+ * the columns are null together, as is typical for multi-column FKs, and
+ * otherwise it's a lower bound.
+ */
+static Selectivity
+fkey_referencing_nullfrac(PlannerInfo *root, ForeignKeyOptInfo *fkinfo)
+{
+ RelOptInfo *con_rel = find_base_rel(root, fkinfo->con_relid);
+ RangeTblEntry *rte = planner_rt_fetch(fkinfo->con_relid, root);
+ List *nonnullable_vars = NIL;
+ Selectivity nullfrac = 0.0;
+
+ foreach_node(RestrictInfo, rinfo, con_rel->baserestrictinfo)
+ nonnullable_vars =
+ mbms_add_members(nonnullable_vars,
+ find_nonnullable_vars((Node *) rinfo->clause));
+
+ for (int i = 0; i < fkinfo->nkeys; i++)
+ {
+ AttrNumber attno = fkinfo->conkey[i];
+ HeapTuple tup;
+
+ if (mbms_is_member(fkinfo->con_relid,
+ attno - FirstLowInvalidHeapAttributeNumber,
+ nonnullable_vars))
+ continue;
+
+ tup = SearchSysCache3(STATRELATTINH,
+ ObjectIdGetDatum(rte->relid),
+ Int16GetDatum(attno),
+ BoolGetDatum(rte->inh));
+ if (HeapTupleIsValid(tup))
+ {
+ nullfrac = Max(nullfrac,
+ ((Form_pg_statistic) GETSTRUCT(tup))->stanullfrac);
+ ReleaseSysCache(tup);
+ }
+ }
+
+ return nullfrac;
+}
+
/*
* set_subquery_size_estimates
* Set the size estimates for a base relation that is a subquery.
--
2.43.0
