Apply extended statistics to join clause during parameterized path costing

Started by Ilia Evdokimov3 months ago3 messageshackers
Jump to latest
#1Ilia Evdokimov
ilya.evdokimov@tantorlabs.com

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]/messages/by-id/9c16f5aa-06a4-4eb0-be2e-cb7122343bc2@tantorlabs.com.

Any feedback are welcome.

[0]: /messages/by-id/9c16f5aa-06a4-4eb0-be2e-cb7122343bc2@tantorlabs.com
/messages/by-id/9c16f5aa-06a4-4eb0-be2e-cb7122343bc2@tantorlabs.com

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

Attachments:

t253450_1
v1-0001-Use-extended-statistics-for-join-clauses-during-p.patchtext/x-patch; charset=UTF-8; name=v1-0001-Use-extended-statistics-for-join-clauses-during-p.patchDownload+42-4
#2Tomas Vondra
tomas@vondra.me
In reply to: Ilia Evdokimov (#1)
Re: Apply extended statistics to join clause during parameterized path costing

On 8/17/26 13:17, Ilia Evdokimov wrote:

Hi hackers,

...
                                                           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].

Why couldn't it leverage ndistict and/or MCV list too? I was imagining
we'd use mostly the same logic as for regular univariate stats.

Any feedback are welcome.

I agree using existing per-table extended statistics for estimating
joins is a good idea, and something I suggested in the past. But doing
it this way also introduces an annoying inconsistency, because it
changes estimate for the scan, not for the join.

This is actually visible in your example, where you have

Nested Loop (cost=5.86..4474.19 rows=98 width=18)
-> Seq Scan on small t2 (cost=0.00..1.50 rows=50 width=8)
-> Bitmap Heap Scan on big t1 (cost=5.86..87.45 rows=200 ...

but 50 * 200 != 98.

I do think we'd need to make sure the join cardinality estimate also
considers the per-table statistics. Say, eqjoinsel() would need to look
not just for regular per-attribute ndistinct / MCV / histograms, but
also the extended stats.

It's not entirely trivial, though. It's likely that only one side of the
join has extended stats (e.g. fact table has MCV, but the dimension side
is uniform/unique, and so has just basic per-attribute stats). So we'd
need to consider extended-extended as well as extended-plain and
plain-plain cases.

regards

--
Tomas Vondra

#3Ilia Evdokimov
ilya.evdokimov@tantorlabs.com
In reply to: Tomas Vondra (#2)
Re: Apply extended statistics to join clause during parameterized path costing

Hi Tomas,

Thank you for the review

On 8/21/26 19:35, Tomas Vondra wrote:

Why couldn't it leverage ndistict and/or MCV list too? I was imagining
we'd use mostly the same logic as for regular univariate stats.

It could, but the amount of code required is not really comparable, and
I think that's worth being explicit about before we decide where to
spend effort.

MCV: mcv_get_match_bitmap() walks every MCV item and evaluate the clause
that requires a literal Const on one side. The same one in
examine_opclause_args(), which returns false if neither side is a Const.
In the parameterized-scan case the other side is not Const, so this
can't be reused as-is. Making MCV useful here means estimating, for a
row drawn from other relation's own distribution, how much of the
referencing relation's MCV mass would match. That's a bigger piece of
work, closer in shape to what eqjoinsel() would need for the join-level
fix below than to what this patch does.

ndistinct: maps onto this cleanly in principle: ndistinct(a,b) is the
count of distinct (a,b) pairs, so rel->tuples / ndistinct(a,b) gives the
average rows per pair directly 200000/1000 = 200 here, matching the
dependencies estimate exactly, no direction to pick. But it's not free
to wire in: there's no existing clause-list matcher for it the way
dependency_is_compatible_clause() exists for dependencies (would need
writing, including the two-relid extension), it'd need to slot into
statext_clauselist_selectivity()'s estimated clauses bookkeeping to
avoid double-applying alongside MCV/dependencies, and unlike
dependencies' degree, which blends smoothly between independence and
full determination, a flat tuples/ndistinct(a,b) assumes uniformity
across whichever pairs exist. On skewed join keys that's its own source
of bad estimates, and guarding against it would pull back in some of the
MCV complexity above.

Given all three have a different cost/shape, I'd rather not write any of
that code speculatively. I think it makes sense to first agree on which
of these we actually want (dependencies now, ndistinct and/or MCV as
separate, larger follow-ups) before either of us puts time into an
implementation that might need to be reshaped once we've settled the
approach.

I agree using existing per-table extended statistics for estimating
joins is a good idea, and something I suggested in the past. But doing
it this way also introduces an annoying inconsistency, because it
changes estimate for the scan, not for the join.

This is actually visible in your example, where you have

Nested Loop (cost=5.86..4474.19 rows=98 width=18)
-> Seq Scan on small t2 (cost=0.00..1.50 rows=50 width=8)
-> Bitmap Heap Scan on big t1 (cost=5.86..87.45 rows=200 ...

but 50 * 200 != 98.

I do think we'd need to make sure the join cardinality estimate also
considers the per-table statistics. Say, eqjoinsel() would need to look
not just for regular per-attribute ndistinct / MCV / histograms, but
also the extended stats.

It's not entirely trivial, though. It's likely that only one side of the
join has extended stats (e.g. fact table has MCV, but the dimension side
is uniform/unique, and so has just basic per-attribute stats). So we'd
need to consider extended-extended as well as extended-plain and
plain-plain cases.

I agree join-level estimation needs this too [0]/messages/by-id/BE2AB1CA-8187-4A68-8E00-0DFD55D39B7E@outlook.com, but I'd like to first
get the single-relation side as it reasonably can be, before taking on
calc_joinrel_size_estimate, which is shared by every join algorithm and
is materially bigger, separate change. It's also worth noting that while
estimated rows didn't change, the cost of the nested loop did (579.23 ->
4474.19): cost_bitmapheapscan()/cost_index() cost the parameterized path
off inner_path->rows, not joinrel->rows.

[0]: /messages/by-id/BE2AB1CA-8187-4A68-8E00-0DFD55D39B7E@outlook.com
/messages/by-id/BE2AB1CA-8187-4A68-8E00-0DFD55D39B7E@outlook.com

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