Skip to content

Commit d23321d

Browse files
author
Gene Bordegaray
authored
Add logical range partitioning representation (apache#22777)
## 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. --> - Closes apache#22778. - Related: apache#21992, apache#22395. - Needed by apache#22657. ## Rationale for this change <!-- 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. ## What changes are included in this PR? <!-- 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. ## Are these changes tested? <!-- 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 ## Are there any user-facing changes? <!-- 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 d77a02d commit d23321d

11 files changed

Lines changed: 508 additions & 145 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;
@@ -1264,6 +1264,22 @@ impl DefaultPhysicalPlanner {
12641264
.collect::<Result<Vec<_>>>()?;
12651265
Partitioning::Hash(runtime_expr, *n)
12661266
}
1267+
LogicalPartitioning::Range(range) => {
1268+
let sort_exprs = create_physical_sort_exprs(
1269+
range.ordering(),
1270+
input_dfschema,
1271+
execution_props,
1272+
)?;
1273+
let ordering = LexOrdering::new(sort_exprs).ok_or_else(|| {
1274+
internal_datafusion_err!(
1275+
"Range repartitioning requires non-empty ordering"
1276+
)
1277+
})?;
1278+
Partitioning::Range(RangePartitioning::try_new(
1279+
ordering,
1280+
range.split_points().to_vec(),
1281+
)?)
1282+
}
12671283
LogicalPartitioning::DistributeBy(_) => {
12681284
return not_impl_err!(
12691285
"Physical plan does not support DistributeBy partitioning"
@@ -3245,8 +3261,8 @@ mod tests {
32453261
use arrow_schema::{FieldRef, SchemaRef};
32463262
use datafusion_common::config::ConfigOptions;
32473263
use datafusion_common::{
3248-
DFSchemaRef, ScalarValue, TableReference, ToDFSchema as _, assert_batches_eq,
3249-
assert_contains,
3264+
DFSchemaRef, ScalarValue, SplitPoint, TableReference, ToDFSchema as _,
3265+
assert_batches_eq, assert_contains,
32503266
};
32513267
use datafusion_execution::TaskContext;
32523268
use datafusion_execution::runtime_env::RuntimeEnv;
@@ -3255,8 +3271,8 @@ mod tests {
32553271
use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs};
32563272
use datafusion_expr::{
32573273
Accumulator, AggregateUDF, AggregateUDFImpl, ExprFunctionExt, LogicalPlanBuilder,
3258-
Signature, TableSource, UserDefinedLogicalNodeCore, Volatility,
3259-
WindowFunctionDefinition, col, lit,
3274+
RangePartitioning, Signature, TableSource, UserDefinedLogicalNodeCore,
3275+
Volatility, WindowFunctionDefinition, col, lit,
32603276
};
32613277
use datafusion_functions_aggregate::count::{count_all, count_udaf};
32623278
use datafusion_functions_aggregate::expr_fn::sum;
@@ -3304,6 +3320,46 @@ mod tests {
33043320
Field::new(name, DataType::Int64, nullable)
33053321
}
33063322

3323+
#[tokio::test]
3324+
async fn logical_range_repartition_plans_output_partitioning() -> Result<()> {
3325+
let batch = RecordBatch::try_from_iter(vec![(
3326+
"a",
3327+
Arc::new(Int32Array::from(vec![1])) as ArrayRef,
3328+
)])?;
3329+
let table = Arc::new(MemTable::try_new(batch.schema(), vec![vec![batch]])?);
3330+
let source = Arc::new(DefaultTableSource::new(table));
3331+
let logical_plan = LogicalPlanBuilder::scan("test", source, None)?
3332+
.repartition(LogicalPartitioning::Range(RangePartitioning::try_new(
3333+
vec![col("a").sort(true, true)],
3334+
vec![SplitPoint::new(vec![ScalarValue::Int32(Some(10))])],
3335+
)?))?
3336+
.build()?;
3337+
3338+
let planner = DefaultPhysicalPlanner::default();
3339+
let physical_plan = planner
3340+
.create_initial_plan(&logical_plan, &make_session_state())
3341+
.await?;
3342+
let repartition = physical_plan
3343+
.as_ref()
3344+
.downcast_ref::<RepartitionExec>()
3345+
.ok_or_else(|| {
3346+
internal_datafusion_err!(
3347+
"expected RepartitionExec, got {}",
3348+
physical_plan.name()
3349+
)
3350+
})?;
3351+
let Partitioning::Range(range) = repartition.partitioning() else {
3352+
return internal_err!(
3353+
"expected Range target partitioning, got {:?}",
3354+
repartition.partitioning()
3355+
);
3356+
};
3357+
assert_eq!(range.partition_count(), 2);
3358+
assert_eq!(physical_plan.output_partitioning().partition_count(), 2);
3359+
3360+
Ok(())
3361+
}
3362+
33073363
#[test]
33083364
fn test_create_window_expr_unwraps_alias_with_metadata() -> Result<()> {
33093365
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: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -41,9 +41,9 @@ 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, TableScanBuilder, ToStringifiedPlan, Union, Unnest, Values,
46-
Window, projection_schema,
44+
RangePartitioning, RecursiveQuery, Repartition, SkipType, Sort, StringifiedPlan,
45+
Subquery, SubqueryAlias, TableScan, TableScanBuilder, ToStringifiedPlan, Union,
46+
Unnest, Values, Window, projection_schema,
4747
};
4848
pub use statement::{
4949
Deallocate, Execute, Prepare, ResetVariable, SetVariable, Statement,

0 commit comments

Comments
 (0)