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], 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]:
https://www.postgresql.org/message-id/BE2AB1CA-8187-4A68-8E00-0DFD55D39B7E%40outlook.com

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