1 //  Copyright (c) 2011-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 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9 
10 #include "db/db_test_util.h"
11 #include "port/stack_trace.h"
12 #include "rocksdb/perf_context.h"
13 #include "table/block_based/filter_policy_internal.h"
14 
15 namespace ROCKSDB_NAMESPACE {
16 
17 namespace {
18 using BFP = BloomFilterPolicy;
19 }  // namespace
20 
21 // DB tests related to bloom filter.
22 
23 class DBBloomFilterTest : public DBTestBase {
24  public:
DBBloomFilterTest()25   DBBloomFilterTest() : DBTestBase("/db_bloom_filter_test") {}
26 };
27 
28 class DBBloomFilterTestWithParam : public DBTestBase,
29                                    public testing::WithParamInterface<
30                                        std::tuple<BFP::Mode, bool, uint32_t>> {
31   //                             public testing::WithParamInterface<bool> {
32  protected:
33   BFP::Mode bfp_impl_;
34   bool partition_filters_;
35   uint32_t format_version_;
36 
37  public:
DBBloomFilterTestWithParam()38   DBBloomFilterTestWithParam() : DBTestBase("/db_bloom_filter_tests") {}
39 
~DBBloomFilterTestWithParam()40   ~DBBloomFilterTestWithParam() override {}
41 
SetUp()42   void SetUp() override {
43     bfp_impl_ = std::get<0>(GetParam());
44     partition_filters_ = std::get<1>(GetParam());
45     format_version_ = std::get<2>(GetParam());
46   }
47 };
48 
49 class DBBloomFilterTestDefFormatVersion : public DBBloomFilterTestWithParam {};
50 
51 class SliceTransformLimitedDomainGeneric : public SliceTransform {
Name() const52   const char* Name() const override {
53     return "SliceTransformLimitedDomainGeneric";
54   }
55 
Transform(const Slice & src) const56   Slice Transform(const Slice& src) const override {
57     return Slice(src.data(), 5);
58   }
59 
InDomain(const Slice & src) const60   bool InDomain(const Slice& src) const override {
61     // prefix will be x????
62     return src.size() >= 5;
63   }
64 
InRange(const Slice & dst) const65   bool InRange(const Slice& dst) const override {
66     // prefix will be x????
67     return dst.size() == 5;
68   }
69 };
70 
71 // KeyMayExist can lead to a few false positives, but not false negatives.
72 // To make test deterministic, use a much larger number of bits per key-20 than
73 // bits in the key, so that false positives are eliminated
TEST_P(DBBloomFilterTestDefFormatVersion,KeyMayExist)74 TEST_P(DBBloomFilterTestDefFormatVersion, KeyMayExist) {
75   do {
76     ReadOptions ropts;
77     std::string value;
78     anon::OptionsOverride options_override;
79     options_override.filter_policy.reset(new BFP(20, bfp_impl_));
80     options_override.partition_filters = partition_filters_;
81     options_override.metadata_block_size = 32;
82     Options options = CurrentOptions(options_override);
83     if (partition_filters_ &&
84         static_cast<BlockBasedTableOptions*>(
85             options.table_factory->GetOptions())
86                 ->index_type != BlockBasedTableOptions::kTwoLevelIndexSearch) {
87       // In the current implementation partitioned filters depend on partitioned
88       // indexes
89       continue;
90     }
91     options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
92     CreateAndReopenWithCF({"pikachu"}, options);
93 
94     ASSERT_TRUE(!db_->KeyMayExist(ropts, handles_[1], "a", &value));
95 
96     ASSERT_OK(Put(1, "a", "b"));
97     bool value_found = false;
98     ASSERT_TRUE(
99         db_->KeyMayExist(ropts, handles_[1], "a", &value, &value_found));
100     ASSERT_TRUE(value_found);
101     ASSERT_EQ("b", value);
102 
103     ASSERT_OK(Flush(1));
104     value.clear();
105 
106     uint64_t numopen = TestGetTickerCount(options, NO_FILE_OPENS);
107     uint64_t cache_added = TestGetTickerCount(options, BLOCK_CACHE_ADD);
108     ASSERT_TRUE(
109         db_->KeyMayExist(ropts, handles_[1], "a", &value, &value_found));
110     ASSERT_TRUE(!value_found);
111     // assert that no new files were opened and no new blocks were
112     // read into block cache.
113     ASSERT_EQ(numopen, TestGetTickerCount(options, NO_FILE_OPENS));
114     ASSERT_EQ(cache_added, TestGetTickerCount(options, BLOCK_CACHE_ADD));
115 
116     ASSERT_OK(Delete(1, "a"));
117 
118     numopen = TestGetTickerCount(options, NO_FILE_OPENS);
119     cache_added = TestGetTickerCount(options, BLOCK_CACHE_ADD);
120     ASSERT_TRUE(!db_->KeyMayExist(ropts, handles_[1], "a", &value));
121     ASSERT_EQ(numopen, TestGetTickerCount(options, NO_FILE_OPENS));
122     ASSERT_EQ(cache_added, TestGetTickerCount(options, BLOCK_CACHE_ADD));
123 
124     ASSERT_OK(Flush(1));
125     dbfull()->TEST_CompactRange(0, nullptr, nullptr, handles_[1],
126                                 true /* disallow trivial move */);
127 
128     numopen = TestGetTickerCount(options, NO_FILE_OPENS);
129     cache_added = TestGetTickerCount(options, BLOCK_CACHE_ADD);
130     ASSERT_TRUE(!db_->KeyMayExist(ropts, handles_[1], "a", &value));
131     ASSERT_EQ(numopen, TestGetTickerCount(options, NO_FILE_OPENS));
132     ASSERT_EQ(cache_added, TestGetTickerCount(options, BLOCK_CACHE_ADD));
133 
134     ASSERT_OK(Delete(1, "c"));
135 
136     numopen = TestGetTickerCount(options, NO_FILE_OPENS);
137     cache_added = TestGetTickerCount(options, BLOCK_CACHE_ADD);
138     ASSERT_TRUE(!db_->KeyMayExist(ropts, handles_[1], "c", &value));
139     ASSERT_EQ(numopen, TestGetTickerCount(options, NO_FILE_OPENS));
140     ASSERT_EQ(cache_added, TestGetTickerCount(options, BLOCK_CACHE_ADD));
141 
142     // KeyMayExist function only checks data in block caches, which is not used
143     // by plain table format.
144   } while (
145       ChangeOptions(kSkipPlainTable | kSkipHashIndex | kSkipFIFOCompaction));
146 }
147 
TEST_F(DBBloomFilterTest,GetFilterByPrefixBloomCustomPrefixExtractor)148 TEST_F(DBBloomFilterTest, GetFilterByPrefixBloomCustomPrefixExtractor) {
149   for (bool partition_filters : {true, false}) {
150     Options options = last_options_;
151     options.prefix_extractor =
152         std::make_shared<SliceTransformLimitedDomainGeneric>();
153     options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
154     get_perf_context()->EnablePerLevelPerfContext();
155     BlockBasedTableOptions bbto;
156     bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
157     if (partition_filters) {
158       bbto.partition_filters = true;
159       bbto.index_type = BlockBasedTableOptions::IndexType::kTwoLevelIndexSearch;
160     }
161     bbto.whole_key_filtering = false;
162     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
163     DestroyAndReopen(options);
164 
165     WriteOptions wo;
166     ReadOptions ro;
167     FlushOptions fo;
168     fo.wait = true;
169     std::string value;
170 
171     ASSERT_OK(dbfull()->Put(wo, "barbarbar", "foo"));
172     ASSERT_OK(dbfull()->Put(wo, "barbarbar2", "foo2"));
173     ASSERT_OK(dbfull()->Put(wo, "foofoofoo", "bar"));
174 
175     dbfull()->Flush(fo);
176 
177     ASSERT_EQ("foo", Get("barbarbar"));
178     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
179     ASSERT_EQ(
180         0,
181         (*(get_perf_context()->level_to_perf_context))[0].bloom_filter_useful);
182     ASSERT_EQ("foo2", Get("barbarbar2"));
183     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
184     ASSERT_EQ(
185         0,
186         (*(get_perf_context()->level_to_perf_context))[0].bloom_filter_useful);
187     ASSERT_EQ("NOT_FOUND", Get("barbarbar3"));
188     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
189     ASSERT_EQ(
190         0,
191         (*(get_perf_context()->level_to_perf_context))[0].bloom_filter_useful);
192 
193     ASSERT_EQ("NOT_FOUND", Get("barfoofoo"));
194     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
195     ASSERT_EQ(
196         1,
197         (*(get_perf_context()->level_to_perf_context))[0].bloom_filter_useful);
198 
199     ASSERT_EQ("NOT_FOUND", Get("foobarbar"));
200     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 2);
201     ASSERT_EQ(
202         2,
203         (*(get_perf_context()->level_to_perf_context))[0].bloom_filter_useful);
204 
205     ro.total_order_seek = true;
206     ASSERT_TRUE(db_->Get(ro, "foobarbar", &value).IsNotFound());
207     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 2);
208     ASSERT_EQ(
209         2,
210         (*(get_perf_context()->level_to_perf_context))[0].bloom_filter_useful);
211     get_perf_context()->Reset();
212   }
213 }
214 
TEST_F(DBBloomFilterTest,GetFilterByPrefixBloom)215 TEST_F(DBBloomFilterTest, GetFilterByPrefixBloom) {
216   for (bool partition_filters : {true, false}) {
217     Options options = last_options_;
218     options.prefix_extractor.reset(NewFixedPrefixTransform(8));
219     options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
220     get_perf_context()->EnablePerLevelPerfContext();
221     BlockBasedTableOptions bbto;
222     bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
223     if (partition_filters) {
224       bbto.partition_filters = true;
225       bbto.index_type = BlockBasedTableOptions::IndexType::kTwoLevelIndexSearch;
226     }
227     bbto.whole_key_filtering = false;
228     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
229     DestroyAndReopen(options);
230 
231     WriteOptions wo;
232     ReadOptions ro;
233     FlushOptions fo;
234     fo.wait = true;
235     std::string value;
236 
237     ASSERT_OK(dbfull()->Put(wo, "barbarbar", "foo"));
238     ASSERT_OK(dbfull()->Put(wo, "barbarbar2", "foo2"));
239     ASSERT_OK(dbfull()->Put(wo, "foofoofoo", "bar"));
240 
241     dbfull()->Flush(fo);
242 
243     ASSERT_EQ("foo", Get("barbarbar"));
244     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
245     ASSERT_EQ("foo2", Get("barbarbar2"));
246     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
247     ASSERT_EQ("NOT_FOUND", Get("barbarbar3"));
248     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
249 
250     ASSERT_EQ("NOT_FOUND", Get("barfoofoo"));
251     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
252 
253     ASSERT_EQ("NOT_FOUND", Get("foobarbar"));
254     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 2);
255 
256     ro.total_order_seek = true;
257     ASSERT_TRUE(db_->Get(ro, "foobarbar", &value).IsNotFound());
258     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 2);
259     ASSERT_EQ(
260         2,
261         (*(get_perf_context()->level_to_perf_context))[0].bloom_filter_useful);
262     get_perf_context()->Reset();
263   }
264 }
265 
TEST_F(DBBloomFilterTest,WholeKeyFilterProp)266 TEST_F(DBBloomFilterTest, WholeKeyFilterProp) {
267   for (bool partition_filters : {true, false}) {
268     Options options = last_options_;
269     options.prefix_extractor.reset(NewFixedPrefixTransform(3));
270     options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
271     get_perf_context()->EnablePerLevelPerfContext();
272 
273     BlockBasedTableOptions bbto;
274     bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
275     bbto.whole_key_filtering = false;
276     if (partition_filters) {
277       bbto.partition_filters = true;
278       bbto.index_type = BlockBasedTableOptions::IndexType::kTwoLevelIndexSearch;
279     }
280     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
281     DestroyAndReopen(options);
282 
283     WriteOptions wo;
284     ReadOptions ro;
285     FlushOptions fo;
286     fo.wait = true;
287     std::string value;
288 
289     ASSERT_OK(dbfull()->Put(wo, "foobar", "foo"));
290     // Needs insert some keys to make sure files are not filtered out by key
291     // ranges.
292     ASSERT_OK(dbfull()->Put(wo, "aaa", ""));
293     ASSERT_OK(dbfull()->Put(wo, "zzz", ""));
294     dbfull()->Flush(fo);
295 
296     Reopen(options);
297     ASSERT_EQ("NOT_FOUND", Get("foo"));
298     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
299     ASSERT_EQ("NOT_FOUND", Get("bar"));
300     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
301     ASSERT_EQ("foo", Get("foobar"));
302     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
303 
304     // Reopen with whole key filtering enabled and prefix extractor
305     // NULL. Bloom filter should be off for both of whole key and
306     // prefix bloom.
307     bbto.whole_key_filtering = true;
308     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
309     options.prefix_extractor.reset();
310     Reopen(options);
311 
312     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
313     ASSERT_EQ("NOT_FOUND", Get("foo"));
314     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
315     ASSERT_EQ("NOT_FOUND", Get("bar"));
316     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
317     ASSERT_EQ("foo", Get("foobar"));
318     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
319     // Write DB with only full key filtering.
320     ASSERT_OK(dbfull()->Put(wo, "foobar", "foo"));
321     // Needs insert some keys to make sure files are not filtered out by key
322     // ranges.
323     ASSERT_OK(dbfull()->Put(wo, "aaa", ""));
324     ASSERT_OK(dbfull()->Put(wo, "zzz", ""));
325     db_->CompactRange(CompactRangeOptions(), nullptr, nullptr);
326 
327     // Reopen with both of whole key off and prefix extractor enabled.
328     // Still no bloom filter should be used.
329     options.prefix_extractor.reset(NewFixedPrefixTransform(3));
330     bbto.whole_key_filtering = false;
331     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
332     Reopen(options);
333 
334     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
335     ASSERT_EQ("NOT_FOUND", Get("foo"));
336     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
337     ASSERT_EQ("NOT_FOUND", Get("bar"));
338     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
339     ASSERT_EQ("foo", Get("foobar"));
340     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
341 
342     // Try to create a DB with mixed files:
343     ASSERT_OK(dbfull()->Put(wo, "foobar", "foo"));
344     // Needs insert some keys to make sure files are not filtered out by key
345     // ranges.
346     ASSERT_OK(dbfull()->Put(wo, "aaa", ""));
347     ASSERT_OK(dbfull()->Put(wo, "zzz", ""));
348     db_->CompactRange(CompactRangeOptions(), nullptr, nullptr);
349 
350     options.prefix_extractor.reset();
351     bbto.whole_key_filtering = true;
352     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
353     Reopen(options);
354 
355     // Try to create a DB with mixed files.
356     ASSERT_OK(dbfull()->Put(wo, "barfoo", "bar"));
357     // In this case needs insert some keys to make sure files are
358     // not filtered out by key ranges.
359     ASSERT_OK(dbfull()->Put(wo, "aaa", ""));
360     ASSERT_OK(dbfull()->Put(wo, "zzz", ""));
361     Flush();
362 
363     // Now we have two files:
364     // File 1: An older file with prefix bloom.
365     // File 2: A newer file with whole bloom filter.
366     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 1);
367     ASSERT_EQ("NOT_FOUND", Get("foo"));
368     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 2);
369     ASSERT_EQ("NOT_FOUND", Get("bar"));
370     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 3);
371     ASSERT_EQ("foo", Get("foobar"));
372     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 4);
373     ASSERT_EQ("bar", Get("barfoo"));
374     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 4);
375 
376     // Reopen with the same setting: only whole key is used
377     Reopen(options);
378     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 4);
379     ASSERT_EQ("NOT_FOUND", Get("foo"));
380     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 5);
381     ASSERT_EQ("NOT_FOUND", Get("bar"));
382     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 6);
383     ASSERT_EQ("foo", Get("foobar"));
384     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 7);
385     ASSERT_EQ("bar", Get("barfoo"));
386     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 7);
387 
388     // Restart with both filters are allowed
389     options.prefix_extractor.reset(NewFixedPrefixTransform(3));
390     bbto.whole_key_filtering = true;
391     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
392     Reopen(options);
393     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 7);
394     // File 1 will has it filtered out.
395     // File 2 will not, as prefix `foo` exists in the file.
396     ASSERT_EQ("NOT_FOUND", Get("foo"));
397     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 8);
398     ASSERT_EQ("NOT_FOUND", Get("bar"));
399     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 10);
400     ASSERT_EQ("foo", Get("foobar"));
401     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 11);
402     ASSERT_EQ("bar", Get("barfoo"));
403     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 11);
404 
405     // Restart with only prefix bloom is allowed.
406     options.prefix_extractor.reset(NewFixedPrefixTransform(3));
407     bbto.whole_key_filtering = false;
408     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
409     Reopen(options);
410     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 11);
411     ASSERT_EQ("NOT_FOUND", Get("foo"));
412     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 11);
413     ASSERT_EQ("NOT_FOUND", Get("bar"));
414     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 12);
415     ASSERT_EQ("foo", Get("foobar"));
416     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 12);
417     ASSERT_EQ("bar", Get("barfoo"));
418     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 12);
419     uint64_t bloom_filter_useful_all_levels = 0;
420     for (auto& kv : (*(get_perf_context()->level_to_perf_context))) {
421       if (kv.second.bloom_filter_useful > 0) {
422         bloom_filter_useful_all_levels += kv.second.bloom_filter_useful;
423       }
424     }
425     ASSERT_EQ(12, bloom_filter_useful_all_levels);
426     get_perf_context()->Reset();
427   }
428 }
429 
TEST_P(DBBloomFilterTestWithParam,BloomFilter)430 TEST_P(DBBloomFilterTestWithParam, BloomFilter) {
431   do {
432     Options options = CurrentOptions();
433     env_->count_random_reads_ = true;
434     options.env = env_;
435     // ChangeCompactOptions() only changes compaction style, which does not
436     // trigger reset of table_factory
437     BlockBasedTableOptions table_options;
438     table_options.no_block_cache = true;
439     table_options.filter_policy.reset(new BFP(10, bfp_impl_));
440     table_options.partition_filters = partition_filters_;
441     if (partition_filters_) {
442       table_options.index_type =
443           BlockBasedTableOptions::IndexType::kTwoLevelIndexSearch;
444     }
445     table_options.format_version = format_version_;
446     if (format_version_ >= 4) {
447       // value delta encoding challenged more with index interval > 1
448       table_options.index_block_restart_interval = 8;
449     }
450     table_options.metadata_block_size = 32;
451     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
452 
453     CreateAndReopenWithCF({"pikachu"}, options);
454 
455     // Populate multiple layers
456     const int N = 10000;
457     for (int i = 0; i < N; i++) {
458       ASSERT_OK(Put(1, Key(i), Key(i)));
459     }
460     Compact(1, "a", "z");
461     for (int i = 0; i < N; i += 100) {
462       ASSERT_OK(Put(1, Key(i), Key(i)));
463     }
464     Flush(1);
465 
466     // Prevent auto compactions triggered by seeks
467     env_->delay_sstable_sync_.store(true, std::memory_order_release);
468 
469     // Lookup present keys.  Should rarely read from small sstable.
470     env_->random_read_counter_.Reset();
471     for (int i = 0; i < N; i++) {
472       ASSERT_EQ(Key(i), Get(1, Key(i)));
473     }
474     int reads = env_->random_read_counter_.Read();
475     fprintf(stderr, "%d present => %d reads\n", N, reads);
476     ASSERT_GE(reads, N);
477     if (partition_filters_) {
478       // Without block cache, we read an extra partition filter per each
479       // level*read and a partition index per each read
480       ASSERT_LE(reads, 4 * N + 2 * N / 100);
481     } else {
482       ASSERT_LE(reads, N + 2 * N / 100);
483     }
484 
485     // Lookup present keys.  Should rarely read from either sstable.
486     env_->random_read_counter_.Reset();
487     for (int i = 0; i < N; i++) {
488       ASSERT_EQ("NOT_FOUND", Get(1, Key(i) + ".missing"));
489     }
490     reads = env_->random_read_counter_.Read();
491     fprintf(stderr, "%d missing => %d reads\n", N, reads);
492     if (partition_filters_) {
493       // With partitioned filter we read one extra filter per level per each
494       // missed read.
495       ASSERT_LE(reads, 2 * N + 3 * N / 100);
496     } else {
497       ASSERT_LE(reads, 3 * N / 100);
498     }
499 
500     env_->delay_sstable_sync_.store(false, std::memory_order_release);
501     Close();
502   } while (ChangeCompactOptions());
503 }
504 
505 #ifndef ROCKSDB_VALGRIND_RUN
506 INSTANTIATE_TEST_CASE_P(
507     FormatDef, DBBloomFilterTestDefFormatVersion,
508     ::testing::Values(
509         std::make_tuple(BFP::kDeprecatedBlock, false,
510                         test::kDefaultFormatVersion),
511         std::make_tuple(BFP::kAuto, true, test::kDefaultFormatVersion),
512         std::make_tuple(BFP::kAuto, false, test::kDefaultFormatVersion)));
513 
514 INSTANTIATE_TEST_CASE_P(
515     FormatDef, DBBloomFilterTestWithParam,
516     ::testing::Values(
517         std::make_tuple(BFP::kDeprecatedBlock, false,
518                         test::kDefaultFormatVersion),
519         std::make_tuple(BFP::kAuto, true, test::kDefaultFormatVersion),
520         std::make_tuple(BFP::kAuto, false, test::kDefaultFormatVersion)));
521 
522 INSTANTIATE_TEST_CASE_P(
523     FormatLatest, DBBloomFilterTestWithParam,
524     ::testing::Values(
525         std::make_tuple(BFP::kDeprecatedBlock, false,
526                         test::kLatestFormatVersion),
527         std::make_tuple(BFP::kAuto, true, test::kLatestFormatVersion),
528         std::make_tuple(BFP::kAuto, false, test::kLatestFormatVersion)));
529 #endif  // ROCKSDB_VALGRIND_RUN
530 
TEST_F(DBBloomFilterTest,BloomFilterRate)531 TEST_F(DBBloomFilterTest, BloomFilterRate) {
532   while (ChangeFilterOptions()) {
533     Options options = CurrentOptions();
534     options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
535     get_perf_context()->EnablePerLevelPerfContext();
536     CreateAndReopenWithCF({"pikachu"}, options);
537 
538     const int maxKey = 10000;
539     for (int i = 0; i < maxKey; i++) {
540       ASSERT_OK(Put(1, Key(i), Key(i)));
541     }
542     // Add a large key to make the file contain wide range
543     ASSERT_OK(Put(1, Key(maxKey + 55555), Key(maxKey + 55555)));
544     Flush(1);
545 
546     // Check if they can be found
547     for (int i = 0; i < maxKey; i++) {
548       ASSERT_EQ(Key(i), Get(1, Key(i)));
549     }
550     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
551 
552     // Check if filter is useful
553     for (int i = 0; i < maxKey; i++) {
554       ASSERT_EQ("NOT_FOUND", Get(1, Key(i + 33333)));
555     }
556     ASSERT_GE(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), maxKey * 0.98);
557     ASSERT_GE(
558         (*(get_perf_context()->level_to_perf_context))[0].bloom_filter_useful,
559         maxKey * 0.98);
560     get_perf_context()->Reset();
561   }
562 }
563 
TEST_F(DBBloomFilterTest,BloomFilterCompatibility)564 TEST_F(DBBloomFilterTest, BloomFilterCompatibility) {
565   Options options = CurrentOptions();
566   options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
567   BlockBasedTableOptions table_options;
568   table_options.filter_policy.reset(NewBloomFilterPolicy(10, true));
569   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
570 
571   // Create with block based filter
572   CreateAndReopenWithCF({"pikachu"}, options);
573 
574   const int maxKey = 10000;
575   for (int i = 0; i < maxKey; i++) {
576     ASSERT_OK(Put(1, Key(i), Key(i)));
577   }
578   ASSERT_OK(Put(1, Key(maxKey + 55555), Key(maxKey + 55555)));
579   Flush(1);
580 
581   // Check db with full filter
582   table_options.filter_policy.reset(NewBloomFilterPolicy(10, false));
583   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
584   ReopenWithColumnFamilies({"default", "pikachu"}, options);
585 
586   // Check if they can be found
587   for (int i = 0; i < maxKey; i++) {
588     ASSERT_EQ(Key(i), Get(1, Key(i)));
589   }
590   ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
591 
592   // Check db with partitioned full filter
593   table_options.partition_filters = true;
594   table_options.index_type =
595       BlockBasedTableOptions::IndexType::kTwoLevelIndexSearch;
596   table_options.filter_policy.reset(NewBloomFilterPolicy(10, false));
597   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
598   ReopenWithColumnFamilies({"default", "pikachu"}, options);
599 
600   // Check if they can be found
601   for (int i = 0; i < maxKey; i++) {
602     ASSERT_EQ(Key(i), Get(1, Key(i)));
603   }
604   ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
605 }
606 
TEST_F(DBBloomFilterTest,BloomFilterReverseCompatibility)607 TEST_F(DBBloomFilterTest, BloomFilterReverseCompatibility) {
608   for (bool partition_filters : {true, false}) {
609     Options options = CurrentOptions();
610     options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
611     BlockBasedTableOptions table_options;
612     if (partition_filters) {
613       table_options.partition_filters = true;
614       table_options.index_type =
615           BlockBasedTableOptions::IndexType::kTwoLevelIndexSearch;
616     }
617     table_options.filter_policy.reset(NewBloomFilterPolicy(10, false));
618     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
619     DestroyAndReopen(options);
620 
621     // Create with full filter
622     CreateAndReopenWithCF({"pikachu"}, options);
623 
624     const int maxKey = 10000;
625     for (int i = 0; i < maxKey; i++) {
626       ASSERT_OK(Put(1, Key(i), Key(i)));
627     }
628     ASSERT_OK(Put(1, Key(maxKey + 55555), Key(maxKey + 55555)));
629     Flush(1);
630 
631     // Check db with block_based filter
632     table_options.filter_policy.reset(NewBloomFilterPolicy(10, true));
633     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
634     ReopenWithColumnFamilies({"default", "pikachu"}, options);
635 
636     // Check if they can be found
637     for (int i = 0; i < maxKey; i++) {
638       ASSERT_EQ(Key(i), Get(1, Key(i)));
639     }
640     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
641   }
642 }
643 
644 namespace {
645 // A wrapped bloom over block-based FilterPolicy
646 class TestingWrappedBlockBasedFilterPolicy : public FilterPolicy {
647  public:
TestingWrappedBlockBasedFilterPolicy(int bits_per_key)648   explicit TestingWrappedBlockBasedFilterPolicy(int bits_per_key)
649       : filter_(NewBloomFilterPolicy(bits_per_key, true)), counter_(0) {}
650 
~TestingWrappedBlockBasedFilterPolicy()651   ~TestingWrappedBlockBasedFilterPolicy() override { delete filter_; }
652 
Name() const653   const char* Name() const override {
654     return "TestingWrappedBlockBasedFilterPolicy";
655   }
656 
CreateFilter(const ROCKSDB_NAMESPACE::Slice * keys,int n,std::string * dst) const657   void CreateFilter(const ROCKSDB_NAMESPACE::Slice* keys, int n,
658                     std::string* dst) const override {
659     std::unique_ptr<ROCKSDB_NAMESPACE::Slice[]> user_keys(
660         new ROCKSDB_NAMESPACE::Slice[n]);
661     for (int i = 0; i < n; ++i) {
662       user_keys[i] = convertKey(keys[i]);
663     }
664     return filter_->CreateFilter(user_keys.get(), n, dst);
665   }
666 
KeyMayMatch(const ROCKSDB_NAMESPACE::Slice & key,const ROCKSDB_NAMESPACE::Slice & filter) const667   bool KeyMayMatch(const ROCKSDB_NAMESPACE::Slice& key,
668                    const ROCKSDB_NAMESPACE::Slice& filter) const override {
669     counter_++;
670     return filter_->KeyMayMatch(convertKey(key), filter);
671   }
672 
GetCounter()673   uint32_t GetCounter() { return counter_; }
674 
675  private:
676   const FilterPolicy* filter_;
677   mutable uint32_t counter_;
678 
convertKey(const ROCKSDB_NAMESPACE::Slice & key) const679   ROCKSDB_NAMESPACE::Slice convertKey(
680       const ROCKSDB_NAMESPACE::Slice& key) const {
681     return key;
682   }
683 };
684 }  // namespace
685 
TEST_F(DBBloomFilterTest,WrappedBlockBasedFilterPolicy)686 TEST_F(DBBloomFilterTest, WrappedBlockBasedFilterPolicy) {
687   Options options = CurrentOptions();
688   options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
689 
690   BlockBasedTableOptions table_options;
691   TestingWrappedBlockBasedFilterPolicy* policy =
692       new TestingWrappedBlockBasedFilterPolicy(10);
693   table_options.filter_policy.reset(policy);
694   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
695 
696   CreateAndReopenWithCF({"pikachu"}, options);
697 
698   const int maxKey = 10000;
699   for (int i = 0; i < maxKey; i++) {
700     ASSERT_OK(Put(1, Key(i), Key(i)));
701   }
702   // Add a large key to make the file contain wide range
703   ASSERT_OK(Put(1, Key(maxKey + 55555), Key(maxKey + 55555)));
704   ASSERT_EQ(0U, policy->GetCounter());
705   Flush(1);
706 
707   // Check if they can be found
708   for (int i = 0; i < maxKey; i++) {
709     ASSERT_EQ(Key(i), Get(1, Key(i)));
710   }
711   ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
712   ASSERT_EQ(1U * maxKey, policy->GetCounter());
713 
714   // Check if filter is useful
715   for (int i = 0; i < maxKey; i++) {
716     ASSERT_EQ("NOT_FOUND", Get(1, Key(i + 33333)));
717   }
718   ASSERT_GE(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), maxKey * 0.98);
719   ASSERT_EQ(2U * maxKey, policy->GetCounter());
720 }
721 
722 namespace {
723 // NOTE: This class is referenced by HISTORY.md as a model for a wrapper
724 // FilterPolicy selecting among configurations based on context.
725 class LevelAndStyleCustomFilterPolicy : public FilterPolicy {
726  public:
LevelAndStyleCustomFilterPolicy(int bpk_fifo,int bpk_l0_other,int bpk_otherwise)727   explicit LevelAndStyleCustomFilterPolicy(int bpk_fifo, int bpk_l0_other,
728                                            int bpk_otherwise)
729       : policy_fifo_(NewBloomFilterPolicy(bpk_fifo)),
730         policy_l0_other_(NewBloomFilterPolicy(bpk_l0_other)),
731         policy_otherwise_(NewBloomFilterPolicy(bpk_otherwise)) {}
732 
733   // OK to use built-in policy name because we are deferring to a
734   // built-in builder. We aren't changing the serialized format.
Name() const735   const char* Name() const override { return policy_fifo_->Name(); }
736 
GetBuilderWithContext(const FilterBuildingContext & context) const737   FilterBitsBuilder* GetBuilderWithContext(
738       const FilterBuildingContext& context) const override {
739     if (context.compaction_style == kCompactionStyleFIFO) {
740       return policy_fifo_->GetBuilderWithContext(context);
741     } else if (context.level_at_creation == 0) {
742       return policy_l0_other_->GetBuilderWithContext(context);
743     } else {
744       return policy_otherwise_->GetBuilderWithContext(context);
745     }
746   }
747 
GetFilterBitsReader(const Slice & contents) const748   FilterBitsReader* GetFilterBitsReader(const Slice& contents) const override {
749     // OK to defer to any of them; they all can parse built-in filters
750     // from any settings.
751     return policy_fifo_->GetFilterBitsReader(contents);
752   }
753 
754   // Defer just in case configuration uses block-based filter
CreateFilter(const Slice * keys,int n,std::string * dst) const755   void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
756     policy_otherwise_->CreateFilter(keys, n, dst);
757   }
KeyMayMatch(const Slice & key,const Slice & filter) const758   bool KeyMayMatch(const Slice& key, const Slice& filter) const override {
759     return policy_otherwise_->KeyMayMatch(key, filter);
760   }
761 
762  private:
763   const std::unique_ptr<const FilterPolicy> policy_fifo_;
764   const std::unique_ptr<const FilterPolicy> policy_l0_other_;
765   const std::unique_ptr<const FilterPolicy> policy_otherwise_;
766 };
767 
768 class TestingContextCustomFilterPolicy
769     : public LevelAndStyleCustomFilterPolicy {
770  public:
TestingContextCustomFilterPolicy(int bpk_fifo,int bpk_l0_other,int bpk_otherwise)771   explicit TestingContextCustomFilterPolicy(int bpk_fifo, int bpk_l0_other,
772                                             int bpk_otherwise)
773       : LevelAndStyleCustomFilterPolicy(bpk_fifo, bpk_l0_other, bpk_otherwise) {
774   }
775 
GetBuilderWithContext(const FilterBuildingContext & context) const776   FilterBitsBuilder* GetBuilderWithContext(
777       const FilterBuildingContext& context) const override {
778     test_report_ += "cf=";
779     test_report_ += context.column_family_name;
780     test_report_ += ",cs=";
781     test_report_ +=
782         OptionsHelper::compaction_style_to_string[context.compaction_style];
783     test_report_ += ",lv=";
784     test_report_ += std::to_string(context.level_at_creation);
785     test_report_ += "\n";
786 
787     return LevelAndStyleCustomFilterPolicy::GetBuilderWithContext(context);
788   }
789 
DumpTestReport()790   std::string DumpTestReport() {
791     std::string rv;
792     std::swap(rv, test_report_);
793     return rv;
794   }
795 
796  private:
797   mutable std::string test_report_;
798 };
799 }  // namespace
800 
TEST_F(DBBloomFilterTest,ContextCustomFilterPolicy)801 TEST_F(DBBloomFilterTest, ContextCustomFilterPolicy) {
802   for (bool fifo : {true, false}) {
803     Options options = CurrentOptions();
804     options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
805     options.compaction_style =
806         fifo ? kCompactionStyleFIFO : kCompactionStyleLevel;
807 
808     BlockBasedTableOptions table_options;
809     auto policy = std::make_shared<TestingContextCustomFilterPolicy>(15, 8, 5);
810     table_options.filter_policy = policy;
811     table_options.format_version = 5;
812     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
813 
814     CreateAndReopenWithCF({fifo ? "abe" : "bob"}, options);
815 
816     const int maxKey = 10000;
817     for (int i = 0; i < maxKey / 2; i++) {
818       ASSERT_OK(Put(1, Key(i), Key(i)));
819     }
820     // Add a large key to make the file contain wide range
821     ASSERT_OK(Put(1, Key(maxKey + 55555), Key(maxKey + 55555)));
822     Flush(1);
823     EXPECT_EQ(policy->DumpTestReport(),
824               fifo ? "cf=abe,cs=kCompactionStyleFIFO,lv=0\n"
825                    : "cf=bob,cs=kCompactionStyleLevel,lv=0\n");
826 
827     for (int i = maxKey / 2; i < maxKey; i++) {
828       ASSERT_OK(Put(1, Key(i), Key(i)));
829     }
830     Flush(1);
831     EXPECT_EQ(policy->DumpTestReport(),
832               fifo ? "cf=abe,cs=kCompactionStyleFIFO,lv=0\n"
833                    : "cf=bob,cs=kCompactionStyleLevel,lv=0\n");
834 
835     // Check that they can be found
836     for (int i = 0; i < maxKey; i++) {
837       ASSERT_EQ(Key(i), Get(1, Key(i)));
838     }
839     // Since we have two tables / two filters, we might have Bloom checks on
840     // our queries, but no more than one "useful" per query on a found key.
841     EXPECT_LE(TestGetAndResetTickerCount(options, BLOOM_FILTER_USEFUL), maxKey);
842 
843     // Check that we have two filters, each about
844     // fifo: 0.12% FP rate (15 bits per key)
845     // level: 2.3% FP rate (8 bits per key)
846     for (int i = 0; i < maxKey; i++) {
847       ASSERT_EQ("NOT_FOUND", Get(1, Key(i + 33333)));
848     }
849     {
850       auto useful_count =
851           TestGetAndResetTickerCount(options, BLOOM_FILTER_USEFUL);
852       EXPECT_GE(useful_count, maxKey * 2 * (fifo ? 0.9980 : 0.975));
853       EXPECT_LE(useful_count, maxKey * 2 * (fifo ? 0.9995 : 0.98));
854     }
855 
856     if (!fifo) {  // FIFO only has L0
857       // Full compaction
858       ASSERT_OK(db_->CompactRange(CompactRangeOptions(), handles_[1], nullptr,
859                                   nullptr));
860       EXPECT_EQ(policy->DumpTestReport(),
861                 "cf=bob,cs=kCompactionStyleLevel,lv=1\n");
862 
863       // Check that we now have one filter, about 9.2% FP rate (5 bits per key)
864       for (int i = 0; i < maxKey; i++) {
865         ASSERT_EQ("NOT_FOUND", Get(1, Key(i + 33333)));
866       }
867       {
868         auto useful_count =
869             TestGetAndResetTickerCount(options, BLOOM_FILTER_USEFUL);
870         EXPECT_GE(useful_count, maxKey * 0.90);
871         EXPECT_LE(useful_count, maxKey * 0.91);
872       }
873     }
874 
875     // Destroy
876     ASSERT_OK(dbfull()->DropColumnFamily(handles_[1]));
877     dbfull()->DestroyColumnFamilyHandle(handles_[1]);
878     handles_[1] = nullptr;
879   }
880 }
881 
882 class SliceTransformLimitedDomain : public SliceTransform {
Name() const883   const char* Name() const override { return "SliceTransformLimitedDomain"; }
884 
Transform(const Slice & src) const885   Slice Transform(const Slice& src) const override {
886     return Slice(src.data(), 5);
887   }
888 
InDomain(const Slice & src) const889   bool InDomain(const Slice& src) const override {
890     // prefix will be x????
891     return src.size() >= 5 && src[0] == 'x';
892   }
893 
InRange(const Slice & dst) const894   bool InRange(const Slice& dst) const override {
895     // prefix will be x????
896     return dst.size() == 5 && dst[0] == 'x';
897   }
898 };
899 
TEST_F(DBBloomFilterTest,PrefixExtractorFullFilter)900 TEST_F(DBBloomFilterTest, PrefixExtractorFullFilter) {
901   BlockBasedTableOptions bbto;
902   // Full Filter Block
903   bbto.filter_policy.reset(ROCKSDB_NAMESPACE::NewBloomFilterPolicy(10, false));
904   bbto.whole_key_filtering = false;
905 
906   Options options = CurrentOptions();
907   options.prefix_extractor = std::make_shared<SliceTransformLimitedDomain>();
908   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
909 
910   DestroyAndReopen(options);
911 
912   ASSERT_OK(Put("x1111_AAAA", "val1"));
913   ASSERT_OK(Put("x1112_AAAA", "val2"));
914   ASSERT_OK(Put("x1113_AAAA", "val3"));
915   ASSERT_OK(Put("x1114_AAAA", "val4"));
916   // Not in domain, wont be added to filter
917   ASSERT_OK(Put("zzzzz_AAAA", "val5"));
918 
919   ASSERT_OK(Flush());
920 
921   ASSERT_EQ(Get("x1111_AAAA"), "val1");
922   ASSERT_EQ(Get("x1112_AAAA"), "val2");
923   ASSERT_EQ(Get("x1113_AAAA"), "val3");
924   ASSERT_EQ(Get("x1114_AAAA"), "val4");
925   // Was not added to filter but rocksdb will try to read it from the filter
926   ASSERT_EQ(Get("zzzzz_AAAA"), "val5");
927 }
928 
TEST_F(DBBloomFilterTest,PrefixExtractorBlockFilter)929 TEST_F(DBBloomFilterTest, PrefixExtractorBlockFilter) {
930   BlockBasedTableOptions bbto;
931   // Block Filter Block
932   bbto.filter_policy.reset(ROCKSDB_NAMESPACE::NewBloomFilterPolicy(10, true));
933 
934   Options options = CurrentOptions();
935   options.prefix_extractor = std::make_shared<SliceTransformLimitedDomain>();
936   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
937 
938   DestroyAndReopen(options);
939 
940   ASSERT_OK(Put("x1113_AAAA", "val3"));
941   ASSERT_OK(Put("x1114_AAAA", "val4"));
942   // Not in domain, wont be added to filter
943   ASSERT_OK(Put("zzzzz_AAAA", "val1"));
944   ASSERT_OK(Put("zzzzz_AAAB", "val2"));
945   ASSERT_OK(Put("zzzzz_AAAC", "val3"));
946   ASSERT_OK(Put("zzzzz_AAAD", "val4"));
947 
948   ASSERT_OK(Flush());
949 
950   std::vector<std::string> iter_res;
951   auto iter = db_->NewIterator(ReadOptions());
952   // Seek to a key that was not in Domain
953   for (iter->Seek("zzzzz_AAAA"); iter->Valid(); iter->Next()) {
954     iter_res.emplace_back(iter->value().ToString());
955   }
956 
957   std::vector<std::string> expected_res = {"val1", "val2", "val3", "val4"};
958   ASSERT_EQ(iter_res, expected_res);
959   delete iter;
960 }
961 
TEST_F(DBBloomFilterTest,MemtableWholeKeyBloomFilter)962 TEST_F(DBBloomFilterTest, MemtableWholeKeyBloomFilter) {
963   // regression test for #2743. the range delete tombstones in memtable should
964   // be added even when Get() skips searching due to its prefix bloom filter
965   const int kMemtableSize = 1 << 20;              // 1MB
966   const int kMemtablePrefixFilterSize = 1 << 13;  // 8KB
967   const int kPrefixLen = 4;
968   Options options = CurrentOptions();
969   options.memtable_prefix_bloom_size_ratio =
970       static_cast<double>(kMemtablePrefixFilterSize) / kMemtableSize;
971   options.prefix_extractor.reset(
972       ROCKSDB_NAMESPACE::NewFixedPrefixTransform(kPrefixLen));
973   options.write_buffer_size = kMemtableSize;
974   options.memtable_whole_key_filtering = false;
975   Reopen(options);
976   std::string key1("AAAABBBB");
977   std::string key2("AAAACCCC");  // not in DB
978   std::string key3("AAAADDDD");
979   std::string key4("AAAAEEEE");
980   std::string value1("Value1");
981   std::string value3("Value3");
982   std::string value4("Value4");
983 
984   ASSERT_OK(Put(key1, value1, WriteOptions()));
985 
986   // check memtable bloom stats
987   ASSERT_EQ("NOT_FOUND", Get(key2));
988   ASSERT_EQ(0, get_perf_context()->bloom_memtable_miss_count);
989   // same prefix, bloom filter false positive
990   ASSERT_EQ(1, get_perf_context()->bloom_memtable_hit_count);
991 
992   // enable whole key bloom filter
993   options.memtable_whole_key_filtering = true;
994   Reopen(options);
995   // check memtable bloom stats
996   ASSERT_OK(Put(key3, value3, WriteOptions()));
997   ASSERT_EQ("NOT_FOUND", Get(key2));
998   // whole key bloom filter kicks in and determines it's a miss
999   ASSERT_EQ(1, get_perf_context()->bloom_memtable_miss_count);
1000   ASSERT_EQ(1, get_perf_context()->bloom_memtable_hit_count);
1001 
1002   // verify whole key filtering does not depend on prefix_extractor
1003   options.prefix_extractor.reset();
1004   Reopen(options);
1005   // check memtable bloom stats
1006   ASSERT_OK(Put(key4, value4, WriteOptions()));
1007   ASSERT_EQ("NOT_FOUND", Get(key2));
1008   // whole key bloom filter kicks in and determines it's a miss
1009   ASSERT_EQ(2, get_perf_context()->bloom_memtable_miss_count);
1010   ASSERT_EQ(1, get_perf_context()->bloom_memtable_hit_count);
1011 }
1012 
TEST_F(DBBloomFilterTest,MemtablePrefixBloomOutOfDomain)1013 TEST_F(DBBloomFilterTest, MemtablePrefixBloomOutOfDomain) {
1014   constexpr size_t kPrefixSize = 8;
1015   const std::string kKey = "key";
1016   assert(kKey.size() < kPrefixSize);
1017   Options options = CurrentOptions();
1018   options.prefix_extractor.reset(NewFixedPrefixTransform(kPrefixSize));
1019   options.memtable_prefix_bloom_size_ratio = 0.25;
1020   Reopen(options);
1021   ASSERT_OK(Put(kKey, "v"));
1022   ASSERT_EQ("v", Get(kKey));
1023   std::unique_ptr<Iterator> iter(dbfull()->NewIterator(ReadOptions()));
1024   iter->Seek(kKey);
1025   ASSERT_TRUE(iter->Valid());
1026   ASSERT_EQ(kKey, iter->key());
1027   iter->SeekForPrev(kKey);
1028   ASSERT_TRUE(iter->Valid());
1029   ASSERT_EQ(kKey, iter->key());
1030 }
1031 
1032 #ifndef ROCKSDB_LITE
1033 namespace {
1034 namespace BFP2 {
1035 // Extends BFP::Mode with option to use Plain table
1036 using PseudoMode = int;
1037 static constexpr PseudoMode kPlainTable = -1;
1038 }  // namespace BFP2
1039 }  // namespace
1040 
1041 class BloomStatsTestWithParam
1042     : public DBBloomFilterTest,
1043       public testing::WithParamInterface<std::tuple<BFP2::PseudoMode, bool>> {
1044  public:
BloomStatsTestWithParam()1045   BloomStatsTestWithParam() {
1046     bfp_impl_ = std::get<0>(GetParam());
1047     partition_filters_ = std::get<1>(GetParam());
1048 
1049     options_.create_if_missing = true;
1050     options_.prefix_extractor.reset(
1051         ROCKSDB_NAMESPACE::NewFixedPrefixTransform(4));
1052     options_.memtable_prefix_bloom_size_ratio =
1053         8.0 * 1024.0 / static_cast<double>(options_.write_buffer_size);
1054     if (bfp_impl_ == BFP2::kPlainTable) {
1055       assert(!partition_filters_);  // not supported in plain table
1056       PlainTableOptions table_options;
1057       options_.table_factory.reset(NewPlainTableFactory(table_options));
1058     } else {
1059       BlockBasedTableOptions table_options;
1060       table_options.hash_index_allow_collision = false;
1061       if (partition_filters_) {
1062         assert(bfp_impl_ != BFP::kDeprecatedBlock);
1063         table_options.partition_filters = partition_filters_;
1064         table_options.index_type =
1065             BlockBasedTableOptions::IndexType::kTwoLevelIndexSearch;
1066       }
1067       table_options.filter_policy.reset(
1068           new BFP(10, static_cast<BFP::Mode>(bfp_impl_)));
1069       options_.table_factory.reset(NewBlockBasedTableFactory(table_options));
1070     }
1071     options_.env = env_;
1072 
1073     get_perf_context()->Reset();
1074     DestroyAndReopen(options_);
1075   }
1076 
~BloomStatsTestWithParam()1077   ~BloomStatsTestWithParam() override {
1078     get_perf_context()->Reset();
1079     Destroy(options_);
1080   }
1081 
1082   // Required if inheriting from testing::WithParamInterface<>
SetUpTestCase()1083   static void SetUpTestCase() {}
TearDownTestCase()1084   static void TearDownTestCase() {}
1085 
1086   BFP2::PseudoMode bfp_impl_;
1087   bool partition_filters_;
1088   Options options_;
1089 };
1090 
1091 // 1 Insert 2 K-V pairs into DB
1092 // 2 Call Get() for both keys - expext memtable bloom hit stat to be 2
1093 // 3 Call Get() for nonexisting key - expect memtable bloom miss stat to be 1
1094 // 4 Call Flush() to create SST
1095 // 5 Call Get() for both keys - expext SST bloom hit stat to be 2
1096 // 6 Call Get() for nonexisting key - expect SST bloom miss stat to be 1
1097 // Test both: block and plain SST
TEST_P(BloomStatsTestWithParam,BloomStatsTest)1098 TEST_P(BloomStatsTestWithParam, BloomStatsTest) {
1099   std::string key1("AAAA");
1100   std::string key2("RXDB");  // not in DB
1101   std::string key3("ZBRA");
1102   std::string value1("Value1");
1103   std::string value3("Value3");
1104 
1105   ASSERT_OK(Put(key1, value1, WriteOptions()));
1106   ASSERT_OK(Put(key3, value3, WriteOptions()));
1107 
1108   // check memtable bloom stats
1109   ASSERT_EQ(value1, Get(key1));
1110   ASSERT_EQ(1, get_perf_context()->bloom_memtable_hit_count);
1111   ASSERT_EQ(value3, Get(key3));
1112   ASSERT_EQ(2, get_perf_context()->bloom_memtable_hit_count);
1113   ASSERT_EQ(0, get_perf_context()->bloom_memtable_miss_count);
1114 
1115   ASSERT_EQ("NOT_FOUND", Get(key2));
1116   ASSERT_EQ(1, get_perf_context()->bloom_memtable_miss_count);
1117   ASSERT_EQ(2, get_perf_context()->bloom_memtable_hit_count);
1118 
1119   // sanity checks
1120   ASSERT_EQ(0, get_perf_context()->bloom_sst_hit_count);
1121   ASSERT_EQ(0, get_perf_context()->bloom_sst_miss_count);
1122 
1123   Flush();
1124 
1125   // sanity checks
1126   ASSERT_EQ(0, get_perf_context()->bloom_sst_hit_count);
1127   ASSERT_EQ(0, get_perf_context()->bloom_sst_miss_count);
1128 
1129   // check SST bloom stats
1130   ASSERT_EQ(value1, Get(key1));
1131   ASSERT_EQ(1, get_perf_context()->bloom_sst_hit_count);
1132   ASSERT_EQ(value3, Get(key3));
1133   ASSERT_EQ(2, get_perf_context()->bloom_sst_hit_count);
1134 
1135   ASSERT_EQ("NOT_FOUND", Get(key2));
1136   ASSERT_EQ(1, get_perf_context()->bloom_sst_miss_count);
1137 }
1138 
1139 // Same scenario as in BloomStatsTest but using an iterator
TEST_P(BloomStatsTestWithParam,BloomStatsTestWithIter)1140 TEST_P(BloomStatsTestWithParam, BloomStatsTestWithIter) {
1141   std::string key1("AAAA");
1142   std::string key2("RXDB");  // not in DB
1143   std::string key3("ZBRA");
1144   std::string value1("Value1");
1145   std::string value3("Value3");
1146 
1147   ASSERT_OK(Put(key1, value1, WriteOptions()));
1148   ASSERT_OK(Put(key3, value3, WriteOptions()));
1149 
1150   std::unique_ptr<Iterator> iter(dbfull()->NewIterator(ReadOptions()));
1151 
1152   // check memtable bloom stats
1153   iter->Seek(key1);
1154   ASSERT_OK(iter->status());
1155   ASSERT_TRUE(iter->Valid());
1156   ASSERT_EQ(value1, iter->value().ToString());
1157   ASSERT_EQ(1, get_perf_context()->bloom_memtable_hit_count);
1158   ASSERT_EQ(0, get_perf_context()->bloom_memtable_miss_count);
1159 
1160   iter->Seek(key3);
1161   ASSERT_OK(iter->status());
1162   ASSERT_TRUE(iter->Valid());
1163   ASSERT_EQ(value3, iter->value().ToString());
1164   ASSERT_EQ(2, get_perf_context()->bloom_memtable_hit_count);
1165   ASSERT_EQ(0, get_perf_context()->bloom_memtable_miss_count);
1166 
1167   iter->Seek(key2);
1168   ASSERT_OK(iter->status());
1169   ASSERT_TRUE(!iter->Valid());
1170   ASSERT_EQ(1, get_perf_context()->bloom_memtable_miss_count);
1171   ASSERT_EQ(2, get_perf_context()->bloom_memtable_hit_count);
1172 
1173   Flush();
1174 
1175   iter.reset(dbfull()->NewIterator(ReadOptions()));
1176 
1177   // Check SST bloom stats
1178   iter->Seek(key1);
1179   ASSERT_OK(iter->status());
1180   ASSERT_TRUE(iter->Valid());
1181   ASSERT_EQ(value1, iter->value().ToString());
1182   ASSERT_EQ(1, get_perf_context()->bloom_sst_hit_count);
1183 
1184   iter->Seek(key3);
1185   ASSERT_OK(iter->status());
1186   ASSERT_TRUE(iter->Valid());
1187   ASSERT_EQ(value3, iter->value().ToString());
1188   // The seek doesn't check block-based bloom filter because last index key
1189   // starts with the same prefix we're seeking to.
1190   uint64_t expected_hits = bfp_impl_ == BFP::kDeprecatedBlock ? 1 : 2;
1191   ASSERT_EQ(expected_hits, get_perf_context()->bloom_sst_hit_count);
1192 
1193   iter->Seek(key2);
1194   ASSERT_OK(iter->status());
1195   ASSERT_TRUE(!iter->Valid());
1196   ASSERT_EQ(1, get_perf_context()->bloom_sst_miss_count);
1197   ASSERT_EQ(expected_hits, get_perf_context()->bloom_sst_hit_count);
1198 }
1199 
1200 INSTANTIATE_TEST_CASE_P(
1201     BloomStatsTestWithParam, BloomStatsTestWithParam,
1202     ::testing::Values(std::make_tuple(BFP::kDeprecatedBlock, false),
1203                       std::make_tuple(BFP::kLegacyBloom, false),
1204                       std::make_tuple(BFP::kLegacyBloom, true),
1205                       std::make_tuple(BFP::kFastLocalBloom, false),
1206                       std::make_tuple(BFP::kFastLocalBloom, true),
1207                       std::make_tuple(BFP2::kPlainTable, false)));
1208 
1209 namespace {
PrefixScanInit(DBBloomFilterTest * dbtest)1210 void PrefixScanInit(DBBloomFilterTest* dbtest) {
1211   char buf[100];
1212   std::string keystr;
1213   const int small_range_sstfiles = 5;
1214   const int big_range_sstfiles = 5;
1215 
1216   // Generate 11 sst files with the following prefix ranges.
1217   // GROUP 0: [0,10]                              (level 1)
1218   // GROUP 1: [1,2], [2,3], [3,4], [4,5], [5, 6]  (level 0)
1219   // GROUP 2: [0,6], [0,7], [0,8], [0,9], [0,10]  (level 0)
1220   //
1221   // A seek with the previous API would do 11 random I/Os (to all the
1222   // files).  With the new API and a prefix filter enabled, we should
1223   // only do 2 random I/O, to the 2 files containing the key.
1224 
1225   // GROUP 0
1226   snprintf(buf, sizeof(buf), "%02d______:start", 0);
1227   keystr = std::string(buf);
1228   ASSERT_OK(dbtest->Put(keystr, keystr));
1229   snprintf(buf, sizeof(buf), "%02d______:end", 10);
1230   keystr = std::string(buf);
1231   ASSERT_OK(dbtest->Put(keystr, keystr));
1232   dbtest->Flush();
1233   dbtest->dbfull()->CompactRange(CompactRangeOptions(), nullptr,
1234                                  nullptr);  // move to level 1
1235 
1236   // GROUP 1
1237   for (int i = 1; i <= small_range_sstfiles; i++) {
1238     snprintf(buf, sizeof(buf), "%02d______:start", i);
1239     keystr = std::string(buf);
1240     ASSERT_OK(dbtest->Put(keystr, keystr));
1241     snprintf(buf, sizeof(buf), "%02d______:end", i + 1);
1242     keystr = std::string(buf);
1243     ASSERT_OK(dbtest->Put(keystr, keystr));
1244     dbtest->Flush();
1245   }
1246 
1247   // GROUP 2
1248   for (int i = 1; i <= big_range_sstfiles; i++) {
1249     snprintf(buf, sizeof(buf), "%02d______:start", 0);
1250     keystr = std::string(buf);
1251     ASSERT_OK(dbtest->Put(keystr, keystr));
1252     snprintf(buf, sizeof(buf), "%02d______:end", small_range_sstfiles + i + 1);
1253     keystr = std::string(buf);
1254     ASSERT_OK(dbtest->Put(keystr, keystr));
1255     dbtest->Flush();
1256   }
1257 }
1258 }  // namespace
1259 
TEST_F(DBBloomFilterTest,PrefixScan)1260 TEST_F(DBBloomFilterTest, PrefixScan) {
1261   while (ChangeFilterOptions()) {
1262     int count;
1263     Slice prefix;
1264     Slice key;
1265     char buf[100];
1266     Iterator* iter;
1267     snprintf(buf, sizeof(buf), "03______:");
1268     prefix = Slice(buf, 8);
1269     key = Slice(buf, 9);
1270     ASSERT_EQ(key.difference_offset(prefix), 8);
1271     ASSERT_EQ(prefix.difference_offset(key), 8);
1272     // db configs
1273     env_->count_random_reads_ = true;
1274     Options options = CurrentOptions();
1275     options.env = env_;
1276     options.prefix_extractor.reset(NewFixedPrefixTransform(8));
1277     options.disable_auto_compactions = true;
1278     options.max_background_compactions = 2;
1279     options.create_if_missing = true;
1280     options.memtable_factory.reset(NewHashSkipListRepFactory(16));
1281     assert(!options.unordered_write);
1282     // It is incompatible with allow_concurrent_memtable_write=false
1283     options.allow_concurrent_memtable_write = false;
1284 
1285     BlockBasedTableOptions table_options;
1286     table_options.no_block_cache = true;
1287     table_options.filter_policy.reset(NewBloomFilterPolicy(10));
1288     table_options.whole_key_filtering = false;
1289     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1290 
1291     // 11 RAND I/Os
1292     DestroyAndReopen(options);
1293     PrefixScanInit(this);
1294     count = 0;
1295     env_->random_read_counter_.Reset();
1296     iter = db_->NewIterator(ReadOptions());
1297     for (iter->Seek(prefix); iter->Valid(); iter->Next()) {
1298       if (!iter->key().starts_with(prefix)) {
1299         break;
1300       }
1301       count++;
1302     }
1303     ASSERT_OK(iter->status());
1304     delete iter;
1305     ASSERT_EQ(count, 2);
1306     ASSERT_EQ(env_->random_read_counter_.Read(), 2);
1307     Close();
1308   }  // end of while
1309 }
1310 
TEST_F(DBBloomFilterTest,OptimizeFiltersForHits)1311 TEST_F(DBBloomFilterTest, OptimizeFiltersForHits) {
1312   Options options = CurrentOptions();
1313   options.write_buffer_size = 64 * 1024;
1314   options.arena_block_size = 4 * 1024;
1315   options.target_file_size_base = 64 * 1024;
1316   options.level0_file_num_compaction_trigger = 2;
1317   options.level0_slowdown_writes_trigger = 2;
1318   options.level0_stop_writes_trigger = 4;
1319   options.max_bytes_for_level_base = 256 * 1024;
1320   options.max_write_buffer_number = 2;
1321   options.max_background_compactions = 8;
1322   options.max_background_flushes = 8;
1323   options.compression = kNoCompression;
1324   options.compaction_style = kCompactionStyleLevel;
1325   options.level_compaction_dynamic_level_bytes = true;
1326   BlockBasedTableOptions bbto;
1327   bbto.cache_index_and_filter_blocks = true;
1328   bbto.filter_policy.reset(NewBloomFilterPolicy(10, true));
1329   bbto.whole_key_filtering = true;
1330   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
1331   options.optimize_filters_for_hits = true;
1332   options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
1333   get_perf_context()->Reset();
1334   get_perf_context()->EnablePerLevelPerfContext();
1335   CreateAndReopenWithCF({"mypikachu"}, options);
1336 
1337   int numkeys = 200000;
1338 
1339   // Generate randomly shuffled keys, so the updates are almost
1340   // random.
1341   std::vector<int> keys;
1342   keys.reserve(numkeys);
1343   for (int i = 0; i < numkeys; i += 2) {
1344     keys.push_back(i);
1345   }
1346   std::random_shuffle(std::begin(keys), std::end(keys));
1347 
1348   int num_inserted = 0;
1349   for (int key : keys) {
1350     ASSERT_OK(Put(1, Key(key), "val"));
1351     if (++num_inserted % 1000 == 0) {
1352       dbfull()->TEST_WaitForFlushMemTable();
1353       dbfull()->TEST_WaitForCompact();
1354     }
1355   }
1356   ASSERT_OK(Put(1, Key(0), "val"));
1357   ASSERT_OK(Put(1, Key(numkeys), "val"));
1358   ASSERT_OK(Flush(1));
1359   dbfull()->TEST_WaitForCompact();
1360 
1361   if (NumTableFilesAtLevel(0, 1) == 0) {
1362     // No Level 0 file. Create one.
1363     ASSERT_OK(Put(1, Key(0), "val"));
1364     ASSERT_OK(Put(1, Key(numkeys), "val"));
1365     ASSERT_OK(Flush(1));
1366     dbfull()->TEST_WaitForCompact();
1367   }
1368 
1369   for (int i = 1; i < numkeys; i += 2) {
1370     ASSERT_EQ(Get(1, Key(i)), "NOT_FOUND");
1371   }
1372 
1373   ASSERT_EQ(0, TestGetTickerCount(options, GET_HIT_L0));
1374   ASSERT_EQ(0, TestGetTickerCount(options, GET_HIT_L1));
1375   ASSERT_EQ(0, TestGetTickerCount(options, GET_HIT_L2_AND_UP));
1376 
1377   // Now we have three sorted run, L0, L5 and L6 with most files in L6 have
1378   // no bloom filter. Most keys be checked bloom filters twice.
1379   ASSERT_GT(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 65000 * 2);
1380   ASSERT_LT(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 120000 * 2);
1381   uint64_t bloom_filter_useful_all_levels = 0;
1382   for (auto& kv : (*(get_perf_context()->level_to_perf_context))) {
1383     if (kv.second.bloom_filter_useful > 0) {
1384       bloom_filter_useful_all_levels += kv.second.bloom_filter_useful;
1385     }
1386   }
1387   ASSERT_GT(bloom_filter_useful_all_levels, 65000 * 2);
1388   ASSERT_LT(bloom_filter_useful_all_levels, 120000 * 2);
1389 
1390   for (int i = 0; i < numkeys; i += 2) {
1391     ASSERT_EQ(Get(1, Key(i)), "val");
1392   }
1393 
1394   // Part 2 (read path): rewrite last level with blooms, then verify they get
1395   // cached only if !optimize_filters_for_hits
1396   options.disable_auto_compactions = true;
1397   options.num_levels = 9;
1398   options.optimize_filters_for_hits = false;
1399   options.statistics = CreateDBStatistics();
1400   bbto.block_cache.reset();
1401   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
1402 
1403   ReopenWithColumnFamilies({"default", "mypikachu"}, options);
1404   MoveFilesToLevel(7 /* level */, 1 /* column family index */);
1405 
1406   std::string value = Get(1, Key(0));
1407   uint64_t prev_cache_filter_hits =
1408       TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT);
1409   value = Get(1, Key(0));
1410   ASSERT_EQ(prev_cache_filter_hits + 1,
1411             TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT));
1412 
1413   // Now that we know the filter blocks exist in the last level files, see if
1414   // filter caching is skipped for this optimization
1415   options.optimize_filters_for_hits = true;
1416   options.statistics = CreateDBStatistics();
1417   bbto.block_cache.reset();
1418   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
1419 
1420   ReopenWithColumnFamilies({"default", "mypikachu"}, options);
1421 
1422   value = Get(1, Key(0));
1423   ASSERT_EQ(0, TestGetTickerCount(options, BLOCK_CACHE_FILTER_MISS));
1424   ASSERT_EQ(0, TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT));
1425   ASSERT_EQ(2 /* index and data block */,
1426             TestGetTickerCount(options, BLOCK_CACHE_ADD));
1427 
1428   // Check filter block ignored for files preloaded during DB::Open()
1429   options.max_open_files = -1;
1430   options.statistics = CreateDBStatistics();
1431   bbto.block_cache.reset();
1432   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
1433 
1434   ReopenWithColumnFamilies({"default", "mypikachu"}, options);
1435 
1436   uint64_t prev_cache_filter_misses =
1437       TestGetTickerCount(options, BLOCK_CACHE_FILTER_MISS);
1438   prev_cache_filter_hits = TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT);
1439   Get(1, Key(0));
1440   ASSERT_EQ(prev_cache_filter_misses,
1441             TestGetTickerCount(options, BLOCK_CACHE_FILTER_MISS));
1442   ASSERT_EQ(prev_cache_filter_hits,
1443             TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT));
1444 
1445   // Check filter block ignored for file trivially-moved to bottom level
1446   bbto.block_cache.reset();
1447   options.max_open_files = 100;  // setting > -1 makes it not preload all files
1448   options.statistics = CreateDBStatistics();
1449   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
1450 
1451   ReopenWithColumnFamilies({"default", "mypikachu"}, options);
1452 
1453   ASSERT_OK(Put(1, Key(numkeys + 1), "val"));
1454   ASSERT_OK(Flush(1));
1455 
1456   int32_t trivial_move = 0;
1457   int32_t non_trivial_move = 0;
1458   ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
1459       "DBImpl::BackgroundCompaction:TrivialMove",
1460       [&](void* /*arg*/) { trivial_move++; });
1461   ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
1462       "DBImpl::BackgroundCompaction:NonTrivial",
1463       [&](void* /*arg*/) { non_trivial_move++; });
1464   ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
1465 
1466   CompactRangeOptions compact_options;
1467   compact_options.bottommost_level_compaction =
1468       BottommostLevelCompaction::kSkip;
1469   compact_options.change_level = true;
1470   compact_options.target_level = 7;
1471   db_->CompactRange(compact_options, handles_[1], nullptr, nullptr);
1472 
1473   ASSERT_EQ(trivial_move, 1);
1474   ASSERT_EQ(non_trivial_move, 0);
1475 
1476   prev_cache_filter_hits = TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT);
1477   prev_cache_filter_misses =
1478       TestGetTickerCount(options, BLOCK_CACHE_FILTER_MISS);
1479   value = Get(1, Key(numkeys + 1));
1480   ASSERT_EQ(prev_cache_filter_hits,
1481             TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT));
1482   ASSERT_EQ(prev_cache_filter_misses,
1483             TestGetTickerCount(options, BLOCK_CACHE_FILTER_MISS));
1484 
1485   // Check filter block not cached for iterator
1486   bbto.block_cache.reset();
1487   options.statistics = CreateDBStatistics();
1488   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
1489 
1490   ReopenWithColumnFamilies({"default", "mypikachu"}, options);
1491 
1492   std::unique_ptr<Iterator> iter(db_->NewIterator(ReadOptions(), handles_[1]));
1493   iter->SeekToFirst();
1494   ASSERT_EQ(0, TestGetTickerCount(options, BLOCK_CACHE_FILTER_MISS));
1495   ASSERT_EQ(0, TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT));
1496   ASSERT_EQ(2 /* index and data block */,
1497             TestGetTickerCount(options, BLOCK_CACHE_ADD));
1498   get_perf_context()->Reset();
1499 }
1500 
CountIter(std::unique_ptr<Iterator> & iter,const Slice & key)1501 int CountIter(std::unique_ptr<Iterator>& iter, const Slice& key) {
1502   int count = 0;
1503   for (iter->Seek(key); iter->Valid() && iter->status() == Status::OK();
1504        iter->Next()) {
1505     count++;
1506   }
1507   return count;
1508 }
1509 
1510 // use iterate_upper_bound to hint compatiability of existing bloom filters.
1511 // The BF is considered compatible if 1) upper bound and seek key transform
1512 // into the same string, or 2) the transformed seek key is of the same length
1513 // as the upper bound and two keys are adjacent according to the comparator.
TEST_F(DBBloomFilterTest,DynamicBloomFilterUpperBound)1514 TEST_F(DBBloomFilterTest, DynamicBloomFilterUpperBound) {
1515   for (auto bfp_impl : BFP::kAllFixedImpls) {
1516     int using_full_builder = bfp_impl != BFP::kDeprecatedBlock;
1517     Options options;
1518     options.create_if_missing = true;
1519     options.prefix_extractor.reset(NewCappedPrefixTransform(4));
1520     options.disable_auto_compactions = true;
1521     options.statistics = CreateDBStatistics();
1522     // Enable prefix bloom for SST files
1523     BlockBasedTableOptions table_options;
1524     table_options.cache_index_and_filter_blocks = true;
1525     table_options.filter_policy.reset(new BFP(10, bfp_impl));
1526     table_options.index_shortening = BlockBasedTableOptions::
1527         IndexShorteningMode::kShortenSeparatorsAndSuccessor;
1528     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1529     DestroyAndReopen(options);
1530 
1531     ASSERT_OK(Put("abcdxxx0", "val1"));
1532     ASSERT_OK(Put("abcdxxx1", "val2"));
1533     ASSERT_OK(Put("abcdxxx2", "val3"));
1534     ASSERT_OK(Put("abcdxxx3", "val4"));
1535     dbfull()->Flush(FlushOptions());
1536     {
1537       // prefix_extractor has not changed, BF will always be read
1538       Slice upper_bound("abce");
1539       ReadOptions read_options;
1540       read_options.prefix_same_as_start = true;
1541       read_options.iterate_upper_bound = &upper_bound;
1542       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1543       ASSERT_EQ(CountIter(iter, "abcd0000"), 4);
1544     }
1545     {
1546       Slice upper_bound("abcdzzzz");
1547       ReadOptions read_options;
1548       read_options.prefix_same_as_start = true;
1549       read_options.iterate_upper_bound = &upper_bound;
1550       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1551       ASSERT_EQ(CountIter(iter, "abcd0000"), 4);
1552       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 2);
1553       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1554     }
1555     ASSERT_OK(dbfull()->SetOptions({{"prefix_extractor", "fixed:5"}}));
1556     ASSERT_EQ(0, strcmp(dbfull()->GetOptions().prefix_extractor->Name(),
1557                         "rocksdb.FixedPrefix.5"));
1558     {
1559       // BF changed, [abcdxx00, abce) is a valid bound, will trigger BF read
1560       Slice upper_bound("abce");
1561       ReadOptions read_options;
1562       read_options.prefix_same_as_start = true;
1563       read_options.iterate_upper_bound = &upper_bound;
1564       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1565       ASSERT_EQ(CountIter(iter, "abcdxx00"), 4);
1566       // should check bloom filter since upper bound meets requirement
1567       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1568                 2 + using_full_builder);
1569       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1570     }
1571     {
1572       // [abcdxx01, abcey) is not valid bound since upper bound is too long for
1573       // the BF in SST (capped:4)
1574       Slice upper_bound("abcey");
1575       ReadOptions read_options;
1576       read_options.prefix_same_as_start = true;
1577       read_options.iterate_upper_bound = &upper_bound;
1578       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1579       ASSERT_EQ(CountIter(iter, "abcdxx01"), 4);
1580       // should skip bloom filter since upper bound is too long
1581       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1582                 2 + using_full_builder);
1583       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1584     }
1585     {
1586       // [abcdxx02, abcdy) is a valid bound since the prefix is the same
1587       Slice upper_bound("abcdy");
1588       ReadOptions read_options;
1589       read_options.prefix_same_as_start = true;
1590       read_options.iterate_upper_bound = &upper_bound;
1591       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1592       ASSERT_EQ(CountIter(iter, "abcdxx02"), 4);
1593       // should check bloom filter since upper bound matches transformed seek
1594       // key
1595       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1596                 2 + using_full_builder * 2);
1597       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1598     }
1599     {
1600       // [aaaaaaaa, abce) is not a valid bound since 1) they don't share the
1601       // same prefix, 2) the prefixes are not consecutive
1602       Slice upper_bound("abce");
1603       ReadOptions read_options;
1604       read_options.prefix_same_as_start = true;
1605       read_options.iterate_upper_bound = &upper_bound;
1606       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1607       ASSERT_EQ(CountIter(iter, "aaaaaaaa"), 0);
1608       // should skip bloom filter since mismatch is found
1609       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1610                 2 + using_full_builder * 2);
1611       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1612     }
1613     ASSERT_OK(dbfull()->SetOptions({{"prefix_extractor", "fixed:3"}}));
1614     {
1615       // [abc, abd) is not a valid bound since the upper bound is too short
1616       // for BF (capped:4)
1617       Slice upper_bound("abd");
1618       ReadOptions read_options;
1619       read_options.prefix_same_as_start = true;
1620       read_options.iterate_upper_bound = &upper_bound;
1621       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1622       ASSERT_EQ(CountIter(iter, "abc"), 4);
1623       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1624                 2 + using_full_builder * 2);
1625       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1626     }
1627     ASSERT_OK(dbfull()->SetOptions({{"prefix_extractor", "capped:4"}}));
1628     {
1629       // set back to capped:4 and verify BF is always read
1630       Slice upper_bound("abd");
1631       ReadOptions read_options;
1632       read_options.prefix_same_as_start = true;
1633       read_options.iterate_upper_bound = &upper_bound;
1634       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1635       ASSERT_EQ(CountIter(iter, "abc"), 0);
1636       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1637                 3 + using_full_builder * 2);
1638       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 1);
1639     }
1640   }
1641 }
1642 
1643 // Create multiple SST files each with a different prefix_extractor config,
1644 // verify iterators can read all SST files using the latest config.
TEST_F(DBBloomFilterTest,DynamicBloomFilterMultipleSST)1645 TEST_F(DBBloomFilterTest, DynamicBloomFilterMultipleSST) {
1646   for (auto bfp_impl : BFP::kAllFixedImpls) {
1647     int using_full_builder = bfp_impl != BFP::kDeprecatedBlock;
1648     Options options;
1649     options.create_if_missing = true;
1650     options.prefix_extractor.reset(NewFixedPrefixTransform(1));
1651     options.disable_auto_compactions = true;
1652     options.statistics = CreateDBStatistics();
1653     // Enable prefix bloom for SST files
1654     BlockBasedTableOptions table_options;
1655     table_options.filter_policy.reset(new BFP(10, bfp_impl));
1656     table_options.cache_index_and_filter_blocks = true;
1657     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1658     DestroyAndReopen(options);
1659 
1660     Slice upper_bound("foz90000");
1661     ReadOptions read_options;
1662     read_options.prefix_same_as_start = true;
1663 
1664     // first SST with fixed:1 BF
1665     ASSERT_OK(Put("foo2", "bar2"));
1666     ASSERT_OK(Put("foo", "bar"));
1667     ASSERT_OK(Put("foq1", "bar1"));
1668     ASSERT_OK(Put("fpa", "0"));
1669     dbfull()->Flush(FlushOptions());
1670     std::unique_ptr<Iterator> iter_old(db_->NewIterator(read_options));
1671     ASSERT_EQ(CountIter(iter_old, "foo"), 4);
1672     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 1);
1673 
1674     ASSERT_OK(dbfull()->SetOptions({{"prefix_extractor", "capped:3"}}));
1675     ASSERT_EQ(0, strcmp(dbfull()->GetOptions().prefix_extractor->Name(),
1676                         "rocksdb.CappedPrefix.3"));
1677     read_options.iterate_upper_bound = &upper_bound;
1678     std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1679     ASSERT_EQ(CountIter(iter, "foo"), 2);
1680     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1681               1 + using_full_builder);
1682     ASSERT_EQ(CountIter(iter, "gpk"), 0);
1683     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1684               1 + using_full_builder);
1685     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1686 
1687     // second SST with capped:3 BF
1688     ASSERT_OK(Put("foo3", "bar3"));
1689     ASSERT_OK(Put("foo4", "bar4"));
1690     ASSERT_OK(Put("foq5", "bar5"));
1691     ASSERT_OK(Put("fpb", "1"));
1692     dbfull()->Flush(FlushOptions());
1693     {
1694       // BF is cappped:3 now
1695       std::unique_ptr<Iterator> iter_tmp(db_->NewIterator(read_options));
1696       ASSERT_EQ(CountIter(iter_tmp, "foo"), 4);
1697       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1698                 2 + using_full_builder * 2);
1699       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1700       ASSERT_EQ(CountIter(iter_tmp, "gpk"), 0);
1701       // both counters are incremented because BF is "not changed" for 1 of the
1702       // 2 SST files, so filter is checked once and found no match.
1703       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1704                 3 + using_full_builder * 2);
1705       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 1);
1706     }
1707 
1708     ASSERT_OK(dbfull()->SetOptions({{"prefix_extractor", "fixed:2"}}));
1709     ASSERT_EQ(0, strcmp(dbfull()->GetOptions().prefix_extractor->Name(),
1710                         "rocksdb.FixedPrefix.2"));
1711     // third SST with fixed:2 BF
1712     ASSERT_OK(Put("foo6", "bar6"));
1713     ASSERT_OK(Put("foo7", "bar7"));
1714     ASSERT_OK(Put("foq8", "bar8"));
1715     ASSERT_OK(Put("fpc", "2"));
1716     dbfull()->Flush(FlushOptions());
1717     {
1718       // BF is fixed:2 now
1719       std::unique_ptr<Iterator> iter_tmp(db_->NewIterator(read_options));
1720       ASSERT_EQ(CountIter(iter_tmp, "foo"), 9);
1721       // the first and last BF are checked
1722       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1723                 4 + using_full_builder * 3);
1724       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 1);
1725       ASSERT_EQ(CountIter(iter_tmp, "gpk"), 0);
1726       // only last BF is checked and not found
1727       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1728                 5 + using_full_builder * 3);
1729       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 2);
1730     }
1731 
1732     // iter_old can only see the first SST, so checked plus 1
1733     ASSERT_EQ(CountIter(iter_old, "foo"), 4);
1734     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1735               6 + using_full_builder * 3);
1736     // iter was created after the first setoptions call so only full filter
1737     // will check the filter
1738     ASSERT_EQ(CountIter(iter, "foo"), 2);
1739     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1740               6 + using_full_builder * 4);
1741 
1742     {
1743       // keys in all three SSTs are visible to iterator
1744       // The range of [foo, foz90000] is compatible with (fixed:1) and (fixed:2)
1745       // so +2 for checked counter
1746       std::unique_ptr<Iterator> iter_all(db_->NewIterator(read_options));
1747       ASSERT_EQ(CountIter(iter_all, "foo"), 9);
1748       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1749                 7 + using_full_builder * 5);
1750       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 2);
1751       ASSERT_EQ(CountIter(iter_all, "gpk"), 0);
1752       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1753                 8 + using_full_builder * 5);
1754       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 3);
1755     }
1756     ASSERT_OK(dbfull()->SetOptions({{"prefix_extractor", "capped:3"}}));
1757     ASSERT_EQ(0, strcmp(dbfull()->GetOptions().prefix_extractor->Name(),
1758                         "rocksdb.CappedPrefix.3"));
1759     {
1760       std::unique_ptr<Iterator> iter_all(db_->NewIterator(read_options));
1761       ASSERT_EQ(CountIter(iter_all, "foo"), 6);
1762       // all three SST are checked because the current options has the same as
1763       // the remaining SST (capped:3)
1764       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1765                 9 + using_full_builder * 7);
1766       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 3);
1767       ASSERT_EQ(CountIter(iter_all, "gpk"), 0);
1768       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED),
1769                 10 + using_full_builder * 7);
1770       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 4);
1771     }
1772     // TODO(Zhongyi): Maybe also need to add Get calls to test point look up?
1773   }
1774 }
1775 
1776 // Create a new column family in a running DB, change prefix_extractor
1777 // dynamically, verify the iterator created on the new column family behaves
1778 // as expected
TEST_F(DBBloomFilterTest,DynamicBloomFilterNewColumnFamily)1779 TEST_F(DBBloomFilterTest, DynamicBloomFilterNewColumnFamily) {
1780   int iteration = 0;
1781   for (auto bfp_impl : BFP::kAllFixedImpls) {
1782     Options options = CurrentOptions();
1783     options.create_if_missing = true;
1784     options.prefix_extractor.reset(NewFixedPrefixTransform(1));
1785     options.disable_auto_compactions = true;
1786     options.statistics = CreateDBStatistics();
1787     // Enable prefix bloom for SST files
1788     BlockBasedTableOptions table_options;
1789     table_options.cache_index_and_filter_blocks = true;
1790     table_options.filter_policy.reset(new BFP(10, bfp_impl));
1791     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1792     CreateAndReopenWithCF({"pikachu" + std::to_string(iteration)}, options);
1793     ReadOptions read_options;
1794     read_options.prefix_same_as_start = true;
1795     // create a new CF and set prefix_extractor dynamically
1796     options.prefix_extractor.reset(NewCappedPrefixTransform(3));
1797     CreateColumnFamilies({"ramen_dojo_" + std::to_string(iteration)}, options);
1798     ASSERT_EQ(0,
1799               strcmp(dbfull()->GetOptions(handles_[2]).prefix_extractor->Name(),
1800                      "rocksdb.CappedPrefix.3"));
1801     ASSERT_OK(Put(2, "foo3", "bar3"));
1802     ASSERT_OK(Put(2, "foo4", "bar4"));
1803     ASSERT_OK(Put(2, "foo5", "bar5"));
1804     ASSERT_OK(Put(2, "foq6", "bar6"));
1805     ASSERT_OK(Put(2, "fpq7", "bar7"));
1806     dbfull()->Flush(FlushOptions());
1807     {
1808       std::unique_ptr<Iterator> iter(
1809           db_->NewIterator(read_options, handles_[2]));
1810       ASSERT_EQ(CountIter(iter, "foo"), 3);
1811       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 0);
1812       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1813     }
1814     ASSERT_OK(
1815         dbfull()->SetOptions(handles_[2], {{"prefix_extractor", "fixed:2"}}));
1816     ASSERT_EQ(0,
1817               strcmp(dbfull()->GetOptions(handles_[2]).prefix_extractor->Name(),
1818                      "rocksdb.FixedPrefix.2"));
1819     {
1820       std::unique_ptr<Iterator> iter(
1821           db_->NewIterator(read_options, handles_[2]));
1822       ASSERT_EQ(CountIter(iter, "foo"), 4);
1823       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 0);
1824       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1825     }
1826     ASSERT_OK(dbfull()->DropColumnFamily(handles_[2]));
1827     dbfull()->DestroyColumnFamilyHandle(handles_[2]);
1828     handles_[2] = nullptr;
1829     ASSERT_OK(dbfull()->DropColumnFamily(handles_[1]));
1830     dbfull()->DestroyColumnFamilyHandle(handles_[1]);
1831     handles_[1] = nullptr;
1832     iteration++;
1833   }
1834 }
1835 
1836 // Verify it's possible to change prefix_extractor at runtime and iterators
1837 // behaves as expected
TEST_F(DBBloomFilterTest,DynamicBloomFilterOptions)1838 TEST_F(DBBloomFilterTest, DynamicBloomFilterOptions) {
1839   for (auto bfp_impl : BFP::kAllFixedImpls) {
1840     Options options;
1841     options.create_if_missing = true;
1842     options.prefix_extractor.reset(NewFixedPrefixTransform(1));
1843     options.disable_auto_compactions = true;
1844     options.statistics = CreateDBStatistics();
1845     // Enable prefix bloom for SST files
1846     BlockBasedTableOptions table_options;
1847     table_options.cache_index_and_filter_blocks = true;
1848     table_options.filter_policy.reset(new BFP(10, bfp_impl));
1849     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1850     DestroyAndReopen(options);
1851 
1852     ASSERT_OK(Put("foo2", "bar2"));
1853     ASSERT_OK(Put("foo", "bar"));
1854     ASSERT_OK(Put("foo1", "bar1"));
1855     ASSERT_OK(Put("fpa", "0"));
1856     dbfull()->Flush(FlushOptions());
1857     ASSERT_OK(Put("foo3", "bar3"));
1858     ASSERT_OK(Put("foo4", "bar4"));
1859     ASSERT_OK(Put("foo5", "bar5"));
1860     ASSERT_OK(Put("fpb", "1"));
1861     dbfull()->Flush(FlushOptions());
1862     ASSERT_OK(Put("foo6", "bar6"));
1863     ASSERT_OK(Put("foo7", "bar7"));
1864     ASSERT_OK(Put("foo8", "bar8"));
1865     ASSERT_OK(Put("fpc", "2"));
1866     dbfull()->Flush(FlushOptions());
1867 
1868     ReadOptions read_options;
1869     read_options.prefix_same_as_start = true;
1870     {
1871       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1872       ASSERT_EQ(CountIter(iter, "foo"), 12);
1873       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 3);
1874       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1875     }
1876     std::unique_ptr<Iterator> iter_old(db_->NewIterator(read_options));
1877     ASSERT_EQ(CountIter(iter_old, "foo"), 12);
1878     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 6);
1879     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1880 
1881     ASSERT_OK(dbfull()->SetOptions({{"prefix_extractor", "capped:3"}}));
1882     ASSERT_EQ(0, strcmp(dbfull()->GetOptions().prefix_extractor->Name(),
1883                         "rocksdb.CappedPrefix.3"));
1884     {
1885       std::unique_ptr<Iterator> iter(db_->NewIterator(read_options));
1886       // "fp*" should be skipped
1887       ASSERT_EQ(CountIter(iter, "foo"), 9);
1888       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 6);
1889       ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1890     }
1891 
1892     // iterator created before should not be affected and see all keys
1893     ASSERT_EQ(CountIter(iter_old, "foo"), 12);
1894     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 9);
1895     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 0);
1896     ASSERT_EQ(CountIter(iter_old, "abc"), 0);
1897     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_CHECKED), 12);
1898     ASSERT_EQ(TestGetTickerCount(options, BLOOM_FILTER_PREFIX_USEFUL), 3);
1899   }
1900 }
1901 
1902 #endif  // ROCKSDB_LITE
1903 
1904 }  // namespace ROCKSDB_NAMESPACE
1905 
main(int argc,char ** argv)1906 int main(int argc, char** argv) {
1907   ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
1908   ::testing::InitGoogleTest(&argc, argv);
1909   return RUN_ALL_TESTS();
1910 }
1911