Repository navigation
Commit 390622a
authored
fix: validate sort pushdown through custom execution plans (#26118)
## Which issue does this PR close?
Closes #26656.
## Rationale for this change
Sort pushdown through a custom execution plan could return incorrectly
ordered results or fail plan validation when the operator reordered or
transformed columns.
[`ExecutionPlan::maintains_input_order`](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-plan/src/execution_plan.rs#L241)
describes row sequence. A custom projection computing `-a AS a`
preserves that sequence but reverses value ordering. For input `[2, 1,
3]`, the sort could move below the custom projection and produce `[-1,
-2, -3]`; keeping it above produces the requested ascending order, `[-3,
-2, -1]`.
Native
[`ProjectionExec`](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-plan/src/projection.rs#L75)
already has [specialized sort
pushdown](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/sort_pushdown.rs#L1334):
it remaps column references and rejects pushdown when a required key
comes from a computed expression. A custom projection can reach the
generic fallback, which did not verify how sorting its inputs affects
its output.
## What changes are included in this PR?
The [generic
fallback](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/sort_pushdown.rs#L1080)
builds temporary sorted inputs and checks the node's original input
ordering requirements. It then rebuilds the node so it recomputes its
properties from those inputs. Pushdown is accepted only if the rebuilt
node's input requirements are satisfied and its output provides the
requested ordering. These temporary plans are never executed.
Safe pushdown and compatible-sort consolidation remain available without
a new API or custom-node opt-in. The existing exclusions for filters,
repartitions, and conflicting input orderings remain.
<details>
<summary>Custom sort pushdown checks</summary>
These checks apply when the generic fallback proposes moving an ordering
below a node. Some built-in nodes also use this path. Nodes already
providing the requested ordering can use an earlier fast path if they
can retain any parent limit.
**1. Valid inputs**
- **Column mapping:** propose remapped plain-column keys for inputs
whose row order the node maintains. Every referenced column index must
be valid in each input that would be sorted.
- **Unbounded inputs:** an unbounded input must already satisfy its
proposed ordering requirement.
- **Input requirements:** temporary sorts preserve partitioning and must
satisfy the original node's input ordering requirements before
rebuilding. After rebuilding, check its input ordering, distribution,
and co-partitioning (compatible partition layouts across inputs).
**2. Correctly ordered output**
- The rebuilt node's output properties must prove the ordering requested
by its parent.
**3. Row selection and limits**
- **Parent limit:** if a parent limit is pending, decline pushdown
unless the node supports limit pushdown and preserves row count.
- **The node's own limit:** if the node reports a `fetch`, it must have
exactly one child, which must be a
[`SortExec`](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/physical-plan/src/sorts/sort.rs#L1134).
The proposed ordering must satisfy that child's complete original
ordering, including hidden keys, without relying on its old ordering
metadata.
- **Limit placement:** forward only a safe parent limit. Do not reuse
the node's own output `fetch` as an input bound: it may discard rows
through an offset or filter. Respect the child's own TopK bound.
A failed safety check declines pushdown; the caller keeps the necessary
sort or limit above the node. Errors propagate.
</details>
## What is the testing strategy for this PR?
[SQL
regressions](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/sqllogictest/test_files/sort_pushdown.slt)
check results and sort placement for transformed/reordered columns,
filtered computed keys, native TopK refinement, hidden sort keys, and a
custom offset with a limit. The [custom test
wrapper](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/sqllogictest/src/test_context/custom_sort_pushdown.rs)
skips identity projections so computed-key tests reach the generic
fallback. The test-only
[`CustomLimitRule`](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/sqllogictest/src/test_context/custom_sort_pushdown.rs#L134)
replaces an unnecessary sort on the already ordered test input with a
custom limit, so SQL `ORDER BY ... LIMIT` exercises the generic
fallback.
[Optimizer
snapshots](https://github.com/apache/datafusion/blob/6f3950c7c0698a88c1106f7fdc2a7d909d53aa7d/datafusion/core/tests/physical_optimizer/enforce_sorting.rs)
cover mandatory ordering conflicts, narrower child schemas, and
unbounded inputs. Removing each of the schema-width, unbounded-input,
and computed-key guards makes its regression test fail.
## Are there any user-facing changes?
Affected custom execution plans retain required sorts and row limits
while preserving safe sort refinements. No public API changes.
Developed with AI assistance.1 parent cadb6cd commit 390622a
7 files changed
Lines changed: 835 additions & 135 deletions
File tree
- datafusion
- core/tests/physical_optimizer
- physical-optimizer/src/ensure_requirements/enforce_sorting
- sqllogictest
- src
- test_context
- test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
13 | 13 | | |
14 | 14 | | |
15 | 15 | | |
16 | | - | |
| 16 | + | |
17 | 17 | | |
18 | 18 | | |
19 | 19 | | |
| |||
2775 | 2775 | | |
2776 | 2776 | | |
2777 | 2777 | | |
| 2778 | + | |
| 2779 | + | |
| 2780 | + | |
| 2781 | + | |
| 2782 | + | |
| 2783 | + | |
| 2784 | + | |
| 2785 | + | |
| 2786 | + | |
| 2787 | + | |
| 2788 | + | |
| 2789 | + | |
| 2790 | + | |
| 2791 | + | |
| 2792 | + | |
| 2793 | + | |
| 2794 | + | |
| 2795 | + | |
| 2796 | + | |
| 2797 | + | |
| 2798 | + | |
| 2799 | + | |
| 2800 | + | |
| 2801 | + | |
| 2802 | + | |
| 2803 | + | |
| 2804 | + | |
| 2805 | + | |
| 2806 | + | |
| 2807 | + | |
| 2808 | + | |
| 2809 | + | |
| 2810 | + | |
| 2811 | + | |
| 2812 | + | |
| 2813 | + | |
| 2814 | + | |
| 2815 | + | |
| 2816 | + | |
| 2817 | + | |
| 2818 | + | |
| 2819 | + | |
| 2820 | + | |
| 2821 | + | |
| 2822 | + | |
| 2823 | + | |
| 2824 | + | |
| 2825 | + | |
| 2826 | + | |
| 2827 | + | |
| 2828 | + | |
| 2829 | + | |
| 2830 | + | |
| 2831 | + | |
| 2832 | + | |
| 2833 | + | |
| 2834 | + | |
| 2835 | + | |
| 2836 | + | |
| 2837 | + | |
| 2838 | + | |
| 2839 | + | |
2778 | 2840 | | |
2779 | 2841 | | |
2780 | 2842 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
21 | 21 | | |
22 | 22 | | |
23 | 23 | | |
| 24 | + | |
24 | 25 | | |
25 | | - | |
| 26 | + | |
| 27 | + | |
26 | 28 | | |
27 | 29 | | |
28 | 30 | | |
| |||
1124 | 1126 | | |
1125 | 1127 | | |
1126 | 1128 | | |
| 1129 | + | |
| 1130 | + | |
| 1131 | + | |
| 1132 | + | |
| 1133 | + | |
| 1134 | + | |
| 1135 | + | |
| 1136 | + | |
| 1137 | + | |
| 1138 | + | |
| 1139 | + | |
| 1140 | + | |
| 1141 | + | |
| 1142 | + | |
| 1143 | + | |
| 1144 | + | |
| 1145 | + | |
| 1146 | + | |
| 1147 | + | |
| 1148 | + | |
| 1149 | + | |
| 1150 | + | |
| 1151 | + | |
1127 | 1152 | | |
1128 | 1153 | | |
1129 | 1154 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
421 | 421 | | |
422 | 422 | | |
423 | 423 | | |
424 | | - | |
| 424 | + | |
| 425 | + | |
425 | 426 | | |
426 | 427 | | |
427 | 428 | | |
428 | 429 | | |
429 | 430 | | |
430 | | - | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
431 | 434 | | |
432 | 435 | | |
433 | 436 | | |
434 | 437 | | |
| 438 | + | |
435 | 439 | | |
436 | 440 | | |
437 | 441 | | |
438 | 442 | | |
439 | | - | |
| 443 | + | |
| 444 | + | |
| 445 | + | |
440 | 446 | | |
441 | 447 | | |
442 | 448 | | |
| 449 | + | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
| 461 | + | |
443 | 462 | | |
444 | 463 | | |
445 | 464 | | |
| |||
490 | 509 | | |
491 | 510 | | |
492 | 511 | | |
493 | | - | |
| 512 | + | |
494 | 513 | | |
495 | 514 | | |
496 | 515 | | |
497 | 516 | | |
498 | 517 | | |
499 | 518 | | |
500 | | - | |
| 519 | + | |
| 520 | + | |
501 | 521 | | |
502 | 522 | | |
503 | 523 | | |
504 | 524 | | |
505 | | - | |
| 525 | + | |
| 526 | + | |
| 527 | + | |
| 528 | + | |
506 | 529 | | |
507 | 530 | | |
508 | 531 | | |
509 | | - | |
| 532 | + | |
510 | 533 | | |
511 | 534 | | |
512 | 535 | | |
513 | | - | |
| 536 | + | |
514 | 537 | | |
515 | 538 | | |
516 | 539 | | |
517 | 540 | | |
518 | 541 | | |
519 | 542 | | |
520 | 543 | | |
521 | | - | |
522 | | - | |
| 544 | + | |
| 545 | + | |
523 | 546 | | |
524 | 547 | | |
525 | | - | |
526 | | - | |
| 548 | + | |
| 549 | + | |
| 550 | + | |
| 551 | + | |
| 552 | + | |
| 553 | + | |
527 | 554 | | |
528 | 555 | | |
529 | 556 | | |
| |||
1061 | 1088 | | |
1062 | 1089 | | |
1063 | 1090 | | |
| 1091 | + | |
| 1092 | + | |
| 1093 | + | |
| 1094 | + | |
1064 | 1095 | | |
1065 | 1096 | | |
1066 | 1097 | | |
| |||
0 commit comments