ceph/src/rocksdb/table/block_based_filter_block_test.cc

   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) 2012 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 "table/block_based_filter_block.h"
  11
  12 #include "rocksdb/filter_policy.h"
  13 #include "util/coding.h"
  14 #include "util/hash.h"
  15 #include "util/string_util.h"
  16 #include "util/testharness.h"
  17 #include "util/testutil.h"
  18
  19 namespace rocksdb {
  20
  21 // For testing: emit an array with one hash value per key
  22 class TestHashFilter : public FilterPolicy {
  23  public:
  24   virtual const char* Name() const override { return "TestHashFilter"; }
  25
  26   virtual void CreateFilter(const Slice* keys, int n,
  27                             std::string* dst) const override {
  28     for (int i = 0; i < n; i++) {
  29       uint32_t h = Hash(keys[i].data(), keys[i].size(), 1);
  30       PutFixed32(dst, h);
  31     }
  32   }
  33
  34   virtual bool KeyMayMatch(const Slice& key,
  35                            const Slice& filter) const override {
  36     uint32_t h = Hash(key.data(), key.size(), 1);
  37     for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) {
  38       if (h == DecodeFixed32(filter.data() + i)) {
  39         return true;
  40       }
  41     }
  42     return false;
  43   }
  44 };
  45
  46 class FilterBlockTest : public testing::Test {
  47  public:
  48   TestHashFilter policy_;
  49   BlockBasedTableOptions table_options_;
  50
  51   FilterBlockTest() {
  52     table_options_.filter_policy.reset(new TestHashFilter());
  53   }
  54 };
  55
  56 TEST_F(FilterBlockTest, EmptyBuilder) {
  57   BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
  58   BlockContents block(builder.Finish(), false, kNoCompression);
  59   ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block.data));
  60   BlockBasedFilterBlockReader reader(nullptr, table_options_, true,
  61                                      std::move(block), nullptr);
  62   ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, uint64_t{0}));
  63   ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, 100000));
  64 }
  65
  66 TEST_F(FilterBlockTest, SingleChunk) {
  67   BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
  68   ASSERT_EQ(0, builder.NumAdded());
  69   builder.StartBlock(100);
  70   builder.Add("foo");
  71   builder.Add("bar");
  72   builder.Add("box");
  73   builder.StartBlock(200);
  74   builder.Add("box");
  75   builder.StartBlock(300);
  76   builder.Add("hello");
  77   ASSERT_EQ(5, builder.NumAdded());
  78   BlockContents block(builder.Finish(), false, kNoCompression);
  79   BlockBasedFilterBlockReader reader(nullptr, table_options_, true,
  80                                      std::move(block), nullptr);
  81   ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, 100));
  82   ASSERT_TRUE(reader.KeyMayMatch("bar", nullptr, 100));
  83   ASSERT_TRUE(reader.KeyMayMatch("box", nullptr, 100));
  84   ASSERT_TRUE(reader.KeyMayMatch("hello", nullptr, 100));
  85   ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, 100));
  86   ASSERT_TRUE(!reader.KeyMayMatch("missing", nullptr, 100));
  87   ASSERT_TRUE(!reader.KeyMayMatch("other", nullptr, 100));
  88 }
  89
  90 TEST_F(FilterBlockTest, MultiChunk) {
  91   BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
  92
  93   // First filter
  94   builder.StartBlock(0);
  95   builder.Add("foo");
  96   builder.StartBlock(2000);
  97   builder.Add("bar");
  98
  99   // Second filter
 100   builder.StartBlock(3100);
 101   builder.Add("box");
 102
 103   // Third filter is empty
 104
 105   // Last filter
 106   builder.StartBlock(9000);
 107   builder.Add("box");
 108   builder.Add("hello");
 109
 110   BlockContents block(builder.Finish(), false, kNoCompression);
 111   BlockBasedFilterBlockReader reader(nullptr, table_options_, true,
 112                                      std::move(block), nullptr);
 113
 114   // Check first filter
 115   ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, uint64_t{0}));
 116   ASSERT_TRUE(reader.KeyMayMatch("bar", nullptr, 2000));
 117   ASSERT_TRUE(!reader.KeyMayMatch("box", nullptr, uint64_t{0}));
 118   ASSERT_TRUE(!reader.KeyMayMatch("hello", nullptr, uint64_t{0}));
 119
 120   // Check second filter
 121   ASSERT_TRUE(reader.KeyMayMatch("box", nullptr, 3100));
 122   ASSERT_TRUE(!reader.KeyMayMatch("foo", nullptr, 3100));
 123   ASSERT_TRUE(!reader.KeyMayMatch("bar", nullptr, 3100));
 124   ASSERT_TRUE(!reader.KeyMayMatch("hello", nullptr, 3100));
 125
 126   // Check third filter (empty)
 127   ASSERT_TRUE(!reader.KeyMayMatch("foo", nullptr, 4100));
 128   ASSERT_TRUE(!reader.KeyMayMatch("bar", nullptr, 4100));
 129   ASSERT_TRUE(!reader.KeyMayMatch("box", nullptr, 4100));
 130   ASSERT_TRUE(!reader.KeyMayMatch("hello", nullptr, 4100));
 131
 132   // Check last filter
 133   ASSERT_TRUE(reader.KeyMayMatch("box", nullptr, 9000));
 134   ASSERT_TRUE(reader.KeyMayMatch("hello", nullptr, 9000));
 135   ASSERT_TRUE(!reader.KeyMayMatch("foo", nullptr, 9000));
 136   ASSERT_TRUE(!reader.KeyMayMatch("bar", nullptr, 9000));
 137 }
 138
 139 // Test for block based filter block
 140 // use new interface in FilterPolicy to create filter builder/reader
 141 class BlockBasedFilterBlockTest : public testing::Test {
 142  public:
 143   BlockBasedTableOptions table_options_;
 144
 145   BlockBasedFilterBlockTest() {
 146     table_options_.filter_policy.reset(NewBloomFilterPolicy(10));
 147   }
 148
 149   ~BlockBasedFilterBlockTest() {}
 150 };
 151
 152 TEST_F(BlockBasedFilterBlockTest, BlockBasedEmptyBuilder) {
 153   FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder(
 154       nullptr, table_options_);
 155   BlockContents block(builder->Finish(), false, kNoCompression);
 156   ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block.data));
 157   FilterBlockReader* reader = new BlockBasedFilterBlockReader(
 158       nullptr, table_options_, true, std::move(block), nullptr);
 159   ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, uint64_t{0}));
 160   ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, 100000));
 161
 162   delete builder;
 163   delete reader;
 164 }
 165
 166 TEST_F(BlockBasedFilterBlockTest, BlockBasedSingleChunk) {
 167   FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder(
 168       nullptr, table_options_);
 169   builder->StartBlock(100);
 170   builder->Add("foo");
 171   builder->Add("bar");
 172   builder->Add("box");
 173   builder->StartBlock(200);
 174   builder->Add("box");
 175   builder->StartBlock(300);
 176   builder->Add("hello");
 177   BlockContents block(builder->Finish(), false, kNoCompression);
 178   FilterBlockReader* reader = new BlockBasedFilterBlockReader(
 179       nullptr, table_options_, true, std::move(block), nullptr);
 180   ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, 100));
 181   ASSERT_TRUE(reader->KeyMayMatch("bar", nullptr, 100));
 182   ASSERT_TRUE(reader->KeyMayMatch("box", nullptr, 100));
 183   ASSERT_TRUE(reader->KeyMayMatch("hello", nullptr, 100));
 184   ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, 100));
 185   ASSERT_TRUE(!reader->KeyMayMatch("missing", nullptr, 100));
 186   ASSERT_TRUE(!reader->KeyMayMatch("other", nullptr, 100));
 187
 188   delete builder;
 189   delete reader;
 190 }
 191
 192 TEST_F(BlockBasedFilterBlockTest, BlockBasedMultiChunk) {
 193   FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder(
 194       nullptr, table_options_);
 195
 196   // First filter
 197   builder->StartBlock(0);
 198   builder->Add("foo");
 199   builder->StartBlock(2000);
 200   builder->Add("bar");
 201
 202   // Second filter
 203   builder->StartBlock(3100);
 204   builder->Add("box");
 205
 206   // Third filter is empty
 207
 208   // Last filter
 209   builder->StartBlock(9000);
 210   builder->Add("box");
 211   builder->Add("hello");
 212
 213   BlockContents block(builder->Finish(), false, kNoCompression);
 214   FilterBlockReader* reader = new BlockBasedFilterBlockReader(
 215       nullptr, table_options_, true, std::move(block), nullptr);
 216
 217   // Check first filter
 218   ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, uint64_t{0}));
 219   ASSERT_TRUE(reader->KeyMayMatch("bar", nullptr, 2000));
 220   ASSERT_TRUE(!reader->KeyMayMatch("box", nullptr, uint64_t{0}));
 221   ASSERT_TRUE(!reader->KeyMayMatch("hello", nullptr, uint64_t{0}));
 222
 223   // Check second filter
 224   ASSERT_TRUE(reader->KeyMayMatch("box", nullptr, 3100));
 225   ASSERT_TRUE(!reader->KeyMayMatch("foo", nullptr, 3100));
 226   ASSERT_TRUE(!reader->KeyMayMatch("bar", nullptr, 3100));
 227   ASSERT_TRUE(!reader->KeyMayMatch("hello", nullptr, 3100));
 228
 229   // Check third filter (empty)
 230   ASSERT_TRUE(!reader->KeyMayMatch("foo", nullptr, 4100));
 231   ASSERT_TRUE(!reader->KeyMayMatch("bar", nullptr, 4100));
 232   ASSERT_TRUE(!reader->KeyMayMatch("box", nullptr, 4100));
 233   ASSERT_TRUE(!reader->KeyMayMatch("hello", nullptr, 4100));
 234
 235   // Check last filter
 236   ASSERT_TRUE(reader->KeyMayMatch("box", nullptr, 9000));
 237   ASSERT_TRUE(reader->KeyMayMatch("hello", nullptr, 9000));
 238   ASSERT_TRUE(!reader->KeyMayMatch("foo", nullptr, 9000));
 239   ASSERT_TRUE(!reader->KeyMayMatch("bar", nullptr, 9000));
 240
 241   delete builder;
 242   delete reader;
 243 }
 244
 245 }  // namespace rocksdb
 246
 247 int main(int argc, char** argv) {
 248   ::testing::InitGoogleTest(&argc, argv);
 249   return RUN_ALL_TESTS();
 250 }