Skip to main content

query/optimizer/
parallelize_scan.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::sync::Arc;
16
17use common_telemetry::debug;
18use datafusion::config::ConfigOptions;
19use datafusion::physical_optimizer::PhysicalOptimizerRule;
20use datafusion::physical_plan::ExecutionPlan;
21use datafusion::physical_plan::sorts::sort::SortExec;
22use datafusion_common::tree_node::{Transformed, TreeNode};
23use datafusion_common::{DataFusionError, Result};
24use table::table::scan::RegionScanExec;
25
26pub use table::table::scan::assign_partition_ranges;
27
28#[derive(Debug)]
29pub struct ParallelizeScan;
30
31impl PhysicalOptimizerRule for ParallelizeScan {
32    fn optimize(
33        &self,
34        plan: Arc<dyn ExecutionPlan>,
35        config: &ConfigOptions,
36    ) -> Result<Arc<dyn ExecutionPlan>> {
37        Self::do_optimize(plan, config)
38    }
39
40    fn name(&self) -> &str {
41        "parallelize_scan"
42    }
43
44    fn schema_check(&self) -> bool {
45        true
46    }
47}
48
49impl ParallelizeScan {
50    fn do_optimize(
51        plan: Arc<dyn ExecutionPlan>,
52        config: &ConfigOptions,
53    ) -> Result<Arc<dyn ExecutionPlan>> {
54        let mut first_order_expr = None;
55
56        let result = plan
57            .transform_down(|plan| {
58                if let Some(sort_exec) = plan.downcast_ref::<SortExec>() {
59                    // save the first order expr
60                    first_order_expr = Some(sort_exec.expr().first()).cloned();
61                } else if let Some(region_scan_exec) = plan.downcast_ref::<RegionScanExec>() {
62                    let expected_partition_num = config.execution.target_partitions;
63                    if region_scan_exec.is_partition_set()
64                        || region_scan_exec.scanner_type().as_str() == "SinglePartition"
65                    {
66                        return Ok(Transformed::no(plan));
67                    }
68
69                    let ranges = region_scan_exec.get_partition_ranges();
70                    let total_range_num = ranges.len();
71
72                    // assign ranges to each partition
73                    let mut partition_ranges =
74                        assign_partition_ranges(ranges, expected_partition_num);
75                    debug!(
76                        "Assign {total_range_num} ranges to {expected_partition_num} partitions"
77                    );
78
79                    // Sort the ranges in each partition based on the order expr
80                    //
81                    // This optimistically assumes that the first order expr is on the time index column
82                    // to skip the validation of the order expr. As it's not harmful if this condition
83                    // is not met.
84                    if let Some(order_expr) = &first_order_expr
85                        && order_expr.options.descending
86                    {
87                        for ranges in partition_ranges.iter_mut() {
88                            // Primary: end descending (larger end first)
89                            // Secondary: start descending (shorter range first when ends are equal)
90                            ranges.sort_by(|a, b| {
91                                b.end.cmp(&a.end).then_with(|| b.start.cmp(&a.start))
92                            });
93                        }
94                    } else {
95                        for ranges in partition_ranges.iter_mut() {
96                            // Primary: start ascending (smaller start first)
97                            // Secondary: end ascending (shorter range first when starts are equal)
98                            ranges.sort_by(|a, b| {
99                                a.start.cmp(&b.start).then_with(|| a.end.cmp(&b.end))
100                            });
101                        }
102                    }
103
104                    // update the partition ranges
105                    let new_exec = region_scan_exec
106                        .with_new_partitions(partition_ranges, expected_partition_num)
107                        .map_err(|e| DataFusionError::External(e.into_inner()))?;
108                    return Ok(Transformed::yes(Arc::new(new_exec)));
109                }
110
111                // The plan might be modified, but it's modified in-place so we always return
112                // Transformed::no(plan) to indicate there is no "new child"
113                Ok(Transformed::no(plan))
114            })?
115            .data;
116
117        Ok(result)
118    }
119}
120
121#[cfg(test)]
122mod test {
123    use common_time::Timestamp;
124    use common_time::timestamp::TimeUnit;
125    use store_api::region_engine::PartitionRange;
126
127    use super::assign_partition_ranges;
128
129    #[test]
130    fn test_assign_unbalance_partition_range() {
131        let ranges = vec![
132            PartitionRange {
133                start: Timestamp::new(0, TimeUnit::Second),
134                end: Timestamp::new(10, TimeUnit::Second),
135                num_rows: 100,
136                identifier: 1,
137            },
138            PartitionRange {
139                start: Timestamp::new(10, TimeUnit::Second),
140                end: Timestamp::new(20, TimeUnit::Second),
141                num_rows: 200,
142                identifier: 2,
143            },
144            PartitionRange {
145                start: Timestamp::new(20, TimeUnit::Second),
146                end: Timestamp::new(30, TimeUnit::Second),
147                num_rows: 150,
148                identifier: 3,
149            },
150            PartitionRange {
151                start: Timestamp::new(30, TimeUnit::Second),
152                end: Timestamp::new(40, TimeUnit::Second),
153                num_rows: 2500,
154                identifier: 4,
155            },
156        ];
157
158        // assign to 2 partitions
159        let expected_partition_num = 2;
160        let result = assign_partition_ranges(ranges.clone(), expected_partition_num);
161        let expected = vec![
162            vec![PartitionRange {
163                start: Timestamp::new(30, TimeUnit::Second),
164                end: Timestamp::new(40, TimeUnit::Second),
165                num_rows: 2500,
166                identifier: 4,
167            }],
168            vec![
169                PartitionRange {
170                    start: Timestamp::new(10, TimeUnit::Second),
171                    end: Timestamp::new(20, TimeUnit::Second),
172                    num_rows: 200,
173                    identifier: 2,
174                },
175                PartitionRange {
176                    start: Timestamp::new(20, TimeUnit::Second),
177                    end: Timestamp::new(30, TimeUnit::Second),
178                    num_rows: 150,
179                    identifier: 3,
180                },
181                PartitionRange {
182                    start: Timestamp::new(0, TimeUnit::Second),
183                    end: Timestamp::new(10, TimeUnit::Second),
184                    num_rows: 100,
185                    identifier: 1,
186                },
187            ],
188        ];
189        assert_eq!(result, expected);
190    }
191}