Skip to content

Commit e62ff41

Browse files
author
Gene Bordegaray
committed
Add logical range partitioning representation (apache#22777)
<!-- 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. --> - Closes apache#22778. - Related: apache#21992, apache#22395. - Needed by apache#22657. <!-- 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. --> Declared scan output partitioning should use logical partitioning metadata, not physical partitioning types. This adds logical range partitioning so range-partitioned sources can declare their layout at the logical layer. <!-- 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. --> - Add logical `Partitioning::Range` and `RangePartitioning`. - Move `SplitPoint` and shared split-point validation to `datafusion-common`. - Wire logical range partitioning through expression traversal, rewrites, and display. - Keep planning, logical proto, and Substrait support explicitly unsupported for now. <!-- 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)? --> Yes. Unit tests added <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. --> Yes. This adds public logical range partitioning API. No breaking API changes. <!-- If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent da286d5 commit e62ff41

11 files changed

Lines changed: 507 additions & 144 deletions

File tree

‎datafusion/common/src/lib.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@ mod dfschema;
3030
mod functional_dependencies;
3131
mod join_type;
3232
mod param_value;
33+
mod partitioning;
3334
mod schema_reference;
3435
mod table_reference;
3536
mod unnest;
@@ -92,6 +93,7 @@ pub use join_type::{JoinConstraint, JoinSide, JoinType};
9293
pub use nested_struct::cast_column;
9394
pub use null_equality::NullEquality;
9495
pub use param_value::ParamValues;
96+
pub use partitioning::{SplitPoint, validate_range_split_points};
9597
pub use scalar::{ScalarType, ScalarValue};
9698
pub use schema_reference::SchemaReference;
9799
pub use spans::{Location, Span, Spans};
Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
use crate::utils::compare_rows;
19+
use crate::{Result, ScalarValue, error::_plan_err};
20+
use arrow::compute::SortOptions;
21+
use std::cmp::Ordering;
22+
use std::fmt::{self, Display};
23+
24+
/// A boundary between adjacent range partitions.
25+
///
26+
/// A split point is a tuple with one [`ScalarValue`] per partitioning
27+
/// expression. Split points are interpreted lexicographically according to the
28+
/// ordering of the range partitioning that owns them.
29+
///
30+
/// `N` split points define `N + 1` partitions:
31+
///
32+
/// ```text
33+
/// partition 0: key < split_points[0]
34+
/// partition 1: split_points[0] <= key < split_points[1]
35+
/// ...
36+
/// partition N - 1: split_points[N - 2] <= key < split_points[N - 1]
37+
/// partition N: split_points[N - 1] <= key
38+
/// ```
39+
///
40+
/// Values equal to split point `i` belong to partition `i + 1`, so interior
41+
/// partitions are lower-inclusive and upper-exclusive.
42+
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Hash)]
43+
pub struct SplitPoint {
44+
values: Vec<ScalarValue>,
45+
}
46+
47+
impl SplitPoint {
48+
/// Creates a new split point from its tuple values.
49+
pub fn new(values: Vec<ScalarValue>) -> Self {
50+
Self { values }
51+
}
52+
53+
/// Returns the tuple values for this split point.
54+
pub fn values(&self) -> &[ScalarValue] {
55+
&self.values
56+
}
57+
}
58+
59+
impl Display for SplitPoint {
60+
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
61+
let values = self
62+
.values
63+
.iter()
64+
.map(ToString::to_string)
65+
.collect::<Vec<_>>()
66+
.join(", ");
67+
write!(f, "({values})")
68+
}
69+
}
70+
71+
/// Validates that split points match the ordering width and are strictly
72+
/// ordered according to the provided sort options.
73+
pub fn validate_range_split_points(
74+
split_points: &[SplitPoint],
75+
sort_options: &[SortOptions],
76+
) -> Result<()> {
77+
let width = sort_options.len();
78+
for (idx, split_point) in split_points.iter().enumerate() {
79+
let split_point_width = split_point.values().len();
80+
if split_point_width != width {
81+
return _plan_err!(
82+
"Range partitioning split point {idx} has width {split_point_width}, but ordering has width {width}"
83+
);
84+
}
85+
}
86+
87+
for (idx, split_points) in split_points.windows(2).enumerate() {
88+
if compare_rows(
89+
split_points[0].values(),
90+
split_points[1].values(),
91+
sort_options,
92+
)? != Ordering::Less
93+
{
94+
return _plan_err!(
95+
"Range partitioning split points must be strictly ordered: split point {idx} ({}) must be less than split point {} ({})",
96+
split_points[0],
97+
idx + 1,
98+
split_points[1]
99+
);
100+
}
101+
}
102+
103+
Ok(())
104+
}

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 61 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -98,7 +98,7 @@ use datafusion_physical_expr::aggregate::{
9898
};
9999
use datafusion_physical_expr::expressions::Literal;
100100
use datafusion_physical_expr::{
101-
LexOrdering, PhysicalSortExpr, create_physical_sort_exprs,
101+
LexOrdering, PhysicalSortExpr, RangePartitioning, create_physical_sort_exprs,
102102
};
103103
use datafusion_physical_optimizer::PhysicalOptimizerRule;
104104
use datafusion_physical_plan::empty::EmptyExec;
@@ -1260,6 +1260,22 @@ impl DefaultPhysicalPlanner {
12601260
.collect::<Result<Vec<_>>>()?;
12611261
Partitioning::Hash(runtime_expr, *n)
12621262
}
1263+
LogicalPartitioning::Range(range) => {
1264+
let sort_exprs = create_physical_sort_exprs(
1265+
range.ordering(),
1266+
input_dfschema,
1267+
execution_props,
1268+
)?;
1269+
let ordering = LexOrdering::new(sort_exprs).ok_or_else(|| {
1270+
internal_datafusion_err!(
1271+
"Range repartitioning requires non-empty ordering"
1272+
)
1273+
})?;
1274+
Partitioning::Range(RangePartitioning::try_new(
1275+
ordering,
1276+
range.split_points().to_vec(),
1277+
)?)
1278+
}
12631279
LogicalPartitioning::DistributeBy(_) => {
12641280
return not_impl_err!(
12651281
"Physical plan does not support DistributeBy partitioning"
@@ -3231,8 +3247,8 @@ mod tests {
32313247
use arrow_schema::{FieldRef, SchemaRef};
32323248
use datafusion_common::config::ConfigOptions;
32333249
use datafusion_common::{
3234-
DFSchemaRef, ScalarValue, TableReference, ToDFSchema as _, assert_batches_eq,
3235-
assert_contains,
3250+
DFSchemaRef, ScalarValue, SplitPoint, TableReference, ToDFSchema as _,
3251+
assert_batches_eq, assert_contains,
32363252
};
32373253
use datafusion_execution::TaskContext;
32383254
use datafusion_execution::runtime_env::RuntimeEnv;
@@ -3241,8 +3257,8 @@ mod tests {
32413257
use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs};
32423258
use datafusion_expr::{
32433259
Accumulator, AggregateUDF, AggregateUDFImpl, ExprFunctionExt, LogicalPlanBuilder,
3244-
Signature, TableSource, UserDefinedLogicalNodeCore, Volatility,
3245-
WindowFunctionDefinition, col, lit,
3260+
RangePartitioning, Signature, TableSource, UserDefinedLogicalNodeCore,
3261+
Volatility, WindowFunctionDefinition, col, lit,
32463262
};
32473263
use datafusion_functions_aggregate::count::{count_all, count_udaf};
32483264
use datafusion_functions_aggregate::expr_fn::sum;
@@ -3290,6 +3306,46 @@ mod tests {
32903306
Field::new(name, DataType::Int64, nullable)
32913307
}
32923308

3309+
#[tokio::test]
3310+
async fn logical_range_repartition_plans_output_partitioning() -> Result<()> {
3311+
let batch = RecordBatch::try_from_iter(vec![(
3312+
"a",
3313+
Arc::new(Int32Array::from(vec![1])) as ArrayRef,
3314+
)])?;
3315+
let table = Arc::new(MemTable::try_new(batch.schema(), vec![vec![batch]])?);
3316+
let source = Arc::new(DefaultTableSource::new(table));
3317+
let logical_plan = LogicalPlanBuilder::scan("test", source, None)?
3318+
.repartition(LogicalPartitioning::Range(RangePartitioning::try_new(
3319+
vec![col("a").sort(true, true)],
3320+
vec![SplitPoint::new(vec![ScalarValue::Int32(Some(10))])],
3321+
)?))?
3322+
.build()?;
3323+
3324+
let planner = DefaultPhysicalPlanner::default();
3325+
let physical_plan = planner
3326+
.create_initial_plan(&logical_plan, &make_session_state())
3327+
.await?;
3328+
let repartition = physical_plan
3329+
.as_ref()
3330+
.downcast_ref::<RepartitionExec>()
3331+
.ok_or_else(|| {
3332+
internal_datafusion_err!(
3333+
"expected RepartitionExec, got {}",
3334+
physical_plan.name()
3335+
)
3336+
})?;
3337+
let Partitioning::Range(range) = repartition.partitioning() else {
3338+
return internal_err!(
3339+
"expected Range target partitioning, got {:?}",
3340+
repartition.partitioning()
3341+
);
3342+
};
3343+
assert_eq!(range.partition_count(), 2);
3344+
assert_eq!(physical_plan.output_partitioning().partition_count(), 2);
3345+
3346+
Ok(())
3347+
}
3348+
32933349
#[test]
32943350
fn test_create_window_expr_unwraps_alias_with_metadata() -> Result<()> {
32953351
use std::collections::HashMap;

‎datafusion/expr/src/logical_plan/display.rs‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -515,6 +515,23 @@ impl<'a, 'b> PgJsonVisitor<'a, 'b> {
515515
"Partitioning Key": hash_expr
516516
})
517517
}
518+
Partitioning::Range(range) => {
519+
let range_expr: Vec<String> =
520+
range.ordering().iter().map(|e| format!("{e}")).collect();
521+
let split_points: Vec<String> = range
522+
.split_points()
523+
.iter()
524+
.map(|e| format!("{e}"))
525+
.collect();
526+
527+
json!({
528+
"Node Type": "Repartition",
529+
"Partitioning Scheme": "Range",
530+
"Partition Count": range.partition_count(),
531+
"Partitioning Key": range_expr,
532+
"Split Points": split_points
533+
})
534+
}
518535
Partitioning::DistributeBy(expr) => {
519536
let dist_by_expr: Vec<String> =
520537
expr.iter().map(|e| format!("{e}")).collect();

‎datafusion/expr/src/logical_plan/mod.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -41,8 +41,8 @@ pub use plan::{
4141
Aggregate, Analyze, ColumnUnnestList, DescribeTable, Distinct, DistinctOn,
4242
EmptyRelation, Explain, ExplainOption, Extension, FetchType, Filter, Join,
4343
JoinConstraint, JoinType, Limit, LogicalPlan, Partitioning, PlanType, Projection,
44-
RecursiveQuery, Repartition, SkipType, Sort, StringifiedPlan, Subquery,
45-
SubqueryAlias, TableScan, ToStringifiedPlan, Union, Unnest, Values, Window,
44+
RangePartitioning, RecursiveQuery, Repartition, SkipType, Sort, StringifiedPlan,
45+
Subquery, SubqueryAlias, TableScan, ToStringifiedPlan, Union, Unnest, Values, Window,
4646
projection_schema,
4747
};
4848
pub use statement::{

0 commit comments

Comments
 (0)