Follow-ups for stats-based RG / file reorder (#21956): multi-column, function-wrapped, compound exprs
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
Follow-up enhancements to the row-group / file stats-based reorder landed in #21956. Listed here so they can be picked up independently.
Today `PreparedAccessPlan::reorder_by_statistics` and `ParquetSource::reorder_files` both:
- only look at `sort_order.first()` — secondary sort keys are ignored
- only fire when the leading expression is a plain `Column` — function-wrapped sorts (`date_trunc('day', ts) DESC`, `CAST(x AS Date) DESC`, `ceil(value) DESC`, …) skip the stats-based reorder
Four follow-ups, by priority:
---
### P0 — Multi-column lexicographic reorder by per-column min
For `ORDER BY a ASC, b DESC LIMIT N` where both `a` and `b` are plain columns in the file schema, lex-sort row groups (and files) by `(min(a) ASC, min(b) DESC)` instead of just `min(a) ASC`. Parquet stores per-column stats, so the data is already there — switch from `arrow::compute::sort_to_indices` over a single `stat_mins` to `lexsort_to_indices` over per-column min arrays, with per-column `SortOptions`.
Most useful when the leading sort column has low cardinality (e.g. `ORDER BY country, ts DESC LIMIT 100` — RGs that tie on `country.min` should be broken by `ts.min`).
Estimated cost: ~30-50 lines + a few unit tests.
### P1 — Function-wrapped reorder via leaf-column extraction
For sort expressions like `date_trunc('day', ts) DESC` or `CAST(x AS Date) DESC` — single leaf `Column` wrapped in a monotonic function chain. Parquet has no stats keyed by the function expression, but `min(f(col)) = f(min(col))` when `f` is monotonic, so `min(col)`'s order is a valid proxy.
Approach:
1. Walk the sort expression's `PhysicalExpr::children()` to find the unique leaf `Column`.
2. Verify monotonicity through the wrapper chain — `EquivalenceProperties` already does this in `ordering_satisfy`; the same machinery should be reusable here.
3. Drive `reorder_by_statistics` off the leaf column's stats.
DataFusion's existing `evaluate_bounds` / monotonicity inference is the right tool — happy to discuss the cleanest hook point.
### P1 — Detect "already-sorted" sources to skip redundant reorder
When the source's declared `output_ordering` already matches the request **modulo NULL placement** (and the column is either non-nullable or known null-free), `try_pushdown_sort` currently returns `Inexact` instead of `Exact` because `EquivalenceProperties::ordering_satisfy` is strict about `nulls_first` / `nulls_last`.
Concrete example surfaced while diagnosing CI snapshot drift on `topk.slt`'s `partial_sorted` case in #21956:
- Source declares `output_ordering=[number DESC]` — DataFusion's default makes that `number DESC NULLS FIRST`.
- Query asks for `ORDER BY number DESC NULLS LAST LIMIT 3`.
- `ordering_satisfy` returns `false` on the NULL position mismatch, so the Phase 3 column-in-schema branch fires, setting `sort_order_for_reorder=[number DESC NULLS LAST]` and `reverse_row_groups=true`.
- At runtime the opener sorts row groups ASC-by-min, then reverses iteration — two operations that very nearly cancel out, returning the row groups to (approximately) their on-disk DESC order. Correct, but wasteful, and the surrounding `SortExec` is kept even though the data is already in the requested order on disk.
A softer "Exact-equivalent" check would help: when the source ordering matches the request on `(expr, descending)` and either the column is non-nullable or null-count statistics confirm no NULLs in the sort column, `try_pushdown_sort` could short-circuit to `Exact` so the optimizer drops the `SortExec` outright.
### P2 — Compound-expression reorder via interval propagation (probably defer)
For sorts on expressions involving more than one column (`a + b DESC`, `a * 2 - b DESC`, …) parquet stats give per-column intervals; combining them needs operator-specific interval arithmetic (`[min(a)+min(b), max(a)+max(b)]` for `+`, sign-aware for `*`, etc.). DataFusion has the building blocks (`evaluate_bounds`), but real-world workloads rarely sort by compound expressions and the integration cost is non-trivial. Listed for completeness; probably not worth doing unless a concrete benchmark motivates it.
---
cc @adriangb @alamb — wanted to keep the parent PR focused on the core mechanism + the review feedback you raised; these were good directions that came out of the design discussion but seemed better as separate issues.
Contributor guide
Assessment
This issue has not been assessed yet.