Skip to content

Commit 13ea24a

Browse files
authored
fix: defer InterleaveExec partitioning check to InvariantLevel::Executable (apache#24963)
## Which issue does this PR close? - Closes apache#21826. Builds on apache#24959, which handled the `EnsureRequirements` side. ## Rationale for this change `InterleaveExec` is only valid while every child shares the same hash (or range) partitioning. `EnsureRequirements` creates it from a `UnionExec` when that happens to hold. Any later rule that rewrites a child and changes its output partitioning, for example `JoinSelection` swapping a join's sides, makes the optimizer's tree walk rebuild the interleave over children that no longer match. `InterleaveExec::replace_children` asserted on that, so the whole rule failed: ``` join_selection caused by Internal error: Assertion failed: can_interleave(children.iter()): Can not create InterleaveExec: new children can not be interleaved. ``` This is the chain reported in apache#21826: distribution enforcement builds the interleave, `JoinSelection` breaks it, and no rule can repair it because the failure happens inside the rebuild, before any rule's closure runs. apache#24959 made `EnsureRequirements` itself immune by normalizing interleaves back to unions before it runs, but that does not help when the rebuild happens inside another rule. The root cause is that `InterleaveExec` enforces a cross-child distribution property one level earlier than the rest of the framework does. Co-partitioning for joins is validated by `InputDistributionRequirements::check_invariants` only at `InvariantLevel::Executable`; a hash join rebuilt over children that lost their partitioning does not error at rebuild time, it becomes temporarily unsatisfied and is either repaired by a later distribution pass or rejected by `SanityCheckPlan`. This PR makes `InterleaveExec` behave the same way. This is not the fallback proposed in apache#21827. Nothing is substituted for a different node and no error is downgraded to a log. The node stays an `InterleaveExec`, the error is the same, and it is raised at the executable checkpoint instead of at rebuild time. The decision on how to recover is left to the optimizer rule, which apache#24959 already implements. ## What changes are included in this PR? In `datafusion/physical-plan/src/union.rs`: - `InterleaveExec::try_new` still asserts interleavability, so explicit construction and proto decoding keep the strict check. - A private `try_new_unchecked` builds the node without the check. `replace_children` in `Recompute` mode now uses it. - `compute_properties` only claims the shared hash / range partitioning when every child still has it, and reports `UnknownPartitioning` otherwise, so nothing downstream can rely on a layout the node does not have. - `InterleaveExec::check_invariants` runs the `can_interleave` check at `InvariantLevel::Executable`, with the same message as before. The physical planner already checks `Always` after each rule and `Executable` at the end, so an unrepaired interleave is still rejected, with the same error, by `SanityCheckPlan`. ## What is the testing strategy for this PR? - `test_interleave_rebuild_defers_partitioning_invariant` (unit test in `union.rs`): rebuilding over one round-robin child succeeds, `try_new` on the same children still fails, the node reports unknown partitioning, the `Always` check passes, and the `Executable` check fails with the original message. - `issue_21826_join_selection_after_distribution_pass` (`core/tests/physical_optimizer/enforce_distribution.rs`): the exact reported chain. A union of two partitioned hash joins with statistics chosen so `JoinSelection` swaps only one of them. On `main` this fails inside `JoinSelection` with the error above. Here `JoinSelection` completes, the interleave reports unknown partitioning, `SanityCheckPlan` rejects the unrepaired plan, and a second `EnsureRequirements` pass produces a valid union that the sanity checker accepts (snapshotted). - `interleave_broken_by_later_rewrite_is_repaired_on_next_pass`: the same mechanism where the disruption is a removable `CoalescePartitionsExec`, so the repair restores the interleave rather than demoting it, showing the optimization is not permanently lost. ## Are there any user-facing changes? No API changes. Behaviorally, an `InterleaveExec` whose children lose their shared partitioning during optimization is now reported as an invariant failure by `SanityCheckPlan` at the end of the pipeline instead of as an error from the rule that rebuilt it. The diagnostic is therefore coarser (it names the node, not the rule), which is the trade-off for letting rules complete and a later distribution pass repair the plan. Custom pipelines that run rules between two distribution passes no longer need a workaround.
1 parent c98fe99 commit 13ea24a

2 files changed

Lines changed: 274 additions & 8 deletions

File tree

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

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,8 +38,10 @@ use datafusion::datasource::physical_plan::{CsvSource, ParquetSource};
3838
use datafusion::datasource::source::DataSourceExec;
3939
use datafusion::prelude::{SessionConfig, SessionContext};
4040
use datafusion_common::ScalarValue;
41+
use datafusion_common::Statistics;
4142
use datafusion_common::config::CsvOptions;
4243
use datafusion_common::error::Result;
44+
use datafusion_common::stats::Precision;
4345
use datafusion_common::tree_node::{
4446
Transformed, TransformedResult, TreeNode, TreeNodeRecursion,
4547
};
@@ -56,7 +58,9 @@ use datafusion_physical_expr_common::sort_expr::{
5658
use datafusion_physical_optimizer::PhysicalOptimizerRule;
5759
use datafusion_physical_optimizer::enforce_distribution::*;
5860
use datafusion_physical_optimizer::ensure_requirements::EnsureRequirements;
61+
use datafusion_physical_optimizer::join_selection::JoinSelection;
5962
use datafusion_physical_optimizer::output_requirements::OutputRequirements;
63+
use datafusion_physical_optimizer::sanity_checker::SanityCheckPlan;
6064
use datafusion_physical_plan::aggregates::{
6165
AggregateExec, AggregateMode, PhysicalGroupBy,
6266
};
@@ -2856,6 +2860,142 @@ fn existing_interleave_is_kept_when_children_stay_interleavable() -> Result<()>
28562860
Ok(())
28572861
}
28582862

2863+
#[test]
2864+
fn interleave_broken_by_later_rewrite_is_repaired_on_next_pass() -> Result<()> {
2865+
// The chain reported in https://github.com/apache/datafusion/issues/21826:
2866+
// a distribution pass builds an interleave, a later rule changes one
2867+
// child's partitioning while rebuilding the tree, and another distribution
2868+
// pass runs afterwards.
2869+
let alias = vec![("a".to_string(), "a1".to_string())];
2870+
let union = union_exec(vec![
2871+
aggregate_exec_with_alias(parquet_exec(), alias.clone()),
2872+
aggregate_exec_with_alias(parquet_exec(), alias),
2873+
]);
2874+
let config = TestConfig::default().config;
2875+
let pass1 = EnsureRequirements::new().optimize(union, &config)?;
2876+
assert!(pass1.is::<InterleaveExec>());
2877+
2878+
// Stand-in for the later rewrite: one child loses its hash partitioning.
2879+
// Rebuilding the interleave over it used to fail here.
2880+
let children = pass1.children();
2881+
let coalesced: Arc<dyn ExecutionPlan> =
2882+
Arc::new(CoalescePartitionsExec::new(Arc::clone(children[1])));
2883+
let rewritten = Arc::clone(&pass1).replace_children(
2884+
vec![Arc::clone(children[0]), coalesced],
2885+
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Recompute),
2886+
)?;
2887+
assert!(matches!(
2888+
rewritten.output_partitioning(),
2889+
Partitioning::UnknownPartitioning(10)
2890+
));
2891+
// Without a repair, the plan is rejected rather than executed.
2892+
assert!(
2893+
SanityCheckPlan::new()
2894+
.optimize(Arc::clone(&rewritten), &config)
2895+
.is_err()
2896+
);
2897+
2898+
// The next distribution pass restores a valid interleave.
2899+
let pass2 = EnsureRequirements::new().optimize(rewritten, &config)?;
2900+
SanityCheckPlan::new().optimize(Arc::clone(&pass2), &config)?;
2901+
assert_plan!(pass2,
2902+
@r"
2903+
InterleaveExec
2904+
AggregateExec: mode=FinalPartitioned, gby=[a1@0 as a1], aggr=[]
2905+
RepartitionExec: partitioning=Hash([a1@0], 10), input_partitions=10
2906+
AggregateExec: mode=Partial, gby=[a@0 as a1], aggr=[]
2907+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=1
2908+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2909+
AggregateExec: mode=FinalPartitioned, gby=[a1@0 as a1], aggr=[]
2910+
RepartitionExec: partitioning=Hash([a1@0], 10), input_partitions=10
2911+
AggregateExec: mode=Partial, gby=[a@0 as a1], aggr=[]
2912+
RepartitionExec: partitioning=RoundRobinBatch(10), input_partitions=1
2913+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2914+
");
2915+
2916+
Ok(())
2917+
}
2918+
2919+
/// A single-partition parquet scan with the given (inexact) row and byte
2920+
/// statistics, so `JoinSelection` can compare build and probe sizes.
2921+
fn parquet_exec_with_size(
2922+
num_rows: usize,
2923+
total_byte_size: usize,
2924+
) -> Arc<dyn ExecutionPlan> {
2925+
let mut statistics = Statistics::new_unknown(&schema());
2926+
statistics.num_rows = Precision::Inexact(num_rows);
2927+
statistics.total_byte_size = Precision::Inexact(total_byte_size);
2928+
let config = FileScanConfigBuilder::new(
2929+
ObjectStoreUrl::parse("test:///").unwrap(),
2930+
Arc::new(ParquetSource::new(schema())),
2931+
)
2932+
.with_file(PartitionedFile::new(
2933+
"x".to_string(),
2934+
total_byte_size as u64,
2935+
))
2936+
.with_statistics(statistics)
2937+
.build();
2938+
DataSourceExec::from_data_source(config)
2939+
}
2940+
2941+
#[test]
2942+
fn issue_21826_join_selection_after_distribution_pass() -> Result<()> {
2943+
// The exact chain from https://github.com/apache/datafusion/issues/21826:
2944+
// a distribution pass turns a union of hash joins into an interleave,
2945+
// `JoinSelection` then swaps the sides of one join, which changes that
2946+
// child's output partitioning, and a second distribution pass follows.
2947+
let schema = schema();
2948+
let on: JoinOn = vec![(col("a", &schema)?, col("a", &schema)?)];
2949+
let big = || parquet_exec_with_size(100_000, 8_000_000);
2950+
let small = || parquet_exec_with_size(10, 800);
2951+
let union = union_exec(vec![
2952+
// Build side is the bigger input: JoinSelection swaps this join.
2953+
hash_join_exec(big(), small(), &on, &JoinType::Inner),
2954+
// Already the right way around: left as is.
2955+
hash_join_exec(small(), big(), &on, &JoinType::Inner),
2956+
]);
2957+
let config = TestConfig::default().config;
2958+
2959+
let pass1 = EnsureRequirements::new().optimize(union, &config)?;
2960+
assert!(pass1.is::<InterleaveExec>());
2961+
2962+
// Rebuilding the interleave over the swapped join used to fail here with
2963+
// "Can not create InterleaveExec: new children can not be interleaved".
2964+
let reordered = JoinSelection::new().optimize(pass1, &config)?;
2965+
assert!(matches!(
2966+
reordered.output_partitioning(),
2967+
Partitioning::UnknownPartitioning(10)
2968+
));
2969+
// Without a repair, the plan is rejected rather than executed.
2970+
assert!(
2971+
SanityCheckPlan::new()
2972+
.optimize(Arc::clone(&reordered), &config)
2973+
.is_err()
2974+
);
2975+
2976+
// The second distribution pass repairs it. The two joins no longer share
2977+
// a partitioning, so the result is a plain union.
2978+
let pass2 = EnsureRequirements::new().optimize(reordered, &config)?;
2979+
SanityCheckPlan::new().optimize(Arc::clone(&pass2), &config)?;
2980+
assert_plan!(pass2,
2981+
@r"
2982+
UnionExec
2983+
ProjectionExec: expr=[a@5 as a, b@6 as b, c@7 as c, d@8 as d, e@9 as e, a@0 as a, b@1 as b, c@2 as c, d@3 as d, e@4 as e]
2984+
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a@0, a@0)]
2985+
RepartitionExec: partitioning=Hash([a@0], 10), input_partitions=1
2986+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2987+
RepartitionExec: partitioning=Hash([a@0], 10), input_partitions=1
2988+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2989+
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a@0, a@0)]
2990+
RepartitionExec: partitioning=Hash([a@0], 10), input_partitions=1
2991+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2992+
RepartitionExec: partitioning=Hash([a@0], 10), input_partitions=1
2993+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
2994+
");
2995+
2996+
Ok(())
2997+
}
2998+
28592999
#[test]
28603000
fn added_repartition_to_single_partition() -> Result<()> {
28613001
let alias = vec![("a".to_string(), "a".to_string())];

‎datafusion/physical-plan/src/union.rs‎

Lines changed: 134 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -670,6 +670,23 @@ impl InterleaveExec {
670670
can_interleave(inputs.iter()),
671671
"Not all InterleaveExec children have a consistent hash or range partitioning"
672672
);
673+
Self::try_new_unchecked(inputs)
674+
}
675+
676+
/// Like [`Self::try_new`], but does not require the inputs to be
677+
/// interleavable.
678+
///
679+
/// Optimizer rules rebuild every parent from its rewritten children while
680+
/// walking the plan, so a rewrite that changes a child's partitioning
681+
/// (join side swaps, removed repartitions, ...) hands this node children
682+
/// that are no longer interleavable before any rule has had the chance to
683+
/// repair it. Such a node reports [`Partitioning::UnknownPartitioning`],
684+
/// so nothing downstream can rely on a hash layout it does not have, and
685+
/// [`ExecutionPlan::check_invariants`] rejects it at
686+
/// [`InvariantLevel::Executable`] if it is never repaired. This mirrors
687+
/// how unmet distribution requirements are handled for every other
688+
/// operator.
689+
fn try_new_unchecked(inputs: Vec<Arc<dyn ExecutionPlan>>) -> Result<Self> {
673690
let schema = union_schema(&inputs)?;
674691
let inputs = inputs
675692
.into_iter()
@@ -694,8 +711,23 @@ impl InterleaveExec {
694711
schema: SchemaRef,
695712
) -> Result<PlanProperties> {
696713
let eq_properties = EquivalenceProperties::new(schema);
697-
// Get output partitioning:
698-
let output_partitioning = inputs[0].output_partitioning().clone();
714+
// Get output partitioning. Only claim the shared hash / range layout
715+
// when every input actually has it (see `try_new_unchecked`).
716+
let output_partitioning = if can_interleave(inputs.iter()) {
717+
inputs[0].output_partitioning().clone()
718+
} else {
719+
// Non-interleavable inputs need not even agree on a partition
720+
// count. Report the largest one: `execute` errors out for a
721+
// partition that some input lacks, so an unrepaired node fails
722+
// loudly instead of silently dropping the extra partitions of
723+
// the widest input.
724+
let partition_count = inputs
725+
.iter()
726+
.map(|input| input.output_partitioning().partition_count())
727+
.max()
728+
.unwrap_or(0);
729+
Partitioning::UnknownPartitioning(partition_count)
730+
};
699731
Ok(PlanProperties::new(
700732
eq_properties,
701733
output_partitioning,
@@ -758,16 +790,25 @@ impl ExecutionPlan for InterleaveExec {
758790
..Self::clone(&*self)
759791
})),
760792
ChildrenPropertiesMode::Recompute => {
761-
// New children are no longer interleavable, which might be a bug of optimization rewrite.
762-
assert_or_internal_err!(
763-
can_interleave(children.iter()),
764-
"Can not create InterleaveExec: new children can not be interleaved"
765-
);
766-
Ok(Arc::new(InterleaveExec::try_new(children)?))
793+
// The new children may no longer be interleavable; see
794+
// `try_new_unchecked` for why this is not rejected here.
795+
Ok(Arc::new(InterleaveExec::try_new_unchecked(children)?))
767796
}
768797
}
769798
}
770799

800+
fn check_invariants(&self, check: InvariantLevel) -> Result<()> {
801+
check_default_invariants(self, check)?;
802+
803+
if matches!(check, InvariantLevel::Executable) {
804+
assert_or_internal_err!(
805+
can_interleave(self.inputs.iter()),
806+
"Not all InterleaveExec children have a consistent hash or range partitioning"
807+
);
808+
}
809+
Ok(())
810+
}
811+
771812
fn with_new_children(
772813
self: Arc<Self>,
773814
children: Vec<Arc<dyn ExecutionPlan>>,
@@ -1751,6 +1792,91 @@ mod tests {
17511792
)?))
17521793
}
17531794

1795+
#[test]
1796+
fn test_interleave_rebuild_defers_partitioning_invariant() -> Result<()> {
1797+
let schema =
1798+
Arc::new(Schema::new(vec![Field::new("name", DataType::Int32, true)]));
1799+
let hash = || make_hash_exec(&schema, vec!["name"], 3);
1800+
let interleave: Arc<dyn ExecutionPlan> =
1801+
Arc::new(InterleaveExec::try_new(vec![hash()?, hash()?])?);
1802+
assert!(matches!(
1803+
interleave.output_partitioning(),
1804+
Partitioning::Hash(_, 3)
1805+
));
1806+
1807+
// A rewrite that takes one child's hash partitioning away. The
1808+
// optimizer's tree walk rebuilds the parent from such children before
1809+
// any rule can repair it, so the rebuild itself must not fail.
1810+
let round_robin: Arc<dyn ExecutionPlan> = Arc::new(RepartitionExec::try_new(
1811+
hash()?,
1812+
Partitioning::RoundRobinBatch(3),
1813+
)?);
1814+
let rebuilt = interleave.replace_children(
1815+
vec![hash()?, round_robin],
1816+
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Recompute),
1817+
)?;
1818+
1819+
// Explicit construction still requires interleavable inputs.
1820+
let children = rebuilt.children().into_iter().cloned().collect();
1821+
assert!(InterleaveExec::try_new(children).is_err());
1822+
1823+
// The rebuilt node no longer claims a hash layout, is structurally
1824+
// sound, but is not executable until a distribution pass repairs it.
1825+
assert!(matches!(
1826+
rebuilt.output_partitioning(),
1827+
Partitioning::UnknownPartitioning(3)
1828+
));
1829+
rebuilt.check_invariants(InvariantLevel::Always)?;
1830+
let err = rebuilt
1831+
.check_invariants(InvariantLevel::Executable)
1832+
.unwrap_err()
1833+
.to_string();
1834+
assert!(
1835+
err.contains(
1836+
"Not all InterleaveExec children have a consistent hash or range partitioning"
1837+
),
1838+
"{err}"
1839+
);
1840+
Ok(())
1841+
}
1842+
1843+
#[test]
1844+
fn test_interleave_rebuild_reports_widest_partition_count() -> Result<()> {
1845+
let schema =
1846+
Arc::new(Schema::new(vec![Field::new("name", DataType::Int32, true)]));
1847+
let interleave: Arc<dyn ExecutionPlan> =
1848+
Arc::new(InterleaveExec::try_new(vec![
1849+
make_hash_exec(&schema, vec!["name"], 3)?,
1850+
make_hash_exec(&schema, vec!["name"], 3)?,
1851+
])?);
1852+
1853+
// A rewrite that leaves the children with different partition counts.
1854+
let rebuilt = interleave.replace_children(
1855+
vec![
1856+
make_hash_exec(&schema, vec!["name"], 3)?,
1857+
make_hash_exec(&schema, vec!["name"], 5)?,
1858+
],
1859+
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Recompute),
1860+
)?;
1861+
1862+
// The widest child decides the reported count, so the partitions only
1863+
// it has are still visible to callers instead of being dropped.
1864+
assert!(matches!(
1865+
rebuilt.output_partitioning(),
1866+
Partitioning::UnknownPartitioning(5)
1867+
));
1868+
// Executing one of them fails loudly rather than returning no rows.
1869+
let Err(err) = rebuilt.execute(4, Arc::new(TaskContext::default())) else {
1870+
panic!("executing a partition the narrow child lacks must fail");
1871+
};
1872+
let err = err.to_string();
1873+
assert!(
1874+
err.contains("Partition 4 not found in InterleaveExec"),
1875+
"{err}"
1876+
);
1877+
Ok(())
1878+
}
1879+
17541880
#[test]
17551881
fn test_can_interleave_matrix() -> Result<()> {
17561882
let name_column = "name";

0 commit comments

Comments
 (0)