You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 102da39
Browse filesBrowse the repository at this point in the historyBrowse files
feat: globally reorder files and row groups by statistics for TopK queries (#21956)
## Which issue does this PR close?
- Closes#21317
- Partial Closes#21733
- Partial fix for #21399
- Split from #21580
## Rationale
TopK queries (`ORDER BY col LIMIT K`) on parquet with multiple
out-of-order row groups converge slowly: the dynamic-filter threshold
tightens only after the "best" row groups happen to be read. Reordering
row groups so the most-promising ones come first lets the threshold
tighten fast and prune the rest.
## What changes
- **`PreparedAccessPlan::reorder_by_statistics`** — sorts row groups by
`min(col)` ASC using parquet column statistics; composes with
`reverse()` for DESC requests. Graceful no-op when stats are unavailable
or the column isn't in the file schema.
- **`ParquetSource::try_pushdown_sort`** — sets `sort_order_for_reorder`
+ `reverse_row_groups` whenever pushdown fires. Pushdown fires when the
leading sort column is in the file schema, or when the source's reversed
equivalence ordering satisfies the request (covers function-wrapped
sorts via `EquivalenceProperties`'s monotonicity machinery).
- **`FileSource::reorder_files`** — file-level reorder in the shared
work queue, keyed off the file's `min` (ASC by `min` for ASC requests,
DESC by `min` for DESC requests) so it matches `reorder_by_statistics`
at the row-group level. The two orderings nest: file `i`'s `min` is a
lower bound on every row group inside it, so the file queue's order is a
natural prefix of the within-file row-group order.
EXPLAIN surfaces both `sort_order_for_reorder=[...]` and
`reverse_row_groups=true` so the optimization is visible in plans and
snapshot tests.
## Where the optimization applies
```sql
SELECT ... FROM <parquet_table> ORDER BY <col> [ASC|DESC] [LIMIT N]
```
The leading sort key must be a column that exists in the parquet file
schema, with no `AggregateExec` between the `SortExec` and the parquet
scan. Time-series, log-tailing, ranking lookups, and the `sort_pushdown`
benchmark in this repo (`benchmarks/queries/sort_pushdown/q1-q8.sql`)
all fit.
ClickBench's TopK queries (`ORDER BY COUNT(*) DESC LIMIT N` etc.) are
**not** in this category — the leading sort key is an aggregation
result, so the column-in-schema check fails and the pushdown does not
fire. Pushing sort metadata through `AggregateExec` is a separate
problem (the aggregated column doesn't exist before aggregation, so even
if the metadata reached the scan there'd be nothing actionable to do
with it).
## Tested
- 116 parquet lib unit tests pass (incl. `reorder_files`
ASC/DESC/missing-stats/no-op coverage)
- 32 `physical_optimizer::pushdown_sort` integration tests pass
- SLT suites: `sort_pushdown`, `topk`, `dynamic_filter_pushdown_config`,
`push_down_filter_parquet`, `window_topk_pushdown`
- `cargo clippy --all-targets --all-features -- -D warnings` clean
## User-facing changes
None — pure performance optimization. Query results unchanged.
0 commit comments