]>
Commit | Line | Data |
---|---|---|
494da23a | 1 | // Copyright (c) 2018-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae | 5 | |
494da23a TL |
6 | #include "db/range_del_aggregator.h" |
7 | ||
8 | #include <memory> | |
9 | #include <string> | |
10 | #include <vector> | |
7c673cae FG |
11 | |
12 | #include "db/db_test_util.h" | |
494da23a TL |
13 | #include "db/dbformat.h" |
14 | #include "db/range_tombstone_fragmenter.h" | |
f67539c2 | 15 | #include "test_util/testutil.h" |
7c673cae | 16 | |
f67539c2 | 17 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
18 | |
19 | class RangeDelAggregatorTest : public testing::Test {}; | |
20 | ||
21 | namespace { | |
22 | ||
11fdf7f2 TL |
23 | static auto bytewise_icmp = InternalKeyComparator(BytewiseComparator()); |
24 | ||
494da23a TL |
25 | std::unique_ptr<InternalIterator> MakeRangeDelIter( |
26 | const std::vector<RangeTombstone>& range_dels) { | |
11fdf7f2 TL |
27 | std::vector<std::string> keys, values; |
28 | for (const auto& range_del : range_dels) { | |
29 | auto key_and_value = range_del.Serialize(); | |
30 | keys.push_back(key_and_value.first.Encode().ToString()); | |
31 | values.push_back(key_and_value.second.ToString()); | |
32 | } | |
494da23a | 33 | return std::unique_ptr<test::VectorIterator>( |
11fdf7f2 | 34 | new test::VectorIterator(keys, values)); |
11fdf7f2 TL |
35 | } |
36 | ||
494da23a TL |
37 | std::vector<std::unique_ptr<FragmentedRangeTombstoneList>> |
38 | MakeFragmentedTombstoneLists( | |
39 | const std::vector<std::vector<RangeTombstone>>& range_dels_list) { | |
40 | std::vector<std::unique_ptr<FragmentedRangeTombstoneList>> fragment_lists; | |
41 | for (const auto& range_dels : range_dels_list) { | |
42 | auto range_del_iter = MakeRangeDelIter(range_dels); | |
43 | fragment_lists.emplace_back(new FragmentedRangeTombstoneList( | |
44 | std::move(range_del_iter), bytewise_icmp)); | |
45 | } | |
46 | return fragment_lists; | |
11fdf7f2 TL |
47 | } |
48 | ||
494da23a TL |
49 | struct TruncatedIterScanTestCase { |
50 | ParsedInternalKey start; | |
51 | ParsedInternalKey end; | |
52 | SequenceNumber seq; | |
53 | }; | |
54 | ||
55 | struct TruncatedIterSeekTestCase { | |
56 | Slice target; | |
57 | ParsedInternalKey start; | |
58 | ParsedInternalKey end; | |
59 | SequenceNumber seq; | |
60 | bool invalid; | |
61 | }; | |
62 | ||
63 | struct ShouldDeleteTestCase { | |
64 | ParsedInternalKey lookup_key; | |
65 | bool result; | |
66 | }; | |
67 | ||
68 | struct IsRangeOverlappedTestCase { | |
69 | Slice start; | |
70 | Slice end; | |
71 | bool result; | |
72 | }; | |
73 | ||
74 | ParsedInternalKey UncutEndpoint(const Slice& s) { | |
75 | return ParsedInternalKey(s, kMaxSequenceNumber, kTypeRangeDeletion); | |
76 | } | |
77 | ||
78 | ParsedInternalKey InternalValue(const Slice& key, SequenceNumber seq) { | |
79 | return ParsedInternalKey(key, seq, kTypeValue); | |
80 | } | |
81 | ||
82 | void VerifyIterator( | |
83 | TruncatedRangeDelIterator* iter, const InternalKeyComparator& icmp, | |
84 | const std::vector<TruncatedIterScanTestCase>& expected_range_dels) { | |
85 | // Test forward iteration. | |
86 | iter->SeekToFirst(); | |
87 | for (size_t i = 0; i < expected_range_dels.size(); i++, iter->Next()) { | |
88 | ASSERT_TRUE(iter->Valid()); | |
89 | EXPECT_EQ(0, icmp.Compare(iter->start_key(), expected_range_dels[i].start)); | |
90 | EXPECT_EQ(0, icmp.Compare(iter->end_key(), expected_range_dels[i].end)); | |
91 | EXPECT_EQ(expected_range_dels[i].seq, iter->seq()); | |
92 | } | |
93 | EXPECT_FALSE(iter->Valid()); | |
94 | ||
95 | // Test reverse iteration. | |
96 | iter->SeekToLast(); | |
97 | std::vector<TruncatedIterScanTestCase> reverse_expected_range_dels( | |
98 | expected_range_dels.rbegin(), expected_range_dels.rend()); | |
99 | for (size_t i = 0; i < reverse_expected_range_dels.size(); | |
100 | i++, iter->Prev()) { | |
101 | ASSERT_TRUE(iter->Valid()); | |
102 | EXPECT_EQ(0, icmp.Compare(iter->start_key(), | |
103 | reverse_expected_range_dels[i].start)); | |
104 | EXPECT_EQ( | |
105 | 0, icmp.Compare(iter->end_key(), reverse_expected_range_dels[i].end)); | |
106 | EXPECT_EQ(reverse_expected_range_dels[i].seq, iter->seq()); | |
11fdf7f2 | 107 | } |
494da23a | 108 | EXPECT_FALSE(iter->Valid()); |
11fdf7f2 TL |
109 | } |
110 | ||
494da23a TL |
111 | void VerifySeek(TruncatedRangeDelIterator* iter, |
112 | const InternalKeyComparator& icmp, | |
113 | const std::vector<TruncatedIterSeekTestCase>& test_cases) { | |
114 | for (const auto& test_case : test_cases) { | |
115 | iter->Seek(test_case.target); | |
116 | if (test_case.invalid) { | |
117 | ASSERT_FALSE(iter->Valid()); | |
118 | } else { | |
119 | ASSERT_TRUE(iter->Valid()); | |
120 | EXPECT_EQ(0, icmp.Compare(iter->start_key(), test_case.start)); | |
121 | EXPECT_EQ(0, icmp.Compare(iter->end_key(), test_case.end)); | |
122 | EXPECT_EQ(test_case.seq, iter->seq()); | |
7c673cae FG |
123 | } |
124 | } | |
494da23a | 125 | } |
11fdf7f2 | 126 | |
494da23a TL |
127 | void VerifySeekForPrev( |
128 | TruncatedRangeDelIterator* iter, const InternalKeyComparator& icmp, | |
129 | const std::vector<TruncatedIterSeekTestCase>& test_cases) { | |
130 | for (const auto& test_case : test_cases) { | |
131 | iter->SeekForPrev(test_case.target); | |
132 | if (test_case.invalid) { | |
133 | ASSERT_FALSE(iter->Valid()); | |
11fdf7f2 | 134 | } else { |
494da23a TL |
135 | ASSERT_TRUE(iter->Valid()); |
136 | EXPECT_EQ(0, icmp.Compare(iter->start_key(), test_case.start)); | |
137 | EXPECT_EQ(0, icmp.Compare(iter->end_key(), test_case.end)); | |
138 | EXPECT_EQ(test_case.seq, iter->seq()); | |
11fdf7f2 TL |
139 | } |
140 | } | |
7c673cae FG |
141 | } |
142 | ||
494da23a TL |
143 | void VerifyShouldDelete(RangeDelAggregator* range_del_agg, |
144 | const std::vector<ShouldDeleteTestCase>& test_cases) { | |
145 | for (const auto& test_case : test_cases) { | |
146 | EXPECT_EQ( | |
147 | test_case.result, | |
148 | range_del_agg->ShouldDelete( | |
149 | test_case.lookup_key, RangeDelPositioningMode::kForwardTraversal)); | |
150 | } | |
151 | for (auto it = test_cases.rbegin(); it != test_cases.rend(); ++it) { | |
152 | const auto& test_case = *it; | |
153 | EXPECT_EQ( | |
154 | test_case.result, | |
155 | range_del_agg->ShouldDelete( | |
156 | test_case.lookup_key, RangeDelPositioningMode::kBackwardTraversal)); | |
157 | } | |
7c673cae FG |
158 | } |
159 | ||
494da23a TL |
160 | void VerifyIsRangeOverlapped( |
161 | ReadRangeDelAggregator* range_del_agg, | |
162 | const std::vector<IsRangeOverlappedTestCase>& test_cases) { | |
163 | for (const auto& test_case : test_cases) { | |
164 | EXPECT_EQ(test_case.result, | |
165 | range_del_agg->IsRangeOverlapped(test_case.start, test_case.end)); | |
166 | } | |
7c673cae FG |
167 | } |
168 | ||
494da23a TL |
169 | void CheckIterPosition(const RangeTombstone& tombstone, |
170 | const FragmentedRangeTombstoneIterator* iter) { | |
171 | // Test InternalIterator interface. | |
172 | EXPECT_EQ(tombstone.start_key_, ExtractUserKey(iter->key())); | |
173 | EXPECT_EQ(tombstone.end_key_, iter->value()); | |
174 | EXPECT_EQ(tombstone.seq_, iter->seq()); | |
175 | ||
176 | // Test FragmentedRangeTombstoneIterator interface. | |
177 | EXPECT_EQ(tombstone.start_key_, iter->start_key()); | |
178 | EXPECT_EQ(tombstone.end_key_, iter->end_key()); | |
179 | EXPECT_EQ(tombstone.seq_, GetInternalKeySeqno(iter->key())); | |
7c673cae FG |
180 | } |
181 | ||
494da23a TL |
182 | void VerifyFragmentedRangeDels( |
183 | FragmentedRangeTombstoneIterator* iter, | |
184 | const std::vector<RangeTombstone>& expected_tombstones) { | |
185 | iter->SeekToFirst(); | |
186 | for (size_t i = 0; i < expected_tombstones.size(); i++, iter->Next()) { | |
187 | ASSERT_TRUE(iter->Valid()); | |
188 | CheckIterPosition(expected_tombstones[i], iter); | |
189 | } | |
190 | EXPECT_FALSE(iter->Valid()); | |
7c673cae FG |
191 | } |
192 | ||
494da23a | 193 | } // namespace |
11fdf7f2 | 194 | |
494da23a TL |
195 | TEST_F(RangeDelAggregatorTest, EmptyTruncatedIter) { |
196 | auto range_del_iter = MakeRangeDelIter({}); | |
197 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
198 | bytewise_icmp); | |
199 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
200 | new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp, | |
201 | kMaxSequenceNumber)); | |
7c673cae | 202 | |
494da23a TL |
203 | TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, nullptr, |
204 | nullptr); | |
7c673cae | 205 | |
494da23a TL |
206 | iter.SeekToFirst(); |
207 | ASSERT_FALSE(iter.Valid()); | |
7c673cae | 208 | |
494da23a TL |
209 | iter.SeekToLast(); |
210 | ASSERT_FALSE(iter.Valid()); | |
7c673cae FG |
211 | } |
212 | ||
494da23a TL |
213 | TEST_F(RangeDelAggregatorTest, UntruncatedIter) { |
214 | auto range_del_iter = | |
215 | MakeRangeDelIter({{"a", "e", 10}, {"e", "g", 8}, {"j", "n", 4}}); | |
216 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
217 | bytewise_icmp); | |
218 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
219 | new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp, | |
220 | kMaxSequenceNumber)); | |
221 | ||
222 | TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, nullptr, | |
223 | nullptr); | |
224 | ||
225 | VerifyIterator(&iter, bytewise_icmp, | |
226 | {{UncutEndpoint("a"), UncutEndpoint("e"), 10}, | |
227 | {UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
228 | {UncutEndpoint("j"), UncutEndpoint("n"), 4}}); | |
229 | ||
230 | VerifySeek( | |
231 | &iter, bytewise_icmp, | |
232 | {{"d", UncutEndpoint("a"), UncutEndpoint("e"), 10}, | |
233 | {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
234 | {"ia", UncutEndpoint("j"), UncutEndpoint("n"), 4}, | |
235 | {"n", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}, | |
236 | {"", UncutEndpoint("a"), UncutEndpoint("e"), 10}}); | |
237 | ||
238 | VerifySeekForPrev( | |
239 | &iter, bytewise_icmp, | |
240 | {{"d", UncutEndpoint("a"), UncutEndpoint("e"), 10}, | |
241 | {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
242 | {"ia", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
243 | {"n", UncutEndpoint("j"), UncutEndpoint("n"), 4}, | |
244 | {"", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}}); | |
7c673cae FG |
245 | } |
246 | ||
494da23a TL |
247 | TEST_F(RangeDelAggregatorTest, UntruncatedIterWithSnapshot) { |
248 | auto range_del_iter = | |
249 | MakeRangeDelIter({{"a", "e", 10}, {"e", "g", 8}, {"j", "n", 4}}); | |
250 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
251 | bytewise_icmp); | |
252 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
253 | new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp, | |
254 | 9 /* snapshot */)); | |
255 | ||
256 | TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, nullptr, | |
257 | nullptr); | |
258 | ||
259 | VerifyIterator(&iter, bytewise_icmp, | |
260 | {{UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
261 | {UncutEndpoint("j"), UncutEndpoint("n"), 4}}); | |
262 | ||
263 | VerifySeek( | |
264 | &iter, bytewise_icmp, | |
265 | {{"d", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
266 | {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
267 | {"ia", UncutEndpoint("j"), UncutEndpoint("n"), 4}, | |
268 | {"n", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}, | |
269 | {"", UncutEndpoint("e"), UncutEndpoint("g"), 8}}); | |
270 | ||
271 | VerifySeekForPrev( | |
272 | &iter, bytewise_icmp, | |
273 | {{"d", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}, | |
274 | {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
275 | {"ia", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
276 | {"n", UncutEndpoint("j"), UncutEndpoint("n"), 4}, | |
277 | {"", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}}); | |
11fdf7f2 TL |
278 | } |
279 | ||
494da23a TL |
280 | TEST_F(RangeDelAggregatorTest, TruncatedIterPartiallyCutTombstones) { |
281 | auto range_del_iter = | |
282 | MakeRangeDelIter({{"a", "e", 10}, {"e", "g", 8}, {"j", "n", 4}}); | |
283 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
284 | bytewise_icmp); | |
285 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
286 | new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp, | |
287 | kMaxSequenceNumber)); | |
288 | ||
289 | InternalKey smallest("d", 7, kTypeValue); | |
290 | InternalKey largest("m", 9, kTypeValue); | |
291 | TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, | |
292 | &smallest, &largest); | |
293 | ||
294 | VerifyIterator(&iter, bytewise_icmp, | |
295 | {{InternalValue("d", 7), UncutEndpoint("e"), 10}, | |
296 | {UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
297 | {UncutEndpoint("j"), InternalValue("m", 8), 4}}); | |
298 | ||
299 | VerifySeek( | |
300 | &iter, bytewise_icmp, | |
301 | {{"d", InternalValue("d", 7), UncutEndpoint("e"), 10}, | |
302 | {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
303 | {"ia", UncutEndpoint("j"), InternalValue("m", 8), 4}, | |
304 | {"n", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}, | |
305 | {"", InternalValue("d", 7), UncutEndpoint("e"), 10}}); | |
306 | ||
307 | VerifySeekForPrev( | |
308 | &iter, bytewise_icmp, | |
309 | {{"d", InternalValue("d", 7), UncutEndpoint("e"), 10}, | |
310 | {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
311 | {"ia", UncutEndpoint("e"), UncutEndpoint("g"), 8}, | |
312 | {"n", UncutEndpoint("j"), InternalValue("m", 8), 4}, | |
313 | {"", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}}); | |
11fdf7f2 TL |
314 | } |
315 | ||
494da23a TL |
316 | TEST_F(RangeDelAggregatorTest, TruncatedIterFullyCutTombstones) { |
317 | auto range_del_iter = | |
318 | MakeRangeDelIter({{"a", "e", 10}, {"e", "g", 8}, {"j", "n", 4}}); | |
319 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
320 | bytewise_icmp); | |
321 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
322 | new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp, | |
323 | kMaxSequenceNumber)); | |
324 | ||
325 | InternalKey smallest("f", 7, kTypeValue); | |
326 | InternalKey largest("i", 9, kTypeValue); | |
327 | TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, | |
328 | &smallest, &largest); | |
329 | ||
330 | VerifyIterator(&iter, bytewise_icmp, | |
331 | {{InternalValue("f", 7), UncutEndpoint("g"), 8}}); | |
332 | ||
333 | VerifySeek( | |
334 | &iter, bytewise_icmp, | |
335 | {{"d", InternalValue("f", 7), UncutEndpoint("g"), 8}, | |
336 | {"f", InternalValue("f", 7), UncutEndpoint("g"), 8}, | |
337 | {"j", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}}); | |
338 | ||
339 | VerifySeekForPrev( | |
340 | &iter, bytewise_icmp, | |
341 | {{"d", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}, | |
342 | {"f", InternalValue("f", 7), UncutEndpoint("g"), 8}, | |
343 | {"j", InternalValue("f", 7), UncutEndpoint("g"), 8}}); | |
11fdf7f2 TL |
344 | } |
345 | ||
494da23a TL |
346 | TEST_F(RangeDelAggregatorTest, SingleIterInAggregator) { |
347 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, {"c", "g", 8}}); | |
348 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
349 | bytewise_icmp); | |
350 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
351 | new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp, | |
352 | kMaxSequenceNumber)); | |
353 | ||
354 | ReadRangeDelAggregator range_del_agg(&bytewise_icmp, kMaxSequenceNumber); | |
355 | range_del_agg.AddTombstones(std::move(input_iter)); | |
356 | ||
357 | VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 19), false}, | |
358 | {InternalValue("b", 9), true}, | |
359 | {InternalValue("d", 9), true}, | |
360 | {InternalValue("e", 7), true}, | |
361 | {InternalValue("g", 7), false}}); | |
362 | ||
363 | VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false}, | |
364 | {"_", "a", true}, | |
365 | {"a", "c", true}, | |
366 | {"d", "f", true}, | |
367 | {"g", "l", false}}); | |
11fdf7f2 TL |
368 | } |
369 | ||
494da23a TL |
370 | TEST_F(RangeDelAggregatorTest, MultipleItersInAggregator) { |
371 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
372 | {{{"a", "e", 10}, {"c", "g", 8}}, | |
373 | {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}}); | |
374 | ||
375 | ReadRangeDelAggregator range_del_agg(&bytewise_icmp, kMaxSequenceNumber); | |
376 | for (const auto& fragment_list : fragment_lists) { | |
377 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
378 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
379 | kMaxSequenceNumber)); | |
380 | range_del_agg.AddTombstones(std::move(input_iter)); | |
381 | } | |
382 | ||
383 | VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 19), true}, | |
384 | {InternalValue("b", 19), false}, | |
385 | {InternalValue("b", 9), true}, | |
386 | {InternalValue("d", 9), true}, | |
387 | {InternalValue("e", 7), true}, | |
388 | {InternalValue("g", 7), false}, | |
389 | {InternalValue("h", 24), true}, | |
390 | {InternalValue("i", 24), false}, | |
391 | {InternalValue("ii", 14), true}, | |
392 | {InternalValue("j", 14), false}}); | |
393 | ||
394 | VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false}, | |
395 | {"_", "a", true}, | |
396 | {"a", "c", true}, | |
397 | {"d", "f", true}, | |
398 | {"g", "l", true}, | |
399 | {"x", "y", false}}); | |
7c673cae FG |
400 | } |
401 | ||
494da23a TL |
402 | TEST_F(RangeDelAggregatorTest, MultipleItersInAggregatorWithUpperBound) { |
403 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
404 | {{{"a", "e", 10}, {"c", "g", 8}}, | |
405 | {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}}); | |
406 | ||
407 | ReadRangeDelAggregator range_del_agg(&bytewise_icmp, 19); | |
408 | for (const auto& fragment_list : fragment_lists) { | |
409 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
410 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
411 | 19 /* snapshot */)); | |
412 | range_del_agg.AddTombstones(std::move(input_iter)); | |
413 | } | |
414 | ||
415 | VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 19), false}, | |
416 | {InternalValue("a", 9), true}, | |
417 | {InternalValue("b", 9), true}, | |
418 | {InternalValue("d", 9), true}, | |
419 | {InternalValue("e", 7), true}, | |
420 | {InternalValue("g", 7), false}, | |
421 | {InternalValue("h", 24), false}, | |
422 | {InternalValue("i", 24), false}, | |
423 | {InternalValue("ii", 14), true}, | |
424 | {InternalValue("j", 14), false}}); | |
425 | ||
426 | VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false}, | |
427 | {"_", "a", true}, | |
428 | {"a", "c", true}, | |
429 | {"d", "f", true}, | |
430 | {"g", "l", true}, | |
431 | {"x", "y", false}}); | |
7c673cae FG |
432 | } |
433 | ||
494da23a TL |
434 | TEST_F(RangeDelAggregatorTest, MultipleTruncatedItersInAggregator) { |
435 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
436 | {{{"a", "z", 10}}, {{"a", "z", 10}}, {{"a", "z", 10}}}); | |
437 | std::vector<std::pair<InternalKey, InternalKey>> iter_bounds = { | |
438 | {InternalKey("a", 4, kTypeValue), | |
439 | InternalKey("m", kMaxSequenceNumber, kTypeRangeDeletion)}, | |
440 | {InternalKey("m", 20, kTypeValue), | |
441 | InternalKey("x", kMaxSequenceNumber, kTypeRangeDeletion)}, | |
442 | {InternalKey("x", 5, kTypeValue), InternalKey("zz", 30, kTypeValue)}}; | |
443 | ||
444 | ReadRangeDelAggregator range_del_agg(&bytewise_icmp, 19); | |
445 | for (size_t i = 0; i < fragment_lists.size(); i++) { | |
446 | const auto& fragment_list = fragment_lists[i]; | |
447 | const auto& bounds = iter_bounds[i]; | |
448 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
449 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
450 | 19 /* snapshot */)); | |
451 | range_del_agg.AddTombstones(std::move(input_iter), &bounds.first, | |
452 | &bounds.second); | |
453 | } | |
454 | ||
455 | VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 10), false}, | |
456 | {InternalValue("a", 9), false}, | |
457 | {InternalValue("a", 4), true}, | |
458 | {InternalValue("m", 10), false}, | |
459 | {InternalValue("m", 9), true}, | |
460 | {InternalValue("x", 10), false}, | |
461 | {InternalValue("x", 9), false}, | |
462 | {InternalValue("x", 5), true}, | |
463 | {InternalValue("z", 9), false}}); | |
464 | ||
465 | VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false}, | |
466 | {"_", "a", true}, | |
467 | {"a", "n", true}, | |
468 | {"l", "x", true}, | |
469 | {"w", "z", true}, | |
470 | {"zzz", "zz", false}, | |
471 | {"zz", "zzz", false}}); | |
7c673cae FG |
472 | } |
473 | ||
494da23a TL |
474 | TEST_F(RangeDelAggregatorTest, MultipleTruncatedItersInAggregatorSameLevel) { |
475 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
476 | {{{"a", "z", 10}}, {{"a", "z", 10}}, {{"a", "z", 10}}}); | |
477 | std::vector<std::pair<InternalKey, InternalKey>> iter_bounds = { | |
478 | {InternalKey("a", 4, kTypeValue), | |
479 | InternalKey("m", kMaxSequenceNumber, kTypeRangeDeletion)}, | |
480 | {InternalKey("m", 20, kTypeValue), | |
481 | InternalKey("x", kMaxSequenceNumber, kTypeRangeDeletion)}, | |
482 | {InternalKey("x", 5, kTypeValue), InternalKey("zz", 30, kTypeValue)}}; | |
483 | ||
484 | ReadRangeDelAggregator range_del_agg(&bytewise_icmp, 19); | |
485 | ||
486 | auto add_iter_to_agg = [&](size_t i) { | |
487 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
488 | new FragmentedRangeTombstoneIterator(fragment_lists[i].get(), | |
489 | bytewise_icmp, 19 /* snapshot */)); | |
490 | range_del_agg.AddTombstones(std::move(input_iter), &iter_bounds[i].first, | |
491 | &iter_bounds[i].second); | |
492 | }; | |
493 | ||
494 | add_iter_to_agg(0); | |
495 | VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 10), false}, | |
496 | {InternalValue("a", 9), false}, | |
497 | {InternalValue("a", 4), true}}); | |
498 | ||
499 | add_iter_to_agg(1); | |
500 | VerifyShouldDelete(&range_del_agg, {{InternalValue("m", 10), false}, | |
501 | {InternalValue("m", 9), true}}); | |
502 | ||
503 | add_iter_to_agg(2); | |
504 | VerifyShouldDelete(&range_del_agg, {{InternalValue("x", 10), false}, | |
505 | {InternalValue("x", 9), false}, | |
506 | {InternalValue("x", 5), true}, | |
507 | {InternalValue("z", 9), false}}); | |
508 | ||
509 | VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false}, | |
510 | {"_", "a", true}, | |
511 | {"a", "n", true}, | |
512 | {"l", "x", true}, | |
513 | {"w", "z", true}, | |
514 | {"zzz", "zz", false}, | |
515 | {"zz", "zzz", false}}); | |
7c673cae FG |
516 | } |
517 | ||
494da23a TL |
518 | TEST_F(RangeDelAggregatorTest, CompactionAggregatorNoSnapshots) { |
519 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
520 | {{{"a", "e", 10}, {"c", "g", 8}}, | |
521 | {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}}); | |
522 | ||
523 | std::vector<SequenceNumber> snapshots; | |
524 | CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots); | |
525 | for (const auto& fragment_list : fragment_lists) { | |
526 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
527 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
528 | kMaxSequenceNumber)); | |
529 | range_del_agg.AddTombstones(std::move(input_iter)); | |
530 | } | |
531 | ||
532 | VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 19), true}, | |
533 | {InternalValue("b", 19), false}, | |
534 | {InternalValue("b", 9), true}, | |
535 | {InternalValue("d", 9), true}, | |
536 | {InternalValue("e", 7), true}, | |
537 | {InternalValue("g", 7), false}, | |
538 | {InternalValue("h", 24), true}, | |
539 | {InternalValue("i", 24), false}, | |
540 | {InternalValue("ii", 14), true}, | |
541 | {InternalValue("j", 14), false}}); | |
542 | ||
543 | auto range_del_compaction_iter = range_del_agg.NewIterator(); | |
544 | VerifyFragmentedRangeDels(range_del_compaction_iter.get(), {{"a", "b", 20}, | |
545 | {"b", "c", 10}, | |
546 | {"c", "e", 10}, | |
547 | {"e", "g", 8}, | |
548 | {"h", "i", 25}, | |
549 | {"ii", "j", 15}}); | |
11fdf7f2 TL |
550 | } |
551 | ||
494da23a TL |
552 | TEST_F(RangeDelAggregatorTest, CompactionAggregatorWithSnapshots) { |
553 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
554 | {{{"a", "e", 10}, {"c", "g", 8}}, | |
555 | {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}}); | |
556 | ||
557 | std::vector<SequenceNumber> snapshots{9, 19}; | |
558 | CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots); | |
559 | for (const auto& fragment_list : fragment_lists) { | |
560 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
561 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
562 | kMaxSequenceNumber)); | |
563 | range_del_agg.AddTombstones(std::move(input_iter)); | |
11fdf7f2 | 564 | } |
494da23a TL |
565 | |
566 | VerifyShouldDelete( | |
567 | &range_del_agg, | |
568 | { | |
569 | {InternalValue("a", 19), false}, // [10, 19] | |
570 | {InternalValue("a", 9), false}, // [0, 9] | |
571 | {InternalValue("b", 9), false}, // [0, 9] | |
572 | {InternalValue("d", 9), false}, // [0, 9] | |
573 | {InternalValue("d", 7), true}, // [0, 9] | |
574 | {InternalValue("e", 7), true}, // [0, 9] | |
575 | {InternalValue("g", 7), false}, // [0, 9] | |
576 | {InternalValue("h", 24), true}, // [20, kMaxSequenceNumber] | |
577 | {InternalValue("i", 24), false}, // [20, kMaxSequenceNumber] | |
578 | {InternalValue("ii", 14), true}, // [10, 19] | |
579 | {InternalValue("j", 14), false} // [10, 19] | |
580 | }); | |
581 | ||
582 | auto range_del_compaction_iter = range_del_agg.NewIterator(); | |
583 | VerifyFragmentedRangeDels(range_del_compaction_iter.get(), {{"a", "b", 20}, | |
584 | {"a", "b", 10}, | |
585 | {"b", "c", 10}, | |
586 | {"c", "e", 10}, | |
587 | {"c", "e", 8}, | |
588 | {"e", "g", 8}, | |
589 | {"h", "i", 25}, | |
590 | {"ii", "j", 15}}); | |
11fdf7f2 TL |
591 | } |
592 | ||
494da23a TL |
593 | TEST_F(RangeDelAggregatorTest, CompactionAggregatorEmptyIteratorLeft) { |
594 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
595 | {{{"a", "e", 10}, {"c", "g", 8}}, | |
596 | {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}}); | |
597 | ||
598 | std::vector<SequenceNumber> snapshots{9, 19}; | |
599 | CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots); | |
600 | for (const auto& fragment_list : fragment_lists) { | |
601 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
602 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
603 | kMaxSequenceNumber)); | |
604 | range_del_agg.AddTombstones(std::move(input_iter)); | |
11fdf7f2 | 605 | } |
494da23a TL |
606 | |
607 | Slice start("_"); | |
608 | Slice end("__"); | |
11fdf7f2 TL |
609 | } |
610 | ||
494da23a TL |
611 | TEST_F(RangeDelAggregatorTest, CompactionAggregatorEmptyIteratorRight) { |
612 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
613 | {{{"a", "e", 10}, {"c", "g", 8}}, | |
614 | {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}}); | |
615 | ||
616 | std::vector<SequenceNumber> snapshots{9, 19}; | |
617 | CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots); | |
618 | for (const auto& fragment_list : fragment_lists) { | |
619 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
620 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
621 | kMaxSequenceNumber)); | |
622 | range_del_agg.AddTombstones(std::move(input_iter)); | |
623 | } | |
624 | ||
625 | Slice start("p"); | |
626 | Slice end("q"); | |
627 | auto range_del_compaction_iter1 = | |
628 | range_del_agg.NewIterator(&start, &end, false /* end_key_inclusive */); | |
629 | VerifyFragmentedRangeDels(range_del_compaction_iter1.get(), {}); | |
630 | ||
631 | auto range_del_compaction_iter2 = | |
632 | range_del_agg.NewIterator(&start, &end, true /* end_key_inclusive */); | |
633 | VerifyFragmentedRangeDels(range_del_compaction_iter2.get(), {}); | |
11fdf7f2 TL |
634 | } |
635 | ||
494da23a TL |
636 | TEST_F(RangeDelAggregatorTest, CompactionAggregatorBoundedIterator) { |
637 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
638 | {{{"a", "e", 10}, {"c", "g", 8}}, | |
639 | {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}}); | |
640 | ||
641 | std::vector<SequenceNumber> snapshots{9, 19}; | |
642 | CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots); | |
643 | for (const auto& fragment_list : fragment_lists) { | |
644 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
645 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
646 | kMaxSequenceNumber)); | |
647 | range_del_agg.AddTombstones(std::move(input_iter)); | |
648 | } | |
649 | ||
650 | Slice start("bb"); | |
651 | Slice end("e"); | |
652 | auto range_del_compaction_iter1 = | |
653 | range_del_agg.NewIterator(&start, &end, false /* end_key_inclusive */); | |
654 | VerifyFragmentedRangeDels(range_del_compaction_iter1.get(), | |
655 | {{"a", "c", 10}, {"c", "e", 10}, {"c", "e", 8}}); | |
656 | ||
657 | auto range_del_compaction_iter2 = | |
658 | range_del_agg.NewIterator(&start, &end, true /* end_key_inclusive */); | |
659 | VerifyFragmentedRangeDels( | |
660 | range_del_compaction_iter2.get(), | |
661 | {{"a", "c", 10}, {"c", "e", 10}, {"c", "e", 8}, {"e", "g", 8}}); | |
11fdf7f2 TL |
662 | } |
663 | ||
494da23a TL |
664 | TEST_F(RangeDelAggregatorTest, |
665 | CompactionAggregatorBoundedIteratorExtraFragments) { | |
666 | auto fragment_lists = MakeFragmentedTombstoneLists( | |
667 | {{{"a", "d", 10}, {"c", "g", 8}}, | |
668 | {{"b", "c", 20}, {"d", "f", 30}, {"h", "i", 25}, {"ii", "j", 15}}}); | |
669 | ||
670 | std::vector<SequenceNumber> snapshots{9, 19}; | |
671 | CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots); | |
672 | for (const auto& fragment_list : fragment_lists) { | |
673 | std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter( | |
674 | new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp, | |
675 | kMaxSequenceNumber)); | |
676 | range_del_agg.AddTombstones(std::move(input_iter)); | |
677 | } | |
678 | ||
679 | Slice start("bb"); | |
680 | Slice end("e"); | |
681 | auto range_del_compaction_iter1 = | |
682 | range_del_agg.NewIterator(&start, &end, false /* end_key_inclusive */); | |
683 | VerifyFragmentedRangeDels(range_del_compaction_iter1.get(), {{"a", "b", 10}, | |
684 | {"b", "c", 20}, | |
685 | {"b", "c", 10}, | |
686 | {"c", "d", 10}, | |
687 | {"c", "d", 8}, | |
688 | {"d", "f", 30}, | |
689 | {"d", "f", 8}, | |
690 | {"f", "g", 8}}); | |
691 | ||
692 | auto range_del_compaction_iter2 = | |
693 | range_del_agg.NewIterator(&start, &end, true /* end_key_inclusive */); | |
694 | VerifyFragmentedRangeDels(range_del_compaction_iter2.get(), {{"a", "b", 10}, | |
695 | {"b", "c", 20}, | |
696 | {"b", "c", 10}, | |
697 | {"c", "d", 10}, | |
698 | {"c", "d", 8}, | |
699 | {"d", "f", 30}, | |
700 | {"d", "f", 8}, | |
701 | {"f", "g", 8}}); | |
7c673cae FG |
702 | } |
703 | ||
f67539c2 | 704 | } // namespace ROCKSDB_NAMESPACE |
7c673cae FG |
705 | |
706 | int main(int argc, char** argv) { | |
707 | ::testing::InitGoogleTest(&argc, argv); | |
708 | return RUN_ALL_TESTS(); | |
709 | } |