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