Line data Source code
1 : // Copyright 2011 The LevelDB-Go and Pebble Authors. All rights reserved. Use
2 : // of this source code is governed by a BSD-style license that can be found in
3 : // the LICENSE file.
4 :
5 : package sstable
6 :
7 : import (
8 : "context"
9 : "fmt"
10 :
11 : "github.com/cockroachdb/pebble/internal/base"
12 : "github.com/cockroachdb/pebble/objstorage/objstorageprovider/objiotracing"
13 : )
14 :
15 : type twoLevelIterator struct {
16 : singleLevelIterator
17 : // maybeFilteredKeysSingleLevel indicates whether the last iterator
18 : // positioning operation may have skipped any index blocks due to
19 : // block-property filters when positioning the top-level-index.
20 : maybeFilteredKeysTwoLevel bool
21 : topLevelIndex blockIter
22 : }
23 :
24 : // twoLevelIterator implements the base.InternalIterator interface.
25 : var _ base.InternalIterator = (*twoLevelIterator)(nil)
26 :
27 : // loadIndex loads the index block at the current top level index position and
28 : // leaves i.index unpositioned. If unsuccessful, it gets i.err to any error
29 : // encountered, which may be nil if we have simply exhausted the entire table.
30 : // This is used for two level indexes.
31 1 : func (i *twoLevelIterator) loadIndex(dir int8) loadBlockResult {
32 1 : // Ensure the index data block iterators are invalidated even if loading of
33 1 : // the index fails.
34 1 : i.data.invalidate()
35 1 : i.index.invalidate()
36 1 : if !i.topLevelIndex.valid() {
37 0 : i.index.offset = 0
38 0 : i.index.restarts = 0
39 0 : return loadBlockFailed
40 0 : }
41 1 : v := i.topLevelIndex.value()
42 1 : bhp, err := decodeBlockHandleWithProperties(v.InPlaceValue())
43 1 : if err != nil {
44 0 : i.err = base.CorruptionErrorf("pebble/table: corrupt top level index entry")
45 0 : return loadBlockFailed
46 0 : }
47 1 : if i.bpfs != nil {
48 1 : intersects, err := i.bpfs.intersects(bhp.Props)
49 1 : if err != nil {
50 0 : i.err = errCorruptIndexEntry
51 0 : return loadBlockFailed
52 0 : }
53 1 : if intersects == blockMaybeExcluded {
54 0 : intersects = i.resolveMaybeExcluded(dir)
55 0 : }
56 1 : if intersects == blockExcluded {
57 1 : i.maybeFilteredKeysTwoLevel = true
58 1 : return loadBlockIrrelevant
59 1 : }
60 : // blockIntersects
61 : }
62 1 : ctx := objiotracing.WithBlockType(i.ctx, objiotracing.MetadataBlock)
63 1 : indexBlock, err := i.reader.readBlock(ctx, bhp.BlockHandle, nil /* transform */, nil /* readHandle */, i.stats, i.bufferPool)
64 1 : if err != nil {
65 1 : i.err = err
66 1 : return loadBlockFailed
67 1 : }
68 1 : if i.err = i.index.initHandle(i.cmp, indexBlock, i.reader.Properties.GlobalSeqNum, false); i.err == nil {
69 1 : return loadBlockOK
70 1 : }
71 0 : return loadBlockFailed
72 : }
73 :
74 : // resolveMaybeExcluded is invoked when the block-property filterer has found
75 : // that an index block is excluded according to its properties but only if its
76 : // bounds fall within the filter's current bounds. This function consults the
77 : // apprioriate bound, depending on the iteration direction, and returns either
78 : // `blockIntersects` or
79 : // `blockMaybeExcluded`.
80 0 : func (i *twoLevelIterator) resolveMaybeExcluded(dir int8) intersectsResult {
81 0 : // This iterator is configured with a bound-limited block property filter.
82 0 : // The bpf determined this entire index block could be excluded from
83 0 : // iteration based on the property encoded in the block handle. However, we
84 0 : // still need to determine if the index block is wholly contained within the
85 0 : // filter's key bounds.
86 0 : //
87 0 : // External guarantees ensure all its data blocks' keys are ≥ the filter's
88 0 : // lower bound during forward iteration, and that all its data blocks' keys
89 0 : // are < the filter's upper bound during backward iteration. We only need to
90 0 : // determine if the opposite bound is also met.
91 0 : //
92 0 : // The index separator in topLevelIndex.Key() provides an inclusive
93 0 : // upper-bound for the index block's keys, guaranteeing that all its keys
94 0 : // are ≤ topLevelIndex.Key(). For forward iteration, this is all we need.
95 0 : if dir > 0 {
96 0 : // Forward iteration.
97 0 : if i.bpfs.boundLimitedFilter.KeyIsWithinUpperBound(i.topLevelIndex.Key().UserKey) {
98 0 : return blockExcluded
99 0 : }
100 0 : return blockIntersects
101 : }
102 :
103 : // Reverse iteration.
104 : //
105 : // Because we're iterating in the reverse direction, we don't yet have
106 : // enough context available to determine if the block is wholly contained
107 : // within its bounds. This case arises only during backward iteration,
108 : // because of the way the index is structured.
109 : //
110 : // Consider a bound-limited bpf limited to the bounds [b,d), loading the
111 : // block with separator `c`. During reverse iteration, the guarantee that
112 : // all the block's keys are < `d` is externally provided, but no guarantee
113 : // is made on the bpf's lower bound. The separator `c` only provides an
114 : // inclusive upper bound on the block's keys, indicating that the
115 : // corresponding block handle points to a block containing only keys ≤ `c`.
116 : //
117 : // To establish a lower bound, we step the top-level index backwards to read
118 : // the previous block's separator, which provides an inclusive lower bound
119 : // on the original index block's keys. Afterwards, we step forward to
120 : // restore our top-level index position.
121 0 : if peekKey, _ := i.topLevelIndex.Prev(); peekKey == nil {
122 0 : // The original block points to the first index block of this table. If
123 0 : // we knew the lower bound for the entire table, it could provide a
124 0 : // lower bound, but the code refactoring necessary to read it doesn't
125 0 : // seem worth the payoff. We fall through to loading the block.
126 0 : } else if i.bpfs.boundLimitedFilter.KeyIsWithinLowerBound(peekKey.UserKey) {
127 0 : // The lower-bound on the original index block falls within the filter's
128 0 : // bounds, and we can skip the block (after restoring our current
129 0 : // top-level index position).
130 0 : _, _ = i.topLevelIndex.Next()
131 0 : return blockExcluded
132 0 : }
133 0 : _, _ = i.topLevelIndex.Next()
134 0 : return blockIntersects
135 : }
136 :
137 : // Note that lower, upper passed into init has nothing to do with virtual sstable
138 : // bounds. If the virtualState passed in is not nil, then virtual sstable bounds
139 : // will be enforced.
140 : func (i *twoLevelIterator) init(
141 : ctx context.Context,
142 : r *Reader,
143 : v *virtualState,
144 : lower, upper []byte,
145 : filterer *BlockPropertiesFilterer,
146 : useFilter, hideObsoletePoints bool,
147 : stats *base.InternalIteratorStats,
148 : rp ReaderProvider,
149 : bufferPool *BufferPool,
150 1 : ) error {
151 1 : if r.err != nil {
152 0 : return r.err
153 0 : }
154 1 : topLevelIndexH, err := r.readIndex(ctx, stats)
155 1 : if err != nil {
156 1 : return err
157 1 : }
158 1 : if v != nil {
159 1 : i.vState = v
160 1 : // Note that upper is exclusive here.
161 1 : i.endKeyInclusive, lower, upper = v.constrainBounds(lower, upper, false /* endInclusive */)
162 1 : }
163 :
164 1 : i.ctx = ctx
165 1 : i.lower = lower
166 1 : i.upper = upper
167 1 : i.bpfs = filterer
168 1 : i.useFilter = useFilter
169 1 : i.reader = r
170 1 : i.cmp = r.Compare
171 1 : i.stats = stats
172 1 : i.hideObsoletePoints = hideObsoletePoints
173 1 : i.bufferPool = bufferPool
174 1 : err = i.topLevelIndex.initHandle(i.cmp, topLevelIndexH, r.Properties.GlobalSeqNum, false)
175 1 : if err != nil {
176 0 : // blockIter.Close releases topLevelIndexH and always returns a nil error
177 0 : _ = i.topLevelIndex.Close()
178 0 : return err
179 0 : }
180 1 : i.dataRH = r.readable.NewReadHandle(ctx)
181 1 : if r.tableFormat >= TableFormatPebblev3 {
182 1 : if r.Properties.NumValueBlocks > 0 {
183 1 : i.vbReader = &valueBlockReader{
184 1 : ctx: ctx,
185 1 : bpOpen: i,
186 1 : rp: rp,
187 1 : vbih: r.valueBIH,
188 1 : stats: stats,
189 1 : }
190 1 : i.data.lazyValueHandling.vbr = i.vbReader
191 1 : i.vbRH = r.readable.NewReadHandle(ctx)
192 1 : }
193 1 : i.data.lazyValueHandling.hasValuePrefix = true
194 : }
195 1 : return nil
196 : }
197 :
198 0 : func (i *twoLevelIterator) String() string {
199 0 : if i.vState != nil {
200 0 : return i.vState.fileNum.String()
201 0 : }
202 0 : return i.reader.fileNum.String()
203 : }
204 :
205 : // MaybeFilteredKeys may be called when an iterator is exhausted to indicate
206 : // whether or not the last positioning method may have skipped any keys due to
207 : // block-property filters.
208 1 : func (i *twoLevelIterator) MaybeFilteredKeys() bool {
209 1 : // While reading sstables with two-level indexes, knowledge of whether we've
210 1 : // filtered keys is tracked separately for each index level. The
211 1 : // seek-using-next optimizations have different criteria. We can only reset
212 1 : // maybeFilteredKeys back to false during a seek when NOT using the
213 1 : // fast-path that uses the current iterator position.
214 1 : //
215 1 : // If either level might have filtered keys to arrive at the current
216 1 : // iterator position, return MaybeFilteredKeys=true.
217 1 : return i.maybeFilteredKeysTwoLevel || i.maybeFilteredKeysSingleLevel
218 1 : }
219 :
220 : // SeekGE implements internalIterator.SeekGE, as documented in the pebble
221 : // package. Note that SeekGE only checks the upper bound. It is up to the
222 : // caller to ensure that key is greater than or equal to the lower bound.
223 : func (i *twoLevelIterator) SeekGE(
224 : key []byte, flags base.SeekGEFlags,
225 1 : ) (*InternalKey, base.LazyValue) {
226 1 : if i.vState != nil {
227 1 : // Callers of SeekGE don't know about virtual sstable bounds, so we may
228 1 : // have to internally restrict the bounds.
229 1 : //
230 1 : // TODO(bananabrick): We can optimize away this check for the level iter
231 1 : // if necessary.
232 1 : if i.cmp(key, i.lower) < 0 {
233 1 : key = i.lower
234 1 : }
235 : }
236 :
237 1 : err := i.err
238 1 : i.err = nil // clear cached iteration error
239 1 :
240 1 : // The twoLevelIterator could be already exhausted. Utilize that when
241 1 : // trySeekUsingNext is true. See the comment about data-exhausted, PGDE, and
242 1 : // bounds-exhausted near the top of the file.
243 1 : if flags.TrySeekUsingNext() &&
244 1 : (i.exhaustedBounds == +1 || (i.data.isDataInvalidated() && i.index.isDataInvalidated())) &&
245 1 : err == nil {
246 1 : // Already exhausted, so return nil.
247 1 : return nil, base.LazyValue{}
248 1 : }
249 :
250 : // SeekGE performs various step-instead-of-seeking optimizations: eg enabled
251 : // by trySeekUsingNext, or by monotonically increasing bounds (i.boundsCmp).
252 : // Care must be taken to ensure that when performing these optimizations and
253 : // the iterator becomes exhausted, i.maybeFilteredKeys is set appropriately.
254 : // Consider a previous SeekGE that filtered keys from k until the current
255 : // iterator position.
256 : //
257 : // If the previous SeekGE exhausted the iterator while seeking within the
258 : // two-level index, it's possible keys greater than or equal to the current
259 : // search key were filtered through skipped index blocks. We must not reuse
260 : // the position of the two-level index iterator without remembering the
261 : // previous value of maybeFilteredKeys.
262 :
263 : // We fall into the slow path if i.index.isDataInvalidated() even if the
264 : // top-level iterator is already positioned correctly and all other
265 : // conditions are met. An alternative structure could reuse topLevelIndex's
266 : // current position and reload the index block to which it points. Arguably,
267 : // an index block load is expensive and the index block may still be earlier
268 : // than the index block containing the sought key, resulting in a wasteful
269 : // block load.
270 :
271 1 : var dontSeekWithinSingleLevelIter bool
272 1 : if i.topLevelIndex.isDataInvalidated() || !i.topLevelIndex.valid() || i.index.isDataInvalidated() || err != nil ||
273 1 : (i.boundsCmp <= 0 && !flags.TrySeekUsingNext()) || i.cmp(key, i.topLevelIndex.Key().UserKey) > 0 {
274 1 : // Slow-path: need to position the topLevelIndex.
275 1 :
276 1 : // The previous exhausted state of singleLevelIterator is no longer
277 1 : // relevant, since we may be moving to a different index block.
278 1 : i.exhaustedBounds = 0
279 1 : i.maybeFilteredKeysTwoLevel = false
280 1 : flags = flags.DisableTrySeekUsingNext()
281 1 : var ikey *InternalKey
282 1 : if ikey, _ = i.topLevelIndex.SeekGE(key, flags); ikey == nil {
283 1 : i.data.invalidate()
284 1 : i.index.invalidate()
285 1 : return nil, base.LazyValue{}
286 1 : }
287 :
288 1 : result := i.loadIndex(+1)
289 1 : if result == loadBlockFailed {
290 0 : i.boundsCmp = 0
291 0 : return nil, base.LazyValue{}
292 0 : }
293 1 : if result == loadBlockIrrelevant {
294 1 : // Enforce the upper bound here since don't want to bother moving
295 1 : // to the next entry in the top level index if upper bound is
296 1 : // already exceeded. Note that the next entry starts with keys >=
297 1 : // ikey.UserKey since even though this is the block separator, the
298 1 : // same user key can span multiple index blocks. If upper is
299 1 : // exclusive we use >= below, else we use >.
300 1 : if i.upper != nil {
301 1 : cmp := i.cmp(ikey.UserKey, i.upper)
302 1 : if (!i.endKeyInclusive && cmp >= 0) || cmp > 0 {
303 1 : i.exhaustedBounds = +1
304 1 : }
305 : }
306 : // Fall through to skipForward.
307 1 : dontSeekWithinSingleLevelIter = true
308 1 : // Clear boundsCmp.
309 1 : //
310 1 : // In the typical cases where dontSeekWithinSingleLevelIter=false,
311 1 : // the singleLevelIterator.SeekGE call will clear boundsCmp.
312 1 : // However, in this case where dontSeekWithinSingleLevelIter=true,
313 1 : // we never seek on the single-level iterator. This call will fall
314 1 : // through to skipForward, which may improperly leave boundsCmp=+1
315 1 : // unless we clear it here.
316 1 : i.boundsCmp = 0
317 : }
318 1 : } else {
319 1 : // INVARIANT: err == nil.
320 1 : //
321 1 : // Else fast-path: There are two possible cases, from
322 1 : // (i.boundsCmp > 0 || flags.TrySeekUsingNext()):
323 1 : //
324 1 : // 1) The bounds have moved forward (i.boundsCmp > 0) and this SeekGE is
325 1 : // respecting the lower bound (guaranteed by Iterator). We know that the
326 1 : // iterator must already be positioned within or just outside the previous
327 1 : // bounds. Therefore, the topLevelIndex iter cannot be positioned at an
328 1 : // entry ahead of the seek position (though it can be positioned behind).
329 1 : // The !i.cmp(key, i.topLevelIndex.Key().UserKey) > 0 confirms that it is
330 1 : // not behind. Since it is not ahead and not behind it must be at the
331 1 : // right position.
332 1 : //
333 1 : // 2) This SeekGE will land on a key that is greater than the key we are
334 1 : // currently at (guaranteed by trySeekUsingNext), but since i.cmp(key,
335 1 : // i.topLevelIndex.Key().UserKey) <= 0, we are at the correct lower level
336 1 : // index block. No need to reset the state of singleLevelIterator.
337 1 : //
338 1 : // Note that cases 1 and 2 never overlap, and one of them must be true,
339 1 : // but we have some test code (TestIterRandomizedMaybeFilteredKeys) that
340 1 : // sets both to true, so we fix things here and then do an invariant
341 1 : // check.
342 1 : //
343 1 : // This invariant checking is important enough that we do not gate it
344 1 : // behind invariants.Enabled.
345 1 : if i.boundsCmp > 0 {
346 1 : // TODO(sumeer): fix TestIterRandomizedMaybeFilteredKeys so as to not
347 1 : // need this behavior.
348 1 : flags = flags.DisableTrySeekUsingNext()
349 1 : }
350 1 : if i.boundsCmp > 0 == flags.TrySeekUsingNext() {
351 0 : panic(fmt.Sprintf("inconsistency in optimization case 1 %t and case 2 %t",
352 0 : i.boundsCmp > 0, flags.TrySeekUsingNext()))
353 : }
354 :
355 1 : if !flags.TrySeekUsingNext() {
356 1 : // Case 1. Bounds have changed so the previous exhausted bounds state is
357 1 : // irrelevant.
358 1 : // WARNING-data-exhausted: this is safe to do only because the monotonic
359 1 : // bounds optimizations only work when !data-exhausted. If they also
360 1 : // worked with data-exhausted, we have made it unclear whether
361 1 : // data-exhausted is actually true. See the comment at the top of the
362 1 : // file.
363 1 : i.exhaustedBounds = 0
364 1 : }
365 : // Else flags.TrySeekUsingNext(). The i.exhaustedBounds is important to
366 : // preserve for singleLevelIterator, and twoLevelIterator.skipForward. See
367 : // bug https://github.com/cockroachdb/pebble/issues/2036.
368 : }
369 :
370 1 : if !dontSeekWithinSingleLevelIter {
371 1 : // Note that while trySeekUsingNext could be false here, singleLevelIterator
372 1 : // could do its own boundsCmp-based optimization to seek using next.
373 1 : if ikey, val := i.singleLevelIterator.SeekGE(key, flags); ikey != nil {
374 1 : return ikey, val
375 1 : }
376 : }
377 1 : return i.skipForward()
378 : }
379 :
380 : // SeekPrefixGE implements internalIterator.SeekPrefixGE, as documented in the
381 : // pebble package. Note that SeekPrefixGE only checks the upper bound. It is up
382 : // to the caller to ensure that key is greater than or equal to the lower bound.
383 : func (i *twoLevelIterator) SeekPrefixGE(
384 : prefix, key []byte, flags base.SeekGEFlags,
385 1 : ) (*base.InternalKey, base.LazyValue) {
386 1 : if i.vState != nil {
387 1 : // Callers of SeekGE don't know about virtual sstable bounds, so we may
388 1 : // have to internally restrict the bounds.
389 1 : //
390 1 : // TODO(bananabrick): We can optimize away this check for the level iter
391 1 : // if necessary.
392 1 : if i.cmp(key, i.lower) < 0 {
393 1 : key = i.lower
394 1 : }
395 : }
396 :
397 : // NOTE: prefix is only used for bloom filter checking and not later work in
398 : // this method. Hence, we can use the existing iterator position if the last
399 : // SeekPrefixGE did not fail bloom filter matching.
400 :
401 1 : err := i.err
402 1 : i.err = nil // clear cached iteration error
403 1 :
404 1 : // The twoLevelIterator could be already exhausted. Utilize that when
405 1 : // trySeekUsingNext is true. See the comment about data-exhausted, PGDE, and
406 1 : // bounds-exhausted near the top of the file.
407 1 : filterUsedAndDidNotMatch :=
408 1 : i.reader.tableFilter != nil && i.useFilter && !i.lastBloomFilterMatched
409 1 : if flags.TrySeekUsingNext() && !filterUsedAndDidNotMatch &&
410 1 : (i.exhaustedBounds == +1 || (i.data.isDataInvalidated() && i.index.isDataInvalidated())) &&
411 1 : err == nil {
412 0 : // Already exhausted, so return nil.
413 0 : return nil, base.LazyValue{}
414 0 : }
415 :
416 : // Check prefix bloom filter.
417 1 : if i.reader.tableFilter != nil && i.useFilter {
418 1 : if !i.lastBloomFilterMatched {
419 1 : // Iterator is not positioned based on last seek.
420 1 : flags = flags.DisableTrySeekUsingNext()
421 1 : }
422 1 : i.lastBloomFilterMatched = false
423 1 : var dataH bufferHandle
424 1 : dataH, i.err = i.reader.readFilter(i.ctx, i.stats)
425 1 : if i.err != nil {
426 0 : i.data.invalidate()
427 0 : return nil, base.LazyValue{}
428 0 : }
429 1 : mayContain := i.reader.tableFilter.mayContain(dataH.Get(), prefix)
430 1 : dataH.Release()
431 1 : if !mayContain {
432 1 : // This invalidation may not be necessary for correctness, and may
433 1 : // be a place to optimize later by reusing the already loaded
434 1 : // block. It was necessary in earlier versions of the code since
435 1 : // the caller was allowed to call Next when SeekPrefixGE returned
436 1 : // nil. This is no longer allowed.
437 1 : i.data.invalidate()
438 1 : return nil, base.LazyValue{}
439 1 : }
440 1 : i.lastBloomFilterMatched = true
441 : }
442 :
443 : // Bloom filter matches.
444 :
445 : // SeekPrefixGE performs various step-instead-of-seeking optimizations: eg
446 : // enabled by trySeekUsingNext, or by monotonically increasing bounds
447 : // (i.boundsCmp). Care must be taken to ensure that when performing these
448 : // optimizations and the iterator becomes exhausted,
449 : // i.maybeFilteredKeysTwoLevel is set appropriately. Consider a previous
450 : // SeekPrefixGE that filtered keys from k until the current iterator
451 : // position.
452 : //
453 : // If the previous SeekPrefixGE exhausted the iterator while seeking within
454 : // the two-level index, it's possible keys greater than or equal to the
455 : // current search key were filtered through skipped index blocks. We must
456 : // not reuse the position of the two-level index iterator without
457 : // remembering the previous value of maybeFilteredKeysTwoLevel.
458 :
459 : // We fall into the slow path if i.index.isDataInvalidated() even if the
460 : // top-level iterator is already positioned correctly and all other
461 : // conditions are met. An alternative structure could reuse topLevelIndex's
462 : // current position and reload the index block to which it points. Arguably,
463 : // an index block load is expensive and the index block may still be earlier
464 : // than the index block containing the sought key, resulting in a wasteful
465 : // block load.
466 :
467 1 : var dontSeekWithinSingleLevelIter bool
468 1 : if i.topLevelIndex.isDataInvalidated() || !i.topLevelIndex.valid() || i.index.isDataInvalidated() || err != nil ||
469 1 : (i.boundsCmp <= 0 && !flags.TrySeekUsingNext()) || i.cmp(key, i.topLevelIndex.Key().UserKey) > 0 {
470 1 : // Slow-path: need to position the topLevelIndex.
471 1 :
472 1 : // The previous exhausted state of singleLevelIterator is no longer
473 1 : // relevant, since we may be moving to a different index block.
474 1 : i.exhaustedBounds = 0
475 1 : i.maybeFilteredKeysTwoLevel = false
476 1 : flags = flags.DisableTrySeekUsingNext()
477 1 : var ikey *InternalKey
478 1 : if ikey, _ = i.topLevelIndex.SeekGE(key, flags); ikey == nil {
479 1 : i.data.invalidate()
480 1 : i.index.invalidate()
481 1 : return nil, base.LazyValue{}
482 1 : }
483 :
484 1 : result := i.loadIndex(+1)
485 1 : if result == loadBlockFailed {
486 0 : i.boundsCmp = 0
487 0 : return nil, base.LazyValue{}
488 0 : }
489 1 : if result == loadBlockIrrelevant {
490 1 : // Enforce the upper bound here since don't want to bother moving
491 1 : // to the next entry in the top level index if upper bound is
492 1 : // already exceeded. Note that the next entry starts with keys >=
493 1 : // ikey.UserKey since even though this is the block separator, the
494 1 : // same user key can span multiple index blocks. If upper is
495 1 : // exclusive we use >= below, else we use >.
496 1 : if i.upper != nil {
497 1 : cmp := i.cmp(ikey.UserKey, i.upper)
498 1 : if (!i.endKeyInclusive && cmp >= 0) || cmp > 0 {
499 1 : i.exhaustedBounds = +1
500 1 : }
501 : }
502 : // Fall through to skipForward.
503 1 : dontSeekWithinSingleLevelIter = true
504 1 : // Clear boundsCmp.
505 1 : //
506 1 : // In the typical cases where dontSeekWithinSingleLevelIter=false,
507 1 : // the singleLevelIterator.SeekPrefixGE call will clear boundsCmp.
508 1 : // However, in this case where dontSeekWithinSingleLevelIter=true,
509 1 : // we never seek on the single-level iterator. This call will fall
510 1 : // through to skipForward, which may improperly leave boundsCmp=+1
511 1 : // unless we clear it here.
512 1 : i.boundsCmp = 0
513 : }
514 1 : } else {
515 1 : // INVARIANT: err == nil.
516 1 : //
517 1 : // Else fast-path: There are two possible cases, from
518 1 : // (i.boundsCmp > 0 || flags.TrySeekUsingNext()):
519 1 : //
520 1 : // 1) The bounds have moved forward (i.boundsCmp > 0) and this
521 1 : // SeekPrefixGE is respecting the lower bound (guaranteed by Iterator). We
522 1 : // know that the iterator must already be positioned within or just
523 1 : // outside the previous bounds. Therefore, the topLevelIndex iter cannot
524 1 : // be positioned at an entry ahead of the seek position (though it can be
525 1 : // positioned behind). The !i.cmp(key, i.topLevelIndex.Key().UserKey) > 0
526 1 : // confirms that it is not behind. Since it is not ahead and not behind it
527 1 : // must be at the right position.
528 1 : //
529 1 : // 2) This SeekPrefixGE will land on a key that is greater than the key we
530 1 : // are currently at (guaranteed by trySeekUsingNext), but since i.cmp(key,
531 1 : // i.topLevelIndex.Key().UserKey) <= 0, we are at the correct lower level
532 1 : // index block. No need to reset the state of singleLevelIterator.
533 1 : //
534 1 : // Note that cases 1 and 2 never overlap, and one of them must be true.
535 1 : // This invariant checking is important enough that we do not gate it
536 1 : // behind invariants.Enabled.
537 1 : if i.boundsCmp > 0 == flags.TrySeekUsingNext() {
538 0 : panic(fmt.Sprintf("inconsistency in optimization case 1 %t and case 2 %t",
539 0 : i.boundsCmp > 0, flags.TrySeekUsingNext()))
540 : }
541 :
542 1 : if !flags.TrySeekUsingNext() {
543 0 : // Case 1. Bounds have changed so the previous exhausted bounds state is
544 0 : // irrelevant.
545 0 : // WARNING-data-exhausted: this is safe to do only because the monotonic
546 0 : // bounds optimizations only work when !data-exhausted. If they also
547 0 : // worked with data-exhausted, we have made it unclear whether
548 0 : // data-exhausted is actually true. See the comment at the top of the
549 0 : // file.
550 0 : i.exhaustedBounds = 0
551 0 : }
552 : // Else flags.TrySeekUsingNext(). The i.exhaustedBounds is important to
553 : // preserve for singleLevelIterator, and twoLevelIterator.skipForward. See
554 : // bug https://github.com/cockroachdb/pebble/issues/2036.
555 : }
556 :
557 1 : if !dontSeekWithinSingleLevelIter {
558 1 : if ikey, val := i.singleLevelIterator.seekPrefixGE(
559 1 : prefix, key, flags, false /* checkFilter */); ikey != nil {
560 1 : return ikey, val
561 1 : }
562 : }
563 : // NB: skipForward checks whether exhaustedBounds is already +1.
564 1 : return i.skipForward()
565 : }
566 :
567 : // virtualLast should only be called if i.vReader != nil and i.endKeyInclusive
568 : // is true.
569 1 : func (i *twoLevelIterator) virtualLast() (*InternalKey, base.LazyValue) {
570 1 : if i.vState == nil {
571 0 : panic("pebble: invalid call to virtualLast")
572 : }
573 :
574 : // Seek to the first internal key.
575 1 : ikey, _ := i.SeekGE(i.upper, base.SeekGEFlagsNone)
576 1 : if i.endKeyInclusive {
577 1 : // Let's say the virtual sstable upper bound is c#1, with the keys c#3, c#2,
578 1 : // c#1, d, e, ... in the sstable. So, the last key in the virtual sstable is
579 1 : // c#1. We can perform SeekGE(i.upper) and then keep nexting until we find
580 1 : // the last key with userkey == i.upper.
581 1 : //
582 1 : // TODO(bananabrick): Think about how to improve this. If many internal keys
583 1 : // with the same user key at the upper bound then this could be slow, but
584 1 : // maybe the odds of having many internal keys with the same user key at the
585 1 : // upper bound are low.
586 1 : for ikey != nil && i.cmp(ikey.UserKey, i.upper) == 0 {
587 1 : ikey, _ = i.Next()
588 1 : }
589 1 : return i.Prev()
590 : }
591 : // We seeked to the first key >= i.upper.
592 1 : return i.Prev()
593 : }
594 :
595 : // SeekLT implements internalIterator.SeekLT, as documented in the pebble
596 : // package. Note that SeekLT only checks the lower bound. It is up to the
597 : // caller to ensure that key is less than the upper bound.
598 : func (i *twoLevelIterator) SeekLT(
599 : key []byte, flags base.SeekLTFlags,
600 1 : ) (*InternalKey, base.LazyValue) {
601 1 : if i.vState != nil {
602 1 : // Might have to fix upper bound since virtual sstable bounds are not
603 1 : // known to callers of SeekLT.
604 1 : //
605 1 : // TODO(bananabrick): We can optimize away this check for the level iter
606 1 : // if necessary.
607 1 : cmp := i.cmp(key, i.upper)
608 1 : // key == i.upper is fine. We'll do the right thing and return the
609 1 : // first internal key with user key < key.
610 1 : if cmp > 0 {
611 1 : return i.virtualLast()
612 1 : }
613 : }
614 :
615 1 : i.exhaustedBounds = 0
616 1 : i.err = nil // clear cached iteration error
617 1 : // Seek optimization only applies until iterator is first positioned after SetBounds.
618 1 : i.boundsCmp = 0
619 1 :
620 1 : var result loadBlockResult
621 1 : var ikey *InternalKey
622 1 : // NB: Unlike SeekGE, we don't have a fast-path here since we don't know
623 1 : // whether the topLevelIndex is positioned after the position that would
624 1 : // be returned by doing i.topLevelIndex.SeekGE(). To know this we would
625 1 : // need to know the index key preceding the current one.
626 1 : // NB: If a bound-limited block property filter is configured, it's
627 1 : // externally ensured that the filter is disabled (through returning
628 1 : // Intersects=false irrespective of the block props provided) during seeks.
629 1 : i.maybeFilteredKeysTwoLevel = false
630 1 : if ikey, _ = i.topLevelIndex.SeekGE(key, base.SeekGEFlagsNone); ikey == nil {
631 1 : if ikey, _ = i.topLevelIndex.Last(); ikey == nil {
632 0 : i.data.invalidate()
633 0 : i.index.invalidate()
634 0 : return nil, base.LazyValue{}
635 0 : }
636 :
637 1 : result = i.loadIndex(-1)
638 1 : if result == loadBlockFailed {
639 0 : return nil, base.LazyValue{}
640 0 : }
641 1 : if result == loadBlockOK {
642 1 : if ikey, val := i.singleLevelIterator.lastInternal(); ikey != nil {
643 1 : return i.maybeVerifyKey(ikey, val)
644 1 : }
645 : // Fall through to skipBackward since the singleLevelIterator did
646 : // not have any blocks that satisfy the block interval
647 : // constraints, or the lower bound was reached.
648 : }
649 : // Else loadBlockIrrelevant, so fall through.
650 1 : } else {
651 1 : result = i.loadIndex(-1)
652 1 : if result == loadBlockFailed {
653 0 : return nil, base.LazyValue{}
654 0 : }
655 1 : if result == loadBlockOK {
656 1 : if ikey, val := i.singleLevelIterator.SeekLT(key, flags); ikey != nil {
657 1 : return i.maybeVerifyKey(ikey, val)
658 1 : }
659 : // Fall through to skipBackward since the singleLevelIterator did
660 : // not have any blocks that satisfy the block interval
661 : // constraint, or the lower bound was reached.
662 : }
663 : // Else loadBlockIrrelevant, so fall through.
664 : }
665 1 : if result == loadBlockIrrelevant {
666 1 : // Enforce the lower bound here since don't want to bother moving to
667 1 : // the previous entry in the top level index if lower bound is already
668 1 : // exceeded. Note that the previous entry starts with keys <=
669 1 : // ikey.UserKey since even though this is the current block's
670 1 : // separator, the same user key can span multiple index blocks.
671 1 : if i.lower != nil && i.cmp(ikey.UserKey, i.lower) < 0 {
672 0 : i.exhaustedBounds = -1
673 0 : }
674 : }
675 : // NB: skipBackward checks whether exhaustedBounds is already -1.
676 1 : return i.skipBackward()
677 : }
678 :
679 : // First implements internalIterator.First, as documented in the pebble
680 : // package. Note that First only checks the upper bound. It is up to the caller
681 : // to ensure that key is greater than or equal to the lower bound (e.g. via a
682 : // call to SeekGE(lower)).
683 1 : func (i *twoLevelIterator) First() (*InternalKey, base.LazyValue) {
684 1 : // If the iterator was created on a virtual sstable, we will SeekGE to the
685 1 : // lower bound instead of using First, because First does not respect
686 1 : // bounds.
687 1 : if i.vState != nil {
688 1 : return i.SeekGE(i.lower, base.SeekGEFlagsNone)
689 1 : }
690 :
691 1 : if i.lower != nil {
692 0 : panic("twoLevelIterator.First() used despite lower bound")
693 : }
694 1 : i.exhaustedBounds = 0
695 1 : i.maybeFilteredKeysTwoLevel = false
696 1 : i.err = nil // clear cached iteration error
697 1 : // Seek optimization only applies until iterator is first positioned after SetBounds.
698 1 : i.boundsCmp = 0
699 1 :
700 1 : var ikey *InternalKey
701 1 : if ikey, _ = i.topLevelIndex.First(); ikey == nil {
702 0 : return nil, base.LazyValue{}
703 0 : }
704 :
705 1 : result := i.loadIndex(+1)
706 1 : if result == loadBlockFailed {
707 1 : return nil, base.LazyValue{}
708 1 : }
709 1 : if result == loadBlockOK {
710 1 : if ikey, val := i.singleLevelIterator.First(); ikey != nil {
711 1 : return ikey, val
712 1 : }
713 : // Else fall through to skipForward.
714 1 : } else {
715 1 : // result == loadBlockIrrelevant. Enforce the upper bound here since
716 1 : // don't want to bother moving to the next entry in the top level
717 1 : // index if upper bound is already exceeded. Note that the next entry
718 1 : // starts with keys >= ikey.UserKey since even though this is the
719 1 : // block separator, the same user key can span multiple index blocks.
720 1 : // If upper is exclusive we use >= below, else we use >.
721 1 : if i.upper != nil {
722 0 : cmp := i.cmp(ikey.UserKey, i.upper)
723 0 : if (!i.endKeyInclusive && cmp >= 0) || cmp > 0 {
724 0 : i.exhaustedBounds = +1
725 0 : }
726 : }
727 : }
728 : // NB: skipForward checks whether exhaustedBounds is already +1.
729 1 : return i.skipForward()
730 : }
731 :
732 : // Last implements internalIterator.Last, as documented in the pebble
733 : // package. Note that Last only checks the lower bound. It is up to the caller
734 : // to ensure that key is less than the upper bound (e.g. via a call to
735 : // SeekLT(upper))
736 1 : func (i *twoLevelIterator) Last() (*InternalKey, base.LazyValue) {
737 1 : if i.vState != nil {
738 1 : if i.endKeyInclusive {
739 1 : return i.virtualLast()
740 1 : }
741 1 : return i.SeekLT(i.upper, base.SeekLTFlagsNone)
742 : }
743 :
744 1 : if i.upper != nil {
745 0 : panic("twoLevelIterator.Last() used despite upper bound")
746 : }
747 1 : i.exhaustedBounds = 0
748 1 : i.maybeFilteredKeysTwoLevel = false
749 1 : i.err = nil // clear cached iteration error
750 1 : // Seek optimization only applies until iterator is first positioned after SetBounds.
751 1 : i.boundsCmp = 0
752 1 :
753 1 : var ikey *InternalKey
754 1 : if ikey, _ = i.topLevelIndex.Last(); ikey == nil {
755 0 : return nil, base.LazyValue{}
756 0 : }
757 :
758 1 : result := i.loadIndex(-1)
759 1 : if result == loadBlockFailed {
760 0 : return nil, base.LazyValue{}
761 0 : }
762 1 : if result == loadBlockOK {
763 1 : if ikey, val := i.singleLevelIterator.Last(); ikey != nil {
764 1 : return ikey, val
765 1 : }
766 : // Else fall through to skipBackward.
767 1 : } else {
768 1 : // result == loadBlockIrrelevant. Enforce the lower bound here
769 1 : // since don't want to bother moving to the previous entry in the
770 1 : // top level index if lower bound is already exceeded. Note that
771 1 : // the previous entry starts with keys <= ikey.UserKey since even
772 1 : // though this is the current block's separator, the same user key
773 1 : // can span multiple index blocks.
774 1 : if i.lower != nil && i.cmp(ikey.UserKey, i.lower) < 0 {
775 0 : i.exhaustedBounds = -1
776 0 : }
777 : }
778 : // NB: skipBackward checks whether exhaustedBounds is already -1.
779 1 : return i.skipBackward()
780 : }
781 :
782 : // Next implements internalIterator.Next, as documented in the pebble
783 : // package.
784 : // Note: twoLevelCompactionIterator.Next mirrors the implementation of
785 : // twoLevelIterator.Next due to performance. Keep the two in sync.
786 1 : func (i *twoLevelIterator) Next() (*InternalKey, base.LazyValue) {
787 1 : // Seek optimization only applies until iterator is first positioned after SetBounds.
788 1 : i.boundsCmp = 0
789 1 : i.maybeFilteredKeysTwoLevel = false
790 1 : if i.err != nil {
791 0 : return nil, base.LazyValue{}
792 0 : }
793 1 : if key, val := i.singleLevelIterator.Next(); key != nil {
794 1 : return key, val
795 1 : }
796 1 : return i.skipForward()
797 : }
798 :
799 : // NextPrefix implements (base.InternalIterator).NextPrefix.
800 1 : func (i *twoLevelIterator) NextPrefix(succKey []byte) (*InternalKey, base.LazyValue) {
801 1 : if i.exhaustedBounds == +1 {
802 0 : panic("Next called even though exhausted upper bound")
803 : }
804 : // Seek optimization only applies until iterator is first positioned after SetBounds.
805 1 : i.boundsCmp = 0
806 1 : i.maybeFilteredKeysTwoLevel = false
807 1 : if i.err != nil {
808 0 : return nil, base.LazyValue{}
809 0 : }
810 1 : if key, val := i.singleLevelIterator.NextPrefix(succKey); key != nil {
811 1 : return key, val
812 1 : }
813 : // Did not find prefix in the existing second-level index block. This is the
814 : // slow-path where we seek the iterator.
815 1 : var ikey *InternalKey
816 1 : if ikey, _ = i.topLevelIndex.SeekGE(succKey, base.SeekGEFlagsNone); ikey == nil {
817 0 : i.data.invalidate()
818 0 : i.index.invalidate()
819 0 : return nil, base.LazyValue{}
820 0 : }
821 1 : result := i.loadIndex(+1)
822 1 : if result == loadBlockFailed {
823 0 : return nil, base.LazyValue{}
824 0 : }
825 1 : if result == loadBlockIrrelevant {
826 0 : // Enforce the upper bound here since don't want to bother moving to the
827 0 : // next entry in the top level index if upper bound is already exceeded.
828 0 : // Note that the next entry starts with keys >= ikey.UserKey since even
829 0 : // though this is the block separator, the same user key can span multiple
830 0 : // index blocks. If upper is exclusive we use >= below, else we use >.
831 0 : if i.upper != nil {
832 0 : cmp := i.cmp(ikey.UserKey, i.upper)
833 0 : if (!i.endKeyInclusive && cmp >= 0) || cmp > 0 {
834 0 : i.exhaustedBounds = +1
835 0 : }
836 : }
837 1 : } else if key, val := i.singleLevelIterator.SeekGE(succKey, base.SeekGEFlagsNone); key != nil {
838 1 : return i.maybeVerifyKey(key, val)
839 1 : }
840 1 : return i.skipForward()
841 : }
842 :
843 : // Prev implements internalIterator.Prev, as documented in the pebble
844 : // package.
845 1 : func (i *twoLevelIterator) Prev() (*InternalKey, base.LazyValue) {
846 1 : // Seek optimization only applies until iterator is first positioned after SetBounds.
847 1 : i.boundsCmp = 0
848 1 : i.maybeFilteredKeysTwoLevel = false
849 1 : if i.err != nil {
850 0 : return nil, base.LazyValue{}
851 0 : }
852 1 : if key, val := i.singleLevelIterator.Prev(); key != nil {
853 1 : return key, val
854 1 : }
855 1 : return i.skipBackward()
856 : }
857 :
858 1 : func (i *twoLevelIterator) skipForward() (*InternalKey, base.LazyValue) {
859 1 : for {
860 1 : if i.err != nil || i.exhaustedBounds > 0 {
861 1 : return nil, base.LazyValue{}
862 1 : }
863 1 : i.exhaustedBounds = 0
864 1 : var ikey *InternalKey
865 1 : if ikey, _ = i.topLevelIndex.Next(); ikey == nil {
866 1 : i.data.invalidate()
867 1 : i.index.invalidate()
868 1 : return nil, base.LazyValue{}
869 1 : }
870 1 : result := i.loadIndex(+1)
871 1 : if result == loadBlockFailed {
872 1 : return nil, base.LazyValue{}
873 1 : }
874 1 : if result == loadBlockOK {
875 1 : if ikey, val := i.singleLevelIterator.firstInternal(); ikey != nil {
876 1 : return i.maybeVerifyKey(ikey, val)
877 1 : }
878 : // Next iteration will return if singleLevelIterator set
879 : // exhaustedBounds = +1.
880 1 : } else {
881 1 : // result == loadBlockIrrelevant. Enforce the upper bound here
882 1 : // since don't want to bother moving to the next entry in the top
883 1 : // level index if upper bound is already exceeded. Note that the
884 1 : // next entry starts with keys >= ikey.UserKey since even though
885 1 : // this is the block separator, the same user key can span
886 1 : // multiple index blocks. If upper is exclusive we use >=
887 1 : // below, else we use >.
888 1 : if i.upper != nil {
889 1 : cmp := i.cmp(ikey.UserKey, i.upper)
890 1 : if (!i.endKeyInclusive && cmp >= 0) || cmp > 0 {
891 1 : i.exhaustedBounds = +1
892 1 : // Next iteration will return.
893 1 : }
894 : }
895 : }
896 : }
897 : }
898 :
899 1 : func (i *twoLevelIterator) skipBackward() (*InternalKey, base.LazyValue) {
900 1 : for {
901 1 : if i.err != nil || i.exhaustedBounds < 0 {
902 1 : return nil, base.LazyValue{}
903 1 : }
904 1 : i.exhaustedBounds = 0
905 1 : var ikey *InternalKey
906 1 : if ikey, _ = i.topLevelIndex.Prev(); ikey == nil {
907 1 : i.data.invalidate()
908 1 : i.index.invalidate()
909 1 : return nil, base.LazyValue{}
910 1 : }
911 1 : result := i.loadIndex(-1)
912 1 : if result == loadBlockFailed {
913 0 : return nil, base.LazyValue{}
914 0 : }
915 1 : if result == loadBlockOK {
916 1 : if ikey, val := i.singleLevelIterator.lastInternal(); ikey != nil {
917 1 : return i.maybeVerifyKey(ikey, val)
918 1 : }
919 : // Next iteration will return if singleLevelIterator set
920 : // exhaustedBounds = -1.
921 1 : } else {
922 1 : // result == loadBlockIrrelevant. Enforce the lower bound here
923 1 : // since don't want to bother moving to the previous entry in the
924 1 : // top level index if lower bound is already exceeded. Note that
925 1 : // the previous entry starts with keys <= ikey.UserKey since even
926 1 : // though this is the current block's separator, the same user key
927 1 : // can span multiple index blocks.
928 1 : if i.lower != nil && i.cmp(ikey.UserKey, i.lower) < 0 {
929 0 : i.exhaustedBounds = -1
930 0 : // Next iteration will return.
931 0 : }
932 : }
933 : }
934 : }
935 :
936 : // Close implements internalIterator.Close, as documented in the pebble
937 : // package.
938 1 : func (i *twoLevelIterator) Close() error {
939 1 : var err error
940 1 : if i.closeHook != nil {
941 1 : err = firstError(err, i.closeHook(i))
942 1 : }
943 1 : err = firstError(err, i.data.Close())
944 1 : err = firstError(err, i.index.Close())
945 1 : err = firstError(err, i.topLevelIndex.Close())
946 1 : if i.dataRH != nil {
947 1 : err = firstError(err, i.dataRH.Close())
948 1 : i.dataRH = nil
949 1 : }
950 1 : err = firstError(err, i.err)
951 1 : if i.bpfs != nil {
952 1 : releaseBlockPropertiesFilterer(i.bpfs)
953 1 : }
954 1 : if i.vbReader != nil {
955 1 : i.vbReader.close()
956 1 : }
957 1 : if i.vbRH != nil {
958 1 : err = firstError(err, i.vbRH.Close())
959 1 : i.vbRH = nil
960 1 : }
961 1 : *i = twoLevelIterator{
962 1 : singleLevelIterator: i.singleLevelIterator.resetForReuse(),
963 1 : topLevelIndex: i.topLevelIndex.resetForReuse(),
964 1 : }
965 1 : twoLevelIterPool.Put(i)
966 1 : return err
967 : }
968 :
969 : // Note: twoLevelCompactionIterator and compactionIterator are very similar but
970 : // were separated due to performance.
971 : type twoLevelCompactionIterator struct {
972 : *twoLevelIterator
973 : bytesIterated *uint64
974 : prevOffset uint64
975 : }
976 :
977 : // twoLevelCompactionIterator implements the base.InternalIterator interface.
978 : var _ base.InternalIterator = (*twoLevelCompactionIterator)(nil)
979 :
980 1 : func (i *twoLevelCompactionIterator) Close() error {
981 1 : return i.twoLevelIterator.Close()
982 1 : }
983 :
984 : func (i *twoLevelCompactionIterator) SeekGE(
985 : key []byte, flags base.SeekGEFlags,
986 0 : ) (*InternalKey, base.LazyValue) {
987 0 : panic("pebble: SeekGE unimplemented")
988 : }
989 :
990 : func (i *twoLevelCompactionIterator) SeekPrefixGE(
991 : prefix, key []byte, flags base.SeekGEFlags,
992 0 : ) (*base.InternalKey, base.LazyValue) {
993 0 : panic("pebble: SeekPrefixGE unimplemented")
994 : }
995 :
996 : func (i *twoLevelCompactionIterator) SeekLT(
997 : key []byte, flags base.SeekLTFlags,
998 0 : ) (*InternalKey, base.LazyValue) {
999 0 : panic("pebble: SeekLT unimplemented")
1000 : }
1001 :
1002 1 : func (i *twoLevelCompactionIterator) First() (*InternalKey, base.LazyValue) {
1003 1 : i.err = nil // clear cached iteration error
1004 1 : return i.skipForward(i.twoLevelIterator.First())
1005 1 : }
1006 :
1007 0 : func (i *twoLevelCompactionIterator) Last() (*InternalKey, base.LazyValue) {
1008 0 : panic("pebble: Last unimplemented")
1009 : }
1010 :
1011 : // Note: twoLevelCompactionIterator.Next mirrors the implementation of
1012 : // twoLevelIterator.Next due to performance. Keep the two in sync.
1013 1 : func (i *twoLevelCompactionIterator) Next() (*InternalKey, base.LazyValue) {
1014 1 : if i.err != nil {
1015 0 : return nil, base.LazyValue{}
1016 0 : }
1017 1 : return i.skipForward(i.singleLevelIterator.Next())
1018 : }
1019 :
1020 0 : func (i *twoLevelCompactionIterator) NextPrefix(succKey []byte) (*InternalKey, base.LazyValue) {
1021 0 : panic("pebble: NextPrefix unimplemented")
1022 : }
1023 :
1024 0 : func (i *twoLevelCompactionIterator) Prev() (*InternalKey, base.LazyValue) {
1025 0 : panic("pebble: Prev unimplemented")
1026 : }
1027 :
1028 0 : func (i *twoLevelCompactionIterator) String() string {
1029 0 : if i.vState != nil {
1030 0 : return i.vState.fileNum.String()
1031 0 : }
1032 0 : return i.reader.fileNum.String()
1033 : }
1034 :
1035 : func (i *twoLevelCompactionIterator) skipForward(
1036 : key *InternalKey, val base.LazyValue,
1037 1 : ) (*InternalKey, base.LazyValue) {
1038 1 : if key == nil {
1039 1 : for {
1040 1 : if key, _ := i.topLevelIndex.Next(); key == nil {
1041 1 : break
1042 : }
1043 1 : result := i.loadIndex(+1)
1044 1 : if result != loadBlockOK {
1045 0 : if i.err != nil {
1046 0 : break
1047 : }
1048 0 : switch result {
1049 0 : case loadBlockFailed:
1050 0 : // We checked that i.index was at a valid entry, so
1051 0 : // loadBlockFailed could not have happened due to to i.index
1052 0 : // being exhausted, and must be due to an error.
1053 0 : panic("loadBlock should not have failed with no error")
1054 0 : case loadBlockIrrelevant:
1055 0 : panic("compactionIter should not be using block intervals for skipping")
1056 0 : default:
1057 0 : panic(fmt.Sprintf("unexpected case %d", result))
1058 : }
1059 : }
1060 : // result == loadBlockOK
1061 1 : if key, val = i.singleLevelIterator.First(); key != nil {
1062 1 : break
1063 : }
1064 : }
1065 : }
1066 :
1067 1 : curOffset := i.recordOffset()
1068 1 : *i.bytesIterated += uint64(curOffset - i.prevOffset)
1069 1 : i.prevOffset = curOffset
1070 1 :
1071 1 : if i.vState != nil && key != nil {
1072 1 : cmp := i.cmp(key.UserKey, i.vState.upper.UserKey)
1073 1 : if cmp > 0 || (i.vState.upper.IsExclusiveSentinel() && cmp == 0) {
1074 0 : return nil, base.LazyValue{}
1075 0 : }
1076 : }
1077 :
1078 1 : return key, val
1079 : }
|
