Repository navigation
Commit 17694ac
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
- datasource-parquet/src
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
433 | 433 | | |
434 | 434 | | |
435 | 435 | | |
| 436 | + | |
| 437 | + | |
| 438 | + | |
| 439 | + | |
| 440 | + | |
| 441 | + | |
| 442 | + | |
| 443 | + | |
| 444 | + | |
| 445 | + | |
| 446 | + | |
| 447 | + | |
| 448 | + | |
| 449 | + | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
| 461 | + | |
| 462 | + | |
| 463 | + | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
| 470 | + | |
| 471 | + | |
| 472 | + | |
| 473 | + | |
| 474 | + | |
| 475 | + | |
| 476 | + | |
| 477 | + | |
| 478 | + | |
| 479 | + | |
| 480 | + | |
| 481 | + | |
| 482 | + | |
| 483 | + | |
| 484 | + | |
| 485 | + | |
| 486 | + | |
| 487 | + | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
| 505 | + | |
| 506 | + | |
| 507 | + | |
| 508 | + | |
| 509 | + | |
| 510 | + | |
| 511 | + | |
| 512 | + | |
| 513 | + | |
| 514 | + | |
| 515 | + | |
| 516 | + | |
| 517 | + | |
| 518 | + | |
| 519 | + | |
| 520 | + | |
| 521 | + | |
| 522 | + | |
| 523 | + | |
| 524 | + | |
| 525 | + | |
| 526 | + | |
| 527 | + | |
| 528 | + | |
| 529 | + | |
| 530 | + | |
| 531 | + | |
| 532 | + | |
| 533 | + | |
| 534 | + | |
| 535 | + | |
| 536 | + | |
| 537 | + | |
| 538 | + | |
| 539 | + | |
| 540 | + | |
| 541 | + | |
| 542 | + | |
| 543 | + | |
| 544 | + | |
| 545 | + | |
| 546 | + | |
| 547 | + | |
| 548 | + | |
| 549 | + | |
| 550 | + | |
| 551 | + | |
| 552 | + | |
| 553 | + | |
| 554 | + | |
| 555 | + | |
| 556 | + | |
| 557 | + | |
| 558 | + | |
| 559 | + | |
| 560 | + | |
| 561 | + | |
| 562 | + | |
| 563 | + | |
| 564 | + | |
| 565 | + | |
| 566 | + | |
| 567 | + | |
| 568 | + | |
| 569 | + | |
| 570 | + | |
| 571 | + | |
| 572 | + | |
| 573 | + | |
| 574 | + | |
| 575 | + | |
| 576 | + | |
| 577 | + | |
| 578 | + | |
| 579 | + | |
| 580 | + | |
| 581 | + | |
| 582 | + | |
| 583 | + | |
| 584 | + | |
| 585 | + | |
| 586 | + | |
| 587 | + | |
0 commit comments