Skip to main content

partition/
multi_dim.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::any::Any;
16use std::cmp::Ordering;
17use std::collections::hash_map::Entry;
18use std::collections::{BTreeSet, HashMap};
19use std::sync::{Arc, RwLock};
20
21use datafusion_common::tree_node::{Transformed, TreeNode};
22use datafusion_expr::{ColumnarValue, Expr};
23use datafusion_physical_expr::PhysicalExpr;
24use datatypes::arrow;
25use datatypes::arrow::array::{
26    Array, BooleanArray, BooleanBufferBuilder, NullArray, RecordBatch, UInt32Array,
27};
28use datatypes::arrow::buffer::BooleanBuffer;
29use datatypes::arrow::compute::prep_null_mask_filter;
30use datatypes::arrow::datatypes::{DataType as ArrowDataType, Field, Schema};
31use datatypes::arrow::record_batch::RecordBatchOptions;
32use datatypes::data_type::DataType as _;
33use datatypes::prelude::Value;
34use datatypes::vectors::{Helper, VectorRef};
35use serde::{Deserialize, Serialize};
36use snafu::{OptionExt, ResultExt, ensure};
37use store_api::metric_engine_consts::DATA_SCHEMA_TABLE_ID_COLUMN_NAME;
38use store_api::storage::RegionNumber;
39
40use crate::PartitionRule;
41use crate::checker::PartitionChecker;
42use crate::error::{self, Result, UndefinedColumnSnafu};
43use crate::expr::{Operand, PartitionExpr, RestrictedOp, plan_physical_expr};
44use crate::function::IcebergHash;
45use crate::partition::{PartitionEvalContext, RegionMask};
46
47/// The default region number when no partition exprs are matched.
48const DEFAULT_REGION: RegionNumber = 0;
49
50type PhysicalExprCache = Option<Arc<PhysicalPartitionExprs>>;
51
52/// Partition predicates planned for one input schema.
53#[derive(Debug)]
54struct PhysicalPartitionExprs {
55    input_schema: Arc<Schema>,
56    exprs: Vec<Arc<dyn PhysicalExpr>>,
57    /// Input indices of the columns under `iceberg_hash`. Each hash is evaluated
58    /// once per batch and appended to the input as `eval_schema` describes, and
59    /// `exprs` read the results instead of hashing per predicate.
60    hash_inputs: Vec<usize>,
61    eval_schema: Arc<Schema>,
62}
63
64/// Multi-Dimiension partition rule. RFC [here](https://github.com/GreptimeTeam/greptimedb/blob/main/docs/rfcs/2024-02-21-multi-dimension-partition-rule/rfc.md)
65///
66/// This partition rule is defined by a set of simple expressions on the partition
67/// key columns. Compare to RANGE partition, which can be considered as
68/// single-dimension rule, this will evaluate expression on each column separately.
69#[derive(Debug, Serialize, Deserialize)]
70pub struct MultiDimPartitionRule {
71    /// Allow list of which columns can be used for partitioning.
72    partition_columns: Vec<String>,
73    /// Name to index of `partition_columns`. Used for quick lookup.
74    name_to_index: HashMap<String, usize>,
75    /// Region number for each partition. This list has the same length as `exprs`
76    /// (dispiting the default region).
77    regions: Vec<RegionNumber>,
78    /// Partition expressions.
79    exprs: Vec<PartitionExpr>,
80    /// Cache of physical expressions.
81    #[serde(skip)]
82    physical_expr_cache: RwLock<PhysicalExprCache>,
83    /// Write-local routing context; not persisted. Deserialization defaults to
84    /// [`PartitionEvalContext::FromPayload`].
85    #[serde(skip)]
86    eval_context: PartitionEvalContext,
87}
88
89impl MultiDimPartitionRule {
90    /// Create a new [`MultiDimPartitionRule`].
91    ///
92    /// If `check_exprs` is true, the function will check if the expressions are valid. This is
93    /// required when constructing a new partition rule like `CREATE TABLE` or `ALTER TABLE`.
94    pub fn try_new(
95        partition_columns: Vec<String>,
96        regions: Vec<RegionNumber>,
97        exprs: Vec<PartitionExpr>,
98        check_exprs: bool,
99    ) -> Result<Self> {
100        let name_to_index = partition_columns
101            .iter()
102            .enumerate()
103            .map(|(i, name)| (name.clone(), i))
104            .collect::<HashMap<_, _>>();
105
106        let rule = Self {
107            partition_columns,
108            name_to_index,
109            regions,
110            exprs,
111            physical_expr_cache: RwLock::new(None),
112            eval_context: PartitionEvalContext::FromPayload,
113        };
114
115        if check_exprs {
116            let checker = PartitionChecker::try_new(&rule)?;
117            checker.check()?;
118        }
119
120        Ok(rule)
121    }
122
123    /// Attaches write-local table identity without changing persisted partition expressions.
124    pub(crate) fn with_eval_context(mut self, context: PartitionEvalContext) -> Self {
125        self.eval_context = context;
126        self
127    }
128
129    pub fn exprs(&self) -> &[PartitionExpr] {
130        &self.exprs
131    }
132
133    fn find_region(&self, values: &[Value]) -> Result<RegionNumber> {
134        ensure!(
135            values.len() == self.partition_columns.len(),
136            error::RegionKeysSizeSnafu {
137                expect: self.partition_columns.len(),
138                actual: values.len(),
139            }
140        );
141
142        match self.eval_context {
143            PartitionEvalContext::FromPayload => self.find_region_from_payload(values),
144            PartitionEvalContext::WithTableId { .. } => self.find_region_with_context(values),
145        }
146    }
147
148    fn evaluate_expr(&self, expr: &PartitionExpr, values: &[Value]) -> Result<bool> {
149        match (expr.lhs.as_ref(), expr.rhs.as_ref()) {
150            (Operand::Column(name), Operand::Value(r)) => {
151                let index = self
152                    .name_to_index
153                    .get(name)
154                    .context(UndefinedColumnSnafu { column: name })?;
155                let l = &values[*index];
156                Self::perform_op(l, &expr.op, r)
157            }
158            (Operand::Value(l), Operand::Column(name)) => {
159                let index = self
160                    .name_to_index
161                    .get(name)
162                    .context(UndefinedColumnSnafu { column: name })?;
163                let r = &values[*index];
164                Self::perform_op(l, &expr.op, r)
165            }
166            (Operand::IcebergHash(hash), Operand::Value(r)) => {
167                let l = self.evaluate_hash(hash, values)?;
168                Self::perform_op(&l, &expr.op, r)
169            }
170            (Operand::Value(l), Operand::IcebergHash(hash)) => {
171                let r = self.evaluate_hash(hash, values)?;
172                Self::perform_op(l, &expr.op, &r)
173            }
174            (Operand::Expr(lhs), Operand::Expr(rhs)) => {
175                let lhs = self.evaluate_expr(lhs, values)?;
176                let rhs = self.evaluate_expr(rhs, values)?;
177                match expr.op {
178                    RestrictedOp::And => Ok(lhs && rhs),
179                    RestrictedOp::Or => Ok(lhs || rhs),
180                    _ => unreachable!(),
181                }
182            }
183            _ => unreachable!(),
184        }
185    }
186
187    fn evaluate_hash(&self, hash: &IcebergHash, values: &[Value]) -> Result<Value> {
188        let column = hash.column();
189        let index = self
190            .name_to_index
191            .get(column)
192            .context(UndefinedColumnSnafu { column })?;
193        IcebergHash::evaluate_value(&values[*index])
194    }
195
196    fn perform_op(lhs: &Value, op: &RestrictedOp, rhs: &Value) -> Result<bool> {
197        let result = match op {
198            RestrictedOp::Eq => lhs.eq(rhs),
199            RestrictedOp::NotEq => lhs.ne(rhs),
200            RestrictedOp::Lt => lhs.partial_cmp(rhs) == Some(Ordering::Less),
201            RestrictedOp::LtEq => {
202                let result = lhs.partial_cmp(rhs);
203                result == Some(Ordering::Less) || result == Some(Ordering::Equal)
204            }
205            RestrictedOp::Gt => lhs.partial_cmp(rhs) == Some(Ordering::Greater),
206            RestrictedOp::GtEq => {
207                let result = lhs.partial_cmp(rhs);
208                result == Some(Ordering::Greater) || result == Some(Ordering::Equal)
209            }
210            RestrictedOp::And | RestrictedOp::Or => unreachable!(),
211        };
212
213        Ok(result)
214    }
215
216    pub fn row_at(&self, cols: &[VectorRef], index: usize, row: &mut [Value]) -> Result<()> {
217        for (col_idx, col) in cols.iter().enumerate() {
218            row[col_idx] = col.get(index);
219        }
220        Ok(())
221    }
222
223    pub fn record_batch_to_cols(&self, record_batch: &RecordBatch) -> Result<Vec<VectorRef>> {
224        self.partition_columns
225            .iter()
226            .map(|col_name| {
227                record_batch
228                    .column_by_name(col_name)
229                    .context(UndefinedColumnSnafu { column: col_name })
230                    .and_then(|array| {
231                        Helper::try_into_vector(array).context(error::ConvertToVectorSnafu)
232                    })
233            })
234            .collect::<Result<Vec<_>>>()
235    }
236
237    pub fn split_record_batch_naive(
238        &self,
239        record_batch: &RecordBatch,
240    ) -> Result<HashMap<RegionNumber, BooleanArray>> {
241        let num_rows = record_batch.num_rows();
242
243        let mut result = self
244            .regions
245            .iter()
246            .map(|region| {
247                let mut builder = BooleanBufferBuilder::new(num_rows);
248                builder.append_n(num_rows, false);
249                (*region, builder)
250            })
251            .collect::<HashMap<_, _>>();
252
253        let cols = self.record_batch_to_cols(record_batch)?;
254        let mut current_row = vec![Value::Null; self.partition_columns.len()];
255        for row_idx in 0..num_rows {
256            self.row_at(&cols, row_idx, &mut current_row)?;
257            let current_region = self.find_region(&current_row)?;
258            let region_mask = result
259                .get_mut(&current_region)
260                .unwrap_or_else(|| panic!("Region {} must be initialized", current_region));
261            region_mask.set_bit(row_idx, true);
262        }
263
264        Ok(result
265            .into_iter()
266            .map(|(region, mut mask)| (region, BooleanArray::new(mask.finish(), None)))
267            .collect())
268    }
269
270    pub fn split_record_batch(
271        &self,
272        record_batch: &RecordBatch,
273    ) -> Result<HashMap<RegionNumber, RegionMask>> {
274        let routing_batch = self.build_routing_batch(record_batch)?;
275        let record_batch = routing_batch.as_ref().unwrap_or(record_batch);
276        let num_rows = record_batch.num_rows();
277        if self.regions.len() == 1 {
278            return Ok([(
279                self.regions[0],
280                RegionMask::from(BooleanArray::from(vec![true; num_rows])),
281            )]
282            .into_iter()
283            .collect());
284        }
285        let physical_exprs = {
286            let cache_read_guard = self.physical_expr_cache.read().unwrap();
287            if let Some(cached) = cache_read_guard.as_ref()
288                && &cached.input_schema == record_batch.schema_ref()
289            {
290                cached.clone()
291            } else {
292                drop(cache_read_guard); // Release the read lock before acquiring write lock
293
294                let new_cache = Arc::new(self.plan_physical_exprs(record_batch.schema())?);
295                let mut cache_write_guard = self.physical_expr_cache.write().unwrap();
296                cache_write_guard.replace(new_cache.clone());
297                new_cache
298            }
299        };
300
301        let eval_batch;
302        let record_batch = if physical_exprs.hash_inputs.is_empty() {
303            record_batch
304        } else {
305            let mut columns = record_batch.columns().to_vec();
306            for index in &physical_exprs.hash_inputs {
307                columns.push(
308                    IcebergHash::evaluate_array(record_batch.column(*index).as_ref())
309                        .context(error::EvaluateRecordBatchSnafu)?,
310                );
311            }
312            eval_batch = RecordBatch::try_new(physical_exprs.eval_schema.clone(), columns)
313                .context(error::ComputeArrowKernelSnafu)?;
314            &eval_batch
315        };
316
317        let mut result: HashMap<u32, RegionMask> = physical_exprs
318            .exprs
319            .iter()
320            .zip(self.regions.iter())
321            .filter_map(|(expr, region_num)| {
322                let col_val = match expr
323                    .evaluate(record_batch)
324                    .context(error::EvaluateRecordBatchSnafu)
325                {
326                    Ok(array) => array,
327                    Err(e) => {
328                        return Some(Err(e));
329                    }
330                };
331                let array = match columnar_value_to_boolean_array(col_val, num_rows) {
332                    // A NULL result means the row is not in this region. Masks are merged
333                    // with non-Kleene `or` below, where a NULL would drop the row.
334                    Ok(array) if array.null_count() > 0 => prep_null_mask_filter(&array),
335                    Ok(array) => array,
336                    Err(e) => {
337                        return Some(Err(e));
338                    }
339                };
340                let selected_rows = array.true_count();
341                if selected_rows == 0 {
342                    // skip empty region in results.
343                    return None;
344                }
345                Some(Ok((*region_num, RegionMask::new(array, selected_rows))))
346            })
347            .collect::<error::Result<_>>()?;
348
349        let selected = if result.len() == 1 {
350            result.values().next().unwrap().array().clone()
351        } else {
352            let mut selected = BooleanArray::new(BooleanBuffer::new_unset(num_rows), None);
353            for region_mask in result.values() {
354                selected = arrow::compute::kernels::boolean::or(&selected, region_mask.array())
355                    .context(error::ComputeArrowKernelSnafu)?;
356            }
357            selected
358        };
359
360        // fast path: all rows are selected
361        if selected.true_count() == num_rows {
362            return Ok(result);
363        }
364
365        // find unselected rows and assign to default region
366        let unselected = arrow::compute::kernels::boolean::not(&selected)
367            .context(error::ComputeArrowKernelSnafu)?;
368        match result.entry(DEFAULT_REGION) {
369            Entry::Occupied(mut o) => {
370                // merge default region with unselected rows.
371                let default_region_mask = RegionMask::from(
372                    arrow::compute::kernels::boolean::or(o.get().array(), &unselected)
373                        .context(error::ComputeArrowKernelSnafu)?,
374                );
375                o.insert(default_region_mask);
376            }
377            Entry::Vacant(v) => {
378                // default region has no rows, simply put all unselected rows to default region.
379                v.insert(RegionMask::from(unselected));
380            }
381        }
382        Ok(result)
383    }
384
385    /// Finds a region using the supplied scalar partition values.
386    fn find_region_from_payload(&self, values: &[Value]) -> Result<RegionNumber> {
387        for (region_index, expr) in self.exprs.iter().enumerate() {
388            if self.evaluate_expr(expr, values)? {
389                return Ok(self.regions[region_index]);
390            }
391        }
392
393        // return the default region number
394        Ok(DEFAULT_REGION)
395    }
396
397    /// Evaluates one row through the same context-aware batch path as bulk writes.
398    fn find_region_with_context(&self, values: &[Value]) -> Result<RegionNumber> {
399        let mut fields = Vec::new();
400        let mut arrays = Vec::new();
401        for (name, value) in self.partition_columns.iter().zip(values) {
402            if name == DATA_SCHEMA_TABLE_ID_COLUMN_NAME {
403                continue;
404            }
405            let vector =
406                Helper::try_from_row_into_vector(std::slice::from_ref(value), &value.data_type())
407                    .context(error::ConvertToVectorSnafu)?;
408            let array = vector.to_arrow_array();
409            fields.push(Field::new(name, array.data_type().clone(), true));
410            arrays.push(array);
411        }
412        let batch = RecordBatch::try_new_with_options(
413            Arc::new(Schema::new(fields)),
414            arrays,
415            &RecordBatchOptions::new().with_row_count(Some(1)),
416        )
417        .context(error::ComputeArrowKernelSnafu)?;
418        let masks = self.split_record_batch(&batch)?;
419        masks
420            .into_iter()
421            .find(|(_, mask)| !mask.select_none())
422            .map(|(region, _)| region)
423            .context(error::UnexpectedSnafu {
424                err_msg: "No partition selected the row",
425            })
426    }
427
428    /// Supplies contextual identity and missing payload inputs for complete expressions.
429    /// Other partition columns remain in the batch, so mixed-column predicates use
430    /// the same evaluator as predicates over table id alone.
431    fn build_routing_batch(&self, record_batch: &RecordBatch) -> Result<Option<RecordBatch>> {
432        let PartitionEvalContext::WithTableId { table_id } = self.eval_context else {
433            return Ok(None);
434        };
435        let needs_inputs = self.partition_columns.iter().any(|name| {
436            name == DATA_SCHEMA_TABLE_ID_COLUMN_NAME || record_batch.column_by_name(name).is_none()
437        });
438        if !needs_inputs {
439            return Ok(None);
440        }
441
442        // Materialize only the routing input. The original write payload stays logical.
443        let mut fields = Vec::with_capacity(record_batch.num_columns() + 1);
444        let mut columns = Vec::with_capacity(record_batch.num_columns() + 1);
445        for (field, column) in record_batch
446            .schema()
447            .fields()
448            .iter()
449            .zip(record_batch.columns())
450        {
451            if field.name() != DATA_SCHEMA_TABLE_ID_COLUMN_NAME {
452                fields.push(field.clone());
453                columns.push(column.clone());
454            }
455        }
456        for name in &self.partition_columns {
457            if name == DATA_SCHEMA_TABLE_ID_COLUMN_NAME {
458                fields.push(Arc::new(Field::new(name, ArrowDataType::UInt32, false)));
459                columns.push(Arc::new(UInt32Array::from(vec![
460                    table_id;
461                    record_batch.num_rows()
462                ])));
463            } else if record_batch.column_by_name(name).is_none() {
464                // The manager validates these columns against the logical schema.
465                // Omitted payload columns retain row routing's NULL semantics.
466                fields.push(Arc::new(Field::new(name, ArrowDataType::Null, true)));
467                columns.push(Arc::new(NullArray::new(record_batch.num_rows())));
468            }
469        }
470        RecordBatch::try_new(Arc::new(Schema::new(fields)), columns)
471            .map(Some)
472            .context(error::ComputeArrowKernelSnafu)
473    }
474
475    fn plan_physical_exprs(&self, input_schema: Arc<Schema>) -> Result<PhysicalPartitionExprs> {
476        let mut hashes = BTreeSet::new();
477        for expr in &self.exprs {
478            collect_hashes(expr, &mut hashes);
479        }
480        if hashes.is_empty() {
481            let exprs = self
482                .exprs
483                .iter()
484                .map(|e| e.try_as_physical_expr(&input_schema))
485                .collect::<Result<Vec<_>>>()?;
486            return Ok(PhysicalPartitionExprs {
487                eval_schema: input_schema.clone(),
488                input_schema,
489                exprs,
490                hash_inputs: vec![],
491            });
492        }
493
494        let mut fields = input_schema.fields().to_vec();
495        let mut hash_columns = HashMap::with_capacity(hashes.len());
496        let mut hash_inputs = Vec::with_capacity(hashes.len());
497        for hash in hashes {
498            let index =
499                input_schema
500                    .index_of(hash.column())
501                    .ok()
502                    .context(UndefinedColumnSnafu {
503                        column: hash.column(),
504                    })?;
505            let mut name = format!("__partition_hash_{}", hash_inputs.len());
506            while input_schema.field_with_name(&name).is_ok() {
507                name.push('_');
508            }
509            fields.push(Arc::new(Field::new(
510                &name,
511                IcebergHash::output_type().as_arrow_type(),
512                true,
513            )));
514            hash_columns.insert(
515                hash.to_logical_expr(),
516                Expr::Column(datafusion_common::Column::from_name(name)),
517            );
518            hash_inputs.push(index);
519        }
520        let eval_schema = Arc::new(Schema::new(fields));
521
522        let exprs = self
523            .exprs
524            .iter()
525            .map(|expr| {
526                let expr = expr
527                    .try_as_logical_expr()?
528                    .transform(|expr| {
529                        Ok(match hash_columns.get(&expr) {
530                            Some(column) => Transformed::yes(column.clone()),
531                            None => Transformed::no(expr),
532                        })
533                    })
534                    .context(error::CreatePhysicalExprSnafu)?
535                    .data;
536                debug_assert!(
537                    !expr
538                        .exists(|expr| Ok(matches!(expr, Expr::ScalarFunction(_))))
539                        .unwrap(),
540                    "iceberg_hash should read the precomputed columns: {expr}"
541                );
542                plan_physical_expr(expr, &eval_schema)
543            })
544            .collect::<Result<Vec<_>>>()?;
545
546        Ok(PhysicalPartitionExprs {
547            input_schema,
548            exprs,
549            hash_inputs,
550            eval_schema,
551        })
552    }
553}
554
555fn collect_hashes(expr: &PartitionExpr, hashes: &mut BTreeSet<IcebergHash>) {
556    for operand in [expr.lhs(), expr.rhs()] {
557        match operand {
558            Operand::IcebergHash(hash) => {
559                hashes.insert(hash.clone());
560            }
561            Operand::Expr(expr) => collect_hashes(expr, hashes),
562            Operand::Column(_) | Operand::Value(_) => {}
563        }
564    }
565}
566
567fn columnar_value_to_boolean_array(
568    col_val: ColumnarValue,
569    num_rows: usize,
570) -> Result<BooleanArray> {
571    let column = col_val
572        .into_array(num_rows)
573        .context(error::EvaluateRecordBatchSnafu)?;
574    let array = column
575        .as_any()
576        .downcast_ref::<BooleanArray>()
577        .with_context(|| error::UnexpectedColumnTypeSnafu {
578            data_type: column.data_type().clone(),
579        })?;
580    Ok(array.clone())
581}
582
583impl PartitionRule for MultiDimPartitionRule {
584    fn eval_context(&self) -> PartitionEvalContext {
585        self.eval_context
586    }
587
588    fn as_any(&self) -> &dyn Any {
589        self
590    }
591
592    fn partition_columns(&self) -> &[String] {
593        &self.partition_columns
594    }
595
596    fn find_region(&self, values: &[Value]) -> Result<RegionNumber> {
597        self.find_region(values)
598    }
599
600    fn split_record_batch(
601        &self,
602        record_batch: &RecordBatch,
603    ) -> Result<HashMap<RegionNumber, RegionMask>> {
604        self.split_record_batch(record_batch)
605    }
606}
607
608#[cfg(test)]
609mod tests {
610    use std::assert_matches;
611
612    use super::*;
613    use crate::error::{self, Error};
614    use crate::expr::col;
615
616    #[test]
617    fn test_partition_eval_context() {
618        use datatypes::arrow::array::Int32Array;
619
620        use crate::splitter::RowSplitter;
621
622        let column = || col(DATA_SCHEMA_TABLE_ID_COLUMN_NAME);
623        let hash = || Operand::IcebergHash(IcebergHash::new(DATA_SCHEMA_TABLE_ID_COLUMN_NAME));
624        let hash_boundary = IcebergHash::evaluate_value(&Value::UInt32(1029)).unwrap();
625        for exprs in [
626            vec![
627                column().lt(Value::Int64(1029)),
628                column()
629                    .gt_eq(Value::UInt64(1029))
630                    .and(col("a").lt(Value::Int32(10))),
631                column()
632                    .gt_eq(Value::Int64(1029))
633                    .and(col("a").gt_eq(Value::Int32(10))),
634            ],
635            vec![
636                hash().lt(hash_boundary.clone()),
637                hash()
638                    .gt_eq(hash_boundary.clone())
639                    .and(col("a").lt(Value::Int32(10))),
640                hash()
641                    .gt_eq(hash_boundary)
642                    .and(col("a").gt_eq(Value::Int32(10))),
643            ],
644        ] {
645            let rule = MultiDimPartitionRule::try_new(
646                vec![DATA_SCHEMA_TABLE_ID_COLUMN_NAME.into(), "a".into()],
647                vec![0, 1, 2],
648                exprs,
649                false,
650            )
651            .unwrap();
652            let batch = RecordBatch::try_from_iter([
653                (
654                    DATA_SCHEMA_TABLE_ID_COLUMN_NAME,
655                    Arc::new(UInt32Array::from(vec![1029, 1029])) as arrow::array::ArrayRef,
656                ),
657                (
658                    "a",
659                    Arc::new(Int32Array::from(vec![1, 20])) as arrow::array::ArrayRef,
660                ),
661            ])
662            .unwrap();
663            let ordinary = rule.split_record_batch(&batch).unwrap();
664            let serialized = serde_json::to_string(&rule).unwrap();
665            let rule = rule.with_eval_context(PartitionEvalContext::WithTableId { table_id: 1029 });
666            assert_eq!(serde_json::to_string(&rule).unwrap(), serialized);
667            let logical = rule
668                .split_record_batch(&batch.project(&[1]).unwrap())
669                .unwrap();
670            for region in [1, 2] {
671                assert_eq!(logical[&region].array(), ordinary[&region].array());
672                assert_eq!(logical[&region].selected_rows(), 1);
673            }
674            assert_eq!(
675                rule.find_region(&[Value::Null, Value::Int32(1)]).unwrap(),
676                1
677            );
678            assert_eq!(
679                rule.find_region(&[Value::UInt32(0), Value::Int32(20)])
680                    .unwrap(),
681                2
682            );
683            let spoofed = RecordBatch::try_from_iter([
684                (
685                    DATA_SCHEMA_TABLE_ID_COLUMN_NAME,
686                    Arc::new(UInt32Array::from(vec![0, 0])) as arrow::array::ArrayRef,
687                ),
688                ("a", batch.column(1).clone()),
689            ])
690            .unwrap();
691            let masks = rule.split_record_batch(&spoofed).unwrap();
692            assert_eq!(masks[&1].array(), logical[&1].array());
693            assert_eq!(masks[&2].array(), logical[&2].array());
694            assert!(
695                rule.split_record_batch(&batch.slice(0, 0))
696                    .unwrap()
697                    .values()
698                    .all(|mask| mask.select_none())
699            );
700            let rows = api::v1::Rows {
701                schema: vec![api::v1::helper::tag_column_schema(
702                    "a",
703                    api::v1::ColumnDataType::Int32,
704                )],
705                rows: vec![
706                    api::v1::Row {
707                        values: vec![api::v1::value::ValueData::I32Value(1).into()],
708                    },
709                    api::v1::Row {
710                        values: vec![api::v1::value::ValueData::I32Value(20).into()],
711                    },
712                ],
713            };
714            let expected = rows.clone();
715            let rule = Arc::new(rule);
716            let missing = api::v1::Rows {
717                schema: vec![],
718                rows: vec![api::v1::Row { values: vec![] }],
719            };
720            let splits = RowSplitter::new(rule.clone())
721                .split(missing.clone())
722                .unwrap();
723            // Partition comparisons order NULL before non-NULL values.
724            assert_eq!(splits[&1], missing);
725            let splits = RowSplitter::new(rule).split(rows).unwrap();
726            assert_eq!(splits[&1].rows, vec![expected.rows[0].clone()]);
727            assert_eq!(splits[&2].rows, vec![expected.rows[1].clone()]);
728            assert_eq!(splits[&1].schema, expected.schema);
729        }
730    }
731
732    #[test]
733    fn test_find_region() {
734        // PARTITION ON COLUMNS (b) (
735        //     b < 'hz',
736        //     b >= 'hz' AND b < 'sh',
737        //     b >= 'sh'
738        // )
739        let rule = MultiDimPartitionRule::try_new(
740            vec!["b".to_string()],
741            vec![1, 2, 3],
742            vec![
743                PartitionExpr::new(
744                    Operand::Column("b".to_string()),
745                    RestrictedOp::Lt,
746                    Operand::Value(datatypes::value::Value::String("hz".into())),
747                ),
748                PartitionExpr::new(
749                    Operand::Expr(PartitionExpr::new(
750                        Operand::Column("b".to_string()),
751                        RestrictedOp::GtEq,
752                        Operand::Value(datatypes::value::Value::String("hz".into())),
753                    )),
754                    RestrictedOp::And,
755                    Operand::Expr(PartitionExpr::new(
756                        Operand::Column("b".to_string()),
757                        RestrictedOp::Lt,
758                        Operand::Value(datatypes::value::Value::String("sh".into())),
759                    )),
760                ),
761                PartitionExpr::new(
762                    Operand::Column("b".to_string()),
763                    RestrictedOp::GtEq,
764                    Operand::Value(datatypes::value::Value::String("sh".into())),
765                ),
766            ],
767            true,
768        )
769        .unwrap();
770        assert_matches!(
771            rule.find_region(&["foo".into(), 1000_i32.into()]),
772            Err(error::Error::RegionKeysSize {
773                expect: 1,
774                actual: 2,
775                ..
776            })
777        );
778        assert_matches!(rule.find_region(&["foo".into()]), Ok(1));
779        assert_matches!(rule.find_region(&["bar".into()]), Ok(1));
780        assert_matches!(rule.find_region(&["hz".into()]), Ok(2));
781        assert_matches!(rule.find_region(&["hzz".into()]), Ok(2));
782        assert_matches!(rule.find_region(&["sh".into()]), Ok(3));
783        assert_matches!(rule.find_region(&["zzzz".into()]), Ok(3));
784    }
785
786    #[test]
787    fn test_find_region_rejects_undeclared_column_on_lhs() {
788        let rule = MultiDimPartitionRule::try_new(
789            vec!["host".to_string()],
790            vec![1],
791            vec![PartitionExpr::new(
792                Operand::Column("rack".to_string()),
793                RestrictedOp::Lt,
794                Operand::Value(Value::String("n".into())),
795            )],
796            false,
797        )
798        .unwrap();
799
800        assert_matches!(
801            rule.find_region(&[Value::String("z".into())]),
802            Err(Error::UndefinedColumn { column, .. }) if column == "rack"
803        );
804    }
805
806    #[test]
807    fn test_find_region_rejects_undeclared_column_on_rhs() {
808        let rule = MultiDimPartitionRule::try_new(
809            vec!["host".to_string()],
810            vec![1],
811            vec![PartitionExpr::new(
812                Operand::Value(Value::String("n".into())),
813                RestrictedOp::Gt,
814                Operand::Column("rack".to_string()),
815            )],
816            false,
817        )
818        .unwrap();
819
820        assert_matches!(
821            rule.find_region(&[Value::String("z".into())]),
822            Err(Error::UndefinedColumn { column, .. }) if column == "rack"
823        );
824    }
825
826    #[test]
827    fn invalid_expr_case_1() {
828        // PARTITION ON COLUMNS (b) (
829        //     b <= b >= 'hz' AND b < 'sh',
830        // )
831        let rule = MultiDimPartitionRule::try_new(
832            vec!["a".to_string(), "b".to_string()],
833            vec![1],
834            vec![PartitionExpr::new(
835                Operand::Column("b".to_string()),
836                RestrictedOp::LtEq,
837                Operand::Expr(PartitionExpr::new(
838                    Operand::Expr(PartitionExpr::new(
839                        Operand::Column("b".to_string()),
840                        RestrictedOp::GtEq,
841                        Operand::Value(datatypes::value::Value::String("hz".into())),
842                    )),
843                    RestrictedOp::And,
844                    Operand::Expr(PartitionExpr::new(
845                        Operand::Column("b".to_string()),
846                        RestrictedOp::Lt,
847                        Operand::Value(datatypes::value::Value::String("sh".into())),
848                    )),
849                )),
850            )],
851            true,
852        );
853
854        // check rule
855        assert_matches!(rule.unwrap_err(), Error::InvalidExpr { .. });
856    }
857
858    #[test]
859    fn invalid_expr_case_2() {
860        // PARTITION ON COLUMNS (b) (
861        //     b >= 'hz' AND 'sh',
862        // )
863        let rule = MultiDimPartitionRule::try_new(
864            vec!["a".to_string(), "b".to_string()],
865            vec![1],
866            vec![PartitionExpr::new(
867                Operand::Expr(PartitionExpr::new(
868                    Operand::Column("b".to_string()),
869                    RestrictedOp::GtEq,
870                    Operand::Value(datatypes::value::Value::String("hz".into())),
871                )),
872                RestrictedOp::And,
873                Operand::Value(datatypes::value::Value::String("sh".into())),
874            )],
875            true,
876        );
877
878        // check rule
879        assert_matches!(rule.unwrap_err(), Error::InvalidExpr { .. });
880    }
881
882    /// ```ignore
883    ///          │          │
884    ///          │          │
885    /// ─────────┼──────────┼────────────► b
886    ///          │          │
887    ///          │          │
888    ///      b <= h     b >= s
889    /// ```
890    #[test]
891    fn empty_expr_case_1() {
892        // PARTITION ON COLUMNS (b) (
893        //     b <= 'h',
894        //     b >= 's'
895        // )
896        let rule = MultiDimPartitionRule::try_new(
897            vec!["a".to_string(), "b".to_string()],
898            vec![1, 2],
899            vec![
900                PartitionExpr::new(
901                    Operand::Column("b".to_string()),
902                    RestrictedOp::LtEq,
903                    Operand::Value(datatypes::value::Value::String("h".into())),
904                ),
905                PartitionExpr::new(
906                    Operand::Column("b".to_string()),
907                    RestrictedOp::GtEq,
908                    Operand::Value(datatypes::value::Value::String("s".into())),
909                ),
910            ],
911            true,
912        );
913
914        // check rule
915        assert_matches!(rule.unwrap_err(), Error::CheckpointNotCovered { .. });
916    }
917
918    /// ```
919    ///     a
920    ///     ▲
921    ///     │                   ‖
922    ///     │                   ‖
923    /// 200 │         ┌─────────┤
924    ///     │         │         │
925    ///     │         │         │
926    ///     │         │         │
927    /// 100 │   ======┴─────────┘
928    ///     │
929    ///     └──────────────────────────►b
930    ///              10          20
931    /// ```
932    #[test]
933    fn empty_expr_case_2() {
934        // PARTITION ON COLUMNS (b) (
935        //     a >= 100 AND b <= 10  OR  a > 100 AND a <= 200 AND b <= 10  OR  a >= 200 AND b > 10 AND b <= 20  OR  a > 200 AND b <= 20
936        //     a < 100 AND b <= 20  OR  a >= 100 AND b > 20
937        // )
938        let rule = MultiDimPartitionRule::try_new(
939            vec!["a".to_string(), "b".to_string()],
940            vec![1, 2],
941            vec![
942                PartitionExpr::new(
943                    Operand::Expr(PartitionExpr::new(
944                        Operand::Expr(PartitionExpr::new(
945                            //  a >= 100 AND b <= 10
946                            Operand::Expr(PartitionExpr::new(
947                                Operand::Expr(PartitionExpr::new(
948                                    Operand::Column("a".to_string()),
949                                    RestrictedOp::GtEq,
950                                    Operand::Value(datatypes::value::Value::Int64(100)),
951                                )),
952                                RestrictedOp::And,
953                                Operand::Expr(PartitionExpr::new(
954                                    Operand::Column("b".to_string()),
955                                    RestrictedOp::LtEq,
956                                    Operand::Value(datatypes::value::Value::Int64(10)),
957                                )),
958                            )),
959                            RestrictedOp::Or,
960                            // a > 100 AND a <= 200 AND b <= 10
961                            Operand::Expr(PartitionExpr::new(
962                                Operand::Expr(PartitionExpr::new(
963                                    Operand::Expr(PartitionExpr::new(
964                                        Operand::Column("a".to_string()),
965                                        RestrictedOp::Gt,
966                                        Operand::Value(datatypes::value::Value::Int64(100)),
967                                    )),
968                                    RestrictedOp::And,
969                                    Operand::Expr(PartitionExpr::new(
970                                        Operand::Column("a".to_string()),
971                                        RestrictedOp::LtEq,
972                                        Operand::Value(datatypes::value::Value::Int64(200)),
973                                    )),
974                                )),
975                                RestrictedOp::And,
976                                Operand::Expr(PartitionExpr::new(
977                                    Operand::Column("b".to_string()),
978                                    RestrictedOp::LtEq,
979                                    Operand::Value(datatypes::value::Value::Int64(10)),
980                                )),
981                            )),
982                        )),
983                        RestrictedOp::Or,
984                        // a >= 200 AND b > 10 AND b <= 20
985                        Operand::Expr(PartitionExpr::new(
986                            Operand::Expr(PartitionExpr::new(
987                                Operand::Expr(PartitionExpr::new(
988                                    Operand::Column("a".to_string()),
989                                    RestrictedOp::GtEq,
990                                    Operand::Value(datatypes::value::Value::Int64(200)),
991                                )),
992                                RestrictedOp::And,
993                                Operand::Expr(PartitionExpr::new(
994                                    Operand::Column("b".to_string()),
995                                    RestrictedOp::Gt,
996                                    Operand::Value(datatypes::value::Value::Int64(10)),
997                                )),
998                            )),
999                            RestrictedOp::And,
1000                            Operand::Expr(PartitionExpr::new(
1001                                Operand::Column("b".to_string()),
1002                                RestrictedOp::LtEq,
1003                                Operand::Value(datatypes::value::Value::Int64(20)),
1004                            )),
1005                        )),
1006                    )),
1007                    RestrictedOp::Or,
1008                    // a > 200 AND b <= 20
1009                    Operand::Expr(PartitionExpr::new(
1010                        Operand::Expr(PartitionExpr::new(
1011                            Operand::Column("a".to_string()),
1012                            RestrictedOp::Gt,
1013                            Operand::Value(datatypes::value::Value::Int64(200)),
1014                        )),
1015                        RestrictedOp::And,
1016                        Operand::Expr(PartitionExpr::new(
1017                            Operand::Column("b".to_string()),
1018                            RestrictedOp::LtEq,
1019                            Operand::Value(datatypes::value::Value::Int64(20)),
1020                        )),
1021                    )),
1022                ),
1023                PartitionExpr::new(
1024                    // a < 100 AND b <= 20
1025                    Operand::Expr(PartitionExpr::new(
1026                        Operand::Expr(PartitionExpr::new(
1027                            Operand::Column("a".to_string()),
1028                            RestrictedOp::Lt,
1029                            Operand::Value(datatypes::value::Value::Int64(100)),
1030                        )),
1031                        RestrictedOp::And,
1032                        Operand::Expr(PartitionExpr::new(
1033                            Operand::Column("b".to_string()),
1034                            RestrictedOp::LtEq,
1035                            Operand::Value(datatypes::value::Value::Int64(20)),
1036                        )),
1037                    )),
1038                    RestrictedOp::Or,
1039                    // a >= 100 AND b > 20
1040                    Operand::Expr(PartitionExpr::new(
1041                        Operand::Expr(PartitionExpr::new(
1042                            Operand::Column("a".to_string()),
1043                            RestrictedOp::GtEq,
1044                            Operand::Value(datatypes::value::Value::Int64(100)),
1045                        )),
1046                        RestrictedOp::And,
1047                        Operand::Expr(PartitionExpr::new(
1048                            Operand::Column("b".to_string()),
1049                            RestrictedOp::GtEq,
1050                            Operand::Value(datatypes::value::Value::Int64(20)),
1051                        )),
1052                    )),
1053                ),
1054            ],
1055            true,
1056        );
1057
1058        // check rule
1059        assert_matches!(rule.unwrap_err(), Error::CheckpointNotCovered { .. });
1060    }
1061
1062    #[test]
1063    fn duplicate_expr_case_1() {
1064        // PARTITION ON COLUMNS (a) (
1065        //     a <= 20,
1066        //     a >= 10
1067        // )
1068        let rule = MultiDimPartitionRule::try_new(
1069            vec!["a".to_string(), "b".to_string()],
1070            vec![1, 2],
1071            vec![
1072                PartitionExpr::new(
1073                    Operand::Column("a".to_string()),
1074                    RestrictedOp::LtEq,
1075                    Operand::Value(datatypes::value::Value::Int64(20)),
1076                ),
1077                PartitionExpr::new(
1078                    Operand::Column("a".to_string()),
1079                    RestrictedOp::GtEq,
1080                    Operand::Value(datatypes::value::Value::Int64(10)),
1081                ),
1082            ],
1083            true,
1084        );
1085
1086        // check rule
1087        assert_matches!(rule.unwrap_err(), Error::CheckpointOverlapped { .. });
1088    }
1089
1090    #[test]
1091    fn duplicate_expr_case_2() {
1092        // PARTITION ON COLUMNS (a) (
1093        //     a != 20,
1094        //     a <= 20,
1095        //     a > 20,
1096        // )
1097        let rule = MultiDimPartitionRule::try_new(
1098            vec!["a".to_string(), "b".to_string()],
1099            vec![1, 2],
1100            vec![
1101                PartitionExpr::new(
1102                    Operand::Column("a".to_string()),
1103                    RestrictedOp::NotEq,
1104                    Operand::Value(datatypes::value::Value::Int64(20)),
1105                ),
1106                PartitionExpr::new(
1107                    Operand::Column("a".to_string()),
1108                    RestrictedOp::LtEq,
1109                    Operand::Value(datatypes::value::Value::Int64(20)),
1110                ),
1111                PartitionExpr::new(
1112                    Operand::Column("a".to_string()),
1113                    RestrictedOp::Gt,
1114                    Operand::Value(datatypes::value::Value::Int64(20)),
1115                ),
1116            ],
1117            true,
1118        );
1119
1120        // check rule
1121        assert_matches!(rule.unwrap_err(), Error::CheckpointOverlapped { .. });
1122    }
1123
1124    /// ```ignore
1125    /// value
1126    ///                                 │
1127    ///                                 │
1128    ///    value=10 --------------------│
1129    ///                                 │
1130    /// ────────────────────────────────┼──► host
1131    ///                                 │
1132    ///                             host=server10
1133    /// ```
1134    #[test]
1135    fn test_partial_divided() {
1136        let _rule = MultiDimPartitionRule::try_new(
1137            vec!["host".to_string(), "value".to_string()],
1138            vec![0, 1, 2, 3],
1139            vec![
1140                col("host")
1141                    .lt(Value::String("server10".into()))
1142                    .and(col("value").lt(Value::Int64(10))),
1143                col("host")
1144                    .lt(Value::String("server10".into()))
1145                    .and(col("value").gt_eq(Value::Int64(10))),
1146                col("host").gt_eq(Value::String("server10".into())),
1147            ],
1148            true,
1149        )
1150        .unwrap();
1151    }
1152}
1153
1154#[cfg(test)]
1155mod test_split_record_batch {
1156    use std::sync::Arc;
1157
1158    use common_time::timestamp::Timestamp;
1159    use datafusion_common::ScalarValue;
1160    use datatypes::arrow::array::{Int64Array, StringArray, TimestampNanosecondArray};
1161    use datatypes::arrow::datatypes::{DataType, Field, Schema, TimeUnit};
1162    use datatypes::arrow::record_batch::RecordBatch;
1163    use rand::Rng;
1164
1165    use super::*;
1166    use crate::expr::{Operand, col};
1167
1168    fn test_schema() -> Arc<Schema> {
1169        Arc::new(Schema::new(vec![
1170            Field::new("host", DataType::Utf8, false),
1171            Field::new("value", DataType::Int64, false),
1172        ]))
1173    }
1174
1175    fn generate_random_record_batch(num_rows: usize) -> RecordBatch {
1176        let schema = test_schema();
1177        let mut rng = rand::thread_rng();
1178        let mut host_array = Vec::with_capacity(num_rows);
1179        let mut value_array = Vec::with_capacity(num_rows);
1180        for _ in 0..num_rows {
1181            host_array.push(format!("server{}", rng.gen_range(0..20)));
1182            value_array.push(rng.gen_range(0..20));
1183        }
1184        let host_array = StringArray::from(host_array);
1185        let value_array = Int64Array::from(value_array);
1186        RecordBatch::try_new(schema, vec![Arc::new(host_array), Arc::new(value_array)]).unwrap()
1187    }
1188
1189    #[test]
1190    fn test_split_record_batch_by_one_column() {
1191        // Create a simple MultiDimPartitionRule
1192        let rule = MultiDimPartitionRule::try_new(
1193            vec!["host".to_string(), "value".to_string()],
1194            vec![0, 1],
1195            vec![
1196                col("host").lt(Value::String("server1".into())),
1197                col("host").gt_eq(Value::String("server1".into())),
1198            ],
1199            true,
1200        )
1201        .unwrap();
1202
1203        let batch = generate_random_record_batch(1000);
1204        // Split the batch
1205        let result = rule.split_record_batch(&batch).unwrap();
1206        let expected = rule.split_record_batch_naive(&batch).unwrap();
1207        assert_eq!(result.len(), expected.len());
1208        for (region, value) in &result {
1209            assert_eq!(
1210                value.array(),
1211                expected.get(region).unwrap(),
1212                "failed on region: {}",
1213                region
1214            );
1215        }
1216    }
1217
1218    #[test]
1219    fn test_split_record_batch_widened_time_index_unit_with_hash() {
1220        // The precomputed-hash path must coerce millisecond bounds against a
1221        // nanosecond time index too.
1222        let bound = Value::from(Timestamp::new_millisecond(1_000));
1223        let hash = Operand::IcebergHash(IcebergHash::new("host"));
1224        let exprs = [
1225            (
1226                col("ts").lt(bound.clone()),
1227                hash.clone().lt(Value::Int32(0)),
1228            ),
1229            (
1230                col("ts").lt(bound.clone()),
1231                hash.clone().gt_eq(Value::Int32(0)),
1232            ),
1233            (
1234                col("ts").gt_eq(bound.clone()),
1235                hash.clone().lt(Value::Int32(0)),
1236            ),
1237            (col("ts").gt_eq(bound), hash.gt_eq(Value::Int32(0))),
1238        ]
1239        .into_iter()
1240        .map(|(ts, hash)| ts.and(hash))
1241        .collect();
1242        let rule = MultiDimPartitionRule::try_new(
1243            vec!["ts".to_string(), "host".to_string()],
1244            vec![1, 2, 3, 4],
1245            exprs,
1246            true,
1247        )
1248        .unwrap();
1249
1250        let hosts = ["a", "b", "c", "server42"];
1251        let mut ts = vec![];
1252        let mut host = vec![];
1253        for nanos in [500_000_000, 2_000_000_000] {
1254            for h in hosts {
1255                ts.push(nanos);
1256                host.push(h);
1257            }
1258        }
1259        let schema = Arc::new(Schema::new(vec![
1260            Field::new("ts", DataType::Timestamp(TimeUnit::Nanosecond, None), false),
1261            Field::new("host", DataType::Utf8, false),
1262        ]));
1263        let batch = RecordBatch::try_new(
1264            schema,
1265            vec![
1266                Arc::new(TimestampNanosecondArray::from(ts)),
1267                Arc::new(StringArray::from(host)),
1268            ],
1269        )
1270        .unwrap();
1271
1272        let expected = rule.split_record_batch_naive(&batch).unwrap();
1273        let result = rule.split_record_batch(&batch).unwrap();
1274        for (region, expected) in expected {
1275            let actual = result
1276                .get(&region)
1277                .map(|mask| mask.array().clone())
1278                .unwrap_or_else(|| BooleanArray::from(vec![false; batch.num_rows()]));
1279            assert_eq!(actual, expected, "region {region}");
1280        }
1281    }
1282
1283    #[test]
1284    fn test_split_record_batch_widened_time_index_unit() {
1285        // https://github.com/GreptimeTeam/greptimedb/issues/9747
1286        // The partition bounds keep the unit they were created with (millisecond)
1287        // after the time index column is widened to nanosecond, so the batch
1288        // schema and the bound values mix timestamp units.
1289        let bound = Value::from(Timestamp::new_millisecond(1_000));
1290        let rule = MultiDimPartitionRule::try_new(
1291            vec!["ts".to_string()],
1292            vec![0, 1],
1293            vec![col("ts").lt(bound.clone()), col("ts").gt_eq(bound)],
1294            true,
1295        )
1296        .unwrap();
1297
1298        let schema = Arc::new(Schema::new(vec![Field::new(
1299            "ts",
1300            DataType::Timestamp(TimeUnit::Nanosecond, None),
1301            false,
1302        )]));
1303        let batch = RecordBatch::try_new(
1304            schema,
1305            vec![Arc::new(TimestampNanosecondArray::from(vec![
1306                500_000_000,
1307                2_000_000_000,
1308            ]))],
1309        )
1310        .unwrap();
1311
1312        // 500_000_000ns < 1000ms and 2_000_000_000ns >= 1000ms: one row per region.
1313        let expected = rule.split_record_batch_naive(&batch).unwrap();
1314        assert_eq!(expected.len(), 2);
1315        let result = rule.split_record_batch(&batch).unwrap();
1316        assert_eq!(result.len(), expected.len());
1317        for (region, value) in &result {
1318            assert_eq!(value.array(), expected.get(region).unwrap());
1319        }
1320    }
1321
1322    #[test]
1323    fn test_split_record_batch_empty() {
1324        // Create a simple MultiDimPartitionRule
1325        let rule = MultiDimPartitionRule::try_new(
1326            vec!["host".to_string()],
1327            vec![1],
1328            vec![
1329                col("host").lt(Value::String("server1".into())),
1330                col("host").gt_eq(Value::String("server1".into())),
1331            ],
1332            true,
1333        )
1334        .unwrap();
1335
1336        let schema = test_schema();
1337        let host_array = StringArray::from(Vec::<&str>::new());
1338        let value_array = Int64Array::from(Vec::<i64>::new());
1339        let batch = RecordBatch::try_new(schema, vec![Arc::new(host_array), Arc::new(value_array)])
1340            .unwrap();
1341
1342        let result = rule.split_record_batch(&batch).unwrap();
1343        assert_eq!(result.len(), 1);
1344    }
1345
1346    #[test]
1347    fn test_split_record_batch_by_two_columns() {
1348        let rule = MultiDimPartitionRule::try_new(
1349            vec!["host".to_string(), "value".to_string()],
1350            vec![0, 1, 2, 3],
1351            vec![
1352                col("host")
1353                    .lt(Value::String("server10".into()))
1354                    .and(col("value").lt(Value::Int64(10))),
1355                col("host")
1356                    .lt(Value::String("server10".into()))
1357                    .and(col("value").gt_eq(Value::Int64(10))),
1358                col("host")
1359                    .gt_eq(Value::String("server10".into()))
1360                    .and(col("value").lt(Value::Int64(10))),
1361                col("host")
1362                    .gt_eq(Value::String("server10".into()))
1363                    .and(col("value").gt_eq(Value::Int64(10))),
1364            ],
1365            true,
1366        )
1367        .unwrap();
1368
1369        let batch = generate_random_record_batch(1000);
1370        let result = rule.split_record_batch(&batch).unwrap();
1371        let expected = rule.split_record_batch_naive(&batch).unwrap();
1372        assert_eq!(result.len(), expected.len());
1373        for (region, value) in &result {
1374            assert_eq!(value.array(), expected.get(region).unwrap());
1375        }
1376    }
1377
1378    #[test]
1379    fn test_all_rows_selected() {
1380        // Test the fast path where all rows are selected by some partition
1381        let rule = MultiDimPartitionRule::try_new(
1382            vec!["value".to_string()],
1383            vec![1, 2],
1384            vec![
1385                col("value").lt(Value::Int64(30)),
1386                col("value").gt_eq(Value::Int64(30)),
1387            ],
1388            true,
1389        )
1390        .unwrap();
1391
1392        let schema = test_schema();
1393        let host_array = StringArray::from(vec!["server1", "server2", "server3", "server4"]);
1394        let value_array = Int64Array::from(vec![10, 20, 30, 40]);
1395        let batch = RecordBatch::try_new(schema, vec![Arc::new(host_array), Arc::new(value_array)])
1396            .unwrap();
1397
1398        let result = rule.split_record_batch(&batch).unwrap();
1399
1400        // Check that we have 2 regions and no default region
1401        assert_eq!(result.len(), 2);
1402        assert!(result.contains_key(&1));
1403        assert!(result.contains_key(&2));
1404
1405        // Verify each region has the correct number of rows
1406        assert_eq!(result.get(&1).unwrap().selected_rows(), 2); // values < 30
1407        assert_eq!(result.get(&2).unwrap().selected_rows(), 2); // values >= 30
1408    }
1409
1410    #[test]
1411    fn test_split_record_batch_with_scalar_predicate() {
1412        // Ensure split handles conjunctive/disjunctive predicates on the same column.
1413        let rule = MultiDimPartitionRule::try_new(
1414            vec!["host".to_string()],
1415            vec![0, 1],
1416            vec![
1417                PartitionExpr::new(
1418                    Operand::Column("host".to_string()),
1419                    RestrictedOp::Lt,
1420                    Operand::Value(Value::String("never_happen_1".into())),
1421                ),
1422                PartitionExpr::new(
1423                    Operand::Expr(PartitionExpr::new(
1424                        Operand::Column("host".to_string()),
1425                        RestrictedOp::GtEq,
1426                        Operand::Value(Value::String("never_happen_1".into())),
1427                    )),
1428                    RestrictedOp::And,
1429                    Operand::Value(Value::Boolean(false)),
1430                ),
1431            ],
1432            false,
1433        )
1434        .unwrap();
1435
1436        let batch = generate_random_record_batch(8);
1437        let result = rule.split_record_batch(&batch).unwrap();
1438
1439        assert_eq!(result.len(), 1);
1440        assert!(result.contains_key(&0));
1441
1442        let total_rows = result.get(&0).unwrap().selected_rows();
1443        assert_eq!(total_rows, batch.num_rows());
1444    }
1445
1446    #[test]
1447    fn test_hash_partition_batch_matches_row() {
1448        use datatypes::arrow::array::{Array, StringDictionaryBuilder, UInt64Array};
1449        use datatypes::arrow::datatypes::{DataType, Field, UInt32Type};
1450
1451        let host_hash = Operand::IcebergHash(IcebergHash::new("host"));
1452        let tenant_hash = Operand::IcebergHash(IcebergHash::new("tenant"));
1453        let exprs = [
1454            host_hash
1455                .clone()
1456                .lt(Value::Int32(0))
1457                .and(col("tenant").lt(Value::UInt64(100))),
1458            host_hash
1459                .clone()
1460                .lt(Value::Int32(0))
1461                .and(col("tenant").gt_eq(Value::UInt64(100))),
1462            host_hash
1463                .clone()
1464                .gt_eq(Value::Int32(0))
1465                .and(tenant_hash.clone().lt(Value::Int32(0))),
1466            host_hash
1467                .gt_eq(Value::Int32(0))
1468                .and(tenant_hash.gt_eq(Value::Int32(0))),
1469        ]
1470        .iter()
1471        .map(|expr| {
1472            PartitionExpr::from_json_str(&expr.as_json_str().unwrap())
1473                .unwrap()
1474                .unwrap()
1475        })
1476        .collect();
1477        let rule = MultiDimPartitionRule::try_new(
1478            vec!["host".to_string(), "tenant".to_string()],
1479            vec![1, 2, 3, 4],
1480            exprs,
1481            true,
1482        )
1483        .unwrap();
1484
1485        let hosts = [
1486            None,
1487            Some(""),
1488            Some("a"),
1489            Some("b"),
1490            Some("中🙂"),
1491            Some("server42"),
1492        ];
1493        let tenants = [None, Some(0), Some(99), Some(100), Some(u64::MAX)];
1494        let mut host_builder = StringDictionaryBuilder::<UInt32Type>::new();
1495        let mut tenant_values = vec![];
1496        for host in hosts {
1497            for tenant in tenants {
1498                host_builder.append_option(host);
1499                tenant_values.push(tenant);
1500            }
1501        }
1502        let host_array = Arc::new(host_builder.finish());
1503        let batch = RecordBatch::try_new(
1504            Arc::new(Schema::new(vec![
1505                Field::new("host", host_array.data_type().clone(), true),
1506                Field::new("tenant", DataType::UInt64, true),
1507            ])),
1508            vec![host_array, Arc::new(UInt64Array::from(tenant_values))],
1509        )
1510        .unwrap();
1511
1512        let by_row = rule.split_record_batch_naive(&batch).unwrap();
1513        let by_batch = rule.split_record_batch(&batch).unwrap();
1514        assert!(!by_batch.contains_key(&DEFAULT_REGION));
1515        for (region, expected) in by_row {
1516            let actual = by_batch
1517                .get(&region)
1518                .map(|mask| mask.array().clone())
1519                .unwrap_or_else(|| BooleanArray::from(vec![false; batch.num_rows()]));
1520            assert_eq!(actual, expected, "region {region}");
1521        }
1522    }
1523
1524    #[test]
1525    fn test_comparison_batch_matches_row() {
1526        use datatypes::arrow::array::Array;
1527        use datatypes::arrow::datatypes::{DataType, Field};
1528
1529        let inputs = [None, Some(4), Some(5), Some(6)];
1530        let batch = RecordBatch::try_new(
1531            Arc::new(Schema::new(vec![Field::new("a", DataType::Int64, true)])),
1532            vec![Arc::new(Int64Array::from(inputs.to_vec()))],
1533        )
1534        .unwrap();
1535        let mut mismatches = vec![];
1536        for op in [
1537            RestrictedOp::Eq,
1538            RestrictedOp::NotEq,
1539            RestrictedOp::Lt,
1540            RestrictedOp::LtEq,
1541            RestrictedOp::Gt,
1542            RestrictedOp::GtEq,
1543        ] {
1544            for bound in [Value::Null, Value::Int64(5)] {
1545                // Both operand orders, since a rule restored without canonicalization may
1546                // keep the literal on the left.
1547                for expr in [
1548                    PartitionExpr::new(col("a"), op.clone(), bound.clone().into()),
1549                    PartitionExpr {
1550                        lhs: Box::new(bound.clone().into()),
1551                        op: op.clone(),
1552                        rhs: Box::new(col("a")),
1553                    },
1554                ] {
1555                    let rule = MultiDimPartitionRule::try_new(
1556                        vec!["a".to_string()],
1557                        vec![1],
1558                        vec![expr.clone()],
1559                        false,
1560                    )
1561                    .unwrap();
1562                    let by_batch = match expr
1563                        .try_as_physical_expr(batch.schema_ref())
1564                        .unwrap()
1565                        .evaluate(&batch)
1566                    {
1567                        Ok(by_batch) => {
1568                            columnar_value_to_boolean_array(by_batch, batch.num_rows()).unwrap()
1569                        }
1570                        Err(err) => {
1571                            mismatches.push(format!("{expr}: batch error {err}"));
1572                            continue;
1573                        }
1574                    };
1575                    for (row, input) in inputs.iter().enumerate() {
1576                        let value = input.map_or(Value::Null, Value::Int64);
1577                        let by_row = rule.evaluate_expr(&expr, &[value]).unwrap();
1578                        let by_batch = by_batch.is_valid(row) && by_batch.value(row);
1579                        if by_row != by_batch {
1580                            mismatches.push(format!(
1581                                "{expr} with a = {input:?}: row {by_row}, batch {by_batch}"
1582                            ));
1583                        }
1584                    }
1585                }
1586            }
1587        }
1588        assert!(mismatches.is_empty(), "{mismatches:#?}");
1589    }
1590
1591    #[test]
1592    fn test_split_null_rows_match_row_routing() {
1593        use datatypes::arrow::datatypes::{DataType, Field};
1594
1595        let rule = MultiDimPartitionRule::try_new(
1596            vec!["host".to_string()],
1597            vec![0, 1],
1598            vec![
1599                col("host").not_eq(Value::from("a")),
1600                col("host").eq(Value::from("a")),
1601            ],
1602            true,
1603        )
1604        .unwrap();
1605        for hosts in [vec![Some("a"), None, Some("z")], vec![Some("a"), None]] {
1606            let batch = RecordBatch::try_new(
1607                Arc::new(Schema::new(vec![Field::new("host", DataType::Utf8, true)])),
1608                vec![Arc::new(StringArray::from(hosts.clone()))],
1609            )
1610            .unwrap();
1611            let by_row = rule.split_record_batch_naive(&batch).unwrap();
1612            let by_batch = rule.split_record_batch(&batch).unwrap();
1613            for (region, expected) in by_row {
1614                let actual = by_batch
1615                    .get(&region)
1616                    .map(|mask| mask.array().clone())
1617                    .unwrap_or_else(|| BooleanArray::from(vec![false; batch.num_rows()]));
1618                assert_eq!(actual, expected, "{hosts:?}, region {region}");
1619            }
1620        }
1621    }
1622
1623    #[test]
1624    fn test_columnar_value_to_boolean_array_scalar_false() {
1625        let result = columnar_value_to_boolean_array(
1626            ColumnarValue::Scalar(ScalarValue::Boolean(Some(false))),
1627            4,
1628        )
1629        .unwrap();
1630        assert_eq!(result.len(), 4);
1631        assert_eq!(result.true_count(), 0);
1632    }
1633
1634    #[test]
1635    fn test_columnar_value_to_boolean_array_scalar_true() {
1636        let result = columnar_value_to_boolean_array(
1637            ColumnarValue::Scalar(ScalarValue::Boolean(Some(true))),
1638            4,
1639        )
1640        .unwrap();
1641        assert_eq!(result.len(), 4);
1642        assert_eq!(result.true_count(), 4);
1643    }
1644}