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