Skip to main content

partition/
splitter.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::collections::HashMap;
16use std::sync::Arc;
17
18use api::helper;
19use api::v1::{ColumnSchema, Row, Rows};
20use datatypes::arrow::array::ArrayRef;
21use datatypes::arrow::datatypes::{Field, Schema};
22use datatypes::arrow::record_batch::{RecordBatch, RecordBatchOptions};
23use datatypes::data_type::{ConcreteDataType, DataType};
24use datatypes::value::Value;
25use snafu::{OptionExt, ResultExt};
26use store_api::metric_engine_consts::DATA_SCHEMA_TABLE_ID_COLUMN_NAME;
27use store_api::storage::RegionNumber;
28
29use crate::PartitionRuleRef;
30use crate::error::{self, Result};
31use crate::partition::PartitionEvalContext;
32
33pub struct RowSplitter {
34    partition_rule: PartitionRuleRef,
35}
36
37impl RowSplitter {
38    pub fn new(partition_rule: PartitionRuleRef) -> Self {
39        Self { partition_rule }
40    }
41
42    pub fn split(&self, rows: Rows) -> Result<HashMap<RegionNumber, Rows>> {
43        // No data
44        if rows.rows.is_empty() {
45            return Ok(HashMap::new());
46        }
47
48        // No partition
49        let partition_columns = self.partition_rule.partition_columns();
50        if partition_columns.is_empty() {
51            return Ok(HashMap::from([(0, rows)]));
52        }
53
54        let splitter = SplitReadRowHelper::new(rows, &self.partition_rule);
55        splitter.split_rows()
56    }
57}
58
59struct SplitReadRowHelper<'a> {
60    schema: Vec<ColumnSchema>,
61    rows: Vec<Row>,
62    partition_rule: &'a PartitionRuleRef,
63    // Map from partition column name to index in the schema/row.
64    partition_cols_indexes: Vec<Option<usize>>,
65}
66
67impl<'a> SplitReadRowHelper<'a> {
68    fn new(rows: Rows, partition_rule: &'a PartitionRuleRef) -> Self {
69        let col_name_to_idx = rows
70            .schema
71            .iter()
72            .enumerate()
73            .map(|(idx, col)| (&col.column_name, idx))
74            .collect::<HashMap<_, _>>();
75        let partition_cols = partition_rule.partition_columns();
76        let partition_cols_indexes = partition_cols
77            .iter()
78            .map(|col_name| col_name_to_idx.get(&col_name).cloned())
79            .collect::<Vec<_>>();
80
81        Self {
82            schema: rows.schema,
83            rows: rows.rows,
84            partition_rule,
85            partition_cols_indexes,
86        }
87    }
88
89    fn split_rows(mut self) -> Result<HashMap<RegionNumber, Rows>> {
90        let regions = self.split_to_regions()?;
91        if regions.len() == 1
92            && let Some((&region, indices)) = regions.iter().next()
93            && indices.len() == self.rows.len()
94        {
95            return Ok(HashMap::from([(
96                region,
97                Rows {
98                    schema: self.schema,
99                    rows: self.rows,
100                },
101            )]));
102        }
103        let request_splits = regions
104            .into_iter()
105            .map(|(region_number, row_indexes)| {
106                let rows = row_indexes
107                    .into_iter()
108                    .map(|row_idx| std::mem::take(&mut self.rows[row_idx]))
109                    .collect();
110                let rows = Rows {
111                    schema: self.schema.clone(),
112                    rows,
113                };
114                (region_number, rows)
115            })
116            .collect::<HashMap<_, _>>();
117
118        Ok(request_splits)
119    }
120
121    fn split_to_regions(&self) -> Result<HashMap<RegionNumber, Vec<usize>>> {
122        match self.partition_rule.eval_context() {
123            PartitionEvalContext::FromPayload => self.split_rows_from_payload(),
124            PartitionEvalContext::WithTableId { .. } => self.split_rows_with_context(),
125        }
126    }
127
128    /// Routes payload values row by row without materializing Arrow arrays.
129    fn split_rows_from_payload(&self) -> Result<HashMap<RegionNumber, Vec<usize>>> {
130        let mut regions_row_indexes: HashMap<RegionNumber, Vec<usize>> = HashMap::new();
131        for (row_idx, values) in self.iter_partition_values().enumerate() {
132            let region_number = self.partition_rule.find_region(&values)?;
133            regions_row_indexes
134                .entry(region_number)
135                .or_default()
136                .push(row_idx);
137        }
138
139        Ok(regions_row_indexes)
140    }
141
142    /// Routes complete expressions through the batch evaluator with contextual inputs.
143    fn split_rows_with_context(&self) -> Result<HashMap<RegionNumber, Vec<usize>>> {
144        let batch = self.build_routing_batch()?;
145        Ok(self
146            .partition_rule
147            .split_record_batch(&batch)?
148            .into_iter()
149            .filter(|(_, mask)| !mask.select_none())
150            .map(|(region, mask)| (region, mask.array().values().set_indices().collect()))
151            .collect())
152    }
153
154    /// Converts present payload partition columns; the evaluator supplies missing inputs.
155    fn build_routing_batch(&self) -> Result<RecordBatch> {
156        let mut fields = Vec::new();
157        let mut arrays = Vec::new();
158        for (name, index) in self
159            .partition_rule
160            .partition_columns()
161            .iter()
162            .zip(&self.partition_cols_indexes)
163        {
164            if name == DATA_SCHEMA_TABLE_ID_COLUMN_NAME {
165                continue;
166            }
167            let Some(index) = *index else {
168                continue;
169            };
170            let array = self.build_partition_column_array(index)?;
171            fields.push(Field::new(name, array.data_type().clone(), true));
172            arrays.push(array);
173        }
174        RecordBatch::try_new_with_options(
175            Arc::new(Schema::new(fields)),
176            arrays,
177            &RecordBatchOptions::new().with_row_count(Some(self.rows.len())),
178        )
179        .context(error::ComputeArrowKernelSnafu)
180    }
181
182    /// Converts one payload partition column, validating its type and row values.
183    fn build_partition_column_array(&self, index: usize) -> Result<ArrayRef> {
184        let column = &self.schema[index];
185        let data_type = helper::ColumnDataTypeWrapper::try_new(
186            column.datatype,
187            column.datatype_extension.clone(),
188        )
189        .map_err(|err| {
190            error::InvalidPartitionInputSnafu {
191                reason: err.to_string(),
192            }
193            .build()
194        })?;
195        let mut builder = ConcreteDataType::from(data_type).create_mutable_vector(self.rows.len());
196        for row in &self.rows {
197            let value =
198                row.values
199                    .get(index)
200                    .with_context(|| error::InvalidPartitionInputSnafu {
201                        reason: format!(
202                            "Missing value for partition column {}",
203                            column.column_name
204                        ),
205                    })?;
206            builder
207                .try_push_value_ref(&helper::pb_value_to_value_ref(
208                    value,
209                    column.datatype_extension.as_ref(),
210                ))
211                .context(error::ConvertToVectorSnafu)?;
212        }
213        Ok(builder.to_vector().to_arrow_array())
214    }
215
216    fn iter_partition_values(&'a self) -> impl Iterator<Item = Vec<Value>> + 'a {
217        self.rows.iter().map(|row| {
218            self.partition_cols_indexes
219                .iter()
220                .map(|idx| {
221                    idx.as_ref().map_or(Value::Null, |idx| {
222                        helper::pb_value_to_value_ref(
223                            &row.values[*idx],
224                            self.schema[*idx].datatype_extension.as_ref(),
225                        )
226                        .into()
227                    })
228                })
229                .collect()
230        })
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use std::any::Any;
237    use std::sync::Arc;
238
239    use api::v1::ColumnDataType;
240    use api::v1::helper::{field_column_schema, tag_column_schema};
241    use api::v1::value::ValueData;
242    use serde::{Deserialize, Serialize};
243
244    use super::*;
245    use crate::PartitionRule;
246    use crate::partition::RegionMask;
247
248    fn mock_rows() -> Rows {
249        let schema = vec![
250            tag_column_schema("id", ColumnDataType::String),
251            tag_column_schema("name", ColumnDataType::String),
252            field_column_schema("age", ColumnDataType::Uint32),
253        ];
254        let rows = vec![
255            Row {
256                values: vec![
257                    ValueData::StringValue("1".to_string()).into(),
258                    ValueData::StringValue("Smith".to_string()).into(),
259                    ValueData::U32Value(20).into(),
260                ],
261            },
262            Row {
263                values: vec![
264                    ValueData::StringValue("2".to_string()).into(),
265                    ValueData::StringValue("Johnson".to_string()).into(),
266                    ValueData::U32Value(21).into(),
267                ],
268            },
269            Row {
270                values: vec![
271                    ValueData::StringValue("3".to_string()).into(),
272                    ValueData::StringValue("Williams".to_string()).into(),
273                    ValueData::U32Value(22).into(),
274                ],
275            },
276        ];
277        Rows { schema, rows }
278    }
279
280    #[derive(Debug, Serialize, Deserialize)]
281    struct MockPartitionRule {
282        partition_columns: Vec<String>,
283    }
284
285    impl Default for MockPartitionRule {
286        fn default() -> Self {
287            Self {
288                partition_columns: vec!["id".to_string()],
289            }
290        }
291    }
292
293    impl PartitionRule for MockPartitionRule {
294        fn as_any(&self) -> &dyn Any {
295            self
296        }
297
298        fn partition_columns(&self) -> &[String] {
299            &self.partition_columns
300        }
301
302        fn find_region(&self, values: &[Value]) -> Result<RegionNumber> {
303            let val = values.first().unwrap().clone();
304            let val = match val {
305                Value::String(v) => v.as_utf8().to_string(),
306                _ => unreachable!(),
307            };
308
309            Ok(val.parse::<u32>().unwrap() % 2)
310        }
311
312        fn split_record_batch(
313            &self,
314            _record_batch: &datatypes::arrow::array::RecordBatch,
315        ) -> Result<HashMap<RegionNumber, RegionMask>> {
316            unimplemented!()
317        }
318    }
319
320    #[derive(Debug, Serialize, Deserialize)]
321    struct MockMissedColPartitionRule {
322        partition_columns: Vec<String>,
323    }
324
325    impl Default for MockMissedColPartitionRule {
326        fn default() -> Self {
327            Self {
328                partition_columns: vec!["missed_col".to_string()],
329            }
330        }
331    }
332
333    impl PartitionRule for MockMissedColPartitionRule {
334        fn as_any(&self) -> &dyn Any {
335            self
336        }
337
338        fn partition_columns(&self) -> &[String] {
339            &self.partition_columns
340        }
341
342        fn find_region(&self, values: &[Value]) -> Result<RegionNumber> {
343            let val = values.first().unwrap().clone();
344            let val = match val {
345                Value::Null => 1,
346                _ => 0,
347            };
348
349            Ok(val)
350        }
351
352        fn split_record_batch(
353            &self,
354            _record_batch: &datatypes::arrow::array::RecordBatch,
355        ) -> Result<HashMap<RegionNumber, RegionMask>> {
356            unimplemented!()
357        }
358    }
359
360    #[derive(Debug, Serialize, Deserialize)]
361    struct EmptyPartitionRule;
362
363    impl PartitionRule for EmptyPartitionRule {
364        fn as_any(&self) -> &dyn Any {
365            self
366        }
367
368        fn partition_columns(&self) -> &[String] {
369            &[]
370        }
371
372        fn find_region(&self, _values: &[Value]) -> Result<RegionNumber> {
373            Ok(0)
374        }
375
376        fn split_record_batch(
377            &self,
378            _record_batch: &datatypes::arrow::array::RecordBatch,
379        ) -> Result<HashMap<RegionNumber, RegionMask>> {
380            unimplemented!()
381        }
382    }
383
384    #[test]
385    fn test_invalid_logical_partition_input() {
386        use common_error::ext::ErrorExt;
387        use common_error::status_code::StatusCode;
388
389        let rule = crate::multi_dim::MultiDimPartitionRule::try_new(
390            vec!["a".to_string()],
391            vec![0],
392            vec![crate::expr::col("a").gt_eq(Value::Int32(0))],
393            false,
394        )
395        .unwrap()
396        .with_eval_context(PartitionEvalContext::WithTableId { table_id: 1025 });
397        let splitter = RowSplitter::new(Arc::new(rule));
398        for (datatype, values) in [
399            (-1, vec![ValueData::I32Value(1).into()]),
400            (ColumnDataType::Int32 as i32, vec![]),
401        ] {
402            let mut column = tag_column_schema("a", ColumnDataType::Int32);
403            column.datatype = datatype;
404            let error = splitter
405                .split(Rows {
406                    schema: vec![column],
407                    rows: vec![api::v1::Row { values }],
408                })
409                .unwrap_err();
410            assert!(matches!(error, error::Error::InvalidPartitionInput { .. }));
411            assert_eq!(error.status_code(), StatusCode::InvalidArguments);
412        }
413    }
414
415    #[test]
416    fn test_writer_splitter() {
417        let rows = mock_rows();
418        let rule = Arc::new(MockPartitionRule::default()) as PartitionRuleRef;
419        let splitter = RowSplitter::new(rule);
420
421        let mut splits = splitter.split(rows).unwrap();
422        assert_eq!(splits.len(), 2);
423
424        let rows0 = splits.remove(&0).unwrap().rows;
425        let rows1 = splits.remove(&1).unwrap().rows;
426        assert_eq!(rows0.len(), 1);
427        assert_eq!(rows1.len(), 2);
428    }
429
430    #[test]
431    fn test_missed_col_writer_splitter() {
432        let rows = mock_rows();
433        let rule = Arc::new(MockMissedColPartitionRule::default()) as PartitionRuleRef;
434
435        let splitter = RowSplitter::new(rule);
436        let mut splits = splitter.split(rows).unwrap();
437        assert_eq!(splits.len(), 1);
438
439        let rows = splits.remove(&1).unwrap().rows;
440        assert_eq!(rows.len(), 3);
441    }
442
443    #[test]
444    fn test_empty_partition_rule_writer_splitter() {
445        let rows = mock_rows();
446        let rule = Arc::new(EmptyPartitionRule) as PartitionRuleRef;
447        let splitter = RowSplitter::new(rule);
448
449        let mut splits = splitter.split(rows).unwrap();
450        assert_eq!(splits.len(), 1);
451
452        let rows = splits.remove(&0).unwrap().rows;
453        assert_eq!(rows.len(), 3);
454    }
455}