Skip to content

Commit 17694ac

Browse files
authored
feat(parquet): multi-column lexicographic stats reorder for TopK sort pushdown (apache#23888)
## Which issue does this PR close? - Part of apache#22198 (the **P0 — multi-column lexicographic reorder** item) - Part of apache#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.
1 parent f248f45 commit 17694ac

4 files changed

Lines changed: 556 additions & 99 deletions

File tree

‎datafusion/core/tests/parquet/dynamic_row_group_pruning.rs‎

Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -433,3 +433,155 @@ async fn dynamic_rg_pruning_coexists_with_row_filter() {
433433
output.description(),
434434
);
435435
}
436+
437+
/// Build five two-column `RecordBatch`es: `a` is physically clustered
438+
/// (batch `i` carries `a ∈ [i*100, (i+1)*100)`, disjoint per-RG stats)
439+
/// and `b` is a per-batch shuffle (identical `[0, 100)` range in every
440+
/// RG, useless for pruning).
441+
fn build_two_col_leading_clustered(schema: &Arc<Schema>) -> Vec<RecordBatch> {
442+
(0..5i64)
443+
.map(|rg| {
444+
let base = rg * 100;
445+
let a: Vec<i64> = (base..base + 100).collect();
446+
// pseudo-shuffled b, same value set in every RG
447+
let b: Vec<i64> = (0..100).map(|i| (i * 37) % 100).collect();
448+
RecordBatch::try_new(
449+
Arc::clone(schema),
450+
vec![
451+
Arc::new(Int64Array::from(a)) as ArrayRef,
452+
Arc::new(Int64Array::from(b)) as ArrayRef,
453+
],
454+
)
455+
.unwrap()
456+
})
457+
.collect()
458+
}
459+
460+
/// Build five two-column `RecordBatch`es where the *leading* sort key
461+
/// ties everywhere (`a = 1` in every row / RG) and the *secondary* key
462+
/// is clustered but stored in DESC disk order: batch 0 carries
463+
/// `b ∈ [400, 500)`, batch 4 carries `b ∈ [0, 100)`.
464+
///
465+
/// An `ORDER BY a, b LIMIT k` query wants the rows in batch 4 first;
466+
/// reading disk order decodes every RG with a monotonically *improving*
467+
/// threshold that never proves a later RG unwinnable.
468+
fn build_two_col_leading_tied_desc(schema: &Arc<Schema>) -> Vec<RecordBatch> {
469+
(0..5i64)
470+
.map(|rg| {
471+
let base = (4 - rg) * 100;
472+
let a: Vec<i64> = vec![1; 100];
473+
let b: Vec<i64> = (base..base + 100).collect();
474+
RecordBatch::try_new(
475+
Arc::clone(schema),
476+
vec![
477+
Arc::new(Int64Array::from(a)) as ArrayRef,
478+
Arc::new(Int64Array::from(b)) as ArrayRef,
479+
],
480+
)
481+
.unwrap()
482+
})
483+
.collect()
484+
}
485+
486+
fn two_col_schema() -> Arc<Schema> {
487+
Arc::new(Schema::new(vec![
488+
Field::new("a", DataType::Int64, false),
489+
Field::new("b", DataType::Int64, false),
490+
]))
491+
}
492+
493+
/// A multi-column `ORDER BY a, b LIMIT k` must still engage the runtime
494+
/// RG pruner through the *leading* disjunct of the lexicographic dynamic
495+
/// filter (`a < x OR (a = x AND b < y)`): once the heap fills from the
496+
/// first (best) row group, `min(a) > x` alone proves later RGs
497+
/// unwinnable regardless of `b`.
498+
#[tokio::test]
499+
async fn dynamic_rg_pruning_fires_for_multi_column_sort_leading_clustered() {
500+
let schema = two_col_schema();
501+
let batches = build_two_col_leading_clustered(&schema);
502+
503+
let mut ctx = ContextWithParquet::with_custom_data(
504+
Scenario::Int,
505+
RowGroup(100),
506+
Arc::clone(&schema),
507+
batches,
508+
)
509+
.await;
510+
511+
let output = ctx
512+
.query("SELECT a, b FROM t ORDER BY a ASC, b ASC LIMIT 5")
513+
.await;
514+
515+
assert_eq!(output.result_rows, 5, "query must return LIMIT rows");
516+
517+
let pruned = output
518+
.row_groups_pruned_dynamic_filter()
519+
.expect("`row_groups_pruned_dynamic_filter` metric must be registered");
520+
assert!(
521+
pruned >= 1,
522+
"multi-column TopK must prune via the leading column's disjunct; \
523+
pruned={pruned}\n{}",
524+
output.description(),
525+
);
526+
}
527+
528+
/// When the leading sort key ties across all row groups, pruning (and
529+
/// reading the right RG first) must fall to the *secondary* key: RG
530+
/// stats give `min(a) = max(a) = 1` everywhere, so the lex dynamic
531+
/// filter reduces to `a = 1 AND b < y` — prunable via `min(b)`.
532+
///
533+
/// The disk order is adversarial (secondary key DESC), so without
534+
/// multi-column stats reorder the scan reads the worst RG first and the
535+
/// threshold never proves later RGs unwinnable. With multi-column
536+
/// reorder the best RG is read first and every other RG is pruned.
537+
#[tokio::test]
538+
async fn dynamic_rg_pruning_fires_for_multi_column_sort_leading_tied() {
539+
let schema = two_col_schema();
540+
let batches = build_two_col_leading_tied_desc(&schema);
541+
542+
let mut ctx = ContextWithParquet::with_custom_data(
543+
Scenario::Int,
544+
RowGroup(100),
545+
Arc::clone(&schema),
546+
batches,
547+
)
548+
.await;
549+
550+
let output = ctx
551+
.query("SELECT a, b FROM t ORDER BY a ASC, b ASC LIMIT 5")
552+
.await;
553+
554+
assert_eq!(output.result_rows, 5, "query must return LIMIT rows");
555+
// The leading key `a = 1` is tied everywhere, so correctness rests
556+
// entirely on the secondary key: the five smallest `b` values must come
557+
// back, in ascending secondary order. Assert the exact result rows
558+
// (full two-column text, in order) rather than just probing for each
559+
// `b` — a bare `| {b} ` match would be satisfied by the leading `a = 1`
560+
// column even if that `b` were missing or misordered.
561+
let formatted = output.pretty_results();
562+
let data_rows: Vec<&str> = formatted
563+
.lines()
564+
.filter(|line| line.starts_with("| 1 |"))
565+
.collect();
566+
assert_eq!(
567+
data_rows,
568+
vec![
569+
"| 1 | 0 |",
570+
"| 1 | 1 |",
571+
"| 1 | 2 |",
572+
"| 1 | 3 |",
573+
"| 1 | 4 |",
574+
],
575+
"output must be exactly (a=1, b=0..=4) in ascending secondary order; got:\n{formatted}",
576+
);
577+
578+
let pruned = output
579+
.row_groups_pruned_dynamic_filter()
580+
.expect("`row_groups_pruned_dynamic_filter` metric must be registered");
581+
assert!(
582+
pruned >= 1,
583+
"with the leading key tied everywhere, the secondary key must \
584+
drive RG reorder + pruning; pruned={pruned}\n{}",
585+
output.description(),
586+
);
587+
}

0 commit comments

Comments
 (0)