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).
6 #include "db/range_del_aggregator.h"
12 #include "db/db_test_util.h"
13 #include "db/dbformat.h"
14 #include "db/range_tombstone_fragmenter.h"
15 #include "util/testutil.h"
19 class RangeDelAggregatorTest
: public testing::Test
{};
23 static auto bytewise_icmp
= InternalKeyComparator(BytewiseComparator());
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());
33 return std::unique_ptr
<test::VectorIterator
>(
34 new test::VectorIterator(keys
, values
));
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
));
46 return fragment_lists
;
49 struct TruncatedIterScanTestCase
{
50 ParsedInternalKey start
;
51 ParsedInternalKey end
;
55 struct TruncatedIterSeekTestCase
{
57 ParsedInternalKey start
;
58 ParsedInternalKey end
;
63 struct ShouldDeleteTestCase
{
64 ParsedInternalKey lookup_key
;
68 struct IsRangeOverlappedTestCase
{
74 ParsedInternalKey
UncutEndpoint(const Slice
& s
) {
75 return ParsedInternalKey(s
, kMaxSequenceNumber
, kTypeRangeDeletion
);
78 ParsedInternalKey
InternalValue(const Slice
& key
, SequenceNumber seq
) {
79 return ParsedInternalKey(key
, seq
, kTypeValue
);
83 TruncatedRangeDelIterator
* iter
, const InternalKeyComparator
& icmp
,
84 const std::vector
<TruncatedIterScanTestCase
>& expected_range_dels
) {
85 // Test forward iteration.
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());
93 EXPECT_FALSE(iter
->Valid());
95 // Test reverse iteration.
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();
101 ASSERT_TRUE(iter
->Valid());
102 EXPECT_EQ(0, icmp
.Compare(iter
->start_key(),
103 reverse_expected_range_dels
[i
].start
));
105 0, icmp
.Compare(iter
->end_key(), reverse_expected_range_dels
[i
].end
));
106 EXPECT_EQ(reverse_expected_range_dels
[i
].seq
, iter
->seq());
108 EXPECT_FALSE(iter
->Valid());
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());
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());
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());
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());
143 void VerifyShouldDelete(RangeDelAggregator
* range_del_agg
,
144 const std::vector
<ShouldDeleteTestCase
>& test_cases
) {
145 for (const auto& test_case
: test_cases
) {
148 range_del_agg
->ShouldDelete(
149 test_case
.lookup_key
, RangeDelPositioningMode::kForwardTraversal
));
151 for (auto it
= test_cases
.rbegin(); it
!= test_cases
.rend(); ++it
) {
152 const auto& test_case
= *it
;
155 range_del_agg
->ShouldDelete(
156 test_case
.lookup_key
, RangeDelPositioningMode::kBackwardTraversal
));
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
));
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());
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()));
182 void VerifyFragmentedRangeDels(
183 FragmentedRangeTombstoneIterator
* iter
,
184 const std::vector
<RangeTombstone
>& expected_tombstones
) {
186 for (size_t i
= 0; i
< expected_tombstones
.size(); i
++, iter
->Next()) {
187 ASSERT_TRUE(iter
->Valid());
188 CheckIterPosition(expected_tombstones
[i
], iter
);
190 EXPECT_FALSE(iter
->Valid());
195 TEST_F(RangeDelAggregatorTest
, EmptyTruncatedIter
) {
196 auto range_del_iter
= MakeRangeDelIter({});
197 FragmentedRangeTombstoneList
fragment_list(std::move(range_del_iter
),
199 std::unique_ptr
<FragmentedRangeTombstoneIterator
> input_iter(
200 new FragmentedRangeTombstoneIterator(&fragment_list
, bytewise_icmp
,
201 kMaxSequenceNumber
));
203 TruncatedRangeDelIterator
iter(std::move(input_iter
), &bytewise_icmp
, nullptr,
207 ASSERT_FALSE(iter
.Valid());
210 ASSERT_FALSE(iter
.Valid());
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
),
218 std::unique_ptr
<FragmentedRangeTombstoneIterator
> input_iter(
219 new FragmentedRangeTombstoneIterator(&fragment_list
, bytewise_icmp
,
220 kMaxSequenceNumber
));
222 TruncatedRangeDelIterator
iter(std::move(input_iter
), &bytewise_icmp
, nullptr,
225 VerifyIterator(&iter
, bytewise_icmp
,
226 {{UncutEndpoint("a"), UncutEndpoint("e"), 10},
227 {UncutEndpoint("e"), UncutEndpoint("g"), 8},
228 {UncutEndpoint("j"), UncutEndpoint("n"), 4}});
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}});
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 */}});
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
),
252 std::unique_ptr
<FragmentedRangeTombstoneIterator
> input_iter(
253 new FragmentedRangeTombstoneIterator(&fragment_list
, bytewise_icmp
,
256 TruncatedRangeDelIterator
iter(std::move(input_iter
), &bytewise_icmp
, nullptr,
259 VerifyIterator(&iter
, bytewise_icmp
,
260 {{UncutEndpoint("e"), UncutEndpoint("g"), 8},
261 {UncutEndpoint("j"), UncutEndpoint("n"), 4}});
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}});
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 */}});
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
),
285 std::unique_ptr
<FragmentedRangeTombstoneIterator
> input_iter(
286 new FragmentedRangeTombstoneIterator(&fragment_list
, bytewise_icmp
,
287 kMaxSequenceNumber
));
289 InternalKey
smallest("d", 7, kTypeValue
);
290 InternalKey
largest("m", 9, kTypeValue
);
291 TruncatedRangeDelIterator
iter(std::move(input_iter
), &bytewise_icmp
,
292 &smallest
, &largest
);
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}});
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}});
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 */}});
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
),
321 std::unique_ptr
<FragmentedRangeTombstoneIterator
> input_iter(
322 new FragmentedRangeTombstoneIterator(&fragment_list
, bytewise_icmp
,
323 kMaxSequenceNumber
));
325 InternalKey
smallest("f", 7, kTypeValue
);
326 InternalKey
largest("i", 9, kTypeValue
);
327 TruncatedRangeDelIterator
iter(std::move(input_iter
), &bytewise_icmp
,
328 &smallest
, &largest
);
330 VerifyIterator(&iter
, bytewise_icmp
,
331 {{InternalValue("f", 7), UncutEndpoint("g"), 8}});
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 */}});
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}});
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
),
350 std::unique_ptr
<FragmentedRangeTombstoneIterator
> input_iter(
351 new FragmentedRangeTombstoneIterator(&fragment_list
, bytewise_icmp
,
352 kMaxSequenceNumber
));
354 ReadRangeDelAggregator
range_del_agg(&bytewise_icmp
, kMaxSequenceNumber
);
355 range_del_agg
.AddTombstones(std::move(input_iter
));
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}});
363 VerifyIsRangeOverlapped(&range_del_agg
, {{"", "_", false},
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}}});
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
));
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}});
394 VerifyIsRangeOverlapped(&range_del_agg
, {{"", "_", false},
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}}});
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
,
412 range_del_agg
.AddTombstones(std::move(input_iter
));
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}});
426 VerifyIsRangeOverlapped(&range_del_agg
, {{"", "_", false},
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
)}};
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
,
451 range_del_agg
.AddTombstones(std::move(input_iter
), &bounds
.first
,
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}});
465 VerifyIsRangeOverlapped(&range_del_agg
, {{"", "_", false},
470 {"zzz", "zz", false},
471 {"zz", "zzz", false}});
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
)}};
484 ReadRangeDelAggregator
range_del_agg(&bytewise_icmp
, 19);
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
);
495 VerifyShouldDelete(&range_del_agg
, {{InternalValue("a", 10), false},
496 {InternalValue("a", 9), false},
497 {InternalValue("a", 4), true}});
500 VerifyShouldDelete(&range_del_agg
, {{InternalValue("m", 10), false},
501 {InternalValue("m", 9), true}});
504 VerifyShouldDelete(&range_del_agg
, {{InternalValue("x", 10), false},
505 {InternalValue("x", 9), false},
506 {InternalValue("x", 5), true},
507 {InternalValue("z", 9), false}});
509 VerifyIsRangeOverlapped(&range_del_agg
, {{"", "_", false},
514 {"zzz", "zz", false},
515 {"zz", "zzz", false}});
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}}});
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
));
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}});
543 auto range_del_compaction_iter
= range_del_agg
.NewIterator();
544 VerifyFragmentedRangeDels(range_del_compaction_iter
.get(), {{"a", "b", 20},
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}}});
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
));
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]
582 auto range_del_compaction_iter
= range_del_agg
.NewIterator();
583 VerifyFragmentedRangeDels(range_del_compaction_iter
.get(), {{"a", "b", 20},
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}}});
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
));
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}}});
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
));
627 auto range_del_compaction_iter1
=
628 range_del_agg
.NewIterator(&start
, &end
, false /* end_key_inclusive */);
629 VerifyFragmentedRangeDels(range_del_compaction_iter1
.get(), {});
631 auto range_del_compaction_iter2
=
632 range_del_agg
.NewIterator(&start
, &end
, true /* end_key_inclusive */);
633 VerifyFragmentedRangeDels(range_del_compaction_iter2
.get(), {});
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}}});
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
));
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}});
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}});
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}}});
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
));
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},
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},
704 } // namespace rocksdb
706 int main(int argc
, char** argv
) {
707 ::testing::InitGoogleTest(&argc
, argv
);
708 return RUN_ALL_TESTS();