apache / apache/datafusion

Use exact column statistics to prove ordering through integer arithmetic

Open
#25,220 1 comment 0 reactions 1 assignee Claimed by @haohuaijin View on GitHub
enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.