Skip to content

Commit 6709f72

Browse files
Rich-T-kidGene Bordegaray
authored andcommitted
allow interleaveExec to support Range partioning (apache#23623)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123. --> - works towards apache#22395 - Closes apache#23455. ## Rationale for this change see apache#23455 <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. --> ## What changes are included in this PR? The goal of this PR is to allow range partitioning to propagate through `InterleaveExec`. Updated `can_interleave()` to accept `Partitioning::Range` when all children share an identical RangePartitioning (same ordering and split points), matching the existing behavior for `Partitioning::Hash`. Updated `range_partitioning.slt` to expect InterleaveExec where it previously expected UnionExec, since `can_interleave()` now accepts Partitioning::Range. <!-- There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR. --> ## Are these changes tested? yes, the `range_partioning.slt` file as well as the `union.slt` file sql logic test. This PR also includes three test. <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code If tests are not included in your PR, please explain why (for example, are they covered by existing tests)? --> ## Are there any user-facing changes? physical plans may look different now. <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. --> <!-- If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent a9de07a commit 6709f72

2 files changed

Lines changed: 273 additions & 8 deletions

File tree

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

Lines changed: 133 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -462,7 +462,10 @@ impl ExecutionPlan for UnionExec {
462462

463463
/// Combines multiple input streams by interleaving them.
464464
///
465-
/// This only works if all inputs have the same hash-partitioning.
465+
/// All inputs must share an identical [`Partitioning::Hash`] or [`Partitioning::Range`] so that
466+
/// partition `k` covers the same data across every input. Each output partition is the
467+
/// interleaving of the same-indexed partition from all inputs:
468+
/// `output[k] = input[0][k] + input[1][k] + ... + input[n-1][k]`
466469
///
467470
/// # Data Flow
468471
/// ```text
@@ -507,7 +510,7 @@ impl InterleaveExec {
507510
pub fn try_new(inputs: Vec<Arc<dyn ExecutionPlan>>) -> Result<Self> {
508511
assert_or_internal_err!(
509512
can_interleave(inputs.iter()),
510-
"Not all InterleaveExec children have a consistent hash partitioning"
513+
"Not all InterleaveExec children have a consistent hash or range partitioning"
511514
);
512515
let cache = Self::compute_properties(&inputs)?;
513516
Ok(InterleaveExec {
@@ -655,8 +658,12 @@ impl ExecutionPlan for InterleaveExec {
655658
}
656659
}
657660

658-
/// If all the input partitions have the same Hash partition spec with the first_input_partition
659-
/// The InterleaveExec is partition aware.
661+
/// Returns true if all inputs have the same [`Partitioning::Hash`] or [`Partitioning::Range`]
662+
/// spec, making them safe to interleave. Two inputs are interleave-compatible when partition
663+
/// `k` covers the identical key range or hash bucket across every input.
664+
///
665+
/// Note: compatibility is checked sequentially against the first input, so
666+
/// `InputDistributionRequirements::co_partitioned` is not needed here.
660667
///
661668
/// It might be too strict here in the case that the input partition specs are compatible but not exactly the same.
662669
/// For example one input partition has the partition spec Hash('a','b','c') and
@@ -669,7 +676,7 @@ pub fn can_interleave<T: Borrow<Arc<dyn ExecutionPlan>>>(
669676
};
670677

671678
let reference = first.borrow().output_partitioning();
672-
matches!(reference, Partitioning::Hash(_, _))
679+
matches!(reference, Partitioning::Hash(_, _) | Partitioning::Range(_))
673680
&& inputs
674681
.map(|plan| plan.borrow().output_partitioning().clone())
675682
.all(|partition| partition == *reference)
@@ -833,10 +840,13 @@ mod tests {
833840

834841
use arrow::compute::SortOptions;
835842
use arrow::datatypes::DataType;
843+
use datafusion_common::SplitPoint;
836844
use datafusion_common::stats::Precision;
837845
use datafusion_common::{ColumnStatistics, ScalarValue};
846+
use datafusion_physical_expr::RangePartitioning;
838847
use datafusion_physical_expr::equivalence::convert_to_orderings;
839848
use datafusion_physical_expr::expressions::col;
849+
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
840850

841851
// Generate a schema which consists of 7 columns (a, b, c, d, e, f, g)
842852
fn create_test_schema() -> Result<SchemaRef> {
@@ -1273,6 +1283,124 @@ mod tests {
12731283
);
12741284
}
12751285

1286+
fn make_hash_exec(
1287+
schema: &SchemaRef,
1288+
hash_cols: Vec<&str>,
1289+
buckets: usize,
1290+
) -> Result<Arc<dyn ExecutionPlan>> {
1291+
let exprs = hash_cols
1292+
.iter()
1293+
.map(|c| col(c, schema))
1294+
.collect::<Result<Vec<_>>>()?;
1295+
let base = Arc::new(TestMemoryExec::try_new(&[], Arc::clone(schema), None)?);
1296+
Ok(Arc::new(RepartitionExec::try_new(
1297+
base,
1298+
Partitioning::Hash(exprs, buckets),
1299+
)?))
1300+
}
1301+
1302+
fn make_range_exec(
1303+
schema: &SchemaRef,
1304+
split_values: Vec<i32>,
1305+
sort_options: SortOptions,
1306+
) -> Result<Arc<dyn ExecutionPlan>> {
1307+
let sort_expr =
1308+
PhysicalSortExpr::new(col(schema.field(0).name(), schema)?, sort_options);
1309+
let ordering = LexOrdering::new(vec![sort_expr]).unwrap();
1310+
let split_points = split_values
1311+
.into_iter()
1312+
.map(|v| SplitPoint::new(vec![ScalarValue::Int32(Some(v))]))
1313+
.collect();
1314+
let base = Arc::new(TestMemoryExec::try_new(&[], Arc::clone(schema), None)?);
1315+
Ok(Arc::new(RepartitionExec::try_new(
1316+
base,
1317+
Partitioning::Range(RangePartitioning::try_new(ordering, split_points)?),
1318+
)?))
1319+
}
1320+
1321+
#[test]
1322+
fn test_can_interleave_matrix() -> Result<()> {
1323+
let name_column = "name";
1324+
let age_column = "age";
1325+
let schema = Arc::new(Schema::new(vec![
1326+
Field::new(name_column, DataType::Int32, true),
1327+
Field::new(age_column, DataType::Int32, true),
1328+
]));
1329+
1330+
let ascending = SortOptions {
1331+
descending: false,
1332+
nulls_first: false,
1333+
};
1334+
struct Case {
1335+
inputs: Vec<Arc<dyn ExecutionPlan>>,
1336+
expected: bool,
1337+
label: &'static str,
1338+
}
1339+
1340+
let cases = vec![
1341+
// compatible
1342+
Case {
1343+
label: "matching hash on single column",
1344+
expected: true,
1345+
inputs: vec![
1346+
make_hash_exec(&schema, vec![name_column], 3)?,
1347+
make_hash_exec(&schema, vec![name_column], 3)?,
1348+
],
1349+
},
1350+
Case {
1351+
label: "matching hash on multiple columns",
1352+
expected: true,
1353+
inputs: vec![
1354+
make_hash_exec(&schema, vec![name_column, age_column], 3)?,
1355+
make_hash_exec(&schema, vec![name_column, age_column], 3)?,
1356+
],
1357+
},
1358+
Case {
1359+
label: "matching range same splits and order",
1360+
expected: true,
1361+
inputs: vec![
1362+
make_range_exec(&schema, vec![10, 20], ascending)?,
1363+
make_range_exec(&schema, vec![10, 20], ascending)?,
1364+
],
1365+
},
1366+
// incompatible
1367+
Case {
1368+
label: "subset range partition",
1369+
expected: false,
1370+
inputs: vec![
1371+
make_range_exec(&schema, vec![10, 20], ascending)?,
1372+
make_range_exec(&schema, vec![10, 15], ascending)?,
1373+
],
1374+
},
1375+
Case {
1376+
label: "range different split points",
1377+
expected: false,
1378+
inputs: vec![
1379+
make_range_exec(&schema, vec![10, 20], ascending)?,
1380+
make_range_exec(&schema, vec![10, 30], ascending)?,
1381+
],
1382+
},
1383+
Case {
1384+
label: "mixed range and hash",
1385+
expected: false,
1386+
inputs: vec![
1387+
make_range_exec(&schema, vec![10, 20], ascending)?,
1388+
make_hash_exec(&schema, vec![name_column], 3)?,
1389+
],
1390+
},
1391+
];
1392+
1393+
for case in cases {
1394+
assert_eq!(
1395+
can_interleave(case.inputs.iter()),
1396+
case.expected,
1397+
"{}",
1398+
case.label
1399+
);
1400+
}
1401+
Ok(())
1402+
}
1403+
12761404
#[test]
12771405
fn test_union_cardinality_effect() -> Result<()> {
12781406
let schema = create_test_schema()?;

‎datafusion/sqllogictest/test_files/range_partitioning.slt‎

Lines changed: 140 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -772,8 +772,8 @@ reset datafusion.optimizer.preserve_file_partitions;
772772

773773
##########
774774
# TEST 22: Union of Range Partitioned Inputs
775-
# Each input exposes Range partitioning on range_key. These changes do not add a
776-
# cross-child Range relationship for UNION ALL.
775+
# Each input exposes the same Range partitioning on range_key, so the optimizer
776+
# converts UnionExec to InterleaveExec to avoid redundant repartitioning.
777777
##########
778778

779779
query TT
@@ -782,7 +782,7 @@ UNION ALL
782782
SELECT range_key, value FROM range_partitioned;
783783
----
784784
physical_plan
785-
01)UnionExec
785+
01)InterleaveExec
786786
02)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
787787
03)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
788788

@@ -1193,3 +1193,140 @@ reset datafusion.explain.physical_plan_only;
11931193

11941194
statement ok
11951195
reset datafusion.optimizer.enable_window_topn;
1196+
1197+
##########
1198+
# TEST 34: Subset of Inputs Compatible Does Not Trigger InterleaveExec
1199+
# In a three-way union, two inputs share the same Range split points [10,20,30]
1200+
# while the third has a partially-overlapping but different set [15,20,30].
1201+
# can_interleave requires ALL inputs to match, so UnionExec is kept.
1202+
##########
1203+
1204+
statement ok
1205+
set datafusion.explain.physical_plan_only = true;
1206+
1207+
query TT
1208+
EXPLAIN SELECT range_key, value FROM range_partitioned
1209+
UNION ALL
1210+
SELECT range_key, value FROM range_partitioned
1211+
UNION ALL
1212+
SELECT range_key, value FROM range_partitioned_shifted;
1213+
----
1214+
physical_plan
1215+
01)UnionExec
1216+
02)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
1217+
03)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
1218+
04)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(15), (20), (30)], 4), file_type=csv, has_header=false
1219+
1220+
query II
1221+
SELECT range_key, value FROM range_partitioned
1222+
UNION ALL
1223+
SELECT range_key, value FROM range_partitioned
1224+
UNION ALL
1225+
SELECT range_key, value FROM range_partitioned_shifted
1226+
ORDER BY range_key, value;
1227+
----
1228+
1 10
1229+
1 10
1230+
1 10
1231+
5 50
1232+
5 50
1233+
5 50
1234+
10 100
1235+
10 100
1236+
10 100
1237+
15 150
1238+
15 150
1239+
15 150
1240+
20 200
1241+
20 200
1242+
20 200
1243+
25 250
1244+
25 250
1245+
25 250
1246+
30 300
1247+
30 300
1248+
30 300
1249+
35 350
1250+
35 350
1251+
35 350
1252+
1253+
##########
1254+
# TEST 35: Incompatible Range Split Points Falls Back to UnionExec
1255+
# Two range-partitioned inputs with different split points cannot be interleaved,
1256+
# so the optimizer keeps UnionExec instead of converting to InterleaveExec.
1257+
##########
1258+
1259+
statement ok
1260+
set datafusion.explain.physical_plan_only = true;
1261+
1262+
query TT
1263+
EXPLAIN SELECT range_key, value FROM range_partitioned
1264+
UNION ALL
1265+
SELECT range_key, value FROM range_partitioned_shifted;
1266+
----
1267+
physical_plan
1268+
01)UnionExec
1269+
02)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
1270+
03)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(15), (20), (30)], 4), file_type=csv, has_header=false
1271+
1272+
query II
1273+
SELECT range_key, value FROM range_partitioned
1274+
UNION ALL
1275+
SELECT range_key, value FROM range_partitioned_shifted
1276+
ORDER BY range_key, value;
1277+
----
1278+
1 10
1279+
1 10
1280+
5 50
1281+
5 50
1282+
10 100
1283+
10 100
1284+
15 150
1285+
15 150
1286+
20 200
1287+
20 200
1288+
25 250
1289+
25 250
1290+
30 300
1291+
30 300
1292+
35 350
1293+
35 350
1294+
1295+
##########
1296+
# TEST 36: InterleaveExec Propagates Range Partitioning to Aggregate
1297+
# InterleaveExec outputs the same Range partitioning as its compatible inputs,
1298+
# allowing a downstream aggregate on range_key to run SinglePartitioned without
1299+
# a Hash repartition.
1300+
##########
1301+
1302+
query TT
1303+
EXPLAIN SELECT range_key, SUM(value) FROM (
1304+
SELECT range_key, value FROM range_partitioned
1305+
UNION ALL
1306+
SELECT range_key, value FROM range_partitioned
1307+
) GROUP BY range_key;
1308+
----
1309+
physical_plan
1310+
01)AggregateExec: mode=SinglePartitioned, gby=[range_key@0 as range_key], aggr=[sum(value)]
1311+
02)--InterleaveExec
1312+
03)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
1313+
04)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
1314+
1315+
query II
1316+
SELECT range_key, SUM(value) FROM (
1317+
SELECT range_key, value FROM range_partitioned
1318+
UNION ALL
1319+
SELECT range_key, value FROM range_partitioned
1320+
) GROUP BY range_key ORDER BY range_key;
1321+
----
1322+
1 20
1323+
5 100
1324+
10 200
1325+
15 300
1326+
20 400
1327+
25 500
1328+
30 600
1329+
35 700
1330+
1331+
statement ok
1332+
reset datafusion.explain.physical_plan_only;

0 commit comments

Comments
 (0)