Use exact column statistics to prove ordering through integer arithmetic
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
DataFusion can retain an unnecessary sort for integer arithmetic even when exact column extrema prove overflow is impossible.
The following SQL creates a sorted Parquet file with exact bounds `a ∈ [1, 3]` and registers its ordering:
```sql
SET datafusion.execution.target_partitions = 1;
SET datafusion.execution.collect_statistics = true;
COPY (
SELECT * FROM (VALUES (1), (2), (3)) AS src(a) ORDER BY a
)
TO '/tmp/statistics_ordering_example.parquet'
STORED AS PARQUET;
CREATE EXTERNAL TABLE t
STORED AS PARQUET
WITH ORDER (a ASC)
LOCATION '/tmp/statistics_ordering_example.parquet';
SELECT a + 1 AS x FROM t ORDER BY x;
EXPLAIN SELECT a + 1 AS x FROM t ORDER BY x;
```
The query returns `2, 3, 4`. Before this enhancement, the physical plan retains `SortExec` even though the input is ordered and the exact bounds prove that `a + 1` cannot overflow.
Expected: return the same ordered results without `SortExec`. The explicit ordering and exact bounds together justify removing the sort.
### Describe the solution you'd like
Use existing execution-plan statistics to supply exact integer bounds during projection ordering inference. Remove the sort when addition or subtraction is proven safe. Retain it when ordering cannot be proven.
Statistics establish value bounds; the input must independently have a known ordering.
### Describe alternatives you've considered
Keep the existing sort, or introduce a separate bounds-propagation interface. Reusing existing statistics avoids another execution-plan interface.
### Additional context
_No response_
Contributor guide
Assessment
This issue has not been assessed yet.