zhuqi-lucas opened a new pull request, #23888:
URL: https://github.com/apache/datafusion/pull/23888
## Which issue does this PR close?
- Part of #22198 (the **P0 — multi-column lexicographic reorder** item)
- Part of #23036 (Sort Pushdown epic)
## Rationale for this change
`PreparedAccessPlan::reorder_by_statistics` (row-group level) and
`ParquetSource::reorder_files` (file level) key only off the **leading** sort
column's `min` statistic. When the leading key ties across row groups or files
— the `ORDER BY low_cardinality_col, ts LIMIT k` shape — the reorder
degenerates to a no-op, the scan reads data in disk order, and the TopK dynamic
filter's threshold improves monotonically without ever proving a later row
group unwinnable. Result: zero runtime RG pruning and a full-file decode even
though per-column statistics contain everything needed to read the best row
group first.
The end-to-end test in this PR demonstrates the failure concretely on
current main: leading key tied across 5 row groups, secondary key clustered but
stored in adversarial DESC disk order → `row_groups_pruned_dynamic_filter=0`,
all 500 rows decoded. With this change the scan reads the best RG first and
prunes the other 4.
Note the *pruning* machinery itself already handles multi-column
lexicographic dynamic filters (the leading disjunct of `a < x OR (a = x AND b <
y)` prunes on `min(a)` stats — verified by the other new e2e test, which passes
on main unmodified). The gap was purely in the *reorder* layers feeding it.
## What changes are included in this PR?
Both reorder layers now sort lexicographically over the **longest
plain-`Column` prefix** of the sort order, using per-column `min` statistics:
- **RG level** (`access_plan.rs`): switch from `sort_to_indices` over the
leading column's mins to `lexsort_to_indices` over per-column min arrays. The
leading key stays normalized ASC (direction still applied by the downstream
`reverse()`, unchanged); secondary keys sort by their direction *relative to*
the leading key, with null placement pre-flipped when the reverse is coming so
the post-reverse order matches the request. The prefix walk stops at the first
non-`Column` / not-in-file-schema expression (leading-key-only graceful skips
unchanged).
- **File level** (`sort.rs`): `extract_topk_sort_info` extended from the
single leading column to the plain-`Column` prefix, comparator compares
tuple-wise with per-column direction; missing-stats files still sort last per
column.
Behavior for single-column sort orders is unchanged.
## Are these changes tested?
- 4 new unit tests for `reorder_by_statistics`: secondary tie-break,
relative secondary direction (`a ASC, b DESC`), DESC/DESC normalization through
`reverse()`, and prefix-stop on a non-`Column` secondary expression.
- 1 new unit test for file-level reorder: secondary tie-break with
missing-stats file placement.
- 2 new end-to-end tests in `dynamic_row_group_pruning.rs`:
- multi-column sort with clustered leading key → pruning fires via the
leading disjunct (passes before this PR; guards the existing behavior),
- multi-column sort with tied leading key + adversarial disk order →
pruning fires only with this PR's lexicographic reorder.
- Existing reorder unit tests, `dynamic_row_group_pruning` integration
tests, and `topk.slt` / `sort_pushdown.slt` / `dynamic_row_group_pruning.slt` /
`dynamic_filter_pushdown_config.slt` all pass.
- `topk_tpch` (sort-tpch `-l 100`) shows no regressions (all 11 queries
within noise; lineitem's secondary keys are not clustered when the leading key
ties, so no wins expected on that suite — the win case is the `ORDER BY
low_card, ts` shape shown in the e2e test).
## Are there any user-facing changes?
No API changes. Queries with multi-column `ORDER BY ... LIMIT` over parquet
whose leading sort key ties across row groups / files can now skip row groups
at runtime instead of decoding the whole file.
--
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]
