zhuqi-lucas opened a new pull request, #21580:
URL: https://github.com/apache/datafusion/pull/21580
## Which issue does this PR close?
Closes #21317
## Rationale for this change
When sort pushdown is active for Inexact paths (e.g., reverse scan or
statistics-based reordering that can't be elevated to Exact), row groups within
a file are currently read in their original order. This means TopK queries may
read suboptimal row groups first, delaying threshold tightening.
By reordering row groups by their min/max statistics to match the requested
sort order, TopK finds optimal values first. This gives two levels of benefit:
1. **Row-level filtering (immediate):** TopK sets a tight dynamic filter
threshold after reading the first (best) row group. For subsequent row groups,
the dynamic filter acts as a row-level filter — the parquet reader uses page
index to skip non-matching pages and avoids decoding non-sort columns for
filtered rows. Significant I/O reduction for wide tables.
2. **Row-group-level skipping (follow-up with morsel API):** Once
morsel-driven scanning lands, the dynamic filter can be re-evaluated between
row groups, skipping entire row groups when their min statistics exceed the
TopK threshold.
## What changes are included in this PR?
- Add `reorder_by_statistics` to `PreparedAccessPlan` that sorts
`row_group_indexes` by the first sort column's min values (ASC or DESC based on
sort options)
- Add `sort_order_for_reorder: Option<LexOrdering>` field to
`ParquetMorselizer` and `ParquetSource`
- Pass sort order from `ParquetSource::try_pushdown_sort` (Inexact path)
through to the opener
- Reorder is applied after pruning but before reverse — the two
optimizations compose
- Graceful fallback (returns plan unchanged) when:
- `row_selection` is present (remapping is complex)
- 0 or 1 row groups (nothing to reorder)
- Sort expression is not a simple column reference
- Statistics converter cannot be built (column missing, type mismatch,
etc.)
- Min values cannot be extracted from statistics
## Are these changes tested?
Yes. Added 8 unit tests in `access_plan.rs` covering:
- ASC reorder with unordered row groups
- DESC reorder
- Single row group (no reorder needed)
- Reorder with some row groups skipped (pruning applied first)
- Skip with `row_selection` present
- Already-sorted row groups preserved
- Skip when sort expr is not a simple column (e.g., `col + 1`)
- Skip when column is missing from schema
All existing tests continue to pass.
## Are there any user-facing changes?
No API changes. Users benefit from improved TopK performance on queries like
`SELECT * FROM t ORDER BY col LIMIT N` when:
- Files have multiple row groups
- Row groups are not in sort order (e.g., append-heavy workloads)
- Statistics are available on the sort column
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
