Skip to content

Commit ac17a7b

Browse files
authored
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 apache#123` indicates that this PR will close issue apache#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 5063883 commit ac17a7b

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
@@ -477,7 +477,10 @@ impl ExecutionPlan for UnionExec {
477477

478478
/// Combines multiple input streams by interleaving them.
479479
///
480-
/// This only works if all inputs have the same hash-partitioning.
480+
/// All inputs must share an identical [`Partitioning::Hash`] or [`Partitioning::Range`] so that
481+
/// partition `k` covers the same data across every input. Each output partition is the
482+
/// interleaving of the same-indexed partition from all inputs:
483+
/// `output[k] = input[0][k] + input[1][k] + ... + input[n-1][k]`
481484
///
482485
/// # Data Flow
483486
/// ```text
@@ -522,7 +525,7 @@ impl InterleaveExec {
522525
pub fn try_new(inputs: Vec<Arc<dyn ExecutionPlan>>) -> Result<Self> {
523526
assert_or_internal_err!(
524527
can_interleave(inputs.iter()),
525-
"Not all InterleaveExec children have a consistent hash partitioning"
528+
"Not all InterleaveExec children have a consistent hash or range partitioning"
526529
);
527530
let cache = Self::compute_properties(&inputs)?;
528531
Ok(InterleaveExec {
@@ -682,8 +685,12 @@ impl ExecutionPlan for InterleaveExec {
682685
}
683686
}
684687

685-
/// If all the input partitions have the same Hash partition spec with the first_input_partition
686-
/// The InterleaveExec is partition aware.
688+
/// Returns true if all inputs have the same [`Partitioning::Hash`] or [`Partitioning::Range`]
689+
/// spec, making them safe to interleave. Two inputs are interleave-compatible when partition
690+
/// `k` covers the identical key range or hash bucket across every input.
691+
///
692+
/// Note: compatibility is checked sequentially against the first input, so
693+
/// `InputDistributionRequirements::co_partitioned` is not needed here.
687694
///
688695
/// It might be too strict here in the case that the input partition specs are compatible but not exactly the same.
689696
/// For example one input partition has the partition spec Hash('a','b','c') and
@@ -696,7 +703,7 @@ pub fn can_interleave<T: Borrow<Arc<dyn ExecutionPlan>>>(
696703
};
697704

698705
let reference = first.borrow().output_partitioning();
699-
matches!(reference, Partitioning::Hash(_, _))
706+
matches!(reference, Partitioning::Hash(_, _) | Partitioning::Range(_))
700707
&& inputs
701708
.map(|plan| plan.borrow().output_partitioning().clone())
702709
.all(|partition| partition == *reference)
@@ -844,10 +851,13 @@ mod tests {
844851

845852
use arrow::compute::SortOptions;
846853
use arrow::datatypes::DataType;
854+
use datafusion_common::SplitPoint;
847855
use datafusion_common::stats::Precision;
848856
use datafusion_common::{ColumnStatistics, ScalarValue};
857+
use datafusion_physical_expr::RangePartitioning;
849858
use datafusion_physical_expr::equivalence::convert_to_orderings;
850859
use datafusion_physical_expr::expressions::col;
860+
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
851861

852862
// Generate a schema which consists of 7 columns (a, b, c, d, e, f, g)
853863
fn create_test_schema() -> Result<SchemaRef> {
@@ -1288,6 +1298,124 @@ mod tests {
12881298
);
12891299
}
12901300

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

783783
##########
784784
# TEST 22: Union of Range Partitioned Inputs
785-
# Each input exposes Range partitioning on range_key. These changes do not add a
786-
# cross-child Range relationship for UNION ALL.
785+
# Each input exposes the same Range partitioning on range_key, so the optimizer
786+
# converts UnionExec to InterleaveExec to avoid redundant repartitioning.
787787
##########
788788

789789
query TT
@@ -792,7 +792,7 @@ UNION ALL
792792
SELECT range_key, value FROM range_partitioned;
793793
----
794794
physical_plan
795-
01)UnionExec
795+
01)InterleaveExec
796796
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
797797
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
798798

@@ -1203,3 +1203,140 @@ reset datafusion.explain.physical_plan_only;
12031203

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

0 commit comments

Comments
 (0)