1 // Copyright (c) 2018-present, Facebook, Inc. All rights reserved.
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).
5
6 #include "db/range_del_aggregator.h"
7
8 #include <memory>
9 #include <string>
10 #include <vector>
11
12 #include "db/db_test_util.h"
13 #include "db/dbformat.h"
14 #include "db/range_tombstone_fragmenter.h"
15 #include "test_util/testutil.h"
16
17 namespace ROCKSDB_NAMESPACE {
18
19 class RangeDelAggregatorTest : public testing::Test {};
20
21 namespace {
22
23 static auto bytewise_icmp = InternalKeyComparator(BytewiseComparator());
24
MakeRangeDelIter(const std::vector<RangeTombstone> & range_dels)25 std::unique_ptr<InternalIterator> MakeRangeDelIter(
26 const std::vector<RangeTombstone>& range_dels) {
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 }
33 return std::unique_ptr<test::VectorIterator>(
34 new test::VectorIterator(keys, values));
35 }
36
37 std::vector<std::unique_ptr<FragmentedRangeTombstoneList>>
MakeFragmentedTombstoneLists(const std::vector<std::vector<RangeTombstone>> & range_dels_list)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;
47 }
48
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
UncutEndpoint(const Slice & s)74 ParsedInternalKey UncutEndpoint(const Slice& s) {
75 return ParsedInternalKey(s, kMaxSequenceNumber, kTypeRangeDeletion);
76 }
77
InternalValue(const Slice & key,SequenceNumber seq)78 ParsedInternalKey InternalValue(const Slice& key, SequenceNumber seq) {
79 return ParsedInternalKey(key, seq, kTypeValue);
80 }
81
VerifyIterator(TruncatedRangeDelIterator * iter,const InternalKeyComparator & icmp,const std::vector<TruncatedIterScanTestCase> & expected_range_dels)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());
107 }
108 EXPECT_FALSE(iter->Valid());
109 }
110
VerifySeek(TruncatedRangeDelIterator * iter,const InternalKeyComparator & icmp,const std::vector<TruncatedIterSeekTestCase> & test_cases)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());
123 }
124 }
125 }
126
VerifySeekForPrev(TruncatedRangeDelIterator * iter,const InternalKeyComparator & icmp,const std::vector<TruncatedIterSeekTestCase> & test_cases)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());
134 } else {
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());
139 }
140 }
141 }
142
VerifyShouldDelete(RangeDelAggregator * range_del_agg,const std::vector<ShouldDeleteTestCase> & test_cases)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 }
158 }
159
VerifyIsRangeOverlapped(ReadRangeDelAggregator * range_del_agg,const std::vector<IsRangeOverlappedTestCase> & test_cases)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 }
167 }
168
CheckIterPosition(const RangeTombstone & tombstone,const FragmentedRangeTombstoneIterator * iter)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()));
180 }
181
VerifyFragmentedRangeDels(FragmentedRangeTombstoneIterator * iter,const std::vector<RangeTombstone> & expected_tombstones)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());
191 }
192
193 } // namespace
194
TEST_F(RangeDelAggregatorTest,EmptyTruncatedIter)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));
202
203 TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, nullptr,
204 nullptr);
205
206 iter.SeekToFirst();
207 ASSERT_FALSE(iter.Valid());
208
209 iter.SeekToLast();
210 ASSERT_FALSE(iter.Valid());
211 }
212
TEST_F(RangeDelAggregatorTest,UntruncatedIter)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 */}});
245 }
246
TEST_F(RangeDelAggregatorTest,UntruncatedIterWithSnapshot)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 */}});
278 }
279
TEST_F(RangeDelAggregatorTest,TruncatedIterPartiallyCutTombstones)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 */}});
314 }
315
TEST_F(RangeDelAggregatorTest,TruncatedIterFullyCutTombstones)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}});
344 }
345
TEST_F(RangeDelAggregatorTest,SingleIterInAggregator)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}});
368 }
369
TEST_F(RangeDelAggregatorTest,MultipleItersInAggregator)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}});
400 }
401
TEST_F(RangeDelAggregatorTest,MultipleItersInAggregatorWithUpperBound)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}});
432 }
433
TEST_F(RangeDelAggregatorTest,MultipleTruncatedItersInAggregator)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}});
472 }
473
TEST_F(RangeDelAggregatorTest,MultipleTruncatedItersInAggregatorSameLevel)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}});
516 }
517
TEST_F(RangeDelAggregatorTest,CompactionAggregatorNoSnapshots)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}});
550 }
551
TEST_F(RangeDelAggregatorTest,CompactionAggregatorWithSnapshots)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));
564 }
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}});
591 }
592
TEST_F(RangeDelAggregatorTest,CompactionAggregatorEmptyIteratorLeft)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));
605 }
606
607 Slice start("_");
608 Slice end("__");
609 }
610
TEST_F(RangeDelAggregatorTest,CompactionAggregatorEmptyIteratorRight)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(), {});
634 }
635
TEST_F(RangeDelAggregatorTest,CompactionAggregatorBoundedIterator)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}});
662 }
663
TEST_F(RangeDelAggregatorTest,CompactionAggregatorBoundedIteratorExtraFragments)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}});
702 }
703
704 } // namespace ROCKSDB_NAMESPACE
705
main(int argc,char ** argv)706 int main(int argc, char** argv) {
707 ::testing::InitGoogleTest(&argc, argv);
708 return RUN_ALL_TESTS();
709 }
710