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).
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"
22 namespace ROCKSDB_NAMESPACE
{
25 class FilterBitsBuilder
;
26 class FilterBitsReader
;
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
38 class FullFilterBlockBuilder
: public FilterBlockBuilder
{
40 explicit FullFilterBlockBuilder(const SliceTransform
* prefix_extractor
,
41 bool whole_key_filtering
,
42 FilterBitsBuilder
* filter_bits_builder
);
44 FullFilterBlockBuilder(const FullFilterBlockBuilder
&) = delete;
45 void operator=(const FullFilterBlockBuilder
&) = delete;
47 // bits_builder is created in filter_policy, it should be passed in here
48 // directly. and be deleted here
49 ~FullFilterBlockBuilder() {}
51 virtual bool IsBlockBased() override
{ return false; }
52 virtual void StartBlock(uint64_t /*block_offset*/) override
{}
53 virtual void Add(const Slice
& key
) override
;
54 virtual size_t NumAdded() const override
{ return num_added_
; }
55 virtual Slice
Finish(const BlockHandle
& tmp
, Status
* status
) override
;
56 using FilterBlockBuilder::Finish
;
59 virtual void AddKey(const Slice
& key
);
60 std::unique_ptr
<FilterBitsBuilder
> filter_bits_builder_
;
62 void AddPrefix(const Slice
& key
);
63 const SliceTransform
* prefix_extractor() { return prefix_extractor_
; }
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_
;
77 std::unique_ptr
<const char[]> filter_data_
;
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
> {
86 FullFilterBlockReader(const BlockBasedTable
* t
,
87 CachableEntry
<ParsedFullFilterBlock
>&& filter_block
);
89 static std::unique_ptr
<FilterBlockReader
> Create(
90 const BlockBasedTable
* table
, const ReadOptions
& ro
,
91 FilePrefetchBuffer
* prefetch_buffer
, bool use_cache
, bool prefetch
,
92 bool pin
, BlockCacheLookupContext
* lookup_context
);
94 bool IsBlockBased() override
{ return false; }
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
;
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
;
108 void KeysMayMatch(MultiGetRange
* range
,
109 const SliceTransform
* prefix_extractor
,
110 uint64_t block_offset
, const bool no_io
,
111 BlockCacheLookupContext
* lookup_context
) override
;
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
, bool no_io
,
123 BlockCacheLookupContext
* lookup_context
) override
;
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;
135 bool full_length_enabled_
;
136 size_t prefix_extractor_full_length_
;
139 } // namespace ROCKSDB_NAMESPACE