risingwave_common/util/
scan_range.rs

1// Copyright 2022 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                                    ) if (right - left + 1) as u64 <= max_gap => {
281                                        return Some(
282                                            (*left..=*right)
283                                                .map(|i| ScanRange {
284                                                    eq_conds: vec![Some(ScalarImpl::$type_name(i))],
285                                                    range: full_range(),
286                                                })
287                                                .collect(),
288                                        );
289                                    }
290                                )*
291                                _ => {}
292                            }
293                        }
294                    }
295
296                    None
297                }
298            }
299        }
300    };
301}
302
303for_all_scalar_int_variants! { impl_split_small_range }
304
305#[cfg(test)]
306mod tests {
307    use super::*;
308    use crate::row::OwnedRow;
309    // dist_key is prefix of pk
310    #[test]
311    fn test_vnode_prefix() {
312        let dist_key = vec![1, 3];
313        let pk = vec![1, 3, 2];
314        let dist_key_idx_in_pk =
315            crate::catalog::get_dist_key_in_pk_indices(&dist_key, &pk).unwrap();
316        let dist = TableDistribution::all(dist_key_idx_in_pk, VirtualNode::COUNT_FOR_TEST);
317
318        let mut scan_range = ScanRange::full_table_scan();
319        assert!(scan_range.try_compute_vnode(&dist).is_none());
320
321        scan_range.eq_conds.push(Some(ScalarImpl::from(114)));
322        assert!(scan_range.try_compute_vnode(&dist).is_none());
323
324        scan_range.eq_conds.push(Some(ScalarImpl::from(514)));
325        let row = OwnedRow::new(vec![
326            Some(ScalarImpl::from(114)),
327            Some(ScalarImpl::from(514)),
328        ]);
329
330        let vnode = VirtualNode::compute_row_for_test(&row, &[0, 1]);
331
332        assert_eq!(scan_range.try_compute_vnode(&dist), Some(vnode));
333    }
334
335    // dist_key is not prefix of pk
336    #[test]
337    fn test_vnode_not_prefix() {
338        let dist_key = vec![2, 3];
339        let pk = vec![1, 3, 2];
340        let dist_key_idx_in_pk =
341            crate::catalog::get_dist_key_in_pk_indices(&dist_key, &pk).unwrap();
342        let dist = TableDistribution::all(dist_key_idx_in_pk, VirtualNode::COUNT_FOR_TEST);
343
344        let mut scan_range = ScanRange::full_table_scan();
345        assert!(scan_range.try_compute_vnode(&dist).is_none());
346
347        scan_range.eq_conds.push(Some(ScalarImpl::from(114)));
348        assert!(scan_range.try_compute_vnode(&dist).is_none());
349
350        scan_range.eq_conds.push(Some(ScalarImpl::from(514)));
351        assert!(scan_range.try_compute_vnode(&dist).is_none());
352
353        scan_range.eq_conds.push(Some(ScalarImpl::from(114514)));
354        let row = OwnedRow::new(vec![
355            Some(ScalarImpl::from(114)),
356            Some(ScalarImpl::from(514)),
357            Some(ScalarImpl::from(114514)),
358        ]);
359
360        let vnode = VirtualNode::compute_row_for_test(&row, &[2, 1]);
361
362        assert_eq!(scan_range.try_compute_vnode(&dist), Some(vnode));
363    }
364
365    #[test]
366    fn test_convert_to_range() {
367        {
368            // test empty eq_conds
369            let scan_range = ScanRange {
370                eq_conds: vec![],
371                range: (
372                    Bound::Included(vec![Some(ScalarImpl::from(1))]),
373                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
374                ),
375            };
376
377            let (left, right) = scan_range.convert_to_range();
378            assert_eq!(left, Bound::Included(vec![Some(ScalarImpl::from(1))]));
379            assert_eq!(right, Bound::Included(vec![Some(ScalarImpl::from(2))]));
380        }
381
382        {
383            // test exclude bound with empty eq_conds
384            let scan_range = ScanRange {
385                eq_conds: vec![],
386                range: (
387                    Bound::Excluded(vec![Some(ScalarImpl::from(1))]),
388                    Bound::Excluded(vec![Some(ScalarImpl::from(2))]),
389                ),
390            };
391
392            let (left, right) = scan_range.convert_to_range();
393            assert_eq!(left, Bound::Excluded(vec![Some(ScalarImpl::from(1))]));
394            assert_eq!(right, Bound::Excluded(vec![Some(ScalarImpl::from(2))]));
395        }
396
397        {
398            // test include bound with empty eq_conds
399            let scan_range = ScanRange {
400                eq_conds: vec![],
401                range: (
402                    Bound::Included(vec![Some(ScalarImpl::from(1))]),
403                    Bound::Unbounded,
404                ),
405            };
406
407            let (left, right) = scan_range.convert_to_range();
408            assert_eq!(left, Bound::Included(vec![Some(ScalarImpl::from(1))]));
409            assert_eq!(right, Bound::Unbounded);
410        }
411
412        {
413            // test exclude bound with non-empty eq_conds
414            let scan_range = ScanRange {
415                eq_conds: vec![Some(ScalarImpl::from(1))],
416                range: (
417                    Bound::Excluded(vec![Some(ScalarImpl::from(2))]),
418                    Bound::Excluded(vec![Some(ScalarImpl::from(3))]),
419                ),
420            };
421
422            let (left, right) = scan_range.convert_to_range();
423            assert_eq!(
424                left,
425                Bound::Excluded(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
426            );
427            assert_eq!(
428                right,
429                Bound::Excluded(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(3))])
430            );
431        }
432
433        {
434            // test include bound with non-empty eq_conds
435            let scan_range = ScanRange {
436                eq_conds: vec![Some(ScalarImpl::from(1))],
437                range: (
438                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
439                    Bound::Included(vec![Some(ScalarImpl::from(3))]),
440                ),
441            };
442
443            let (left, right) = scan_range.convert_to_range();
444            assert_eq!(
445                left,
446                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
447            );
448            assert_eq!(
449                right,
450                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(3))])
451            );
452        }
453
454        {
455            let scan_range = ScanRange {
456                eq_conds: vec![Some(ScalarImpl::from(1))],
457                range: (
458                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
459                    Bound::Unbounded,
460                ),
461            };
462
463            let (left, right) = scan_range.convert_to_range();
464            assert_eq!(
465                left,
466                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
467            );
468            assert_eq!(right, Bound::Included(vec![Some(ScalarImpl::from(1))]));
469        }
470    }
471
472    #[test]
473    fn test_range_overlap_check() {
474        let order_types = vec![OrderType::ascending()];
475
476        // (Included, Included) vs (Included, Included)
477        assert!(ScanRange::range_overlap_check(
478            (
479                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
480                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
481            ),
482            (
483                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
484                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
485            ),
486            &order_types
487        ));
488
489        // (Included, Included) vs (Included, Excluded)
490        assert!(ScanRange::range_overlap_check(
491            (
492                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
493                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
494            ),
495            (
496                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
497                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
498            ),
499            &order_types
500        ));
501
502        // (Included, Included) vs (Excluded, Included)
503        assert!(ScanRange::range_overlap_check(
504            (
505                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
506                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
507            ),
508            (
509                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
510                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
511            ),
512            &order_types
513        ));
514
515        // (Included, Included) vs (Excluded, Excluded)
516        assert!(ScanRange::range_overlap_check(
517            (
518                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
519                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
520            ),
521            (
522                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
523                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
524            ),
525            &order_types
526        ));
527
528        // (Included, Excluded) vs (Included, Included)
529        assert!(ScanRange::range_overlap_check(
530            (
531                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
532                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
533            ),
534            (
535                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
536                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
537            ),
538            &order_types
539        ));
540
541        // (Included, Excluded) vs (Included, Excluded)
542        assert!(ScanRange::range_overlap_check(
543            (
544                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
545                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
546            ),
547            (
548                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
549                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
550            ),
551            &order_types
552        ));
553
554        // (Included, Excluded) vs (Excluded, Included)
555        assert!(ScanRange::range_overlap_check(
556            (
557                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
558                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
559            ),
560            (
561                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
562                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
563            ),
564            &order_types
565        ));
566
567        // (Included, Excluded) vs (Excluded, Excluded)
568        assert!(ScanRange::range_overlap_check(
569            (
570                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
571                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
572            ),
573            (
574                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
575                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
576            ),
577            &order_types
578        ));
579
580        // (Excluded, Included) vs (Included, Included)
581        assert!(ScanRange::range_overlap_check(
582            (
583                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
584                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
585            ),
586            (
587                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
588                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
589            ),
590            &order_types
591        ));
592
593        // (Excluded, Included) vs (Included, Excluded)
594        assert!(ScanRange::range_overlap_check(
595            (
596                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
597                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
598            ),
599            (
600                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
601                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
602            ),
603            &order_types
604        ));
605
606        // (Excluded, Included) vs (Excluded, Included)
607        assert!(ScanRange::range_overlap_check(
608            (
609                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
610                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
611            ),
612            (
613                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
614                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
615            ),
616            &order_types
617        ));
618
619        // (Excluded, Included) vs (Excluded, Excluded)
620        assert!(ScanRange::range_overlap_check(
621            (
622                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
623                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
624            ),
625            (
626                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
627                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
628            ),
629            &order_types
630        ));
631
632        // (Excluded, Excluded) vs (Included, Included)
633        assert!(ScanRange::range_overlap_check(
634            (
635                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
636                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
637            ),
638            (
639                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
640                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
641            ),
642            &order_types
643        ));
644
645        // (Excluded, Excluded) vs (Included, Excluded)
646        assert!(ScanRange::range_overlap_check(
647            (
648                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
649                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
650            ),
651            (
652                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
653                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
654            ),
655            &order_types
656        ));
657
658        // (Excluded, Excluded) vs (Excluded, Included)
659        assert!(ScanRange::range_overlap_check(
660            (
661                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
662                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
663            ),
664            (
665                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
666                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
667            ),
668            &order_types
669        ));
670
671        // (Excluded, Excluded) vs (Excluded, Excluded)
672        assert!(ScanRange::range_overlap_check(
673            (
674                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
675                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
676            ),
677            (
678                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
679                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
680            ),
681            &order_types
682        ));
683
684        // (Included, Included) vs (Included, Included)
685        assert!(ScanRange::range_overlap_check(
686            (
687                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
688                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
689            ),
690            (
691                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
692                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
693            ),
694            &order_types
695        ));
696
697        // (Included, Included) vs (Included, Included)
698        assert!(ScanRange::range_overlap_check(
699            (
700                Bound::Included(vec![Some(ScalarImpl::Int32(3)), Some(ScalarImpl::Int32(3))]),
701                Bound::Included(vec![Some(ScalarImpl::Int32(7)), Some(ScalarImpl::Int32(7))])
702            ),
703            (
704                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
705                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
706            ),
707            &order_types
708        ));
709
710        // (Included, Included) vs (Included, Included)
711        assert!(!ScanRange::range_overlap_check(
712            (
713                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
714                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
715            ),
716            (
717                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
718                Bound::Included(vec![Some(ScalarImpl::Int32(2))])
719            ),
720            &order_types
721        ));
722
723        // (Included, Included) vs (Included, Included)
724        assert!(ScanRange::range_overlap_check(
725            (
726                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
727                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
728            ),
729            (
730                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
731                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
732            ),
733            &order_types
734        ));
735
736        // (Included, Included) vs (Excluded, Included)
737        assert!(!ScanRange::range_overlap_check(
738            (
739                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
740                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
741            ),
742            (
743                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
744                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
745            ),
746            &order_types
747        ));
748
749        // (Included, Included) vs (Included, Included)
750        assert!(ScanRange::range_overlap_check(
751            (
752                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
753                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
754            ),
755            (
756                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
757                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
758            ),
759            &order_types
760        ));
761
762        assert!(!ScanRange::range_overlap_check(
763            (
764                Bound::Unbounded,
765                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
766            ),
767            (
768                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
769                Bound::Unbounded,
770            ),
771            &order_types
772        ));
773
774        assert!(ScanRange::range_overlap_check(
775            (
776                Bound::Unbounded,
777                Bound::Included(vec![Some(ScalarImpl::Int32(10))])
778            ),
779            (
780                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
781                Bound::Unbounded,
782            ),
783            &order_types
784        ));
785
786        assert!(ScanRange::range_overlap_check(
787            (Bound::Unbounded, Bound::Unbounded,),
788            (
789                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
790                Bound::Unbounded,
791            ),
792            &order_types
793        ));
794
795        assert!(ScanRange::range_overlap_check(
796            (Bound::Unbounded, Bound::Unbounded),
797            (Bound::Unbounded, Bound::Unbounded),
798            &order_types
799        ));
800
801        assert!(!ScanRange::range_overlap_check(
802            (
803                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
804                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
805            ),
806            (
807                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
808                Bound::Unbounded,
809            ),
810            &order_types
811        ));
812
813        assert!(ScanRange::range_overlap_check(
814            (
815                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
816                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
817            ),
818            (
819                Bound::Unbounded,
820                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
821            ),
822            &order_types
823        ));
824    }
825}
risingwave_common/util/scan_range.rs

risingwave_common/util/
scan_range.rs
