risingwave_common/util/
scan_range.rs

1// Copyright 2025 RisingWave Labs
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::cmp::Ordering;
16use std::ops::{Bound, RangeBounds};
17
18use itertools::Itertools;
19use paste::paste;
20use risingwave_pb::batch_plan::ScanRange as PbScanRange;
21use risingwave_pb::batch_plan::scan_range::Bound as PbBound;
22
23use super::sort_util::{OrderType, cmp_rows};
24use crate::hash::VirtualNode;
25use crate::hash::table_distribution::TableDistribution;
26use crate::types::{Datum, ScalarImpl};
27use crate::util::value_encoding::serialize_datum_into;
28
29#[derive(Debug, Clone, PartialEq, Eq, Hash)]
30pub struct ScanRange {
31    pub eq_conds: Vec<Datum>,
32    pub range: (Bound<Vec<Datum>>, Bound<Vec<Datum>>),
33}
34
35fn bound_vec_datum_to_proto(bound: &Bound<Vec<Datum>>) -> Option<PbBound> {
36    match bound {
37        Bound::Included(literal) => Some(PbBound {
38            value: literal
39                .iter()
40                .map(|datum| {
41                    let mut encoded = vec![];
42                    serialize_datum_into(datum, &mut encoded);
43                    encoded
44                })
45                .collect(),
46            inclusive: true,
47        }),
48        Bound::Excluded(literal) => Some(PbBound {
49            value: literal
50                .iter()
51                .map(|datum| {
52                    let mut encoded = vec![];
53                    serialize_datum_into(datum, &mut encoded);
54                    encoded
55                })
56                .collect(),
57            inclusive: false,
58        }),
59        Bound::Unbounded => None,
60    }
61}
62
63impl ScanRange {
64    pub fn to_protobuf(&self) -> PbScanRange {
65        PbScanRange {
66            eq_conds: self
67                .eq_conds
68                .iter()
69                .map(|datum| {
70                    let mut encoded = vec![];
71                    serialize_datum_into(datum, &mut encoded);
72                    encoded
73                })
74                .collect(),
75            lower_bound: bound_vec_datum_to_proto(&self.range.0),
76            upper_bound: bound_vec_datum_to_proto(&self.range.1),
77        }
78    }
79
80    pub fn is_full_table_scan(&self) -> bool {
81        self.eq_conds.is_empty() && self.range == full_range()
82    }
83
84    pub fn has_eq_conds(&self) -> bool {
85        !self.eq_conds.is_empty()
86    }
87
88    pub fn two_side_bound(&self) -> bool {
89        let bounds = &self.range;
90        !matches!(bounds.start_bound(), Bound::Unbounded)
91            && !matches!(bounds.end_bound(), Bound::Unbounded)
92    }
93
94    pub fn try_compute_vnode(&self, table_distribution: &TableDistribution) -> Option<VirtualNode> {
95        table_distribution.try_compute_vnode_by_pk_prefix(self.eq_conds.as_slice())
96    }
97
98    pub const fn full_table_scan() -> Self {
99        Self {
100            eq_conds: vec![],
101            range: full_range(),
102        }
103    }
104
105    pub fn convert_to_range(&self) -> (Bound<Vec<Datum>>, Bound<Vec<Datum>>) {
106        fn handle_bound(eq_conds: &Vec<Datum>, bound: &Bound<Vec<Datum>>) -> Bound<Vec<Datum>> {
107            match bound {
108                Bound::Included(literal) => {
109                    let mut prefix = eq_conds.clone();
110                    prefix.extend_from_slice(literal);
111                    Bound::Included(prefix)
112                }
113                Bound::Excluded(literal) => {
114                    let mut prefix = eq_conds.clone();
115                    prefix.extend_from_slice(literal);
116                    Bound::Excluded(prefix)
117                }
118                Bound::Unbounded => {
119                    if eq_conds.is_empty() {
120                        Bound::Unbounded
121                    } else {
122                        Bound::Included(eq_conds.clone())
123                    }
124                }
125            }
126        }
127
128        let new_left = handle_bound(&self.eq_conds, &self.range.0);
129        let new_right = handle_bound(&self.eq_conds, &self.range.1);
130        (new_left, new_right)
131    }
132
133    pub fn is_overlap(left: &ScanRange, right: &ScanRange, order_types: &[OrderType]) -> bool {
134        let range_left = left.convert_to_range();
135        let range_right = right.convert_to_range();
136        Self::range_overlap_check(range_left, range_right, order_types)
137    }
138
139    fn range_overlap_check(
140        left: (Bound<Vec<Datum>>, Bound<Vec<Datum>>),
141        right: (Bound<Vec<Datum>>, Bound<Vec<Datum>>),
142        order_types: &[OrderType],
143    ) -> bool {
144        let (left_start, left_end) = &left;
145        let (right_start, right_end) = &right;
146
147        let left_start_vec = match &left_start {
148            Bound::Included(vec) | Bound::Excluded(vec) => vec,
149            _ => &vec![],
150        };
151        let right_start_vec = match &right_start {
152            Bound::Included(vec) | Bound::Excluded(vec) => vec,
153            _ => &vec![],
154        };
155
156        if left_start_vec.is_empty() && right_start_vec.is_empty() {
157            return true;
158        }
159
160        let order_types = if order_types.iter().all(|o| o.is_ascending()) {
161            order_types
162        } else {
163            // reverse order types to ascending
164            &order_types
165                .iter()
166                .cloned()
167                .map(|o| if o.is_descending() { o.reverse() } else { o })
168                .collect_vec()
169        };
170
171        // Unbounded is always less than any other bound
172        if left_start_vec.is_empty() {
173            // pass
174        } else if right_start_vec.is_empty() {
175            return Self::range_overlap_check(right, left, order_types);
176        } else {
177            assert!(!left_start_vec.is_empty());
178            assert!(!right_start_vec.is_empty());
179            let cmp_column_len = left_start_vec.len().min(right_start_vec.len());
180            let cmp_start = cmp_rows(
181                &left_start_vec[0..cmp_column_len],
182                &right_start_vec[0..cmp_column_len],
183                &order_types[0..cmp_column_len],
184            );
185
186            let right_start_before_left_start = cmp_start.is_gt();
187
188            if right_start_before_left_start {
189                return Self::range_overlap_check(right, left, order_types);
190            }
191
192            if cmp_start == Ordering::Equal
193                && let (Bound::Included(_), Bound::Included(_)) = (left_start, right_start)
194            {
195                return true;
196            }
197        }
198
199        let left_end_vec = match &left_end {
200            Bound::Included(vec) | Bound::Excluded(vec) => vec,
201            _ => &vec![],
202        };
203        let right_end_vec = match &right_end {
204            Bound::Included(vec) | Bound::Excluded(vec) => vec,
205            _ => &vec![],
206        };
207
208        if left_end_vec.is_empty() && right_end_vec.is_empty() {
209            return true;
210        }
211
212        if left_end_vec.is_empty() {
213            true
214        } else {
215            // cmp left_end and right_start
216            assert!(!left_end_vec.is_empty());
217            assert!(!right_start_vec.is_empty());
218
219            let cmp_column_len = left_end_vec.len().min(right_start_vec.len());
220            let cmp_end = cmp_rows(
221                &left_end_vec[0..cmp_column_len],
222                &right_start_vec[0..cmp_column_len],
223                &order_types[0..cmp_column_len],
224            );
225
226            match cmp_end {
227                Ordering::Equal => {
228                    if let (Bound::Included(_), Bound::Included(_)) = (left_end, right_start) {
229                        return true;
230                    }
231                }
232
233                Ordering::Greater => {
234                    return true;
235                }
236
237                Ordering::Less => {
238                    return false;
239                }
240            }
241
242            false
243        }
244    }
245}
246
247pub const fn full_range<T>() -> (Bound<T>, Bound<T>) {
248    (Bound::Unbounded, Bound::Unbounded)
249}
250
251pub fn is_full_range<T>(bounds: &impl RangeBounds<T>) -> bool {
252    matches!(bounds.start_bound(), Bound::Unbounded)
253        && matches!(bounds.end_bound(), Bound::Unbounded)
254}
255
256macro_rules! for_all_scalar_int_variants {
257    ($macro:ident) => {
258        $macro! {
259            { Int16 },
260            { Int32 },
261            { Int64 }
262        }
263    };
264}
265
266macro_rules! impl_split_small_range {
267    ($( { $type_name:ident} ),*) => {
268        paste! {
269            impl ScanRange {
270                /// `Precondition`: make sure the first order key is int type if you call this method.
271                /// Optimize small range scan. It turns x between 0 and 5 into x in (0, 1, 2, 3, 4, 5).s
272                pub fn split_small_range(&self, max_gap: u64) -> Option<Vec<Self>> {
273                    if self.eq_conds.is_empty() {
274                        if let (Bound::Included(left),Bound::Included(right)) = (&self.range.0, &self.range.1){
275                            match (left.get(0),right.get(0)) {
276                                $(
277                                    (
278                                        Some(Some(ScalarImpl::$type_name(left))),
279                                        Some(Some(ScalarImpl::$type_name(right))),
280                                    ) => {
281
282                                        if (right - left + 1) as u64 <= max_gap {
283                                            return Some(
284                                                (*left..=*right)
285                                                    .into_iter()
286                                                    .map(|i| ScanRange {
287                                                        eq_conds: vec![Some(ScalarImpl::$type_name(i))],
288                                                        range: full_range(),
289                                                    })
290                                                    .collect(),
291                                            );
292                                        }
293                                    }
294                                )*
295                                _ => {}
296                            }
297                        }
298                    }
299
300                    None
301                }
302            }
303        }
304    };
305}
306
307for_all_scalar_int_variants! { impl_split_small_range }
308
309#[cfg(test)]
310mod tests {
311    use super::*;
312    use crate::row::OwnedRow;
313    // dist_key is prefix of pk
314    #[test]
315    fn test_vnode_prefix() {
316        let dist_key = vec![1, 3];
317        let pk = vec![1, 3, 2];
318        let dist_key_idx_in_pk =
319            crate::catalog::get_dist_key_in_pk_indices(&dist_key, &pk).unwrap();
320        let dist = TableDistribution::all(dist_key_idx_in_pk, VirtualNode::COUNT_FOR_TEST);
321
322        let mut scan_range = ScanRange::full_table_scan();
323        assert!(scan_range.try_compute_vnode(&dist).is_none());
324
325        scan_range.eq_conds.push(Some(ScalarImpl::from(114)));
326        assert!(scan_range.try_compute_vnode(&dist).is_none());
327
328        scan_range.eq_conds.push(Some(ScalarImpl::from(514)));
329        let row = OwnedRow::new(vec![
330            Some(ScalarImpl::from(114)),
331            Some(ScalarImpl::from(514)),
332        ]);
333
334        let vnode = VirtualNode::compute_row_for_test(&row, &[0, 1]);
335
336        assert_eq!(scan_range.try_compute_vnode(&dist), Some(vnode));
337    }
338
339    // dist_key is not prefix of pk
340    #[test]
341    fn test_vnode_not_prefix() {
342        let dist_key = vec![2, 3];
343        let pk = vec![1, 3, 2];
344        let dist_key_idx_in_pk =
345            crate::catalog::get_dist_key_in_pk_indices(&dist_key, &pk).unwrap();
346        let dist = TableDistribution::all(dist_key_idx_in_pk, VirtualNode::COUNT_FOR_TEST);
347
348        let mut scan_range = ScanRange::full_table_scan();
349        assert!(scan_range.try_compute_vnode(&dist).is_none());
350
351        scan_range.eq_conds.push(Some(ScalarImpl::from(114)));
352        assert!(scan_range.try_compute_vnode(&dist).is_none());
353
354        scan_range.eq_conds.push(Some(ScalarImpl::from(514)));
355        assert!(scan_range.try_compute_vnode(&dist).is_none());
356
357        scan_range.eq_conds.push(Some(ScalarImpl::from(114514)));
358        let row = OwnedRow::new(vec![
359            Some(ScalarImpl::from(114)),
360            Some(ScalarImpl::from(514)),
361            Some(ScalarImpl::from(114514)),
362        ]);
363
364        let vnode = VirtualNode::compute_row_for_test(&row, &[2, 1]);
365
366        assert_eq!(scan_range.try_compute_vnode(&dist), Some(vnode));
367    }
368
369    #[test]
370    fn test_convert_to_range() {
371        {
372            // test empty eq_conds
373            let scan_range = ScanRange {
374                eq_conds: vec![],
375                range: (
376                    Bound::Included(vec![Some(ScalarImpl::from(1))]),
377                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
378                ),
379            };
380
381            let (left, right) = scan_range.convert_to_range();
382            assert_eq!(left, Bound::Included(vec![Some(ScalarImpl::from(1))]));
383            assert_eq!(right, Bound::Included(vec![Some(ScalarImpl::from(2))]));
384        }
385
386        {
387            // test exclude bound with empty eq_conds
388            let scan_range = ScanRange {
389                eq_conds: vec![],
390                range: (
391                    Bound::Excluded(vec![Some(ScalarImpl::from(1))]),
392                    Bound::Excluded(vec![Some(ScalarImpl::from(2))]),
393                ),
394            };
395
396            let (left, right) = scan_range.convert_to_range();
397            assert_eq!(left, Bound::Excluded(vec![Some(ScalarImpl::from(1))]));
398            assert_eq!(right, Bound::Excluded(vec![Some(ScalarImpl::from(2))]));
399        }
400
401        {
402            // test include bound with empty eq_conds
403            let scan_range = ScanRange {
404                eq_conds: vec![],
405                range: (
406                    Bound::Included(vec![Some(ScalarImpl::from(1))]),
407                    Bound::Unbounded,
408                ),
409            };
410
411            let (left, right) = scan_range.convert_to_range();
412            assert_eq!(left, Bound::Included(vec![Some(ScalarImpl::from(1))]));
413            assert_eq!(right, Bound::Unbounded);
414        }
415
416        {
417            // test exclude bound with non-empty eq_conds
418            let scan_range = ScanRange {
419                eq_conds: vec![Some(ScalarImpl::from(1))],
420                range: (
421                    Bound::Excluded(vec![Some(ScalarImpl::from(2))]),
422                    Bound::Excluded(vec![Some(ScalarImpl::from(3))]),
423                ),
424            };
425
426            let (left, right) = scan_range.convert_to_range();
427            assert_eq!(
428                left,
429                Bound::Excluded(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
430            );
431            assert_eq!(
432                right,
433                Bound::Excluded(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(3))])
434            );
435        }
436
437        {
438            // test include bound with non-empty eq_conds
439            let scan_range = ScanRange {
440                eq_conds: vec![Some(ScalarImpl::from(1))],
441                range: (
442                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
443                    Bound::Included(vec![Some(ScalarImpl::from(3))]),
444                ),
445            };
446
447            let (left, right) = scan_range.convert_to_range();
448            assert_eq!(
449                left,
450                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
451            );
452            assert_eq!(
453                right,
454                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(3))])
455            );
456        }
457
458        {
459            let scan_range = ScanRange {
460                eq_conds: vec![Some(ScalarImpl::from(1))],
461                range: (
462                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
463                    Bound::Unbounded,
464                ),
465            };
466
467            let (left, right) = scan_range.convert_to_range();
468            assert_eq!(
469                left,
470                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
471            );
472            assert_eq!(right, Bound::Included(vec![Some(ScalarImpl::from(1))]));
473        }
474    }
475
476    #[test]
477    fn test_range_overlap_check() {
478        let order_types = vec![OrderType::ascending()];
479
480        // (Included, Included) vs (Included, Included)
481        assert!(ScanRange::range_overlap_check(
482            (
483                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
484                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
485            ),
486            (
487                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
488                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
489            ),
490            &order_types
491        ));
492
493        // (Included, Included) vs (Included, Excluded)
494        assert!(ScanRange::range_overlap_check(
495            (
496                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
497                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
498            ),
499            (
500                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
501                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
502            ),
503            &order_types
504        ));
505
506        // (Included, Included) vs (Excluded, Included)
507        assert!(ScanRange::range_overlap_check(
508            (
509                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
510                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
511            ),
512            (
513                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
514                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
515            ),
516            &order_types
517        ));
518
519        // (Included, Included) vs (Excluded, Excluded)
520        assert!(ScanRange::range_overlap_check(
521            (
522                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
523                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
524            ),
525            (
526                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
527                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
528            ),
529            &order_types
530        ));
531
532        // (Included, Excluded) vs (Included, Included)
533        assert!(ScanRange::range_overlap_check(
534            (
535                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
536                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
537            ),
538            (
539                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
540                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
541            ),
542            &order_types
543        ));
544
545        // (Included, Excluded) vs (Included, Excluded)
546        assert!(ScanRange::range_overlap_check(
547            (
548                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
549                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
550            ),
551            (
552                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
553                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
554            ),
555            &order_types
556        ));
557
558        // (Included, Excluded) vs (Excluded, Included)
559        assert!(ScanRange::range_overlap_check(
560            (
561                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
562                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
563            ),
564            (
565                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
566                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
567            ),
568            &order_types
569        ));
570
571        // (Included, Excluded) vs (Excluded, Excluded)
572        assert!(ScanRange::range_overlap_check(
573            (
574                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
575                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
576            ),
577            (
578                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
579                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
580            ),
581            &order_types
582        ));
583
584        // (Excluded, Included) vs (Included, Included)
585        assert!(ScanRange::range_overlap_check(
586            (
587                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
588                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
589            ),
590            (
591                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
592                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
593            ),
594            &order_types
595        ));
596
597        // (Excluded, Included) vs (Included, Excluded)
598        assert!(ScanRange::range_overlap_check(
599            (
600                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
601                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
602            ),
603            (
604                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
605                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
606            ),
607            &order_types
608        ));
609
610        // (Excluded, Included) vs (Excluded, Included)
611        assert!(ScanRange::range_overlap_check(
612            (
613                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
614                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
615            ),
616            (
617                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
618                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
619            ),
620            &order_types
621        ));
622
623        // (Excluded, Included) vs (Excluded, Excluded)
624        assert!(ScanRange::range_overlap_check(
625            (
626                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
627                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
628            ),
629            (
630                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
631                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
632            ),
633            &order_types
634        ));
635
636        // (Excluded, Excluded) vs (Included, Included)
637        assert!(ScanRange::range_overlap_check(
638            (
639                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
640                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
641            ),
642            (
643                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
644                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
645            ),
646            &order_types
647        ));
648
649        // (Excluded, Excluded) vs (Included, Excluded)
650        assert!(ScanRange::range_overlap_check(
651            (
652                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
653                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
654            ),
655            (
656                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
657                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
658            ),
659            &order_types
660        ));
661
662        // (Excluded, Excluded) vs (Excluded, Included)
663        assert!(ScanRange::range_overlap_check(
664            (
665                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
666                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
667            ),
668            (
669                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
670                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
671            ),
672            &order_types
673        ));
674
675        // (Excluded, Excluded) vs (Excluded, Excluded)
676        assert!(ScanRange::range_overlap_check(
677            (
678                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
679                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
680            ),
681            (
682                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
683                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
684            ),
685            &order_types
686        ));
687
688        // (Included, Included) vs (Included, Included)
689        assert!(ScanRange::range_overlap_check(
690            (
691                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
692                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
693            ),
694            (
695                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
696                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
697            ),
698            &order_types
699        ));
700
701        // (Included, Included) vs (Included, Included)
702        assert!(ScanRange::range_overlap_check(
703            (
704                Bound::Included(vec![Some(ScalarImpl::Int32(3)), Some(ScalarImpl::Int32(3))]),
705                Bound::Included(vec![Some(ScalarImpl::Int32(7)), Some(ScalarImpl::Int32(7))])
706            ),
707            (
708                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
709                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
710            ),
711            &order_types
712        ));
713
714        // (Included, Included) vs (Included, Included)
715        assert!(!ScanRange::range_overlap_check(
716            (
717                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
718                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
719            ),
720            (
721                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
722                Bound::Included(vec![Some(ScalarImpl::Int32(2))])
723            ),
724            &order_types
725        ));
726
727        // (Included, Included) vs (Included, Included)
728        assert!(ScanRange::range_overlap_check(
729            (
730                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
731                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
732            ),
733            (
734                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
735                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
736            ),
737            &order_types
738        ));
739
740        // (Included, Included) vs (Excluded, Encluded)
741        assert!(!ScanRange::range_overlap_check(
742            (
743                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
744                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
745            ),
746            (
747                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
748                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
749            ),
750            &order_types
751        ));
752
753        // (Included, Included) vs (Included, Encluded)
754        assert!(ScanRange::range_overlap_check(
755            (
756                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
757                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
758            ),
759            (
760                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
761                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
762            ),
763            &order_types
764        ));
765
766        assert!(!ScanRange::range_overlap_check(
767            (
768                Bound::Unbounded,
769                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
770            ),
771            (
772                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
773                Bound::Unbounded,
774            ),
775            &order_types
776        ));
777
778        assert!(ScanRange::range_overlap_check(
779            (
780                Bound::Unbounded,
781                Bound::Included(vec![Some(ScalarImpl::Int32(10))])
782            ),
783            (
784                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
785                Bound::Unbounded,
786            ),
787            &order_types
788        ));
789
790        assert!(ScanRange::range_overlap_check(
791            (Bound::Unbounded, Bound::Unbounded,),
792            (
793                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
794                Bound::Unbounded,
795            ),
796            &order_types
797        ));
798
799        assert!(ScanRange::range_overlap_check(
800            (Bound::Unbounded, Bound::Unbounded),
801            (Bound::Unbounded, Bound::Unbounded),
802            &order_types
803        ));
804
805        assert!(!ScanRange::range_overlap_check(
806            (
807                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
808                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
809            ),
810            (
811                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
812                Bound::Unbounded,
813            ),
814            &order_types
815        ));
816
817        assert!(ScanRange::range_overlap_check(
818            (
819                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
820                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
821            ),
822            (
823                Bound::Unbounded,
824                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
825            ),
826            &order_types
827        ));
828    }
829}
risingwave_common/util/scan_range.rs

risingwave_common/util/
scan_range.rs
