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 paste::paste;
19use risingwave_pb::batch_plan::ScanRange as PbScanRange;
20use risingwave_pb::batch_plan::scan_range::Bound as PbBound;
21
22use super::sort_util::{OrderType, cmp_rows};
23use crate::hash::VirtualNode;
24use crate::hash::table_distribution::TableDistribution;
25use crate::types::{Datum, ScalarImpl};
26use crate::util::value_encoding::serialize_datum_into;
27
28#[derive(Debug, Clone, PartialEq, Eq, Hash)]
29pub struct ScanRange {
30    pub eq_conds: Vec<Datum>,
31    pub range: (Bound<Vec<Datum>>, Bound<Vec<Datum>>),
32}
33
34fn bound_vec_datum_to_proto(bound: &Bound<Vec<Datum>>) -> Option<PbBound> {
35    match bound {
36        Bound::Included(literal) => Some(PbBound {
37            value: literal
38                .iter()
39                .map(|datum| {
40                    let mut encoded = vec![];
41                    serialize_datum_into(datum, &mut encoded);
42                    encoded
43                })
44                .collect(),
45            inclusive: true,
46        }),
47        Bound::Excluded(literal) => Some(PbBound {
48            value: literal
49                .iter()
50                .map(|datum| {
51                    let mut encoded = vec![];
52                    serialize_datum_into(datum, &mut encoded);
53                    encoded
54                })
55                .collect(),
56            inclusive: false,
57        }),
58        Bound::Unbounded => None,
59    }
60}
61
62impl ScanRange {
63    pub fn to_protobuf(&self) -> PbScanRange {
64        PbScanRange {
65            eq_conds: self
66                .eq_conds
67                .iter()
68                .map(|datum| {
69                    let mut encoded = vec![];
70                    serialize_datum_into(datum, &mut encoded);
71                    encoded
72                })
73                .collect(),
74            lower_bound: bound_vec_datum_to_proto(&self.range.0),
75            upper_bound: bound_vec_datum_to_proto(&self.range.1),
76        }
77    }
78
79    pub fn is_full_table_scan(&self) -> bool {
80        self.eq_conds.is_empty() && self.range == full_range()
81    }
82
83    pub fn has_eq_conds(&self) -> bool {
84        !self.eq_conds.is_empty()
85    }
86
87    pub fn two_side_bound(&self) -> bool {
88        let bounds = &self.range;
89        !matches!(bounds.start_bound(), Bound::Unbounded)
90            && !matches!(bounds.end_bound(), Bound::Unbounded)
91    }
92
93    pub fn try_compute_vnode(&self, table_distribution: &TableDistribution) -> Option<VirtualNode> {
94        table_distribution.try_compute_vnode_by_pk_prefix(self.eq_conds.as_slice())
95    }
96
97    pub const fn full_table_scan() -> Self {
98        Self {
99            eq_conds: vec![],
100            range: full_range(),
101        }
102    }
103
104    pub fn convert_to_range(&self) -> (Bound<Vec<Datum>>, Bound<Vec<Datum>>) {
105        fn handle_bound(eq_conds: &Vec<Datum>, bound: &Bound<Vec<Datum>>) -> Bound<Vec<Datum>> {
106            match bound {
107                Bound::Included(literal) => {
108                    let mut prefix = eq_conds.clone();
109                    prefix.extend_from_slice(literal);
110                    Bound::Included(prefix)
111                }
112                Bound::Excluded(literal) => {
113                    let mut prefix = eq_conds.clone();
114                    prefix.extend_from_slice(literal);
115                    Bound::Excluded(prefix)
116                }
117                Bound::Unbounded => {
118                    if eq_conds.is_empty() {
119                        Bound::Unbounded
120                    } else {
121                        Bound::Included(eq_conds.clone())
122                    }
123                }
124            }
125        }
126
127        let new_left = handle_bound(&self.eq_conds, &self.range.0);
128        let new_right = handle_bound(&self.eq_conds, &self.range.1);
129        (new_left, new_right)
130    }
131
132    /// Returns whether the two ranges may contain a common row.
133    ///
134    /// `order_types` are the pk order types with descending ones reversed, i.e. the order in which
135    /// the range bounds are compared.
136    pub fn is_overlap(left: &ScanRange, right: &ScanRange, order_types: &[OrderType]) -> bool {
137        cmp_cut(
138            &left.start_cut(order_types),
139            &right.end_cut(order_types),
140            order_types,
141        )
142        .is_lt()
143            && cmp_cut(
144                &right.start_cut(order_types),
145                &left.end_cut(order_types),
146                order_types,
147            )
148            .is_lt()
149    }
150
151    /// Compares where the two ranges start. See [`Self::is_overlap`] for `order_types`.
152    pub fn cmp_start(left: &ScanRange, right: &ScanRange, order_types: &[OrderType]) -> Ordering {
153        cmp_cut(
154            &left.start_cut(order_types),
155            &right.start_cut(order_types),
156            order_types,
157        )
158    }
159
160    /// Returns a range covering two overlapping ranges. It is exact if one range contains the other
161    /// or both have the same `eq_conds`. Otherwise, it is widened to the whole common prefix of
162    /// their `eq_conds`. See [`Self::is_overlap`] for `order_types`.
163    pub fn union(self, other: ScanRange, order_types: &[OrderType]) -> ScanRange {
164        let cmp_start = Self::cmp_start(&self, &other, order_types);
165        let cmp_end = cmp_cut(
166            &self.end_cut(order_types),
167            &other.end_cut(order_types),
168            order_types,
169        );
170        if cmp_start.is_le() && cmp_end.is_ge() {
171            return self;
172        }
173        if cmp_start.is_ge() && cmp_end.is_le() {
174            return other;
175        }
176        if self.eq_conds == other.eq_conds {
177            let start = if cmp_start.is_le() {
178                self.range.0
179            } else {
180                other.range.0
181            };
182            let end = if cmp_end.is_ge() {
183                self.range.1
184            } else {
185                other.range.1
186            };
187            ScanRange {
188                eq_conds: self.eq_conds,
189                range: (start, end),
190            }
191        } else {
192            let common_len = (0..self.eq_conds.len().min(other.eq_conds.len()))
193                .take_while(|&i| self.eq_conds[i] == other.eq_conds[i])
194                .count();
195            let mut eq_conds = self.eq_conds;
196            eq_conds.truncate(common_len);
197            ScanRange {
198                eq_conds,
199                range: full_range(),
200            }
201        }
202    }
203
204    /// Where the range starts in pk order. See [`Cut`].
205    fn start_cut(&self, order_types: &[OrderType]) -> Cut {
206        let mut prefix = self.eq_conds.clone();
207        let after = match &self.range.0 {
208            Bound::Included(literal) => {
209                prefix.extend_from_slice(literal);
210                false
211            }
212            Bound::Excluded(literal) => {
213                prefix.extend_from_slice(literal);
214                true
215            }
216            Bound::Unbounded => {
217                if self.skipped_nulls_are_largest(order_types) == Some(false) {
218                    prefix.push(None);
219                    true
220                } else {
221                    false
222                }
223            }
224        };
225        (prefix, after)
226    }
227
228    /// Where the range ends in pk order. See [`Cut`].
229    fn end_cut(&self, order_types: &[OrderType]) -> Cut {
230        let mut prefix = self.eq_conds.clone();
231        let after = match &self.range.1 {
232            Bound::Included(literal) => {
233                prefix.extend_from_slice(literal);
234                true
235            }
236            Bound::Excluded(literal) => {
237                prefix.extend_from_slice(literal);
238                false
239            }
240            Bound::Unbounded => {
241                if self.skipped_nulls_are_largest(order_types) == Some(true) {
242                    prefix.push(None);
243                    false
244                } else {
245                    true
246                }
247            }
248        };
249        (prefix, after)
250    }
251
252    /// When only one side of the range is bounded, storage skips the NULLs of the first range
253    /// column (see `PkScanRange::convert_to_range_bounds`). Returns whether those NULLs sort after
254    /// the other values, or `None` if no NULLs are skipped.
255    fn skipped_nulls_are_largest(&self, order_types: &[OrderType]) -> Option<bool> {
256        let half_bounded =
257            matches!(self.range.0, Bound::Unbounded) != matches!(self.range.1, Bound::Unbounded);
258        let order_type = order_types.get(self.eq_conds.len())?;
259        half_bounded.then(|| order_type.nulls_are_largest())
260    }
261}
262
263/// A position in pk order: right before (`false`) or right after (`true`) all the keys starting
264/// with the prefix.
265type Cut = (Vec<Datum>, bool);
266
267/// Compares two cuts. When one prefix is shorter, it is compared as if extended with -inf or +inf.
268fn cmp_cut(
269    (left, left_after): &Cut,
270    (right, right_after): &Cut,
271    order_types: &[OrderType],
272) -> Ordering {
273    let len = left.len().min(right.len());
274    cmp_rows(&left[..len], &right[..len], &order_types[..len]).then_with(|| {
275        match left.len().cmp(&right.len()) {
276            Ordering::Equal => left_after.cmp(right_after),
277            Ordering::Less if *left_after => Ordering::Greater,
278            Ordering::Less => Ordering::Less,
279            Ordering::Greater if *right_after => Ordering::Less,
280            Ordering::Greater => Ordering::Greater,
281        }
282    })
283}
284
285pub const fn full_range<T>() -> (Bound<T>, Bound<T>) {
286    (Bound::Unbounded, Bound::Unbounded)
287}
288
289pub fn is_full_range<T>(bounds: &impl RangeBounds<T>) -> bool {
290    matches!(bounds.start_bound(), Bound::Unbounded)
291        && matches!(bounds.end_bound(), Bound::Unbounded)
292}
293
294macro_rules! for_all_scalar_int_variants {
295    ($macro:ident) => {
296        $macro! {
297            { Int16 },
298            { Int32 },
299            { Int64 }
300        }
301    };
302}
303
304macro_rules! impl_split_small_range {
305    ($( { $type_name:ident} ),*) => {
306        paste! {
307            impl ScanRange {
308                /// `Precondition`: make sure the first order key is int type if you call this method.
309                /// Optimize small range scan. It turns x between 0 and 5 into x in (0, 1, 2, 3, 4, 5).s
310                pub fn split_small_range(&self, max_gap: u64) -> Option<Vec<Self>> {
311                    if self.eq_conds.is_empty() {
312                        if let (Bound::Included(left),Bound::Included(right)) = (&self.range.0, &self.range.1){
313                            match (left.get(0),right.get(0)) {
314                                $(
315                                    // Compute the gap in i128 so that it cannot overflow.
316                                    (
317                                        Some(Some(ScalarImpl::$type_name(left))),
318                                        Some(Some(ScalarImpl::$type_name(right))),
319                                    ) if (0..i128::from(max_gap))
320                                        .contains(&(i128::from(*right) - i128::from(*left))) =>
321                                    {
322                                        return Some(
323                                            (*left..=*right)
324                                                .map(|i| ScanRange {
325                                                    eq_conds: vec![Some(ScalarImpl::$type_name(i))],
326                                                    range: full_range(),
327                                                })
328                                                .collect(),
329                                        );
330                                    }
331                                )*
332                                _ => {}
333                            }
334                        }
335                    }
336
337                    None
338                }
339            }
340        }
341    };
342}
343
344for_all_scalar_int_variants! { impl_split_small_range }
345
346#[cfg(test)]
347mod tests {
348    use super::*;
349    use crate::row::OwnedRow;
350    // dist_key is prefix of pk
351    #[test]
352    fn test_vnode_prefix() {
353        let dist_key = vec![1, 3];
354        let pk = vec![1, 3, 2];
355        let dist_key_idx_in_pk =
356            crate::catalog::get_dist_key_in_pk_indices(&dist_key, &pk).unwrap();
357        let dist = TableDistribution::all(dist_key_idx_in_pk, VirtualNode::COUNT_FOR_TEST);
358
359        let mut scan_range = ScanRange::full_table_scan();
360        assert!(scan_range.try_compute_vnode(&dist).is_none());
361
362        scan_range.eq_conds.push(Some(ScalarImpl::from(114)));
363        assert!(scan_range.try_compute_vnode(&dist).is_none());
364
365        scan_range.eq_conds.push(Some(ScalarImpl::from(514)));
366        let row = OwnedRow::new(vec![
367            Some(ScalarImpl::from(114)),
368            Some(ScalarImpl::from(514)),
369        ]);
370
371        let vnode = VirtualNode::compute_row_for_test(&row, &[0, 1]);
372
373        assert_eq!(scan_range.try_compute_vnode(&dist), Some(vnode));
374    }
375
376    // dist_key is not prefix of pk
377    #[test]
378    fn test_vnode_not_prefix() {
379        let dist_key = vec![2, 3];
380        let pk = vec![1, 3, 2];
381        let dist_key_idx_in_pk =
382            crate::catalog::get_dist_key_in_pk_indices(&dist_key, &pk).unwrap();
383        let dist = TableDistribution::all(dist_key_idx_in_pk, VirtualNode::COUNT_FOR_TEST);
384
385        let mut scan_range = ScanRange::full_table_scan();
386        assert!(scan_range.try_compute_vnode(&dist).is_none());
387
388        scan_range.eq_conds.push(Some(ScalarImpl::from(114)));
389        assert!(scan_range.try_compute_vnode(&dist).is_none());
390
391        scan_range.eq_conds.push(Some(ScalarImpl::from(514)));
392        assert!(scan_range.try_compute_vnode(&dist).is_none());
393
394        scan_range.eq_conds.push(Some(ScalarImpl::from(114514)));
395        let row = OwnedRow::new(vec![
396            Some(ScalarImpl::from(114)),
397            Some(ScalarImpl::from(514)),
398            Some(ScalarImpl::from(114514)),
399        ]);
400
401        let vnode = VirtualNode::compute_row_for_test(&row, &[2, 1]);
402
403        assert_eq!(scan_range.try_compute_vnode(&dist), Some(vnode));
404    }
405
406    #[test]
407    fn test_convert_to_range() {
408        {
409            // test empty eq_conds
410            let scan_range = ScanRange {
411                eq_conds: vec![],
412                range: (
413                    Bound::Included(vec![Some(ScalarImpl::from(1))]),
414                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
415                ),
416            };
417
418            let (left, right) = scan_range.convert_to_range();
419            assert_eq!(left, Bound::Included(vec![Some(ScalarImpl::from(1))]));
420            assert_eq!(right, Bound::Included(vec![Some(ScalarImpl::from(2))]));
421        }
422
423        {
424            // test exclude bound with empty eq_conds
425            let scan_range = ScanRange {
426                eq_conds: vec![],
427                range: (
428                    Bound::Excluded(vec![Some(ScalarImpl::from(1))]),
429                    Bound::Excluded(vec![Some(ScalarImpl::from(2))]),
430                ),
431            };
432
433            let (left, right) = scan_range.convert_to_range();
434            assert_eq!(left, Bound::Excluded(vec![Some(ScalarImpl::from(1))]));
435            assert_eq!(right, Bound::Excluded(vec![Some(ScalarImpl::from(2))]));
436        }
437
438        {
439            // test include bound with empty eq_conds
440            let scan_range = ScanRange {
441                eq_conds: vec![],
442                range: (
443                    Bound::Included(vec![Some(ScalarImpl::from(1))]),
444                    Bound::Unbounded,
445                ),
446            };
447
448            let (left, right) = scan_range.convert_to_range();
449            assert_eq!(left, Bound::Included(vec![Some(ScalarImpl::from(1))]));
450            assert_eq!(right, Bound::Unbounded);
451        }
452
453        {
454            // test exclude bound with non-empty eq_conds
455            let scan_range = ScanRange {
456                eq_conds: vec![Some(ScalarImpl::from(1))],
457                range: (
458                    Bound::Excluded(vec![Some(ScalarImpl::from(2))]),
459                    Bound::Excluded(vec![Some(ScalarImpl::from(3))]),
460                ),
461            };
462
463            let (left, right) = scan_range.convert_to_range();
464            assert_eq!(
465                left,
466                Bound::Excluded(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
467            );
468            assert_eq!(
469                right,
470                Bound::Excluded(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(3))])
471            );
472        }
473
474        {
475            // test include bound with non-empty eq_conds
476            let scan_range = ScanRange {
477                eq_conds: vec![Some(ScalarImpl::from(1))],
478                range: (
479                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
480                    Bound::Included(vec![Some(ScalarImpl::from(3))]),
481                ),
482            };
483
484            let (left, right) = scan_range.convert_to_range();
485            assert_eq!(
486                left,
487                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
488            );
489            assert_eq!(
490                right,
491                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(3))])
492            );
493        }
494
495        {
496            let scan_range = ScanRange {
497                eq_conds: vec![Some(ScalarImpl::from(1))],
498                range: (
499                    Bound::Included(vec![Some(ScalarImpl::from(2))]),
500                    Bound::Unbounded,
501                ),
502            };
503
504            let (left, right) = scan_range.convert_to_range();
505            assert_eq!(
506                left,
507                Bound::Included(vec![Some(ScalarImpl::from(1)), Some(ScalarImpl::from(2))])
508            );
509            assert_eq!(right, Bound::Included(vec![Some(ScalarImpl::from(1))]));
510        }
511    }
512
513    fn range_overlap_check(
514        left: (Bound<Vec<Datum>>, Bound<Vec<Datum>>),
515        right: (Bound<Vec<Datum>>, Bound<Vec<Datum>>),
516        order_types: &[OrderType],
517    ) -> bool {
518        let to_scan_range = |range| ScanRange {
519            eq_conds: vec![],
520            range,
521        };
522        ScanRange::is_overlap(&to_scan_range(left), &to_scan_range(right), order_types)
523    }
524
525    #[test]
526    fn test_range_overlap_check() {
527        let order_types = vec![OrderType::ascending()];
528
529        // (Included, Included) vs (Included, Included)
530        assert!(range_overlap_check(
531            (
532                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
533                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
534            ),
535            (
536                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
537                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
538            ),
539            &order_types
540        ));
541
542        // (Included, Included) vs (Included, Excluded)
543        assert!(range_overlap_check(
544            (
545                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
546                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
547            ),
548            (
549                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
550                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
551            ),
552            &order_types
553        ));
554
555        // (Included, Included) vs (Excluded, Included)
556        assert!(range_overlap_check(
557            (
558                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
559                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
560            ),
561            (
562                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
563                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
564            ),
565            &order_types
566        ));
567
568        // (Included, Included) vs (Excluded, Excluded)
569        assert!(range_overlap_check(
570            (
571                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
572                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
573            ),
574            (
575                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
576                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
577            ),
578            &order_types
579        ));
580
581        // (Included, Excluded) vs (Included, Included)
582        assert!(range_overlap_check(
583            (
584                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
585                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
586            ),
587            (
588                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
589                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
590            ),
591            &order_types
592        ));
593
594        // (Included, Excluded) vs (Included, Excluded)
595        assert!(range_overlap_check(
596            (
597                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
598                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
599            ),
600            (
601                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
602                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
603            ),
604            &order_types
605        ));
606
607        // (Included, Excluded) vs (Excluded, Included)
608        assert!(range_overlap_check(
609            (
610                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
611                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
612            ),
613            (
614                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
615                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
616            ),
617            &order_types
618        ));
619
620        // (Included, Excluded) vs (Excluded, Excluded)
621        assert!(range_overlap_check(
622            (
623                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
624                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
625            ),
626            (
627                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
628                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
629            ),
630            &order_types
631        ));
632
633        // (Excluded, Included) vs (Included, Included)
634        assert!(range_overlap_check(
635            (
636                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
637                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
638            ),
639            (
640                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
641                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
642            ),
643            &order_types
644        ));
645
646        // (Excluded, Included) vs (Included, Excluded)
647        assert!(range_overlap_check(
648            (
649                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
650                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
651            ),
652            (
653                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
654                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
655            ),
656            &order_types
657        ));
658
659        // (Excluded, Included) vs (Excluded, Included)
660        assert!(range_overlap_check(
661            (
662                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
663                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
664            ),
665            (
666                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
667                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
668            ),
669            &order_types
670        ));
671
672        // (Excluded, Included) vs (Excluded, Excluded)
673        assert!(range_overlap_check(
674            (
675                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
676                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
677            ),
678            (
679                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
680                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
681            ),
682            &order_types
683        ));
684
685        // (Excluded, Excluded) vs (Included, Included)
686        assert!(range_overlap_check(
687            (
688                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
689                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
690            ),
691            (
692                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
693                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
694            ),
695            &order_types
696        ));
697
698        // (Excluded, Excluded) vs (Included, Excluded)
699        assert!(range_overlap_check(
700            (
701                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
702                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
703            ),
704            (
705                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
706                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
707            ),
708            &order_types
709        ));
710
711        // (Excluded, Excluded) vs (Excluded, Included)
712        assert!(range_overlap_check(
713            (
714                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
715                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
716            ),
717            (
718                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
719                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
720            ),
721            &order_types
722        ));
723
724        // (Excluded, Excluded) vs (Excluded, Excluded)
725        assert!(range_overlap_check(
726            (
727                Bound::Excluded(vec![Some(ScalarImpl::Int32(1))]),
728                Bound::Excluded(vec![Some(ScalarImpl::Int32(5))])
729            ),
730            (
731                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
732                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
733            ),
734            &order_types
735        ));
736
737        // (Included, Included) vs (Included, Included)
738        assert!(range_overlap_check(
739            (
740                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
741                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
742            ),
743            (
744                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
745                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
746            ),
747            &order_types
748        ));
749
750        // (Included, Included) vs (Included, Included)
751        assert!(range_overlap_check(
752            (
753                Bound::Included(vec![Some(ScalarImpl::Int32(3)), Some(ScalarImpl::Int32(3))]),
754                Bound::Included(vec![Some(ScalarImpl::Int32(7)), Some(ScalarImpl::Int32(7))])
755            ),
756            (
757                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
758                Bound::Included(vec![Some(ScalarImpl::Int32(5))])
759            ),
760            &order_types
761        ));
762
763        // (Included, Included) vs (Included, Included)
764        assert!(!range_overlap_check(
765            (
766                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
767                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
768            ),
769            (
770                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
771                Bound::Included(vec![Some(ScalarImpl::Int32(2))])
772            ),
773            &order_types
774        ));
775
776        // (Included, Included) vs (Included, Included)
777        assert!(range_overlap_check(
778            (
779                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
780                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
781            ),
782            (
783                Bound::Included(vec![Some(ScalarImpl::Int32(3))]),
784                Bound::Included(vec![Some(ScalarImpl::Int32(7))])
785            ),
786            &order_types
787        ));
788
789        // (Included, Included) vs (Excluded, Included)
790        assert!(!range_overlap_check(
791            (
792                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
793                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
794            ),
795            (
796                Bound::Excluded(vec![Some(ScalarImpl::Int32(3))]),
797                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
798            ),
799            &order_types
800        ));
801
802        // (Included, Included) vs (Included, Included)
803        assert!(range_overlap_check(
804            (
805                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
806                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
807            ),
808            (
809                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
810                Bound::Excluded(vec![Some(ScalarImpl::Int32(7))])
811            ),
812            &order_types
813        ));
814
815        assert!(!range_overlap_check(
816            (
817                Bound::Unbounded,
818                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
819            ),
820            (
821                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
822                Bound::Unbounded,
823            ),
824            &order_types
825        ));
826
827        assert!(range_overlap_check(
828            (
829                Bound::Unbounded,
830                Bound::Included(vec![Some(ScalarImpl::Int32(10))])
831            ),
832            (
833                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
834                Bound::Unbounded,
835            ),
836            &order_types
837        ));
838
839        assert!(range_overlap_check(
840            (Bound::Unbounded, Bound::Unbounded,),
841            (
842                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
843                Bound::Unbounded,
844            ),
845            &order_types
846        ));
847
848        assert!(range_overlap_check(
849            (Bound::Unbounded, Bound::Unbounded),
850            (Bound::Unbounded, Bound::Unbounded),
851            &order_types
852        ));
853
854        assert!(!range_overlap_check(
855            (
856                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
857                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
858            ),
859            (
860                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
861                Bound::Unbounded,
862            ),
863            &order_types
864        ));
865
866        assert!(range_overlap_check(
867            (
868                Bound::Included(vec![Some(ScalarImpl::Int32(1))]),
869                Bound::Included(vec![Some(ScalarImpl::Int32(3))])
870            ),
871            (
872                Bound::Unbounded,
873                Bound::Included(vec![Some(ScalarImpl::Int32(5))]),
874            ),
875            &order_types
876        ));
877    }
878    #[test]
879    fn test_overlap_and_union_with_prefix_bounds() {
880        let order_types = vec![OrderType::ascending(), OrderType::ascending()];
881        let int = |v: i32| Some(ScalarImpl::Int32(v));
882        let range = |eq_conds: Vec<Datum>, range| ScanRange { eq_conds, range };
883
884        // `a = 1` covers `a = 1 AND b > 5`.
885        let a_eq_1 = range(vec![int(1)], full_range());
886        let a_eq_1_b_gt_5 = range(
887            vec![int(1)],
888            (Bound::Excluded(vec![int(5)]), Bound::Unbounded),
889        );
890        assert!(ScanRange::is_overlap(&a_eq_1, &a_eq_1_b_gt_5, &order_types));
891        assert_eq!(
892            a_eq_1.clone().union(a_eq_1_b_gt_5.clone(), &order_types),
893            a_eq_1
894        );
895
896        // `a BETWEEN 0 AND 100` covers `a = 1 AND b > 5`.
897        let a_0_100 = range(
898            vec![],
899            (
900                Bound::Included(vec![int(0)]),
901                Bound::Included(vec![int(100)]),
902            ),
903        );
904        assert!(ScanRange::is_overlap(
905            &a_eq_1_b_gt_5,
906            &a_0_100,
907            &order_types
908        ));
909        assert_eq!(
910            a_eq_1_b_gt_5.clone().union(a_0_100.clone(), &order_types),
911            a_0_100
912        );
913
914        // `a >= 1` covers `(a, b) > (1, 5)`.
915        let a_b_gt_1_5 = range(
916            vec![],
917            (Bound::Excluded(vec![int(1), int(5)]), Bound::Unbounded),
918        );
919        let a_ge_1 = range(vec![], (Bound::Included(vec![int(1)]), Bound::Unbounded));
920        assert_eq!(
921            a_b_gt_1_5.clone().union(a_ge_1.clone(), &order_types),
922            a_ge_1
923        );
924        assert_eq!(
925            ScanRange::cmp_start(&a_ge_1, &a_b_gt_1_5, &order_types),
926            Ordering::Less
927        );
928
929        // `a > 0` skips NULLs, so it does not overlap with `a IS NULL`.
930        let a_is_null = range(vec![None], full_range());
931        let a_gt_0 = range(vec![], (Bound::Excluded(vec![int(0)]), Bound::Unbounded));
932        assert!(!ScanRange::is_overlap(&a_is_null, &a_gt_0, &order_types));
933
934        // Otherwise, the union is widened to the common prefix of `eq_conds`.
935        let a_b_gt_1_6 = range(
936            vec![],
937            (Bound::Excluded(vec![int(1), int(6)]), Bound::Unbounded),
938        );
939        assert!(ScanRange::is_overlap(
940            &a_eq_1_b_gt_5,
941            &a_b_gt_1_6,
942            &order_types
943        ));
944        assert_eq!(
945            a_eq_1_b_gt_5.union(a_b_gt_1_6, &order_types),
946            ScanRange::full_table_scan()
947        );
948    }
949}
risingwave_common/util/scan_range.rs

risingwave_common/util/
scan_range.rs
