datafusion_common/
partitioning.rs

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
18use crate::utils::compare_rows;
19use crate::{Result, ScalarValue, error::_plan_err};
20use arrow::compute::SortOptions;
21use std::cmp::Ordering;
22use 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)]
43pub struct SplitPoint {
44    values: Vec<ScalarValue>,
45}
46
47impl 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
59impl 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.
73pub 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_common/partitioning.rs

datafusion_common/
partitioning.rs
