/Users/deen/code/yugabyte-db/src/yb/rocksdb/table/block_based_filter_block_test.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | // Copyright (c) 2012 The LevelDB Authors. All rights reserved. |
21 | | // Use of this source code is governed by a BSD-style license that can be |
22 | | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
23 | | |
24 | | #include <string> |
25 | | #include <gtest/gtest.h> |
26 | | |
27 | | #include "yb/rocksdb/table/block_based_filter_block.h" |
28 | | |
29 | | #include "yb/rocksdb/filter_policy.h" |
30 | | #include "yb/rocksdb/util/coding.h" |
31 | | #include "yb/rocksdb/util/hash.h" |
32 | | #include "yb/rocksdb/util/logging.h" |
33 | | #include "yb/rocksdb/env.h" |
34 | | |
35 | | #include "yb/rocksdb/util/testutil.h" |
36 | | |
37 | | namespace rocksdb { |
38 | | |
39 | | // For testing: emit an array with one hash value per key |
40 | | class TestHashFilter : public FilterPolicy { |
41 | | public: |
42 | 0 | const char* Name() const override { return "TestHashFilter"; } |
43 | | |
44 | | virtual void CreateFilter(const Slice* keys, int n, |
45 | 4 | std::string* dst) const override { |
46 | 14 | for (int i = 0; i < n; i++) { |
47 | 10 | uint32_t h = Hash(keys[i].data(), keys[i].size(), 1); |
48 | 10 | PutFixed32(dst, h); |
49 | 10 | } |
50 | 4 | } |
51 | | |
52 | | virtual bool KeyMayMatch(const Slice& key, |
53 | 23 | const Slice& filter) const override { |
54 | 23 | uint32_t h = Hash(key.data(), key.size(), 1); |
55 | 53 | for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) { |
56 | 40 | if (h == DecodeFixed32(filter.data() + i)) { |
57 | 10 | return true; |
58 | 10 | } |
59 | 40 | } |
60 | 13 | return false; |
61 | 23 | } |
62 | | |
63 | 0 | virtual FilterType GetFilterType() const override { return kBlockBasedFilter; } |
64 | | }; |
65 | | |
66 | | class FilterBlockTest : public RocksDBTest { |
67 | | public: |
68 | | TestHashFilter policy_; |
69 | | BlockBasedTableOptions table_options_; |
70 | | |
71 | 3 | FilterBlockTest() { |
72 | 3 | table_options_.filter_policy.reset(new TestHashFilter()); |
73 | 3 | } |
74 | | }; |
75 | | |
76 | 1 | TEST_F(FilterBlockTest, EmptyBuilder) { |
77 | 1 | BlockBasedFilterBlockBuilder builder(nullptr, table_options_); |
78 | 1 | BlockContents block(builder.Finish(), false, kNoCompression); |
79 | 1 | ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block.data)); |
80 | 1 | BlockBasedFilterBlockReader reader(nullptr, table_options_, true, |
81 | 1 | std::move(block)); |
82 | 1 | ASSERT_TRUE(reader.KeyMayMatch("foo", 0)); |
83 | 1 | ASSERT_TRUE(reader.KeyMayMatch("foo", 100000)); |
84 | 1 | } |
85 | | |
86 | 1 | TEST_F(FilterBlockTest, SingleChunk) { |
87 | 1 | BlockBasedFilterBlockBuilder builder(nullptr, table_options_); |
88 | 1 | builder.StartBlock(100); |
89 | 1 | builder.Add("foo"); |
90 | 1 | builder.Add("bar"); |
91 | 1 | builder.Add("box"); |
92 | 1 | builder.StartBlock(200); |
93 | 1 | builder.Add("box"); |
94 | 1 | builder.StartBlock(300); |
95 | 1 | builder.Add("hello"); |
96 | 1 | BlockContents block(builder.Finish(), false, kNoCompression); |
97 | 1 | BlockBasedFilterBlockReader reader(nullptr, table_options_, true, |
98 | 1 | std::move(block)); |
99 | 1 | ASSERT_TRUE(reader.KeyMayMatch("foo", 100)); |
100 | 1 | ASSERT_TRUE(reader.KeyMayMatch("bar", 100)); |
101 | 1 | ASSERT_TRUE(reader.KeyMayMatch("box", 100)); |
102 | 1 | ASSERT_TRUE(reader.KeyMayMatch("hello", 100)); |
103 | 1 | ASSERT_TRUE(reader.KeyMayMatch("foo", 100)); |
104 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("missing", 100)); |
105 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("other", 100)); |
106 | 1 | } |
107 | | |
108 | 1 | TEST_F(FilterBlockTest, MultiChunk) { |
109 | 1 | BlockBasedFilterBlockBuilder builder(nullptr, table_options_); |
110 | | |
111 | | // First filter |
112 | 1 | builder.StartBlock(0); |
113 | 1 | builder.Add("foo"); |
114 | 1 | builder.StartBlock(2000); |
115 | 1 | builder.Add("bar"); |
116 | | |
117 | | // Second filter |
118 | 1 | builder.StartBlock(3100); |
119 | 1 | builder.Add("box"); |
120 | | |
121 | | // Third filter is empty |
122 | | |
123 | | // Last filter |
124 | 1 | builder.StartBlock(9000); |
125 | 1 | builder.Add("box"); |
126 | 1 | builder.Add("hello"); |
127 | | |
128 | 1 | BlockContents block(builder.Finish(), false, kNoCompression); |
129 | 1 | BlockBasedFilterBlockReader reader(nullptr, table_options_, true, |
130 | 1 | std::move(block)); |
131 | | |
132 | | // Check first filter |
133 | 1 | ASSERT_TRUE(reader.KeyMayMatch("foo", 0)); |
134 | 1 | ASSERT_TRUE(reader.KeyMayMatch("bar", 2000)); |
135 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("box", 0)); |
136 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("hello", 0)); |
137 | | |
138 | | // Check second filter |
139 | 1 | ASSERT_TRUE(reader.KeyMayMatch("box", 3100)); |
140 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("foo", 3100)); |
141 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("bar", 3100)); |
142 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("hello", 3100)); |
143 | | |
144 | | // Check third filter (empty) |
145 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("foo", 4100)); |
146 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("bar", 4100)); |
147 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("box", 4100)); |
148 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("hello", 4100)); |
149 | | |
150 | | // Check last filter |
151 | 1 | ASSERT_TRUE(reader.KeyMayMatch("box", 9000)); |
152 | 1 | ASSERT_TRUE(reader.KeyMayMatch("hello", 9000)); |
153 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("foo", 9000)); |
154 | 1 | ASSERT_TRUE(!reader.KeyMayMatch("bar", 9000)); |
155 | 1 | } |
156 | | |
157 | | // Test for block based filter block |
158 | | // use new interface in FilterPolicy to create filter builder/reader |
159 | | class BlockBasedFilterBlockTest : public RocksDBTest { |
160 | | public: |
161 | | BlockBasedTableOptions table_options_; |
162 | | |
163 | 3 | BlockBasedFilterBlockTest() { |
164 | 3 | table_options_.filter_policy.reset(NewBloomFilterPolicy(10)); |
165 | 3 | } |
166 | | |
167 | 3 | ~BlockBasedFilterBlockTest() {} |
168 | | }; |
169 | | |
170 | 1 | TEST_F(BlockBasedFilterBlockTest, BlockBasedEmptyBuilder) { |
171 | 1 | FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder( |
172 | 1 | nullptr, table_options_); |
173 | 1 | BlockContents block(builder->Finish(), false, kNoCompression); |
174 | 1 | ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block.data)); |
175 | 1 | FilterBlockReader* reader = new BlockBasedFilterBlockReader( |
176 | 1 | nullptr, table_options_, true, std::move(block)); |
177 | 1 | ASSERT_TRUE(reader->KeyMayMatch("foo", 0)); |
178 | 1 | ASSERT_TRUE(reader->KeyMayMatch("foo", 100000)); |
179 | | |
180 | 1 | delete builder; |
181 | 1 | delete reader; |
182 | 1 | } |
183 | | |
184 | 1 | TEST_F(BlockBasedFilterBlockTest, BlockBasedSingleChunk) { |
185 | 1 | FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder( |
186 | 1 | nullptr, table_options_); |
187 | 1 | builder->StartBlock(100); |
188 | 1 | builder->Add("foo"); |
189 | 1 | builder->Add("bar"); |
190 | 1 | builder->Add("box"); |
191 | 1 | builder->StartBlock(200); |
192 | 1 | builder->Add("box"); |
193 | 1 | builder->StartBlock(300); |
194 | 1 | builder->Add("hello"); |
195 | 1 | BlockContents block(builder->Finish(), false, kNoCompression); |
196 | 1 | FilterBlockReader* reader = new BlockBasedFilterBlockReader( |
197 | 1 | nullptr, table_options_, true, std::move(block)); |
198 | 1 | ASSERT_TRUE(reader->KeyMayMatch("foo", 100)); |
199 | 1 | ASSERT_TRUE(reader->KeyMayMatch("bar", 100)); |
200 | 1 | ASSERT_TRUE(reader->KeyMayMatch("box", 100)); |
201 | 1 | ASSERT_TRUE(reader->KeyMayMatch("hello", 100)); |
202 | 1 | ASSERT_TRUE(reader->KeyMayMatch("foo", 100)); |
203 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("missing", 100)); |
204 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("other", 100)); |
205 | | |
206 | 1 | delete builder; |
207 | 1 | delete reader; |
208 | 1 | } |
209 | | |
210 | 1 | TEST_F(BlockBasedFilterBlockTest, BlockBasedMultiChunk) { |
211 | 1 | FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder( |
212 | 1 | nullptr, table_options_); |
213 | | |
214 | | // First filter |
215 | 1 | builder->StartBlock(0); |
216 | 1 | builder->Add("foo"); |
217 | 1 | builder->StartBlock(2000); |
218 | 1 | builder->Add("bar"); |
219 | | |
220 | | // Second filter |
221 | 1 | builder->StartBlock(3100); |
222 | 1 | builder->Add("box"); |
223 | | |
224 | | // Third filter is empty |
225 | | |
226 | | // Last filter |
227 | 1 | builder->StartBlock(9000); |
228 | 1 | builder->Add("box"); |
229 | 1 | builder->Add("hello"); |
230 | | |
231 | 1 | BlockContents block(builder->Finish(), false, kNoCompression); |
232 | 1 | FilterBlockReader* reader = new BlockBasedFilterBlockReader( |
233 | 1 | nullptr, table_options_, true, std::move(block)); |
234 | | |
235 | | // Check first filter |
236 | 1 | ASSERT_TRUE(reader->KeyMayMatch("foo", 0)); |
237 | 1 | ASSERT_TRUE(reader->KeyMayMatch("bar", 2000)); |
238 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("box", 0)); |
239 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("hello", 0)); |
240 | | |
241 | | // Check second filter |
242 | 1 | ASSERT_TRUE(reader->KeyMayMatch("box", 3100)); |
243 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("foo", 3100)); |
244 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("bar", 3100)); |
245 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("hello", 3100)); |
246 | | |
247 | | // Check third filter (empty) |
248 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("foo", 4100)); |
249 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("bar", 4100)); |
250 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("box", 4100)); |
251 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("hello", 4100)); |
252 | | |
253 | | // Check last filter |
254 | 1 | ASSERT_TRUE(reader->KeyMayMatch("box", 9000)); |
255 | 1 | ASSERT_TRUE(reader->KeyMayMatch("hello", 9000)); |
256 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("foo", 9000)); |
257 | 1 | ASSERT_TRUE(!reader->KeyMayMatch("bar", 9000)); |
258 | | |
259 | 1 | delete builder; |
260 | 1 | delete reader; |
261 | 1 | } |
262 | | |
263 | | } // namespace rocksdb |
264 | | |
265 | 13.2k | int main(int argc, char** argv) { |
266 | 13.2k | ::testing::InitGoogleTest(&argc, argv); |
267 | 13.2k | return RUN_ALL_TESTS(); |
268 | 13.2k | } |