LCOV - code coverage report
Current view: top level - pebble - level_iter.go (source / functions) Coverage Total Hit
Test: 2025-08-07 08:18Z 436c169a - meta test only.lcov Lines: 91.4 % 604 552
Test Date: 2025-08-07 08:19:55 Functions: - 0 0

            Line data    Source code
       1              : // Copyright 2018 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 pebble
       6              : 
       7              : import (
       8              :         "context"
       9              :         "fmt"
      10              :         "runtime/debug"
      11              : 
      12              :         "github.com/cockroachdb/errors"
      13              :         "github.com/cockroachdb/pebble/internal/base"
      14              :         "github.com/cockroachdb/pebble/internal/invariants"
      15              :         "github.com/cockroachdb/pebble/internal/keyspan"
      16              :         "github.com/cockroachdb/pebble/internal/manifest"
      17              :         "github.com/cockroachdb/pebble/internal/treeprinter"
      18              : )
      19              : 
      20              : // levelIter provides a merged view of the sstables in a level.
      21              : //
      22              : // levelIter is used during compaction and as part of the Iterator
      23              : // implementation. When used as part of the Iterator implementation, level
      24              : // iteration needs to "pause" at range deletion boundaries if file contains
      25              : // range deletions. In this case, the levelIter uses a keyspan.InterleavingIter
      26              : // to materialize InternalKVs at start and end boundaries of range deletions.
      27              : // This prevents mergingIter from advancing past the sstable until the sstable
      28              : // contains the smallest (or largest for reverse iteration) key in the merged
      29              : // heap. Note that mergingIter treats a range deletion tombstone returned by the
      30              : // point iterator as a no-op.
      31              : type levelIter struct {
      32              :         // The context is stored here since (a) iterators are expected to be
      33              :         // short-lived (since they pin sstables), (b) plumbing a context into every
      34              :         // method is very painful, (c) they do not (yet) respect context
      35              :         // cancellation and are only used for tracing.
      36              :         ctx      context.Context
      37              :         logger   Logger
      38              :         comparer *Comparer
      39              :         cmp      Compare
      40              :         split    Split
      41              :         // The lower/upper bounds for iteration as specified at creation or the most
      42              :         // recent call to SetBounds.
      43              :         lower []byte
      44              :         upper []byte
      45              :         // prefix holds the iteration prefix when the most recent absolute
      46              :         // positioning method was a SeekPrefixGE.
      47              :         prefix []byte
      48              :         // The iterator options for the currently open table. If
      49              :         // tableOpts.{Lower,Upper}Bound are nil, the corresponding iteration boundary
      50              :         // does not lie within the table bounds.
      51              :         tableOpts IterOptions
      52              :         // The layer this levelIter is initialized for. This can be either
      53              :         // a level L1+, an L0 sublevel, or a flushable ingests layer.
      54              :         layer manifest.Layer
      55              :         // combinedIterState may be set when a levelIter is used during user
      56              :         // iteration. Although levelIter only iterates over point keys, it's also
      57              :         // responsible for lazily constructing the combined range & point iterator
      58              :         // when it observes a file containing range keys. If the combined iter
      59              :         // state's initialized field is true, the iterator is already using combined
      60              :         // iterator, OR the iterator is not configured to use combined iteration. If
      61              :         // it's false, the levelIter must set the `triggered` and `key` fields when
      62              :         // the levelIter passes over a file containing range keys. See the
      63              :         // lazyCombinedIter for more details.
      64              :         combinedIterState *combinedIterState
      65              :         // The iter for the current file. It is nil under any of the following conditions:
      66              :         // - files.Current() == nil
      67              :         // - err != nil
      68              :         // - some other constraint, like the bounds in opts, caused the file at index to not
      69              :         //   be relevant to the iteration.
      70              :         iter internalIterator
      71              :         // iterFile holds the current file. It is always equal to l.files.Current().
      72              :         iterFile *manifest.TableMetadata
      73              :         newIters tableNewIters
      74              :         files    manifest.LevelIterator
      75              :         err      error
      76              : 
      77              :         // When rangeDelIterSetter != nil, the caller requires that this function
      78              :         // gets called with a range deletion iterator whenever the current file
      79              :         // changes.  The iterator is relinquished to the caller which is responsible
      80              :         // for closing it.
      81              :         //
      82              :         // When rangeDelIterSetter != nil, the levelIter will also interleave the
      83              :         // boundaries of range deletions among point keys.
      84              :         rangeDelIterSetter rangeDelIterSetter
      85              : 
      86              :         // interleaving is used when rangeDelIterFn != nil to interleave the
      87              :         // boundaries of range deletions among point keys. When the leve iterator is
      88              :         // used by a merging iterator, this ensures that we don't advance to a new
      89              :         // file until the range deletions are no longer needed by other levels.
      90              :         interleaving keyspan.InterleavingIter
      91              : 
      92              :         // internalOpts holds the internal iterator options to pass to the table
      93              :         // cache when constructing new table iterators.
      94              :         internalOpts internalIterOpts
      95              : 
      96              :         // Scratch space for the obsolete keys filter, when there are no other block
      97              :         // property filters specified. See the performance note where
      98              :         // IterOptions.PointKeyFilters is declared.
      99              :         filtersBuf [1]BlockPropertyFilter
     100              : 
     101              :         // exhaustedDir is set to +1 or -1 when the levelIter has been exhausted in
     102              :         // the forward or backward direction respectively. It is set when the
     103              :         // underlying data is exhausted or when iteration has reached the upper or
     104              :         // lower boundary and interleaved a synthetic iterator bound key. When the
     105              :         // iterator is exhausted and Next or Prev is called, the levelIter uses
     106              :         // exhaustedDir to determine whether the iterator should step on to the
     107              :         // first or last key within iteration bounds.
     108              :         exhaustedDir int8
     109              : 
     110              :         // Disable invariant checks even if they are otherwise enabled. Used by tests
     111              :         // which construct "impossible" situations (e.g. seeking to a key before the
     112              :         // lower bound).
     113              :         disableInvariants bool
     114              : }
     115              : 
     116              : type rangeDelIterSetter interface {
     117              :         setRangeDelIter(rangeDelIter keyspan.FragmentIterator)
     118              : }
     119              : 
     120              : // levelIter implements the base.InternalIterator interface.
     121              : var _ base.InternalIterator = (*levelIter)(nil)
     122              : 
     123              : // newLevelIter returns a levelIter. It is permissible to pass a nil split
     124              : // parameter if the caller is never going to call SeekPrefixGE.
     125              : func newLevelIter(
     126              :         ctx context.Context,
     127              :         opts IterOptions,
     128              :         comparer *Comparer,
     129              :         newIters tableNewIters,
     130              :         files manifest.LevelIterator,
     131              :         layer manifest.Layer,
     132              :         internalOpts internalIterOpts,
     133            1 : ) *levelIter {
     134            1 :         l := &levelIter{}
     135            1 :         l.init(ctx, opts, comparer, newIters, files, layer, internalOpts)
     136            1 :         return l
     137            1 : }
     138              : 
     139              : func (l *levelIter) init(
     140              :         ctx context.Context,
     141              :         opts IterOptions,
     142              :         comparer *Comparer,
     143              :         newIters tableNewIters,
     144              :         files manifest.LevelIterator,
     145              :         layer manifest.Layer,
     146              :         internalOpts internalIterOpts,
     147            1 : ) {
     148            1 :         l.ctx = ctx
     149            1 :         l.err = nil
     150            1 :         l.layer = layer
     151            1 :         l.logger = opts.getLogger()
     152            1 :         l.prefix = nil
     153            1 :         l.lower = opts.LowerBound
     154            1 :         l.upper = opts.UpperBound
     155            1 :         l.tableOpts.PointKeyFilters = opts.PointKeyFilters
     156            1 :         if len(opts.PointKeyFilters) == 0 {
     157            1 :                 l.tableOpts.PointKeyFilters = l.filtersBuf[:0:1]
     158            1 :         }
     159            1 :         l.tableOpts.UseL6Filters = opts.UseL6Filters
     160            1 :         l.tableOpts.Category = opts.Category
     161            1 :         l.tableOpts.layer = l.layer
     162            1 :         l.tableOpts.snapshotForHideObsoletePoints = opts.snapshotForHideObsoletePoints
     163            1 :         l.comparer = comparer
     164            1 :         l.cmp = comparer.Compare
     165            1 :         l.split = comparer.Split
     166            1 :         l.iterFile = nil
     167            1 :         l.newIters = newIters
     168            1 :         l.files = files
     169            1 :         l.exhaustedDir = 0
     170            1 :         l.internalOpts = internalOpts
     171              : }
     172              : 
     173              : // initRangeDel puts the level iterator into a mode where it interleaves range
     174              : // deletion boundaries with point keys and provides a range deletion iterator
     175              : // (through rangeDelIterFn) whenever the current file changes.
     176              : //
     177              : // The range deletion iterator passed to rangeDelIterFn is relinquished to the
     178              : // implementor who is responsible for closing it.
     179            1 : func (l *levelIter) initRangeDel(rangeDelSetter rangeDelIterSetter) {
     180            1 :         l.rangeDelIterSetter = rangeDelSetter
     181            1 : }
     182              : 
     183            1 : func (l *levelIter) initCombinedIterState(state *combinedIterState) {
     184            1 :         l.combinedIterState = state
     185            1 : }
     186              : 
     187            1 : func (l *levelIter) maybeTriggerCombinedIteration(file *manifest.TableMetadata, dir int) {
     188            1 :         // If we encounter a file that contains range keys, we may need to
     189            1 :         // trigger a switch to combined range-key and point-key iteration,
     190            1 :         // if the *pebble.Iterator is configured for it. This switch is done
     191            1 :         // lazily because range keys are intended to be rare, and
     192            1 :         // constructing the range-key iterator substantially adds to the
     193            1 :         // cost of iterator construction and seeking.
     194            1 :         if file == nil || !file.HasRangeKeys {
     195            1 :                 return
     196            1 :         }
     197              : 
     198              :         // If l.combinedIterState.initialized is already true, either the
     199              :         // iterator is already using combined iteration or the iterator is not
     200              :         // configured to observe range keys. Either way, there's nothing to do.
     201              :         // If false, trigger the switch to combined iteration, using the
     202              :         // file's bounds to seek the range-key iterator appropriately.
     203            1 :         if l.combinedIterState == nil || l.combinedIterState.initialized {
     204            1 :                 return
     205            1 :         }
     206              : 
     207            1 :         if l.upper != nil && l.cmp(file.RangeKeyBounds.SmallestUserKey(), l.upper) >= 0 {
     208            1 :                 // Range key bounds are above the upper iteration bound.
     209            1 :                 return
     210            1 :         }
     211            1 :         if l.lower != nil && l.cmp(file.RangeKeyBounds.LargestUserKey(), l.lower) <= 0 {
     212            1 :                 // Range key bounds are below the lower iteration bound.
     213            1 :                 return
     214            1 :         }
     215            1 :         if stats, ok := file.Stats(); ok && stats.NumRangeKeySets == 0 {
     216            1 :                 // We only need to trigger combined iteration if the file contains
     217            1 :                 // RangeKeySets: if there are only Unsets and Dels, the user will observe no
     218            1 :                 // range keys regardless. If this file has table stats available, they'll
     219            1 :                 // tell us whether the file has any RangeKeySets. Otherwise, we must
     220            1 :                 // fallback to assuming it does (given that HasRangeKeys=true).
     221            1 :                 return
     222            1 :         }
     223              : 
     224              :         // The file contains range keys, and we're not using combined iteration yet.
     225              :         // Trigger a switch to combined iteration. It's possible that a switch has
     226              :         // already been triggered if multiple levels encounter files containing
     227              :         // range keys while executing a single mergingIter operation. In this case,
     228              :         // we need to compare the existing key recorded to l.combinedIterState.key,
     229              :         // adjusting it if our key is smaller (forward iteration) or larger
     230              :         // (backward iteration) than the existing key.
     231              :         //
     232              :         // These key comparisons are only required during a single high-level
     233              :         // iterator operation. When the high-level iter op completes,
     234              :         // iinitialized will be true, and future calls to this function will be
     235              :         // no-ops.
     236            1 :         switch dir {
     237            1 :         case +1:
     238            1 :                 if !l.combinedIterState.triggered {
     239            1 :                         l.combinedIterState.triggered = true
     240            1 :                         l.combinedIterState.key = file.RangeKeyBounds.SmallestUserKey()
     241            1 :                 } else if l.cmp(l.combinedIterState.key, file.RangeKeyBounds.SmallestUserKey()) > 0 {
     242            1 :                         l.combinedIterState.key = file.RangeKeyBounds.SmallestUserKey()
     243            1 :                 }
     244            1 :         case -1:
     245            1 :                 if !l.combinedIterState.triggered {
     246            1 :                         l.combinedIterState.triggered = true
     247            1 :                         l.combinedIterState.key = file.RangeKeyBounds.LargestUserKey()
     248            1 :                 } else if l.cmp(l.combinedIterState.key, file.RangeKeyBounds.LargestUserKey()) < 0 {
     249            1 :                         l.combinedIterState.key = file.RangeKeyBounds.LargestUserKey()
     250            1 :                 }
     251              :         }
     252              : }
     253              : 
     254            1 : func (l *levelIter) findFileGE(key []byte, flags base.SeekGEFlags) *manifest.TableMetadata {
     255            1 :         // Find the earliest file whose largest key is >= key.
     256            1 : 
     257            1 :         // NB: if flags.TrySeekUsingNext()=true, the levelIter must respect it. If
     258            1 :         // the levelIter is positioned at the key P, it must return a key ≥ P. If
     259            1 :         // used within a merging iterator, the merging iterator will depend on the
     260            1 :         // levelIter only moving forward to maintain heap invariants.
     261            1 : 
     262            1 :         // Ordinarily we seek the LevelIterator using SeekGE. In some instances, we
     263            1 :         // Next instead. In other instances, we try Next-ing first, falling back to
     264            1 :         // seek:
     265            1 :         //   a) flags.TrySeekUsingNext(): The top-level Iterator knows we're seeking
     266            1 :         //      to a key later than the current iterator position. We don't know how
     267            1 :         //      much later the seek key is, so it's possible there are many sstables
     268            1 :         //      between the current position and the seek key. However in most real-
     269            1 :         //      world use cases, the seek key is likely to be nearby. Rather than
     270            1 :         //      performing a log(N) seek through the table metadata, we next a few
     271            1 :         //      times from our existing location. If we don't find a file whose
     272            1 :         //      largest is >= key within a few nexts, we fall back to seeking.
     273            1 :         //
     274            1 :         //      Note that in this case, the file returned by findFileGE may be
     275            1 :         //      different than the file returned by a raw binary search (eg, when
     276            1 :         //      TrySeekUsingNext=false). This is possible because the most recent
     277            1 :         //      positioning operation may have already determined that previous
     278            1 :         //      files' keys that are ≥ key are all deleted. This information is
     279            1 :         //      encoded within the iterator's current iterator position and is
     280            1 :         //      unavailable to a fresh binary search.
     281            1 :         //
     282            1 :         //   b) flags.RelativeSeek(): The merging iterator decided to re-seek this
     283            1 :         //      level according to a range tombstone. When lazy combined iteration
     284            1 :         //      is enabled, the level iterator is responsible for watching for
     285            1 :         //      files containing range keys and triggering the switch to combined
     286            1 :         //      iteration when such a file is observed. If a range deletion was
     287            1 :         //      observed in a higher level causing the merging iterator to seek the
     288            1 :         //      level to the range deletion's end key, we need to check whether all
     289            1 :         //      of the files between the old position and the new position contain
     290            1 :         //      any range keys.
     291            1 :         //
     292            1 :         //      In this scenario, we don't seek the LevelIterator and instead we
     293            1 :         //      Next it, one file at a time, checking each for range keys. The
     294            1 :         //      merging iterator sets this flag to inform us that we're moving
     295            1 :         //      forward relative to the existing position and that we must examine
     296            1 :         //      each intermediate sstable's metadata for lazy-combined iteration.
     297            1 :         //      In this case, we only Next and never Seek. We set nextsUntilSeek=-1
     298            1 :         //      to signal this intention.
     299            1 :         //
     300            1 :         // NB: At most one of flags.RelativeSeek() and flags.TrySeekUsingNext() may
     301            1 :         // be set, because the merging iterator re-seeks relative seeks with
     302            1 :         // explicitly only the RelativeSeek flag set.
     303            1 :         var nextsUntilSeek int
     304            1 :         var nextInsteadOfSeek bool
     305            1 :         if flags.TrySeekUsingNext() {
     306            1 :                 nextInsteadOfSeek = true
     307            1 :                 nextsUntilSeek = 4 // arbitrary
     308            1 :         }
     309            1 :         if flags.RelativeSeek() && l.combinedIterState != nil && !l.combinedIterState.initialized {
     310            1 :                 nextInsteadOfSeek = true
     311            1 :                 nextsUntilSeek = -1
     312            1 :         }
     313              : 
     314            1 :         var m *manifest.TableMetadata
     315            1 :         if nextInsteadOfSeek {
     316            1 :                 m = l.iterFile
     317            1 :         } else {
     318            1 :                 m = l.files.SeekGE(l.cmp, key)
     319            1 :         }
     320              :         // The below loop has a bit of an unusual organization. There are several
     321              :         // conditions under which we need to Next to a later file. If none of those
     322              :         // conditions are met, the file in `m` is okay to return. The loop body is
     323              :         // structured with a series of if statements, each of which may continue the
     324              :         // loop to the next file. If none of the statements are met, the end of the
     325              :         // loop body is a break.
     326            1 :         for m != nil {
     327            1 :                 if m.HasRangeKeys {
     328            1 :                         l.maybeTriggerCombinedIteration(m, +1)
     329            1 : 
     330            1 :                         // Some files may only contain range keys, which we can skip.
     331            1 :                         // NB: HasPointKeys=true if the file contains any points or range
     332            1 :                         // deletions (which delete points).
     333            1 :                         if !m.HasPointKeys {
     334            1 :                                 m = l.files.Next()
     335            1 :                                 continue
     336              :                         }
     337              :                 }
     338              : 
     339              :                 // This file has point keys.
     340              :                 //
     341              :                 // However, there are a couple reasons why `m` may not be positioned ≥
     342              :                 // `key` yet:
     343              :                 //
     344              :                 // 1. If SeekGE(key) landed on a file containing range keys, the file
     345              :                 //    may contain range keys ≥ `key` but no point keys ≥ `key`.
     346              :                 // 2. When nexting instead of seeking, we must check to see whether
     347              :                 //    we've nexted sufficiently far, or we need to next again.
     348              :                 //
     349              :                 // If the file does not contain point keys ≥ `key`, next to continue
     350              :                 // looking for a file that does.
     351            1 :                 if (m.HasRangeKeys || nextInsteadOfSeek) && l.cmp(m.PointKeyBounds.LargestUserKey(), key) < 0 {
     352            1 :                         // If nextInsteadOfSeek is set and nextsUntilSeek is non-negative,
     353            1 :                         // the iterator has been nexting hoping to discover the relevant
     354            1 :                         // file without seeking. It's exhausted the allotted nextsUntilSeek
     355            1 :                         // and should seek to the sought key.
     356            1 :                         if nextInsteadOfSeek && nextsUntilSeek == 0 {
     357            1 :                                 nextInsteadOfSeek = false
     358            1 :                                 m = l.files.SeekGE(l.cmp, key)
     359            1 :                                 continue
     360            1 :                         } else if nextsUntilSeek > 0 {
     361            1 :                                 nextsUntilSeek--
     362            1 :                         }
     363            1 :                         m = l.files.Next()
     364            1 :                         continue
     365              :                 }
     366              : 
     367              :                 // This file has a point key bound ≥ `key`. But the largest point key
     368              :                 // bound may still be a range deletion sentinel, which is exclusive.  In
     369              :                 // this case, the file doesn't actually contain any point keys equal to
     370              :                 // `key`. We next to keep searching for a file that actually contains
     371              :                 // point keys ≥ key.
     372              :                 //
     373              :                 // Additionally, this prevents loading untruncated range deletions from
     374              :                 // a table which can't possibly contain the target key and is required
     375              :                 // for correctness by mergingIter.SeekGE (see the comment in that
     376              :                 // function).
     377            1 :                 if m.PointKeyBounds.Largest().IsExclusiveSentinel() && l.cmp(m.PointKeyBounds.LargestUserKey(), key) == 0 {
     378            1 :                         m = l.files.Next()
     379            1 :                         continue
     380              :                 }
     381              : 
     382              :                 // This file contains point keys ≥ `key`. Break and return it.
     383            1 :                 break
     384              :         }
     385            1 :         return m
     386              : }
     387              : 
     388            1 : func (l *levelIter) findFileLT(key []byte, flags base.SeekLTFlags) *manifest.TableMetadata {
     389            1 :         // Find the last file whose smallest key is < ikey.
     390            1 : 
     391            1 :         // Ordinarily we seek the LevelIterator using SeekLT.
     392            1 :         //
     393            1 :         // When lazy combined iteration is enabled, there's a complication. The
     394            1 :         // level iterator is responsible for watching for files containing range
     395            1 :         // keys and triggering the switch to combined iteration when such a file is
     396            1 :         // observed. If a range deletion was observed in a higher level causing the
     397            1 :         // merging iterator to seek the level to the range deletion's start key, we
     398            1 :         // need to check whether all of the files between the old position and the
     399            1 :         // new position contain any range keys.
     400            1 :         //
     401            1 :         // In this scenario, we don't seek the LevelIterator and instead we Prev it,
     402            1 :         // one file at a time, checking each for range keys.
     403            1 :         prevInsteadOfSeek := flags.RelativeSeek() && l.combinedIterState != nil && !l.combinedIterState.initialized
     404            1 : 
     405            1 :         var m *manifest.TableMetadata
     406            1 :         if prevInsteadOfSeek {
     407            1 :                 m = l.iterFile
     408            1 :         } else {
     409            1 :                 m = l.files.SeekLT(l.cmp, key)
     410            1 :         }
     411              :         // The below loop has a bit of an unusual organization. There are several
     412              :         // conditions under which we need to Prev to a previous file. If none of
     413              :         // those conditions are met, the file in `m` is okay to return. The loop
     414              :         // body is structured with a series of if statements, each of which may
     415              :         // continue the loop to the previous file. If none of the statements are
     416              :         // met, the end of the loop body is a break.
     417            1 :         for m != nil {
     418            1 :                 if m.HasRangeKeys {
     419            1 :                         l.maybeTriggerCombinedIteration(m, -1)
     420            1 : 
     421            1 :                         // Some files may only contain range keys, which we can skip.
     422            1 :                         // NB: HasPointKeys=true if the file contains any points or range
     423            1 :                         // deletions (which delete points).
     424            1 :                         if !m.HasPointKeys {
     425            1 :                                 m = l.files.Prev()
     426            1 :                                 continue
     427              :                         }
     428              :                 }
     429              : 
     430              :                 // This file has point keys.
     431              :                 //
     432              :                 // However, there are a couple reasons why `m` may not be positioned <
     433              :                 // `key` yet:
     434              :                 //
     435              :                 // 1. If SeekLT(key) landed on a file containing range keys, the file
     436              :                 //    may contain range keys < `key` but no point keys < `key`.
     437              :                 // 2. When preving instead of seeking, we must check to see whether
     438              :                 //    we've preved sufficiently far, or we need to prev again.
     439              :                 //
     440              :                 // If the file does not contain point keys < `key`, prev to continue
     441              :                 // looking for a file that does.
     442            1 :                 if (m.HasRangeKeys || prevInsteadOfSeek) && l.cmp(m.PointKeyBounds.SmallestUserKey(), key) >= 0 {
     443            1 :                         m = l.files.Prev()
     444            1 :                         continue
     445              :                 }
     446              : 
     447              :                 // This file contains point keys < `key`. Break and return it.
     448            1 :                 break
     449              :         }
     450            1 :         return m
     451              : }
     452              : 
     453              : // Init the iteration bounds for the current table. Returns -1 if the table
     454              : // lies fully before the lower bound, +1 if the table lies fully after the
     455              : // upper bound, and 0 if the table overlaps the iteration bounds.
     456            1 : func (l *levelIter) initTableBounds(f *manifest.TableMetadata) int {
     457            1 :         l.tableOpts.LowerBound = l.lower
     458            1 :         if l.tableOpts.LowerBound != nil {
     459            1 :                 if l.cmp(f.PointKeyBounds.LargestUserKey(), l.tableOpts.LowerBound) < 0 {
     460            1 :                         // The largest key in the sstable is smaller than the lower bound.
     461            1 :                         return -1
     462            1 :                 }
     463            1 :                 if l.cmp(l.tableOpts.LowerBound, f.PointKeyBounds.SmallestUserKey()) <= 0 {
     464            1 :                         // The lower bound is smaller or equal to the smallest key in the
     465            1 :                         // table. Iteration within the table does not need to check the lower
     466            1 :                         // bound.
     467            1 :                         l.tableOpts.LowerBound = nil
     468            1 :                 }
     469              :         }
     470            1 :         l.tableOpts.UpperBound = l.upper
     471            1 :         if l.tableOpts.UpperBound != nil {
     472            1 :                 if l.cmp(f.PointKeyBounds.SmallestUserKey(), l.tableOpts.UpperBound) >= 0 {
     473            1 :                         // The smallest key in the sstable is greater than or equal to the upper
     474            1 :                         // bound.
     475            1 :                         return 1
     476            1 :                 }
     477            1 :                 if l.cmp(l.tableOpts.UpperBound, f.PointKeyBounds.LargestUserKey()) > 0 {
     478            1 :                         // The upper bound is greater than the largest key in the
     479            1 :                         // table. Iteration within the table does not need to check the upper
     480            1 :                         // bound. NB: tableOpts.UpperBound is exclusive and f.PointKeyBounds.Largest() is
     481            1 :                         // inclusive.
     482            1 :                         l.tableOpts.UpperBound = nil
     483            1 :                 }
     484              :         }
     485            1 :         return 0
     486              : }
     487              : 
     488              : type loadFileReturnIndicator int8
     489              : 
     490              : const (
     491              :         noFileLoaded loadFileReturnIndicator = iota
     492              :         fileAlreadyLoaded
     493              :         newFileLoaded
     494              : )
     495              : 
     496            1 : func (l *levelIter) loadFile(file *manifest.TableMetadata, dir int) loadFileReturnIndicator {
     497            1 :         if l.iterFile == file {
     498            1 :                 if l.err != nil {
     499            0 :                         return noFileLoaded
     500            0 :                 }
     501            1 :                 if l.iter != nil {
     502            1 :                         // We don't bother comparing the file bounds with the iteration bounds when we have
     503            1 :                         // an already open iterator. It is possible that the iter may not be relevant given the
     504            1 :                         // current iteration bounds, but it knows those bounds, so it will enforce them.
     505            1 : 
     506            1 :                         // There are a few reasons we might not have triggered combined
     507            1 :                         // iteration yet, even though we already had `file` open.
     508            1 :                         // 1. If the bounds changed, we might have previously avoided
     509            1 :                         //    switching to combined iteration because the bounds excluded
     510            1 :                         //    the range keys contained in this file.
     511            1 :                         // 2. If an existing iterator was reconfigured to iterate over range
     512            1 :                         //    keys (eg, using SetOptions), then we wouldn't have triggered
     513            1 :                         //    the switch to combined iteration yet.
     514            1 :                         l.maybeTriggerCombinedIteration(file, dir)
     515            1 :                         return fileAlreadyLoaded
     516            1 :                 }
     517              :                 // We were already at file, but don't have an iterator, probably because the file was
     518              :                 // beyond the iteration bounds. It may still be, but it is also possible that the bounds
     519              :                 // have changed. We handle that below.
     520              :         }
     521              : 
     522              :         // Close iter and send a nil iterator through rangeDelIterFn.rangeDelIterFn.
     523            1 :         if err := l.Close(); err != nil {
     524            0 :                 return noFileLoaded
     525            0 :         }
     526              : 
     527            1 :         for {
     528            1 :                 l.iterFile = file
     529            1 :                 if file == nil {
     530            1 :                         return noFileLoaded
     531            1 :                 }
     532              : 
     533            1 :                 l.maybeTriggerCombinedIteration(file, dir)
     534            1 :                 if !file.HasPointKeys {
     535            1 :                         switch dir {
     536            1 :                         case +1:
     537            1 :                                 file = l.files.Next()
     538            1 :                                 continue
     539            1 :                         case -1:
     540            1 :                                 file = l.files.Prev()
     541            1 :                                 continue
     542              :                         }
     543              :                 }
     544              : 
     545            1 :                 switch l.initTableBounds(file) {
     546            1 :                 case -1:
     547            1 :                         // The largest key in the sstable is smaller than the lower bound.
     548            1 :                         if dir < 0 {
     549            1 :                                 return noFileLoaded
     550            1 :                         }
     551            0 :                         file = l.files.Next()
     552            0 :                         continue
     553            1 :                 case +1:
     554            1 :                         // The smallest key in the sstable is greater than or equal to the upper
     555            1 :                         // bound.
     556            1 :                         if dir > 0 {
     557            1 :                                 return noFileLoaded
     558            1 :                         }
     559            0 :                         file = l.files.Prev()
     560            0 :                         continue
     561              :                 }
     562              :                 // If we're in prefix iteration, it's possible this file's smallest
     563              :                 // boundary is large enough to prove the file cannot possibly contain
     564              :                 // any keys within the iteration prefix. Loading the next file is
     565              :                 // unnecessary. This has been observed in practice on slow shared
     566              :                 // storage. See #3575.
     567            1 :                 if l.prefix != nil && l.cmp(l.split.Prefix(file.PointKeyBounds.SmallestUserKey()), l.prefix) > 0 {
     568            1 :                         // Note that because l.iter is nil, a subsequent call to
     569            1 :                         // SeekPrefixGE with TrySeekUsingNext()=true will load the file
     570            1 :                         // (returning newFileLoaded) and disable TrySeekUsingNext before
     571            1 :                         // performing a seek in the file.
     572            1 :                         return noFileLoaded
     573            1 :                 }
     574              : 
     575            1 :                 iterKinds := iterPointKeys
     576            1 :                 if l.rangeDelIterSetter != nil {
     577            1 :                         iterKinds |= iterRangeDeletions
     578            1 :                 }
     579              : 
     580            1 :                 var iters iterSet
     581            1 :                 iters, l.err = l.newIters(l.ctx, l.iterFile, &l.tableOpts, l.internalOpts, iterKinds)
     582            1 :                 if l.err != nil {
     583            0 :                         if l.rangeDelIterSetter != nil {
     584            0 :                                 l.rangeDelIterSetter.setRangeDelIter(nil)
     585            0 :                         }
     586            0 :                         return noFileLoaded
     587              :                 }
     588            1 :                 l.iter = iters.Point()
     589            1 :                 if l.rangeDelIterSetter != nil && iters.rangeDeletion != nil {
     590            1 :                         // If this file has range deletions, interleave the bounds of the
     591            1 :                         // range deletions among the point keys. When used with a
     592            1 :                         // mergingIter, this ensures we don't move beyond a file with range
     593            1 :                         // deletions until its range deletions are no longer relevant.
     594            1 :                         //
     595            1 :                         // For now, we open a second range deletion iterator. Future work
     596            1 :                         // will avoid the need to open a second range deletion iterator, and
     597            1 :                         // avoid surfacing the file's range deletion iterator via rangeDelIterFn.
     598            1 :                         itersForBounds, err := l.newIters(l.ctx, l.iterFile, &l.tableOpts, l.internalOpts, iterRangeDeletions)
     599            1 :                         if err != nil {
     600            0 :                                 l.iter = nil
     601            0 :                                 l.err = errors.CombineErrors(err, iters.CloseAll())
     602            0 :                                 return noFileLoaded
     603            0 :                         }
     604            1 :                         l.interleaving.Init(l.comparer, l.iter, itersForBounds.RangeDeletion(), keyspan.InterleavingIterOpts{
     605            1 :                                 LowerBound:        l.tableOpts.LowerBound,
     606            1 :                                 UpperBound:        l.tableOpts.UpperBound,
     607            1 :                                 InterleaveEndKeys: true,
     608            1 :                         })
     609            1 :                         l.iter = &l.interleaving
     610            1 : 
     611            1 :                         // Relinquish iters.rangeDeletion to the caller.
     612            1 :                         l.rangeDelIterSetter.setRangeDelIter(iters.rangeDeletion)
     613              :                 }
     614            1 :                 return newFileLoaded
     615              :         }
     616              : }
     617              : 
     618              : // In race builds we verify that the keys returned by levelIter lie within
     619              : // [lower,upper).
     620            1 : func (l *levelIter) verify(kv *base.InternalKV) *base.InternalKV {
     621            1 :         // Note that invariants.Enabled is a compile time constant, which means the
     622            1 :         // block of code will be compiled out of normal builds making this method
     623            1 :         // eligible for inlining. Do not change this to use a variable.
     624            1 :         if invariants.Enabled && !l.disableInvariants && kv != nil {
     625            1 :                 // We allow returning a boundary key that is outside of the lower/upper
     626            1 :                 // bounds as such keys are always range tombstones which will be skipped
     627            1 :                 // by the Iterator.
     628            1 :                 if l.lower != nil && kv != nil && !kv.K.IsExclusiveSentinel() && l.cmp(kv.K.UserKey, l.lower) < 0 {
     629            0 :                         l.logger.Fatalf("levelIter %s: lower bound violation: %s < %s\n%s", l.layer, kv, l.lower, debug.Stack())
     630            0 :                 }
     631            1 :                 if l.upper != nil && kv != nil && !kv.K.IsExclusiveSentinel() && l.cmp(kv.K.UserKey, l.upper) > 0 {
     632            0 :                         l.logger.Fatalf("levelIter %s: upper bound violation: %s > %s\n%s", l.layer, kv, l.upper, debug.Stack())
     633            0 :                 }
     634              :         }
     635            1 :         return kv
     636              : }
     637              : 
     638            1 : func (l *levelIter) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKV {
     639            1 :         if invariants.Enabled && l.lower != nil && l.cmp(key, l.lower) < 0 {
     640            0 :                 panic(errors.AssertionFailedf("levelIter SeekGE to key %q violates lower bound %q", key, l.lower))
     641              :         }
     642              : 
     643            1 :         l.err = nil // clear cached iteration error
     644            1 :         l.exhaustedDir = 0
     645            1 :         l.prefix = nil
     646            1 :         // NB: the top-level Iterator has already adjusted key based on
     647            1 :         // IterOptions.LowerBound.
     648            1 :         loadFileIndicator := l.loadFile(l.findFileGE(key, flags), +1)
     649            1 :         if loadFileIndicator == noFileLoaded {
     650            1 :                 l.exhaustedForward()
     651            1 :                 return nil
     652            1 :         }
     653            1 :         if loadFileIndicator == newFileLoaded {
     654            1 :                 // File changed, so l.iter has changed, and that iterator is not
     655            1 :                 // positioned appropriately.
     656            1 :                 flags = flags.DisableTrySeekUsingNext()
     657            1 :         }
     658            1 :         if kv := l.iter.SeekGE(key, flags); kv != nil {
     659            1 :                 return l.verify(kv)
     660            1 :         }
     661            1 :         return l.verify(l.skipEmptyFileForward())
     662              : }
     663              : 
     664            1 : func (l *levelIter) SeekPrefixGE(prefix, key []byte, flags base.SeekGEFlags) *base.InternalKV {
     665            1 :         if invariants.Enabled && l.lower != nil && l.cmp(key, l.lower) < 0 {
     666            0 :                 panic(errors.AssertionFailedf("levelIter SeekGE to key %q violates lower bound %q", key, l.lower))
     667              :         }
     668            1 :         l.err = nil // clear cached iteration error
     669            1 :         l.exhaustedDir = 0
     670            1 :         l.prefix = prefix
     671            1 : 
     672            1 :         // NB: the top-level Iterator has already adjusted key based on
     673            1 :         // IterOptions.LowerBound.
     674            1 :         loadFileIndicator := l.loadFile(l.findFileGE(key, flags), +1)
     675            1 :         if loadFileIndicator == noFileLoaded {
     676            1 :                 l.exhaustedForward()
     677            1 :                 return nil
     678            1 :         }
     679            1 :         if loadFileIndicator == newFileLoaded {
     680            1 :                 // File changed, so l.iter has changed, and that iterator is not
     681            1 :                 // positioned appropriately.
     682            1 :                 flags = flags.DisableTrySeekUsingNext()
     683            1 :         }
     684            1 :         if kv := l.iter.SeekPrefixGE(prefix, key, flags); kv != nil {
     685            1 :                 return l.verify(kv)
     686            1 :         }
     687            1 :         if err := l.iter.Error(); err != nil {
     688            0 :                 return nil
     689            0 :         }
     690            1 :         return l.verify(l.skipEmptyFileForward())
     691              : }
     692              : 
     693            1 : func (l *levelIter) SeekLT(key []byte, flags base.SeekLTFlags) *base.InternalKV {
     694            1 :         if invariants.Enabled && l.upper != nil && l.cmp(key, l.upper) > 0 {
     695            0 :                 panic(errors.AssertionFailedf("levelIter SeekLT to key %q violates upper bound %q", key, l.upper))
     696              :         }
     697              : 
     698            1 :         l.err = nil // clear cached iteration error
     699            1 :         l.exhaustedDir = 0
     700            1 :         l.prefix = nil
     701            1 : 
     702            1 :         // NB: the top-level Iterator has already adjusted key based on
     703            1 :         // IterOptions.UpperBound.
     704            1 :         if l.loadFile(l.findFileLT(key, flags), -1) == noFileLoaded {
     705            1 :                 l.exhaustedBackward()
     706            1 :                 return nil
     707            1 :         }
     708            1 :         if kv := l.iter.SeekLT(key, flags); kv != nil {
     709            1 :                 return l.verify(kv)
     710            1 :         }
     711            1 :         return l.verify(l.skipEmptyFileBackward())
     712              : }
     713              : 
     714            1 : func (l *levelIter) First() *base.InternalKV {
     715            1 :         if invariants.Enabled && l.lower != nil {
     716            0 :                 panic(errors.AssertionFailedf("levelIter First called while lower bound %q is set", l.lower))
     717              :         }
     718              : 
     719            1 :         l.err = nil // clear cached iteration error
     720            1 :         l.exhaustedDir = 0
     721            1 :         l.prefix = nil
     722            1 : 
     723            1 :         // NB: the top-level Iterator will call SeekGE if IterOptions.LowerBound is
     724            1 :         // set.
     725            1 :         if l.loadFile(l.files.First(), +1) == noFileLoaded {
     726            1 :                 l.exhaustedForward()
     727            1 :                 return nil
     728            1 :         }
     729            1 :         if kv := l.iter.First(); kv != nil {
     730            1 :                 return l.verify(kv)
     731            1 :         }
     732            1 :         return l.verify(l.skipEmptyFileForward())
     733              : }
     734              : 
     735            1 : func (l *levelIter) Last() *base.InternalKV {
     736            1 :         if invariants.Enabled && l.upper != nil {
     737            0 :                 panic(errors.AssertionFailedf("levelIter Last called while upper bound %q is set", l.upper))
     738              :         }
     739              : 
     740            1 :         l.err = nil // clear cached iteration error
     741            1 :         l.exhaustedDir = 0
     742            1 :         l.prefix = nil
     743            1 : 
     744            1 :         // NB: the top-level Iterator will call SeekLT if IterOptions.UpperBound is
     745            1 :         // set.
     746            1 :         if l.loadFile(l.files.Last(), -1) == noFileLoaded {
     747            1 :                 l.exhaustedBackward()
     748            1 :                 return nil
     749            1 :         }
     750            1 :         if kv := l.iter.Last(); kv != nil {
     751            1 :                 return l.verify(kv)
     752            1 :         }
     753            1 :         return l.verify(l.skipEmptyFileBackward())
     754              : }
     755              : 
     756            1 : func (l *levelIter) Next() *base.InternalKV {
     757            1 :         if l.exhaustedDir == -1 {
     758            1 :                 if l.lower != nil {
     759            1 :                         return l.SeekGE(l.lower, base.SeekGEFlagsNone)
     760            1 :                 }
     761            1 :                 return l.First()
     762              :         }
     763            1 :         if l.err != nil || l.iter == nil {
     764            0 :                 return nil
     765            0 :         }
     766            1 :         if kv := l.iter.Next(); kv != nil {
     767            1 :                 return l.verify(kv)
     768            1 :         }
     769            1 :         return l.verify(l.skipEmptyFileForward())
     770              : }
     771              : 
     772            1 : func (l *levelIter) NextPrefix(succKey []byte) *base.InternalKV {
     773            1 :         if l.err != nil || l.iter == nil {
     774            0 :                 return nil
     775            0 :         }
     776              : 
     777            1 :         if kv := l.iter.NextPrefix(succKey); kv != nil {
     778            1 :                 return l.verify(kv)
     779            1 :         }
     780            1 :         if l.iter.Error() != nil {
     781            0 :                 return nil
     782            0 :         }
     783            1 :         if l.tableOpts.UpperBound != nil {
     784            1 :                 // The UpperBound was within this file, so don't load the next file.
     785            1 :                 l.exhaustedForward()
     786            1 :                 return nil
     787            1 :         }
     788              : 
     789              :         // Seek the manifest level iterator using TrySeekUsingNext=true and
     790              :         // RelativeSeek=true so that we take advantage of the knowledge that
     791              :         // `succKey` can only be contained in later files.
     792            1 :         metadataSeekFlags := base.SeekGEFlagsNone.EnableTrySeekUsingNext().EnableRelativeSeek()
     793            1 :         if l.loadFile(l.findFileGE(succKey, metadataSeekFlags), +1) != noFileLoaded {
     794            1 :                 // NB: The SeekGE on the file's iterator must not set TrySeekUsingNext,
     795            1 :                 // because l.iter is unpositioned.
     796            1 :                 if kv := l.iter.SeekGE(succKey, base.SeekGEFlagsNone); kv != nil {
     797            1 :                         return l.verify(kv)
     798            1 :                 }
     799            1 :                 return l.verify(l.skipEmptyFileForward())
     800              :         }
     801            1 :         l.exhaustedForward()
     802            1 :         return nil
     803              : }
     804              : 
     805            1 : func (l *levelIter) Prev() *base.InternalKV {
     806            1 :         if l.exhaustedDir == +1 {
     807            1 :                 if l.upper != nil {
     808            1 :                         return l.SeekLT(l.upper, base.SeekLTFlagsNone)
     809            1 :                 }
     810            1 :                 return l.Last()
     811              :         }
     812            1 :         if l.err != nil || l.iter == nil {
     813            0 :                 return nil
     814            0 :         }
     815            1 :         if kv := l.iter.Prev(); kv != nil {
     816            1 :                 return l.verify(kv)
     817            1 :         }
     818            1 :         return l.verify(l.skipEmptyFileBackward())
     819              : }
     820              : 
     821            1 : func (l *levelIter) skipEmptyFileForward() *base.InternalKV {
     822            1 :         var kv *base.InternalKV
     823            1 :         // The first iteration of this loop starts with an already exhausted l.iter.
     824            1 :         // The reason for the exhaustion is either that we iterated to the end of
     825            1 :         // the sstable, or our iteration was terminated early due to the presence of
     826            1 :         // an upper-bound or the use of SeekPrefixGE.
     827            1 :         //
     828            1 :         // Subsequent iterations will examine consecutive files such that the first
     829            1 :         // file that does not have an exhausted iterator causes the code to return
     830            1 :         // that key.
     831            1 :         for ; kv == nil; kv = l.iter.First() {
     832            1 :                 if l.iter.Error() != nil {
     833            0 :                         return nil
     834            0 :                 }
     835              :                 // If an upper bound is present and the upper bound lies within the
     836              :                 // current sstable, then we will have reached the upper bound rather
     837              :                 // than the end of the sstable.
     838            1 :                 if l.tableOpts.UpperBound != nil {
     839            1 :                         l.exhaustedForward()
     840            1 :                         return nil
     841            1 :                 }
     842              : 
     843              :                 // If the iterator is in prefix iteration mode, it's possible that we
     844              :                 // are here because bloom filter matching failed. In that case it is
     845              :                 // likely that all keys matching the prefix are wholly within the
     846              :                 // current file and cannot be in a subsequent file. In that case we
     847              :                 // don't want to go to the next file, since loading and seeking in there
     848              :                 // has some cost.
     849              :                 //
     850              :                 // This is not just an optimization. We must not advance to the next
     851              :                 // file if the current file might possibly contain keys relevant to any
     852              :                 // prefix greater than our current iteration prefix. If we did, a
     853              :                 // subsequent SeekPrefixGE with TrySeekUsingNext could mistakenly skip
     854              :                 // the file's relevant keys.
     855            1 :                 if l.prefix != nil {
     856            1 :                         if l.cmp(l.split.Prefix(l.iterFile.PointKeyBounds.LargestUserKey()), l.prefix) > 0 {
     857            1 :                                 l.exhaustedForward()
     858            1 :                                 return nil
     859            1 :                         }
     860              :                 }
     861              : 
     862              :                 // Current file was exhausted. Move to the next file.
     863            1 :                 if l.loadFile(l.files.Next(), +1) == noFileLoaded {
     864            1 :                         l.exhaustedForward()
     865            1 :                         return nil
     866            1 :                 }
     867              :         }
     868            1 :         return kv
     869              : }
     870              : 
     871            1 : func (l *levelIter) skipEmptyFileBackward() *base.InternalKV {
     872            1 :         var kv *base.InternalKV
     873            1 :         // The first iteration of this loop starts with an already exhausted
     874            1 :         // l.iter. The reason for the exhaustion is either that we iterated to the
     875            1 :         // end of the sstable, or our iteration was terminated early due to the
     876            1 :         // presence of a lower-bound.
     877            1 :         //
     878            1 :         // Subsequent iterations will examine consecutive files such that the first
     879            1 :         // file that does not have an exhausted iterator causes the code to return
     880            1 :         // that key.
     881            1 :         for ; kv == nil; kv = l.iter.Last() {
     882            1 :                 if l.iter.Error() != nil {
     883            0 :                         return nil
     884            0 :                 }
     885              :                 // If a lower bound is present and the lower bound lies within the
     886              :                 // current sstable, then we will have reached the lowerr bound rather
     887              :                 // than the end of the sstable.
     888            1 :                 if l.tableOpts.LowerBound != nil {
     889            1 :                         l.exhaustedBackward()
     890            1 :                         return nil
     891            1 :                 }
     892              :                 // Current file was exhausted. Move to the previous file.
     893            1 :                 if l.loadFile(l.files.Prev(), -1) == noFileLoaded {
     894            1 :                         l.exhaustedBackward()
     895            1 :                         return nil
     896            1 :                 }
     897              :         }
     898            1 :         return kv
     899              : }
     900              : 
     901            1 : func (l *levelIter) exhaustedForward() {
     902            1 :         l.exhaustedDir = +1
     903            1 : }
     904              : 
     905            1 : func (l *levelIter) exhaustedBackward() {
     906            1 :         l.exhaustedDir = -1
     907            1 : }
     908              : 
     909            1 : func (l *levelIter) Error() error {
     910            1 :         if l.err != nil || l.iter == nil {
     911            1 :                 return l.err
     912            1 :         }
     913            1 :         return l.iter.Error()
     914              : }
     915              : 
     916            1 : func (l *levelIter) Close() error {
     917            1 :         if l.iter != nil {
     918            1 :                 l.err = l.iter.Close()
     919            1 :                 l.iter = nil
     920            1 :         }
     921            1 :         if l.rangeDelIterSetter != nil {
     922            1 :                 l.rangeDelIterSetter.setRangeDelIter(nil)
     923            1 :         }
     924            1 :         return l.err
     925              : }
     926              : 
     927            1 : func (l *levelIter) SetBounds(lower, upper []byte) {
     928            1 :         l.lower = lower
     929            1 :         l.upper = upper
     930            1 : 
     931            1 :         if l.iter == nil {
     932            1 :                 return
     933            1 :         }
     934              : 
     935              :         // Update tableOpts.{Lower,Upper}Bound in case the new boundaries fall within
     936              :         // the boundaries of the current table.
     937            1 :         if l.initTableBounds(l.iterFile) != 0 {
     938            1 :                 // The table does not overlap the bounds. Close() will set levelIter.err if
     939            1 :                 // an error occurs.
     940            1 :                 _ = l.Close()
     941            1 :                 return
     942            1 :         }
     943              : 
     944            1 :         l.iter.SetBounds(l.tableOpts.LowerBound, l.tableOpts.UpperBound)
     945              : }
     946              : 
     947            0 : func (l *levelIter) SetContext(ctx context.Context) {
     948            0 :         l.ctx = ctx
     949            0 :         if l.iter != nil {
     950            0 :                 // TODO(sumeer): this is losing the ctx = objiotracing.WithLevel(ctx,
     951            0 :                 // manifest.LevelToInt(opts.level)) that happens in table_cache.go.
     952            0 :                 l.iter.SetContext(ctx)
     953            0 :         }
     954              : }
     955              : 
     956              : // DebugTree is part of the InternalIterator interface.
     957            0 : func (l *levelIter) DebugTree(tp treeprinter.Node) {
     958            0 :         n := tp.Childf("%T(%p) %s", l, l, l.String())
     959            0 :         if l.iter != nil {
     960            0 :                 l.iter.DebugTree(n)
     961            0 :         }
     962              : }
     963              : 
     964            1 : func (l *levelIter) String() string {
     965            1 :         if l.iterFile != nil {
     966            1 :                 return fmt.Sprintf("%s: fileNum=%s", l.layer, l.iterFile.TableNum.String())
     967            1 :         }
     968            0 :         return fmt.Sprintf("%s: fileNum=<nil>", l.layer)
     969              : }
     970              : 
     971              : var _ internalIterator = &levelIter{}
        

Generated by: LCOV version 2.0-1