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 #pragma once 7 8 #include <stddef.h> 9 #include <stdint.h> 10 #include <memory> 11 #include <string> 12 #include <vector> 13 14 #include "db/dbformat.h" 15 #include "rocksdb/options.h" 16 #include "rocksdb/slice.h" 17 #include "rocksdb/slice_transform.h" 18 #include "table/block_based/filter_block_reader_common.h" 19 #include "table/block_based/parsed_full_filter_block.h" 20 #include "util/hash.h" 21 22 namespace ROCKSDB_NAMESPACE { 23 24 class FilterPolicy; 25 class FilterBitsBuilder; 26 class FilterBitsReader; 27 28 // A FullFilterBlockBuilder is used to construct a full filter for a 29 // particular Table. It generates a single string which is stored as 30 // a special block in the Table. 31 // The format of full filter block is: 32 // +----------------------------------------------------------------+ 33 // | full filter for all keys in sst file | 34 // +----------------------------------------------------------------+ 35 // The full filter can be very large. At the end of it, we put 36 // num_probes: how many hash functions are used in bloom filter 37 // 38 class FullFilterBlockBuilder : public FilterBlockBuilder { 39 public: 40 explicit FullFilterBlockBuilder(const SliceTransform* prefix_extractor, 41 bool whole_key_filtering, 42 FilterBitsBuilder* filter_bits_builder); 43 // No copying allowed 44 FullFilterBlockBuilder(const FullFilterBlockBuilder&) = delete; 45 void operator=(const FullFilterBlockBuilder&) = delete; 46 47 // bits_builder is created in filter_policy, it should be passed in here 48 // directly. and be deleted here ~FullFilterBlockBuilder()49 ~FullFilterBlockBuilder() {} 50 IsBlockBased()51 virtual bool IsBlockBased() override { return false; } StartBlock(uint64_t)52 virtual void StartBlock(uint64_t /*block_offset*/) override {} 53 virtual void Add(const Slice& key) override; NumAdded()54 virtual size_t NumAdded() const override { return num_added_; } 55 virtual Slice Finish(const BlockHandle& tmp, Status* status) override; 56 using FilterBlockBuilder::Finish; 57 58 protected: 59 virtual void AddKey(const Slice& key); 60 std::unique_ptr<FilterBitsBuilder> filter_bits_builder_; 61 virtual void Reset(); 62 void AddPrefix(const Slice& key); prefix_extractor()63 const SliceTransform* prefix_extractor() { return prefix_extractor_; } 64 65 private: 66 // important: all of these might point to invalid addresses 67 // at the time of destruction of this filter block. destructor 68 // should NOT dereference them. 69 const SliceTransform* prefix_extractor_; 70 bool whole_key_filtering_; 71 bool last_whole_key_recorded_; 72 std::string last_whole_key_str_; 73 bool last_prefix_recorded_; 74 std::string last_prefix_str_; 75 76 uint32_t num_added_; 77 std::unique_ptr<const char[]> filter_data_; 78 79 }; 80 81 // A FilterBlockReader is used to parse filter from SST table. 82 // KeyMayMatch and PrefixMayMatch would trigger filter checking 83 class FullFilterBlockReader 84 : public FilterBlockReaderCommon<ParsedFullFilterBlock> { 85 public: 86 FullFilterBlockReader(const BlockBasedTable* t, 87 CachableEntry<ParsedFullFilterBlock>&& filter_block); 88 89 static std::unique_ptr<FilterBlockReader> Create( 90 const BlockBasedTable* table, FilePrefetchBuffer* prefetch_buffer, 91 bool use_cache, bool prefetch, bool pin, 92 BlockCacheLookupContext* lookup_context); 93 IsBlockBased()94 bool IsBlockBased() override { return false; } 95 96 bool KeyMayMatch(const Slice& key, const SliceTransform* prefix_extractor, 97 uint64_t block_offset, const bool no_io, 98 const Slice* const const_ikey_ptr, GetContext* get_context, 99 BlockCacheLookupContext* lookup_context) override; 100 101 bool PrefixMayMatch(const Slice& prefix, 102 const SliceTransform* prefix_extractor, 103 uint64_t block_offset, const bool no_io, 104 const Slice* const const_ikey_ptr, 105 GetContext* get_context, 106 BlockCacheLookupContext* lookup_context) override; 107 108 void KeysMayMatch(MultiGetRange* range, 109 const SliceTransform* prefix_extractor, 110 uint64_t block_offset, const bool no_io, 111 BlockCacheLookupContext* lookup_context) override; 112 113 void PrefixesMayMatch(MultiGetRange* range, 114 const SliceTransform* prefix_extractor, 115 uint64_t block_offset, const bool no_io, 116 BlockCacheLookupContext* lookup_context) override; 117 size_t ApproximateMemoryUsage() const override; 118 bool RangeMayExist(const Slice* iterate_upper_bound, const Slice& user_key, 119 const SliceTransform* prefix_extractor, 120 const Comparator* comparator, 121 const Slice* const const_ikey_ptr, bool* filter_checked, 122 bool need_upper_bound_check, 123 BlockCacheLookupContext* lookup_context) override; 124 125 private: 126 bool MayMatch(const Slice& entry, bool no_io, GetContext* get_context, 127 BlockCacheLookupContext* lookup_context) const; 128 void MayMatch(MultiGetRange* range, bool no_io, 129 const SliceTransform* prefix_extractor, 130 BlockCacheLookupContext* lookup_context) const; 131 bool IsFilterCompatible(const Slice* iterate_upper_bound, const Slice& prefix, 132 const Comparator* comparator) const; 133 134 private: 135 bool full_length_enabled_; 136 size_t prefix_extractor_full_length_; 137 }; 138 139 } // namespace ROCKSDB_NAMESPACE 140