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, table: &SstableInfo);
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);
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_tables(
50        &self,
51        tables: &[SstableInfo],
52        others: &[SstableInfo],
53    ) -> Vec<SstableInfo> {
54        if tables.is_empty() || others.is_empty() {
55            return vec![];
56        }
57        let mut info = self.create_overlap_info();
58        for table in tables {
59            info.update(table);
60        }
61        others
62            .iter()
63            .filter(|table| info.check_overlap(table))
64            .cloned()
65            .collect_vec()
66    }
67
68    fn create_overlap_info(&self) -> Box<dyn OverlapInfo>;
69}
70
71#[derive(Default, Debug)]
72pub struct RangeOverlapInfo {
73    target_range: Option<KeyRange>,
74}
75
76impl OverlapInfo for RangeOverlapInfo {
77    fn check_overlap(&self, a: &SstableInfo) -> bool {
78        match self.target_range.as_ref() {
79            Some(range) => check_table_overlap(range, a),
80            None => false,
81        }
82    }
83
84    fn check_multiple_overlap(&self, others: &[SstableInfo]) -> Range<usize> {
85        match self.target_range.as_ref() {
86            Some(key_range) => {
87                let overlap_begin = others.partition_point(|table_status| {
88                    table_status.key_range.compare_right_with(&key_range.left)
89                        == cmp::Ordering::Less
90                });
91                if overlap_begin >= others.len() {
92                    return overlap_begin..overlap_begin;
93                }
94                let overlap_end = others.partition_point(|table_status| {
95                    key_range.compare_right_with(&table_status.key_range.left)
96                        != cmp::Ordering::Less
97                });
98                overlap_begin..overlap_end
99            }
100            None => others.len()..others.len(),
101        }
102    }
103
104    fn check_multiple_include(&self, others: &[SstableInfo]) -> Range<usize> {
105        match self.target_range.as_ref() {
106            Some(key_range) => {
107                let overlap_begin = others.partition_point(|table_status| {
108                    KeyComparator::compare_encoded_full_key(
109                        &table_status.key_range.left,
110                        &key_range.left,
111                    ) == cmp::Ordering::Less
112                });
113                if overlap_begin >= others.len() {
114                    return overlap_begin..overlap_begin;
115                }
116                let mut overlap_end = overlap_begin;
117                for table in &others[overlap_begin..] {
118                    if key_range.compare_right_with(&table.key_range.right) == cmp::Ordering::Less {
119                        break;
120                    }
121                    overlap_end += 1;
122                }
123                overlap_begin..overlap_end
124            }
125            None => others.len()..others.len(),
126        }
127    }
128
129    fn update(&mut self, table: &SstableInfo) {
130        let other = &table.key_range;
131        if let Some(range) = self.target_range.as_mut() {
132            range.full_key_extend(other);
133            return;
134        }
135        self.target_range = Some(other.clone());
136    }
137}
138
139#[derive(Default)]
140pub struct RangeOverlapStrategy {}
141
142impl OverlapStrategy for RangeOverlapStrategy {
143    fn check_overlap(&self, a: &SstableInfo, b: &SstableInfo) -> bool {
144        check_table_overlap(&a.key_range, b)
145    }
146
147    fn create_overlap_info(&self) -> Box<dyn OverlapInfo> {
148        Box::<RangeOverlapInfo>::default()
149    }
150}
151
152fn check_table_overlap(key_range: &KeyRange, table: &SstableInfo) -> bool {
153    key_range.sstable_overlap(&table.key_range)
154}
risingwave_meta/hummock/compaction/overlap_strategy.rs

risingwave_meta/hummock/compaction/
overlap_strategy.rs
