/Users/deen/code/yugabyte-db/src/yb/rocksdb/table/index_reader.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) YugaByte, Inc. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
4 | | // in compliance with the License. You may obtain a copy of the License at |
5 | | // |
6 | | // http://www.apache.org/licenses/LICENSE-2.0 |
7 | | // |
8 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
9 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
10 | | // or implied. See the License for the specific language governing permissions and limitations |
11 | | // under the License. |
12 | | // |
13 | | |
14 | | #ifndef YB_ROCKSDB_TABLE_INDEX_READER_H |
15 | | #define YB_ROCKSDB_TABLE_INDEX_READER_H |
16 | | |
17 | | #include <stddef.h> |
18 | | |
19 | | #include "yb/rocksdb/status.h" |
20 | | #include "yb/rocksdb/table/block.h" |
21 | | #include "yb/rocksdb/table/two_level_iterator.h" |
22 | | |
23 | | #include "yb/util/logging.h" |
24 | | |
25 | | namespace rocksdb { |
26 | | |
27 | | using yb::Result; |
28 | | |
29 | | class BlockBasedTable; |
30 | | class BlockHandle; |
31 | | class BlockIter; |
32 | | class Comparator; |
33 | | class Env; |
34 | | class Footer; |
35 | | class InternalIterator; |
36 | | class RandomAccessFileReader; |
37 | | |
38 | | // -- IndexReader and its subclasses |
39 | | // IndexReader is the interface that provide the functionality for index access. |
40 | | class IndexReader { |
41 | | public: |
42 | | explicit IndexReader(const ComparatorPtr& comparator) |
43 | 76.1k | : comparator_(comparator) {} |
44 | | |
45 | 71.9k | virtual ~IndexReader() {} |
46 | | |
47 | | // Create an iterator for index access. |
48 | | // If not null iter is passed in, implementation was able to update it and it should be used by |
49 | | // caller as an index iterator, then nullptr is returned. |
50 | | // Otherwise, new iterator is created and returned. |
51 | | // |
52 | | // For multi-level index: |
53 | | // - top level index block iterator is passed and updated instead of the whole index iterator, |
54 | | // but return semantic is the same - the whole index iterator is returned. |
55 | | // - index_iterator_state is used to create secondary iterators on index. |
56 | | virtual InternalIterator* NewIterator(BlockIter* iter = nullptr, |
57 | | TwoLevelIteratorState* index_iterator_state = nullptr, |
58 | | bool total_order_seek = true) = 0; |
59 | | |
60 | | // Returns approximate middle key from the index. Key from the index might not match any key |
61 | | // actually written to SST file, because keys could be shortened and substituted before them are |
62 | | // written into the index (see ShortenedIndexBuilder). |
63 | | virtual Result<Slice> GetMiddleKey() = 0; |
64 | | |
65 | | // The size of the index. |
66 | | virtual size_t size() const = 0; |
67 | | // Memory usage of the index block |
68 | | virtual size_t usable_size() const = 0; |
69 | | |
70 | | // Report an approximation of how much memory has been used other than memory |
71 | | // that was allocated in block cache. |
72 | | virtual size_t ApproximateMemoryUsage() const = 0; |
73 | | |
74 | | protected: |
75 | | ComparatorPtr comparator_; |
76 | | }; |
77 | | |
78 | | // Index that allows binary search lookup for the first key of each block. |
79 | | // This class can be viewed as a thin wrapper for `Block` class which already |
80 | | // supports binary search. |
81 | | class BinarySearchIndexReader : public IndexReader { |
82 | | public: |
83 | | // Read index from the file and create an instance for |
84 | | // `BinarySearchIndexReader`. |
85 | | // On success, index_reader will be populated; otherwise it will remain |
86 | | // unmodified. |
87 | | static CHECKED_STATUS Create( |
88 | | RandomAccessFileReader* file, const Footer& footer, const BlockHandle& index_handle, Env* env, |
89 | | const ComparatorPtr& comparator, std::unique_ptr<IndexReader>* index_reader, |
90 | | const std::shared_ptr<yb::MemTracker>& mem_tracker); |
91 | | |
92 | | InternalIterator* NewIterator( |
93 | | BlockIter* iter = nullptr, |
94 | | // Rest of parameters are ignored by BinarySearchIndexReader. |
95 | 4.55M | TwoLevelIteratorState* state = nullptr, bool total_order_seek = true) override { |
96 | 4.55M | auto new_iter = index_block_->NewIndexIterator(comparator_.get(), iter, true); |
97 | 4.55M | return iter ? nullptr : new_iter; |
98 | 4.55M | } |
99 | | |
100 | 0 | size_t size() const override { |
101 | 0 | DCHECK(index_block_); |
102 | 0 | return index_block_->size(); |
103 | 0 | } |
104 | | |
105 | 0 | size_t usable_size() const override { |
106 | 0 | DCHECK(index_block_); |
107 | 0 | return index_block_->usable_size(); |
108 | 0 | } |
109 | | |
110 | 0 | size_t ApproximateMemoryUsage() const override { |
111 | 0 | DCHECK(index_block_); |
112 | 0 | return index_block_->ApproximateMemoryUsage(); |
113 | 0 | } |
114 | | |
115 | | Result<Slice> GetMiddleKey() override; |
116 | | |
117 | | private: |
118 | | BinarySearchIndexReader(const ComparatorPtr& comparator, |
119 | | std::unique_ptr<Block>&& index_block) |
120 | 3.71k | : IndexReader(comparator), index_block_(std::move(index_block)) { |
121 | 3.71k | DCHECK(index_block_); |
122 | 3.71k | } |
123 | | |
124 | 3.42k | ~BinarySearchIndexReader() {} |
125 | | |
126 | | const std::unique_ptr<Block> index_block_; |
127 | | }; |
128 | | |
129 | | // Index that leverages an internal hash table to quicken the lookup for a given |
130 | | // key. |
131 | | class HashIndexReader : public IndexReader { |
132 | | public: |
133 | | static CHECKED_STATUS Create( |
134 | | const SliceTransform* hash_key_extractor, const Footer& footer, RandomAccessFileReader* file, |
135 | | Env* env, const ComparatorPtr& comparator, const BlockHandle& index_handle, |
136 | | InternalIterator* meta_index_iter, std::unique_ptr<IndexReader>* index_reader, |
137 | | bool hash_index_allow_collision, const std::shared_ptr<yb::MemTracker>& mem_tracker); |
138 | | |
139 | | InternalIterator* NewIterator( |
140 | | BlockIter* iter = nullptr, TwoLevelIteratorState* state = nullptr, |
141 | 111k | bool total_order_seek = true) override { |
142 | 111k | auto new_iter = index_block_->NewIndexIterator(comparator_.get(), iter, total_order_seek); |
143 | 102k | return iter ? nullptr : new_iter; |
144 | 111k | } |
145 | | |
146 | 0 | size_t size() const override { |
147 | 0 | DCHECK(index_block_); |
148 | 0 | return index_block_->size(); |
149 | 0 | } |
150 | | |
151 | 0 | size_t usable_size() const override { |
152 | 0 | DCHECK(index_block_); |
153 | 0 | return index_block_->usable_size(); |
154 | 0 | } |
155 | | |
156 | 0 | size_t ApproximateMemoryUsage() const override { |
157 | 0 | DCHECK(index_block_); |
158 | 0 | return index_block_->ApproximateMemoryUsage() + prefixes_contents_.data.size(); |
159 | 0 | } |
160 | | |
161 | | Result<Slice> GetMiddleKey() override; |
162 | | |
163 | | private: |
164 | | HashIndexReader(const ComparatorPtr& comparator, std::unique_ptr<Block>&& index_block) |
165 | 1.65k | : IndexReader(comparator), index_block_(std::move(index_block)) { |
166 | 1.65k | DCHECK(index_block_); |
167 | 1.65k | } |
168 | | |
169 | 1.65k | ~HashIndexReader() {} |
170 | | |
171 | 0 | void OwnPrefixesContents(BlockContents&& prefixes_contents) { |
172 | 0 | prefixes_contents_ = std::move(prefixes_contents); |
173 | 0 | } |
174 | | |
175 | | const std::unique_ptr<Block> index_block_; |
176 | | BlockContents prefixes_contents_; |
177 | | }; |
178 | | |
179 | | // Index that allows binary search lookup in a multi-level index structure. |
180 | | class MultiLevelIndexReader : public IndexReader { |
181 | | public: |
182 | | // Read the top level index from the file and create an instance for `MultiLevelIndexReader`. |
183 | | static Result<std::unique_ptr<MultiLevelIndexReader>> Create( |
184 | | RandomAccessFileReader* file, const Footer& footer, int num_levels, |
185 | | const BlockHandle& top_level_index_handle, Env* env, const ComparatorPtr& comparator, |
186 | | const std::shared_ptr<yb::MemTracker>& mem_tracker); |
187 | | |
188 | | MultiLevelIndexReader( |
189 | | const ComparatorPtr& comparator, int num_levels, |
190 | | std::unique_ptr<Block> top_level_index_block) |
191 | | : IndexReader(comparator), |
192 | | num_levels_(num_levels), |
193 | 70.8k | top_level_index_block_(std::move(top_level_index_block)) { |
194 | 70.8k | DCHECK_ONLY_NOTNULL(top_level_index_block_.get()); |
195 | 70.8k | } |
196 | | |
197 | 66.8k | ~MultiLevelIndexReader() {} |
198 | | |
199 | | InternalIterator* NewIterator( |
200 | | BlockIter* iter, TwoLevelIteratorState* index_iterator_state, bool) override; |
201 | | |
202 | | Result<Slice> GetMiddleKey() override; |
203 | | |
204 | | private: |
205 | 0 | size_t size() const override { return top_level_index_block_->size(); } |
206 | | |
207 | 4.23k | size_t usable_size() const override { |
208 | 4.23k | return top_level_index_block_->usable_size(); |
209 | 4.23k | } |
210 | | |
211 | 29 | size_t ApproximateMemoryUsage() const override { |
212 | 29 | return top_level_index_block_->ApproximateMemoryUsage(); |
213 | 29 | } |
214 | | |
215 | | const int num_levels_; |
216 | | const std::unique_ptr<Block> top_level_index_block_; |
217 | | }; |
218 | | |
219 | | } // namespace rocksdb |
220 | | |
221 | | #endif // YB_ROCKSDB_TABLE_INDEX_READER_H |