Pluggable expression-level statistics estimation (ExpressionAnalyzer)

[asolimando]

Is your feature request related to a problem or challenge?

DataFusion currently loses expression-level statistics when computing plan metadata:

• Projections: any expression that isn't a bare column or literal gets NDV = Absent, even for simple cases like col + 1 where NDV is trivially derivable from the input
• Filters: when interval analysis cannot handle a predicate (check_support returns false), selectivity falls back to a hardcoded 20% regardless of available column statistics
• Custom UDFs: there is no way for users to provide statistics metadata for their functions, making all UDFs opaque to the optimizer

Without expression-level statistics, the optimizer lacks the information it needs for join ordering, cardinality estimation, and cost-based decisions involving computed columns or UDFs. Projects embedding DataFusion currently have no extension point to provide this information for their own functions.

Related: this was previously raised in #992 (closed as non-actionable at the time).

Describe the solution you'd like

A pluggable chain-of-responsibility framework for expression-level statistics, covering:

1. Selectivity (predicate filtering fraction)
2. NDV (number of distinct values)
3. Min/max bounds
4. Null fraction

The framework should:

• Ship with a default Selinger-style analyzer handling columns, literals, binary expressions (AND/OR/NOT/comparisons), and arithmetic
• Include built-in analyzers for common function families (string, math, date_part/date_trunc)
• Allow users to register custom analyzers via SessionState for UDF-specific or domain-specific estimation (e.g., histogram-based, geometry-aware)
• Integrate into physical operators that need expression-level statistics (projections, filters, joins, aggregates, etc.)
• Be non-breaking and purely additive

Describe alternatives you've considered

• Extending PhysicalExpr::evaluate_statistics() (StatisticsV2: initial statistics framework redesign #14699): this provides per-expression statistics but doesn't support chain delegation or user-registered overrides, and would require changes to the PhysicalExpr trait
• Hardcoding heuristics in each operator (the status quo): does not scale as more expressions and operators need statistics, and provides no extension point for users
• Distribution-based API (Statistics: Migrate to Distribution from Precision #14896, StatisticsV2: initial statistics framework redesign #14699): more powerful but significantly more complex to implement and adopt; ExpressionAnalyzer can serve as the foundation, with distribution-based estimation plugged in as a custom analyzer

Planned work

Framework

• ExpressionAnalyzer trait, chain-of-responsibility registry, SessionState integration
• Default analyzer with Selinger-style heuristics (columns, literals, binary expressions, NOT)

Built-in analyzers for common functions

• String functions (UPPER, LOWER, TRIM, SUBSTRING, REPLACE, ...)
• Math functions (FLOOR, CEIL, ROUND, ABS, EXP, LN, ...)
• Date/time functions (date_part, date_trunc)

Operator integration

• Projection: propagate statistics through projected expressions
• Filter: use analyzer selectivity when interval analysis is not applicable
• Joins: expression-aware cardinality estimation for join key expressions
• Aggregates: NDV-based output row estimation for GROUP BY expressions

Additional context

• Related: Expressions should also evaluate on statistics #992 (similar request, closed as non-actionable), Epic: Statistics improvements #8227 (statistics improvements epic), StatisticsV2: initial statistics framework redesign #14699 (expression statistics API), Statistics: Migrate to Distribution from Precision #14896 (expression statistics tracking)

[asolimando]

take

[2010YOUY01]

This work looks really exciting, thank you for making it happen!

One future challenge I see is that the planned work follows a bottom-up approach: we first build the infrastructure, then evolve the optimizer. The issue is that some low-level design decisions (e.g., using algorithm X to estimate NDV for expression Y) can be difficult to reason about, unless the reviewer is a CBO expert.

Perhaps we could also provide a top-down write-up, starting from the end goal (making certain workloads faster) and working step by step down to the local algorithm choices. A TLDR with references would likely help.

[asolimando]

This work looks really exciting, thank you for making it happen!

One future challenge I see is that the planned work follows a bottom-up approach: we first build the infrastructure, then evolve the optimizer. The issue is that some low-level design decisions (e.g., using algorithm X to estimate NDV for expression Y) can be difficult to reason about, unless the reviewer is a CBO expert.

Perhaps we could also provide a top-down write-up, starting from the end goal (making certain workloads faster) and working step by step down to the local algorithm choices. A TLDR with references would likely help.

Thanks for your reply @2010YOUY01, I agree that this proposal could use a document to explain the end goal and sketch how this improvement would lead us there, I will try to work on that in parallel.

In general, for work around statistics today it's a bit the chicken-egg problem: we don't leverage statistics fully in planning as propagation is incomplete, and we can't prove with existing benchmarks that changes help as their output is not consumed for planning in most cases. And that's where #20292 could help while we improve the current situation.

This proposal is, however, a little different from the other efforts tracked by existing epics like #8227 and #20766, it aims at introducing tooling to enable override mechanism for downstream projects (with just a reasonable default). This links to @paleolimbot's interest (stats propagation for a specific type of stats) and your work on #19609: since people use statistics in a very different way, we need to provide an override mechanisms.

To make things a little more concrete, I could take a few examples from our existing benchmarks (probably TPC-DS), and showcase how planning could be improved with better statistics and propagation, like a motivating example.

WDYT?

[paleolimbot]

This links to paleolimbot's interest in stats propagation for a specific type of stats

I am new to this part of DataFusion but I took a look at the draft PR...we probably would be able to use this (but would need Statistics to be able to represent something pluggable, and would need the analyzer trait to be able to calculate something fancier than min/max and NDV). No pressure to cater to that here, but my personal motivating example is to ask for GeoStatistics (we have our own definition) for a specific column output of a dyn ExecutionPlan when planning a join.

[2010YOUY01]

This proposal is, however, a little different from the other efforts tracked by existing epics like #8227 and #20766, it aims at introducing tooling to enable override mechanism for downstream projects (with just a reasonable default). This links to @paleolimbot's interest (stats propagation for a specific type of stats) and your work on #19609: since people use statistics in a very different way, we need to provide an override mechanisms.

To make things a little more concrete, I could take a few examples from our existing benchmarks (probably TPC-DS), and showcase how planning could be improved with better statistics and propagation, like a motivating example.

WDYT?

This makes sense, I think now at the API framework stage, the goal is clear. I was thinking a little bit ahead, when adding expression/operator coverage for advanced statistics like NDV, it should better be workload guided at that time.

Also it looks like the API for #21122 and #19609 can be unified, I’ll try to help with the review.

[asolimando]

This links to paleolimbot's interest in stats propagation for a specific type of stats

I am new to this part of DataFusion but I took a look at the draft PR...we probably would be able to use this (but would need Statistics to be able to represent something pluggable, and would need the analyzer trait to be able to calculate something fancier than min/max and NDV). No pressure to cater to that here, but my personal motivating example is to ask for GeoStatistics (we have our own definition) for a specific column output of a dyn ExecutionPlan when planning a join.

Thanks for your feedback @paleolimbot. This issue covers the expression level only, as I tried to keep the scope to the minimum to not overload reviewers.

But I am also working on a POC for a similar chain-of-responsibility registry for the operator level, to be able to override the statistics propagation mechanism for individual operators beyond what's implemented in partition_statistics today. The idea is to buy the same freedom we have today for connectors/data source, and physical rules, but for statistics.

Being able to override operators' behavior for statistics propagation, would also allow supporting custom statistics, which matches exactly your use-case (provided a mechanism for storing them too, of course).

Concretely speaking, I had in mind DataSketches as custom stats, similar to what I implemented in HIVE-26221 to add support for histogram-like statistics for range filters based on KLL sketches, but it can very well be used for any kind of "custom" stats.

I will hopefully have a draft PR/POC for when I will open this new issue, but I'd like to keep the two discussions separate for now to not broaden the scope too much, as you have mentioned.

[asolimando]

This makes sense, I think now at the API framework stage, the goal is clear. I was thinking a little bit ahead, when adding expression/operator coverage for advanced statistics like NDV, it should better be workload guided at that time.

Makes sense, I thought you were referring to individual tasks composing this issue.

FWIW #20292 is a good starting point for evaluating improvements to statistics propagation, it's a bit coarse as reviewers have pointed out, but it can be refined over time and gives us a first measure.

At the moment stats aren't "consumed" in many places, therefore I understand that it's hard for reviewers to evaluate changes. What I have tried to do so far, is to push to look into systems with good CBO (Spark, Postgres, Trino, Hive, etc.) and make explicit references to them (e.g., #20904 (comment)), for any non-trivial change.

Also it looks like the API for #21122 and #19609 can be unified, I’ll try to help with the review.

Thanks, help with the review would be greatly appreciated, on my hand I will take another closer look at #19609.

#21122 is probably already reviewable, but I wanted to take another close look before removing the "Draft" label, but I don't expect any major change, in case you want to take a look already.

[Whatsonyourmind]

A few notes on the Selinger-style default analyzer for the planned work:

For selectivity estimation of comparison predicates (col > const), the classic approach when histograms are unavailable is the uniform distribution assumption with min/max bounds:

selectivity(col > c) = (max - c) / (max - min)    when min ≤ c ≤ max
selectivity(col > c) = 0                           when c > max
selectivity(col > c) = 1                           when c < min

For compound predicates, the independence assumption gives:

• AND: multiply selectivities
• OR: 1 - (1 - s1)(1 - s2)
• NOT: 1 - s

For NDV propagation through expressions: arithmetic operations like col + 1 preserve NDV exactly. For col1 + col2, the upper bound on NDV is min(NDV1 * NDV2, row_count). For functions like FLOOR(col), NDV can only decrease: NDV_out ≤ NDV_in. For date_trunc('month', ts_col), NDV can be estimated as (max - min) / interval_size.

One design consideration: the chain-of-responsibility pattern should propagate confidence levels alongside estimates. A histogram-based analyzer might return (selectivity=0.23, confidence=High), while a fallback heuristic returns (selectivity=0.20, confidence=Low). The optimizer can then weight its cost model decisions by confidence -- preferring plans that are robust to estimation error when confidence is low.