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).
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/filter_policy_internal.h"
20 #include "table/block_based/parsed_full_filter_block.h"
21 #include "util/hash.h"
23 namespace ROCKSDB_NAMESPACE
{
26 class FilterBitsBuilder
;
27 class FilterBitsReader
;
29 // A FullFilterBlockBuilder is used to construct a full filter for a
30 // particular Table. It generates a single string which is stored as
31 // a special block in the Table.
32 // The format of full filter block is:
33 // +----------------------------------------------------------------+
34 // | full filter for all keys in sst file |
35 // +----------------------------------------------------------------+
36 // The full filter can be very large. At the end of it, we put
37 // num_probes: how many hash functions are used in bloom filter
39 class FullFilterBlockBuilder
: public FilterBlockBuilder
{
41 explicit FullFilterBlockBuilder(const SliceTransform
* prefix_extractor
,
42 bool whole_key_filtering
,
43 FilterBitsBuilder
* filter_bits_builder
);
45 FullFilterBlockBuilder(const FullFilterBlockBuilder
&) = delete;
46 void operator=(const FullFilterBlockBuilder
&) = delete;
48 // bits_builder is created in filter_policy, it should be passed in here
49 // directly. and be deleted here
50 ~FullFilterBlockBuilder() {}
52 virtual void Add(const Slice
& key_without_ts
) override
;
53 virtual bool IsEmpty() const override
{ return !any_added_
; }
54 virtual size_t EstimateEntriesAdded() override
;
56 const BlockHandle
& tmp
, Status
* status
,
57 std::unique_ptr
<const char[]>* filter_data
= nullptr) override
;
58 using FilterBlockBuilder::Finish
;
60 virtual void ResetFilterBitsBuilder() override
{
61 filter_bits_builder_
.reset();
64 virtual Status
MaybePostVerifyFilter(const Slice
& filter_content
) override
{
65 return filter_bits_builder_
->MaybePostVerify(filter_content
);
69 virtual void AddKey(const Slice
& key
);
70 std::unique_ptr
<FilterBitsBuilder
> filter_bits_builder_
;
72 void AddPrefix(const Slice
& key
);
73 const SliceTransform
* prefix_extractor() { return prefix_extractor_
; }
74 const std::string
& last_prefix_str() const { return last_prefix_str_
; }
77 // important: all of these might point to invalid addresses
78 // at the time of destruction of this filter block. destructor
79 // should NOT dereference them.
80 const SliceTransform
* prefix_extractor_
;
81 bool whole_key_filtering_
;
82 bool last_whole_key_recorded_
;
83 std::string last_whole_key_str_
;
84 bool last_prefix_recorded_
;
85 std::string last_prefix_str_
;
86 // Whether prefix_extractor_->InDomain(last_whole_key_) is true.
87 // Used in partitioned filters so that the last prefix from the previous
88 // filter partition will be added to the current partition if
89 // last_key_in_domain_ is true, regardless of the current key.
90 bool last_key_in_domain_
;
92 std::unique_ptr
<const char[]> filter_data_
;
95 // A FilterBlockReader is used to parse filter from SST table.
96 // KeyMayMatch and PrefixMayMatch would trigger filter checking
97 class FullFilterBlockReader
98 : public FilterBlockReaderCommon
<ParsedFullFilterBlock
> {
100 FullFilterBlockReader(const BlockBasedTable
* t
,
101 CachableEntry
<ParsedFullFilterBlock
>&& filter_block
);
103 static std::unique_ptr
<FilterBlockReader
> Create(
104 const BlockBasedTable
* table
, const ReadOptions
& ro
,
105 FilePrefetchBuffer
* prefetch_buffer
, bool use_cache
, bool prefetch
,
106 bool pin
, BlockCacheLookupContext
* lookup_context
);
108 bool KeyMayMatch(const Slice
& key
, const bool no_io
,
109 const Slice
* const const_ikey_ptr
, GetContext
* get_context
,
110 BlockCacheLookupContext
* lookup_context
,
111 Env::IOPriority rate_limiter_priority
) override
;
113 bool PrefixMayMatch(const Slice
& prefix
, const bool no_io
,
114 const Slice
* const const_ikey_ptr
,
115 GetContext
* get_context
,
116 BlockCacheLookupContext
* lookup_context
,
117 Env::IOPriority rate_limiter_priority
) override
;
119 void KeysMayMatch(MultiGetRange
* range
, const bool no_io
,
120 BlockCacheLookupContext
* lookup_context
,
121 Env::IOPriority rate_limiter_priority
) override
;
122 // Used in partitioned filter code
123 void KeysMayMatch2(MultiGetRange
* range
,
124 const SliceTransform
* /*prefix_extractor*/,
125 const bool no_io
, BlockCacheLookupContext
* lookup_context
,
126 Env::IOPriority rate_limiter_priority
) {
127 KeysMayMatch(range
, no_io
, lookup_context
, rate_limiter_priority
);
130 void PrefixesMayMatch(MultiGetRange
* range
,
131 const SliceTransform
* prefix_extractor
,
133 BlockCacheLookupContext
* lookup_context
,
134 Env::IOPriority rate_limiter_priority
) override
;
135 size_t ApproximateMemoryUsage() const override
;
138 bool MayMatch(const Slice
& entry
, bool no_io
, GetContext
* get_context
,
139 BlockCacheLookupContext
* lookup_context
,
140 Env::IOPriority rate_limiter_priority
) const;
141 void MayMatch(MultiGetRange
* range
, bool no_io
,
142 const SliceTransform
* prefix_extractor
,
143 BlockCacheLookupContext
* lookup_context
,
144 Env::IOPriority rate_limiter_priority
) const;
147 } // namespace ROCKSDB_NAMESPACE