Line data    Source code

       1             : // Copyright 2011 The LevelDB-Go and Pebble Authors. All rights reserved. Use
       2             : // of this source code is governed by a BSD-style license that can be found in
       3             : // the LICENSE file.
       4             : 
       5             : package sstable
       6             : 
       7             : import (
       8             :         "fmt"
       9             :         "os"
      10             :         "sync"
      11             : 
      12             :         "github.com/cockroachdb/pebble/internal/base"
      13             :         "github.com/cockroachdb/pebble/internal/invariants"
      14             : )
      15             : 
      16             : // Iterator iterates over an entire table of data.
      17             : type Iterator interface {
      18             :         base.InternalIterator
      19             : 
      20             :         // NextPrefix implements (base.InternalIterator).NextPrefix.
      21             :         NextPrefix(succKey []byte) *base.InternalKV
      22             : 
      23             :         SetCloseHook(fn func(i Iterator) error)
      24             : }
      25             : 
      26             : // Iterator positioning optimizations and singleLevelIterator and
      27             : // twoLevelIterator:
      28             : //
      29             : // An iterator is absolute positioned using one of the Seek or First or Last
      30             : // calls. After absolute positioning, there can be relative positioning done
      31             : // by stepping using Prev or Next.
      32             : //
      33             : // We implement optimizations below where an absolute positioning call can in
      34             : // some cases use the current position to do less work. To understand these,
      35             : // we first define some terms. An iterator is bounds-exhausted if the bounds
      36             : // (upper of lower) have been reached. An iterator is data-exhausted if it has
      37             : // the reached the end of the data (forward or reverse) in the sstable. A
      38             : // singleLevelIterator only knows a local-data-exhausted property since when
      39             : // it is used as part of a twoLevelIterator, the twoLevelIterator can step to
      40             : // the next lower-level index block.
      41             : //
      42             : // The bounds-exhausted property is tracked by
      43             : // singleLevelIterator.exhaustedBounds being +1 (upper bound reached) or -1
      44             : // (lower bound reached). The same field is reused by twoLevelIterator. Either
      45             : // may notice the exhaustion of the bound and set it. Note that if
      46             : // singleLevelIterator sets this property, it is not a local property (since
      47             : // the bound has been reached regardless of whether this is in the context of
      48             : // the twoLevelIterator or not).
      49             : //
      50             : // The data-exhausted property is tracked in a more subtle manner. We define
      51             : // two predicates:
      52             : // - partial-local-data-exhausted (PLDE):
      53             : //   i.data.isDataInvalidated() || !i.data.valid()
      54             : // - partial-global-data-exhausted (PGDE):
      55             : //   i.index.isDataInvalidated() || !i.index.valid() || i.data.isDataInvalidated() ||
      56             : //   !i.data.valid()
      57             : //
      58             : // PLDE is defined for a singleLevelIterator. PGDE is defined for a
      59             : // twoLevelIterator. Oddly, in our code below the singleLevelIterator does not
      60             : // know when it is part of a twoLevelIterator so it does not know when its
      61             : // property is local or global.
      62             : //
      63             : // Now to define data-exhausted:
      64             : // - Prerequisite: we must know that the iterator has been positioned and
      65             : //   i.err is nil.
      66             : // - bounds-exhausted must not be true:
      67             : //   If bounds-exhausted is true, we have incomplete knowledge of
      68             : //   data-exhausted since PLDE or PGDE could be true because we could have
      69             : //   chosen not to load index block or data block and figured out that the
      70             : //   bound is exhausted (due to block property filters filtering out index and
      71             : //   data blocks and going past the bound on the top level index block). Note
      72             : //   that if we tried to separate out the BPF case from others we could
      73             : //   develop more knowledge here.
      74             : // - PGDE is true for twoLevelIterator. PLDE is true if it is a standalone
      75             : //   singleLevelIterator. !PLDE or !PGDE of course imply that data-exhausted
      76             : //   is not true.
      77             : //
      78             : // An implication of the above is that if we are going to somehow utilize
      79             : // knowledge of data-exhausted in an optimization, we must not forget the
      80             : // existing value of bounds-exhausted since by forgetting the latter we can
      81             : // erroneously think that data-exhausted is true. Bug #2036 was due to this
      82             : // forgetting.
      83             : //
      84             : // Now to the two categories of optimizations we currently have:
      85             : // - Monotonic bounds optimization that reuse prior iterator position when
      86             : //   doing seek: These only work with !data-exhausted. We could choose to make
      87             : //   these work with data-exhausted but have not bothered because in the
      88             : //   context of a DB if data-exhausted were true, the DB would move to the
      89             : //   next file in the level. Note that this behavior of moving to the next
      90             : //   file is not necessarily true for L0 files, so there could be some benefit
      91             : //   in the future in this optimization. See the WARNING-data-exhausted
      92             : //   comments if trying to optimize this in the future.
      93             : // - TrySeekUsingNext optimizations: these work regardless of exhaustion
      94             : //   state.
      95             : //
      96             : // Implementation detail: In the code PLDE only checks that
      97             : // i.data.isDataInvalidated(). This narrower check is safe, since this is a
      98             : // subset of the set expressed by the OR expression. Also, it is not a
      99             : // de-optimization since whenever we exhaust the iterator we explicitly call
     100             : // i.data.invalidate(). PGDE checks i.index.isDataInvalidated() &&
     101             : // i.data.isDataInvalidated(). Again, this narrower check is safe, and not a
     102             : // de-optimization since whenever we exhaust the iterator we explicitly call
     103             : // i.index.invalidate() and i.data.invalidate(). The && is questionable -- for
     104             : // now this is a bit of defensive code. We should seriously consider removing
     105             : // it, since defensive code suggests we are not confident about our invariants
     106             : // (and if we are not confident, we need more invariant assertions, not
     107             : // defensive code).
     108             : //
     109             : // TODO(sumeer): remove the aforementioned defensive code.
     110             : 
     111             : var singleLevelIterPool = sync.Pool{
     112           1 :         New: func() interface{} {
     113           1 :                 i := &singleLevelIterator{}
     114           1 :                 // Note: this is a no-op if invariants are disabled or race is enabled.
     115           1 :                 invariants.SetFinalizer(i, checkSingleLevelIterator)
     116           1 :                 return i
     117           1 :         },
     118             : }
     119             : 
     120             : var twoLevelIterPool = sync.Pool{
     121           1 :         New: func() interface{} {
     122           1 :                 i := &twoLevelIterator{}
     123           1 :                 // Note: this is a no-op if invariants are disabled or race is enabled.
     124           1 :                 invariants.SetFinalizer(i, checkTwoLevelIterator)
     125           1 :                 return i
     126           1 :         },
     127             : }
     128             : 
     129             : // TODO(jackson): rangedel fragmentBlockIters can't be pooled because of some
     130             : // code paths that double Close the iters. Fix the double close and pool the
     131             : // *fragmentBlockIter type directly.
     132             : 
     133             : var rangeKeyFragmentBlockIterPool = sync.Pool{
     134           1 :         New: func() interface{} {
     135           1 :                 i := &rangeKeyFragmentBlockIter{}
     136           1 :                 // Note: this is a no-op if invariants are disabled or race is enabled.
     137           1 :                 invariants.SetFinalizer(i, checkRangeKeyFragmentBlockIterator)
     138           1 :                 return i
     139           1 :         },
     140             : }
     141             : 
     142           1 : func checkSingleLevelIterator(obj interface{}) {
     143           1 :         i := obj.(*singleLevelIterator)
     144           1 :         if p := i.data.handle.Get(); p != nil {
     145           0 :                 fmt.Fprintf(os.Stderr, "singleLevelIterator.data.handle is not nil: %p\n", p)
     146           0 :                 os.Exit(1)
     147           0 :         }
     148           1 :         if p := i.index.handle.Get(); p != nil {
     149           0 :                 fmt.Fprintf(os.Stderr, "singleLevelIterator.index.handle is not nil: %p\n", p)
     150           0 :                 os.Exit(1)
     151           0 :         }
     152             : }
     153             : 
     154           1 : func checkTwoLevelIterator(obj interface{}) {
     155           1 :         i := obj.(*twoLevelIterator)
     156           1 :         if p := i.data.handle.Get(); p != nil {
     157           0 :                 fmt.Fprintf(os.Stderr, "singleLevelIterator.data.handle is not nil: %p\n", p)
     158           0 :                 os.Exit(1)
     159           0 :         }
     160           1 :         if p := i.index.handle.Get(); p != nil {
     161           0 :                 fmt.Fprintf(os.Stderr, "singleLevelIterator.index.handle is not nil: %p\n", p)
     162           0 :                 os.Exit(1)
     163           0 :         }
     164             : }
     165             : 
     166           1 : func checkRangeKeyFragmentBlockIterator(obj interface{}) {
     167           1 :         i := obj.(*rangeKeyFragmentBlockIter)
     168           1 :         if p := i.blockIter.handle.Get(); p != nil {
     169           0 :                 fmt.Fprintf(os.Stderr, "fragmentBlockIter.blockIter.handle is not nil: %p\n", p)
     170           0 :                 os.Exit(1)
     171           0 :         }
     172             : }
     173             : 
     174             : // compactionIterator is similar to Iterator but it increments the number of
     175             : // bytes that have been iterated through.
     176             : type compactionIterator struct {
     177             :         *singleLevelIterator
     178             : }
     179             : 
     180             : // compactionIterator implements the base.InternalIterator interface.
     181             : var _ base.InternalIterator = (*compactionIterator)(nil)
     182             : 
     183           0 : func (i *compactionIterator) String() string {
     184           0 :         if i.vState != nil {
     185           0 :                 return i.vState.fileNum.String()
     186           0 :         }
     187           0 :         return i.reader.fileNum.String()
     188             : }
     189             : 
     190           0 : func (i *compactionIterator) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKV {
     191           0 :         panic("pebble: SeekGE unimplemented")
     192             : }
     193             : 
     194             : func (i *compactionIterator) SeekPrefixGE(
     195             :         prefix, key []byte, flags base.SeekGEFlags,
     196           0 : ) *base.InternalKV {
     197           0 :         panic("pebble: SeekPrefixGE unimplemented")
     198             : }
     199             : 
     200           0 : func (i *compactionIterator) SeekLT(key []byte, flags base.SeekLTFlags) *base.InternalKV {
     201           0 :         panic("pebble: SeekLT unimplemented")
     202             : }
     203             : 
     204           1 : func (i *compactionIterator) First() *base.InternalKV {
     205           1 :         i.err = nil // clear cached iteration error
     206           1 :         return i.skipForward(i.singleLevelIterator.First())
     207           1 : }
     208             : 
     209           0 : func (i *compactionIterator) Last() *base.InternalKV {
     210           0 :         panic("pebble: Last unimplemented")
     211             : }
     212             : 
     213             : // Note: compactionIterator.Next mirrors the implementation of Iterator.Next
     214             : // due to performance. Keep the two in sync.
     215           1 : func (i *compactionIterator) Next() *base.InternalKV {
     216           1 :         if i.err != nil {
     217           0 :                 return nil
     218           0 :         }
     219           1 :         return i.skipForward(i.data.Next())
     220             : }
     221             : 
     222           0 : func (i *compactionIterator) NextPrefix(succKey []byte) *base.InternalKV {
     223           0 :         panic("pebble: NextPrefix unimplemented")
     224             : }
     225             : 
     226           0 : func (i *compactionIterator) Prev() *base.InternalKV {
     227           0 :         panic("pebble: Prev unimplemented")
     228             : }
     229             : 
     230           1 : func (i *compactionIterator) skipForward(kv *base.InternalKV) *base.InternalKV {
     231           1 :         if kv == nil {
     232           1 :                 for {
     233           1 :                         if kv := i.index.Next(); kv == nil {
     234           1 :                                 break
     235             :                         }
     236           1 :                         result := i.loadBlock(+1)
     237           1 :                         if result != loadBlockOK {
     238           0 :                                 if i.err != nil {
     239           0 :                                         break
     240             :                                 }
     241           0 :                                 switch result {
     242           0 :                                 case loadBlockFailed:
     243           0 :                                         // We checked that i.index was at a valid entry, so
     244           0 :                                         // loadBlockFailed could not have happened due to to i.index
     245           0 :                                         // being exhausted, and must be due to an error.
     246           0 :                                         panic("loadBlock should not have failed with no error")
     247           0 :                                 case loadBlockIrrelevant:
     248           0 :                                         panic("compactionIter should not be using block intervals for skipping")
     249           0 :                                 default:
     250           0 :                                         panic(fmt.Sprintf("unexpected case %d", result))
     251             :                                 }
     252             :                         }
     253             :                         // result == loadBlockOK
     254           1 :                         if kv = i.data.First(); kv != nil {
     255           1 :                                 break
     256             :                         }
     257             :                 }
     258             :         }
     259             : 
     260             :         // We have an upper bound when the table is virtual.
     261           1 :         if i.upper != nil && kv != nil {
     262           1 :                 cmp := i.cmp(kv.K.UserKey, i.upper)
     263           1 :                 if cmp > 0 || (!i.endKeyInclusive && cmp == 0) {
     264           1 :                         return nil
     265           1 :                 }
     266             :         }
     267             : 
     268           1 :         return kv
     269             : }