]>
git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/table/block_based/filter_block.h
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).
6 // Copyright (c) 2012 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
10 // A filter block is stored near the end of a Table file. It contains
11 // filters (e.g., bloom filters) for all data blocks in the table combined
12 // into a single filter block.
14 // It is a base class for BlockBasedFilter and FullFilter.
15 // These two are both used in BlockBasedTable. The first one contain filter
16 // For a part of keys in sst file, the second contain filter for all keys
26 #include "db/dbformat.h"
27 #include "rocksdb/options.h"
28 #include "rocksdb/slice.h"
29 #include "rocksdb/slice_transform.h"
30 #include "rocksdb/table.h"
31 #include "table/format.h"
32 #include "table/multiget_context.h"
33 #include "trace_replay/block_cache_tracer.h"
34 #include "util/hash.h"
36 namespace ROCKSDB_NAMESPACE
{
38 const uint64_t kNotValid
= ULLONG_MAX
;
42 using MultiGetRange
= MultiGetContext::Range
;
44 // A FilterBlockBuilder is used to construct all of the filters for a
45 // particular Table. It generates a single string which is stored as
46 // a special block in the Table.
48 // The sequence of calls to FilterBlockBuilder must match the regexp:
49 // (StartBlock Add*)* Finish
51 // BlockBased/Full FilterBlock would be called in the same way.
52 class FilterBlockBuilder
{
54 explicit FilterBlockBuilder() {}
56 FilterBlockBuilder(const FilterBlockBuilder
&) = delete;
57 void operator=(const FilterBlockBuilder
&) = delete;
59 virtual ~FilterBlockBuilder() {}
61 virtual bool IsBlockBased() = 0; // If is blockbased filter
62 virtual void StartBlock(uint64_t block_offset
) = 0; // Start new block filter
63 virtual void Add(const Slice
& key
) = 0; // Add a key to current filter
64 virtual size_t NumAdded() const = 0; // Number of keys added
65 Slice
Finish() { // Generate Filter
66 const BlockHandle empty_handle
;
67 Status dont_care_status
;
68 auto ret
= Finish(empty_handle
, &dont_care_status
);
69 assert(dont_care_status
.ok());
72 virtual Slice
Finish(const BlockHandle
& tmp
, Status
* status
) = 0;
75 // A FilterBlockReader is used to parse filter from SST table.
76 // KeyMayMatch and PrefixMayMatch would trigger filter checking
78 // BlockBased/Full FilterBlock would be called in the same way.
79 class FilterBlockReader
{
81 FilterBlockReader() = default;
82 virtual ~FilterBlockReader() = default;
84 FilterBlockReader(const FilterBlockReader
&) = delete;
85 FilterBlockReader
& operator=(const FilterBlockReader
&) = delete;
87 virtual bool IsBlockBased() = 0; // If is blockbased filter
90 * If no_io is set, then it returns true if it cannot answer the query without
91 * reading data from disk. This is used in PartitionedFilterBlockReader to
92 * avoid reading partitions that are not in block cache already
94 * Normally filters are built on only the user keys and the InternalKey is not
95 * needed for a query. The index in PartitionedFilterBlockReader however is
96 * built upon InternalKey and must be provided via const_ikey_ptr when running
99 virtual bool KeyMayMatch(const Slice
& key
,
100 const SliceTransform
* prefix_extractor
,
101 uint64_t block_offset
, const bool no_io
,
102 const Slice
* const const_ikey_ptr
,
103 GetContext
* get_context
,
104 BlockCacheLookupContext
* lookup_context
) = 0;
106 virtual void KeysMayMatch(MultiGetRange
* range
,
107 const SliceTransform
* prefix_extractor
,
108 uint64_t block_offset
, const bool no_io
,
109 BlockCacheLookupContext
* lookup_context
) {
110 for (auto iter
= range
->begin(); iter
!= range
->end(); ++iter
) {
111 const Slice ukey
= iter
->ukey
;
112 const Slice ikey
= iter
->ikey
;
113 GetContext
* const get_context
= iter
->get_context
;
114 if (!KeyMayMatch(ukey
, prefix_extractor
, block_offset
, no_io
, &ikey
,
115 get_context
, lookup_context
)) {
116 range
->SkipKey(iter
);
122 * no_io and const_ikey_ptr here means the same as in KeyMayMatch
124 virtual bool PrefixMayMatch(const Slice
& prefix
,
125 const SliceTransform
* prefix_extractor
,
126 uint64_t block_offset
, const bool no_io
,
127 const Slice
* const const_ikey_ptr
,
128 GetContext
* get_context
,
129 BlockCacheLookupContext
* lookup_context
) = 0;
131 virtual void PrefixesMayMatch(MultiGetRange
* range
,
132 const SliceTransform
* prefix_extractor
,
133 uint64_t block_offset
, const bool no_io
,
134 BlockCacheLookupContext
* lookup_context
) {
135 for (auto iter
= range
->begin(); iter
!= range
->end(); ++iter
) {
136 const Slice ukey
= iter
->ukey
;
137 const Slice ikey
= iter
->ikey
;
138 GetContext
* const get_context
= iter
->get_context
;
139 if (prefix_extractor
->InDomain(ukey
) &&
140 !PrefixMayMatch(prefix_extractor
->Transform(ukey
), prefix_extractor
,
141 block_offset
, no_io
, &ikey
, get_context
,
143 range
->SkipKey(iter
);
148 virtual size_t ApproximateMemoryUsage() const = 0;
150 // convert this object to a human readable form
151 virtual std::string
ToString() const {
152 std::string
error_msg("Unsupported filter \n");
156 virtual void CacheDependencies(bool /*pin*/) {}
158 virtual bool RangeMayExist(const Slice
* /*iterate_upper_bound*/,
159 const Slice
& user_key
,
160 const SliceTransform
* prefix_extractor
,
161 const Comparator
* /*comparator*/,
162 const Slice
* const const_ikey_ptr
,
163 bool* filter_checked
, bool need_upper_bound_check
,
164 BlockCacheLookupContext
* lookup_context
) {
165 if (need_upper_bound_check
) {
168 *filter_checked
= true;
169 Slice prefix
= prefix_extractor
->Transform(user_key
);
170 return PrefixMayMatch(prefix
, prefix_extractor
, kNotValid
, false,
171 const_ikey_ptr
, /* get_context */ nullptr,
176 } // namespace ROCKSDB_NAMESPACE