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.