LCOV - code coverage report
Current view: top level - pebble - iterator.go (source / functions) Hit Total Coverage
Test: 2023-12-19 08:16Z 5c5ad7ed - tests only.lcov Lines: 1633 1811 90.2 %
Date: 2023-12-19 08:16:27 Functions: 0 0 -

          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 pebble
       6             : 
       7             : import (
       8             :         "bytes"
       9             :         "context"
      10             :         "io"
      11             :         "sync"
      12             :         "unsafe"
      13             : 
      14             :         "github.com/cockroachdb/errors"
      15             :         "github.com/cockroachdb/pebble/internal/base"
      16             :         "github.com/cockroachdb/pebble/internal/bytealloc"
      17             :         "github.com/cockroachdb/pebble/internal/fastrand"
      18             :         "github.com/cockroachdb/pebble/internal/humanize"
      19             :         "github.com/cockroachdb/pebble/internal/invariants"
      20             :         "github.com/cockroachdb/pebble/internal/keyspan"
      21             :         "github.com/cockroachdb/pebble/internal/manifest"
      22             :         "github.com/cockroachdb/pebble/internal/rangekey"
      23             :         "github.com/cockroachdb/pebble/sstable"
      24             :         "github.com/cockroachdb/redact"
      25             : )
      26             : 
      27             : // iterPos describes the state of the internal iterator, in terms of whether it
      28             : // is at the position returned to the user (cur), one ahead of the position
      29             : // returned (next for forward iteration and prev for reverse iteration). The cur
      30             : // position is split into two states, for forward and reverse iteration, since
      31             : // we need to differentiate for switching directions.
      32             : //
      33             : // There is subtlety in what is considered the current position of the Iterator.
      34             : // The internal iterator exposes a sequence of internal keys. There is not
      35             : // always a single internalIterator position corresponding to the position
      36             : // returned to the user. Consider the example:
      37             : //
      38             : //      a.MERGE.9 a.MERGE.8 a.MERGE.7 a.SET.6 b.DELETE.9 b.DELETE.5 b.SET.4
      39             : //      \                                   /
      40             : //        \       Iterator.Key() = 'a'    /
      41             : //
      42             : // The Iterator exposes one valid position at user key 'a' and the two exhausted
      43             : // positions at the beginning and end of iteration. The underlying
      44             : // internalIterator contains 7 valid positions and 2 exhausted positions.
      45             : //
      46             : // Iterator positioning methods must set iterPos to iterPosCur{Foward,Backward}
      47             : // iff the user key at the current internalIterator position equals the
      48             : // Iterator.Key returned to the user. This guarantees that a call to nextUserKey
      49             : // or prevUserKey will advance to the next or previous iterator position.
      50             : // iterPosCur{Forward,Backward} does not make any guarantee about the internal
      51             : // iterator position among internal keys with matching user keys, and it will
      52             : // vary subtly depending on the particular key kinds encountered. In the above
      53             : // example, the iterator returning 'a' may set iterPosCurForward if the internal
      54             : // iterator is positioned at any of a.MERGE.9, a.MERGE.8, a.MERGE.7 or a.SET.6.
      55             : //
      56             : // When setting iterPos to iterPosNext or iterPosPrev, the internal iterator
      57             : // must be advanced to the first internalIterator position at a user key greater
      58             : // (iterPosNext) or less (iterPosPrev) than the key returned to the user. An
      59             : // internalIterator position that's !Valid() must also be considered greater or
      60             : // less—depending on the direction of iteration—than the last valid Iterator
      61             : // position.
      62             : type iterPos int8
      63             : 
      64             : const (
      65             :         iterPosCurForward iterPos = 0
      66             :         iterPosNext       iterPos = 1
      67             :         iterPosPrev       iterPos = -1
      68             :         iterPosCurReverse iterPos = -2
      69             : 
      70             :         // For limited iteration. When the iterator is at iterPosCurForwardPaused
      71             :         // - Next*() call should behave as if the internal iterator is already
      72             :         //   at next (akin to iterPosNext).
      73             :         // - Prev*() call should behave as if the internal iterator is at the
      74             :         //   current key (akin to iterPosCurForward).
      75             :         //
      76             :         // Similar semantics apply to CurReversePaused.
      77             :         iterPosCurForwardPaused iterPos = 2
      78             :         iterPosCurReversePaused iterPos = -3
      79             : )
      80             : 
      81             : // Approximate gap in bytes between samples of data read during iteration.
      82             : // This is multiplied with a default ReadSamplingMultiplier of 1 << 4 to yield
      83             : // 1 << 20 (1MB). The 1MB factor comes from:
      84             : // https://github.com/cockroachdb/pebble/issues/29#issuecomment-494477985
      85             : const readBytesPeriod uint64 = 1 << 16
      86             : 
      87             : var errReversePrefixIteration = errors.New("pebble: unsupported reverse prefix iteration")
      88             : 
      89             : // IteratorMetrics holds per-iterator metrics. These do not change over the
      90             : // lifetime of the iterator.
      91             : type IteratorMetrics struct {
      92             :         // The read amplification experienced by this iterator. This is the sum of
      93             :         // the memtables, the L0 sublevels and the non-empty Ln levels. Higher read
      94             :         // amplification generally results in slower reads, though allowing higher
      95             :         // read amplification can also result in faster writes.
      96             :         ReadAmp int
      97             : }
      98             : 
      99             : // IteratorStatsKind describes the two kind of iterator stats.
     100             : type IteratorStatsKind int8
     101             : 
     102             : const (
     103             :         // InterfaceCall represents calls to Iterator.
     104             :         InterfaceCall IteratorStatsKind = iota
     105             :         // InternalIterCall represents calls by Iterator to its internalIterator.
     106             :         InternalIterCall
     107             :         // NumStatsKind is the number of kinds, and is used for array sizing.
     108             :         NumStatsKind
     109             : )
     110             : 
     111             : // IteratorStats contains iteration stats.
     112             : type IteratorStats struct {
     113             :         // ForwardSeekCount includes SeekGE, SeekPrefixGE, First.
     114             :         ForwardSeekCount [NumStatsKind]int
     115             :         // ReverseSeek includes SeekLT, Last.
     116             :         ReverseSeekCount [NumStatsKind]int
     117             :         // ForwardStepCount includes Next.
     118             :         ForwardStepCount [NumStatsKind]int
     119             :         // ReverseStepCount includes Prev.
     120             :         ReverseStepCount [NumStatsKind]int
     121             :         InternalStats    InternalIteratorStats
     122             :         RangeKeyStats    RangeKeyIteratorStats
     123             : }
     124             : 
     125             : var _ redact.SafeFormatter = &IteratorStats{}
     126             : 
     127             : // InternalIteratorStats contains miscellaneous stats produced by internal
     128             : // iterators.
     129             : type InternalIteratorStats = base.InternalIteratorStats
     130             : 
     131             : // RangeKeyIteratorStats contains miscellaneous stats about range keys
     132             : // encountered by the iterator.
     133             : type RangeKeyIteratorStats struct {
     134             :         // Count records the number of range keys encountered during
     135             :         // iteration. Range keys may be counted multiple times if the iterator
     136             :         // leaves a range key's bounds and then returns.
     137             :         Count int
     138             :         // ContainedPoints records the number of point keys encountered within the
     139             :         // bounds of a range key. Note that this includes point keys with suffixes
     140             :         // that sort both above and below the covering range key's suffix.
     141             :         ContainedPoints int
     142             :         // SkippedPoints records the count of the subset of ContainedPoints point
     143             :         // keys that were skipped during iteration due to range-key masking. It does
     144             :         // not include point keys that were never loaded because a
     145             :         // RangeKeyMasking.Filter excluded the entire containing block.
     146             :         SkippedPoints int
     147             : }
     148             : 
     149             : // Merge adds all of the argument's statistics to the receiver. It may be used
     150             : // to accumulate stats across multiple iterators.
     151           1 : func (s *RangeKeyIteratorStats) Merge(o RangeKeyIteratorStats) {
     152           1 :         s.Count += o.Count
     153           1 :         s.ContainedPoints += o.ContainedPoints
     154           1 :         s.SkippedPoints += o.SkippedPoints
     155           1 : }
     156             : 
     157             : // LazyValue is a lazy value. See the long comment in base.LazyValue.
     158             : type LazyValue = base.LazyValue
     159             : 
     160             : // Iterator iterates over a DB's key/value pairs in key order.
     161             : //
     162             : // An iterator must be closed after use, but it is not necessary to read an
     163             : // iterator until exhaustion.
     164             : //
     165             : // An iterator is not goroutine-safe, but it is safe to use multiple iterators
     166             : // concurrently, with each in a dedicated goroutine.
     167             : //
     168             : // It is also safe to use an iterator concurrently with modifying its
     169             : // underlying DB, if that DB permits modification. However, the resultant
     170             : // key/value pairs are not guaranteed to be a consistent snapshot of that DB
     171             : // at a particular point in time.
     172             : //
     173             : // If an iterator encounters an error during any operation, it is stored by
     174             : // the Iterator and surfaced through the Error method. All absolute
     175             : // positioning methods (eg, SeekLT, SeekGT, First, Last, etc) reset any
     176             : // accumulated error before positioning. All relative positioning methods (eg,
     177             : // Next, Prev) return without advancing if the iterator has an accumulated
     178             : // error.
     179             : type Iterator struct {
     180             :         // The context is stored here since (a) Iterators are expected to be
     181             :         // short-lived (since they pin memtables and sstables), (b) plumbing a
     182             :         // context into every method is very painful, (c) they do not (yet) respect
     183             :         // context cancellation and are only used for tracing.
     184             :         ctx       context.Context
     185             :         opts      IterOptions
     186             :         merge     Merge
     187             :         comparer  base.Comparer
     188             :         iter      internalIterator
     189             :         pointIter internalIterator
     190             :         // Either readState or version is set, but not both.
     191             :         readState *readState
     192             :         version   *version
     193             :         // rangeKey holds iteration state specific to iteration over range keys.
     194             :         // The range key field may be nil if the Iterator has never been configured
     195             :         // to iterate over range keys. Its non-nilness cannot be used to determine
     196             :         // if the Iterator is currently iterating over range keys: For that, consult
     197             :         // the IterOptions using opts.rangeKeys(). If non-nil, its rangeKeyIter
     198             :         // field is guaranteed to be non-nil too.
     199             :         rangeKey *iteratorRangeKeyState
     200             :         // rangeKeyMasking holds state for range-key masking of point keys.
     201             :         rangeKeyMasking rangeKeyMasking
     202             :         err             error
     203             :         // When iterValidityState=IterValid, key represents the current key, which
     204             :         // is backed by keyBuf.
     205             :         key    []byte
     206             :         keyBuf []byte
     207             :         value  LazyValue
     208             :         // For use in LazyValue.Clone.
     209             :         valueBuf []byte
     210             :         fetcher  base.LazyFetcher
     211             :         // For use in LazyValue.Value.
     212             :         lazyValueBuf []byte
     213             :         valueCloser  io.Closer
     214             :         // boundsBuf holds two buffers used to store the lower and upper bounds.
     215             :         // Whenever the Iterator's bounds change, the new bounds are copied into
     216             :         // boundsBuf[boundsBufIdx]. The two bounds share a slice to reduce
     217             :         // allocations. opts.LowerBound and opts.UpperBound point into this slice.
     218             :         boundsBuf    [2][]byte
     219             :         boundsBufIdx int
     220             :         // iterKey, iterValue reflect the latest position of iter, except when
     221             :         // SetBounds is called. In that case, these are explicitly set to nil.
     222             :         iterKey             *InternalKey
     223             :         iterValue           LazyValue
     224             :         alloc               *iterAlloc
     225             :         getIterAlloc        *getIterAlloc
     226             :         prefixOrFullSeekKey []byte
     227             :         readSampling        readSampling
     228             :         stats               IteratorStats
     229             :         externalReaders     [][]*sstable.Reader
     230             : 
     231             :         // Following fields used when constructing an iterator stack, eg, in Clone
     232             :         // and SetOptions or when re-fragmenting a batch's range keys/range dels.
     233             :         // Non-nil if this Iterator includes a Batch.
     234             :         batch            *Batch
     235             :         newIters         tableNewIters
     236             :         newIterRangeKey  keyspan.TableNewSpanIter
     237             :         lazyCombinedIter lazyCombinedIter
     238             :         seqNum           uint64
     239             :         // batchSeqNum is used by Iterators over indexed batches to detect when the
     240             :         // underlying batch has been mutated. The batch beneath an indexed batch may
     241             :         // be mutated while the Iterator is open, but new keys are not surfaced
     242             :         // until the next call to SetOptions.
     243             :         batchSeqNum uint64
     244             :         // batch{PointIter,RangeDelIter,RangeKeyIter} are used when the Iterator is
     245             :         // configured to read through an indexed batch. If a batch is set, these
     246             :         // iterators will be included within the iterator stack regardless of
     247             :         // whether the batch currently contains any keys of their kind. These
     248             :         // pointers are used during a call to SetOptions to refresh the Iterator's
     249             :         // view of its indexed batch.
     250             :         batchPointIter    batchIter
     251             :         batchRangeDelIter keyspan.Iter
     252             :         batchRangeKeyIter keyspan.Iter
     253             :         // merging is a pointer to this iterator's point merging iterator. It
     254             :         // appears here because key visibility is handled by the merging iterator.
     255             :         // During SetOptions on an iterator over an indexed batch, this field is
     256             :         // used to update the merging iterator's batch snapshot.
     257             :         merging *mergingIter
     258             : 
     259             :         // Keeping the bools here after all the 8 byte aligned fields shrinks the
     260             :         // sizeof this struct by 24 bytes.
     261             : 
     262             :         // INVARIANT:
     263             :         // iterValidityState==IterAtLimit <=>
     264             :         //  pos==iterPosCurForwardPaused || pos==iterPosCurReversePaused
     265             :         iterValidityState IterValidityState
     266             :         // Set to true by SetBounds, SetOptions. Causes the Iterator to appear
     267             :         // exhausted externally, while preserving the correct iterValidityState for
     268             :         // the iterator's internal state. Preserving the correct internal validity
     269             :         // is used for SeekPrefixGE(..., trySeekUsingNext), and SeekGE/SeekLT
     270             :         // optimizations after "no-op" calls to SetBounds and SetOptions.
     271             :         requiresReposition bool
     272             :         // The position of iter. When this is iterPos{Prev,Next} the iter has been
     273             :         // moved past the current key-value, which can only happen if
     274             :         // iterValidityState=IterValid, i.e., there is something to return to the
     275             :         // client for the current position.
     276             :         pos iterPos
     277             :         // Relates to the prefixOrFullSeekKey field above.
     278             :         hasPrefix bool
     279             :         // Used for deriving the value of SeekPrefixGE(..., trySeekUsingNext),
     280             :         // and SeekGE/SeekLT optimizations
     281             :         lastPositioningOp lastPositioningOpKind
     282             :         // Used for determining when it's safe to perform SeekGE optimizations that
     283             :         // reuse the iterator state to avoid the cost of a full seek if the iterator
     284             :         // is already positioned in the correct place. If the iterator's view of its
     285             :         // indexed batch was just refreshed, some optimizations cannot be applied on
     286             :         // the first seek after the refresh:
     287             :         // - SeekGE has a no-op optimization that does not seek on the internal
     288             :         //   iterator at all if the iterator is already in the correct place.
     289             :         //   This optimization cannot be performed if the internal iterator was
     290             :         //   last positioned when the iterator had a different view of an
     291             :         //   underlying batch.
     292             :         // - Seek[Prefix]GE set flags.TrySeekUsingNext()=true when the seek key is
     293             :         //   greater than the previous operation's seek key, under the expectation
     294             :         //   that the various internal iterators can use their current position to
     295             :         //   avoid a full expensive re-seek. This applies to the batchIter as well.
     296             :         //   However, if the view of the batch was just refreshed, the batchIter's
     297             :         //   position is not useful because it may already be beyond new keys less
     298             :         //   than the seek key. To prevent the use of this optimization in
     299             :         //   batchIter, Seek[Prefix]GE set flags.BatchJustRefreshed()=true if this
     300             :         //   bit is enabled.
     301             :         batchJustRefreshed bool
     302             :         // Used for an optimization in external iterators to reduce the number of
     303             :         // merging levels.
     304             :         forwardOnly bool
     305             :         // batchOnlyIter is set to true for Batch.NewBatchOnlyIter.
     306             :         batchOnlyIter bool
     307             :         // closePointIterOnce is set to true if this point iter can only be Close()d
     308             :         // once, _and_ closing i.iter and then i.pointIter would close i.pointIter
     309             :         // twice. This is necessary to track if the point iter is an internal iterator
     310             :         // that could release its resources to a pool on Close(), making it harder for
     311             :         // that iterator to make its own closes idempotent.
     312             :         //
     313             :         // TODO(bilal): Update SetOptions to always close out point key iterators when
     314             :         // they won't be used, so that Close() doesn't need to default to closing
     315             :         // point iterators twice.
     316             :         closePointIterOnce bool
     317             :         // Used in some tests to disable the random disabling of seek optimizations.
     318             :         forceEnableSeekOpt bool
     319             :         // Set to true if NextPrefix is not currently permitted. Defaults to false
     320             :         // in case an iterator never had any bounds.
     321             :         nextPrefixNotPermittedByUpperBound bool
     322             : }
     323             : 
     324             : // cmp is a convenience shorthand for the i.comparer.Compare function.
     325           1 : func (i *Iterator) cmp(a, b []byte) int {
     326           1 :         return i.comparer.Compare(a, b)
     327           1 : }
     328             : 
     329             : // split is a convenience shorthand for the i.comparer.Split function.
     330           1 : func (i *Iterator) split(a []byte) int {
     331           1 :         return i.comparer.Split(a)
     332           1 : }
     333             : 
     334             : // equal is a convenience shorthand for the i.comparer.Equal function.
     335           1 : func (i *Iterator) equal(a, b []byte) bool {
     336           1 :         return i.comparer.Equal(a, b)
     337           1 : }
     338             : 
     339             : // iteratorRangeKeyState holds an iterator's range key iteration state.
     340             : type iteratorRangeKeyState struct {
     341             :         opts  *IterOptions
     342             :         cmp   base.Compare
     343             :         split base.Split
     344             :         // rangeKeyIter holds the range key iterator stack that iterates over the
     345             :         // merged spans across the entirety of the LSM.
     346             :         rangeKeyIter keyspan.FragmentIterator
     347             :         iiter        keyspan.InterleavingIter
     348             :         // stale is set to true when the range key state recorded here (in start,
     349             :         // end and keys) may not be in sync with the current range key at the
     350             :         // interleaving iterator's current position.
     351             :         //
     352             :         // When the interelaving iterator passes over a new span, it invokes the
     353             :         // SpanChanged hook defined on the `rangeKeyMasking` type,  which sets stale
     354             :         // to true if the span is non-nil.
     355             :         //
     356             :         // The parent iterator may not be positioned over the interleaving
     357             :         // iterator's current position (eg, i.iterPos = iterPos{Next,Prev}), so
     358             :         // {keys,start,end} are only updated to the new range key during a call to
     359             :         // Iterator.saveRangeKey.
     360             :         stale bool
     361             :         // updated is used to signal to the Iterator client whether the state of
     362             :         // range keys has changed since the previous iterator position through the
     363             :         // `RangeKeyChanged` method. It's set to true during an Iterator positioning
     364             :         // operation that changes the state of the current range key. Each Iterator
     365             :         // positioning operation sets it back to false before executing.
     366             :         //
     367             :         // TODO(jackson): The lifecycle of {stale,updated,prevPosHadRangeKey} is
     368             :         // intricate and confusing. Try to refactor to reduce complexity.
     369             :         updated bool
     370             :         // prevPosHadRangeKey records whether the previous Iterator position had a
     371             :         // range key (HasPointAndRage() = (_, true)). It's updated at the beginning
     372             :         // of each new Iterator positioning operation. It's required by saveRangeKey to
     373             :         // to set `updated` appropriately: Without this record of the previous iterator
     374             :         // state, it's ambiguous whether an iterator only temporarily stepped onto a
     375             :         // position without a range key.
     376             :         prevPosHadRangeKey bool
     377             :         // rangeKeyOnly is set to true if at the current iterator position there is
     378             :         // no point key, only a range key start boundary.
     379             :         rangeKeyOnly bool
     380             :         // hasRangeKey is true when the current iterator position has a covering
     381             :         // range key (eg, a range key with bounds [<lower>,<upper>) such that
     382             :         // <lower> ≤ Key() < <upper>).
     383             :         hasRangeKey bool
     384             :         // start and end are the [start, end) boundaries of the current range keys.
     385             :         start []byte
     386             :         end   []byte
     387             : 
     388             :         rangeKeyBuffers
     389             : 
     390             :         // iterConfig holds fields that are used for the construction of the
     391             :         // iterator stack, but do not need to be directly accessed during iteration.
     392             :         // This struct is bundled within the iteratorRangeKeyState struct to reduce
     393             :         // allocations.
     394             :         iterConfig rangekey.UserIteratorConfig
     395             : }
     396             : 
     397             : type rangeKeyBuffers struct {
     398             :         // keys is sorted by Suffix ascending.
     399             :         keys []RangeKeyData
     400             :         // buf is used to save range-key data before moving the range-key iterator.
     401             :         // Start and end boundaries, suffixes and values are all copied into buf.
     402             :         buf bytealloc.A
     403             :         // internal holds buffers used by the range key internal iterators.
     404             :         internal rangekey.Buffers
     405             : }
     406             : 
     407           1 : func (b *rangeKeyBuffers) PrepareForReuse() {
     408           1 :         const maxKeysReuse = 100
     409           1 :         if len(b.keys) > maxKeysReuse {
     410           0 :                 b.keys = nil
     411           0 :         }
     412             :         // Avoid caching the key buf if it is overly large. The constant is
     413             :         // fairly arbitrary.
     414           1 :         if cap(b.buf) >= maxKeyBufCacheSize {
     415           0 :                 b.buf = nil
     416           1 :         } else {
     417           1 :                 b.buf = b.buf[:0]
     418           1 :         }
     419           1 :         b.internal.PrepareForReuse()
     420             : }
     421             : 
     422           1 : func (i *iteratorRangeKeyState) init(cmp base.Compare, split base.Split, opts *IterOptions) {
     423           1 :         i.cmp = cmp
     424           1 :         i.split = split
     425           1 :         i.opts = opts
     426           1 : }
     427             : 
     428             : var iterRangeKeyStateAllocPool = sync.Pool{
     429           1 :         New: func() interface{} {
     430           1 :                 return &iteratorRangeKeyState{}
     431           1 :         },
     432             : }
     433             : 
     434             : // isEphemeralPosition returns true iff the current iterator position is
     435             : // ephemeral, and won't be visited during subsequent relative positioning
     436             : // operations.
     437             : //
     438             : // The iterator position resulting from a SeekGE or SeekPrefixGE that lands on a
     439             : // straddling range key without a coincident point key is such a position.
     440           1 : func (i *Iterator) isEphemeralPosition() bool {
     441           1 :         return i.opts.rangeKeys() && i.rangeKey != nil && i.rangeKey.rangeKeyOnly &&
     442           1 :                 !i.equal(i.rangeKey.start, i.key)
     443           1 : }
     444             : 
     445             : type lastPositioningOpKind int8
     446             : 
     447             : const (
     448             :         unknownLastPositionOp lastPositioningOpKind = iota
     449             :         seekPrefixGELastPositioningOp
     450             :         seekGELastPositioningOp
     451             :         seekLTLastPositioningOp
     452             :         // internalNextOp is a special internal iterator positioning operation used
     453             :         // by CanDeterministicallySingleDelete. It exists for enforcing requirements
     454             :         // around calling CanDeterministicallySingleDelete at most once per external
     455             :         // iterator position.
     456             :         internalNextOp
     457             :         // invalidatedLastPositionOp is similar to unknownLastPositionOp and the
     458             :         // only reason to distinguish this is for the wider set of SeekGE
     459             :         // optimizations we permit for the external iterator Iterator.forwardOnly
     460             :         // case. Most code predicates should be doing equality comparisons with one
     461             :         // of the seek* enum values, so this duplication should not result in code
     462             :         // of the form:
     463             :         //  if unknownLastPositionOp || invalidLastPositionOp
     464             :         invalidatedLastPositionOp
     465             : )
     466             : 
     467             : // Limited iteration mode. Not for use with prefix iteration.
     468             : //
     469             : // SeekGE, SeekLT, Prev, Next have WithLimit variants, that pause the iterator
     470             : // at the limit in a best-effort manner. The client should behave correctly
     471             : // even if the limits are ignored. These limits are not "deep", in that they
     472             : // are not passed down to the underlying collection of internalIterators. This
     473             : // is because the limits are transient, and apply only until the next
     474             : // iteration call. They serve mainly as a way to bound the amount of work when
     475             : // two (or more) Iterators are being coordinated at a higher level.
     476             : //
     477             : // In limited iteration mode:
     478             : // - Avoid using Iterator.Valid if the last call was to a *WithLimit() method.
     479             : //   The return value from the *WithLimit() method provides a more precise
     480             : //   disposition.
     481             : // - The limit is exclusive for forward and inclusive for reverse.
     482             : //
     483             : //
     484             : // Limited iteration mode & range keys
     485             : //
     486             : // Limited iteration interacts with range-key iteration. When range key
     487             : // iteration is enabled, range keys are interleaved at their start boundaries.
     488             : // Limited iteration must ensure that if a range key exists within the limit,
     489             : // the iterator visits the range key.
     490             : //
     491             : // During forward limited iteration, this is trivial: An overlapping range key
     492             : // must have a start boundary less than the limit, and the range key's start
     493             : // boundary will be interleaved and found to be within the limit.
     494             : //
     495             : // During reverse limited iteration, the tail of the range key may fall within
     496             : // the limit. The range key must be surfaced even if the range key's start
     497             : // boundary is less than the limit, and if there are no point keys between the
     498             : // current iterator position and the limit. To provide this guarantee, reverse
     499             : // limited iteration ignores the limit as long as there is a range key
     500             : // overlapping the iteration position.
     501             : 
     502             : // IterValidityState captures the state of the Iterator.
     503             : type IterValidityState int8
     504             : 
     505             : const (
     506             :         // IterExhausted represents an Iterator that is exhausted.
     507             :         IterExhausted IterValidityState = iota
     508             :         // IterValid represents an Iterator that is valid.
     509             :         IterValid
     510             :         // IterAtLimit represents an Iterator that has a non-exhausted
     511             :         // internalIterator, but has reached a limit without any key for the
     512             :         // caller.
     513             :         IterAtLimit
     514             : )
     515             : 
     516             : // readSampling stores variables used to sample a read to trigger a read
     517             : // compaction
     518             : type readSampling struct {
     519             :         bytesUntilReadSampling uint64
     520             :         initialSamplePassed    bool
     521             :         pendingCompactions     readCompactionQueue
     522             :         // forceReadSampling is used for testing purposes to force a read sample on every
     523             :         // call to Iterator.maybeSampleRead()
     524             :         forceReadSampling bool
     525             : }
     526             : 
     527           1 : func (i *Iterator) findNextEntry(limit []byte) {
     528           1 :         i.iterValidityState = IterExhausted
     529           1 :         i.pos = iterPosCurForward
     530           1 :         if i.opts.rangeKeys() && i.rangeKey != nil {
     531           1 :                 i.rangeKey.rangeKeyOnly = false
     532           1 :         }
     533             : 
     534             :         // Close the closer for the current value if one was open.
     535           1 :         if i.closeValueCloser() != nil {
     536           0 :                 return
     537           0 :         }
     538             : 
     539           1 :         for i.iterKey != nil {
     540           1 :                 key := *i.iterKey
     541           1 : 
     542           1 :                 if i.hasPrefix {
     543           1 :                         if n := i.split(key.UserKey); !i.equal(i.prefixOrFullSeekKey, key.UserKey[:n]) {
     544           1 :                                 return
     545           1 :                         }
     546             :                 }
     547             :                 // Compare with limit every time we start at a different user key.
     548             :                 // Note that given the best-effort contract of limit, we could avoid a
     549             :                 // comparison in the common case by doing this only after
     550             :                 // i.nextUserKey is called for the deletes below. However that makes
     551             :                 // the behavior non-deterministic (since the behavior will vary based
     552             :                 // on what has been compacted), which makes it hard to test with the
     553             :                 // metamorphic test. So we forego that performance optimization.
     554           1 :                 if limit != nil && i.cmp(limit, i.iterKey.UserKey) <= 0 {
     555           1 :                         i.iterValidityState = IterAtLimit
     556           1 :                         i.pos = iterPosCurForwardPaused
     557           1 :                         return
     558           1 :                 }
     559             : 
     560             :                 // If the user has configured a SkipPoint function, invoke it to see
     561             :                 // whether we should skip over the current user key.
     562           1 :                 if i.opts.SkipPoint != nil && key.Kind() != InternalKeyKindRangeKeySet && i.opts.SkipPoint(i.iterKey.UserKey) {
     563           1 :                         // NB: We could call nextUserKey, but in some cases the SkipPoint
     564           1 :                         // predicate function might be cheaper than nextUserKey's key copy
     565           1 :                         // and key comparison. This should be the case for MVCC suffix
     566           1 :                         // comparisons, for example. In the future, we could expand the
     567           1 :                         // SkipPoint interface to give the implementor more control over
     568           1 :                         // whether we skip over just the internal key, the user key, or even
     569           1 :                         // the key prefix.
     570           1 :                         i.stats.ForwardStepCount[InternalIterCall]++
     571           1 :                         i.iterKey, i.iterValue = i.iter.Next()
     572           1 :                         continue
     573             :                 }
     574             : 
     575           1 :                 switch key.Kind() {
     576           1 :                 case InternalKeyKindRangeKeySet:
     577           1 :                         // Save the current key.
     578           1 :                         i.keyBuf = append(i.keyBuf[:0], key.UserKey...)
     579           1 :                         i.key = i.keyBuf
     580           1 :                         i.value = LazyValue{}
     581           1 :                         // There may also be a live point key at this userkey that we have
     582           1 :                         // not yet read. We need to find the next entry with this user key
     583           1 :                         // to find it. Save the range key so we don't lose it when we Next
     584           1 :                         // the underlying iterator.
     585           1 :                         i.saveRangeKey()
     586           1 :                         pointKeyExists := i.nextPointCurrentUserKey()
     587           1 :                         if i.err != nil {
     588           0 :                                 i.iterValidityState = IterExhausted
     589           0 :                                 return
     590           0 :                         }
     591           1 :                         i.rangeKey.rangeKeyOnly = !pointKeyExists
     592           1 :                         i.iterValidityState = IterValid
     593           1 :                         return
     594             : 
     595           1 :                 case InternalKeyKindDelete, InternalKeyKindSingleDelete, InternalKeyKindDeleteSized:
     596           1 :                         // NB: treating InternalKeyKindSingleDelete as equivalent to DEL is not
     597           1 :                         // only simpler, but is also necessary for correctness due to
     598           1 :                         // InternalKeyKindSSTableInternalObsoleteBit.
     599           1 :                         i.nextUserKey()
     600           1 :                         continue
     601             : 
     602           1 :                 case InternalKeyKindSet, InternalKeyKindSetWithDelete:
     603           1 :                         i.keyBuf = append(i.keyBuf[:0], key.UserKey...)
     604           1 :                         i.key = i.keyBuf
     605           1 :                         i.value = i.iterValue
     606           1 :                         i.iterValidityState = IterValid
     607           1 :                         i.saveRangeKey()
     608           1 :                         return
     609             : 
     610           1 :                 case InternalKeyKindMerge:
     611           1 :                         // Resolving the merge may advance us to the next point key, which
     612           1 :                         // may be covered by a different set of range keys. Save the range
     613           1 :                         // key state so we don't lose it.
     614           1 :                         i.saveRangeKey()
     615           1 :                         if i.mergeForward(key) {
     616           1 :                                 i.iterValidityState = IterValid
     617           1 :                                 return
     618           1 :                         }
     619             : 
     620             :                         // The merge didn't yield a valid key, either because the value
     621             :                         // merger indicated it should be deleted, or because an error was
     622             :                         // encountered.
     623           1 :                         i.iterValidityState = IterExhausted
     624           1 :                         if i.err != nil {
     625           0 :                                 return
     626           0 :                         }
     627           1 :                         if i.pos != iterPosNext {
     628           0 :                                 i.nextUserKey()
     629           0 :                         }
     630           1 :                         if i.closeValueCloser() != nil {
     631           0 :                                 return
     632           0 :                         }
     633           1 :                         i.pos = iterPosCurForward
     634             : 
     635           0 :                 default:
     636           0 :                         i.err = base.CorruptionErrorf("pebble: invalid internal key kind: %d", errors.Safe(key.Kind()))
     637           0 :                         i.iterValidityState = IterExhausted
     638           0 :                         return
     639             :                 }
     640             :         }
     641             : }
     642             : 
     643           1 : func (i *Iterator) nextPointCurrentUserKey() bool {
     644           1 :         // If the user has configured a SkipPoint function and the current user key
     645           1 :         // would be skipped by it, there's no need to step forward looking for a
     646           1 :         // point key. If we were to find one, it should be skipped anyways.
     647           1 :         if i.opts.SkipPoint != nil && i.opts.SkipPoint(i.key) {
     648           1 :                 return false
     649           1 :         }
     650             : 
     651           1 :         i.pos = iterPosCurForward
     652           1 : 
     653           1 :         i.iterKey, i.iterValue = i.iter.Next()
     654           1 :         i.stats.ForwardStepCount[InternalIterCall]++
     655           1 :         if i.iterKey == nil || !i.equal(i.key, i.iterKey.UserKey) {
     656           1 :                 i.pos = iterPosNext
     657           1 :                 return false
     658           1 :         }
     659             : 
     660           1 :         key := *i.iterKey
     661           1 :         switch key.Kind() {
     662           0 :         case InternalKeyKindRangeKeySet:
     663           0 :                 // RangeKeySets must always be interleaved as the first internal key
     664           0 :                 // for a user key.
     665           0 :                 i.err = base.CorruptionErrorf("pebble: unexpected range key set mid-user key")
     666           0 :                 return false
     667             : 
     668           1 :         case InternalKeyKindDelete, InternalKeyKindSingleDelete, InternalKeyKindDeleteSized:
     669           1 :                 // NB: treating InternalKeyKindSingleDelete as equivalent to DEL is not
     670           1 :                 // only simpler, but is also necessary for correctness due to
     671           1 :                 // InternalKeyKindSSTableInternalObsoleteBit.
     672           1 :                 return false
     673             : 
     674           1 :         case InternalKeyKindSet, InternalKeyKindSetWithDelete:
     675           1 :                 i.value = i.iterValue
     676           1 :                 return true
     677             : 
     678           1 :         case InternalKeyKindMerge:
     679           1 :                 return i.mergeForward(key)
     680             : 
     681           0 :         default:
     682           0 :                 i.err = base.CorruptionErrorf("pebble: invalid internal key kind: %d", errors.Safe(key.Kind()))
     683           0 :                 return false
     684             :         }
     685             : }
     686             : 
     687             : // mergeForward resolves a MERGE key, advancing the underlying iterator forward
     688             : // to merge with subsequent keys with the same userkey. mergeForward returns a
     689             : // boolean indicating whether or not the merge yielded a valid key. A merge may
     690             : // not yield a valid key if an error occurred, in which case i.err is non-nil,
     691             : // or the user's value merger specified the key to be deleted.
     692             : //
     693             : // mergeForward does not update iterValidityState.
     694           1 : func (i *Iterator) mergeForward(key base.InternalKey) (valid bool) {
     695           1 :         var iterValue []byte
     696           1 :         iterValue, _, i.err = i.iterValue.Value(nil)
     697           1 :         if i.err != nil {
     698           0 :                 return false
     699           0 :         }
     700           1 :         var valueMerger ValueMerger
     701           1 :         valueMerger, i.err = i.merge(key.UserKey, iterValue)
     702           1 :         if i.err != nil {
     703           0 :                 return false
     704           0 :         }
     705             : 
     706           1 :         i.mergeNext(key, valueMerger)
     707           1 :         if i.err != nil {
     708           0 :                 return false
     709           0 :         }
     710             : 
     711           1 :         var needDelete bool
     712           1 :         var value []byte
     713           1 :         value, needDelete, i.valueCloser, i.err = finishValueMerger(
     714           1 :                 valueMerger, true /* includesBase */)
     715           1 :         i.value = base.MakeInPlaceValue(value)
     716           1 :         if i.err != nil {
     717           0 :                 return false
     718           0 :         }
     719           1 :         if needDelete {
     720           1 :                 _ = i.closeValueCloser()
     721           1 :                 return false
     722           1 :         }
     723           1 :         return true
     724             : }
     725             : 
     726           1 : func (i *Iterator) closeValueCloser() error {
     727           1 :         if i.valueCloser != nil {
     728           0 :                 i.err = i.valueCloser.Close()
     729           0 :                 i.valueCloser = nil
     730           0 :         }
     731           1 :         return i.err
     732             : }
     733             : 
     734           1 : func (i *Iterator) nextUserKey() {
     735           1 :         if i.iterKey == nil {
     736           1 :                 return
     737           1 :         }
     738           1 :         trailer := i.iterKey.Trailer
     739           1 :         done := i.iterKey.Trailer <= base.InternalKeyZeroSeqnumMaxTrailer
     740           1 :         if i.iterValidityState != IterValid {
     741           1 :                 i.keyBuf = append(i.keyBuf[:0], i.iterKey.UserKey...)
     742           1 :                 i.key = i.keyBuf
     743           1 :         }
     744           1 :         for {
     745           1 :                 i.iterKey, i.iterValue = i.iter.Next()
     746           1 :                 i.stats.ForwardStepCount[InternalIterCall]++
     747           1 :                 // NB: We're guaranteed to be on the next user key if the previous key
     748           1 :                 // had a zero sequence number (`done`), or the new key has a trailer
     749           1 :                 // greater or equal to the previous key's trailer. This is true because
     750           1 :                 // internal keys with the same user key are sorted by Trailer in
     751           1 :                 // strictly monotonically descending order. We expect the trailer
     752           1 :                 // optimization to trigger around 50% of the time with randomly
     753           1 :                 // distributed writes. We expect it to trigger very frequently when
     754           1 :                 // iterating through ingested sstables, which contain keys that all have
     755           1 :                 // the same sequence number.
     756           1 :                 if done || i.iterKey == nil || i.iterKey.Trailer >= trailer {
     757           1 :                         break
     758             :                 }
     759           1 :                 if !i.equal(i.key, i.iterKey.UserKey) {
     760           1 :                         break
     761             :                 }
     762           1 :                 done = i.iterKey.Trailer <= base.InternalKeyZeroSeqnumMaxTrailer
     763           1 :                 trailer = i.iterKey.Trailer
     764             :         }
     765             : }
     766             : 
     767           1 : func (i *Iterator) maybeSampleRead() {
     768           1 :         // This method is only called when a public method of Iterator is
     769           1 :         // returning, and below we exclude the case were the iterator is paused at
     770           1 :         // a limit. The effect of these choices is that keys that are deleted, but
     771           1 :         // are encountered during iteration, are not accounted for in the read
     772           1 :         // sampling and will not cause read driven compactions, even though we are
     773           1 :         // incurring cost in iterating over them. And this issue is not limited to
     774           1 :         // Iterator, which does not see the effect of range deletes, which may be
     775           1 :         // causing iteration work in mergingIter. It is not clear at this time
     776           1 :         // whether this is a deficiency worth addressing.
     777           1 :         if i.iterValidityState != IterValid {
     778           1 :                 return
     779           1 :         }
     780           1 :         if i.readState == nil {
     781           1 :                 return
     782           1 :         }
     783           1 :         if i.readSampling.forceReadSampling {
     784           1 :                 i.sampleRead()
     785           1 :                 return
     786           1 :         }
     787           1 :         samplingPeriod := int32(int64(readBytesPeriod) * i.readState.db.opts.Experimental.ReadSamplingMultiplier)
     788           1 :         if samplingPeriod <= 0 {
     789           0 :                 return
     790           0 :         }
     791           1 :         bytesRead := uint64(len(i.key) + i.value.Len())
     792           1 :         for i.readSampling.bytesUntilReadSampling < bytesRead {
     793           1 :                 i.readSampling.bytesUntilReadSampling += uint64(fastrand.Uint32n(2 * uint32(samplingPeriod)))
     794           1 :                 // The block below tries to adjust for the case where this is the
     795           1 :                 // first read in a newly-opened iterator. As bytesUntilReadSampling
     796           1 :                 // starts off at zero, we don't want to sample the first read of
     797           1 :                 // every newly-opened iterator, but we do want to sample some of them.
     798           1 :                 if !i.readSampling.initialSamplePassed {
     799           1 :                         i.readSampling.initialSamplePassed = true
     800           1 :                         if fastrand.Uint32n(uint32(i.readSampling.bytesUntilReadSampling)) > uint32(bytesRead) {
     801           1 :                                 continue
     802             :                         }
     803             :                 }
     804           1 :                 i.sampleRead()
     805             :         }
     806           1 :         i.readSampling.bytesUntilReadSampling -= bytesRead
     807             : }
     808             : 
     809           1 : func (i *Iterator) sampleRead() {
     810           1 :         var topFile *manifest.FileMetadata
     811           1 :         topLevel, numOverlappingLevels := numLevels, 0
     812           1 :         mi := i.merging
     813           1 :         if mi == nil {
     814           1 :                 return
     815           1 :         }
     816           1 :         if len(mi.levels) > 1 {
     817           1 :                 mi.ForEachLevelIter(func(li *levelIter) bool {
     818           1 :                         l := manifest.LevelToInt(li.level)
     819           1 :                         if f := li.iterFile; f != nil {
     820           1 :                                 var containsKey bool
     821           1 :                                 if i.pos == iterPosNext || i.pos == iterPosCurForward ||
     822           1 :                                         i.pos == iterPosCurForwardPaused {
     823           1 :                                         containsKey = i.cmp(f.SmallestPointKey.UserKey, i.key) <= 0
     824           1 :                                 } else if i.pos == iterPosPrev || i.pos == iterPosCurReverse ||
     825           1 :                                         i.pos == iterPosCurReversePaused {
     826           1 :                                         containsKey = i.cmp(f.LargestPointKey.UserKey, i.key) >= 0
     827           1 :                                 }
     828             :                                 // Do nothing if the current key is not contained in f's
     829             :                                 // bounds. We could seek the LevelIterator at this level
     830             :                                 // to find the right file, but the performance impacts of
     831             :                                 // doing that are significant enough to negate the benefits
     832             :                                 // of read sampling in the first place. See the discussion
     833             :                                 // at:
     834             :                                 // https://github.com/cockroachdb/pebble/pull/1041#issuecomment-763226492
     835           1 :                                 if containsKey {
     836           1 :                                         numOverlappingLevels++
     837           1 :                                         if numOverlappingLevels >= 2 {
     838           1 :                                                 // Terminate the loop early if at least 2 overlapping levels are found.
     839           1 :                                                 return true
     840           1 :                                         }
     841           1 :                                         topLevel = l
     842           1 :                                         topFile = f
     843             :                                 }
     844             :                         }
     845           1 :                         return false
     846             :                 })
     847             :         }
     848           1 :         if topFile == nil || topLevel >= numLevels {
     849           1 :                 return
     850           1 :         }
     851           1 :         if numOverlappingLevels >= 2 {
     852           1 :                 allowedSeeks := topFile.AllowedSeeks.Add(-1)
     853           1 :                 if allowedSeeks == 0 {
     854           1 : 
     855           1 :                         // Since the compaction queue can handle duplicates, we can keep
     856           1 :                         // adding to the queue even once allowedSeeks hits 0.
     857           1 :                         // In fact, we NEED to keep adding to the queue, because the queue
     858           1 :                         // is small and evicts older and possibly useful compactions.
     859           1 :                         topFile.AllowedSeeks.Add(topFile.InitAllowedSeeks)
     860           1 : 
     861           1 :                         read := readCompaction{
     862           1 :                                 start:   topFile.SmallestPointKey.UserKey,
     863           1 :                                 end:     topFile.LargestPointKey.UserKey,
     864           1 :                                 level:   topLevel,
     865           1 :                                 fileNum: topFile.FileNum,
     866           1 :                         }
     867           1 :                         i.readSampling.pendingCompactions.add(&read, i.cmp)
     868           1 :                 }
     869             :         }
     870             : }
     871             : 
     872           1 : func (i *Iterator) findPrevEntry(limit []byte) {
     873           1 :         i.iterValidityState = IterExhausted
     874           1 :         i.pos = iterPosCurReverse
     875           1 :         if i.opts.rangeKeys() && i.rangeKey != nil {
     876           1 :                 i.rangeKey.rangeKeyOnly = false
     877           1 :         }
     878             : 
     879             :         // Close the closer for the current value if one was open.
     880           1 :         if i.valueCloser != nil {
     881           0 :                 i.err = i.valueCloser.Close()
     882           0 :                 i.valueCloser = nil
     883           0 :                 if i.err != nil {
     884           0 :                         i.iterValidityState = IterExhausted
     885           0 :                         return
     886           0 :                 }
     887             :         }
     888             : 
     889           1 :         var valueMerger ValueMerger
     890           1 :         firstLoopIter := true
     891           1 :         rangeKeyBoundary := false
     892           1 :         // The code below compares with limit in multiple places. As documented in
     893           1 :         // findNextEntry, this is being done to make the behavior of limit
     894           1 :         // deterministic to allow for metamorphic testing. It is not required by
     895           1 :         // the best-effort contract of limit.
     896           1 :         for i.iterKey != nil {
     897           1 :                 key := *i.iterKey
     898           1 : 
     899           1 :                 // NB: We cannot pause if the current key is covered by a range key.
     900           1 :                 // Otherwise, the user might not ever learn of a range key that covers
     901           1 :                 // the key space being iterated over in which there are no point keys.
     902           1 :                 // Since limits are best effort, ignoring the limit in this case is
     903           1 :                 // allowed by the contract of limit.
     904           1 :                 if firstLoopIter && limit != nil && i.cmp(limit, i.iterKey.UserKey) > 0 && !i.rangeKeyWithinLimit(limit) {
     905           1 :                         i.iterValidityState = IterAtLimit
     906           1 :                         i.pos = iterPosCurReversePaused
     907           1 :                         return
     908           1 :                 }
     909           1 :                 firstLoopIter = false
     910           1 : 
     911           1 :                 if i.iterValidityState == IterValid {
     912           1 :                         if !i.equal(key.UserKey, i.key) {
     913           1 :                                 // We've iterated to the previous user key.
     914           1 :                                 i.pos = iterPosPrev
     915           1 :                                 if valueMerger != nil {
     916           1 :                                         var needDelete bool
     917           1 :                                         var value []byte
     918           1 :                                         value, needDelete, i.valueCloser, i.err = finishValueMerger(valueMerger, true /* includesBase */)
     919           1 :                                         i.value = base.MakeInPlaceValue(value)
     920           1 :                                         if i.err == nil && needDelete {
     921           1 :                                                 // The point key at this key is deleted. If we also have
     922           1 :                                                 // a range key boundary at this key, we still want to
     923           1 :                                                 // return. Otherwise, we need to continue looking for
     924           1 :                                                 // a live key.
     925           1 :                                                 i.value = LazyValue{}
     926           1 :                                                 if rangeKeyBoundary {
     927           0 :                                                         i.rangeKey.rangeKeyOnly = true
     928           1 :                                                 } else {
     929           1 :                                                         i.iterValidityState = IterExhausted
     930           1 :                                                         if i.closeValueCloser() == nil {
     931           1 :                                                                 continue
     932             :                                                         }
     933             :                                                 }
     934             :                                         }
     935             :                                 }
     936           1 :                                 if i.err != nil {
     937           0 :                                         i.iterValidityState = IterExhausted
     938           0 :                                 }
     939           1 :                                 return
     940             :                         }
     941             :                 }
     942             : 
     943             :                 // If the user has configured a SkipPoint function, invoke it to see
     944             :                 // whether we should skip over the current user key.
     945           1 :                 if i.opts.SkipPoint != nil && key.Kind() != InternalKeyKindRangeKeySet && i.opts.SkipPoint(key.UserKey) {
     946           1 :                         // NB: We could call prevUserKey, but in some cases the SkipPoint
     947           1 :                         // predicate function might be cheaper than prevUserKey's key copy
     948           1 :                         // and key comparison. This should be the case for MVCC suffix
     949           1 :                         // comparisons, for example. In the future, we could expand the
     950           1 :                         // SkipPoint interface to give the implementor more control over
     951           1 :                         // whether we skip over just the internal key, the user key, or even
     952           1 :                         // the key prefix.
     953           1 :                         i.stats.ReverseStepCount[InternalIterCall]++
     954           1 :                         i.iterKey, i.iterValue = i.iter.Prev()
     955           1 :                         if limit != nil && i.iterKey != nil && i.cmp(limit, i.iterKey.UserKey) > 0 && !i.rangeKeyWithinLimit(limit) {
     956           1 :                                 i.iterValidityState = IterAtLimit
     957           1 :                                 i.pos = iterPosCurReversePaused
     958           1 :                                 return
     959           1 :                         }
     960           1 :                         continue
     961             :                 }
     962             : 
     963           1 :                 switch key.Kind() {
     964           1 :                 case InternalKeyKindRangeKeySet:
     965           1 :                         // Range key start boundary markers are interleaved with the maximum
     966           1 :                         // sequence number, so if there's a point key also at this key, we
     967           1 :                         // must've already iterated over it.
     968           1 :                         // This is the final entry at this user key, so we may return
     969           1 :                         i.rangeKey.rangeKeyOnly = i.iterValidityState != IterValid
     970           1 :                         i.keyBuf = append(i.keyBuf[:0], key.UserKey...)
     971           1 :                         i.key = i.keyBuf
     972           1 :                         i.iterValidityState = IterValid
     973           1 :                         i.saveRangeKey()
     974           1 :                         // In all other cases, previous iteration requires advancing to
     975           1 :                         // iterPosPrev in order to determine if the key is live and
     976           1 :                         // unshadowed by another key at the same user key. In this case,
     977           1 :                         // because range key start boundary markers are always interleaved
     978           1 :                         // at the maximum sequence number, we know that there aren't any
     979           1 :                         // additional keys with the same user key in the backward direction.
     980           1 :                         //
     981           1 :                         // We Prev the underlying iterator once anyways for consistency, so
     982           1 :                         // that we can maintain the invariant during backward iteration that
     983           1 :                         // i.iterPos = iterPosPrev.
     984           1 :                         i.stats.ReverseStepCount[InternalIterCall]++
     985           1 :                         i.iterKey, i.iterValue = i.iter.Prev()
     986           1 : 
     987           1 :                         // Set rangeKeyBoundary so that on the next iteration, we know to
     988           1 :                         // return the key even if the MERGE point key is deleted.
     989           1 :                         rangeKeyBoundary = true
     990             : 
     991           1 :                 case InternalKeyKindDelete, InternalKeyKindSingleDelete, InternalKeyKindDeleteSized:
     992           1 :                         i.value = LazyValue{}
     993           1 :                         i.iterValidityState = IterExhausted
     994           1 :                         valueMerger = nil
     995           1 :                         i.iterKey, i.iterValue = i.iter.Prev()
     996           1 :                         i.stats.ReverseStepCount[InternalIterCall]++
     997           1 :                         // Compare with the limit. We could optimize by only checking when
     998           1 :                         // we step to the previous user key, but detecting that requires a
     999           1 :                         // comparison too. Note that this position may already passed a
    1000           1 :                         // number of versions of this user key, but they are all deleted, so
    1001           1 :                         // the fact that a subsequent Prev*() call will not see them is
    1002           1 :                         // harmless. Also note that this is the only place in the loop,
    1003           1 :                         // other than the firstLoopIter and SkipPoint cases above, where we
    1004           1 :                         // could step to a different user key and start processing it for
    1005           1 :                         // returning to the caller.
    1006           1 :                         if limit != nil && i.iterKey != nil && i.cmp(limit, i.iterKey.UserKey) > 0 && !i.rangeKeyWithinLimit(limit) {
    1007           1 :                                 i.iterValidityState = IterAtLimit
    1008           1 :                                 i.pos = iterPosCurReversePaused
    1009           1 :                                 return
    1010           1 :                         }
    1011           1 :                         continue
    1012             : 
    1013           1 :                 case InternalKeyKindSet, InternalKeyKindSetWithDelete:
    1014           1 :                         i.keyBuf = append(i.keyBuf[:0], key.UserKey...)
    1015           1 :                         i.key = i.keyBuf
    1016           1 :                         // iterValue is owned by i.iter and could change after the Prev()
    1017           1 :                         // call, so use valueBuf instead. Note that valueBuf is only used
    1018           1 :                         // in this one instance; everywhere else (eg. in findNextEntry),
    1019           1 :                         // we just point i.value to the unsafe i.iter-owned value buffer.
    1020           1 :                         i.value, i.valueBuf = i.iterValue.Clone(i.valueBuf[:0], &i.fetcher)
    1021           1 :                         i.saveRangeKey()
    1022           1 :                         i.iterValidityState = IterValid
    1023           1 :                         i.iterKey, i.iterValue = i.iter.Prev()
    1024           1 :                         i.stats.ReverseStepCount[InternalIterCall]++
    1025           1 :                         valueMerger = nil
    1026           1 :                         continue
    1027             : 
    1028           1 :                 case InternalKeyKindMerge:
    1029           1 :                         if i.iterValidityState == IterExhausted {
    1030           1 :                                 i.keyBuf = append(i.keyBuf[:0], key.UserKey...)
    1031           1 :                                 i.key = i.keyBuf
    1032           1 :                                 i.saveRangeKey()
    1033           1 :                                 var iterValue []byte
    1034           1 :                                 iterValue, _, i.err = i.iterValue.Value(nil)
    1035           1 :                                 if i.err != nil {
    1036           0 :                                         return
    1037           0 :                                 }
    1038           1 :                                 valueMerger, i.err = i.merge(i.key, iterValue)
    1039           1 :                                 if i.err != nil {
    1040           0 :                                         return
    1041           0 :                                 }
    1042           1 :                                 i.iterValidityState = IterValid
    1043           1 :                         } else if valueMerger == nil {
    1044           1 :                                 // Extract value before iterValue since we use value before iterValue
    1045           1 :                                 // and the underlying iterator is not required to provide backing
    1046           1 :                                 // memory for both simultaneously.
    1047           1 :                                 var value []byte
    1048           1 :                                 var callerOwned bool
    1049           1 :                                 value, callerOwned, i.err = i.value.Value(i.lazyValueBuf)
    1050           1 :                                 if callerOwned {
    1051           0 :                                         i.lazyValueBuf = value[:0]
    1052           0 :                                 }
    1053           1 :                                 if i.err != nil {
    1054           0 :                                         return
    1055           0 :                                 }
    1056           1 :                                 valueMerger, i.err = i.merge(i.key, value)
    1057           1 :                                 var iterValue []byte
    1058           1 :                                 iterValue, _, i.err = i.iterValue.Value(nil)
    1059           1 :                                 if i.err != nil {
    1060           0 :                                         return
    1061           0 :                                 }
    1062           1 :                                 if i.err == nil {
    1063           1 :                                         i.err = valueMerger.MergeNewer(iterValue)
    1064           1 :                                 }
    1065           1 :                                 if i.err != nil {
    1066           0 :                                         i.iterValidityState = IterExhausted
    1067           0 :                                         return
    1068           0 :                                 }
    1069           1 :                         } else {
    1070           1 :                                 var iterValue []byte
    1071           1 :                                 iterValue, _, i.err = i.iterValue.Value(nil)
    1072           1 :                                 if i.err != nil {
    1073           0 :                                         return
    1074           0 :                                 }
    1075           1 :                                 i.err = valueMerger.MergeNewer(iterValue)
    1076           1 :                                 if i.err != nil {
    1077           0 :                                         i.iterValidityState = IterExhausted
    1078           0 :                                         return
    1079           0 :                                 }
    1080             :                         }
    1081           1 :                         i.iterKey, i.iterValue = i.iter.Prev()
    1082           1 :                         i.stats.ReverseStepCount[InternalIterCall]++
    1083           1 :                         continue
    1084             : 
    1085           0 :                 default:
    1086           0 :                         i.err = base.CorruptionErrorf("pebble: invalid internal key kind: %d", errors.Safe(key.Kind()))
    1087           0 :                         i.iterValidityState = IterExhausted
    1088           0 :                         return
    1089             :                 }
    1090             :         }
    1091             : 
    1092             :         // i.iterKey == nil, so broke out of the preceding loop.
    1093           1 :         if i.iterValidityState == IterValid {
    1094           1 :                 i.pos = iterPosPrev
    1095           1 :                 if valueMerger != nil {
    1096           1 :                         var needDelete bool
    1097           1 :                         var value []byte
    1098           1 :                         value, needDelete, i.valueCloser, i.err = finishValueMerger(valueMerger, true /* includesBase */)
    1099           1 :                         i.value = base.MakeInPlaceValue(value)
    1100           1 :                         if i.err == nil && needDelete {
    1101           1 :                                 i.key = nil
    1102           1 :                                 i.value = LazyValue{}
    1103           1 :                                 i.iterValidityState = IterExhausted
    1104           1 :                         }
    1105             :                 }
    1106           1 :                 if i.err != nil {
    1107           0 :                         i.iterValidityState = IterExhausted
    1108           0 :                 }
    1109             :         }
    1110             : }
    1111             : 
    1112           1 : func (i *Iterator) prevUserKey() {
    1113           1 :         if i.iterKey == nil {
    1114           1 :                 return
    1115           1 :         }
    1116           1 :         if i.iterValidityState != IterValid {
    1117           1 :                 // If we're going to compare against the prev key, we need to save the
    1118           1 :                 // current key.
    1119           1 :                 i.keyBuf = append(i.keyBuf[:0], i.iterKey.UserKey...)
    1120           1 :                 i.key = i.keyBuf
    1121           1 :         }
    1122           1 :         for {
    1123           1 :                 i.iterKey, i.iterValue = i.iter.Prev()
    1124           1 :                 i.stats.ReverseStepCount[InternalIterCall]++
    1125           1 :                 if i.iterKey == nil {
    1126           1 :                         break
    1127             :                 }
    1128           1 :                 if !i.equal(i.key, i.iterKey.UserKey) {
    1129           1 :                         break
    1130             :                 }
    1131             :         }
    1132             : }
    1133             : 
    1134           1 : func (i *Iterator) mergeNext(key InternalKey, valueMerger ValueMerger) {
    1135           1 :         // Save the current key.
    1136           1 :         i.keyBuf = append(i.keyBuf[:0], key.UserKey...)
    1137           1 :         i.key = i.keyBuf
    1138           1 : 
    1139           1 :         // Loop looking for older values for this key and merging them.
    1140           1 :         for {
    1141           1 :                 i.iterKey, i.iterValue = i.iter.Next()
    1142           1 :                 i.stats.ForwardStepCount[InternalIterCall]++
    1143           1 :                 if i.iterKey == nil {
    1144           1 :                         i.pos = iterPosNext
    1145           1 :                         return
    1146           1 :                 }
    1147           1 :                 key = *i.iterKey
    1148           1 :                 if !i.equal(i.key, key.UserKey) {
    1149           1 :                         // We've advanced to the next key.
    1150           1 :                         i.pos = iterPosNext
    1151           1 :                         return
    1152           1 :                 }
    1153           1 :                 switch key.Kind() {
    1154           1 :                 case InternalKeyKindDelete, InternalKeyKindSingleDelete, InternalKeyKindDeleteSized:
    1155           1 :                         // We've hit a deletion tombstone. Return everything up to this
    1156           1 :                         // point.
    1157           1 :                         //
    1158           1 :                         // NB: treating InternalKeyKindSingleDelete as equivalent to DEL is not
    1159           1 :                         // only simpler, but is also necessary for correctness due to
    1160           1 :                         // InternalKeyKindSSTableInternalObsoleteBit.
    1161           1 :                         return
    1162             : 
    1163           1 :                 case InternalKeyKindSet, InternalKeyKindSetWithDelete:
    1164           1 :                         // We've hit a Set value. Merge with the existing value and return.
    1165           1 :                         var iterValue []byte
    1166           1 :                         iterValue, _, i.err = i.iterValue.Value(nil)
    1167           1 :                         if i.err != nil {
    1168           0 :                                 return
    1169           0 :                         }
    1170           1 :                         i.err = valueMerger.MergeOlder(iterValue)
    1171           1 :                         return
    1172             : 
    1173           1 :                 case InternalKeyKindMerge:
    1174           1 :                         // We've hit another Merge value. Merge with the existing value and
    1175           1 :                         // continue looping.
    1176           1 :                         var iterValue []byte
    1177           1 :                         iterValue, _, i.err = i.iterValue.Value(nil)
    1178           1 :                         if i.err != nil {
    1179           0 :                                 return
    1180           0 :                         }
    1181           1 :                         i.err = valueMerger.MergeOlder(iterValue)
    1182           1 :                         if i.err != nil {
    1183           0 :                                 return
    1184           0 :                         }
    1185           1 :                         continue
    1186             : 
    1187           0 :                 case InternalKeyKindRangeKeySet:
    1188           0 :                         // The RANGEKEYSET marker must sort before a MERGE at the same user key.
    1189           0 :                         i.err = base.CorruptionErrorf("pebble: out of order range key marker")
    1190           0 :                         return
    1191             : 
    1192           0 :                 default:
    1193           0 :                         i.err = base.CorruptionErrorf("pebble: invalid internal key kind: %d", errors.Safe(key.Kind()))
    1194           0 :                         return
    1195             :                 }
    1196             :         }
    1197             : }
    1198             : 
    1199             : // SeekGE moves the iterator to the first key/value pair whose key is greater
    1200             : // than or equal to the given key. Returns true if the iterator is pointing at
    1201             : // a valid entry and false otherwise.
    1202           1 : func (i *Iterator) SeekGE(key []byte) bool {
    1203           1 :         return i.SeekGEWithLimit(key, nil) == IterValid
    1204           1 : }
    1205             : 
    1206             : // SeekGEWithLimit moves the iterator to the first key/value pair whose key is
    1207             : // greater than or equal to the given key.
    1208             : //
    1209             : // If limit is provided, it serves as a best-effort exclusive limit. If the
    1210             : // first key greater than or equal to the given search key is also greater than
    1211             : // or equal to limit, the Iterator may pause and return IterAtLimit. Because
    1212             : // limits are best-effort, SeekGEWithLimit may return a key beyond limit.
    1213             : //
    1214             : // If the Iterator is configured to iterate over range keys, SeekGEWithLimit
    1215             : // guarantees it will surface any range keys with bounds overlapping the
    1216             : // keyspace [key, limit).
    1217           1 : func (i *Iterator) SeekGEWithLimit(key []byte, limit []byte) IterValidityState {
    1218           1 :         if i.rangeKey != nil {
    1219           1 :                 // NB: Check Valid() before clearing requiresReposition.
    1220           1 :                 i.rangeKey.prevPosHadRangeKey = i.rangeKey.hasRangeKey && i.Valid()
    1221           1 :                 // If we have a range key but did not expose it at the previous iterator
    1222           1 :                 // position (because the iterator was not at a valid position), updated
    1223           1 :                 // must be true. This ensures that after an iterator op sequence like:
    1224           1 :                 //   - Next()             → (IterValid, RangeBounds() = [a,b))
    1225           1 :                 //   - NextWithLimit(...) → (IterAtLimit, RangeBounds() = -)
    1226           1 :                 //   - SeekGE(...)        → (IterValid, RangeBounds() = [a,b))
    1227           1 :                 // the iterator returns RangeKeyChanged()=true.
    1228           1 :                 //
    1229           1 :                 // The remainder of this function will only update i.rangeKey.updated if
    1230           1 :                 // the iterator moves into a new range key, or out of the current range
    1231           1 :                 // key.
    1232           1 :                 i.rangeKey.updated = i.rangeKey.hasRangeKey && !i.Valid() && i.opts.rangeKeys()
    1233           1 :         }
    1234           1 :         lastPositioningOp := i.lastPositioningOp
    1235           1 :         hasPrefix := i.hasPrefix
    1236           1 :         // Set it to unknown, since this operation may not succeed, in which case
    1237           1 :         // the SeekGE following this should not make any assumption about iterator
    1238           1 :         // position.
    1239           1 :         i.lastPositioningOp = unknownLastPositionOp
    1240           1 :         i.requiresReposition = false
    1241           1 :         i.err = nil // clear cached iteration error
    1242           1 :         i.hasPrefix = false
    1243           1 :         i.stats.ForwardSeekCount[InterfaceCall]++
    1244           1 :         if lowerBound := i.opts.GetLowerBound(); lowerBound != nil && i.cmp(key, lowerBound) < 0 {
    1245           1 :                 key = lowerBound
    1246           1 :         } else if upperBound := i.opts.GetUpperBound(); upperBound != nil && i.cmp(key, upperBound) > 0 {
    1247           1 :                 key = upperBound
    1248           1 :         }
    1249           1 :         seekInternalIter := true
    1250           1 : 
    1251           1 :         var flags base.SeekGEFlags
    1252           1 :         if i.batchJustRefreshed {
    1253           1 :                 i.batchJustRefreshed = false
    1254           1 :                 flags = flags.EnableBatchJustRefreshed()
    1255           1 :         }
    1256           1 :         if lastPositioningOp == seekGELastPositioningOp {
    1257           1 :                 cmp := i.cmp(i.prefixOrFullSeekKey, key)
    1258           1 :                 // If this seek is to the same or later key, and the iterator is
    1259           1 :                 // already positioned there, this is a noop. This can be helpful for
    1260           1 :                 // sparse key spaces that have many deleted keys, where one can avoid
    1261           1 :                 // the overhead of iterating past them again and again.
    1262           1 :                 if cmp <= 0 {
    1263           1 :                         if !flags.BatchJustRefreshed() &&
    1264           1 :                                 (i.iterValidityState == IterExhausted ||
    1265           1 :                                         (i.iterValidityState == IterValid && i.cmp(key, i.key) <= 0 &&
    1266           1 :                                                 (limit == nil || i.cmp(i.key, limit) < 0))) {
    1267           1 :                                 // Noop
    1268           1 :                                 if !invariants.Enabled || !disableSeekOpt(key, uintptr(unsafe.Pointer(i))) || i.forceEnableSeekOpt {
    1269           1 :                                         i.lastPositioningOp = seekGELastPositioningOp
    1270           1 :                                         return i.iterValidityState
    1271           1 :                                 }
    1272             :                         }
    1273             :                         // cmp == 0 is not safe to optimize since
    1274             :                         // - i.pos could be at iterPosNext, due to a merge.
    1275             :                         // - Even if i.pos were at iterPosCurForward, we could have a DELETE,
    1276             :                         //   SET pair for a key, and the iterator would have moved past DELETE
    1277             :                         //   but stayed at iterPosCurForward. A similar situation occurs for a
    1278             :                         //   MERGE, SET pair where the MERGE is consumed and the iterator is
    1279             :                         //   at the SET.
    1280             :                         // We also leverage the IterAtLimit <=> i.pos invariant defined in the
    1281             :                         // comment on iterValidityState, to exclude any cases where i.pos
    1282             :                         // is iterPosCur{Forward,Reverse}Paused. This avoids the need to
    1283             :                         // special-case those iterator positions and their interactions with
    1284             :                         // TrySeekUsingNext, as the main uses for TrySeekUsingNext in CockroachDB
    1285             :                         // do not use limited Seeks in the first place.
    1286           1 :                         if cmp < 0 && i.iterValidityState != IterAtLimit && limit == nil {
    1287           1 :                                 flags = flags.EnableTrySeekUsingNext()
    1288           1 :                         }
    1289           1 :                         if invariants.Enabled && flags.TrySeekUsingNext() && !i.forceEnableSeekOpt && disableSeekOpt(key, uintptr(unsafe.Pointer(i))) {
    1290           1 :                                 flags = flags.DisableTrySeekUsingNext()
    1291           1 :                         }
    1292           1 :                         if !flags.BatchJustRefreshed() && i.pos == iterPosCurForwardPaused && i.cmp(key, i.iterKey.UserKey) <= 0 {
    1293           1 :                                 // Have some work to do, but don't need to seek, and we can
    1294           1 :                                 // start doing findNextEntry from i.iterKey.
    1295           1 :                                 seekInternalIter = false
    1296           1 :                         }
    1297             :                 }
    1298             :         }
    1299             :         // Check for another TrySeekUsingNext optimization opportunity, currently
    1300             :         // specifically tailored to external iterators. This case is intended to
    1301             :         // trigger in instances of Seek-ing with monotonically increasing keys with
    1302             :         // Nexts interspersed. At the time of writing, this is the case for
    1303             :         // CockroachDB scans. This optimization is important for external iterators
    1304             :         // to avoid re-seeking within an already-exhausted sstable. It is not always
    1305             :         // a performance win more generally, so we restrict it to external iterators
    1306             :         // that are configured to only use forward positioning operations.
    1307             :         //
    1308             :         // TODO(jackson): This optimization should be obsolete once we introduce and
    1309             :         // use the NextPrefix iterator positioning operation.
    1310           1 :         if seekInternalIter && i.forwardOnly && lastPositioningOp != invalidatedLastPositionOp &&
    1311           1 :                 i.pos == iterPosCurForward && !hasPrefix && i.iterValidityState == IterValid &&
    1312           1 :                 i.cmp(key, i.iterKey.UserKey) > 0 {
    1313           1 :                 flags = flags.EnableTrySeekUsingNext()
    1314           1 :                 if invariants.Enabled && flags.TrySeekUsingNext() && !i.forceEnableSeekOpt && disableSeekOpt(key, uintptr(unsafe.Pointer(i))) {
    1315           0 :                         flags = flags.DisableTrySeekUsingNext()
    1316           0 :                 }
    1317             :         }
    1318           1 :         if seekInternalIter {
    1319           1 :                 i.iterKey, i.iterValue = i.iter.SeekGE(key, flags)
    1320           1 :                 i.stats.ForwardSeekCount[InternalIterCall]++
    1321           1 :         }
    1322           1 :         i.findNextEntry(limit)
    1323           1 :         i.maybeSampleRead()
    1324           1 :         if i.Error() == nil {
    1325           1 :                 // Prepare state for a future noop optimization.
    1326           1 :                 i.prefixOrFullSeekKey = append(i.prefixOrFullSeekKey[:0], key...)
    1327           1 :                 i.lastPositioningOp = seekGELastPositioningOp
    1328           1 :         }
    1329           1 :         return i.iterValidityState
    1330             : }
    1331             : 
    1332             : // SeekPrefixGE moves the iterator to the first key/value pair whose key is
    1333             : // greater than or equal to the given key and which has the same "prefix" as
    1334             : // the given key. The prefix for a key is determined by the user-defined
    1335             : // Comparer.Split function. The iterator will not observe keys not matching the
    1336             : // "prefix" of the search key. Calling SeekPrefixGE puts the iterator in prefix
    1337             : // iteration mode. The iterator remains in prefix iteration until a subsequent
    1338             : // call to another absolute positioning method (SeekGE, SeekLT, First,
    1339             : // Last). Reverse iteration (Prev) is not supported when an iterator is in
    1340             : // prefix iteration mode. Returns true if the iterator is pointing at a valid
    1341             : // entry and false otherwise.
    1342             : //
    1343             : // The semantics of SeekPrefixGE are slightly unusual and designed for
    1344             : // iteration to be able to take advantage of bloom filters that have been
    1345             : // created on the "prefix". If you're not using bloom filters, there is no
    1346             : // reason to use SeekPrefixGE.
    1347             : //
    1348             : // An example Split function may separate a timestamp suffix from the prefix of
    1349             : // the key.
    1350             : //
    1351             : //      Split(<key>@<timestamp>) -> <key>
    1352             : //
    1353             : // Consider the keys "a@1", "a@2", "aa@3", "aa@4". The prefixes for these keys
    1354             : // are "a", and "aa". Note that despite "a" and "aa" sharing a prefix by the
    1355             : // usual definition, those prefixes differ by the definition of the Split
    1356             : // function. To see how this works, consider the following set of calls on this
    1357             : // data set:
    1358             : //
    1359             : //      SeekPrefixGE("a@0") -> "a@1"
    1360             : //      Next()              -> "a@2"
    1361             : //      Next()              -> EOF
    1362             : //
    1363             : // If you're just looking to iterate over keys with a shared prefix, as
    1364             : // defined by the configured comparer, set iterator bounds instead:
    1365             : //
    1366             : //      iter := db.NewIter(&pebble.IterOptions{
    1367             : //        LowerBound: []byte("prefix"),
    1368             : //        UpperBound: []byte("prefiy"),
    1369             : //      })
    1370             : //      for iter.First(); iter.Valid(); iter.Next() {
    1371             : //        // Only keys beginning with "prefix" will be visited.
    1372             : //      }
    1373             : //
    1374             : // See ExampleIterator_SeekPrefixGE for a working example.
    1375             : //
    1376             : // When iterating with range keys enabled, all range keys encountered are
    1377             : // truncated to the seek key's prefix's bounds. The truncation of the upper
    1378             : // bound requires that the database's Comparer is configured with a
    1379             : // ImmediateSuccessor method. For example, a SeekPrefixGE("a@9") call with the
    1380             : // prefix "a" will truncate range key bounds to [a,ImmediateSuccessor(a)].
    1381           1 : func (i *Iterator) SeekPrefixGE(key []byte) bool {
    1382           1 :         if i.rangeKey != nil {
    1383           1 :                 // NB: Check Valid() before clearing requiresReposition.
    1384           1 :                 i.rangeKey.prevPosHadRangeKey = i.rangeKey.hasRangeKey && i.Valid()
    1385           1 :                 // If we have a range key but did not expose it at the previous iterator
    1386           1 :                 // position (because the iterator was not at a valid position), updated
    1387           1 :                 // must be true. This ensures that after an iterator op sequence like:
    1388           1 :                 //   - Next()             → (IterValid, RangeBounds() = [a,b))
    1389           1 :                 //   - NextWithLimit(...) → (IterAtLimit, RangeBounds() = -)
    1390           1 :                 //   - SeekPrefixGE(...)  → (IterValid, RangeBounds() = [a,b))
    1391           1 :                 // the iterator returns RangeKeyChanged()=true.
    1392           1 :                 //
    1393           1 :                 // The remainder of this function will only update i.rangeKey.updated if
    1394           1 :                 // the iterator moves into a new range key, or out of the current range
    1395           1 :                 // key.
    1396           1 :                 i.rangeKey.updated = i.rangeKey.hasRangeKey && !i.Valid() && i.opts.rangeKeys()
    1397           1 :         }
    1398           1 :         lastPositioningOp := i.lastPositioningOp
    1399           1 :         // Set it to unknown, since this operation may not succeed, in which case
    1400           1 :         // the SeekPrefixGE following this should not make any assumption about
    1401           1 :         // iterator position.
    1402           1 :         i.lastPositioningOp = unknownLastPositionOp
    1403           1 :         i.requiresReposition = false
    1404           1 :         i.err = nil // clear cached iteration error
    1405           1 :         i.stats.ForwardSeekCount[InterfaceCall]++
    1406           1 :         if i.comparer.Split == nil {
    1407           0 :                 panic("pebble: split must be provided for SeekPrefixGE")
    1408             :         }
    1409           1 :         if i.comparer.ImmediateSuccessor == nil && i.opts.KeyTypes != IterKeyTypePointsOnly {
    1410           0 :                 panic("pebble: ImmediateSuccessor must be provided for SeekPrefixGE with range keys")
    1411             :         }
    1412           1 :         prefixLen := i.split(key)
    1413           1 :         keyPrefix := key[:prefixLen]
    1414           1 :         var flags base.SeekGEFlags
    1415           1 :         if i.batchJustRefreshed {
    1416           1 :                 flags = flags.EnableBatchJustRefreshed()
    1417           1 :                 i.batchJustRefreshed = false
    1418           1 :         }
    1419           1 :         if lastPositioningOp == seekPrefixGELastPositioningOp {
    1420           1 :                 if !i.hasPrefix {
    1421           0 :                         panic("lastPositioningOpsIsSeekPrefixGE is true, but hasPrefix is false")
    1422             :                 }
    1423             :                 // The iterator has not been repositioned after the last SeekPrefixGE.
    1424             :                 // See if we are seeking to a larger key, since then we can optimize
    1425             :                 // the seek by using next. Note that we could also optimize if Next
    1426             :                 // has been called, if the iterator is not exhausted and the current
    1427             :                 // position is <= the seek key. We are keeping this limited for now
    1428             :                 // since such optimizations require care for correctness, and to not
    1429             :                 // become de-optimizations (if one usually has to do all the next
    1430             :                 // calls and then the seek). This SeekPrefixGE optimization
    1431             :                 // specifically benefits CockroachDB.
    1432           1 :                 cmp := i.cmp(i.prefixOrFullSeekKey, keyPrefix)
    1433           1 :                 // cmp == 0 is not safe to optimize since
    1434           1 :                 // - i.pos could be at iterPosNext, due to a merge.
    1435           1 :                 // - Even if i.pos were at iterPosCurForward, we could have a DELETE,
    1436           1 :                 //   SET pair for a key, and the iterator would have moved past DELETE
    1437           1 :                 //   but stayed at iterPosCurForward. A similar situation occurs for a
    1438           1 :                 //   MERGE, SET pair where the MERGE is consumed and the iterator is
    1439           1 :                 //   at the SET.
    1440           1 :                 // In general some versions of i.prefix could have been consumed by
    1441           1 :                 // the iterator, so we only optimize for cmp < 0.
    1442           1 :                 if cmp < 0 {
    1443           1 :                         flags = flags.EnableTrySeekUsingNext()
    1444           1 :                 }
    1445           1 :                 if invariants.Enabled && flags.TrySeekUsingNext() && !i.forceEnableSeekOpt && disableSeekOpt(key, uintptr(unsafe.Pointer(i))) {
    1446           1 :                         flags = flags.DisableTrySeekUsingNext()
    1447           1 :                 }
    1448             :         }
    1449             :         // Make a copy of the prefix so that modifications to the key after
    1450             :         // SeekPrefixGE returns does not affect the stored prefix.
    1451           1 :         if cap(i.prefixOrFullSeekKey) < prefixLen {
    1452           1 :                 i.prefixOrFullSeekKey = make([]byte, prefixLen)
    1453           1 :         } else {
    1454           1 :                 i.prefixOrFullSeekKey = i.prefixOrFullSeekKey[:prefixLen]
    1455           1 :         }
    1456           1 :         i.hasPrefix = true
    1457           1 :         copy(i.prefixOrFullSeekKey, keyPrefix)
    1458           1 : 
    1459           1 :         if lowerBound := i.opts.GetLowerBound(); lowerBound != nil && i.cmp(key, lowerBound) < 0 {
    1460           1 :                 if n := i.split(lowerBound); !bytes.Equal(i.prefixOrFullSeekKey, lowerBound[:n]) {
    1461           1 :                         i.err = errors.New("pebble: SeekPrefixGE supplied with key outside of lower bound")
    1462           1 :                         i.iterValidityState = IterExhausted
    1463           1 :                         return false
    1464           1 :                 }
    1465           1 :                 key = lowerBound
    1466           1 :         } else if upperBound := i.opts.GetUpperBound(); upperBound != nil && i.cmp(key, upperBound) > 0 {
    1467           1 :                 if n := i.split(upperBound); !bytes.Equal(i.prefixOrFullSeekKey, upperBound[:n]) {
    1468           1 :                         i.err = errors.New("pebble: SeekPrefixGE supplied with key outside of upper bound")
    1469           1 :                         i.iterValidityState = IterExhausted
    1470           1 :                         return false
    1471           1 :                 }
    1472           0 :                 key = upperBound
    1473             :         }
    1474           1 :         i.iterKey, i.iterValue = i.iter.SeekPrefixGE(i.prefixOrFullSeekKey, key, flags)
    1475           1 :         i.stats.ForwardSeekCount[InternalIterCall]++
    1476           1 :         i.findNextEntry(nil)
    1477           1 :         i.maybeSampleRead()
    1478           1 :         if i.Error() == nil {
    1479           1 :                 i.lastPositioningOp = seekPrefixGELastPositioningOp
    1480           1 :         }
    1481           1 :         return i.iterValidityState == IterValid
    1482             : }
    1483             : 
    1484             : // Deterministic disabling of the seek optimizations. It uses the iterator
    1485             : // pointer, since we want diversity in iterator behavior for the same key.  Used
    1486             : // for tests.
    1487           1 : func disableSeekOpt(key []byte, ptr uintptr) bool {
    1488           1 :         // Fibonacci hash https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/
    1489           1 :         simpleHash := (11400714819323198485 * uint64(ptr)) >> 63
    1490           1 :         return key != nil && key[0]&byte(1) == 0 && simpleHash == 0
    1491           1 : }
    1492             : 
    1493             : // SeekLT moves the iterator to the last key/value pair whose key is less than
    1494             : // the given key. Returns true if the iterator is pointing at a valid entry and
    1495             : // false otherwise.
    1496           1 : func (i *Iterator) SeekLT(key []byte) bool {
    1497           1 :         return i.SeekLTWithLimit(key, nil) == IterValid
    1498           1 : }
    1499             : 
    1500             : // SeekLTWithLimit moves the iterator to the last key/value pair whose key is
    1501             : // less than the given key.
    1502             : //
    1503             : // If limit is provided, it serves as a best-effort inclusive limit. If the last
    1504             : // key less than the given search key is also less than limit, the Iterator may
    1505             : // pause and return IterAtLimit. Because limits are best-effort, SeekLTWithLimit
    1506             : // may return a key beyond limit.
    1507             : //
    1508             : // If the Iterator is configured to iterate over range keys, SeekLTWithLimit
    1509             : // guarantees it will surface any range keys with bounds overlapping the
    1510             : // keyspace up to limit.
    1511           1 : func (i *Iterator) SeekLTWithLimit(key []byte, limit []byte) IterValidityState {
    1512           1 :         if i.rangeKey != nil {
    1513           1 :                 // NB: Check Valid() before clearing requiresReposition.
    1514           1 :                 i.rangeKey.prevPosHadRangeKey = i.rangeKey.hasRangeKey && i.Valid()
    1515           1 :                 // If we have a range key but did not expose it at the previous iterator
    1516           1 :                 // position (because the iterator was not at a valid position), updated
    1517           1 :                 // must be true. This ensures that after an iterator op sequence like:
    1518           1 :                 //   - Next()               → (IterValid, RangeBounds() = [a,b))
    1519           1 :                 //   - NextWithLimit(...)   → (IterAtLimit, RangeBounds() = -)
    1520           1 :                 //   - SeekLTWithLimit(...) → (IterValid, RangeBounds() = [a,b))
    1521           1 :                 // the iterator returns RangeKeyChanged()=true.
    1522           1 :                 //
    1523           1 :                 // The remainder of this function will only update i.rangeKey.updated if
    1524           1 :                 // the iterator moves into a new range key, or out of the current range
    1525           1 :                 // key.
    1526           1 :                 i.rangeKey.updated = i.rangeKey.hasRangeKey && !i.Valid() && i.opts.rangeKeys()
    1527           1 :         }
    1528           1 :         lastPositioningOp := i.lastPositioningOp
    1529           1 :         // Set it to unknown, since this operation may not succeed, in which case
    1530           1 :         // the SeekLT following this should not make any assumption about iterator
    1531           1 :         // position.
    1532           1 :         i.lastPositioningOp = unknownLastPositionOp
    1533           1 :         i.batchJustRefreshed = false
    1534           1 :         i.requiresReposition = false
    1535           1 :         i.err = nil // clear cached iteration error
    1536           1 :         i.stats.ReverseSeekCount[InterfaceCall]++
    1537           1 :         if upperBound := i.opts.GetUpperBound(); upperBound != nil && i.cmp(key, upperBound) > 0 {
    1538           1 :                 key = upperBound
    1539           1 :         } else if lowerBound := i.opts.GetLowerBound(); lowerBound != nil && i.cmp(key, lowerBound) < 0 {
    1540           1 :                 key = lowerBound
    1541           1 :         }
    1542           1 :         i.hasPrefix = false
    1543           1 :         seekInternalIter := true
    1544           1 :         // The following noop optimization only applies when i.batch == nil, since
    1545           1 :         // an iterator over a batch is iterating over mutable data, that may have
    1546           1 :         // changed since the last seek.
    1547           1 :         if lastPositioningOp == seekLTLastPositioningOp && i.batch == nil {
    1548           1 :                 cmp := i.cmp(key, i.prefixOrFullSeekKey)
    1549           1 :                 // If this seek is to the same or earlier key, and the iterator is
    1550           1 :                 // already positioned there, this is a noop. This can be helpful for
    1551           1 :                 // sparse key spaces that have many deleted keys, where one can avoid
    1552           1 :                 // the overhead of iterating past them again and again.
    1553           1 :                 if cmp <= 0 {
    1554           1 :                         // NB: when pos != iterPosCurReversePaused, the invariant
    1555           1 :                         // documented earlier implies that iterValidityState !=
    1556           1 :                         // IterAtLimit.
    1557           1 :                         if i.iterValidityState == IterExhausted ||
    1558           1 :                                 (i.iterValidityState == IterValid && i.cmp(i.key, key) < 0 &&
    1559           1 :                                         (limit == nil || i.cmp(limit, i.key) <= 0)) {
    1560           1 :                                 if !invariants.Enabled || !disableSeekOpt(key, uintptr(unsafe.Pointer(i))) {
    1561           1 :                                         i.lastPositioningOp = seekLTLastPositioningOp
    1562           1 :                                         return i.iterValidityState
    1563           1 :                                 }
    1564             :                         }
    1565           1 :                         if i.pos == iterPosCurReversePaused && i.cmp(i.iterKey.UserKey, key) < 0 {
    1566           1 :                                 // Have some work to do, but don't need to seek, and we can
    1567           1 :                                 // start doing findPrevEntry from i.iterKey.
    1568           1 :                                 seekInternalIter = false
    1569           1 :                         }
    1570             :                 }
    1571             :         }
    1572           1 :         if seekInternalIter {
    1573           1 :                 i.iterKey, i.iterValue = i.iter.SeekLT(key, base.SeekLTFlagsNone)
    1574           1 :                 i.stats.ReverseSeekCount[InternalIterCall]++
    1575           1 :         }
    1576           1 :         i.findPrevEntry(limit)
    1577           1 :         i.maybeSampleRead()
    1578           1 :         if i.Error() == nil && i.batch == nil {
    1579           1 :                 // Prepare state for a future noop optimization.
    1580           1 :                 i.prefixOrFullSeekKey = append(i.prefixOrFullSeekKey[:0], key...)
    1581           1 :                 i.lastPositioningOp = seekLTLastPositioningOp
    1582           1 :         }
    1583           1 :         return i.iterValidityState
    1584             : }
    1585             : 
    1586             : // First moves the iterator the the first key/value pair. Returns true if the
    1587             : // iterator is pointing at a valid entry and false otherwise.
    1588           1 : func (i *Iterator) First() bool {
    1589           1 :         if i.rangeKey != nil {
    1590           1 :                 // NB: Check Valid() before clearing requiresReposition.
    1591           1 :                 i.rangeKey.prevPosHadRangeKey = i.rangeKey.hasRangeKey && i.Valid()
    1592           1 :                 // If we have a range key but did not expose it at the previous iterator
    1593           1 :                 // position (because the iterator was not at a valid position), updated
    1594           1 :                 // must be true. This ensures that after an iterator op sequence like:
    1595           1 :                 //   - Next()             → (IterValid, RangeBounds() = [a,b))
    1596           1 :                 //   - NextWithLimit(...) → (IterAtLimit, RangeBounds() = -)
    1597           1 :                 //   - First(...)         → (IterValid, RangeBounds() = [a,b))
    1598           1 :                 // the iterator returns RangeKeyChanged()=true.
    1599           1 :                 //
    1600           1 :                 // The remainder of this function will only update i.rangeKey.updated if
    1601           1 :                 // the iterator moves into a new range key, or out of the current range
    1602           1 :                 // key.
    1603           1 :                 i.rangeKey.updated = i.rangeKey.hasRangeKey && !i.Valid() && i.opts.rangeKeys()
    1604           1 :         }
    1605           1 :         i.err = nil // clear cached iteration error
    1606           1 :         i.hasPrefix = false
    1607           1 :         i.batchJustRefreshed = false
    1608           1 :         i.lastPositioningOp = unknownLastPositionOp
    1609           1 :         i.requiresReposition = false
    1610           1 :         i.stats.ForwardSeekCount[InterfaceCall]++
    1611           1 : 
    1612           1 :         i.iterFirstWithinBounds()
    1613           1 :         i.findNextEntry(nil)
    1614           1 :         i.maybeSampleRead()
    1615           1 :         return i.iterValidityState == IterValid
    1616             : }
    1617             : 
    1618             : // Last moves the iterator the the last key/value pair. Returns true if the
    1619             : // iterator is pointing at a valid entry and false otherwise.
    1620           1 : func (i *Iterator) Last() bool {
    1621           1 :         if i.rangeKey != nil {
    1622           1 :                 // NB: Check Valid() before clearing requiresReposition.
    1623           1 :                 i.rangeKey.prevPosHadRangeKey = i.rangeKey.hasRangeKey && i.Valid()
    1624           1 :                 // If we have a range key but did not expose it at the previous iterator
    1625           1 :                 // position (because the iterator was not at a valid position), updated
    1626           1 :                 // must be true. This ensures that after an iterator op sequence like:
    1627           1 :                 //   - Next()             → (IterValid, RangeBounds() = [a,b))
    1628           1 :                 //   - NextWithLimit(...) → (IterAtLimit, RangeBounds() = -)
    1629           1 :                 //   - Last(...)          → (IterValid, RangeBounds() = [a,b))
    1630           1 :                 // the iterator returns RangeKeyChanged()=true.
    1631           1 :                 //
    1632           1 :                 // The remainder of this function will only update i.rangeKey.updated if
    1633           1 :                 // the iterator moves into a new range key, or out of the current range
    1634           1 :                 // key.
    1635           1 :                 i.rangeKey.updated = i.rangeKey.hasRangeKey && !i.Valid() && i.opts.rangeKeys()
    1636           1 :         }
    1637           1 :         i.err = nil // clear cached iteration error
    1638           1 :         i.hasPrefix = false
    1639           1 :         i.batchJustRefreshed = false
    1640           1 :         i.lastPositioningOp = unknownLastPositionOp
    1641           1 :         i.requiresReposition = false
    1642           1 :         i.stats.ReverseSeekCount[InterfaceCall]++
    1643           1 : 
    1644           1 :         i.iterLastWithinBounds()
    1645           1 :         i.findPrevEntry(nil)
    1646           1 :         i.maybeSampleRead()
    1647           1 :         return i.iterValidityState == IterValid
    1648             : }
    1649             : 
    1650             : // Next moves the iterator to the next key/value pair. Returns true if the
    1651             : // iterator is pointing at a valid entry and false otherwise.
    1652           1 : func (i *Iterator) Next() bool {
    1653           1 :         return i.nextWithLimit(nil) == IterValid
    1654           1 : }
    1655             : 
    1656             : // NextWithLimit moves the iterator to the next key/value pair.
    1657             : //
    1658             : // If limit is provided, it serves as a best-effort exclusive limit. If the next
    1659             : // key  is greater than or equal to limit, the Iterator may pause and return
    1660             : // IterAtLimit. Because limits are best-effort, NextWithLimit may return a key
    1661             : // beyond limit.
    1662             : //
    1663             : // If the Iterator is configured to iterate over range keys, NextWithLimit
    1664             : // guarantees it will surface any range keys with bounds overlapping the
    1665             : // keyspace up to limit.
    1666           1 : func (i *Iterator) NextWithLimit(limit []byte) IterValidityState {
    1667           1 :         return i.nextWithLimit(limit)
    1668           1 : }
    1669             : 
    1670             : // NextPrefix moves the iterator to the next key/value pair with a key
    1671             : // containing a different prefix than the current key. Prefixes are determined
    1672             : // by Comparer.Split. Exhausts the iterator if invoked while in prefix-iteration
    1673             : // mode.
    1674             : //
    1675             : // It is not permitted to invoke NextPrefix while at a IterAtLimit position.
    1676             : // When called in this condition, NextPrefix has non-deterministic behavior.
    1677             : //
    1678             : // It is not permitted to invoke NextPrefix when the Iterator has an
    1679             : // upper-bound that is a versioned MVCC key (see the comment for
    1680             : // Comparer.Split). It returns an error in this case.
    1681           1 : func (i *Iterator) NextPrefix() bool {
    1682           1 :         if i.nextPrefixNotPermittedByUpperBound {
    1683           1 :                 i.lastPositioningOp = unknownLastPositionOp
    1684           1 :                 i.requiresReposition = false
    1685           1 :                 i.err = errors.Errorf("NextPrefix not permitted with upper bound %s",
    1686           1 :                         i.comparer.FormatKey(i.opts.UpperBound))
    1687           1 :                 i.iterValidityState = IterExhausted
    1688           1 :                 return false
    1689           1 :         }
    1690           1 :         if i.hasPrefix {
    1691           1 :                 i.iterValidityState = IterExhausted
    1692           1 :                 return false
    1693           1 :         }
    1694           1 :         return i.nextPrefix() == IterValid
    1695             : }
    1696             : 
    1697           1 : func (i *Iterator) nextPrefix() IterValidityState {
    1698           1 :         if i.rangeKey != nil {
    1699           1 :                 // NB: Check Valid() before clearing requiresReposition.
    1700           1 :                 i.rangeKey.prevPosHadRangeKey = i.rangeKey.hasRangeKey && i.Valid()
    1701           1 :                 // If we have a range key but did not expose it at the previous iterator
    1702           1 :                 // position (because the iterator was not at a valid position), updated
    1703           1 :                 // must be true. This ensures that after an iterator op sequence like:
    1704           1 :                 //   - Next()             → (IterValid, RangeBounds() = [a,b))
    1705           1 :                 //   - NextWithLimit(...) → (IterAtLimit, RangeBounds() = -)
    1706           1 :                 //   - NextWithLimit(...) → (IterValid, RangeBounds() = [a,b))
    1707           1 :                 // the iterator returns RangeKeyChanged()=true.
    1708           1 :                 //
    1709           1 :                 // The remainder of this function will only update i.rangeKey.updated if
    1710           1 :                 // the iterator moves into a new range key, or out of the current range
    1711           1 :                 // key.
    1712           1 :                 i.rangeKey.updated = i.rangeKey.hasRangeKey && !i.Valid() && i.opts.rangeKeys()
    1713           1 :         }
    1714             : 
    1715             :         // Although NextPrefix documents that behavior at IterAtLimit is undefined,
    1716             :         // this function handles these cases as a simple prefix-agnostic Next. This
    1717             :         // is done for deterministic behavior in the metamorphic tests.
    1718             :         //
    1719             :         // TODO(jackson): If the metamorphic test operation generator is adjusted to
    1720             :         // make generation of some operations conditional on the previous
    1721             :         // operations, then we can remove this behavior and explicitly error.
    1722             : 
    1723           1 :         i.lastPositioningOp = unknownLastPositionOp
    1724           1 :         i.requiresReposition = false
    1725           1 :         switch i.pos {
    1726           1 :         case iterPosCurForward:
    1727           1 :                 // Positioned on the current key. Advance to the next prefix.
    1728           1 :                 i.internalNextPrefix(i.split(i.key))
    1729           0 :         case iterPosCurForwardPaused:
    1730             :                 // Positioned at a limit. Implement as a prefix-agnostic Next. See TODO
    1731             :                 // up above. The iterator is already positioned at the next key.
    1732           1 :         case iterPosCurReverse:
    1733           1 :                 // Switching directions.
    1734           1 :                 // Unless the iterator was exhausted, reverse iteration needs to
    1735           1 :                 // position the iterator at iterPosPrev.
    1736           1 :                 if i.iterKey != nil {
    1737           0 :                         i.err = errors.New("switching from reverse to forward but iter is not at prev")
    1738           0 :                         i.iterValidityState = IterExhausted
    1739           0 :                         return i.iterValidityState
    1740           0 :                 }
    1741             :                 // The Iterator is exhausted and i.iter is positioned before the first
    1742             :                 // key. Reposition to point to the first internal key.
    1743           1 :                 i.iterFirstWithinBounds()
    1744           0 :         case iterPosCurReversePaused:
    1745           0 :                 // Positioned at a limit. Implement as a prefix-agnostic Next. See TODO
    1746           0 :                 // up above.
    1747           0 :                 //
    1748           0 :                 // Switching directions; The iterator must not be exhausted since it
    1749           0 :                 // paused.
    1750           0 :                 if i.iterKey == nil {
    1751           0 :                         i.err = errors.New("switching paused from reverse to forward but iter is exhausted")
    1752           0 :                         i.iterValidityState = IterExhausted
    1753           0 :                         return i.iterValidityState
    1754           0 :                 }
    1755           0 :                 i.nextUserKey()
    1756           1 :         case iterPosPrev:
    1757           1 :                 // The underlying iterator is pointed to the previous key (this can
    1758           1 :                 // only happen when switching iteration directions).
    1759           1 :                 if i.iterKey == nil {
    1760           1 :                         // We're positioned before the first key. Need to reposition to point to
    1761           1 :                         // the first key.
    1762           1 :                         i.iterFirstWithinBounds()
    1763           1 :                 } else {
    1764           1 :                         // Move the internal iterator back onto the user key stored in
    1765           1 :                         // i.key. iterPosPrev guarantees that it's positioned at the last
    1766           1 :                         // key with the user key less than i.key, so we're guaranteed to
    1767           1 :                         // land on the correct key with a single Next.
    1768           1 :                         i.iterKey, i.iterValue = i.iter.Next()
    1769           1 :                         if invariants.Enabled && !i.equal(i.iterKey.UserKey, i.key) {
    1770           0 :                                 i.opts.logger.Fatalf("pebble: invariant violation: Nexting internal iterator from iterPosPrev landed on %q, not %q",
    1771           0 :                                         i.iterKey.UserKey, i.key)
    1772           0 :                         }
    1773             :                 }
    1774             :                 // The internal iterator is now positioned at i.key. Advance to the next
    1775             :                 // prefix.
    1776           1 :                 i.internalNextPrefix(i.split(i.key))
    1777           1 :         case iterPosNext:
    1778           1 :                 // Already positioned on the next key. Only call nextPrefixKey if the
    1779           1 :                 // next key shares the same prefix.
    1780           1 :                 if i.iterKey != nil {
    1781           1 :                         currKeyPrefixLen := i.split(i.key)
    1782           1 :                         iterKeyPrefixLen := i.split(i.iterKey.UserKey)
    1783           1 :                         if bytes.Equal(i.iterKey.UserKey[:iterKeyPrefixLen], i.key[:currKeyPrefixLen]) {
    1784           1 :                                 i.internalNextPrefix(currKeyPrefixLen)
    1785           1 :                         }
    1786             :                 }
    1787             :         }
    1788             : 
    1789           1 :         i.stats.ForwardStepCount[InterfaceCall]++
    1790           1 :         i.findNextEntry(nil /* limit */)
    1791           1 :         i.maybeSampleRead()
    1792           1 :         return i.iterValidityState
    1793             : }
    1794             : 
    1795           1 : func (i *Iterator) internalNextPrefix(currKeyPrefixLen int) {
    1796           1 :         if i.iterKey == nil {
    1797           1 :                 return
    1798           1 :         }
    1799             :         // The Next "fast-path" is not really a fast-path when there is more than
    1800             :         // one version. However, even with TableFormatPebblev3, there is a small
    1801             :         // slowdown (~10%) for one version if we remove it and only call NextPrefix.
    1802             :         // When there are two versions, only calling NextPrefix is ~30% faster.
    1803           1 :         i.stats.ForwardStepCount[InternalIterCall]++
    1804           1 :         if i.iterKey, i.iterValue = i.iter.Next(); i.iterKey == nil {
    1805           1 :                 return
    1806           1 :         }
    1807           1 :         iterKeyPrefixLen := i.split(i.iterKey.UserKey)
    1808           1 :         if !bytes.Equal(i.iterKey.UserKey[:iterKeyPrefixLen], i.key[:currKeyPrefixLen]) {
    1809           1 :                 return
    1810           1 :         }
    1811           1 :         i.stats.ForwardStepCount[InternalIterCall]++
    1812           1 :         i.prefixOrFullSeekKey = i.comparer.ImmediateSuccessor(i.prefixOrFullSeekKey[:0], i.key[:currKeyPrefixLen])
    1813           1 :         i.iterKey, i.iterValue = i.iter.NextPrefix(i.prefixOrFullSeekKey)
    1814           1 :         if invariants.Enabled && i.iterKey != nil {
    1815           1 :                 if iterKeyPrefixLen := i.split(i.iterKey.UserKey); i.cmp(i.iterKey.UserKey[:iterKeyPrefixLen], i.prefixOrFullSeekKey) < 0 {
    1816           0 :                         panic(errors.AssertionFailedf("pebble: iter.NextPrefix did not advance beyond the current prefix: now at %q; expected to be geq %q",
    1817           0 :                                 i.iterKey, i.prefixOrFullSeekKey))
    1818             :                 }
    1819             :         }
    1820             : }
    1821             : 
    1822           1 : func (i *Iterator) nextWithLimit(limit []byte) IterValidityState {
    1823           1 :         i.stats.ForwardStepCount[InterfaceCall]++
    1824           1 :         if i.hasPrefix {
    1825           1 :                 if limit != nil {
    1826           1 :                         i.err = errors.New("cannot use limit with prefix iteration")
    1827           1 :                         i.iterValidityState = IterExhausted
    1828           1 :                         return i.iterValidityState
    1829           1 :                 } else if i.iterValidityState == IterExhausted {
    1830           1 :                         // No-op, already exhasuted. We avoid executing the Next because it
    1831           1 :                         // can break invariants: Specifically, a file that fails the bloom
    1832           1 :                         // filter test may result in its level being removed from the
    1833           1 :                         // merging iterator. The level's removal can cause a lazy combined
    1834           1 :                         // iterator to miss range keys and trigger a switch to combined
    1835           1 :                         // iteration at a larger key, breaking keyspan invariants.
    1836           1 :                         return i.iterValidityState
    1837           1 :                 }
    1838             :         }
    1839           1 :         if i.err != nil {
    1840           1 :                 return i.iterValidityState
    1841           1 :         }
    1842           1 :         if i.rangeKey != nil {
    1843           1 :                 // NB: Check Valid() before clearing requiresReposition.
    1844           1 :                 i.rangeKey.prevPosHadRangeKey = i.rangeKey.hasRangeKey && i.Valid()
    1845           1 :                 // If we have a range key but did not expose it at the previous iterator
    1846           1 :                 // position (because the iterator was not at a valid position), updated
    1847           1 :                 // must be true. This ensures that after an iterator op sequence like:
    1848           1 :                 //   - Next()             → (IterValid, RangeBounds() = [a,b))
    1849           1 :                 //   - NextWithLimit(...) → (IterAtLimit, RangeBounds() = -)
    1850           1 :                 //   - NextWithLimit(...) → (IterValid, RangeBounds() = [a,b))
    1851           1 :                 // the iterator returns RangeKeyChanged()=true.
    1852           1 :                 //
    1853           1 :                 // The remainder of this function will only update i.rangeKey.updated if
    1854           1 :                 // the iterator moves into a new range key, or out of the current range
    1855           1 :                 // key.
    1856           1 :                 i.rangeKey.updated = i.rangeKey.hasRangeKey && !i.Valid() && i.opts.rangeKeys()
    1857           1 :         }
    1858           1 :         i.lastPositioningOp = unknownLastPositionOp
    1859           1 :         i.requiresReposition = false
    1860           1 :         switch i.pos {
    1861           1 :         case iterPosCurForward:
    1862           1 :                 i.nextUserKey()
    1863           1 :         case iterPosCurForwardPaused:
    1864             :                 // Already at the right place.
    1865           1 :         case iterPosCurReverse:
    1866           1 :                 // Switching directions.
    1867           1 :                 // Unless the iterator was exhausted, reverse iteration needs to
    1868           1 :                 // position the iterator at iterPosPrev.
    1869           1 :                 if i.iterKey != nil {
    1870           0 :                         i.err = errors.New("switching from reverse to forward but iter is not at prev")
    1871           0 :                         i.iterValidityState = IterExhausted
    1872           0 :                         return i.iterValidityState
    1873           0 :                 }
    1874             :                 // We're positioned before the first key. Need to reposition to point to
    1875             :                 // the first key.
    1876           1 :                 i.iterFirstWithinBounds()
    1877           1 :         case iterPosCurReversePaused:
    1878           1 :                 // Switching directions.
    1879           1 :                 // The iterator must not be exhausted since it paused.
    1880           1 :                 if i.iterKey == nil {
    1881           0 :                         i.err = errors.New("switching paused from reverse to forward but iter is exhausted")
    1882           0 :                         i.iterValidityState = IterExhausted
    1883           0 :                         return i.iterValidityState
    1884           0 :                 }
    1885           1 :                 i.nextUserKey()
    1886           1 :         case iterPosPrev:
    1887           1 :                 // The underlying iterator is pointed to the previous key (this can
    1888           1 :                 // only happen when switching iteration directions). We set
    1889           1 :                 // i.iterValidityState to IterExhausted here to force the calls to
    1890           1 :                 // nextUserKey to save the current key i.iter is pointing at in order
    1891           1 :                 // to determine when the next user-key is reached.
    1892           1 :                 i.iterValidityState = IterExhausted
    1893           1 :                 if i.iterKey == nil {
    1894           1 :                         // We're positioned before the first key. Need to reposition to point to
    1895           1 :                         // the first key.
    1896           1 :                         i.iterFirstWithinBounds()
    1897           1 :                 } else {
    1898           1 :                         i.nextUserKey()
    1899           1 :                 }
    1900           1 :                 i.nextUserKey()
    1901           1 :         case iterPosNext:
    1902             :                 // Already at the right place.
    1903             :         }
    1904           1 :         i.findNextEntry(limit)
    1905           1 :         i.maybeSampleRead()
    1906           1 :         return i.iterValidityState
    1907             : }
    1908             : 
    1909             : // Prev moves the iterator to the previous key/value pair. Returns true if the
    1910             : // iterator is pointing at a valid entry and false otherwise.
    1911           1 : func (i *Iterator) Prev() bool {
    1912           1 :         return i.PrevWithLimit(nil) == IterValid
    1913           1 : }
    1914             : 
    1915             : // PrevWithLimit moves the iterator to the previous key/value pair.
    1916             : //
    1917             : // If limit is provided, it serves as a best-effort inclusive limit. If the
    1918             : // previous key is less than limit, the Iterator may pause and return
    1919             : // IterAtLimit. Because limits are best-effort, PrevWithLimit may return a key
    1920             : // beyond limit.
    1921             : //
    1922             : // If the Iterator is configured to iterate over range keys, PrevWithLimit
    1923             : // guarantees it will surface any range keys with bounds overlapping the
    1924             : // keyspace up to limit.
    1925           1 : func (i *Iterator) PrevWithLimit(limit []byte) IterValidityState {
    1926           1 :         i.stats.ReverseStepCount[InterfaceCall]++
    1927           1 :         if i.err != nil {
    1928           1 :                 return i.iterValidityState
    1929           1 :         }
    1930           1 :         if i.rangeKey != nil {
    1931           1 :                 // NB: Check Valid() before clearing requiresReposition.
    1932           1 :                 i.rangeKey.prevPosHadRangeKey = i.rangeKey.hasRangeKey && i.Valid()
    1933           1 :                 // If we have a range key but did not expose it at the previous iterator
    1934           1 :                 // position (because the iterator was not at a valid position), updated
    1935           1 :                 // must be true. This ensures that after an iterator op sequence like:
    1936           1 :                 //   - Next()             → (IterValid, RangeBounds() = [a,b))
    1937           1 :                 //   - NextWithLimit(...) → (IterAtLimit, RangeBounds() = -)
    1938           1 :                 //   - PrevWithLimit(...) → (IterValid, RangeBounds() = [a,b))
    1939           1 :                 // the iterator returns RangeKeyChanged()=true.
    1940           1 :                 //
    1941           1 :                 // The remainder of this function will only update i.rangeKey.updated if
    1942           1 :                 // the iterator moves into a new range key, or out of the current range
    1943           1 :                 // key.
    1944           1 :                 i.rangeKey.updated = i.rangeKey.hasRangeKey && !i.Valid() && i.opts.rangeKeys()
    1945           1 :         }
    1946           1 :         i.lastPositioningOp = unknownLastPositionOp
    1947           1 :         i.requiresReposition = false
    1948           1 :         if i.hasPrefix {
    1949           1 :                 i.err = errReversePrefixIteration
    1950           1 :                 i.iterValidityState = IterExhausted
    1951           1 :                 return i.iterValidityState
    1952           1 :         }
    1953           1 :         switch i.pos {
    1954           1 :         case iterPosCurForward:
    1955             :                 // Switching directions, and will handle this below.
    1956           1 :         case iterPosCurForwardPaused:
    1957             :                 // Switching directions, and will handle this below.
    1958           1 :         case iterPosCurReverse:
    1959           1 :                 i.prevUserKey()
    1960           1 :         case iterPosCurReversePaused:
    1961             :                 // Already at the right place.
    1962           1 :         case iterPosNext:
    1963             :                 // The underlying iterator is pointed to the next key (this can only happen
    1964             :                 // when switching iteration directions). We will handle this below.
    1965           1 :         case iterPosPrev:
    1966             :                 // Already at the right place.
    1967             :         }
    1968           1 :         if i.pos == iterPosCurForward || i.pos == iterPosNext || i.pos == iterPosCurForwardPaused {
    1969           1 :                 // Switching direction.
    1970           1 :                 stepAgain := i.pos == iterPosNext
    1971           1 : 
    1972           1 :                 // Synthetic range key markers are a special case. Consider SeekGE(b)
    1973           1 :                 // which finds a range key [a, c). To ensure the user observes the range
    1974           1 :                 // key, the Iterator pauses at Key() = b. The iterator must advance the
    1975           1 :                 // internal iterator to see if there's also a coincident point key at
    1976           1 :                 // 'b', leaving the iterator at iterPosNext if there's not.
    1977           1 :                 //
    1978           1 :                 // This is a problem: Synthetic range key markers are only interleaved
    1979           1 :                 // during the original seek. A subsequent Prev() of i.iter will not move
    1980           1 :                 // back onto the synthetic range key marker. In this case where the
    1981           1 :                 // previous iterator position was a synthetic range key start boundary,
    1982           1 :                 // we must not step a second time.
    1983           1 :                 if i.isEphemeralPosition() {
    1984           1 :                         stepAgain = false
    1985           1 :                 }
    1986             : 
    1987             :                 // We set i.iterValidityState to IterExhausted here to force the calls
    1988             :                 // to prevUserKey to save the current key i.iter is pointing at in
    1989             :                 // order to determine when the prev user-key is reached.
    1990           1 :                 i.iterValidityState = IterExhausted
    1991           1 :                 if i.iterKey == nil {
    1992           1 :                         // We're positioned after the last key. Need to reposition to point to
    1993           1 :                         // the last key.
    1994           1 :                         i.iterLastWithinBounds()
    1995           1 :                 } else {
    1996           1 :                         i.prevUserKey()
    1997           1 :                 }
    1998           1 :                 if stepAgain {
    1999           1 :                         i.prevUserKey()
    2000           1 :                 }
    2001             :         }
    2002           1 :         i.findPrevEntry(limit)
    2003           1 :         i.maybeSampleRead()
    2004           1 :         return i.iterValidityState
    2005             : }
    2006             : 
    2007             : // iterFirstWithinBounds moves the internal iterator to the first key,
    2008             : // respecting bounds.
    2009           1 : func (i *Iterator) iterFirstWithinBounds() {
    2010           1 :         i.stats.ForwardSeekCount[InternalIterCall]++
    2011           1 :         if lowerBound := i.opts.GetLowerBound(); lowerBound != nil {
    2012           1 :                 i.iterKey, i.iterValue = i.iter.SeekGE(lowerBound, base.SeekGEFlagsNone)
    2013           1 :         } else {
    2014           1 :                 i.iterKey, i.iterValue = i.iter.First()
    2015           1 :         }
    2016             : }
    2017             : 
    2018             : // iterLastWithinBounds moves the internal iterator to the last key, respecting
    2019             : // bounds.
    2020           1 : func (i *Iterator) iterLastWithinBounds() {
    2021           1 :         i.stats.ReverseSeekCount[InternalIterCall]++
    2022           1 :         if upperBound := i.opts.GetUpperBound(); upperBound != nil {
    2023           1 :                 i.iterKey, i.iterValue = i.iter.SeekLT(upperBound, base.SeekLTFlagsNone)
    2024           1 :         } else {
    2025           1 :                 i.iterKey, i.iterValue = i.iter.Last()
    2026           1 :         }
    2027             : }
    2028             : 
    2029             : // RangeKeyData describes a range key's data, set through RangeKeySet. The key
    2030             : // boundaries of the range key is provided by Iterator.RangeBounds.
    2031             : type RangeKeyData struct {
    2032             :         Suffix []byte
    2033             :         Value  []byte
    2034             : }
    2035             : 
    2036             : // rangeKeyWithinLimit is called during limited reverse iteration when
    2037             : // positioned over a key beyond the limit. If there exists a range key that lies
    2038             : // within the limit, the iterator must not pause in order to ensure the user has
    2039             : // an opportunity to observe the range key within limit.
    2040             : //
    2041             : // It would be valid to ignore the limit whenever there's a range key covering
    2042             : // the key, but that would introduce nondeterminism. To preserve determinism for
    2043             : // testing, the iterator ignores the limit only if the covering range key does
    2044             : // cover the keyspace within the limit.
    2045             : //
    2046             : // This awkwardness exists because range keys are interleaved at their inclusive
    2047             : // start positions. Note that limit is inclusive.
    2048           1 : func (i *Iterator) rangeKeyWithinLimit(limit []byte) bool {
    2049           1 :         if i.rangeKey == nil || !i.opts.rangeKeys() {
    2050           1 :                 return false
    2051           1 :         }
    2052           1 :         s := i.rangeKey.iiter.Span()
    2053           1 :         // If the range key ends beyond the limit, then the range key does not cover
    2054           1 :         // any portion of the keyspace within the limit and it is safe to pause.
    2055           1 :         return s != nil && i.cmp(s.End, limit) > 0
    2056             : }
    2057             : 
    2058             : // saveRangeKey saves the current range key to the underlying iterator's current
    2059             : // range key state. If the range key has not changed, saveRangeKey is a no-op.
    2060             : // If there is a new range key, saveRangeKey copies all of the key, value and
    2061             : // suffixes into Iterator-managed buffers.
    2062           1 : func (i *Iterator) saveRangeKey() {
    2063           1 :         if i.rangeKey == nil || i.opts.KeyTypes == IterKeyTypePointsOnly {
    2064           1 :                 return
    2065           1 :         }
    2066             : 
    2067           1 :         s := i.rangeKey.iiter.Span()
    2068           1 :         if s == nil {
    2069           1 :                 i.rangeKey.hasRangeKey = false
    2070           1 :                 i.rangeKey.updated = i.rangeKey.prevPosHadRangeKey
    2071           1 :                 return
    2072           1 :         } else if !i.rangeKey.stale {
    2073           1 :                 // The range key `s` is identical to the one currently saved. No-op.
    2074           1 :                 return
    2075           1 :         }
    2076             : 
    2077           1 :         if s.KeysOrder != keyspan.BySuffixAsc {
    2078           0 :                 panic("pebble: range key span's keys unexpectedly not in ascending suffix order")
    2079             :         }
    2080             : 
    2081             :         // Although `i.rangeKey.stale` is true, the span s may still be identical
    2082             :         // to the currently saved span. This is possible when seeking the iterator,
    2083             :         // which may land back on the same range key. If we previously had a range
    2084             :         // key and the new one has an identical start key, then it must be the same
    2085             :         // range key and we can avoid copying and keep `i.rangeKey.updated=false`.
    2086             :         //
    2087             :         // TODO(jackson): These key comparisons could be avoidable during relative
    2088             :         // positioning operations continuing in the same direction, because these
    2089             :         // ops will never encounter the previous position's range key while
    2090             :         // stale=true. However, threading whether the current op is a seek or step
    2091             :         // maybe isn't worth it. This key comparison is only necessary once when we
    2092             :         // step onto a new range key, which should be relatively rare.
    2093           1 :         if i.rangeKey.prevPosHadRangeKey && i.equal(i.rangeKey.start, s.Start) &&
    2094           1 :                 i.equal(i.rangeKey.end, s.End) {
    2095           1 :                 i.rangeKey.updated = false
    2096           1 :                 i.rangeKey.stale = false
    2097           1 :                 i.rangeKey.hasRangeKey = true
    2098           1 :                 return
    2099           1 :         }
    2100           1 :         i.stats.RangeKeyStats.Count += len(s.Keys)
    2101           1 :         i.rangeKey.buf.Reset()
    2102           1 :         i.rangeKey.hasRangeKey = true
    2103           1 :         i.rangeKey.updated = true
    2104           1 :         i.rangeKey.stale = false
    2105           1 :         i.rangeKey.buf, i.rangeKey.start = i.rangeKey.buf.Copy(s.Start)
    2106           1 :         i.rangeKey.buf, i.rangeKey.end = i.rangeKey.buf.Copy(s.End)
    2107           1 :         i.rangeKey.keys = i.rangeKey.keys[:0]
    2108           1 :         for j := 0; j < len(s.Keys); j++ {
    2109           1 :                 if invariants.Enabled {
    2110           1 :                         if s.Keys[j].Kind() != base.InternalKeyKindRangeKeySet {
    2111           0 :                                 panic("pebble: user iteration encountered non-RangeKeySet key kind")
    2112           1 :                         } else if j > 0 && i.cmp(s.Keys[j].Suffix, s.Keys[j-1].Suffix) < 0 {
    2113           0 :                                 panic("pebble: user iteration encountered range keys not in suffix order")
    2114             :                         }
    2115             :                 }
    2116           1 :                 var rkd RangeKeyData
    2117           1 :                 i.rangeKey.buf, rkd.Suffix = i.rangeKey.buf.Copy(s.Keys[j].Suffix)
    2118           1 :                 i.rangeKey.buf, rkd.Value = i.rangeKey.buf.Copy(s.Keys[j].Value)
    2119           1 :                 i.rangeKey.keys = append(i.rangeKey.keys, rkd)
    2120             :         }
    2121             : }
    2122             : 
    2123             : // RangeKeyChanged indicates whether the most recent iterator positioning
    2124             : // operation resulted in the iterator stepping into or out of a new range key.
    2125             : // If true, previously returned range key bounds and data has been invalidated.
    2126             : // If false, previously obtained range key bounds, suffix and value slices are
    2127             : // still valid and may continue to be read.
    2128             : //
    2129             : // Invalid iterator positions are considered to not hold range keys, meaning
    2130             : // that if an iterator steps from an IterExhausted or IterAtLimit position onto
    2131             : // a position with a range key, RangeKeyChanged will yield true.
    2132           1 : func (i *Iterator) RangeKeyChanged() bool {
    2133           1 :         return i.iterValidityState == IterValid && i.rangeKey != nil && i.rangeKey.updated
    2134           1 : }
    2135             : 
    2136             : // HasPointAndRange indicates whether there exists a point key, a range key or
    2137             : // both at the current iterator position.
    2138           1 : func (i *Iterator) HasPointAndRange() (hasPoint, hasRange bool) {
    2139           1 :         if i.iterValidityState != IterValid || i.requiresReposition {
    2140           1 :                 return false, false
    2141           1 :         }
    2142           1 :         if i.opts.KeyTypes == IterKeyTypePointsOnly {
    2143           1 :                 return true, false
    2144           1 :         }
    2145           1 :         return i.rangeKey == nil || !i.rangeKey.rangeKeyOnly, i.rangeKey != nil && i.rangeKey.hasRangeKey
    2146             : }
    2147             : 
    2148             : // RangeBounds returns the start (inclusive) and end (exclusive) bounds of the
    2149             : // range key covering the current iterator position. RangeBounds returns nil
    2150             : // bounds if there is no range key covering the current iterator position, or
    2151             : // the iterator is not configured to surface range keys.
    2152             : //
    2153             : // If valid, the returned start bound is less than or equal to Key() and the
    2154             : // returned end bound is greater than Key().
    2155           1 : func (i *Iterator) RangeBounds() (start, end []byte) {
    2156           1 :         if i.rangeKey == nil || !i.opts.rangeKeys() || !i.rangeKey.hasRangeKey {
    2157           0 :                 return nil, nil
    2158           0 :         }
    2159           1 :         return i.rangeKey.start, i.rangeKey.end
    2160             : }
    2161             : 
    2162             : // Key returns the key of the current key/value pair, or nil if done. The
    2163             : // caller should not modify the contents of the returned slice, and its
    2164             : // contents may change on the next call to Next.
    2165             : //
    2166             : // If positioned at an iterator position that only holds a range key, Key()
    2167             : // always returns the start bound of the range key. Otherwise, it returns the
    2168             : // point key's key.
    2169           1 : func (i *Iterator) Key() []byte {
    2170           1 :         return i.key
    2171           1 : }
    2172             : 
    2173             : // Value returns the value of the current key/value pair, or nil if done. The
    2174             : // caller should not modify the contents of the returned slice, and its
    2175             : // contents may change on the next call to Next.
    2176             : //
    2177             : // Only valid if HasPointAndRange() returns true for hasPoint.
    2178             : // Deprecated: use ValueAndErr instead.
    2179           1 : func (i *Iterator) Value() []byte {
    2180           1 :         val, _ := i.ValueAndErr()
    2181           1 :         return val
    2182           1 : }
    2183             : 
    2184             : // ValueAndErr returns the value, and any error encountered in extracting the value.
    2185             : // REQUIRES: i.Error()==nil and HasPointAndRange() returns true for hasPoint.
    2186             : //
    2187             : // The caller should not modify the contents of the returned slice, and its
    2188             : // contents may change on the next call to Next.
    2189           1 : func (i *Iterator) ValueAndErr() ([]byte, error) {
    2190           1 :         val, callerOwned, err := i.value.Value(i.lazyValueBuf)
    2191           1 :         if err != nil {
    2192           0 :                 i.err = err
    2193           0 :         }
    2194           1 :         if callerOwned {
    2195           1 :                 i.lazyValueBuf = val[:0]
    2196           1 :         }
    2197           1 :         return val, err
    2198             : }
    2199             : 
    2200             : // LazyValue returns the LazyValue. Only for advanced use cases.
    2201             : // REQUIRES: i.Error()==nil and HasPointAndRange() returns true for hasPoint.
    2202           0 : func (i *Iterator) LazyValue() LazyValue {
    2203           0 :         return i.value
    2204           0 : }
    2205             : 
    2206             : // RangeKeys returns the range key values and their suffixes covering the
    2207             : // current iterator position. The range bounds may be retrieved separately
    2208             : // through Iterator.RangeBounds().
    2209           1 : func (i *Iterator) RangeKeys() []RangeKeyData {
    2210           1 :         if i.rangeKey == nil || !i.opts.rangeKeys() || !i.rangeKey.hasRangeKey {
    2211           0 :                 return nil
    2212           0 :         }
    2213           1 :         return i.rangeKey.keys
    2214             : }
    2215             : 
    2216             : // Valid returns true if the iterator is positioned at a valid key/value pair
    2217             : // and false otherwise.
    2218           1 : func (i *Iterator) Valid() bool {
    2219           1 :         valid := i.iterValidityState == IterValid && !i.requiresReposition
    2220           1 :         if invariants.Enabled {
    2221           1 :                 if err := i.Error(); valid && err != nil {
    2222           0 :                         panic(errors.WithSecondaryError(errors.AssertionFailedf("pebble: iterator is valid with non-nil Error"), err))
    2223             :                 }
    2224             :         }
    2225           1 :         return valid
    2226             : }
    2227             : 
    2228             : // Error returns any accumulated error.
    2229           1 : func (i *Iterator) Error() error {
    2230           1 :         if i.iter != nil {
    2231           1 :                 return firstError(i.err, i.iter.Error())
    2232           1 :         }
    2233           0 :         return i.err
    2234             : }
    2235             : 
    2236             : const maxKeyBufCacheSize = 4 << 10 // 4 KB
    2237             : 
    2238             : // Close closes the iterator and returns any accumulated error. Exhausting
    2239             : // all the key/value pairs in a table is not considered to be an error.
    2240             : // It is not valid to call any method, including Close, after the iterator
    2241             : // has been closed.
    2242           1 : func (i *Iterator) Close() error {
    2243           1 :         // Close the child iterator before releasing the readState because when the
    2244           1 :         // readState is released sstables referenced by the readState may be deleted
    2245           1 :         // which will fail on Windows if the sstables are still open by the child
    2246           1 :         // iterator.
    2247           1 :         if i.iter != nil {
    2248           1 :                 i.err = firstError(i.err, i.iter.Close())
    2249           1 : 
    2250           1 :                 // Closing i.iter did not necessarily close the point and range key
    2251           1 :                 // iterators. Calls to SetOptions may have 'disconnected' either one
    2252           1 :                 // from i.iter if iteration key types were changed. Both point and range
    2253           1 :                 // key iterators are preserved in case the iterator needs to switch key
    2254           1 :                 // types again. We explicitly close both of these iterators here.
    2255           1 :                 //
    2256           1 :                 // NB: If the iterators were still connected to i.iter, they may be
    2257           1 :                 // closed, but calling Close on a closed internal iterator or fragment
    2258           1 :                 // iterator is allowed.
    2259           1 :                 if i.pointIter != nil && !i.closePointIterOnce {
    2260           1 :                         i.err = firstError(i.err, i.pointIter.Close())
    2261           1 :                 }
    2262           1 :                 if i.rangeKey != nil && i.rangeKey.rangeKeyIter != nil {
    2263           1 :                         i.err = firstError(i.err, i.rangeKey.rangeKeyIter.Close())
    2264           1 :                 }
    2265             :         }
    2266           1 :         err := i.err
    2267           1 : 
    2268           1 :         if i.readState != nil {
    2269           1 :                 if i.readSampling.pendingCompactions.size > 0 {
    2270           1 :                         // Copy pending read compactions using db.mu.Lock()
    2271           1 :                         i.readState.db.mu.Lock()
    2272           1 :                         i.readState.db.mu.compact.readCompactions.combine(&i.readSampling.pendingCompactions, i.cmp)
    2273           1 :                         reschedule := i.readState.db.mu.compact.rescheduleReadCompaction
    2274           1 :                         i.readState.db.mu.compact.rescheduleReadCompaction = false
    2275           1 :                         concurrentCompactions := i.readState.db.mu.compact.compactingCount
    2276           1 :                         i.readState.db.mu.Unlock()
    2277           1 : 
    2278           1 :                         if reschedule && concurrentCompactions == 0 {
    2279           0 :                                 // In a read heavy workload, flushes may not happen frequently enough to
    2280           0 :                                 // schedule compactions.
    2281           0 :                                 i.readState.db.compactionSchedulers.Add(1)
    2282           0 :                                 go i.readState.db.maybeScheduleCompactionAsync()
    2283           0 :                         }
    2284             :                 }
    2285             : 
    2286           1 :                 i.readState.unref()
    2287           1 :                 i.readState = nil
    2288             :         }
    2289             : 
    2290           1 :         if i.version != nil {
    2291           1 :                 i.version.Unref()
    2292           1 :         }
    2293             : 
    2294           1 :         for _, readers := range i.externalReaders {
    2295           1 :                 for _, r := range readers {
    2296           1 :                         err = firstError(err, r.Close())
    2297           1 :                 }
    2298             :         }
    2299             : 
    2300             :         // Close the closer for the current value if one was open.
    2301           1 :         if i.valueCloser != nil {
    2302           1 :                 err = firstError(err, i.valueCloser.Close())
    2303           1 :                 i.valueCloser = nil
    2304           1 :         }
    2305             : 
    2306           1 :         if i.rangeKey != nil {
    2307           1 : 
    2308           1 :                 i.rangeKey.rangeKeyBuffers.PrepareForReuse()
    2309           1 :                 *i.rangeKey = iteratorRangeKeyState{
    2310           1 :                         rangeKeyBuffers: i.rangeKey.rangeKeyBuffers,
    2311           1 :                 }
    2312           1 :                 iterRangeKeyStateAllocPool.Put(i.rangeKey)
    2313           1 :                 i.rangeKey = nil
    2314           1 :         }
    2315           1 :         if alloc := i.alloc; alloc != nil {
    2316           1 :                 // Avoid caching the key buf if it is overly large. The constant is fairly
    2317           1 :                 // arbitrary.
    2318           1 :                 if cap(i.keyBuf) >= maxKeyBufCacheSize {
    2319           0 :                         alloc.keyBuf = nil
    2320           1 :                 } else {
    2321           1 :                         alloc.keyBuf = i.keyBuf
    2322           1 :                 }
    2323           1 :                 if cap(i.prefixOrFullSeekKey) >= maxKeyBufCacheSize {
    2324           0 :                         alloc.prefixOrFullSeekKey = nil
    2325           1 :                 } else {
    2326           1 :                         alloc.prefixOrFullSeekKey = i.prefixOrFullSeekKey
    2327           1 :                 }
    2328           1 :                 for j := range i.boundsBuf {
    2329           1 :                         if cap(i.boundsBuf[j]) >= maxKeyBufCacheSize {
    2330           0 :                                 alloc.boundsBuf[j] = nil
    2331           1 :                         } else {
    2332           1 :                                 alloc.boundsBuf[j] = i.boundsBuf[j]
    2333           1 :                         }
    2334             :                 }
    2335           1 :                 *alloc = iterAlloc{
    2336           1 :                         keyBuf:              alloc.keyBuf,
    2337           1 :                         boundsBuf:           alloc.boundsBuf,
    2338           1 :                         prefixOrFullSeekKey: alloc.prefixOrFullSeekKey,
    2339           1 :                 }
    2340           1 :                 iterAllocPool.Put(alloc)
    2341           1 :         } else if alloc := i.getIterAlloc; alloc != nil {
    2342           1 :                 if cap(i.keyBuf) >= maxKeyBufCacheSize {
    2343           0 :                         alloc.keyBuf = nil
    2344           1 :                 } else {
    2345           1 :                         alloc.keyBuf = i.keyBuf
    2346           1 :                 }
    2347           1 :                 *alloc = getIterAlloc{
    2348           1 :                         keyBuf: alloc.keyBuf,
    2349           1 :                 }
    2350           1 :                 getIterAllocPool.Put(alloc)
    2351             :         }
    2352           1 :         return err
    2353             : }
    2354             : 
    2355             : // SetBounds sets the lower and upper bounds for the iterator. Once SetBounds
    2356             : // returns, the caller is free to mutate the provided slices.
    2357             : //
    2358             : // The iterator will always be invalidated and must be repositioned with a call
    2359             : // to SeekGE, SeekPrefixGE, SeekLT, First, or Last.
    2360           1 : func (i *Iterator) SetBounds(lower, upper []byte) {
    2361           1 :         // Ensure that the Iterator appears exhausted, regardless of whether we
    2362           1 :         // actually have to invalidate the internal iterator. Optimizations that
    2363           1 :         // avoid exhaustion are an internal implementation detail that shouldn't
    2364           1 :         // leak through the interface. The caller should still call an absolute
    2365           1 :         // positioning method to reposition the iterator.
    2366           1 :         i.requiresReposition = true
    2367           1 : 
    2368           1 :         if ((i.opts.LowerBound == nil) == (lower == nil)) &&
    2369           1 :                 ((i.opts.UpperBound == nil) == (upper == nil)) &&
    2370           1 :                 i.equal(i.opts.LowerBound, lower) &&
    2371           1 :                 i.equal(i.opts.UpperBound, upper) {
    2372           1 :                 // Unchanged, noop.
    2373           1 :                 return
    2374           1 :         }
    2375             : 
    2376             :         // Copy the user-provided bounds into an Iterator-owned buffer, and set them
    2377             :         // on i.opts.{Lower,Upper}Bound.
    2378           1 :         i.processBounds(lower, upper)
    2379           1 : 
    2380           1 :         i.iter.SetBounds(i.opts.LowerBound, i.opts.UpperBound)
    2381           1 :         // If the iterator has an open point iterator that's not currently being
    2382           1 :         // used, propagate the new bounds to it.
    2383           1 :         if i.pointIter != nil && !i.opts.pointKeys() {
    2384           1 :                 i.pointIter.SetBounds(i.opts.LowerBound, i.opts.UpperBound)
    2385           1 :         }
    2386             :         // If the iterator has a range key iterator, propagate bounds to it. The
    2387             :         // top-level SetBounds on the interleaving iterator (i.iter) won't propagate
    2388             :         // bounds to the range key iterator stack, because the FragmentIterator
    2389             :         // interface doesn't define a SetBounds method. We need to directly inform
    2390             :         // the iterConfig stack.
    2391           1 :         if i.rangeKey != nil {
    2392           1 :                 i.rangeKey.iterConfig.SetBounds(i.opts.LowerBound, i.opts.UpperBound)
    2393           1 :         }
    2394             : 
    2395             :         // Even though this is not a positioning operation, the alteration of the
    2396             :         // bounds means we cannot optimize Seeks by using Next.
    2397           1 :         i.invalidate()
    2398             : }
    2399             : 
    2400             : // SetContext replaces the context provided at iterator creation, or the last
    2401             : // one provided by SetContext. Even though iterators are expected to be
    2402             : // short-lived, there are some cases where either (a) iterators are used far
    2403             : // from the code that created them, (b) iterators are reused (while being
    2404             : // short-lived) for processing different requests. For such scenarios, we
    2405             : // allow the caller to replace the context.
    2406           0 : func (i *Iterator) SetContext(ctx context.Context) {
    2407           0 :         i.ctx = ctx
    2408           0 :         i.iter.SetContext(ctx)
    2409           0 :         // If the iterator has an open point iterator that's not currently being
    2410           0 :         // used, propagate the new context to it.
    2411           0 :         if i.pointIter != nil && !i.opts.pointKeys() {
    2412           0 :                 i.pointIter.SetContext(i.ctx)
    2413           0 :         }
    2414             : }
    2415             : 
    2416             : // Initialization and changing of the bounds must call processBounds.
    2417             : // processBounds saves the bounds and computes derived state from those
    2418             : // bounds.
    2419           1 : func (i *Iterator) processBounds(lower, upper []byte) {
    2420           1 :         // Copy the user-provided bounds into an Iterator-owned buffer. We can't
    2421           1 :         // overwrite the current bounds, because some internal iterators compare old
    2422           1 :         // and new bounds for optimizations.
    2423           1 : 
    2424           1 :         buf := i.boundsBuf[i.boundsBufIdx][:0]
    2425           1 :         if lower != nil {
    2426           1 :                 buf = append(buf, lower...)
    2427           1 :                 i.opts.LowerBound = buf
    2428           1 :         } else {
    2429           1 :                 i.opts.LowerBound = nil
    2430           1 :         }
    2431           1 :         i.nextPrefixNotPermittedByUpperBound = false
    2432           1 :         if upper != nil {
    2433           1 :                 buf = append(buf, upper...)
    2434           1 :                 i.opts.UpperBound = buf[len(buf)-len(upper):]
    2435           1 :                 if i.comparer.Split != nil {
    2436           1 :                         if i.comparer.Split(i.opts.UpperBound) != len(i.opts.UpperBound) {
    2437           1 :                                 // Setting an upper bound that is a versioned MVCC key. This means
    2438           1 :                                 // that a key can have some MVCC versions before the upper bound and
    2439           1 :                                 // some after. This causes significant complications for NextPrefix,
    2440           1 :                                 // so we bar the user of NextPrefix.
    2441           1 :                                 i.nextPrefixNotPermittedByUpperBound = true
    2442           1 :                         }
    2443             :                 }
    2444           1 :         } else {
    2445           1 :                 i.opts.UpperBound = nil
    2446           1 :         }
    2447           1 :         i.boundsBuf[i.boundsBufIdx] = buf
    2448           1 :         i.boundsBufIdx = 1 - i.boundsBufIdx
    2449             : }
    2450             : 
    2451             : // SetOptions sets new iterator options for the iterator. Note that the lower
    2452             : // and upper bounds applied here will supersede any bounds set by previous calls
    2453             : // to SetBounds.
    2454             : //
    2455             : // Note that the slices provided in this SetOptions must not be changed by the
    2456             : // caller until the iterator is closed, or a subsequent SetBounds or SetOptions
    2457             : // has returned. This is because comparisons between the existing and new bounds
    2458             : // are sometimes used to optimize seeking. See the extended commentary on
    2459             : // SetBounds.
    2460             : //
    2461             : // If the iterator was created over an indexed mutable batch, the iterator's
    2462             : // view of the mutable batch is refreshed.
    2463             : //
    2464             : // The iterator will always be invalidated and must be repositioned with a call
    2465             : // to SeekGE, SeekPrefixGE, SeekLT, First, or Last.
    2466             : //
    2467             : // If only lower and upper bounds need to be modified, prefer SetBounds.
    2468           1 : func (i *Iterator) SetOptions(o *IterOptions) {
    2469           1 :         if i.externalReaders != nil {
    2470           1 :                 if err := validateExternalIterOpts(o); err != nil {
    2471           0 :                         panic(err)
    2472             :                 }
    2473             :         }
    2474             : 
    2475             :         // Ensure that the Iterator appears exhausted, regardless of whether we
    2476             :         // actually have to invalidate the internal iterator. Optimizations that
    2477             :         // avoid exhaustion are an internal implementation detail that shouldn't
    2478             :         // leak through the interface. The caller should still call an absolute
    2479             :         // positioning method to reposition the iterator.
    2480           1 :         i.requiresReposition = true
    2481           1 : 
    2482           1 :         // Check if global state requires we close all internal iterators.
    2483           1 :         //
    2484           1 :         // If the Iterator is in an error state, invalidate the existing iterators
    2485           1 :         // so that we reconstruct an iterator state from scratch.
    2486           1 :         //
    2487           1 :         // If OnlyReadGuaranteedDurable changed, the iterator stacks are incorrect,
    2488           1 :         // improperly including or excluding memtables. Invalidate them so that
    2489           1 :         // finishInitializingIter will reconstruct them.
    2490           1 :         //
    2491           1 :         // If either the original options or the new options specify a table filter,
    2492           1 :         // we need to reconstruct the iterator stacks. If they both supply a table
    2493           1 :         // filter, we can't be certain that it's the same filter since we have no
    2494           1 :         // mechanism to compare the filter closures.
    2495           1 :         closeBoth := i.err != nil ||
    2496           1 :                 o.OnlyReadGuaranteedDurable != i.opts.OnlyReadGuaranteedDurable ||
    2497           1 :                 o.TableFilter != nil || i.opts.TableFilter != nil
    2498           1 : 
    2499           1 :         // If either options specify block property filters for an iterator stack,
    2500           1 :         // reconstruct it.
    2501           1 :         if i.pointIter != nil && (closeBoth || len(o.PointKeyFilters) > 0 || len(i.opts.PointKeyFilters) > 0 ||
    2502           1 :                 o.RangeKeyMasking.Filter != nil || i.opts.RangeKeyMasking.Filter != nil || o.SkipPoint != nil ||
    2503           1 :                 i.opts.SkipPoint != nil) {
    2504           1 :                 i.err = firstError(i.err, i.pointIter.Close())
    2505           1 :                 i.pointIter = nil
    2506           1 :         }
    2507           1 :         if i.rangeKey != nil {
    2508           1 :                 if closeBoth || len(o.RangeKeyFilters) > 0 || len(i.opts.RangeKeyFilters) > 0 {
    2509           1 :                         i.err = firstError(i.err, i.rangeKey.rangeKeyIter.Close())
    2510           1 :                         i.rangeKey = nil
    2511           1 :                 } else {
    2512           1 :                         // If there's still a range key iterator stack, invalidate the
    2513           1 :                         // iterator. This ensures RangeKeyChanged() returns true if a
    2514           1 :                         // subsequent positioning operation discovers a range key. It also
    2515           1 :                         // prevents seek no-op optimizations.
    2516           1 :                         i.invalidate()
    2517           1 :                 }
    2518             :         }
    2519             : 
    2520             :         // If the iterator is backed by a batch that's been mutated, refresh its
    2521             :         // existing point and range-key iterators, and invalidate the iterator to
    2522             :         // prevent seek-using-next optimizations. If we don't yet have a point-key
    2523             :         // iterator or range-key iterator but we require one, it'll be created in
    2524             :         // the slow path that reconstructs the iterator in finishInitializingIter.
    2525           1 :         if i.batch != nil {
    2526           1 :                 nextBatchSeqNum := (uint64(len(i.batch.data)) | base.InternalKeySeqNumBatch)
    2527           1 :                 if nextBatchSeqNum != i.batchSeqNum {
    2528           1 :                         i.batchSeqNum = nextBatchSeqNum
    2529           1 :                         if i.merging != nil {
    2530           1 :                                 i.merging.batchSnapshot = nextBatchSeqNum
    2531           1 :                         }
    2532             :                         // Prevent a no-op seek optimization on the next seek. We won't be
    2533             :                         // able to reuse the top-level Iterator state, because it may be
    2534             :                         // incorrect after the inclusion of new batch mutations.
    2535           1 :                         i.batchJustRefreshed = true
    2536           1 :                         if i.pointIter != nil && i.batch.countRangeDels > 0 {
    2537           1 :                                 if i.batchRangeDelIter.Count() == 0 {
    2538           1 :                                         // When we constructed this iterator, there were no
    2539           1 :                                         // rangedels in the batch. Iterator construction will
    2540           1 :                                         // have excluded the batch rangedel iterator from the
    2541           1 :                                         // point iterator stack. We need to reconstruct the
    2542           1 :                                         // point iterator to add i.batchRangeDelIter into the
    2543           1 :                                         // iterator stack.
    2544           1 :                                         i.err = firstError(i.err, i.pointIter.Close())
    2545           1 :                                         i.pointIter = nil
    2546           1 :                                 } else {
    2547           1 :                                         // There are range deletions in the batch and we already
    2548           1 :                                         // have a batch rangedel iterator. We can update the
    2549           1 :                                         // batch rangedel iterator in place.
    2550           1 :                                         //
    2551           1 :                                         // NB: There may or may not be new range deletions. We
    2552           1 :                                         // can't tell based on i.batchRangeDelIter.Count(),
    2553           1 :                                         // which is the count of fragmented range deletions, NOT
    2554           1 :                                         // the number of range deletions written to the batch
    2555           1 :                                         // [i.batch.countRangeDels].
    2556           1 :                                         i.batch.initRangeDelIter(&i.opts, &i.batchRangeDelIter, nextBatchSeqNum)
    2557           1 :                                 }
    2558             :                         }
    2559           1 :                         if i.rangeKey != nil && i.batch.countRangeKeys > 0 {
    2560           1 :                                 if i.batchRangeKeyIter.Count() == 0 {
    2561           1 :                                         // When we constructed this iterator, there were no range
    2562           1 :                                         // keys in the batch. Iterator construction will have
    2563           1 :                                         // excluded the batch rangekey iterator from the range key
    2564           1 :                                         // iterator stack. We need to reconstruct the range key
    2565           1 :                                         // iterator to add i.batchRangeKeyIter into the iterator
    2566           1 :                                         // stack.
    2567           1 :                                         i.err = firstError(i.err, i.rangeKey.rangeKeyIter.Close())
    2568           1 :                                         i.rangeKey = nil
    2569           1 :                                 } else {
    2570           1 :                                         // There are range keys in the batch and we already
    2571           1 :                                         // have a batch rangekey iterator. We can update the batch
    2572           1 :                                         // rangekey iterator in place.
    2573           1 :                                         //
    2574           1 :                                         // NB: There may or may not be new range keys. We can't
    2575           1 :                                         // tell based on i.batchRangeKeyIter.Count(), which is the
    2576           1 :                                         // count of fragmented range keys, NOT the number of
    2577           1 :                                         // range keys written to the batch [i.batch.countRangeKeys].
    2578           1 :                                         i.batch.initRangeKeyIter(&i.opts, &i.batchRangeKeyIter, nextBatchSeqNum)
    2579           1 :                                         i.invalidate()
    2580           1 :                                 }
    2581             :                         }
    2582             :                 }
    2583             :         }
    2584             : 
    2585             :         // Reset combinedIterState.initialized in case the iterator key types
    2586             :         // changed. If there's already a range key iterator stack, the combined
    2587             :         // iterator is already initialized.  Additionally, if the iterator is not
    2588             :         // configured to include range keys, mark it as initialized to signal that
    2589             :         // lower level iterators should not trigger a switch to combined iteration.
    2590           1 :         i.lazyCombinedIter.combinedIterState = combinedIterState{
    2591           1 :                 initialized: i.rangeKey != nil || !i.opts.rangeKeys(),
    2592           1 :         }
    2593           1 : 
    2594           1 :         boundsEqual := ((i.opts.LowerBound == nil) == (o.LowerBound == nil)) &&
    2595           1 :                 ((i.opts.UpperBound == nil) == (o.UpperBound == nil)) &&
    2596           1 :                 i.equal(i.opts.LowerBound, o.LowerBound) &&
    2597           1 :                 i.equal(i.opts.UpperBound, o.UpperBound)
    2598           1 : 
    2599           1 :         if boundsEqual && o.KeyTypes == i.opts.KeyTypes &&
    2600           1 :                 (i.pointIter != nil || !i.opts.pointKeys()) &&
    2601           1 :                 (i.rangeKey != nil || !i.opts.rangeKeys() || i.opts.KeyTypes == IterKeyTypePointsAndRanges) &&
    2602           1 :                 i.equal(o.RangeKeyMasking.Suffix, i.opts.RangeKeyMasking.Suffix) &&
    2603           1 :                 o.UseL6Filters == i.opts.UseL6Filters {
    2604           1 :                 // The options are identical, so we can likely use the fast path. In
    2605           1 :                 // addition to all the above constraints, we cannot use the fast path if
    2606           1 :                 // configured to perform lazy combined iteration but an indexed batch
    2607           1 :                 // used by the iterator now contains range keys. Lazy combined iteration
    2608           1 :                 // is not compatible with batch range keys because we always need to
    2609           1 :                 // merge the batch's range keys into iteration.
    2610           1 :                 if i.rangeKey != nil || !i.opts.rangeKeys() || i.batch == nil || i.batch.countRangeKeys == 0 {
    2611           1 :                         // Fast path. This preserves the Seek-using-Next optimizations as
    2612           1 :                         // long as the iterator wasn't already invalidated up above.
    2613           1 :                         return
    2614           1 :                 }
    2615             :         }
    2616             :         // Slow path.
    2617             : 
    2618             :         // The options changed. Save the new ones to i.opts.
    2619           1 :         if boundsEqual {
    2620           1 :                 // Copying the options into i.opts will overwrite LowerBound and
    2621           1 :                 // UpperBound fields with the user-provided slices. We need to hold on
    2622           1 :                 // to the Pebble-owned slices, so save them and re-set them after the
    2623           1 :                 // copy.
    2624           1 :                 lower, upper := i.opts.LowerBound, i.opts.UpperBound
    2625           1 :                 i.opts = *o
    2626           1 :                 i.opts.LowerBound, i.opts.UpperBound = lower, upper
    2627           1 :         } else {
    2628           1 :                 i.opts = *o
    2629           1 :                 i.processBounds(o.LowerBound, o.UpperBound)
    2630           1 :                 // Propagate the changed bounds to the existing point iterator.
    2631           1 :                 // NB: We propagate i.opts.{Lower,Upper}Bound, not o.{Lower,Upper}Bound
    2632           1 :                 // because i.opts now point to buffers owned by Pebble.
    2633           1 :                 if i.pointIter != nil {
    2634           1 :                         i.pointIter.SetBounds(i.opts.LowerBound, i.opts.UpperBound)
    2635           1 :                 }
    2636           1 :                 if i.rangeKey != nil {
    2637           1 :                         i.rangeKey.iterConfig.SetBounds(i.opts.LowerBound, i.opts.UpperBound)
    2638           1 :                 }
    2639             :         }
    2640             : 
    2641             :         // Even though this is not a positioning operation, the invalidation of the
    2642             :         // iterator stack means we cannot optimize Seeks by using Next.
    2643           1 :         i.invalidate()
    2644           1 : 
    2645           1 :         // Iterators created through NewExternalIter have a different iterator
    2646           1 :         // initialization process.
    2647           1 :         if i.externalReaders != nil {
    2648           1 :                 finishInitializingExternal(i.ctx, i)
    2649           1 :                 return
    2650           1 :         }
    2651           1 :         finishInitializingIter(i.ctx, i.alloc)
    2652             : }
    2653             : 
    2654           1 : func (i *Iterator) invalidate() {
    2655           1 :         i.lastPositioningOp = invalidatedLastPositionOp
    2656           1 :         i.hasPrefix = false
    2657           1 :         i.iterKey = nil
    2658           1 :         i.iterValue = LazyValue{}
    2659           1 :         i.err = nil
    2660           1 :         // This switch statement isn't necessary for correctness since callers
    2661           1 :         // should call a repositioning method. We could have arbitrarily set i.pos
    2662           1 :         // to one of the values. But it results in more intuitive behavior in
    2663           1 :         // tests, which do not always reposition.
    2664           1 :         switch i.pos {
    2665           1 :         case iterPosCurForward, iterPosNext, iterPosCurForwardPaused:
    2666           1 :                 i.pos = iterPosCurForward
    2667           1 :         case iterPosCurReverse, iterPosPrev, iterPosCurReversePaused:
    2668           1 :                 i.pos = iterPosCurReverse
    2669             :         }
    2670           1 :         i.iterValidityState = IterExhausted
    2671           1 :         if i.rangeKey != nil {
    2672           1 :                 i.rangeKey.iiter.Invalidate()
    2673           1 :                 i.rangeKey.prevPosHadRangeKey = false
    2674           1 :         }
    2675             : }
    2676             : 
    2677             : // Metrics returns per-iterator metrics.
    2678           0 : func (i *Iterator) Metrics() IteratorMetrics {
    2679           0 :         m := IteratorMetrics{
    2680           0 :                 ReadAmp: 1,
    2681           0 :         }
    2682           0 :         if mi, ok := i.iter.(*mergingIter); ok {
    2683           0 :                 m.ReadAmp = len(mi.levels)
    2684           0 :         }
    2685           0 :         return m
    2686             : }
    2687             : 
    2688             : // ResetStats resets the stats to 0.
    2689           0 : func (i *Iterator) ResetStats() {
    2690           0 :         i.stats = IteratorStats{}
    2691           0 : }
    2692             : 
    2693             : // Stats returns the current stats.
    2694           1 : func (i *Iterator) Stats() IteratorStats {
    2695           1 :         return i.stats
    2696           1 : }
    2697             : 
    2698             : // CloneOptions configures an iterator constructed through Iterator.Clone.
    2699             : type CloneOptions struct {
    2700             :         // IterOptions, if non-nil, define the iterator options to configure a
    2701             :         // cloned iterator. If nil, the clone adopts the same IterOptions as the
    2702             :         // iterator being cloned.
    2703             :         IterOptions *IterOptions
    2704             :         // RefreshBatchView may be set to true when cloning an Iterator over an
    2705             :         // indexed batch. When false, the clone adopts the same (possibly stale)
    2706             :         // view of the indexed batch as the cloned Iterator. When true, the clone is
    2707             :         // constructed with a refreshed view of the batch, observing all of the
    2708             :         // batch's mutations at the time of the Clone. If the cloned iterator was
    2709             :         // not constructed to read over an indexed batch, RefreshVatchView has no
    2710             :         // effect.
    2711             :         RefreshBatchView bool
    2712             : }
    2713             : 
    2714             : // Clone creates a new Iterator over the same underlying data, i.e., over the
    2715             : // same {batch, memtables, sstables}). The resulting iterator is not positioned.
    2716             : // It starts with the same IterOptions, unless opts.IterOptions is set.
    2717             : //
    2718             : // When called on an Iterator over an indexed batch, the clone's visibility of
    2719             : // the indexed batch is determined by CloneOptions.RefreshBatchView. If false,
    2720             : // the clone inherits the iterator's current (possibly stale) view of the batch,
    2721             : // and callers may call SetOptions to subsequently refresh the clone's view to
    2722             : // include all batch mutations. If true, the clone is constructed with a
    2723             : // complete view of the indexed batch's mutations at the time of the Clone.
    2724             : //
    2725             : // Callers can use Clone if they need multiple iterators that need to see
    2726             : // exactly the same underlying state of the DB. This should not be used to
    2727             : // extend the lifetime of the data backing the original Iterator since that
    2728             : // will cause an increase in memory and disk usage (use NewSnapshot for that
    2729             : // purpose).
    2730           1 : func (i *Iterator) Clone(opts CloneOptions) (*Iterator, error) {
    2731           1 :         return i.CloneWithContext(context.Background(), opts)
    2732           1 : }
    2733             : 
    2734             : // CloneWithContext is like Clone, and additionally accepts a context for
    2735             : // tracing.
    2736           1 : func (i *Iterator) CloneWithContext(ctx context.Context, opts CloneOptions) (*Iterator, error) {
    2737           1 :         if opts.IterOptions == nil {
    2738           1 :                 opts.IterOptions = &i.opts
    2739           1 :         }
    2740           1 :         if i.batchOnlyIter {
    2741           1 :                 return nil, errors.Errorf("cannot Clone a batch-only Iterator")
    2742           1 :         }
    2743           1 :         readState := i.readState
    2744           1 :         vers := i.version
    2745           1 :         if readState == nil && vers == nil {
    2746           1 :                 return nil, errors.Errorf("cannot Clone a closed Iterator")
    2747           1 :         }
    2748             :         // i is already holding a ref, so there is no race with unref here.
    2749             :         //
    2750             :         // TODO(bilal): If the underlying iterator was created on a snapshot, we could
    2751             :         // grab a reference to the current readState instead of reffing the original
    2752             :         // readState. This allows us to release references to some zombie sstables
    2753             :         // and memtables.
    2754           1 :         if readState != nil {
    2755           1 :                 readState.ref()
    2756           1 :         }
    2757           1 :         if vers != nil {
    2758           1 :                 vers.Ref()
    2759           1 :         }
    2760             :         // Bundle various structures under a single umbrella in order to allocate
    2761             :         // them together.
    2762           1 :         buf := iterAllocPool.Get().(*iterAlloc)
    2763           1 :         dbi := &buf.dbi
    2764           1 :         *dbi = Iterator{
    2765           1 :                 ctx:                 ctx,
    2766           1 :                 opts:                *opts.IterOptions,
    2767           1 :                 alloc:               buf,
    2768           1 :                 merge:               i.merge,
    2769           1 :                 comparer:            i.comparer,
    2770           1 :                 readState:           readState,
    2771           1 :                 version:             vers,
    2772           1 :                 keyBuf:              buf.keyBuf,
    2773           1 :                 prefixOrFullSeekKey: buf.prefixOrFullSeekKey,
    2774           1 :                 boundsBuf:           buf.boundsBuf,
    2775           1 :                 batch:               i.batch,
    2776           1 :                 batchSeqNum:         i.batchSeqNum,
    2777           1 :                 newIters:            i.newIters,
    2778           1 :                 newIterRangeKey:     i.newIterRangeKey,
    2779           1 :                 seqNum:              i.seqNum,
    2780           1 :         }
    2781           1 :         dbi.processBounds(dbi.opts.LowerBound, dbi.opts.UpperBound)
    2782           1 : 
    2783           1 :         // If the caller requested the clone have a current view of the indexed
    2784           1 :         // batch, set the clone's batch sequence number appropriately.
    2785           1 :         if i.batch != nil && opts.RefreshBatchView {
    2786           1 :                 dbi.batchSeqNum = (uint64(len(i.batch.data)) | base.InternalKeySeqNumBatch)
    2787           1 :         }
    2788             : 
    2789           1 :         return finishInitializingIter(ctx, buf), nil
    2790             : }
    2791             : 
    2792             : // Merge adds all of the argument's statistics to the receiver. It may be used
    2793             : // to accumulate stats across multiple iterators.
    2794           1 : func (stats *IteratorStats) Merge(o IteratorStats) {
    2795           1 :         for i := InterfaceCall; i < NumStatsKind; i++ {
    2796           1 :                 stats.ForwardSeekCount[i] += o.ForwardSeekCount[i]
    2797           1 :                 stats.ReverseSeekCount[i] += o.ReverseSeekCount[i]
    2798           1 :                 stats.ForwardStepCount[i] += o.ForwardStepCount[i]
    2799           1 :                 stats.ReverseStepCount[i] += o.ReverseStepCount[i]
    2800           1 :         }
    2801           1 :         stats.InternalStats.Merge(o.InternalStats)
    2802           1 :         stats.RangeKeyStats.Merge(o.RangeKeyStats)
    2803             : }
    2804             : 
    2805           1 : func (stats *IteratorStats) String() string {
    2806           1 :         return redact.StringWithoutMarkers(stats)
    2807           1 : }
    2808             : 
    2809             : // SafeFormat implements the redact.SafeFormatter interface.
    2810           1 : func (stats *IteratorStats) SafeFormat(s redact.SafePrinter, verb rune) {
    2811           1 :         for i := range stats.ForwardStepCount {
    2812           1 :                 switch IteratorStatsKind(i) {
    2813           1 :                 case InterfaceCall:
    2814           1 :                         s.SafeString("(interface (dir, seek, step): ")
    2815           1 :                 case InternalIterCall:
    2816           1 :                         s.SafeString(", (internal (dir, seek, step): ")
    2817             :                 }
    2818           1 :                 s.Printf("(fwd, %d, %d), (rev, %d, %d))",
    2819           1 :                         redact.Safe(stats.ForwardSeekCount[i]), redact.Safe(stats.ForwardStepCount[i]),
    2820           1 :                         redact.Safe(stats.ReverseSeekCount[i]), redact.Safe(stats.ReverseStepCount[i]))
    2821             :         }
    2822           1 :         if stats.InternalStats != (InternalIteratorStats{}) {
    2823           1 :                 s.SafeString(",\n(internal-stats: ")
    2824           1 :                 s.Printf("(block-bytes: (total %s, cached %s, read-time %s)), "+
    2825           1 :                         "(points: (count %s, key-bytes %s, value-bytes %s, tombstoned %s))",
    2826           1 :                         humanize.Bytes.Uint64(stats.InternalStats.BlockBytes),
    2827           1 :                         humanize.Bytes.Uint64(stats.InternalStats.BlockBytesInCache),
    2828           1 :                         humanize.FormattedString(stats.InternalStats.BlockReadDuration.String()),
    2829           1 :                         humanize.Count.Uint64(stats.InternalStats.PointCount),
    2830           1 :                         humanize.Bytes.Uint64(stats.InternalStats.KeyBytes),
    2831           1 :                         humanize.Bytes.Uint64(stats.InternalStats.ValueBytes),
    2832           1 :                         humanize.Count.Uint64(stats.InternalStats.PointsCoveredByRangeTombstones),
    2833           1 :                 )
    2834           1 :                 if stats.InternalStats.SeparatedPointValue.Count != 0 {
    2835           1 :                         s.Printf(", (separated: (count %s, bytes %s, fetched %s)))",
    2836           1 :                                 humanize.Count.Uint64(stats.InternalStats.SeparatedPointValue.Count),
    2837           1 :                                 humanize.Bytes.Uint64(stats.InternalStats.SeparatedPointValue.ValueBytes),
    2838           1 :                                 humanize.Bytes.Uint64(stats.InternalStats.SeparatedPointValue.ValueBytesFetched))
    2839           1 :                 } else {
    2840           1 :                         s.Printf(")")
    2841           1 :                 }
    2842             :         }
    2843           1 :         if stats.RangeKeyStats != (RangeKeyIteratorStats{}) {
    2844           1 :                 s.SafeString(",\n(range-key-stats: ")
    2845           1 :                 s.Printf("(count %d), (contained points: (count %d, skipped %d)))",
    2846           1 :                         stats.RangeKeyStats.Count,
    2847           1 :                         stats.RangeKeyStats.ContainedPoints,
    2848           1 :                         stats.RangeKeyStats.SkippedPoints)
    2849           1 :         }
    2850             : }
    2851             : 
    2852             : // CanDeterministicallySingleDelete takes a valid iterator and examines internal
    2853             : // state to determine if a SingleDelete deleting Iterator.Key() would
    2854             : // deterministically delete the key. CanDeterministicallySingleDelete requires
    2855             : // the iterator to be oriented in the forward direction (eg, the last
    2856             : // positioning operation must've been a First, a Seek[Prefix]GE, or a
    2857             : // Next[Prefix][WithLimit]).
    2858             : //
    2859             : // This function does not change the external position of the iterator, and all
    2860             : // positioning methods should behave the same as if it was never called. This
    2861             : // function will only return a meaningful result the first time it's invoked at
    2862             : // an iterator position. This function invalidates the iterator Value's memory,
    2863             : // and the caller must not rely on the memory safety of the previous Iterator
    2864             : // position.
    2865             : //
    2866             : // If CanDeterministicallySingleDelete returns true AND the key at the iterator
    2867             : // position is not modified between the creation of the Iterator and the commit
    2868             : // of a batch containing a SingleDelete over the key, then the caller can be
    2869             : // assured that SingleDelete is equivalent to Delete on the local engine, but it
    2870             : // may not be true on another engine that received the same writes and with
    2871             : // logically equivalent state since this engine may have collapsed multiple SETs
    2872             : // into one.
    2873           1 : func CanDeterministicallySingleDelete(it *Iterator) (bool, error) {
    2874           1 :         // This function may only be called once per external iterator position. We
    2875           1 :         // can validate this by checking the last positioning operation.
    2876           1 :         if it.lastPositioningOp == internalNextOp {
    2877           1 :                 return false, errors.New("pebble: CanDeterministicallySingleDelete called twice")
    2878           1 :         }
    2879           1 :         validity, kind := it.internalNext()
    2880           1 :         var shadowedBySingleDelete bool
    2881           1 :         for validity == internalNextValid {
    2882           1 :                 switch kind {
    2883           1 :                 case InternalKeyKindDelete, InternalKeyKindDeleteSized:
    2884           1 :                         // A DEL or DELSIZED tombstone is okay. An internal key
    2885           1 :                         // sequence like SINGLEDEL; SET; DEL; SET can be handled
    2886           1 :                         // deterministically. If there are SETs further down, we
    2887           1 :                         // don't care about them.
    2888           1 :                         return true, nil
    2889           1 :                 case InternalKeyKindSingleDelete:
    2890           1 :                         // A SingleDelete is okay as long as when that SingleDelete was
    2891           1 :                         // written, it was written deterministically (eg, with its own
    2892           1 :                         // CanDeterministicallySingleDelete check). Validate that it was
    2893           1 :                         // written deterministically. We'll allow one set to appear after
    2894           1 :                         // the SingleDelete.
    2895           1 :                         shadowedBySingleDelete = true
    2896           1 :                         validity, kind = it.internalNext()
    2897           1 :                         continue
    2898           1 :                 case InternalKeyKindSet, InternalKeyKindSetWithDelete, InternalKeyKindMerge:
    2899           1 :                         // If we observed a single delete, it's allowed to delete 1 key.
    2900           1 :                         // We'll keep looping to validate that the internal keys beneath the
    2901           1 :                         // already-written single delete are copacetic.
    2902           1 :                         if shadowedBySingleDelete {
    2903           1 :                                 shadowedBySingleDelete = false
    2904           1 :                                 validity, kind = it.internalNext()
    2905           1 :                                 continue
    2906             :                         }
    2907             :                         // We encountered a shadowed SET, SETWITHDEL, MERGE. A SINGLEDEL
    2908             :                         // that deleted the KV at the original iterator position could
    2909             :                         // result in this key becoming visible.
    2910           1 :                         return false, nil
    2911           0 :                 case InternalKeyKindRangeDelete:
    2912           0 :                         // RangeDeletes are handled by the merging iterator and should never
    2913           0 :                         // be observed by the top-level Iterator.
    2914           0 :                         panic(errors.AssertionFailedf("pebble: unexpected range delete"))
    2915           0 :                 case InternalKeyKindRangeKeySet, InternalKeyKindRangeKeyUnset, InternalKeyKindRangeKeyDelete:
    2916           0 :                         // Range keys are interleaved at the maximal sequence number and
    2917           0 :                         // should never be observed within a user key.
    2918           0 :                         panic(errors.AssertionFailedf("pebble: unexpected range key"))
    2919           0 :                 default:
    2920           0 :                         panic(errors.AssertionFailedf("pebble: unexpected key kind: %s", errors.Safe(kind)))
    2921             :                 }
    2922             :         }
    2923           1 :         if validity == internalNextError {
    2924           1 :                 return false, it.Error()
    2925           1 :         }
    2926           1 :         return true, nil
    2927             : }
    2928             : 
    2929             : // internalNextValidity enumerates the potential outcomes of a call to
    2930             : // internalNext.
    2931             : type internalNextValidity int8
    2932             : 
    2933             : const (
    2934             :         // internalNextError is returned by internalNext when an error occurred and
    2935             :         // the caller is responsible for checking iter.Error().
    2936             :         internalNextError internalNextValidity = iota
    2937             :         // internalNextExhausted is returned by internalNext when the next internal
    2938             :         // key is an internal key with a different user key than Iterator.Key().
    2939             :         internalNextExhausted
    2940             :         // internalNextValid is returned by internalNext when the internal next
    2941             :         // found a shadowed internal key with a user key equal to Iterator.Key().
    2942             :         internalNextValid
    2943             : )
    2944             : 
    2945             : // internalNext advances internal Iterator state forward to expose the
    2946             : // InternalKeyKind of the next internal key with a user key equal to Key().
    2947             : //
    2948             : // internalNext is a highly specialized operation and is unlikely to be
    2949             : // generally useful. See Iterator.Next for how to reposition the iterator to the
    2950             : // next key. internalNext requires the Iterator to be at a valid position in the
    2951             : // forward direction (the last positioning operation must've been a First, a
    2952             : // Seek[Prefix]GE, or a Next[Prefix][WithLimit] and Valid() must return true).
    2953             : //
    2954             : // internalNext, unlike all other Iterator methods, exposes internal LSM state.
    2955             : // internalNext advances the Iterator's internal iterator to the next shadowed
    2956             : // key with a user key equal to Key(). When a key is overwritten or deleted, its
    2957             : // removal from the LSM occurs lazily as a part of compactions. internalNext
    2958             : // allows the caller to see whether an obsolete internal key exists with the
    2959             : // current Key(), and what it's key kind is. Note that the existence of an
    2960             : // internal key is nondeterministic and dependent on internal LSM state. These
    2961             : // semantics are unlikely to be applicable to almost all use cases.
    2962             : //
    2963             : // If internalNext finds a key that shares the same user key as Key(), it
    2964             : // returns internalNextValid and the internal key's kind. If internalNext
    2965             : // encounters an error, it returns internalNextError and the caller is expected
    2966             : // to call Iterator.Error() to retrieve it. In all other circumstances,
    2967             : // internalNext returns internalNextExhausted, indicating that there are no more
    2968             : // additional internal keys with the user key Key().
    2969             : //
    2970             : // internalNext does not change the external position of the iterator, and a
    2971             : // Next operation should behave the same as if internalNext was never called.
    2972             : // internalNext does invalidate the iterator Value's memory, and the caller must
    2973             : // not rely on the memory safety of the previous Iterator position.
    2974           1 : func (i *Iterator) internalNext() (internalNextValidity, base.InternalKeyKind) {
    2975           1 :         i.stats.ForwardStepCount[InterfaceCall]++
    2976           1 :         if i.err != nil {
    2977           1 :                 return internalNextError, base.InternalKeyKindInvalid
    2978           1 :         } else if i.iterValidityState != IterValid {
    2979           1 :                 return internalNextExhausted, base.InternalKeyKindInvalid
    2980           1 :         }
    2981           1 :         i.lastPositioningOp = internalNextOp
    2982           1 : 
    2983           1 :         switch i.pos {
    2984           1 :         case iterPosCurForward:
    2985           1 :                 i.iterKey, i.iterValue = i.iter.Next()
    2986           1 :                 if i.iterKey == nil {
    2987           1 :                         // We check i.iter.Error() here and return an internalNextError enum
    2988           1 :                         // variant so that the caller does not need to check i.iter.Error()
    2989           1 :                         // in the common case that the next internal key has a new user key.
    2990           1 :                         if i.err = i.iter.Error(); i.err != nil {
    2991           0 :                                 return internalNextError, base.InternalKeyKindInvalid
    2992           0 :                         }
    2993           1 :                         i.pos = iterPosNext
    2994           1 :                         return internalNextExhausted, base.InternalKeyKindInvalid
    2995           1 :                 } else if i.comparer.Equal(i.iterKey.UserKey, i.key) {
    2996           1 :                         return internalNextValid, i.iterKey.Kind()
    2997           1 :                 }
    2998           1 :                 i.pos = iterPosNext
    2999           1 :                 return internalNextExhausted, base.InternalKeyKindInvalid
    3000           1 :         case iterPosCurReverse, iterPosCurReversePaused, iterPosPrev:
    3001           1 :                 i.err = errors.New("switching from reverse to forward via internalNext is prohibited")
    3002           1 :                 i.iterValidityState = IterExhausted
    3003           1 :                 return internalNextError, base.InternalKeyKindInvalid
    3004           1 :         case iterPosNext, iterPosCurForwardPaused:
    3005           1 :                 // The previous method already moved onto the next user key. This is
    3006           1 :                 // only possible if
    3007           1 :                 //   - the last positioning method was a call to internalNext, and we
    3008           1 :                 //     advanced to a new user key.
    3009           1 :                 //   - the previous non-internalNext iterator operation encountered a
    3010           1 :                 //     range key or merge, forcing an internal Next that found a new
    3011           1 :                 //     user key that's not equal to i.Iterator.Key().
    3012           1 :                 return internalNextExhausted, base.InternalKeyKindInvalid
    3013           0 :         default:
    3014           0 :                 panic("unreachable")
    3015             :         }
    3016             : }

Generated by: LCOV version 1.14