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).
5 //
6 // Copyright (c) 2011 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.
9 #include "table/block_based/partitioned_index_iterator.h"
10
11 namespace ROCKSDB_NAMESPACE {
Seek(const Slice & target)12 void ParititionedIndexIterator::Seek(const Slice& target) { SeekImpl(&target); }
13
SeekToFirst()14 void ParititionedIndexIterator::SeekToFirst() { SeekImpl(nullptr); }
15
SeekImpl(const Slice * target)16 void ParititionedIndexIterator::SeekImpl(const Slice* target) {
17 SavePrevIndexValue();
18
19 if (target) {
20 index_iter_->Seek(*target);
21 } else {
22 index_iter_->SeekToFirst();
23 }
24
25 if (!index_iter_->Valid()) {
26 ResetPartitionedIndexIter();
27 return;
28 }
29
30 InitPartitionedIndexBlock();
31
32 if (target) {
33 block_iter_.Seek(*target);
34 } else {
35 block_iter_.SeekToFirst();
36 }
37 FindKeyForward();
38
39 // We could check upper bound here, but that would be too complicated
40 // and checking index upper bound is less useful than for data blocks.
41
42 if (target) {
43 assert(!Valid() || (table_->get_rep()->index_key_includes_seq
44 ? (icomp_.Compare(*target, key()) <= 0)
45 : (user_comparator_.Compare(ExtractUserKey(*target),
46 key()) <= 0)));
47 }
48 }
49
SeekToLast()50 void ParititionedIndexIterator::SeekToLast() {
51 SavePrevIndexValue();
52 index_iter_->SeekToLast();
53 if (!index_iter_->Valid()) {
54 ResetPartitionedIndexIter();
55 return;
56 }
57 InitPartitionedIndexBlock();
58 block_iter_.SeekToLast();
59 FindKeyBackward();
60 }
61
Next()62 void ParititionedIndexIterator::Next() {
63 assert(block_iter_points_to_real_block_);
64 block_iter_.Next();
65 FindKeyForward();
66 }
67
Prev()68 void ParititionedIndexIterator::Prev() {
69 assert(block_iter_points_to_real_block_);
70 block_iter_.Prev();
71
72 FindKeyBackward();
73 }
74
InitPartitionedIndexBlock()75 void ParititionedIndexIterator::InitPartitionedIndexBlock() {
76 BlockHandle partitioned_index_handle = index_iter_->value().handle;
77 if (!block_iter_points_to_real_block_ ||
78 partitioned_index_handle.offset() != prev_block_offset_ ||
79 // if previous attempt of reading the block missed cache, try again
80 block_iter_.status().IsIncomplete()) {
81 if (block_iter_points_to_real_block_) {
82 ResetPartitionedIndexIter();
83 }
84 auto* rep = table_->get_rep();
85 bool is_for_compaction =
86 lookup_context_.caller == TableReaderCaller::kCompaction;
87 // Prefetch additional data for range scans (iterators).
88 // Implicit auto readahead:
89 // Enabled after 2 sequential IOs when ReadOptions.readahead_size == 0.
90 // Explicit user requested readahead:
91 // Enabled from the very first IO when ReadOptions.readahead_size is set.
92 block_prefetcher_.PrefetchIfNeeded(rep, partitioned_index_handle,
93 read_options_.readahead_size,
94 is_for_compaction);
95
96 Status s;
97 table_->NewDataBlockIterator<IndexBlockIter>(
98 read_options_, partitioned_index_handle, &block_iter_,
99 BlockType::kIndex,
100 /*get_context=*/nullptr, &lookup_context_, s,
101 block_prefetcher_.prefetch_buffer(),
102 /*for_compaction=*/is_for_compaction);
103 block_iter_points_to_real_block_ = true;
104 // We could check upper bound here but it is complicated to reason about
105 // upper bound in index iterator. On the other than, in large scans, index
106 // iterators are moved much less frequently compared to data blocks. So
107 // the upper bound check is skipped for simplicity.
108 }
109 }
110
FindKeyForward()111 void ParititionedIndexIterator::FindKeyForward() {
112 // This method's code is kept short to make it likely to be inlined.
113
114 assert(block_iter_points_to_real_block_);
115
116 if (!block_iter_.Valid()) {
117 // This is the only call site of FindBlockForward(), but it's extracted into
118 // a separate method to keep FindKeyForward() short and likely to be
119 // inlined. When transitioning to a different block, we call
120 // FindBlockForward(), which is much longer and is probably not inlined.
121 FindBlockForward();
122 } else {
123 // This is the fast path that avoids a function call.
124 }
125 }
126
FindBlockForward()127 void ParititionedIndexIterator::FindBlockForward() {
128 // TODO the while loop inherits from two-level-iterator. We don't know
129 // whether a block can be empty so it can be replaced by an "if".
130 do {
131 if (!block_iter_.status().ok()) {
132 return;
133 }
134 ResetPartitionedIndexIter();
135 index_iter_->Next();
136
137 if (!index_iter_->Valid()) {
138 return;
139 }
140
141 InitPartitionedIndexBlock();
142 block_iter_.SeekToFirst();
143 } while (!block_iter_.Valid());
144 }
145
FindKeyBackward()146 void ParititionedIndexIterator::FindKeyBackward() {
147 while (!block_iter_.Valid()) {
148 if (!block_iter_.status().ok()) {
149 return;
150 }
151
152 ResetPartitionedIndexIter();
153 index_iter_->Prev();
154
155 if (index_iter_->Valid()) {
156 InitPartitionedIndexBlock();
157 block_iter_.SeekToLast();
158 } else {
159 return;
160 }
161 }
162 }
163 } // namespace ROCKSDB_NAMESPACE
164