ceph/src/rocksdb/table/filter_block.h

   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 // A filter block is stored near the end of a Table file.  It contains
  11 // filters (e.g., bloom filters) for all data blocks in the table combined
  12 // into a single filter block.
  13 //
  14 // It is a base class for BlockBasedFilter and FullFilter.
  15 // These two are both used in BlockBasedTable. The first one contain filter
  16 // For a part of keys in sst file, the second contain filter for all keys
  17 // in sst file.
  18
  19 #pragma once
  20
  21 #include <memory>
  22 #include <stddef.h>
  23 #include <stdint.h>
  24 #include <string>
  25 #include <vector>
  26 #include "rocksdb/options.h"
  27 #include "rocksdb/slice.h"
  28 #include "rocksdb/slice_transform.h"
  29 #include "rocksdb/table.h"
  30 #include "util/hash.h"
  31 #include "format.h"
  32
  33 namespace rocksdb {
  34
  35 const uint64_t kNotValid = ULLONG_MAX;
  36 class FilterPolicy;
  37
  38 // A FilterBlockBuilder is used to construct all of the filters for a
  39 // particular Table.  It generates a single string which is stored as
  40 // a special block in the Table.
  41 //
  42 // The sequence of calls to FilterBlockBuilder must match the regexp:
  43 //      (StartBlock Add*)* Finish
  44 //
  45 // BlockBased/Full FilterBlock would be called in the same way.
  46 class FilterBlockBuilder {
  47  public:
  48   explicit FilterBlockBuilder() {}
  49   virtual ~FilterBlockBuilder() {}
  50
  51   virtual bool IsBlockBased() = 0;                    // If is blockbased filter
  52   virtual void StartBlock(uint64_t block_offset) = 0;  // Start new block filter
  53   virtual void Add(const Slice& key) = 0;      // Add a key to current filter
  54   virtual size_t NumAdded() const = 0;         // Number of keys added
  55   Slice Finish() {                             // Generate Filter
  56     const BlockHandle empty_handle;
  57     Status dont_care_status;
  58     auto ret = Finish(empty_handle, &dont_care_status);
  59     assert(dont_care_status.ok());
  60     return ret;
  61   }
  62   virtual Slice Finish(const BlockHandle& tmp, Status* status) = 0;
  63
  64  private:
  65   // No copying allowed
  66   FilterBlockBuilder(const FilterBlockBuilder&);
  67   void operator=(const FilterBlockBuilder&);
  68 };
  69
  70 // A FilterBlockReader is used to parse filter from SST table.
  71 // KeyMayMatch and PrefixMayMatch would trigger filter checking
  72 //
  73 // BlockBased/Full FilterBlock would be called in the same way.
  74 class FilterBlockReader {
  75  public:
  76   explicit FilterBlockReader()
  77       : whole_key_filtering_(true), size_(0), statistics_(nullptr) {}
  78   explicit FilterBlockReader(size_t s, Statistics* stats,
  79                              bool _whole_key_filtering)
  80       : whole_key_filtering_(_whole_key_filtering),
  81         size_(s),
  82         statistics_(stats) {}
  83   virtual ~FilterBlockReader() {}
  84
  85   virtual bool IsBlockBased() = 0;  // If is blockbased filter
  86   /**
  87    * If no_io is set, then it returns true if it cannot answer the query without
  88    * reading data from disk. This is used in PartitionedFilterBlockReader to
  89    * avoid reading partitions that are not in block cache already
  90    *
  91    * Normally filters are built on only the user keys and the InternalKey is not
  92    * needed for a query. The index in PartitionedFilterBlockReader however is
  93    * built upon InternalKey and must be provided via const_ikey_ptr when running
  94    * queries.
  95    */
  96   virtual bool KeyMayMatch(const Slice& key,
  97                            const SliceTransform* prefix_extractor,
  98                            uint64_t block_offset = kNotValid,
  99                            const bool no_io = false,
 100                            const Slice* const const_ikey_ptr = nullptr) = 0;
 101
 102   /**
 103    * no_io and const_ikey_ptr here means the same as in KeyMayMatch
 104    */
 105   virtual bool PrefixMayMatch(const Slice& prefix,
 106                               const SliceTransform* prefix_extractor,
 107                               uint64_t block_offset = kNotValid,
 108                               const bool no_io = false,
 109                               const Slice* const const_ikey_ptr = nullptr) = 0;
 110
 111   virtual size_t ApproximateMemoryUsage() const = 0;
 112   virtual size_t size() const { return size_; }
 113   virtual Statistics* statistics() const { return statistics_; }
 114
 115   bool whole_key_filtering() const { return whole_key_filtering_; }
 116
 117   // convert this object to a human readable form
 118   virtual std::string ToString() const {
 119     std::string error_msg("Unsupported filter \n");
 120     return error_msg;
 121   }
 122
 123   virtual void CacheDependencies(bool /*pin*/,
 124                                  const SliceTransform* /*prefix_extractor*/) {}
 125
 126   virtual bool RangeMayExist(
 127       const Slice* /*iterate_upper_bound*/, const Slice& user_key,
 128       const SliceTransform* prefix_extractor,
 129       const Comparator* /*comparator*/, const Slice* const const_ikey_ptr,
 130       bool* filter_checked, bool /*need_upper_bound_check*/) {
 131     *filter_checked = true;
 132     Slice prefix = prefix_extractor->Transform(user_key);
 133     return PrefixMayMatch(prefix, prefix_extractor, kNotValid, false,
 134                           const_ikey_ptr);
 135   }
 136
 137  protected:
 138   bool whole_key_filtering_;
 139
 140  private:
 141   // No copying allowed
 142   FilterBlockReader(const FilterBlockReader&);
 143   void operator=(const FilterBlockReader&);
 144   size_t size_;
 145   Statistics* statistics_;
 146   int level_ = -1;
 147 };
 148
 149 }  // namespace rocksdb