]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae FG |
5 | |
6 | #include "table/full_filter_block.h" | |
7 | ||
11fdf7f2 TL |
8 | #ifdef ROCKSDB_MALLOC_USABLE_SIZE |
9 | #ifdef OS_FREEBSD | |
10 | #include <malloc_np.h> | |
11 | #else | |
12 | #include <malloc.h> | |
13 | #endif | |
14 | #endif | |
15 | ||
7c673cae FG |
16 | #include "monitoring/perf_context_imp.h" |
17 | #include "port/port.h" | |
18 | #include "rocksdb/filter_policy.h" | |
19 | #include "util/coding.h" | |
20 | ||
21 | namespace rocksdb { | |
22 | ||
23 | FullFilterBlockBuilder::FullFilterBlockBuilder( | |
24 | const SliceTransform* prefix_extractor, bool whole_key_filtering, | |
25 | FilterBitsBuilder* filter_bits_builder) | |
26 | : prefix_extractor_(prefix_extractor), | |
27 | whole_key_filtering_(whole_key_filtering), | |
11fdf7f2 TL |
28 | last_whole_key_recorded_(false), |
29 | last_prefix_recorded_(false), | |
7c673cae FG |
30 | num_added_(0) { |
31 | assert(filter_bits_builder != nullptr); | |
32 | filter_bits_builder_.reset(filter_bits_builder); | |
33 | } | |
34 | ||
35 | void FullFilterBlockBuilder::Add(const Slice& key) { | |
11fdf7f2 | 36 | const bool add_prefix = prefix_extractor_ && prefix_extractor_->InDomain(key); |
7c673cae | 37 | if (whole_key_filtering_) { |
11fdf7f2 TL |
38 | if (!add_prefix) { |
39 | AddKey(key); | |
40 | } else { | |
41 | // if both whole_key and prefix are added to bloom then we will have whole | |
42 | // key and prefix addition being interleaved and thus cannot rely on the | |
43 | // bits builder to properly detect the duplicates by comparing with the | |
44 | // last item. | |
45 | Slice last_whole_key = Slice(last_whole_key_str_); | |
46 | if (!last_whole_key_recorded_ || last_whole_key.compare(key) != 0) { | |
47 | AddKey(key); | |
48 | last_whole_key_recorded_ = true; | |
49 | last_whole_key_str_.assign(key.data(), key.size()); | |
50 | } | |
51 | } | |
7c673cae | 52 | } |
11fdf7f2 | 53 | if (add_prefix) { |
7c673cae FG |
54 | AddPrefix(key); |
55 | } | |
56 | } | |
57 | ||
58 | // Add key to filter if needed | |
59 | inline void FullFilterBlockBuilder::AddKey(const Slice& key) { | |
60 | filter_bits_builder_->AddKey(key); | |
61 | num_added_++; | |
62 | } | |
63 | ||
64 | // Add prefix to filter if needed | |
65 | inline void FullFilterBlockBuilder::AddPrefix(const Slice& key) { | |
66 | Slice prefix = prefix_extractor_->Transform(key); | |
11fdf7f2 TL |
67 | if (whole_key_filtering_) { |
68 | // if both whole_key and prefix are added to bloom then we will have whole | |
69 | // key and prefix addition being interleaved and thus cannot rely on the | |
70 | // bits builder to properly detect the duplicates by comparing with the last | |
71 | // item. | |
72 | Slice last_prefix = Slice(last_prefix_str_); | |
73 | if (!last_prefix_recorded_ || last_prefix.compare(prefix) != 0) { | |
74 | AddKey(prefix); | |
75 | last_prefix_recorded_ = true; | |
76 | last_prefix_str_.assign(prefix.data(), prefix.size()); | |
77 | } | |
78 | } else { | |
79 | AddKey(prefix); | |
80 | } | |
7c673cae FG |
81 | } |
82 | ||
11fdf7f2 TL |
83 | void FullFilterBlockBuilder::Reset() { |
84 | last_whole_key_recorded_ = false; | |
85 | last_prefix_recorded_ = false; | |
86 | } | |
87 | ||
88 | Slice FullFilterBlockBuilder::Finish(const BlockHandle& /*tmp*/, | |
89 | Status* status) { | |
90 | Reset(); | |
7c673cae FG |
91 | // In this impl we ignore BlockHandle |
92 | *status = Status::OK(); | |
93 | if (num_added_ != 0) { | |
94 | num_added_ = 0; | |
95 | return filter_bits_builder_->Finish(&filter_data_); | |
96 | } | |
97 | return Slice(); | |
98 | } | |
99 | ||
100 | FullFilterBlockReader::FullFilterBlockReader( | |
101 | const SliceTransform* prefix_extractor, bool _whole_key_filtering, | |
102 | const Slice& contents, FilterBitsReader* filter_bits_reader, | |
103 | Statistics* stats) | |
104 | : FilterBlockReader(contents.size(), stats, _whole_key_filtering), | |
105 | prefix_extractor_(prefix_extractor), | |
106 | contents_(contents) { | |
107 | assert(filter_bits_reader != nullptr); | |
108 | filter_bits_reader_.reset(filter_bits_reader); | |
11fdf7f2 TL |
109 | if (prefix_extractor_ != nullptr) { |
110 | full_length_enabled_ = | |
111 | prefix_extractor_->FullLengthEnabled(&prefix_extractor_full_length_); | |
112 | } | |
7c673cae FG |
113 | } |
114 | ||
115 | FullFilterBlockReader::FullFilterBlockReader( | |
116 | const SliceTransform* prefix_extractor, bool _whole_key_filtering, | |
117 | BlockContents&& contents, FilterBitsReader* filter_bits_reader, | |
118 | Statistics* stats) | |
119 | : FullFilterBlockReader(prefix_extractor, _whole_key_filtering, | |
120 | contents.data, filter_bits_reader, stats) { | |
121 | block_contents_ = std::move(contents); | |
122 | } | |
123 | ||
11fdf7f2 TL |
124 | bool FullFilterBlockReader::KeyMayMatch( |
125 | const Slice& key, const SliceTransform* /*prefix_extractor*/, | |
126 | uint64_t block_offset, const bool /*no_io*/, | |
127 | const Slice* const /*const_ikey_ptr*/) { | |
128 | #ifdef NDEBUG | |
129 | (void)block_offset; | |
130 | #endif | |
7c673cae FG |
131 | assert(block_offset == kNotValid); |
132 | if (!whole_key_filtering_) { | |
133 | return true; | |
134 | } | |
135 | return MayMatch(key); | |
136 | } | |
137 | ||
11fdf7f2 TL |
138 | bool FullFilterBlockReader::PrefixMayMatch( |
139 | const Slice& prefix, const SliceTransform* /* prefix_extractor */, | |
140 | uint64_t block_offset, const bool /*no_io*/, | |
141 | const Slice* const /*const_ikey_ptr*/) { | |
142 | #ifdef NDEBUG | |
143 | (void)block_offset; | |
144 | #endif | |
7c673cae | 145 | assert(block_offset == kNotValid); |
7c673cae FG |
146 | return MayMatch(prefix); |
147 | } | |
148 | ||
149 | bool FullFilterBlockReader::MayMatch(const Slice& entry) { | |
150 | if (contents_.size() != 0) { | |
151 | if (filter_bits_reader_->MayMatch(entry)) { | |
152 | PERF_COUNTER_ADD(bloom_sst_hit_count, 1); | |
153 | return true; | |
154 | } else { | |
155 | PERF_COUNTER_ADD(bloom_sst_miss_count, 1); | |
156 | return false; | |
157 | } | |
158 | } | |
159 | return true; // remain the same with block_based filter | |
160 | } | |
161 | ||
162 | size_t FullFilterBlockReader::ApproximateMemoryUsage() const { | |
11fdf7f2 TL |
163 | size_t usage = block_contents_.usable_size(); |
164 | #ifdef ROCKSDB_MALLOC_USABLE_SIZE | |
165 | usage += malloc_usable_size((void*)this); | |
166 | usage += malloc_usable_size(filter_bits_reader_.get()); | |
167 | #else | |
168 | usage += sizeof(*this); | |
169 | usage += sizeof(*filter_bits_reader_.get()); | |
170 | #endif // ROCKSDB_MALLOC_USABLE_SIZE | |
171 | return usage; | |
7c673cae | 172 | } |
11fdf7f2 TL |
173 | |
174 | bool FullFilterBlockReader::RangeMayExist(const Slice* iterate_upper_bound, | |
175 | const Slice& user_key, const SliceTransform* prefix_extractor, | |
176 | const Comparator* comparator, const Slice* const const_ikey_ptr, | |
177 | bool* filter_checked, bool need_upper_bound_check) { | |
178 | if (!prefix_extractor || !prefix_extractor->InDomain(user_key)) { | |
179 | *filter_checked = false; | |
180 | return true; | |
181 | } | |
182 | Slice prefix = prefix_extractor->Transform(user_key); | |
183 | if (need_upper_bound_check && | |
184 | !IsFilterCompatible(iterate_upper_bound, prefix, comparator)) { | |
185 | *filter_checked = false; | |
186 | return true; | |
187 | } else { | |
188 | *filter_checked = true; | |
189 | return PrefixMayMatch(prefix, prefix_extractor, kNotValid, false, | |
190 | const_ikey_ptr); | |
191 | } | |
192 | } | |
193 | ||
194 | bool FullFilterBlockReader::IsFilterCompatible( | |
195 | const Slice* iterate_upper_bound, const Slice& prefix, | |
196 | const Comparator* comparator) { | |
197 | // Try to reuse the bloom filter in the SST table if prefix_extractor in | |
198 | // mutable_cf_options has changed. If range [user_key, upper_bound) all | |
199 | // share the same prefix then we may still be able to use the bloom filter. | |
200 | if (iterate_upper_bound != nullptr && prefix_extractor_) { | |
201 | if (!prefix_extractor_->InDomain(*iterate_upper_bound)) { | |
202 | return false; | |
203 | } | |
204 | Slice upper_bound_xform = | |
205 | prefix_extractor_->Transform(*iterate_upper_bound); | |
206 | // first check if user_key and upper_bound all share the same prefix | |
207 | if (!comparator->Equal(prefix, upper_bound_xform)) { | |
208 | // second check if user_key's prefix is the immediate predecessor of | |
209 | // upper_bound and have the same length. If so, we know for sure all | |
210 | // keys in the range [user_key, upper_bound) share the same prefix. | |
211 | // Also need to make sure upper_bound are full length to ensure | |
212 | // correctness | |
213 | if (!full_length_enabled_ || | |
214 | iterate_upper_bound->size() != prefix_extractor_full_length_ || | |
215 | !comparator->IsSameLengthImmediateSuccessor(prefix, | |
216 | *iterate_upper_bound)) { | |
217 | return false; | |
218 | } | |
219 | } | |
220 | return true; | |
221 | } else { | |
222 | return false; | |
223 | } | |
224 | } | |
225 | ||
7c673cae | 226 | } // namespace rocksdb |