risingwave_meta/hummock/compaction/
overlap_strategy.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;
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    /// Find overlaps in ordered, non-overlapping `others`.
67    /// `previous` may contain the preceding query's result on the same `others`;
68    /// both query boundaries must be nondecreasing. Strategies may ignore the hint.
69    fn check_overlap_range_with_hint(
70        &self,
71        range: &KeyRange,
72        others: &[SstableInfo],
73        _previous: Option<Range<usize>>,
74    ) -> Range<usize> {
75        let mut info = self.create_overlap_info();
76        info.update(range);
77        info.check_multiple_overlap(others)
78    }
79
80    fn create_overlap_info(&self) -> Box<dyn OverlapInfo>;
81}
82
83#[derive(Default, Debug)]
84pub struct RangeOverlapInfo {
85    target_range: Option<KeyRange>,
86}
87
88impl OverlapInfo for RangeOverlapInfo {
89    fn check_overlap(&self, a: &SstableInfo) -> bool {
90        match self.target_range.as_ref() {
91            Some(range) => check_table_overlap(range, a),
92            None => false,
93        }
94    }
95
96    fn check_multiple_overlap(&self, others: &[SstableInfo]) -> Range<usize> {
97        match self.target_range.as_ref() {
98            Some(key_range) => {
99                let overlap_begin = others.partition_point(|table_status| {
100                    table_status.key_range.compare_right_with(&key_range.left)
101                        == cmp::Ordering::Less
102                });
103                if overlap_begin >= others.len() {
104                    return overlap_begin..overlap_begin;
105                }
106                let overlap_end = others.partition_point(|table_status| {
107                    key_range.compare_right_with(&table_status.key_range.left)
108                        != cmp::Ordering::Less
109                });
110                overlap_begin..overlap_end
111            }
112            None => others.len()..others.len(),
113        }
114    }
115
116    fn check_multiple_include(&self, others: &[SstableInfo]) -> Range<usize> {
117        match self.target_range.as_ref() {
118            Some(key_range) => {
119                let overlap_begin = others.partition_point(|table_status| {
120                    KeyComparator::compare_encoded_full_key(
121                        &table_status.key_range.left,
122                        &key_range.left,
123                    ) == cmp::Ordering::Less
124                });
125                if overlap_begin >= others.len() {
126                    return overlap_begin..overlap_begin;
127                }
128                let mut overlap_end = overlap_begin;
129                for table in &others[overlap_begin..] {
130                    if key_range.compare_right_with(&table.key_range.right) == cmp::Ordering::Less {
131                        break;
132                    }
133                    overlap_end += 1;
134                }
135                overlap_begin..overlap_end
136            }
137            None => others.len()..others.len(),
138        }
139    }
140
141    fn update(&mut self, range: &KeyRange) {
142        let other = range;
143        if let Some(range) = self.target_range.as_mut() {
144            range.full_key_extend(other);
145            return;
146        }
147        self.target_range = Some(other.clone());
148    }
149}
150
151#[derive(Default)]
152pub struct RangeOverlapStrategy {}
153
154impl OverlapStrategy for RangeOverlapStrategy {
155    fn check_overlap(&self, a: &SstableInfo, b: &SstableInfo) -> bool {
156        check_table_overlap(&a.key_range, b)
157    }
158
159    fn check_overlap_range_with_hint(
160        &self,
161        range: &KeyRange,
162        others: &[SstableInfo],
163        previous: Option<Range<usize>>,
164    ) -> Range<usize> {
165        let before = |table: &SstableInfo| {
166            table.key_range.compare_right_with(&range.left) == cmp::Ordering::Less
167        };
168        let overlaps = |table: &SstableInfo| {
169            range.compare_right_with(&table.key_range.left) != cmp::Ordering::Less
170        };
171        if let Some(previous) = previous {
172            let begin = previous.start + partition_point_forward(&others[previous.start..], before);
173            let end = previous.end.max(begin);
174            let end = end + partition_point_forward(&others[end..], overlaps);
175            begin..end
176        } else {
177            // A first query near the end of a large level still costs O(log M).
178            let begin = others.partition_point(before);
179            let end = begin + others[begin..].partition_point(overlaps);
180            begin..end
181        }
182    }
183
184    fn create_overlap_info(&self) -> Box<dyn OverlapInfo> {
185        Box::<RangeOverlapInfo>::default()
186    }
187}
188
189fn check_table_overlap(key_range: &KeyRange, table: &SstableInfo) -> bool {
190    key_range.sstable_overlap(&table.key_range)
191}
192
193// Bracket the boundary exponentially, then binary-search the bracket. Starting
194// at the previous boundary costs O(1 + log(1 + advancement)), without linearly
195// scanning irrelevant SSTs when source ranges are sparse.
196fn partition_point_forward<T>(items: &[T], mut pred: impl FnMut(&T) -> bool) -> usize {
197    if items.is_empty() || !pred(&items[0]) {
198        return 0;
199    }
200    let mut lo = 1;
201    let mut hi = 2.min(items.len());
202    while hi < items.len() && pred(&items[hi - 1]) {
203        lo = hi;
204        hi = hi.saturating_mul(2).min(items.len());
205    }
206    lo + items[lo..hi].partition_point(pred)
207}
risingwave_meta/hummock/compaction/overlap_strategy.rs

risingwave_meta/hummock/compaction/
overlap_strategy.rs
