Epic: Statistics improvements

[alamb]

Is your feature request related to a problem or challenge?

We would like to use "statistics" in our project for transformations that rely on the statisics being "correct" (e.g. that the there are no values outside the min and max range).

DataFusion has several optimizations like this too that rely on statistics being correct such as skipping file scans with limits such as in https://github.com/apache/arrow-datafusion/blob/e54894c39202815b14d9e7eae58f64d3a269c165/datafusion/core/src/datasource/statistics.rs#L34-L33. There are also suggestions of additional such optimizations like #6672

However the current Statistics code seems to make it hard to manage the 'are the statistics exact and can they be guaranteed for transformations' (@crepererum noted this quite some time ago on #5613). This has recently lead to several bugs such as

• Fix incorrect results in COUNT(*) queries with LIMIT #8049
• Bug-fix in Filter and Limit statistics #8094

We would like to make it clearer what is known and what is an estimate is know (e.g. the min/max of row counts may be known, but the actual value may be an estimate after a filter). This is described in more detail on #8078

As we began exploring this concept we ran into several issues with Statistics and I think it is getting big enough to warrant its own tracking epic

Related items

• Show statistics min and max in explain #8110
• Show Statistics in explain Verbose without enabling show statistics #8111
• ParquetExec::statistics() does not read statistics for many column types (like timstamps, strings, etc) #8295
• Consolidate statistics aggregation #8229
• Improve statistics test coverage #8228
• Introduce a way to represent constrained statistics / bounds on values in Statistics #8078
• Statistics::total_byte_size does not account for projection in FileScanConfig::with_projection #14936
• Make default filter selectivity estimate configurable #8133
• Queries that lost statistics or their statistics become inexact #8099
• Use file statistics in query planning to avoid sorting when unecessary #7490
• ParquetExec::statistics::is_exact likely wrong/misunderstood #5614
• Statistics::is_exact semantics #5613
• Possible bug in Parquet pruning code? #8309
• Bug: fix case where num_rows and total_byte_size are not defined (stat should be None instead of Some(0)) #2976
• Support parquet statistics for struct columns #8334
• Parquet pruning will be incorrect if field names are repeated #8335
• Parquet Predicate Pushdown Does Not Handle Type Coercion #7925
• Parquet Statistics Pruning Ignores ColumnOrder, resulting in potentially incorrect statistics #8342

Pruning Improvements (maybe should be its own epic)

• Don't error on unknown column when pruning if predicate can still be proven false #7869
• Support general pruning based on <col> = 'const' in PruningPredicate #8376

Describe the solution you'd like

No response

Describe alternatives you've considered

No response

Additional context

This is somewhat related

[suremarc]

Recently I began looking into implementing #10316, and the proposed approach was to add per-partition statistics to ExecutionPlan and use the information to determine when the partitions have non-overlapping sort keys. However, I realized this requires #8078 to be implemented, as determining whether or not ranges overlap requires upper and lower bounds.

According to @alamb's comment on #8078, the (then) current state of the Statistics code means than implementing #8078 is intractable as of now until other issues with the statistics code are resolved (it seems there were some attempts to simplify the statistics code that ended up not getting completed).

I see that work on this epic has stalled since February, is there interest in continuing it? If so, I'm a willing contributor, but it'd help to know what needs to be done first, in particular if the Statistics code is still in need of some simplification.

[findepi]

If we have per-partition statistics, merging them will be problematic for NDV. Extrapolation techniques are not likely to work.

[suremarc]

If we have per-partition statistics, merging them will be problematic for NDV. Extrapolation techniques are not likely to work.

Ok, well I suppose we can keep the existing global statistics and add a new per-partition statistics method (that defaults to returning the global statistics for each partition). That would probably be a less invasive change too.

Would be happy to discuss the details more over on #10316

[alamb]

According to @alamb's comment on #8078, the (then) current state of the Statistics code means than implementing #8078 is intractable as of now until other issues with the statistics code are resolved (it seems there were some attempts to simplify the statistics code that ended up not getting completed).

Well, that may have also been my attempt / excuse :) -- especially if I didn't have enough time to work on it

I see that work on this epic has stalled since February, is there interest in continuing it? If so, I'm a willing contributor, but it'd help to know what needs to be done first, in particular if the Statistics code is still in need of some simplification.

I personally think we should go about this from the other end: try to implement the analysis for #10316 -- and use that as a vehicle to make any additional Statistics improvements needed. I think it would help to motivate statistics improvements if we had a real usecase.

Thank you @suremarc and @findepi

[alamb]

Here is one idea on how to improve Statistics / Precision. Let me know what you think:

• RFC: Add Precision:AtLeast and Precision::AtMost for more Statistics… precision #13293

[alamb]

The process has started in

• StatisticsV2: initial statistics framework redesign #14699

[clflushopt]

Thanks for this issue @alamb I was actually looking for an EPIC that covers the work planned for statistics; since there's already work done as a followup for #14699 in #14896 I am wondering what else is left that I can take on with regards to this ? There's still the work necessary to finish #3929 i.e #4158 abd #4159 both seem to be relatively related and can benefit from the the redesign in #14699.

[alamb]

@clflushopt I don't really know as I am not driving the statistics rework myself and thus don't have much visibility into what is planned

The only remaining thing I know of that comes to mind is

• Consolidate statistics aggregation #8229

but that is more of an API exercise rather than algorithms.

Another thing that comes to mind is to look at / extend the existing https://github.com/apache/datafusion/blob/main/datafusion/physical-expr/src/intervals/cp_solver.rs code / show how it is useful

I was playing around with duckdb this morning. Somehow it uses its constrait solver to simplify away redundant filters. For example, it correctly deduces x > 1 AND x > 2 AND x > 3 AND x < 6 AND x < 7 AND x < 8 is the same as x>3 AND x<6

create table foo(x int);
D insert into foo values (1);
D insert into foo values (5);

D explain SELECT * from foo where x > 1 AND x > 2 AND x > 3 AND x < 6 AND x < 7 AND x < 8;

┌─────────────────────────────┐
│┌───────────────────────────┐│
││       Physical Plan       ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│         SEQ_SCAN          │
│    ────────────────────   │
│         Table: foo        │
│   Type: Sequential Scan   │
│       Projections: x      │
│    Filters: x>3 AND x<6   │
│                           │
│          ~1 Rows          │
└───────────────────────────┘