Hi hackers,
Extended statistics are currently only applied when all clauses in a
clause list reference a single relation. When one side of an equality
clause is a Var from different relation - which is exactly what happens
while costing a parameterized inner path of a nested loop join - the
correlation between columns of the parametrized relation is silently
ignored, and the planner falls back to the standard per-column
independence assumption for those clauses.
For relations with correlated join columns this can badly estimate the
number of matching rows per probe, which in turn can lead the planner to
pick a needlessly expensive access path for the inner side.
Small example
-----------------------
```
CREATE TABLE big (a int NOT NULL, b int NOT NULL, payload text);
-- b is fully determined by a (functional dependency, degree 1.0)
INSERT INTO big SELECT i % 1000, (i % 1000) / 10, 'x' FROM
generate_series(1, 200000) i;
CREATE INDEX big_ab_idx ON big (a, b);
ANALYZE big;
CREATE TABLE small (a int NOT NULL, b int NOT NULL);
INSERT INTO small SELECT DISTINCT a, b FROM big LIMIT 50;
ANALYZE small;
-- forced to Nested Loop so we exercise the parameterized inner index scan
SET enable_mergejoin = off;
SET enable_hashjoin = off;
EXPLAIN ANALYZE SELECT * FROM big t1 JOIN small t2 ON t1.a = t2.a AND
t1.b = t2.b;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.29..579.23 rows=100 width=18) (actual
time=0.012..2.570 rows=10000.00 loops=1)
Buffers: shared hit=10109
-> Seq Scan on small t2 (cost=0.00..1.50 rows=50 width=8) (actual
time=0.004..0.006 rows=50.00 loops=1)
Buffers: shared hit=1
-> Index Scan using big_ab_idx on big t1 (cost=0.29..11.53
*rows=2* width=10) (actual time=0.001..0.044 rows=200.00 loops=50)
Index Cond: ((a = t2.a) AND (b = t2.b))
Index Searches: 50
Buffers: shared hit=10108
Planning:
Buffers: shared hit=17
Planning Time: 0.110 ms
Execution Time: 2.690 ms
(12 rows)
SELECT COUNT(DISTINCT a), COUNT( DISTINCT b), COUNT(DISTINCT payload)
FROM big ;
count | count | count
-------+-------+-------
1000 | 100 | 1
(1 row)
```
The planner estimates 2 rows per probe (independent multiplication
1/1000 * 1/100), while the actual number is 200 - a 100x underestimate
driven entirely by a -> b dependency. Now after the patch:
```
CREATE STATISTICS (dependencies) ON a, b FROM big;
ANALYZE big;
EXPLAIN ANALYZE SELECT * FROM big t1 JOIN small t2 ON t1.a = t2.a AND
t1.b = t2.b;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=5.86..4474.19 rows=98 width=18) (actual
time=0.772..14.091 rows=10000.00 loops=1)
Buffers: shared hit=9844 read=265
-> Seq Scan on small t2 (cost=0.00..1.50 rows=50 width=8) (actual
time=0.297..0.301 rows=50.00 loops=1)
Buffers: shared read=1
-> Bitmap Heap Scan on big t1 (cost=5.86..87.45 *rows=200*
width=10) (actual time=0.040..0.253 rows=200.00 loops=50)
Recheck Cond: ((a = t2.a) AND (b = t2.b))
Heap Blocks: exact=10000
Buffers: shared hit=9844 read=264
-> Bitmap Index Scan on big_ab_idx (cost=0.00..5.81 rows=200
width=0) (actual time=0.014..0.014 rows=200.00 loops=50)
Index Cond: ((a = t2.a) AND (b = t2.b))
Index Searches: 50
Buffers: shared hit=98 read=10
Planning:
Buffers: shared hit=35 read=5
Planning Time: 0.648 ms
Execution Time: 14.428 ms
(16 rows)
```
The row estimate (200) now matches actual exactly.
Implementation
-----------------------
A clause is now also considered compatible when it has exactly two
varnos, one of which is the 'relid' being estimated and the other
belongs to some single other relation. That other side is treated like a
pseudoconstant for the purposes of this check - its actual value doesn't
matter, only that it is fixed for the duration of one parameterized
probe. The degree logic itself is unchanged.
When clause list doesn't reference a single relation but is being
estimated for a specific varRelid - i.e. we are costing a parameterized
path - look up that relation's dependency extended statistics and apply
them the same way,via dependencies_clauselist_selectivity.
Note this only helps the `dependencies` kind of ext stats. There is
already ongoing work in this direction [0].
Any feedback are welcome.
[0]:
https://www.postgresql.org/message-id/flat/9c16f5aa-06a4-4eb0-be2e-cb7122343bc2%40tantorlabs.com#6073e26e0b3c4a03ee226fb693749396
--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/
From b8bfc22f919f03d63c809cb15c22f9c78e2b9d75 Mon Sep 17 00:00:00 2001
From: Ilia Evdokimov <[email protected]>
Date: Mon, 17 Aug 2026 14:10:45 +0300
Subject: [PATCH v1] Use extended statistics for join clauses during
parameterized costing
Dependency-based extended statistics were only considered when every
clause in a clause list referenced a single relation. When costing a
parameterized inner path of a nested loop join, one side of an
equality clause is a Var belonging to the outer relation, so the
whole clause list was rejected by dependency_is_compatible_clause()
and the planner fell back to the default per-column independence
assumption - even though the parameterized relation's own extended
statistics could produce a much better estimate.
Teach dependency_is_compatible_clause() to also accept clauses of the
form "relid.a = otherrel.b": the other relation's Var is treated like
a pseudoconstant for compatibility-checking purposes, since its value
is fixed for the duration of one parameterized probe and the
degree-based estimate does not depend on it. The degree lookup and
combination logic itself is unchanged.
---
src/backend/optimizer/path/clausesel.c | 10 ++++++++
src/backend/statistics/dependencies.c | 35 +++++++++++++++++++++++---
2 files changed, 42 insertions(+), 3 deletions(-)
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 25c4d177ad9..57a370d5b14 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -155,6 +155,16 @@ clauselist_selectivity_ext(PlannerInfo *root,
&estimatedclauses, false);
}
+ if (use_extended_stats && rel == NULL && varRelid != 0)
+ {
+ RelOptInfo *paramrel = find_base_rel(root, varRelid);
+
+ if (paramrel->rtekind == RTE_RELATION && paramrel->statlist != NIL)
+ s1 *= dependencies_clauselist_selectivity(root, clauses, varRelid,
+ jointype, sjinfo, paramrel,
+ &estimatedclauses);
+ }
+
/*
* Apply normal selectivity estimates for remaining clauses. We'll be
* careful to skip any clauses which were already estimated above.
diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistics/dependencies.c
index 81bcf76cc1c..211100b1547 100644
--- a/src/backend/statistics/dependencies.c
+++ b/src/backend/statistics/dependencies.c
@@ -734,8 +734,14 @@ dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *attnum)
if (rinfo->pseudoconstant)
return false;
- /* Clauses referencing multiple, or no, varnos are incompatible */
- if (bms_membership(rinfo->clause_relids) != BMS_SINGLETON)
+ /*
+ * Clauses referencing more than two, or no, varnos are incompatible.
+ * A second varno is allowed because we also accept "relid's Var =
+ * other relation's Var" below, e.g. a parameterized index qual like
+ * "t1.a = t2.b" while costing an index scan on t1.
+ */
+ if (bms_num_members(rinfo->clause_relids) > 2 ||
+ bms_num_members(rinfo->clause_relids) == 0)
return false;
clause = (Node *) rinfo->clause;
@@ -756,7 +762,30 @@ dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *attnum)
else if (is_pseudo_constant_clause(linitial(expr->args)))
clause_expr = lsecond(expr->args);
else
- return false;
+ {
+ /*
+ * Neither argument is a pseudoconstant, but this can still be a
+ * usable equality clause when costing a parameterized path: one
+ * argument is a Var of "relid" and the other is a Var of some
+ * other single relation, which is fixed for the duration of one
+ * parameterized scan and can be treated like a constant.
+ */
+ Bitmapset *largrelids = pull_varnos(NULL, linitial(expr->args));
+ Bitmapset *rargrelids = pull_varnos(NULL, lsecond(expr->args));
+
+ if (bms_membership(largrelids) == BMS_SINGLETON &&
+ bms_singleton_member(largrelids) == relid &&
+ bms_membership(rargrelids) == BMS_SINGLETON &&
+ bms_singleton_member(rargrelids) != relid)
+ clause_expr = linitial(expr->args);
+ else if (bms_membership(rargrelids) == BMS_SINGLETON &&
+ bms_singleton_member(rargrelids) == relid &&
+ bms_membership(largrelids) == BMS_SINGLETON &&
+ bms_singleton_member(largrelids) != relid)
+ clause_expr = lsecond(expr->args);
+ else
+ return false;
+ }
/*
* If it's not an "=" operator, just ignore the clause, as it's not
--
2.34.1
