Skip to content

Commit 0d3aac0

Browse files
jayzhan211alambclaude
authored
Check the final physical plan in the planner and name the rule that broke it (apache#26461)
## Which issue does this PR close? - Closes apache#26460. Related: apache#26171 (option 3), apache#26351, apache#26360, apache#25688. ## Rationale for this change `SanityCheckPlan` is the last rule in `PhysicalOptimizer::new()`, so rules appended with `SessionStateBuilder::with_physical_optimizer_rule` run after it and are never checked. On `main`, an appended rule that removes a window's sort silently returns wrong `row_number()` values. Custom pipelines have to keep the rule last by hand, and a custom list without it runs plans whose requirements do not hold. When the check does fail, the error only says `SanityCheckPlan`, so finding the rule that broke the plan has needed a manual bisect each time (for example apache#26391, apache#17077, apache#25921). @alamb suggested this change in the review of apache#26107: remove `SanityCheckPlan` as an optimizer pass and always run it after the optimizer is done ([comment](apache#26107 (comment))). apache#26171 agreed (option 3) that a custom pipeline must keep the plan valid, while optimization coverage is not guaranteed. This PR makes that validity part checked for every pipeline. The review on apache#26360 asked for the same shape: one rule, `EnsureRequirements`, makes the plan valid, and every later rule keeps it valid. ## What changes are included in this PR? - `SanityCheckPlan` leaves the default rule list. `DefaultPhysicalPlanner::optimize_physical_plan` runs the same check (unbounded inputs, ordering, distribution, `check_invariants(Executable)`) after the last rule, including appended rules. It replaces the planner's own `InvariantChecker(Executable)` walk, which `SanityCheckPlan` repeated. - When the ordering or distribution requirements fail, the planner runs the rules again from the input plan to name the rule that broke them, so planning that succeeds keeps no intermediate plans: ```text SanityCheckPlan: order and distribution requirements stopped holding after physical optimizer rule 'ProjectionPushdown' caused by Error during planning: Plan: [...] does not satisfy order requirements: [...] ``` or, when the plan was already invalid as `EnsureRequirements` produced it: ```text SanityCheckPlan: the plan produced by physical optimizer rule 'EnsureRequirements' does not satisfy the order and distribution requirements ``` Plans before `EnsureRequirements` need not satisfy the requirements, so only plans from its last run onwards are checked. The rule is recognized by its name; a separate enforcement phase (apache#25688) would give a cleaner boundary. Errors about unbounded inputs keep the plain `SanityCheckPlan` context, so existing messages do not change. - `sanity_checker` exposes `check_plan_tree_sanity`, `check_input_requirements` and `input_requirements_hold`, which the planner uses. - `SanityCheckPlan` is deprecated. Tests that used it to validate a plan call `check_plan_tree_sanity` instead. - The upgrade guide, the optimizer rule reference and `explain.slt` are updated. ## What is the testing strategy for this PR? - `sanity_checker.rs`: a rule appended after the default rules that removes sorts is reported by name; a custom list without `EnsureRequirements` reports that no rule produced a valid plan. - `memory_limit/mod.rs`: the two sort merge join tests ran a `SortMergeJoinExec` over unsorted streams through a custom rule list without `EnsureRequirements`. They now sort the generated data by the join keys and declare that order, so the plan is valid and the tests still measure the join's memory use. - The extended workspace suite passes. ## Are there any user-facing changes? - Plans produced by rules added with `with_physical_optimizer_rule`, or by a custom rule list, are now checked. A plan whose requirements do not hold, such as a sort merge join over unsorted input, fails to plan instead of running and possibly returning wrong results. - `PhysicalOptimizer::new()` no longer contains `SanityCheckPlan`, and `EXPLAIN VERBOSE` no longer prints `physical_plan after SanityCheckPlan`. Code that looks the rule up in the default list no longer finds it. `SanityCheckPlan` itself is deprecated; code that runs optimizer rules without the planner can call `sanity_checker::check_plan_tree_sanity` on the final plan. - Errors for broken ordering or distribution requirements name the rule that broke them. This changes the public behavior of the default rule list, so it needs the `api change` label. --------- Co-authored-by: Andrew Lamb <[email protected]> Co-authored-by: Claude Fable 5.1 <[email protected]>
1 parent 503fde8 commit 0d3aac0

11 files changed

Lines changed: 349 additions & 99 deletions

File tree

‎datafusion/core/src/optimizer_rule_reference.md‎

Lines changed: 28 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -69,27 +69,31 @@ Rule order matters. The default pipeline may change between releases.
6969
The same rule name may appear more than once when the default pipeline runs it
7070
in multiple phases.
7171

72-
| order | rule | phase | summary |
73-
| ----- | ------------------------------ | ----------------------- | ------------------------------------------------------------------------------------------------------------ |
74-
| 1 | `OutputRequirements` | add phase | Adds helper nodes so output requirements survive later physical rewrites. |
75-
| 2 | `aggregate_statistics` | - | Uses exact source statistics to answer some aggregates without scanning data. |
76-
| 3 | `EliminateConstantJoin` | - | Replaces inner joins against a single row of literals with a filter that keeps the other input's order. |
77-
| 4 | `join_selection` | - | Chooses join implementation, build side, and partition mode from statistics and stream properties. |
78-
| 5 | `LimitedDistinctAggregation` | - | Pushes limit hints into grouped distinct-style aggregations when only a small result is needed. |
79-
| 6 | `FilterPushdown` | pre-optimization phase | Pushes supported physical filters down toward data sources before distribution and sorting are enforced. |
80-
| 7 | `WindowTopN` | - | Replaces eligible row-number window and filter patterns with per-partition TopK execution. |
81-
| 8 | `EnsureRequirements` | - | Enforces both distribution and sorting requirements in a single idempotent rule. |
82-
| 9 | `CombinePartialFinalAggregate` | - | Collapses adjacent partial and final aggregates when the distributed shape makes them redundant. |
83-
| 10 | `OptimizeAggregateOrder` | - | Updates aggregate expressions to use the best ordering once sort requirements are known. |
84-
| 11 | `ProjectionPushdown` | early pass | Pushes projections toward inputs before later physical rewrites add more limit and TopK structure. |
85-
| 12 | `OutputRequirements` | remove phase | Removes the temporary output-requirement helper nodes after requirement-sensitive planning is done. |
86-
| 13 | `LimitAggregation` | - | Passes a limit hint into eligible aggregations so they can keep fewer accumulator buckets. |
87-
| 14 | `LimitPushPastWindows` | - | Pushes fetch limits through bounded window operators when doing so keeps the result correct. |
88-
| 15 | `HashJoinBuffering` | - | Adds buffering on the probe side of hash joins so probing can start before build completion. |
89-
| 16 | `LimitPushdown` | - | Moves physical limits into child operators or fetch-enabled variants to cut data early. |
90-
| 17 | `TopKRepartition` | - | Pushes TopK below hash repartition when the partition key is a prefix of the sort key. |
91-
| 18 | `ProjectionPushdown` | late pass | Runs projection pushdown again after limit and TopK rewrites expose new pruning opportunities. |
92-
| 19 | `PushdownSort` | - | Pushes sort requirements into data sources that can already return sorted output. |
93-
| 20 | `EnsureCooperative` | - | Wraps non-cooperative plan parts so long-running tasks yield fairly. |
94-
| 21 | `FilterPushdown(Post)` | post-optimization phase | Pushes dynamic filters at the end of optimization, after plan references stop moving. |
95-
| 22 | `SanityCheckPlan` | - | Validates that the final physical plan meets ordering, distribution, and infinite-input safety requirements. |
72+
After the last rule, including any rule added by the user, the physical planner
73+
checks that the final plan meets its ordering, distribution, and infinite-input
74+
safety requirements (`SanityCheckPlan`). If the ordering or distribution
75+
requirements do not hold, the error names the rule that broke them.
76+
77+
| order | rule | phase | summary |
78+
| ----- | ------------------------------ | ----------------------- | -------------------------------------------------------------------------------------------------------- |
79+
| 1 | `OutputRequirements` | add phase | Adds helper nodes so output requirements survive later physical rewrites. |
80+
| 2 | `aggregate_statistics` | - | Uses exact source statistics to answer some aggregates without scanning data. |
81+
| 3 | `EliminateConstantJoin` | - | Replaces inner joins against a single row of literals with a filter that keeps the other input's order. |
82+
| 4 | `join_selection` | - | Chooses join implementation, build side, and partition mode from statistics and stream properties. |
83+
| 5 | `LimitedDistinctAggregation` | - | Pushes limit hints into grouped distinct-style aggregations when only a small result is needed. |
84+
| 6 | `FilterPushdown` | pre-optimization phase | Pushes supported physical filters down toward data sources before distribution and sorting are enforced. |
85+
| 7 | `WindowTopN` | - | Replaces eligible row-number window and filter patterns with per-partition TopK execution. |
86+
| 8 | `EnsureRequirements` | - | Enforces both distribution and sorting requirements in a single idempotent rule. |
87+
| 9 | `CombinePartialFinalAggregate` | - | Collapses adjacent partial and final aggregates when the distributed shape makes them redundant. |
88+
| 10 | `OptimizeAggregateOrder` | - | Updates aggregate expressions to use the best ordering once sort requirements are known. |
89+
| 11 | `ProjectionPushdown` | early pass | Pushes projections toward inputs before later physical rewrites add more limit and TopK structure. |
90+
| 12 | `OutputRequirements` | remove phase | Removes the temporary output-requirement helper nodes after requirement-sensitive planning is done. |
91+
| 13 | `LimitAggregation` | - | Passes a limit hint into eligible aggregations so they can keep fewer accumulator buckets. |
92+
| 14 | `LimitPushPastWindows` | - | Pushes fetch limits through bounded window operators when doing so keeps the result correct. |
93+
| 15 | `HashJoinBuffering` | - | Adds buffering on the probe side of hash joins so probing can start before build completion. |
94+
| 16 | `LimitPushdown` | - | Moves physical limits into child operators or fetch-enabled variants to cut data early. |
95+
| 17 | `TopKRepartition` | - | Pushes TopK below hash repartition when the partition key is a prefix of the sort key. |
96+
| 18 | `ProjectionPushdown` | late pass | Runs projection pushdown again after limit and TopK rewrites expose new pruning opportunities. |
97+
| 19 | `PushdownSort` | - | Pushes sort requirements into data sources that can already return sorted output. |
98+
| 20 | `EnsureCooperative` | - | Wraps non-cooperative plan parts so long-running tasks yield fairly. |
99+
| 21 | `FilterPushdown(Post)` | post-optimization phase | Pushes dynamic filters at the end of optimization, after plan references stop moving. |

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 83 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,10 @@ use datafusion_physical_expr::expressions::Literal;
9494
use datafusion_physical_expr::{
9595
LexOrdering, PhysicalSortExpr, create_physical_sort_exprs,
9696
};
97+
use datafusion_physical_optimizer::ensure_requirements::EnsureRequirements;
98+
use datafusion_physical_optimizer::sanity_checker::{
99+
check_plan_tree_sanity, input_requirements_hold,
100+
};
97101
use datafusion_physical_plan::empty::EmptyExec;
98102
use datafusion_physical_plan::execution_plan::InvariantLevel;
99103
use datafusion_physical_plan::joins::PiecewiseMergeJoinExec;
@@ -3481,9 +3485,18 @@ impl DefaultPhysicalPlanner {
34813485
observer(new_plan.as_ref(), optimizer.as_ref())
34823486
}
34833487

3484-
// This runs once after all optimizer runs are complete,
3485-
// to verify that the plan is executable.
3486-
InvariantChecker(InvariantLevel::Executable).check(&new_plan)?;
3488+
// This runs once after all optimizer runs are complete, including
3489+
// rules appended by the user, to verify that the plan is executable.
3490+
let optimizer_options = &session_state.config_options().optimizer;
3491+
if let Err(e) = check_plan_tree_sanity(&new_plan, optimizer_options) {
3492+
return Err(sanity_check_error(
3493+
e,
3494+
&new_plan,
3495+
plan,
3496+
optimizers,
3497+
&optimizer_context,
3498+
));
3499+
}
34873500

34883501
debug!(
34893502
"Optimized physical plan:\n{}\n",
@@ -3693,6 +3706,73 @@ fn tuple_err<T, R>(value: (Result<T>, Result<R>)) -> Result<(T, R)> {
36933706
}
36943707
}
36953708

3709+
/// Adds context to an error from the final [`check_plan_tree_sanity`].
3710+
///
3711+
/// `EnsureRequirements` makes the order and distribution requirements hold,
3712+
/// and every rule after it must keep them. When they do not hold for
3713+
/// `final_plan`, the context names the rule that broke this contract: either
3714+
/// `EnsureRequirements` itself, or the rule after which the requirements
3715+
/// stopped holding. To find it, `optimizers` run again from `input_plan`, so
3716+
/// planning that succeeds keeps no intermediate plans.
3717+
fn sanity_check_error(
3718+
error: DataFusionError,
3719+
final_plan: &Arc<dyn ExecutionPlan>,
3720+
input_plan: Arc<dyn ExecutionPlan>,
3721+
optimizers: &[Arc<dyn PhysicalOptimizerRule + Send + Sync>],
3722+
optimizer_context: &dyn PhysicalOptimizerContext,
3723+
) -> DataFusionError {
3724+
const SANITY_CHECK: &str = "SanityCheckPlan";
3725+
let plain_error =
3726+
|error| DataFusionError::Context(SANITY_CHECK.to_string(), Box::new(error));
3727+
if input_requirements_hold(final_plan) {
3728+
// The error is about unbounded inputs or another invariant.
3729+
return plain_error(error);
3730+
}
3731+
3732+
let ensure_requirements = EnsureRequirements::new();
3733+
let enforced = optimizers
3734+
.iter()
3735+
.rposition(|rule| rule.name() == ensure_requirements.name());
3736+
// Plans before `EnsureRequirements` need not satisfy the requirements, so
3737+
// only plans from its last run onwards are checked. Without it, every
3738+
// plan is checked, starting with the input plan.
3739+
let first_checked = enforced.unwrap_or(0);
3740+
let mut held = enforced.is_none() && input_requirements_hold(&input_plan);
3741+
let mut broken_by = None;
3742+
let mut plan = input_plan;
3743+
for (idx, rule) in optimizers.iter().enumerate() {
3744+
plan = match rule.optimize_with_context(plan, optimizer_context) {
3745+
Ok(plan) => plan,
3746+
// The rules did not run as they did before, so no rule is named.
3747+
Err(_) => return plain_error(error),
3748+
};
3749+
if idx >= first_checked {
3750+
let holds = input_requirements_hold(&plan);
3751+
if held && !holds {
3752+
broken_by = Some(rule);
3753+
}
3754+
held = holds;
3755+
}
3756+
}
3757+
let context = match (broken_by, enforced) {
3758+
(Some(rule), _) => format!(
3759+
"{SANITY_CHECK}: order and distribution requirements stopped holding \
3760+
after physical optimizer rule '{}'",
3761+
rule.name()
3762+
),
3763+
(None, Some(_)) => format!(
3764+
"{SANITY_CHECK}: the plan produced by physical optimizer rule '{}' \
3765+
does not satisfy the order and distribution requirements",
3766+
ensure_requirements.name()
3767+
),
3768+
(None, None) => format!(
3769+
"{SANITY_CHECK}: no physical optimizer rule produced a plan that \
3770+
satisfies the order and distribution requirements"
3771+
),
3772+
};
3773+
DataFusionError::Context(context, Box::new(error))
3774+
}
3775+
36963776
struct OptimizationInvariantChecker<'a> {
36973777
rule: &'a Arc<dyn PhysicalOptimizerRule + Send + Sync>,
36983778
}

‎datafusion/core/tests/memory_limit/mod.rs‎

Lines changed: 45 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -578,7 +578,7 @@ async fn sort_merge_join_no_spill() {
578578
])
579579
.with_memory_limit(1_000)
580580
.with_config(config)
581-
.with_scenario(Scenario::AccessLogStreaming)
581+
.with_scenario(Scenario::AccessLogStreamingByPodTime)
582582
.run()
583583
.await
584584
}
@@ -597,7 +597,7 @@ async fn sort_merge_join_spill() {
597597
.with_memory_limit(1_000)
598598
.with_config(config)
599599
.with_disk_manager_builder(DiskManagerBuilder::default())
600-
.with_scenario(Scenario::AccessLogStreaming)
600+
.with_scenario(Scenario::AccessLogStreamingByPodTime)
601601
.with_expected_success()
602602
.run()
603603
.await
@@ -1461,6 +1461,11 @@ enum Scenario {
14611461
/// [`StreamingTable`]
14621462
AccessLogStreaming,
14631463

1464+
/// [`Self::AccessLogStreaming`], sorted by `pod, time`, with a
1465+
/// [`StreamingTable`] that declares that order. A sort merge join on
1466+
/// `pod, time` then needs no sort.
1467+
AccessLogStreamingByPodTime,
1468+
14641469
/// N partitions of sorted, dictionary encoded strings.
14651470
DictionaryStrings {
14661471
partitions: usize,
@@ -1522,6 +1527,23 @@ impl Scenario {
15221527
.with_infinite_table(true);
15231528
Arc::new(table)
15241529
}
1530+
Self::AccessLogStreamingByPodTime => {
1531+
let batches = access_log_batches_by_pod_time();
1532+
let table = StreamingTable::try_new(
1533+
batches[0].schema(),
1534+
vec![Arc::new(DummyStreamPartition {
1535+
schema: batches[0].schema(),
1536+
batches,
1537+
})],
1538+
)
1539+
.unwrap()
1540+
.with_infinite_table(true)
1541+
.with_sort_order(vec![
1542+
datafusion_expr::col("pod").sort(true, true),
1543+
datafusion_expr::col("time").sort(true, true),
1544+
]);
1545+
Arc::new(table)
1546+
}
15251547
Self::DictionaryStrings {
15261548
partitions,
15271549
single_row_batches,
@@ -1570,7 +1592,7 @@ impl Scenario {
15701592
// has a memory budget which we'll likely hit first)
15711593
Some(vec![Arc::new(JoinSelection::new())])
15721594
}
1573-
Self::AccessLogStreaming => {
1595+
Self::AccessLogStreaming | Self::AccessLogStreamingByPodTime => {
15741596
// Disable all physical optimizer rules except the
15751597
// JoinSelection rule to avoid sorts or repartition,
15761598
// as they also have memory budgets that may be hit
@@ -1646,6 +1668,26 @@ fn access_log_batches() -> Vec<RecordBatch> {
16461668
.collect()
16471669
}
16481670

1671+
/// [`access_log_batches`] sorted by `pod, time`, in batches of 50 rows
1672+
fn access_log_batches_by_pod_time() -> Vec<RecordBatch> {
1673+
let batches = access_log_batches();
1674+
let batch = arrow::compute::concat_batches(&batches[0].schema(), &batches).unwrap();
1675+
let sort_column = |name: &str| arrow::compute::SortColumn {
1676+
values: Arc::clone(batch.column_by_name(name).unwrap()),
1677+
options: Some(SortOptions::default()),
1678+
};
1679+
let indices = arrow::compute::lexsort_to_indices(
1680+
&[sort_column("pod"), sort_column("time")],
1681+
None,
1682+
)
1683+
.unwrap();
1684+
let batch = arrow::compute::take_record_batch(&batch, &indices).unwrap();
1685+
(0..batch.num_rows())
1686+
.step_by(50)
1687+
.map(|offset| batch.slice(offset, 50.min(batch.num_rows() - offset)))
1688+
.collect()
1689+
}
1690+
16491691
/// If `one_row_batches` is true, then returns new record batches that
16501692
/// are one row in size
16511693
fn maybe_split_batches(

0 commit comments

Comments
 (0)