risingwave_storage/hummock/iterator/
backward_concat.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 crate::hummock::BackwardSstableIterator;
16use crate::hummock::iterator::concat_inner::ConcatIteratorInner;
17
18/// Iterates backwards on multiple non-overlapping tables.
19pub type BackwardConcatIterator = ConcatIteratorInner<BackwardSstableIterator>;
20
21/// Mirrors the tests used for `SstableIterator`
22#[cfg(test)]
23mod tests {
24    use std::sync::Arc;
25
26    use super::*;
27    use crate::hummock::iterator::HummockIterator;
28    use crate::hummock::iterator::test_utils::{
29        TEST_KEYS_COUNT, default_builder_opt_for_test, gen_iterator_test_sstable_info,
30        iterator_test_key_of, iterator_test_value_of, mock_sstable_store,
31    };
32    use crate::hummock::sstable::SstableIteratorReadOptions;
33
34    #[tokio::test]
35    async fn test_backward_concat_iterator() {
36        let sstable_store = mock_sstable_store().await;
37        let table0 = gen_iterator_test_sstable_info(
38            0,
39            default_builder_opt_for_test(),
40            |x| x,
41            sstable_store.clone(),
42            TEST_KEYS_COUNT,
43        )
44        .await;
45        let table1 = gen_iterator_test_sstable_info(
46            1,
47            default_builder_opt_for_test(),
48            |x| TEST_KEYS_COUNT + x,
49            sstable_store.clone(),
50            TEST_KEYS_COUNT,
51        )
52        .await;
53        let table2 = gen_iterator_test_sstable_info(
54            2,
55            default_builder_opt_for_test(),
56            |x| TEST_KEYS_COUNT * 2 + x,
57            sstable_store.clone(),
58            TEST_KEYS_COUNT,
59        )
60        .await;
61        let mut iter = BackwardConcatIterator::new(
62            vec![table2, table1, table0],
63            sstable_store,
64            Arc::new(SstableIteratorReadOptions::default()),
65        );
66        let mut i = TEST_KEYS_COUNT * 3;
67        iter.rewind().await.unwrap();
68
69        while iter.is_valid() {
70            i -= 1;
71            let key = iter.key();
72            let val = iter.value();
73            assert_eq!(key, iterator_test_key_of(i).to_ref());
74            assert_eq!(
75                val.into_user_value().unwrap(),
76                iterator_test_value_of(i).as_slice()
77            );
78            iter.next().await.unwrap();
79        }
80        assert_eq!(i, 0);
81        assert!(!iter.is_valid());
82
83        iter.rewind().await.unwrap();
84        let key = iter.key();
85        let val = iter.value();
86        assert_eq!(key, iterator_test_key_of(TEST_KEYS_COUNT * 3 - 1).to_ref());
87        assert_eq!(
88            val.into_user_value().unwrap(),
89            iterator_test_value_of(TEST_KEYS_COUNT * 3 - 1).as_slice()
90        );
91    }
92
93    #[tokio::test]
94    async fn test_backward_concat_seek_exists() {
95        let sstable_store = mock_sstable_store().await;
96        let table1 = gen_iterator_test_sstable_info(
97            0,
98            default_builder_opt_for_test(),
99            |x| TEST_KEYS_COUNT + x,
100            sstable_store.clone(),
101            TEST_KEYS_COUNT,
102        )
103        .await;
104        let table2 = gen_iterator_test_sstable_info(
105            1,
106            default_builder_opt_for_test(),
107            |x| TEST_KEYS_COUNT * 2 + x,
108            sstable_store.clone(),
109            TEST_KEYS_COUNT,
110        )
111        .await;
112        let table3 = gen_iterator_test_sstable_info(
113            2,
114            default_builder_opt_for_test(),
115            |x| TEST_KEYS_COUNT * 3 + x,
116            sstable_store.clone(),
117            TEST_KEYS_COUNT,
118        )
119        .await;
120        let mut iter = BackwardConcatIterator::new(
121            vec![table3, table2, table1],
122            sstable_store,
123            Arc::new(SstableIteratorReadOptions::default()),
124        );
125
126        iter.seek(iterator_test_key_of(2 * TEST_KEYS_COUNT + 1).to_ref())
127            .await
128            .unwrap();
129
130        let key = iter.key();
131        let val = iter.value();
132        assert_eq!(key, iterator_test_key_of(2 * TEST_KEYS_COUNT + 1).to_ref());
133        assert_eq!(
134            val.into_user_value().unwrap(),
135            iterator_test_value_of(2 * TEST_KEYS_COUNT + 1).as_slice()
136        );
137
138        // Left edge case
139        iter.seek(iterator_test_key_of(TEST_KEYS_COUNT).to_ref())
140            .await
141            .unwrap();
142        let key = iter.key();
143        let val = iter.value();
144        assert_eq!(key, iterator_test_key_of(TEST_KEYS_COUNT).to_ref());
145        assert_eq!(
146            val.into_user_value().unwrap(),
147            iterator_test_value_of(TEST_KEYS_COUNT).as_slice()
148        );
149
150        // Right edge case
151        iter.seek(iterator_test_key_of(4 * TEST_KEYS_COUNT - 1).to_ref())
152            .await
153            .unwrap();
154
155        let key = iter.key();
156        let val = iter.value();
157        assert_eq!(key, iterator_test_key_of(4 * TEST_KEYS_COUNT - 1).to_ref());
158        assert_eq!(
159            val.into_user_value().unwrap(),
160            iterator_test_value_of(4 * TEST_KEYS_COUNT - 1).as_slice()
161        );
162
163        // Right overflow case
164        iter.seek(iterator_test_key_of(TEST_KEYS_COUNT - 1).to_ref())
165            .await
166            .unwrap();
167        assert!(!iter.is_valid());
168    }
169
170    #[tokio::test]
171    async fn test_backward_concat_seek_not_exists() {
172        let sstable_store = mock_sstable_store().await;
173        let table0 = gen_iterator_test_sstable_info(
174            0,
175            default_builder_opt_for_test(),
176            |x| x * 2,
177            sstable_store.clone(),
178            TEST_KEYS_COUNT,
179        )
180        .await;
181        let table1 = gen_iterator_test_sstable_info(
182            1,
183            default_builder_opt_for_test(),
184            |x| (TEST_KEYS_COUNT + x) * 2,
185            sstable_store.clone(),
186            TEST_KEYS_COUNT,
187        )
188        .await;
189        let table2 = gen_iterator_test_sstable_info(
190            2,
191            default_builder_opt_for_test(),
192            |x| (TEST_KEYS_COUNT * 2 + x) * 2,
193            sstable_store.clone(),
194            TEST_KEYS_COUNT,
195        )
196        .await;
197        let mut iter = BackwardConcatIterator::new(
198            vec![table2, table1, table0],
199            sstable_store,
200            Arc::new(SstableIteratorReadOptions::default()),
201        );
202
203        iter.seek(iterator_test_key_of(TEST_KEYS_COUNT * 2 + 1).to_ref())
204            .await
205            .unwrap();
206
207        let key = iter.key();
208        let val = iter.value();
209        assert_eq!(key, iterator_test_key_of(TEST_KEYS_COUNT * 2).to_ref());
210        assert_eq!(
211            val.into_user_value().unwrap(),
212            iterator_test_value_of(TEST_KEYS_COUNT * 2).as_slice()
213        );
214
215        // table1 last
216        iter.seek(iterator_test_key_of(TEST_KEYS_COUNT * 4 - 1).to_ref())
217            .await
218            .unwrap();
219
220        let key = iter.key();
221        let val = iter.value();
222        assert_eq!(
223            key,
224            iterator_test_key_of((TEST_KEYS_COUNT + 9) * 2).to_ref()
225        );
226        assert_eq!(
227            val.into_user_value().unwrap(),
228            iterator_test_value_of((TEST_KEYS_COUNT + 9) * 2).as_slice()
229        );
230    }
231}
risingwave_storage/hummock/iterator/backward_concat.rs

risingwave_storage/hummock/iterator/
backward_concat.rs
