risingwave_meta/hummock/compaction/
overlap_strategy.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;
16use std::fmt::Debug;
17use std::ops::Range;
18
19use itertools::Itertools;
20use risingwave_hummock_sdk::KeyComparator;
21use risingwave_hummock_sdk::key_range::{KeyRange, KeyRangeCommon};
22use risingwave_hummock_sdk::sstable_info::SstableInfo;
23
24pub trait OverlapInfo: Debug {
25    fn check_overlap(&self, a: &SstableInfo) -> bool;
26    fn check_multiple_overlap(&self, others: &[SstableInfo]) -> Range<usize>;
27    fn check_multiple_include(&self, others: &[SstableInfo]) -> Range<usize>;
28    fn update(&mut self, range: &KeyRange);
29}
30
31pub trait OverlapStrategy: Send + Sync {
32    fn check_overlap(&self, a: &SstableInfo, b: &SstableInfo) -> bool;
33    fn check_base_level_overlap(
34        &self,
35        tables: &[SstableInfo],
36        others: &[SstableInfo],
37    ) -> Vec<SstableInfo> {
38        let mut info = self.create_overlap_info();
39        for table in tables {
40            info.update(&table.key_range);
41        }
42        let range = info.check_multiple_overlap(others);
43        if range.is_empty() {
44            vec![]
45        } else {
46            others[range].to_vec()
47        }
48    }
49    fn check_overlap_with_range(
50        &self,
51        range: &KeyRange,
52        others: &[SstableInfo],
53    ) -> Vec<SstableInfo> {
54        if others.is_empty() {
55            return vec![];
56        }
57        let mut info = self.create_overlap_info();
58        info.update(range);
59        others
60            .iter()
61            .filter(|table| info.check_overlap(table))
62            .cloned()
63            .collect_vec()
64    }
65
66    fn create_overlap_info(&self) -> Box<dyn OverlapInfo>;
67}
68
69#[derive(Default, Debug)]
70pub struct RangeOverlapInfo {
71    target_range: Option<KeyRange>,
72}
73
74impl OverlapInfo for RangeOverlapInfo {
75    fn check_overlap(&self, a: &SstableInfo) -> bool {
76        match self.target_range.as_ref() {
77            Some(range) => check_table_overlap(range, a),
78            None => false,
79        }
80    }
81
82    fn check_multiple_overlap(&self, others: &[SstableInfo]) -> Range<usize> {
83        match self.target_range.as_ref() {
84            Some(key_range) => {
85                let overlap_begin = others.partition_point(|table_status| {
86                    table_status.key_range.compare_right_with(&key_range.left)
87                        == cmp::Ordering::Less
88                });
89                if overlap_begin >= others.len() {
90                    return overlap_begin..overlap_begin;
91                }
92                let overlap_end = others.partition_point(|table_status| {
93                    key_range.compare_right_with(&table_status.key_range.left)
94                        != cmp::Ordering::Less
95                });
96                overlap_begin..overlap_end
97            }
98            None => others.len()..others.len(),
99        }
100    }
101
102    fn check_multiple_include(&self, others: &[SstableInfo]) -> Range<usize> {
103        match self.target_range.as_ref() {
104            Some(key_range) => {
105                let overlap_begin = others.partition_point(|table_status| {
106                    KeyComparator::compare_encoded_full_key(
107                        &table_status.key_range.left,
108                        &key_range.left,
109                    ) == cmp::Ordering::Less
110                });
111                if overlap_begin >= others.len() {
112                    return overlap_begin..overlap_begin;
113                }
114                let mut overlap_end = overlap_begin;
115                for table in &others[overlap_begin..] {
116                    if key_range.compare_right_with(&table.key_range.right) == cmp::Ordering::Less {
117                        break;
118                    }
119                    overlap_end += 1;
120                }
121                overlap_begin..overlap_end
122            }
123            None => others.len()..others.len(),
124        }
125    }
126
127    fn update(&mut self, range: &KeyRange) {
128        let other = range;
129        if let Some(range) = self.target_range.as_mut() {
130            range.full_key_extend(other);
131            return;
132        }
133        self.target_range = Some(other.clone());
134    }
135}
136
137#[derive(Default)]
138pub struct RangeOverlapStrategy {}
139
140impl OverlapStrategy for RangeOverlapStrategy {
141    fn check_overlap(&self, a: &SstableInfo, b: &SstableInfo) -> bool {
142        check_table_overlap(&a.key_range, b)
143    }
144
145    fn create_overlap_info(&self) -> Box<dyn OverlapInfo> {
146        Box::<RangeOverlapInfo>::default()
147    }
148}
149
150fn check_table_overlap(key_range: &KeyRange, table: &SstableInfo) -> bool {
151    key_range.sstable_overlap(&table.key_range)
152}
risingwave_meta/hummock/compaction/overlap_strategy.rs

risingwave_meta/hummock/compaction/
overlap_strategy.rs
