Repository navigation
feat: use exact integer statistics for ordering inference - #26776
haohuaijin wants to merge 8 commits into
Conversation
github-actions
Bot
added
physical-expr
haohuaijin
changed the title
Resolve equivalence property conflicts by preserving both trusted integer bounds and grouping propagation.
kosiew
left a comment
kosiew
left a comment
There was a problem hiding this comment.
Thanks for addressing redundant sorts in ordered integer expressions. Using exact bounds to prove that arithmetic preserves ordering is appropriate. The regression tests cover safe arithmetic, overflow, and several plan transformations. I found no confirmed correctness defect.
The design keeps interval reasoning in EquivalenceProperties rather than adding special cases to sort elimination. This is the right boundary. Bounds remain separate from ordering guarantees, and their propagation through filters, projections, and unions is conservative.
The shared range cache limits repeated interval construction, but it does not eliminate repeated expression-property inference. Please provide before/after planning and execution benchmarks for improved and unchanged workloads. The two test suggestions are non-blocking.
| let dependencies = Dependencies::default(); | ||
| for (source, targets) in mapping.iter() { | ||
| let Ok(properties) = | ||
| get_expr_properties(source, &dependencies, &self.schema, column_ranges) |
There was a problem hiding this comment.
When trusted bounds exist, projected_column_ranges analyzes every projection source, even when no sort is removed. The cache reuses column intervals but not expression-property results. Please benchmark using safe arithmetic, overflow, and unchanged projections. Report planning and execution times separately, with reproducible commands and settings. Include a bounded-integer projection workload because the existing project/wide_struct_fields benchmarks do not exercise this path. This requests performance evidence, not a redesign.
| if data_type.is_integer() | ||
| && let (Precision::Exact(min), Precision::Exact(max)) = | ||
| (&statistics.min_value, &statistics.max_value) | ||
| && !min.is_null() |
There was a problem hiding this comment.
Consider adding table-driven tests through with_column_statistics for inexact, missing, null, reversed, and type-mismatched extrema. Verify that rejected bounds cannot prove ordering for a + 1, while exact bounds [1, 3] can. Nullable columns should remain eligible when their extrema are valid.
|
|
||
| # The same range information is available to grouping-expression analysis. | ||
| query TT | ||
| EXPLAIN SELECT a + 1 AS x, count(*) FROM arithmetic_bounds GROUP BY x ORDER BY x; |
There was a problem hiding this comment.
Consider adding a result check for the new grouped aggregation case. Expect (2, 1), (3, 1), (4, 1), and (NULL, 1) to verify correctness with group_clustering_mode=Full, beyond the existing plan assertion.
Which issue does this PR close?
Rationale for this change
An ordered integer column with exact extrema can still require a redundant sort for expressions such as
a + 1, because ordering analysis starts with an unbounded interval. Whenais ascending and its exact bounds are[1, 3], those bounds prove that adding one cannot overflow and preserves the input ordering.What changes are included in this PR?
EquivalenceProperties.What is the testing strategy for this PR?
Extend the existing
parquet_sorted_statistics.sltwith plan and result checks for safe arithmetic, signed overflow and unsigned underflow, consecutive and reordered projections, grouping, windows, filters and dynamic filters, and unions with bounded or unknown branches. The tests use the SLT runner's four target partitions and default sort pushdown.Strengthen the existing filtered Parquet scan round-trip test with exact integer extrema. The existing TPC-H round-trip test also verifies plans with multiple bounded columns.
Validation passed:
cargo fmt --allcargo clippy --all-targets --all-features -- -D warningsparquet_sorted_statistics.sltfileAre there any user-facing changes?
Ordered integer arithmetic can avoid redundant
SortExecoperators when exact bounds prove it safe. Bounds do not establish ordering on their own.The additive
EquivalenceProperties::with_column_statisticsAPI accepts exact integer extrema. Range propagation adds planning metadata work; it does not calculate bounds per row.