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 : "github.com/cockroachdb/pebble/sstable/block"
15 : "github.com/cockroachdb/pebble/sstable/colblk"
16 : "github.com/cockroachdb/pebble/sstable/rowblk"
17 : )
18 :
19 : // dataBlockIterator extends the block.IndexBlockIterator interface with a
20 : // constraint that the implementing type be a pointer to a type I.
21 : //
22 : // DataBlockIterator requires that the type be a pointer to its type parameter,
23 : // D, to allow sstable iterators embed the block iterator within its struct. See
24 : // this example from the Go generics proposal:
25 : // https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#pointer-method-example
26 : type dataBlockIterator[D any] interface {
27 : block.DataBlockIterator
28 :
29 : *D // non-interface type constraint element
30 : }
31 :
32 : // indexBlockIterator extends the block.IndexBlockIterator interface with a
33 : // constraint that the implementing type be a pointer to a type I.
34 : //
35 : // indexBlockIterator requires that the type be a pointer to its type parameter,
36 : // I, to allow sstable iterators embed the block iterator within its struct. See
37 : // this example from the Go generics proposal:
38 : // https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#pointer-method-example
39 : type indexBlockIterator[I any] interface {
40 : block.IndexBlockIterator
41 :
42 : *I // non-interface type constraint element
43 : }
44 :
45 : // Iterator iterates over an entire table of data.
46 : type Iterator interface {
47 : base.InternalIterator
48 :
49 : // NextPrefix implements (base.InternalIterator).NextPrefix.
50 : NextPrefix(succKey []byte) *base.InternalKV
51 :
52 : SetCloseHook(fn func(i Iterator) error)
53 : }
54 :
55 : // Iterator positioning optimizations and singleLevelIterator and
56 : // twoLevelIterator:
57 : //
58 : // An iterator is absolute positioned using one of the Seek or First or Last
59 : // calls. After absolute positioning, there can be relative positioning done
60 : // by stepping using Prev or Next.
61 : //
62 : // We implement optimizations below where an absolute positioning call can in
63 : // some cases use the current position to do less work. To understand these,
64 : // we first define some terms. An iterator is bounds-exhausted if the bounds
65 : // (upper of lower) have been reached. An iterator is data-exhausted if it has
66 : // the reached the end of the data (forward or reverse) in the sstable. A
67 : // singleLevelIterator only knows a local-data-exhausted property since when
68 : // it is used as part of a twoLevelIterator, the twoLevelIterator can step to
69 : // the next lower-level index block.
70 : //
71 : // The bounds-exhausted property is tracked by
72 : // singleLevelIterator.exhaustedBounds being +1 (upper bound reached) or -1
73 : // (lower bound reached). The same field is reused by twoLevelIterator. Either
74 : // may notice the exhaustion of the bound and set it. Note that if
75 : // singleLevelIterator sets this property, it is not a local property (since
76 : // the bound has been reached regardless of whether this is in the context of
77 : // the twoLevelIterator or not).
78 : //
79 : // The data-exhausted property is tracked in a more subtle manner. We define
80 : // two predicates:
81 : // - partial-local-data-exhausted (PLDE):
82 : // i.data.IsDataInvalidated() || !i.data.Valid()
83 : // - partial-global-data-exhausted (PGDE):
84 : // i.index.IsDataInvalidated() || !i.index.Valid() || i.data.IsDataInvalidated() ||
85 : // !i.data.Valid()
86 : //
87 : // PLDE is defined for a singleLevelIterator. PGDE is defined for a
88 : // twoLevelIterator. Oddly, in our code below the singleLevelIterator does not
89 : // know when it is part of a twoLevelIterator so it does not know when its
90 : // property is local or global.
91 : //
92 : // Now to define data-exhausted:
93 : // - Prerequisite: we must know that the iterator has been positioned and
94 : // i.err is nil.
95 : // - bounds-exhausted must not be true:
96 : // If bounds-exhausted is true, we have incomplete knowledge of
97 : // data-exhausted since PLDE or PGDE could be true because we could have
98 : // chosen not to load index block or data block and figured out that the
99 : // bound is exhausted (due to block property filters filtering out index and
100 : // data blocks and going past the bound on the top level index block). Note
101 : // that if we tried to separate out the BPF case from others we could
102 : // develop more knowledge here.
103 : // - PGDE is true for twoLevelIterator. PLDE is true if it is a standalone
104 : // singleLevelIterator. !PLDE or !PGDE of course imply that data-exhausted
105 : // is not true.
106 : //
107 : // An implication of the above is that if we are going to somehow utilize
108 : // knowledge of data-exhausted in an optimization, we must not forget the
109 : // existing value of bounds-exhausted since by forgetting the latter we can
110 : // erroneously think that data-exhausted is true. Bug #2036 was due to this
111 : // forgetting.
112 : //
113 : // Now to the two categories of optimizations we currently have:
114 : // - Monotonic bounds optimization that reuse prior iterator position when
115 : // doing seek: These only work with !data-exhausted. We could choose to make
116 : // these work with data-exhausted but have not bothered because in the
117 : // context of a DB if data-exhausted were true, the DB would move to the
118 : // next file in the level. Note that this behavior of moving to the next
119 : // file is not necessarily true for L0 files, so there could be some benefit
120 : // in the future in this optimization. See the WARNING-data-exhausted
121 : // comments if trying to optimize this in the future.
122 : // - TrySeekUsingNext optimizations: these work regardless of exhaustion
123 : // state.
124 : //
125 : // Implementation detail: In the code PLDE only checks that
126 : // i.data.IsDataInvalidated(). This narrower check is safe, since this is a
127 : // subset of the set expressed by the OR expression. Also, it is not a
128 : // de-optimization since whenever we exhaust the iterator we explicitly call
129 : // i.data.Invalidate(). PGDE checks i.index.IsDataInvalidated() &&
130 : // i.data.IsDataInvalidated(). Again, this narrower check is safe, and not a
131 : // de-optimization since whenever we exhaust the iterator we explicitly call
132 : // i.index.Invalidate() and i.data.Invalidate(). The && is questionable -- for
133 : // now this is a bit of defensive code. We should seriously consider removing
134 : // it, since defensive code suggests we are not confident about our invariants
135 : // (and if we are not confident, we need more invariant assertions, not
136 : // defensive code).
137 : //
138 : // TODO(sumeer): remove the aforementioned defensive code.
139 :
140 : type (
141 : singleLevelIteratorRowBlocks = singleLevelIterator[rowblk.IndexIter, *rowblk.IndexIter, rowblk.Iter, *rowblk.Iter]
142 : twoLevelIteratorRowBlocks = twoLevelIterator[rowblk.IndexIter, *rowblk.IndexIter, rowblk.Iter, *rowblk.Iter]
143 : singleLevelIteratorColumnBlocks = singleLevelIterator[colblk.IndexIter, *colblk.IndexIter, colblk.DataBlockIter, *colblk.DataBlockIter]
144 : twoLevelIteratorColumnBlocks = twoLevelIterator[colblk.IndexIter, *colblk.IndexIter, colblk.DataBlockIter, *colblk.DataBlockIter]
145 : )
146 :
147 : var (
148 : singleLevelIterRowBlockPool sync.Pool // *singleLevelIteratorRowBlocks
149 : twoLevelIterRowBlockPool sync.Pool // *twoLevelIteratorRowBlocks
150 : singleLevelIterColumnBlockPool sync.Pool // *singleLevelIteratorColumnBlocks
151 : twoLevelIterColumnBlockPool sync.Pool // *singleLevelIteratorColumnBlocks
152 : )
153 :
154 1 : func init() {
155 1 : singleLevelIterRowBlockPool = sync.Pool{
156 1 : New: func() interface{} {
157 1 : i := &singleLevelIteratorRowBlocks{pool: &singleLevelIterRowBlockPool}
158 1 : // Note: this is a no-op if invariants are disabled or race is enabled.
159 1 : invariants.SetFinalizer(i, checkSingleLevelIterator[rowblk.IndexIter, *rowblk.IndexIter, rowblk.Iter, *rowblk.Iter])
160 1 : return i
161 1 : },
162 : }
163 1 : twoLevelIterRowBlockPool = sync.Pool{
164 1 : New: func() interface{} {
165 1 : i := &twoLevelIteratorRowBlocks{pool: &twoLevelIterRowBlockPool}
166 1 : // Note: this is a no-op if invariants are disabled or race is enabled.
167 1 : invariants.SetFinalizer(i, checkTwoLevelIterator[rowblk.IndexIter, *rowblk.IndexIter, rowblk.Iter, *rowblk.Iter])
168 1 : return i
169 1 : },
170 : }
171 1 : singleLevelIterColumnBlockPool = sync.Pool{
172 1 : New: func() interface{} {
173 1 : i := &singleLevelIteratorColumnBlocks{
174 1 : pool: &singleLevelIterColumnBlockPool,
175 1 : }
176 1 : // Note: this is a no-op if invariants are disabled or race is enabled.
177 1 : invariants.SetFinalizer(i, checkSingleLevelIterator[colblk.IndexIter, *colblk.IndexIter, colblk.DataBlockIter, *colblk.DataBlockIter])
178 1 : return i
179 1 : },
180 : }
181 1 : twoLevelIterColumnBlockPool = sync.Pool{
182 1 : New: func() interface{} {
183 1 : i := &twoLevelIteratorColumnBlocks{
184 1 : pool: &twoLevelIterColumnBlockPool,
185 1 : }
186 1 : // Note: this is a no-op if invariants are disabled or race is enabled.
187 1 : invariants.SetFinalizer(i, checkTwoLevelIterator[colblk.IndexIter, *colblk.IndexIter, colblk.DataBlockIter, *colblk.DataBlockIter])
188 1 : return i
189 1 : },
190 : }
191 : }
192 :
193 : func checkSingleLevelIterator[I any, PI indexBlockIterator[I], D any, PD dataBlockIterator[D]](
194 : obj interface{},
195 1 : ) {
196 1 : i := obj.(*singleLevelIterator[I, PI, D, PD])
197 1 : if h := PD(&i.data).Handle(); h.Valid() {
198 0 : fmt.Fprintf(os.Stderr, "singleLevelIterator.data.handle is not nil: %#v\n", h)
199 0 : os.Exit(1)
200 0 : }
201 1 : if h := PI(&i.index).Handle(); h.Valid() {
202 0 : fmt.Fprintf(os.Stderr, "singleLevelIterator.index.handle is not nil: %#v\n", h)
203 0 : os.Exit(1)
204 0 : }
205 : }
206 :
207 : func checkTwoLevelIterator[I any, PI indexBlockIterator[I], D any, PD dataBlockIterator[D]](
208 : obj interface{},
209 1 : ) {
210 1 : i := obj.(*twoLevelIterator[I, PI, D, PD])
211 1 : if h := PD(&i.secondLevel.data).Handle(); h.Valid() {
212 0 : fmt.Fprintf(os.Stderr, "singleLevelIterator.data.handle is not nil: %#v\n", h)
213 0 : os.Exit(1)
214 0 : }
215 1 : if h := PI(&i.secondLevel.index).Handle(); h.Valid() {
216 0 : fmt.Fprintf(os.Stderr, "singleLevelIterator.index.handle is not nil: %#v\n", h)
217 0 : os.Exit(1)
218 0 : }
219 : }
|
