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