Skip to content

Commit 483a48b

Browse files
hareshkhadriangbclaude
authored
[branch-54] fix: keep a CoalescePartitionsExec required by a SinglePartition child (#26961)
Backport of #23948 to `branch-54`. Credits: @adriangb ## Which issue does this PR close? - Related to #23948 - Related to #23805 ## Rationale for this change A valid query can be planned into a physical plan that `SanityCheckPlan` then rejects with `does not satisfy distribution requirements: SinglePartition`. A `CollectLeft` `HashJoinExec` requires `SinglePartition` on its build (left) child. `EnforceDistribution` adds a `CoalescePartitionsExec` there, but the sort-parallelization phase of `EnforceSorting` (`parallelize_sorts`) removes it again: `remove_bottleneck_in_subplan` drops a coalesce at `children[0]` based on its position, without checking the parent's distribution requirement for that child. See #23948 for the full analysis and reproducer. ## What changes are included in this PR? The fix from #23948: `remove_bottleneck_in_subplan` now checks the parent's per-child distribution requirement before removing a coalesce. The node being rewritten (the root of the call) is exempt. Differences from the original, needed for `branch-54`: - The distribution requirements are read with `required_input_distribution()` / `.get(idx)` instead of `input_distribution_requirements()` / `child_distribution(idx)`, which don't exist on this branch. The behavior is the same. - On this branch the logic lives in `EnforceSorting` (`datafusion/physical-optimizer/src/enforce_sorting/mod.rs`) rather than `EnsureRequirements`. ## Are these changes tested? Yes: - The end-to-end sqllogictest in `joins.slt` is the same as in the original (only a comment changes, to name `EnforceSorting`). - `ensure_requirements.rs` doesn't exist on this branch, so the two unit tests are in `datafusion/core/tests/physical_optimizer/enforce_sorting.rs`. They cover the same two build-side shapes (`UnknownPartitioning(n)` and `Hash([k], n)`). Each test builds the plan shape that `parallelize_sorts` receives, runs that phase directly, and then checks the result with `SanityCheckPlan`. Running the full rule would rewrite the plan before it reaches the code path under test. ## Are there any user-facing changes? No API changes. Plans that `SanityCheckPlan` used to reject now plan and execute. --------- Co-authored-by: Adrian Garcia Badaracco <[email protected]> Co-authored-by: Claude Opus 5 <[email protected]>
1 parent 1e317c7 commit 483a48b

3 files changed

Lines changed: 245 additions & 4 deletions

File tree

‎datafusion/core/tests/physical_optimizer/enforce_sorting.rs‎

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,7 +56,11 @@ use datafusion_physical_optimizer::enforce_sorting::replace_with_order_preservin
5656
use datafusion_physical_optimizer::enforce_sorting::sort_pushdown::{SortPushDown, assign_initial_requirements, pushdown_sorts};
5757
use datafusion_physical_optimizer::enforce_distribution::EnforceDistribution;
5858
use datafusion_physical_optimizer::output_requirements::OutputRequirementExec;
59+
use datafusion_physical_optimizer::sanity_checker::SanityCheckPlan;
5960
use datafusion_physical_optimizer::PhysicalOptimizerRule;
61+
use datafusion_physical_plan::joins::{HashJoinExec, PartitionMode};
62+
use datafusion::datasource::memory::MemorySourceConfig;
63+
use datafusion_common::NullEquality;
6064
use datafusion::prelude::*;
6165
use arrow::array::{record_batch, ArrayRef, Int32Array, RecordBatch};
6266
use arrow::datatypes::{Field};
@@ -2850,3 +2854,127 @@ async fn test_sort_with_streaming_table() -> Result<()> {
28502854

28512855
Ok(())
28522856
}
2857+
2858+
/// Builds the plan shape that `parallelize_sorts` sees in the reproducer, i.e. the
2859+
/// output of `EnforceDistribution` and the first `EnforceSorting` phase, not a freshly
2860+
/// planned tree:
2861+
///
2862+
/// ```text
2863+
/// CoalescePartitionsExec <- the node `parallelize_sorts` rewrites
2864+
/// HashJoinExec: mode=CollectLeft
2865+
/// CoalescePartitionsExec <- satisfies `SinglePartition` on the build side
2866+
/// <build>
2867+
/// RepartitionExec: RoundRobinBatch
2868+
/// CoalescePartitionsExec <- links the join into the coalesce cascade
2869+
/// DataSourceExec: partitions=4
2870+
/// ```
2871+
///
2872+
/// Both coalesces below the join matter. The probe-side one is what makes
2873+
/// `update_coalesce_ctx_children` mark the join as connected — it only skips children that
2874+
/// require `SinglePartition`, and the probe side does not — so the walk descends into the
2875+
/// join. The build-side one is the one that must survive.
2876+
fn collect_left_plan_before_parallelize_sorts(
2877+
build: Arc<dyn ExecutionPlan>,
2878+
join_type: JoinType,
2879+
) -> Result<Arc<dyn ExecutionPlan>> {
2880+
let schema = create_test_schema3()?;
2881+
let build = coalesce_partitions_exec(build);
2882+
let probe =
2883+
repartition_exec(coalesce_partitions_exec(multi_partition_exec(&schema)?));
2884+
2885+
let on = vec![(col("a", &schema)?, col("a", &schema)?)];
2886+
let join: Arc<dyn ExecutionPlan> = Arc::new(HashJoinExec::try_new(
2887+
build,
2888+
probe,
2889+
on,
2890+
None,
2891+
&join_type,
2892+
None,
2893+
PartitionMode::CollectLeft,
2894+
NullEquality::NullEqualsNothing,
2895+
false,
2896+
)?);
2897+
2898+
Ok(coalesce_partitions_exec(join))
2899+
}
2900+
2901+
/// A source with 4 partitions and `UnknownPartitioning`.
2902+
fn multi_partition_exec(schema: &SchemaRef) -> Result<Arc<dyn ExecutionPlan>> {
2903+
Ok(MemorySourceConfig::try_new_exec(
2904+
&[vec![], vec![], vec![], vec![]],
2905+
Arc::clone(schema),
2906+
None,
2907+
)?)
2908+
}
2909+
2910+
/// Runs `parallelize_sorts` on its own, the same way `EnforceSorting` drives it, and
2911+
/// checks the result with `SanityCheckPlan`.
2912+
///
2913+
/// The phase is driven directly rather than through `EnforceSorting::optimize` because
2914+
/// the earlier phase would rebuild the plan shape above into something that never reaches
2915+
/// the code path under test.
2916+
fn parallelize_sorts_and_sanity_check(plan: Arc<dyn ExecutionPlan>) -> Result<String> {
2917+
let ctx = PlanWithCorrespondingCoalescePartitions::new_default(plan);
2918+
let rewritten = ctx.transform_up(parallelize_sorts).data()?.plan;
2919+
SanityCheckPlan::new().optimize(Arc::clone(&rewritten), &ConfigOptions::new())?;
2920+
Ok(displayable(rewritten.as_ref()).indent(true).to_string())
2921+
}
2922+
2923+
/// A `CollectLeft` `HashJoinExec` requires `Distribution::SinglePartition` on its build
2924+
/// (left) child, so `EnforceDistribution` puts a `CoalescePartitionsExec` on top of a
2925+
/// multi-partition build side. The sort-parallelization phase must not take that coalesce
2926+
/// back out again.
2927+
///
2928+
/// It used to, because `remove_bottleneck_in_subplan` removed a coalesce found at
2929+
/// `children[0]` positionally, without consulting the parent's distribution requirement for
2930+
/// that child. The result was a build side left multi-partition with nothing to re-enforce
2931+
/// distribution afterwards, which `SanityCheckPlan` rejected with "does not satisfy
2932+
/// distribution requirements: SinglePartition".
2933+
#[test]
2934+
fn test_collect_left_join_keeps_build_side_coalesce() -> Result<()> {
2935+
let schema = create_test_schema3()?;
2936+
let plan = collect_left_plan_before_parallelize_sorts(
2937+
multi_partition_exec(&schema)?,
2938+
JoinType::Left,
2939+
)?;
2940+
2941+
// The build-side coalesce is retained; the probe-side one is still removed, which is
2942+
// the parallelization this phase exists for.
2943+
assert_snapshot!(parallelize_sorts_and_sanity_check(plan)?, @r"
2944+
CoalescePartitionsExec
2945+
HashJoinExec: mode=CollectLeft, join_type=Left, on=[(a@0, a@0)]
2946+
CoalescePartitionsExec
2947+
DataSourceExec: partitions=4, partition_sizes=[0, 0, 0, 0]
2948+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=4
2949+
DataSourceExec: partitions=4, partition_sizes=[0, 0, 0, 0]
2950+
");
2951+
2952+
Ok(())
2953+
}
2954+
2955+
/// The same removal, with a build side that is already hash-partitioned on the join key
2956+
/// rather than `UnknownPartitioning`. This is the shape a `JoinSelection` input swap leaves
2957+
/// behind (a `CollectLeft` join reported as `join_type=Right`) when the build subtree is the
2958+
/// output of an aggregate or a partitioned join: the build side satisfies the join's *hash*
2959+
/// requirement but still not `SinglePartition`, so the coalesce is just as load-bearing.
2960+
#[test]
2961+
fn test_collect_left_join_keeps_hash_partitioned_build_side_coalesce() -> Result<()> {
2962+
let schema = create_test_schema3()?;
2963+
let build = Arc::new(RepartitionExec::try_new(
2964+
multi_partition_exec(&schema)?,
2965+
Partitioning::Hash(vec![col("a", &schema)?], 8),
2966+
)?);
2967+
let plan = collect_left_plan_before_parallelize_sorts(build, JoinType::Right)?;
2968+
2969+
assert_snapshot!(parallelize_sorts_and_sanity_check(plan)?, @r"
2970+
CoalescePartitionsExec
2971+
HashJoinExec: mode=CollectLeft, join_type=Right, on=[(a@0, a@0)]
2972+
CoalescePartitionsExec
2973+
RepartitionExec: partitioning=Hash([a@0], 8), input_partitions=4
2974+
DataSourceExec: partitions=4, partition_sizes=[0, 0, 0, 0]
2975+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=4
2976+
DataSourceExec: partitions=4, partition_sizes=[0, 0, 0, 0]
2977+
");
2978+
2979+
Ok(())
2980+
}

‎datafusion/physical-optimizer/src/enforce_sorting/mod.rs‎

Lines changed: 43 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -676,11 +676,45 @@ fn adjust_window_sort_removal(
676676
/// the plan, some of the remaining `RepartitionExec`s might become unnecessary.
677677
/// Removes such `RepartitionExec`s from the plan as well.
678678
fn remove_bottleneck_in_subplan(
679+
requirements: PlanWithCorrespondingCoalescePartitions,
680+
) -> Result<PlanWithCorrespondingCoalescePartitions> {
681+
// The root is the node `parallelize_sorts` is rewriting (a `SortExec`,
682+
// `SortPreservingMergeExec` or `CoalescePartitionsExec`). Its own distribution
683+
// requirement does not constrain the removal, because the caller drops the node and
684+
// rebuilds the cascade around the result.
685+
remove_bottleneck_in_subplan_impl(requirements, true)
686+
}
687+
688+
fn remove_bottleneck_in_subplan_impl(
679689
mut requirements: PlanWithCorrespondingCoalescePartitions,
690+
is_root: bool,
680691
) -> Result<PlanWithCorrespondingCoalescePartitions> {
681692
let plan = &requirements.plan;
693+
// Below the root, a `CoalescePartitionsExec` feeding a child that requires
694+
// `Distribution::SinglePartition` is not an avoidable bottleneck: it is what satisfies
695+
// that requirement. Removing it leaves the parent with a multi-partition input it cannot
696+
// accept, and nothing re-runs distribution enforcement afterwards, so the plan reaches
697+
// `SanityCheckPlan` invalid. The traversal reaches such a node because
698+
// `update_coalesce_ctx_children` marks a node as connected when *any* child qualifies:
699+
// a `CollectLeft` `HashJoinExec` whose probe side is connected is descended into even
700+
// though its build side must stay single-partition.
701+
//
702+
// Only `SinglePartition` is protected. A `HashPartitioned` child is in principle in the
703+
// same position — a single-partition input trivially satisfies a hash requirement, so a
704+
// coalesce below one is also load-bearing — but nothing puts a coalesce there:
705+
// `ensure_distribution` satisfies a hash requirement with a `RepartitionExec`, never a
706+
// `CoalescePartitionsExec`. Widening the check would be dead code today.
707+
let dist_reqs = plan.required_input_distribution();
708+
let removable = |idx: usize| {
709+
is_root || !matches!(dist_reqs.get(idx), Some(Distribution::SinglePartition))
710+
};
711+
let remove_from_first_child = requirements
712+
.children
713+
.first()
714+
.is_some_and(|child| is_coalesce_partitions(&child.plan))
715+
&& removable(0);
682716
let children = &mut requirements.children;
683-
if is_coalesce_partitions(&children[0].plan) {
717+
if remove_from_first_child {
684718
// We can safely use the 0th index since we have a `CoalescePartitionsExec`.
685719
let mut new_child_node = children[0].children.swap_remove(0);
686720
while new_child_node.plan.output_partitioning() == plan.output_partitioning()
@@ -694,9 +728,14 @@ fn remove_bottleneck_in_subplan(
694728
requirements.children = requirements
695729
.children
696730
.into_iter()
697-
.map(|node| {
698-
if node.data {
699-
remove_bottleneck_in_subplan(node)
731+
.enumerate()
732+
.map(|(idx, node)| {
733+
// Deliberately conservative: not descending at all also skips legitimate
734+
// cleanups *below* a protected child (a redundant second coalesce under the
735+
// load-bearing one, say). This could later be narrowed to "descend, but
736+
// protect only the topmost coalesce" if that turns out to matter.
737+
if node.data && removable(idx) {
738+
remove_bottleneck_in_subplan_impl(node, false)
700739
} else {
701740
Ok(node)
702741
}

‎datafusion/sqllogictest/test_files/joins.slt‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5571,3 +5571,77 @@ set datafusion.execution.target_partitions = 4;
55715571

55725572
statement ok
55735573
reset datafusion.execution.batch_size;
5574+
5575+
# Regression test: a `CollectLeft` `HashJoinExec` requires `SinglePartition` on its build
5576+
# (left) child, and the `CoalescePartitionsExec` that satisfies it must survive the
5577+
# sort-parallelization phase of `EnforceSorting`. It used to be removed positionally
5578+
# (the traversal descends into the join because the *probe* side is linked to a coalesce),
5579+
# leaving a multi-partition build side that `SanityCheckPlan` rejects with
5580+
# "does not satisfy distribution requirements: SinglePartition".
5581+
5582+
statement ok
5583+
set datafusion.execution.target_partitions = 8;
5584+
5585+
# Keep the scan multi-partition as written, i.e. one partition per file.
5586+
statement ok
5587+
set datafusion.optimizer.repartition_file_scans = false;
5588+
5589+
statement ok
5590+
CREATE TABLE collect_left_src (id INT, ts INT) AS VALUES (1, 10), (2, 20), (3, 30);
5591+
5592+
query I
5593+
COPY (SELECT * FROM collect_left_src) TO 'test_files/scratch/joins/collect_left/0.parquet' STORED AS PARQUET;
5594+
----
5595+
3
5596+
5597+
query I
5598+
COPY (SELECT * FROM collect_left_src) TO 'test_files/scratch/joins/collect_left/1.parquet' STORED AS PARQUET;
5599+
----
5600+
3
5601+
5602+
query I
5603+
COPY (SELECT * FROM collect_left_src) TO 'test_files/scratch/joins/collect_left/2.parquet' STORED AS PARQUET;
5604+
----
5605+
3
5606+
5607+
query I
5608+
COPY (SELECT * FROM collect_left_src) TO 'test_files/scratch/joins/collect_left/3.parquet' STORED AS PARQUET;
5609+
----
5610+
3
5611+
5612+
statement ok
5613+
CREATE EXTERNAL TABLE collect_left STORED AS PARQUET LOCATION 'test_files/scratch/joins/collect_left/';
5614+
5615+
# The build side is the 4-partition scan; the probe side is the `DISTINCT ON` aggregate,
5616+
# whose `CoalescePartitionsExec` is what makes the traversal reach the join.
5617+
query I
5618+
SELECT a.id
5619+
FROM collect_left a
5620+
LEFT JOIN (SELECT DISTINCT ON (id) id, ts FROM collect_left ORDER BY id, ts) f
5621+
ON a.id = f.id
5622+
ORDER BY a.id;
5623+
----
5624+
1
5625+
1
5626+
1
5627+
1
5628+
2
5629+
2
5630+
2
5631+
2
5632+
3
5633+
3
5634+
3
5635+
3
5636+
5637+
statement ok
5638+
DROP TABLE collect_left;
5639+
5640+
statement ok
5641+
DROP TABLE collect_left_src;
5642+
5643+
statement ok
5644+
reset datafusion.optimizer.repartition_file_scans;
5645+
5646+
statement ok
5647+
set datafusion.execution.target_partitions = 4;

0 commit comments

Comments
 (0)