Skip to content

Commit c14633e

Browse files
authored
fix: normalize InterleaveExec to UnionExec before enforcing distribution (apache#24959)
## Which issue does this PR close? - Part of apache#21826. ## Rationale for this change `EnsureRequirements` fails with an internal error when the plan it is given already contains an `InterleaveExec` whose children no longer share a hash (or range) partitioning: ``` Internal error: Assertion failed: can_interleave(children.iter()): Can not create InterleaveExec: new children can not be interleaved. ``` `InterleaveExec` declares no distribution requirement of its own. It is only valid while its children happen to share the same partitioning, which is why `ensure_distribution` creates it from a `UnionExec` in the first place. Once it exists, several rewrites can take that partitioning away: this rule strips `RepartitionExec`s that nothing requires, join key reordering changes the hash expressions, `JoinSelection` side swaps change output partitioning, and so on. `PlanContext::with_new_children` rebuilds every parent from its updated children while walking the tree, so the interleave is rebuilt over the changed children *before* the rule's closure sees the node, and the rebuild fails. This affects any pipeline that runs the rule more than once, re-optimizes a deserialized plan, or runs `EnforceDistribution` after other rewrites (the setup reported in apache#21826). It also breaks the idempotency the rule advertises. The discussion on apache#21827 concluded that the fix belongs at the `EnforceDistribution` call site rather than as a silent fallback in `InterleaveExec::with_new_children`; this PR is that fix. ## What changes are included in this PR? - New `replace_interleave_with_union` helper in `ensure_requirements/enforce_distribution.rs`, which turns an `InterleaveExec` back into the equivalent `UnionExec`. - `EnsureRequirements::optimize` runs it as a top-down "Phase 0" before join key reordering. Phase 2 then re-derives interleaves from unions wherever the children still qualify, exactly as it already re-derives `RepartitionExec`, `CoalescePartitionsExec` and `SortPreservingMergeExec`. - The pass is top-down on purpose: demoting a nested interleave first would change its output partitioning and make the parent interleave fail to rebuild. - Module docs updated with the new phase. A minimal reproducer that fails on `main` and passes here: ```rust // Interleave over two hash repartitions that nothing above requires. let plan = InterleaveExec::try_new(vec![ RepartitionExec::try_new(parquet_exec(), Partitioning::Hash(vec![col_a], 10))?, RepartitionExec::try_new(parquet_exec(), Partitioning::Hash(vec![col_a], 10))?, ])?; EnsureRequirements::new().optimize(Arc::new(plan), &config)?; ``` ## What is the testing strategy for this PR? Three new tests in `datafusion/core/tests/physical_optimizer/enforce_distribution.rs`, each run through the existing multi-pass harness (`DISTRIB_DISTRIB_SORT` and `SORT_DISTRIB_DISTRIB`) so idempotency is checked as well: - `interleave_falls_back_to_union_when_children_lose_partitioning`: the reproducer above; the result is a `UnionExec` over the scans. - `interleave_fallback_still_satisfies_parent_hash_requirement`: same input under a `FinalPartitioned` aggregate; the aggregate gets a single hash repartition above the union. - `existing_interleave_is_kept_when_children_stay_interleavable`: an interleave over hash partitioned aggregates is re-derived as an interleave, and stays a union with `prefer_existing_union = true`. The test harness's tree-node integrity block now applies the same pre-pass so it mirrors the rule. Existing `union_to_interleave` and `union_not_to_interleave` tests are unchanged, and `union.slt` passes. ## Are there any user-facing changes? No API changes. One behavioral note: with `datafusion.optimizer.prefer_existing_union = true`, an `InterleaveExec` present in the input plan is now emitted as a `UnionExec`. The rule never creates interleaves under that setting, and plans produced by the default pipeline are unaffected because `EnsureRequirements` is the only creator of `InterleaveExec` and runs once.
1 parent 1d9a982 commit c14633e

3 files changed

Lines changed: 207 additions & 1 deletion

File tree

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

Lines changed: 163 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -71,8 +71,9 @@ use datafusion_physical_plan::filter::FilterExec;
7171
use datafusion_physical_plan::joins::utils::JoinOn;
7272
use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
7373
use datafusion_physical_plan::projection::{ProjectionExec, ProjectionExpr};
74+
use datafusion_physical_plan::repartition::RepartitionExec;
7475
use datafusion_physical_plan::sorts::sort_preserving_merge::SortPreservingMergeExec;
75-
use datafusion_physical_plan::union::UnionExec;
76+
use datafusion_physical_plan::union::{InterleaveExec, UnionExec};
7677
use datafusion_physical_plan::{
7778
ChildrenPropertiesMode, DisplayAs, DisplayFormatType, ExecutionPlanProperties,
7879
PlanProperties, ReplaceChildrenOptions, displayable,
@@ -731,6 +732,12 @@ impl TestConfig {
731732
// After these operations tree nodes should be in a consistent state.
732733
// This code block makes sure that these rules doesn't violate tree node integrity.
733734
{
735+
// Mirror `EnsureRequirements`: interleaves are normalized to
736+
// unions before distribution is enforced.
737+
let plan = plan
738+
.clone()
739+
.transform_down(replace_interleave_with_union)
740+
.data()?;
734741
let adjusted = if self.config.optimizer.top_down_join_key_reordering {
735742
// Run adjust_input_keys_ordering rule
736743
let plan_requirements =
@@ -2694,6 +2701,161 @@ fn union_not_to_interleave() -> Result<()> {
26942701
Ok(())
26952702
}
26962703

2704+
/// Builds `RepartitionExec(Hash([a], 10))` over a single-partition parquet scan.
2705+
fn hash_repartitioned_parquet_exec() -> Result<Arc<dyn ExecutionPlan>> {
2706+
let schema = schema();
2707+
Ok(Arc::new(RepartitionExec::try_new(
2708+
parquet_exec(),
2709+
Partitioning::Hash(vec![col("a", &schema)?], 10),
2710+
)?))
2711+
}
2712+
2713+
/// Builds `FinalPartitioned <- RepartitionExec(Hash([alias], 10)) <- Partial <- input`,
2714+
/// i.e. an aggregate whose output is natively hash partitioned on its group key.
2715+
fn hash_partitioned_aggregate_exec(
2716+
input: Arc<dyn ExecutionPlan>,
2717+
column: &str,
2718+
alias: &str,
2719+
) -> Result<Arc<dyn ExecutionPlan>> {
2720+
let schema = schema();
2721+
let group_by = PhysicalGroupBy::new_single(vec![(
2722+
col(column, &input.schema())?,
2723+
alias.to_string(),
2724+
)]);
2725+
let partial = Arc::new(AggregateExec::try_new(
2726+
AggregateMode::Partial,
2727+
group_by,
2728+
vec![],
2729+
vec![],
2730+
input,
2731+
schema.clone(),
2732+
)?);
2733+
let hash_expr = col(alias, &partial.schema())?;
2734+
let repartition = Arc::new(RepartitionExec::try_new(
2735+
partial,
2736+
Partitioning::Hash(vec![hash_expr], 10),
2737+
)?);
2738+
let final_grouping = PhysicalGroupBy::new_single(vec![(
2739+
Arc::new(Column::new(alias, 0)) as Arc<dyn PhysicalExpr>,
2740+
alias.to_string(),
2741+
)]);
2742+
Ok(Arc::new(AggregateExec::try_new(
2743+
AggregateMode::FinalPartitioned,
2744+
final_grouping,
2745+
vec![],
2746+
vec![],
2747+
repartition,
2748+
schema,
2749+
)?))
2750+
}
2751+
2752+
#[test]
2753+
fn interleave_falls_back_to_union_when_children_lose_partitioning() -> Result<()> {
2754+
// An `InterleaveExec` whose children are hash partitioned only by
2755+
// `RepartitionExec`s that nothing requires. The rule removes those
2756+
// repartitions, after which the children can no longer be interleaved,
2757+
// so the node must degrade to a `UnionExec` instead of failing
2758+
// (https://github.com/apache/datafusion/issues/21826).
2759+
let plan: Arc<dyn ExecutionPlan> = Arc::new(InterleaveExec::try_new(vec![
2760+
hash_repartitioned_parquet_exec()?,
2761+
hash_repartitioned_parquet_exec()?,
2762+
])?);
2763+
2764+
let test_config = TestConfig::default();
2765+
let plan_distrib = test_config.to_plan(plan.clone(), &DISTRIB_DISTRIB_SORT);
2766+
assert_plan!(plan_distrib,
2767+
@r"
2768+
UnionExec
2769+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2770+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2771+
");
2772+
let plan_sort = test_config.to_plan(plan, &SORT_DISTRIB_DISTRIB);
2773+
assert_plan!(plan_distrib, plan_sort);
2774+
2775+
Ok(())
2776+
}
2777+
2778+
#[test]
2779+
fn interleave_fallback_still_satisfies_parent_hash_requirement() -> Result<()> {
2780+
// Same as above, but a parent requires hash partitioning. After the
2781+
// interleave degrades to a union, the parent's requirement is enforced
2782+
// with a single repartition above the union.
2783+
let interleave: Arc<dyn ExecutionPlan> = Arc::new(InterleaveExec::try_new(vec![
2784+
hash_repartitioned_parquet_exec()?,
2785+
hash_repartitioned_parquet_exec()?,
2786+
])?);
2787+
let plan =
2788+
aggregate_exec_with_alias(interleave, vec![("a".to_string(), "a".to_string())]);
2789+
2790+
let test_config = TestConfig::default();
2791+
let plan_distrib = test_config.to_plan(plan.clone(), &DISTRIB_DISTRIB_SORT);
2792+
assert_plan!(plan_distrib,
2793+
@r"
2794+
AggregateExec: mode=FinalPartitioned, gby=[a@0 as a], aggr=[]
2795+
RepartitionExec: partitioning=Hash([a@0], 10), input_partitions=10
2796+
AggregateExec: mode=Partial, gby=[a@0 as a], aggr=[]
2797+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=2
2798+
UnionExec
2799+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2800+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2801+
");
2802+
let plan_sort = test_config.to_plan(plan, &SORT_DISTRIB_DISTRIB);
2803+
assert_plan!(plan_distrib, plan_sort);
2804+
2805+
Ok(())
2806+
}
2807+
2808+
#[test]
2809+
fn existing_interleave_is_kept_when_children_stay_interleavable() -> Result<()> {
2810+
// An `InterleaveExec` over hash-partitioned aggregates. The aggregates
2811+
// require the hash partitioning, so the children stay interleavable and
2812+
// the interleave is re-derived.
2813+
let plan: Arc<dyn ExecutionPlan> = Arc::new(InterleaveExec::try_new(vec![
2814+
hash_partitioned_aggregate_exec(parquet_exec(), "a", "a1")?,
2815+
hash_partitioned_aggregate_exec(parquet_exec(), "a", "a1")?,
2816+
])?);
2817+
2818+
let test_config = TestConfig::default();
2819+
let plan_distrib = test_config.to_plan(plan.clone(), &DISTRIB_DISTRIB_SORT);
2820+
assert_plan!(plan_distrib,
2821+
@r"
2822+
InterleaveExec
2823+
AggregateExec: mode=FinalPartitioned, gby=[a1@0 as a1], aggr=[]
2824+
RepartitionExec: partitioning=Hash([a1@0], 10), input_partitions=10
2825+
AggregateExec: mode=Partial, gby=[a@0 as a1], aggr=[]
2826+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=1
2827+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2828+
AggregateExec: mode=FinalPartitioned, gby=[a1@0 as a1], aggr=[]
2829+
RepartitionExec: partitioning=Hash([a1@0], 10), input_partitions=10
2830+
AggregateExec: mode=Partial, gby=[a@0 as a1], aggr=[]
2831+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=1
2832+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2833+
");
2834+
let plan_sort = test_config.to_plan(plan.clone(), &SORT_DISTRIB_DISTRIB);
2835+
assert_plan!(plan_distrib, plan_sort);
2836+
2837+
// Interleaves are re-derived from unions, so with `prefer_existing_union`
2838+
// the rule keeps the union it normalized the input interleave to.
2839+
let test_config = TestConfig::default().with_prefer_existing_union();
2840+
let plan_prefer_union = test_config.to_plan(plan, &DISTRIB_DISTRIB_SORT);
2841+
assert_plan!(plan_prefer_union,
2842+
@r"
2843+
UnionExec
2844+
AggregateExec: mode=FinalPartitioned, gby=[a1@0 as a1], aggr=[]
2845+
RepartitionExec: partitioning=Hash([a1@0], 10), input_partitions=10
2846+
AggregateExec: mode=Partial, gby=[a@0 as a1], aggr=[]
2847+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=1
2848+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2849+
AggregateExec: mode=FinalPartitioned, gby=[a1@0 as a1], aggr=[]
2850+
RepartitionExec: partitioning=Hash([a1@0], 10), input_partitions=10
2851+
AggregateExec: mode=Partial, gby=[a@0 as a1], aggr=[]
2852+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=1
2853+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2854+
");
2855+
2856+
Ok(())
2857+
}
2858+
26972859
#[test]
26982860
fn added_repartition_to_single_partition() -> Result<()> {
26992861
let alias = vec![("a".to_string(), "a".to_string())];

‎datafusion/physical-optimizer/src/ensure_requirements/enforce_distribution.rs‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -662,6 +662,37 @@ fn new_join_conditions(
662662
.collect()
663663
}
664664

665+
/// Turns an [`InterleaveExec`] back into the equivalent [`UnionExec`], for
666+
/// use with `transform_down` before distribution is (re-)enforced.
667+
///
668+
/// An interleave carries no distribution requirement of its own; it exists
669+
/// only because its children happened to share a hash (or range)
670+
/// partitioning when [`ensure_distribution`] created it from a union. Later
671+
/// rewrites can take that partitioning away: this rule removes
672+
/// `RepartitionExec`s nothing requires, join-key reordering changes hash
673+
/// expressions, join side swaps change output partitioning, and so on.
674+
/// `PlanContext` rebuilds every parent from its updated children while
675+
/// walking the tree, and rebuilding an interleave over children that are no
676+
/// longer interleavable fails (see
677+
/// <https://github.com/apache/datafusion/issues/21826>).
678+
///
679+
/// So, like the other distribution artifacts this rule strips and re-inserts,
680+
/// interleaves are normalized to unions up front and re-derived by
681+
/// [`ensure_distribution`] where the children still qualify.
682+
///
683+
/// This must run top-down: demoting a nested interleave first would change
684+
/// its output partitioning and make its parent interleave fail to rebuild.
685+
pub fn replace_interleave_with_union(
686+
plan: Arc<dyn ExecutionPlan>,
687+
) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
688+
match plan.downcast_ref::<InterleaveExec>() {
689+
Some(interleave) => {
690+
UnionExec::try_new(interleave.inputs().clone()).map(Transformed::yes)
691+
}
692+
None => Ok(Transformed::no(plan)),
693+
}
694+
}
695+
665696
/// Adds RoundRobin repartition operator to the plan increase parallelism.
666697
///
667698
/// # Arguments
@@ -1708,6 +1739,10 @@ pub fn ensure_distribution(
17081739
// - Agg:
17091740
// Repartition (hash):
17101741
// Data
1742+
//
1743+
// An [`InterleaveExec`] present in the input was already turned back
1744+
// into a [`UnionExec`] by [`replace_interleave_with_union`], so it is
1745+
// re-derived here from the children's actual partitioning.
17111746
Arc::new(InterleaveExec::try_new(children_plans)?)
17121747
} else {
17131748
// Route through `replace_children_if_necessary` so the common

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,8 @@
4242
//! ```text
4343
//! EnsureRequirements::optimize(plan)
4444
//! │
45+
//! ├─ Phase 0: top-down Interleave → Union (replace_interleave_with_union)
46+
//! │
4547
//! ├─ Phase 1: top-down join-key reorder (adjust_input_keys_ordering)
4648
//! │
4749
//! ├─ Phase 2: combined distribution + sorting (single bottom-up pass)
@@ -178,6 +180,13 @@ impl PhysicalOptimizerRule for EnsureRequirements {
178180
plan: Arc<dyn ExecutionPlan>,
179181
config: &ConfigOptions,
180182
) -> Result<Arc<dyn ExecutionPlan>> {
183+
// Phase 0: Normalize `InterleaveExec` back to `UnionExec` (top-down).
184+
// Interleaves are distribution artifacts of Phase 2, which re-derives
185+
// them from the children's final partitioning. Keeping them would
186+
// fail as soon as a child loses the partitioning they depend on.
187+
use super::enforce_distribution::replace_interleave_with_union;
188+
let plan = plan.transform_down(replace_interleave_with_union).data()?;
189+
181190
// Phase 1: Join key reordering (top-down, from EnforceDistribution)
182191
use super::enforce_distribution::{
183192
PlanWithKeyRequirements, adjust_input_keys_ordering,

0 commit comments

Comments
 (0)