storage: optimize range key iteration #83049

erikgrinaker · 2022-06-18T09:50:31Z

We need to benchmark and optimize iteration across range keys. Related issues:

There is also likely significant optimization opportunities in Pebble itself, as well as additional opportunities in CRDB. Benchmarks and profiles will tell.

Jira issue: CRDB-16820

The text was updated successfully, but these errors were encountered:

blathers-crl · 2022-06-18T09:50:34Z

cc @cockroachdb/replication

jbowens · 2022-06-22T19:14:31Z

Linking to #82559.

jbowens · 2022-06-29T18:16:34Z

Wrote up a comment about how separating MVCC garbage physically might be useful for optimizing MVCC range deletes, especially considering they're currently non-transactional which avoids some of the other obstacles present to more general MVCC garbage separation: cockroachdb/pebble#1170 (comment)

86093: storage: optimize `pointSynthesizingIter` for `MVCCGet` r=nicktrav a=erikgrinaker **storage: fix slice extention in `MVCCRangeKeyStack.CloneInto`** This patch makes `MVCCRangeKeyStack.CloneInto` extend the existing slice to its full capacity before growing it. Previously, this could build a slice that was too small and panic. Release note: None **storage: add `MVCCIterator.IsPrefix()`** This method allows detecting whether an iterator is a prefix iterator, which comes in handy for wrapping iterators to apply optimizations. Resolves #86104. Release note: None **storage: reuse `pointSynthesizingIter` range key slice** ``` name old time/op new time/op delta MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 3.70µs ± 1% 3.67µs ± 1% -0.89% (p=0.002 n=10+10) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 7.37µs ± 0% 7.25µs ± 0% -1.70% (p=0.000 n=9+10) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=10-24 14.7µs ± 1% 14.4µs ± 1% -2.21% (p=0.000 n=10+10) ``` Touches #83049. Release note: None **storage: add prefix mode for `pointSynthesizingIter`** This patch adds a `prefix` mode for `pointSynthesizingIter`, detected from the parent's `IsPrefix()` method. When enabled, this allows omitting key cloning and comparisons. This replaces the previous `emitOnSeekGE` parameter. ``` name old time/op new time/op delta MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 3.67µs ± 1% 3.67µs ± 1% ~ (p=0.517 n=10+10) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 7.25µs ± 0% 7.07µs ± 0% -2.45% (p=0.000 n=10+9) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=10-24 14.4µs ± 1% 14.2µs ± 1% -1.10% (p=0.000 n=10+10) ``` Touches #83049. Release note: None Co-authored-by: Erik Grinaker <[email protected]>

86109: storage: optimize `pointSynthesizingIter` for `MVCCScan` r=nicktrav a=erikgrinaker **storage: improve `pebbleMVCCScanner` range key assertions** Release note: None **storage: use `RangeKeyChanged()` in `pointSynthesizingIter`** This patch uses `RangeKeyChanged()` to detect changes to range keys in `pointSynthesizingIter`, avoiding repeated key decoding and comparisons in the hot path. ``` name old time/op new time/op delta MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 5.89µs ± 1% 5.94µs ± 0% +0.74% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 12.9µs ± 0% 13.0µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 41.9µs ± 1% 43.0µs ± 1% +2.62% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 75.7µs ± 1% 71.9µs ± 1% -4.90% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 2.97ms ± 1% 2.97ms ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 5.62ms ± 1% 5.13ms ± 0% -8.88% (p=0.008 n=5+5) ``` Touches #83049. Release note: None **storage: memoize parent state in `pointSynthesizingIter`** This patch memoizes the parent iterator state in `pointSynthesizingIter` every time its position changes, which omits a number of redundant function calls and key comparisons. ``` name old time/op new time/op delta MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 5.66µs ± 1% 5.57µs ± 1% -1.61% (p=0.000 n=10+10) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 12.3µs ± 1% 11.9µs ± 1% -3.33% (p=0.000 n=10+10) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 38.7µs ± 2% 38.8µs ± 1% ~ (p=0.448 n=9+9) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 67.0µs ± 1% 60.0µs ± 1% -10.45% (p=0.000 n=10+10) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 2.81ms ± 1% 2.83ms ± 1% +0.73% (p=0.002 n=10+10) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 4.99ms ± 1% 4.29ms ± 1% -14.03% (p=0.000 n=10+9) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 3.33µs ± 2% 3.33µs ± 3% ~ (p=0.382 n=10+10) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 6.71µs ± 2% 6.59µs ± 1% -1.90% (p=0.000 n=10+10) ``` Touches #83049. Release note: None **storage: omit `pointSynthesizingIter` start key comparison** This patch adds a field `rangeKeyStartPassed` which is set to `true` when the iterator moves past the start key of a range key in the forward direction. This allows omitting a key comparison for subsequent point keys until encountering a new range key. ``` name old time/op new time/op delta MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 5.57µs ± 1% 5.58µs ± 2% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 11.8µs ± 1% 11.9µs ± 0% +0.71% (p=0.016 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 164µs ± 1% 163µs ± 1% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 38.9µs ± 1% 38.8µs ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 61.7µs ± 1% 59.5µs ± 0% -3.65% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 170µs ± 1% 165µs ± 1% -3.07% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 2.89ms ± 1% 2.82ms ± 0% -2.29% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 4.37ms ± 0% 4.28ms ± 0% -1.90% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 5.38ms ± 1% 5.40ms ± 1% ~ (p=0.690 n=5+5) ``` Touches #83049. Release note: None **storage: clean up `pointSynthesizingIter`** This patch makes some minor cleanups of `pointSynthesizingIter`. There are no visible behavioral changes. Release note: None Co-authored-by: Erik Grinaker <[email protected]>

erikgrinaker · 2022-08-15T14:27:14Z

Ran some benchmarks comparing no range tombstones to 1 or 100 range tombstones -- these are always written below the data, except for MVCCScanGarbage where they are written above the data.

numRangeKeys=0,1
name                                                            old time/op    new time/op    delta
MVCCScan_Pebble/rows=1/versions=1/valueSize=64-24               5.77µs ± 6%   12.53µs ± 7%  +117.34%  (p=0.000 n=9+10)
MVCCScan_Pebble/rows=100/versions=1/valueSize=64-24             39.5µs ± 2%    61.3µs ± 2%   +55.02%  (p=0.000 n=10+10)
MVCCScan_Pebble/rows=10000/versions=1/valueSize=64-24           2.76ms ± 2%    4.30ms ± 1%   +55.64%  (p=0.000 n=10+9)
MVCCScanGarbage_Pebble/rows=1/versions=2-24                     4.77µs ± 2%   10.15µs ± 1%  +112.55%  (p=0.000 n=10+9)
MVCCScanGarbage_Pebble/rows=100/versions=2-24                   31.2µs ± 1%    24.6µs ± 1%   -21.20%  (p=0.000 n=10+10)
MVCCScanGarbage_Pebble/rows=10000/versions=2-24                 2.48ms ± 1%    0.16ms ± 1%   -93.50%  (p=0.000 n=10+10)
MVCCReverseScan_Pebble/rows=1/versions=1/valueSize=64-24        5.89µs ± 1%   11.95µs ± 1%  +102.90%  (p=0.000 n=10+10)
MVCCReverseScan_Pebble/rows=100/versions=1/valueSize=64-24      50.7µs ± 1%    74.2µs ± 2%   +46.38%  (p=0.000 n=10+10)
MVCCReverseScan_Pebble/rows=10000/versions=1/valueSize=64-24    3.98ms ± 1%    5.50ms ± 1%   +38.23%  (p=0.000 n=10+10)
MVCCGet_Pebble/batch=true/versions=1/valueSize=8-24             2.53µs ± 2%    3.18µs ± 1%   +25.49%  (p=0.000 n=10+10)
MVCCComputeStats_Pebble/valueSize=32-24                          155ms ± 1%     189ms ± 0%   +22.10%  (p=0.000 n=8+9)

numRangeKeys=0,100
name                                                            old time/op    new time/op    delta
MVCCScan_Pebble/rows=1/versions=1/valueSize=64-24               5.77µs ± 6%  165.07µs ± 2%  +2762.49%  (p=0.000 n=9+10)
MVCCScan_Pebble/rows=100/versions=1/valueSize=64-24             39.5µs ± 2%   166.7µs ± 1%   +321.64%  (p=0.000 n=10+10)
MVCCScan_Pebble/rows=10000/versions=1/valueSize=64-24           2.76ms ± 2%    5.42ms ± 1%    +96.39%  (p=0.000 n=10+9)
MVCCScanGarbage_Pebble/rows=1/versions=2-24                     4.77µs ± 2%  172.98µs ± 1%  +3522.96%  (p=0.000 n=10+8)
MVCCScanGarbage_Pebble/rows=100/versions=2-24                   31.2µs ± 1%   273.8µs ± 3%   +778.57%  (p=0.000 n=10+10)
MVCCScanGarbage_Pebble/rows=10000/versions=2-24                 2.48ms ± 1%   10.81ms ± 5%   +336.46%  (p=0.000 n=10+10)
MVCCReverseScan_Pebble/rows=1/versions=1/valueSize=64-24        5.89µs ± 1%   91.20µs ± 1%  +1448.93%  (p=0.000 n=10+10)
MVCCReverseScan_Pebble/rows=100/versions=1/valueSize=64-24      50.7µs ± 1%   174.0µs ± 2%   +243.12%  (p=0.000 n=10+9)
MVCCReverseScan_Pebble/rows=10000/versions=1/valueSize=64-24    3.98ms ± 1%    6.59ms ± 1%    +65.51%  (p=0.000 n=10+10)
MVCCGet_Pebble/batch=true/versions=1/valueSize=8-24             2.53µs ± 2%   76.56µs ± 1%  +2925.91%  (p=0.000 n=10+9)
MVCCComputeStats_Pebble/valueSize=32-24                          155ms ± 1%     209ms ± 1%    +34.74%  (p=0.000 n=8+9)

So we're taking a pretty significant hit once range keys are present. The one highlight is the garbage scan, which shows that scanning across garbage covered by a range tombstone is almost 2 orders of magnitude faster than scanning across the point garbage.

It would be useful to compare this with versions that write point key garbage below the point keys, so we can see the comparative cost of point garbage and range garbage.

I'll also note that in end-to-end benchmarks, such as YCSB, we're approaching the baseline performance when a single range key is present.

Update pebbleIterator to use the new NextPrefix method exposed by Pebble Iterators (cockroachdb/pebble#1860). NextPrefix implements semanatics analgous to MVCCIterator.NextKey and is able to make use of low-level optimizations to avoid much of the work of a full seek. Additionally in the case where the very next key is a new MVCC user key, the pebbleMVCCScanner is able to use NextPrefix to avoid a key copy and a key comparison. Epic: None Informs cockroachdb#83049. Release note: None

Alter the semantics of SeekGE and SeekLT on FragmentIterator. Previously, FragmentIterator's seek operations were defined only in terms of span start keys. This commit changes the seek operations to be defined in terms of the keys contained by the span. A SeekGE now seeks to the first span containing a key ≥ the seek key, and a SeekLT now seeks to the last span containing a key < seek key. These new semantics match the typical top-level iterator use. With these new semantics, SeekLT can still be implemented in terms of a simple span start key seek. Seeking to the last span containing a key < seek key is equivalent to seeking to the last span with a start key less the given key. However, SeekGE implementations now require an extra key comparison and sometimes a Next. Since top-level iterator requires the containment semantics anyways, this key comparison and Next is only being moved down the stack into the interface implementation. When using the keyspan merging iterator, the keyspan.MergingIter's SeekGE implementation performs a SeekLT per-level, which suffers no additional overhead. With the MergingIter and DefragmentingIter implementations, these new semantics reduce the amount of work performed during a seek. The previous iterator stack's SeekGE looked like (left-to-right, top-down): InterleavingIter.SeekGE │ ╭────────────────┴───────────────╮ │ │ DefragmentingIter.SeekLT DefragmentingIter.Next() │ │ ╭───────────┴───╮ │ │ │ │ MergingIter.SeekLT ├── defragmentFwd ├── defragmentFwd │ │ │ │ ╰── defragmentBwd ╰── defragmentFwd ╰───────────╮ │ ╭───────────┴───────────╮ │ │ MergingIter.SeekGE MergingIter.Prev │ ╰─╶╶ per level╶╶ ─╮ │ ╭───────────┴───────────╮ │ │ <?>.SeekLT <?>.Next The new iterator stack's SeekGE, assuming it doesn't hit the new defragmenting fast path, looks like: InterleavingIter.SeekGE │ DefragmentingIter.SeekGE │ ╭────────────────┴───────────────╮ │ ├── defragmentBwd* MergingIter.SeekGE │ │ ╰── defragmentFwd ╰─╶╶ per level╶╶ ─╮ │ │ ├── <?>.SeekLT │ ╰── <?>.Next * — The call to defragmentBackward during SeekGE may now sometimes be elided, specifically if the span discovered by MergingIter.SeekGE does not contain the seek key within its bounds. Note that in this interface, there are no calls to any of the leaf FragmentIterator's SeekGE methods which would suffer the extra key comparison and Next. Instead, the MergingIter calls SeekLT and unconditionally Nexts each of the leafs as a part of its logic to fragment bounds across levels. This reduced work for seeks has a large impact on the MVCCGet and MVCCScan microbenchmarks in the presence of range keys. ``` name old time/op new time/op delta MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=0-24 6.30µs ± 1% 6.22µs ± 2% ~ (p=0.095 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=1-24 11.5µs ± 1% 10.3µs ± 1% -9.95% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=100-24 118µs ± 1% 79µs ± 2% -33.14% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=0-24 23.9µs ± 1% 24.1µs ± 2% ~ (p=0.310 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=1-24 31.7µs ± 2% 29.6µs ± 1% -6.65% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=100-24 109µs ± 1% 69µs ± 2% -36.58% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=0-24 100µs ± 1% 99µs ± 3% ~ (p=0.310 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=1-24 110µs ± 1% 106µs ± 2% -3.24% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=100-24 197µs ± 2% 153µs ± 1% -22.75% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 3.74µs ± 1% 3.57µs ± 1% -4.47% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 6.01µs ± 1% 4.93µs ± 2% -17.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=100-24 66.1µs ± 1% 28.8µs ± 1% -56.35% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=0-24 20.4µs ± 1% 20.4µs ± 1% ~ (p=0.690 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=1-24 25.9µs ± 1% 23.9µs ± 3% -7.79% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=100-24 89.3µs ± 1% 50.2µs ± 2% -43.76% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=0-24 98.7µs ± 1% 97.9µs ± 1% ~ (p=0.151 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=1-24 106µs ± 1% 103µs ± 1% -2.63% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=100-24 179µs ± 3% 131µs ± 2% -26.75% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 10.9µs ± 3% 10.7µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 17.9µs ± 1% 16.1µs ± 2% -10.35% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 172µs ± 1% 94µs ± 2% -45.23% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 13.0µs ± 1% 13.1µs ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 21.1µs ± 1% 19.0µs ± 2% -9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 158µs ± 1% 83µs ± 3% -47.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 20.3µs ± 1% 20.1µs ± 2% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 30.6µs ± 2% 27.6µs ± 1% -9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 160µs ± 2% 88µs ± 3% -45.10% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 41.5µs ± 1% 41.1µs ± 1% -0.97% (p=0.048 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 50.9µs ± 1% 48.6µs ± 2% -4.67% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 140µs ± 2% 94µs ± 1% -32.43% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 15.6µs ± 2% 16.1µs ± 1% +3.21% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 24.0µs ± 1% 23.1µs ± 2% -3.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 117µs ± 1% 78µs ± 2% -33.17% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 20.1µs ± 1% 20.4µs ± 1% +1.30% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 30.1µs ± 1% 28.5µs ± 1% -5.25% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 109µs ± 2% 70µs ± 1% -36.07% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 37.7µs ± 2% 38.1µs ± 1% ~ (p=0.056 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 55.5µs ± 2% 53.9µs ± 1% -2.79% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 140µs ± 2% 101µs ± 1% -27.99% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 97.5µs ± 3% 96.1µs ± 2% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 117µs ± 4% 115µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 216µs ± 1% 176µs ± 4% -18.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 50.9µs ± 1% 53.2µs ± 2% +4.37% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 75.3µs ± 2% 74.8µs ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 184µs ± 3% 141µs ± 1% -23.61% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 68.5µs ± 2% 70.7µs ± 1% +3.27% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 100µs ± 3% 102µs ± 1% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 192µs ± 1% 149µs ± 2% -22.12% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 172µs ± 0% 176µs ± 1% +2.48% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 266µs ± 2% 271µs ± 2% +1.88% (p=0.032 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 404µs ± 3% 364µs ± 3% -9.69% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 579µs ± 1% 578µs ± 1% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 704µs ± 1% 706µs ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 965µs ± 2% 923µs ± 3% -4.45% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 357µs ± 1% 372µs ± 1% +4.34% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 529µs ± 2% 546µs ± 1% +3.26% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 757µs ± 1% 691µs ± 1% -8.72% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 496µs ± 2% 507µs ± 2% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 758µs ± 1% 778µs ± 1% +2.63% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 968µs ± 2% 904µs ± 1% -6.58% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 1.46ms ± 4% 1.50ms ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 2.36ms ± 2% 2.35ms ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 2.97ms ± 5% 2.91ms ± 2% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 5.12ms ± 3% 5.08ms ± 3% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 6.38ms ± 2% 6.34ms ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 8.11ms ± 3% 7.97ms ± 5% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 3.56ms ± 1% 3.37ms ± 1% -5.61% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 5.32ms ± 1% 5.12ms ± 2% -3.90% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 6.35ms ± 1% 6.25ms ± 1% -1.59% (p=0.016 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 4.91ms ± 2% 4.90ms ± 1% ~ (p=1.000 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 7.41ms ± 1% 7.26ms ± 1% -2.10% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 8.48ms ± 1% 8.42ms ± 1% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 14.3ms ± 3% 14.4ms ± 1% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 22.7ms ± 2% 22.6ms ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 27.7ms ± 3% 28.0ms ± 3% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 51.8ms ± 1% 50.4ms ± 5% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 64.0ms ± 6% 63.0ms ± 4% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 83.4ms ± 7% 84.3ms ± 4% ~ (p=0.841 n=5+5) name old speed new speed delta MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=0-24 1.27MB/s ± 2% 1.28MB/s ± 2% ~ (p=0.119 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=1-24 696kB/s ± 1% 774kB/s ± 1% +11.21% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=100-24 70.0kB/s ± 0% 100.0kB/s ± 0% +42.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=0-24 336kB/s ± 2% 330kB/s ± 0% ~ (p=0.095 n=5+4) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=1-24 250kB/s ± 0% 270kB/s ± 0% +8.00% (p=0.016 n=4+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=100-24 70.0kB/s ± 0% 114.0kB/s ± 5% +62.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=0-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=1-24 70.0kB/s ± 0% 76.0kB/s ± 8% ~ (p=0.167 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=100-24 40.0kB/s ± 0% 50.0kB/s ± 0% +25.00% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 2.14MB/s ± 1% 2.24MB/s ± 1% +4.68% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 1.33MB/s ± 1% 1.62MB/s ± 2% +21.77% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=100-24 120kB/s ± 0% 280kB/s ± 0% +133.33% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=0-24 390kB/s ± 0% 390kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=1-24 310kB/s ± 0% 340kB/s ± 0% +9.68% (p=0.016 n=5+4) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=100-24 90.0kB/s ± 0% 160.0kB/s ± 0% +77.78% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=0-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=1-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=100-24 44.0kB/s ±14% 60.0kB/s ± 0% +36.36% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 5.90MB/s ± 3% 6.00MB/s ± 1% ~ (p=0.119 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 3.57MB/s ± 1% 3.98MB/s ± 2% +11.53% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 370kB/s ± 0% 678kB/s ± 2% +83.24% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 4.91MB/s ± 1% 4.90MB/s ± 2% ~ (p=0.730 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 3.04MB/s ± 1% 3.36MB/s ± 2% +10.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 404kB/s ± 1% 772kB/s ± 3% +91.09% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 3.15MB/s ± 1% 3.19MB/s ± 2% ~ (p=0.167 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 2.09MB/s ± 2% 2.32MB/s ± 1% +10.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 400kB/s ± 0% 730kB/s ± 3% +82.50% (p=0.016 n=4+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 1.54MB/s ± 1% 1.56MB/s ± 1% +1.17% (p=0.048 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 1.26MB/s ± 1% 1.32MB/s ± 2% +4.93% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 460kB/s ± 2% 680kB/s ± 0% +47.83% (p=0.016 n=5+4) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 41.0MB/s ± 2% 39.7MB/s ± 1% -3.13% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 26.6MB/s ± 1% 27.7MB/s ± 2% +4.03% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 5.46MB/s ± 1% 8.17MB/s ± 2% +49.56% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 31.8MB/s ± 1% 31.4MB/s ± 1% -1.28% (p=0.024 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 21.3MB/s ± 1% 22.5MB/s ± 1% +5.52% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 5.85MB/s ± 2% 9.15MB/s ± 1% +56.37% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 17.0MB/s ± 2% 16.8MB/s ± 1% ~ (p=0.056 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 11.5MB/s ± 2% 11.9MB/s ± 1% +2.82% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 4.56MB/s ± 2% 6.33MB/s ± 1% +38.89% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 6.57MB/s ± 3% 6.66MB/s ± 2% ~ (p=0.087 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 5.47MB/s ± 4% 5.58MB/s ± 1% ~ (p=0.135 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 2.97MB/s ± 1% 3.65MB/s ± 4% +22.98% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 126MB/s ± 1% 120MB/s ± 2% -4.18% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 85.0MB/s ± 3% 85.6MB/s ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 34.7MB/s ± 4% 45.4MB/s ± 1% +30.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 93.4MB/s ± 2% 90.5MB/s ± 1% -3.17% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 63.8MB/s ± 3% 62.9MB/s ± 1% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 33.4MB/s ± 1% 42.9MB/s ± 2% +28.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 37.2MB/s ± 0% 36.3MB/s ± 1% -2.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 24.1MB/s ± 2% 23.6MB/s ± 2% -1.84% (p=0.032 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 15.9MB/s ± 3% 17.6MB/s ± 3% +10.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 11.1MB/s ± 1% 11.1MB/s ± 1% ~ (p=0.635 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 9.09MB/s ± 2% 9.07MB/s ± 2% ~ (p=0.643 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 6.63MB/s ± 2% 6.94MB/s ± 3% +4.68% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 179MB/s ± 1% 172MB/s ± 1% -4.16% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 121MB/s ± 2% 117MB/s ± 1% -3.16% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 84.5MB/s ± 1% 92.6MB/s ± 1% +9.56% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 129MB/s ± 2% 126MB/s ± 3% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 84.4MB/s ± 1% 82.3MB/s ± 1% -2.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 66.1MB/s ± 2% 70.8MB/s ± 1% +7.04% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 43.7MB/s ± 4% 42.7MB/s ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 27.2MB/s ± 2% 27.3MB/s ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 21.6MB/s ± 5% 22.0MB/s ± 2% ~ (p=0.135 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 12.5MB/s ± 3% 12.6MB/s ± 3% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 10.0MB/s ± 2% 10.1MB/s ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 7.89MB/s ± 3% 8.04MB/s ± 5% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 180MB/s ± 1% 190MB/s ± 1% +5.94% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 120MB/s ± 1% 125MB/s ± 2% +4.06% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 101MB/s ± 1% 102MB/s ± 1% +1.60% (p=0.016 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 130MB/s ± 2% 131MB/s ± 1% ~ (p=1.000 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 86.3MB/s ± 1% 88.2MB/s ± 1% +2.14% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 75.5MB/s ± 1% 76.0MB/s ± 1% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 44.7MB/s ± 3% 44.4MB/s ± 1% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 28.2MB/s ± 2% 28.3MB/s ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 23.2MB/s ± 3% 22.9MB/s ± 3% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 12.4MB/s ± 1% 12.7MB/s ± 5% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 10.0MB/s ± 5% 10.2MB/s ± 5% ~ (p=0.643 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 7.69MB/s ± 7% 7.60MB/s ± 4% ~ (p=0.841 n=5+5) ``` Close cockroachdb#1829. Informs cockroachdb/cockroach#83049.

Update pebbleIterator to use the new NextPrefix method exposed by Pebble Iterators (cockroachdb/pebble#1860). NextPrefix implements semanatics analgous to MVCCIterator.NextKey and is able to make use of low-level optimizations to avoid much of the work of a full seek. Additionally in the case where the very next key is a new MVCC user key, the pebbleMVCCScanner is able to use NextPrefix to avoid a key copy and a key comparison. ``` name old speed new speed delta MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 6.20MB/s ± 2% 6.24MB/s ± 1% ~ (p=0.524 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 3.71MB/s ± 1% 3.90MB/s ± 1% +5.01% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 376kB/s ± 2% 670kB/s ± 0% +78.19% (p=0.016 n=5+4) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 4.87MB/s ± 0% 5.00MB/s ± 2% +2.71% (p=0.032 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 3.08MB/s ± 1% 3.18MB/s ± 1% +3.38% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 420kB/s ± 0% 758kB/s ± 2% +80.48% (p=0.016 n=4+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 3.21MB/s ± 1% 3.27MB/s ± 2% +1.99% (p=0.024 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 2.11MB/s ± 2% 2.23MB/s ± 2% +5.89% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 410kB/s ± 2% 688kB/s ± 2% +67.80% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 1.55MB/s ± 1% 1.65MB/s ± 2% +6.19% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 1.26MB/s ± 2% 1.33MB/s ± 3% +5.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 460kB/s ± 0% 536kB/s ± 3% +16.52% (p=0.016 n=4+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 41.4MB/s ± 2% 41.2MB/s ± 2% ~ (p=0.516 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 26.5MB/s ± 2% 27.1MB/s ± 1% +2.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 5.37MB/s ± 2% 6.17MB/s ± 1% +14.74% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 32.7MB/s ± 2% 31.5MB/s ± 3% -3.51% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 21.4MB/s ± 0% 21.6MB/s ± 1% +1.18% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 5.88MB/s ± 1% 6.74MB/s ± 0% +14.51% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 17.2MB/s ± 2% 18.5MB/s ± 1% +7.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 11.6MB/s ± 2% 13.2MB/s ± 2% +13.93% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 4.56MB/s ± 1% 5.58MB/s ± 1% +22.36% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 6.79MB/s ± 3% 7.50MB/s ± 2% +10.45% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 5.53MB/s ± 2% 6.31MB/s ± 2% +13.95% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 2.94MB/s ± 1% 3.54MB/s ± 1% +20.27% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 125MB/s ± 1% 124MB/s ± 1% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 84.2MB/s ± 3% 86.1MB/s ± 2% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 33.7MB/s ± 3% 38.0MB/s ± 1% +12.83% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 92.7MB/s ± 1% 94.5MB/s ± 1% +1.90% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 62.5MB/s ± 1% 65.4MB/s ± 1% +4.75% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 32.0MB/s ± 1% 36.4MB/s ± 1% +13.51% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 36.5MB/s ± 3% 41.3MB/s ± 4% +13.05% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 23.7MB/s ± 2% 30.8MB/s ± 2% +29.93% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 15.8MB/s ± 1% 21.3MB/s ± 2% +34.67% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 11.1MB/s ± 1% 12.6MB/s ± 2% +13.08% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 9.06MB/s ± 2% 11.08MB/s ± 2% +22.29% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 6.65MB/s ± 1% 8.91MB/s ± 2% +33.95% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 175MB/s ± 2% 176MB/s ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 120MB/s ± 1% 124MB/s ± 1% +3.59% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 81.3MB/s ± 2% 87.5MB/s ± 1% +7.62% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 122MB/s ± 1% 132MB/s ± 2% +7.88% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 82.5MB/s ± 2% 90.5MB/s ± 2% +9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 65.2MB/s ± 1% 72.0MB/s ± 1% +10.41% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 42.9MB/s ± 1% 50.2MB/s ± 2% +17.02% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 27.3MB/s ± 1% 36.7MB/s ± 1% +34.49% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 21.4MB/s ± 3% 31.4MB/s ± 4% +46.71% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 12.5MB/s ± 3% 14.6MB/s ± 5% +16.55% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 10.3MB/s ± 4% 13.2MB/s ± 2% +28.04% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 8.00MB/s ± 4% 11.47MB/s ± 4% +43.25% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 193MB/s ± 2% 197MB/s ± 1% +2.33% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 130MB/s ± 2% 133MB/s ± 1% +2.05% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 104MB/s ± 2% 108MB/s ± 1% +3.41% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 137MB/s ± 1% 143MB/s ± 2% +4.14% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 89.4MB/s ± 2% 95.8MB/s ± 0% +7.10% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 77.3MB/s ± 2% 82.3MB/s ± 2% +6.47% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 44.9MB/s ± 1% 52.7MB/s ± 3% +17.30% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 28.6MB/s ± 2% 39.0MB/s ± 5% +36.19% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 22.6MB/s ± 7% 34.5MB/s ± 5% +52.68% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 13.2MB/s ± 3% 15.2MB/s ± 4% +15.51% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 10.5MB/s ± 4% 13.4MB/s ± 2% +27.11% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 8.13MB/s ± 6% 11.87MB/s ± 3% +45.98% (p=0.008 n=5+5) ``` Epic: None Informs cockroachdb#83049. Release note: None

Alter the semantics of SeekGE and SeekLT on FragmentIterator. Previously, FragmentIterator's seek operations were defined only in terms of span start keys. This commit changes the seek operations to be defined in terms of the keys contained by the span. A SeekGE now seeks to the first span containing a key ≥ the seek key, and a SeekLT now seeks to the last span containing a key < seek key. These new semantics match the typical top-level iterator use. With these new semantics, SeekLT can still be implemented in terms of a simple span start key seek. Seeking to the last span containing a key < seek key is equivalent to seeking to the last span with a start key less the given key. However, SeekGE implementations now require an extra key comparison and sometimes a Next. Since top-level iterator requires the containment semantics anyways, this key comparison and Next is only being moved down the stack into the interface implementation. When using the keyspan merging iterator, the keyspan.MergingIter's SeekGE implementation performs a SeekLT per-level, which suffers no additional overhead. With the MergingIter and DefragmentingIter implementations, these new semantics reduce the amount of work performed during a seek. The previous iterator stack's SeekGE looked like (left-to-right, top-down): InterleavingIter.SeekGE │ ╭────────────────┴───────────────╮ │ │ DefragmentingIter.SeekLT DefragmentingIter.Next() │ │ ╭───────────┴───╮ │ │ │ │ MergingIter.SeekLT ├── defragmentFwd ├── defragmentFwd │ │ │ │ ╰── defragmentBwd ╰── defragmentFwd ╰───────────╮ │ ╭───────────┴───────────╮ │ │ MergingIter.SeekGE MergingIter.Prev │ ╰─╶╶ per level╶╶ ─╮ │ ╭───────────┴───────────╮ │ │ <?>.SeekLT <?>.Next The new iterator stack's SeekGE, assuming it doesn't hit the new defragmenting fast path, looks like: InterleavingIter.SeekGE │ DefragmentingIter.SeekGE │ ╭────────────────┴───────────────╮ │ ├── defragmentBwd* MergingIter.SeekGE │ │ ╰── defragmentFwd ╰─╶╶ per level╶╶ ─╮ │ │ ├── <?>.SeekLT │ ╰── <?>.Next * — The call to defragmentBackward during SeekGE may now sometimes be elided, specifically if the span discovered by MergingIter.SeekGE does not contain the seek key within its bounds. Note that in this interface, there are no calls to any of the leaf FragmentIterator's SeekGE methods which would suffer the extra key comparison and Next. Instead, the MergingIter calls SeekLT and unconditionally Nexts each of the leafs as a part of its logic to fragment bounds across levels. This reduced work for seeks has a large impact on the MVCCGet and MVCCScan microbenchmarks in the presence of range keys. ``` name old time/op new time/op delta MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=0-24 6.30µs ± 1% 6.22µs ± 2% ~ (p=0.095 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=1-24 11.5µs ± 1% 10.3µs ± 1% -9.95% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=100-24 118µs ± 1% 79µs ± 2% -33.14% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=0-24 23.9µs ± 1% 24.1µs ± 2% ~ (p=0.310 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=1-24 31.7µs ± 2% 29.6µs ± 1% -6.65% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=100-24 109µs ± 1% 69µs ± 2% -36.58% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=0-24 100µs ± 1% 99µs ± 3% ~ (p=0.310 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=1-24 110µs ± 1% 106µs ± 2% -3.24% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=100-24 197µs ± 2% 153µs ± 1% -22.75% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 3.74µs ± 1% 3.57µs ± 1% -4.47% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 6.01µs ± 1% 4.93µs ± 2% -17.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=100-24 66.1µs ± 1% 28.8µs ± 1% -56.35% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=0-24 20.4µs ± 1% 20.4µs ± 1% ~ (p=0.690 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=1-24 25.9µs ± 1% 23.9µs ± 3% -7.79% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=100-24 89.3µs ± 1% 50.2µs ± 2% -43.76% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=0-24 98.7µs ± 1% 97.9µs ± 1% ~ (p=0.151 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=1-24 106µs ± 1% 103µs ± 1% -2.63% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=100-24 179µs ± 3% 131µs ± 2% -26.75% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 10.9µs ± 3% 10.7µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 17.9µs ± 1% 16.1µs ± 2% -10.35% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 172µs ± 1% 94µs ± 2% -45.23% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 13.0µs ± 1% 13.1µs ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 21.1µs ± 1% 19.0µs ± 2% -9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 158µs ± 1% 83µs ± 3% -47.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 20.3µs ± 1% 20.1µs ± 2% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 30.6µs ± 2% 27.6µs ± 1% -9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 160µs ± 2% 88µs ± 3% -45.10% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 41.5µs ± 1% 41.1µs ± 1% -0.97% (p=0.048 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 50.9µs ± 1% 48.6µs ± 2% -4.67% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 140µs ± 2% 94µs ± 1% -32.43% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 15.6µs ± 2% 16.1µs ± 1% +3.21% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 24.0µs ± 1% 23.1µs ± 2% -3.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 117µs ± 1% 78µs ± 2% -33.17% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 20.1µs ± 1% 20.4µs ± 1% +1.30% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 30.1µs ± 1% 28.5µs ± 1% -5.25% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 109µs ± 2% 70µs ± 1% -36.07% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 37.7µs ± 2% 38.1µs ± 1% ~ (p=0.056 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 55.5µs ± 2% 53.9µs ± 1% -2.79% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 140µs ± 2% 101µs ± 1% -27.99% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 97.5µs ± 3% 96.1µs ± 2% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 117µs ± 4% 115µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 216µs ± 1% 176µs ± 4% -18.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 50.9µs ± 1% 53.2µs ± 2% +4.37% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 75.3µs ± 2% 74.8µs ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 184µs ± 3% 141µs ± 1% -23.61% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 68.5µs ± 2% 70.7µs ± 1% +3.27% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 100µs ± 3% 102µs ± 1% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 192µs ± 1% 149µs ± 2% -22.12% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 172µs ± 0% 176µs ± 1% +2.48% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 266µs ± 2% 271µs ± 2% +1.88% (p=0.032 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 404µs ± 3% 364µs ± 3% -9.69% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 579µs ± 1% 578µs ± 1% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 704µs ± 1% 706µs ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 965µs ± 2% 923µs ± 3% -4.45% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 357µs ± 1% 372µs ± 1% +4.34% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 529µs ± 2% 546µs ± 1% +3.26% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 757µs ± 1% 691µs ± 1% -8.72% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 496µs ± 2% 507µs ± 2% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 758µs ± 1% 778µs ± 1% +2.63% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 968µs ± 2% 904µs ± 1% -6.58% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 1.46ms ± 4% 1.50ms ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 2.36ms ± 2% 2.35ms ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 2.97ms ± 5% 2.91ms ± 2% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 5.12ms ± 3% 5.08ms ± 3% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 6.38ms ± 2% 6.34ms ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 8.11ms ± 3% 7.97ms ± 5% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 3.56ms ± 1% 3.37ms ± 1% -5.61% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 5.32ms ± 1% 5.12ms ± 2% -3.90% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 6.35ms ± 1% 6.25ms ± 1% -1.59% (p=0.016 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 4.91ms ± 2% 4.90ms ± 1% ~ (p=1.000 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 7.41ms ± 1% 7.26ms ± 1% -2.10% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 8.48ms ± 1% 8.42ms ± 1% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 14.3ms ± 3% 14.4ms ± 1% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 22.7ms ± 2% 22.6ms ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 27.7ms ± 3% 28.0ms ± 3% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 51.8ms ± 1% 50.4ms ± 5% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 64.0ms ± 6% 63.0ms ± 4% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 83.4ms ± 7% 84.3ms ± 4% ~ (p=0.841 n=5+5) name old speed new speed delta MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=0-24 1.27MB/s ± 2% 1.28MB/s ± 2% ~ (p=0.119 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=1-24 696kB/s ± 1% 774kB/s ± 1% +11.21% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=100-24 70.0kB/s ± 0% 100.0kB/s ± 0% +42.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=0-24 336kB/s ± 2% 330kB/s ± 0% ~ (p=0.095 n=5+4) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=1-24 250kB/s ± 0% 270kB/s ± 0% +8.00% (p=0.016 n=4+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=100-24 70.0kB/s ± 0% 114.0kB/s ± 5% +62.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=0-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=1-24 70.0kB/s ± 0% 76.0kB/s ± 8% ~ (p=0.167 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=100-24 40.0kB/s ± 0% 50.0kB/s ± 0% +25.00% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 2.14MB/s ± 1% 2.24MB/s ± 1% +4.68% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 1.33MB/s ± 1% 1.62MB/s ± 2% +21.77% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=100-24 120kB/s ± 0% 280kB/s ± 0% +133.33% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=0-24 390kB/s ± 0% 390kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=1-24 310kB/s ± 0% 340kB/s ± 0% +9.68% (p=0.016 n=5+4) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=100-24 90.0kB/s ± 0% 160.0kB/s ± 0% +77.78% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=0-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=1-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=100-24 44.0kB/s ±14% 60.0kB/s ± 0% +36.36% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 5.90MB/s ± 3% 6.00MB/s ± 1% ~ (p=0.119 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 3.57MB/s ± 1% 3.98MB/s ± 2% +11.53% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 370kB/s ± 0% 678kB/s ± 2% +83.24% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 4.91MB/s ± 1% 4.90MB/s ± 2% ~ (p=0.730 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 3.04MB/s ± 1% 3.36MB/s ± 2% +10.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 404kB/s ± 1% 772kB/s ± 3% +91.09% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 3.15MB/s ± 1% 3.19MB/s ± 2% ~ (p=0.167 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 2.09MB/s ± 2% 2.32MB/s ± 1% +10.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 400kB/s ± 0% 730kB/s ± 3% +82.50% (p=0.016 n=4+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 1.54MB/s ± 1% 1.56MB/s ± 1% +1.17% (p=0.048 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 1.26MB/s ± 1% 1.32MB/s ± 2% +4.93% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 460kB/s ± 2% 680kB/s ± 0% +47.83% (p=0.016 n=5+4) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 41.0MB/s ± 2% 39.7MB/s ± 1% -3.13% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 26.6MB/s ± 1% 27.7MB/s ± 2% +4.03% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 5.46MB/s ± 1% 8.17MB/s ± 2% +49.56% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 31.8MB/s ± 1% 31.4MB/s ± 1% -1.28% (p=0.024 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 21.3MB/s ± 1% 22.5MB/s ± 1% +5.52% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 5.85MB/s ± 2% 9.15MB/s ± 1% +56.37% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 17.0MB/s ± 2% 16.8MB/s ± 1% ~ (p=0.056 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 11.5MB/s ± 2% 11.9MB/s ± 1% +2.82% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 4.56MB/s ± 2% 6.33MB/s ± 1% +38.89% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 6.57MB/s ± 3% 6.66MB/s ± 2% ~ (p=0.087 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 5.47MB/s ± 4% 5.58MB/s ± 1% ~ (p=0.135 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 2.97MB/s ± 1% 3.65MB/s ± 4% +22.98% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 126MB/s ± 1% 120MB/s ± 2% -4.18% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 85.0MB/s ± 3% 85.6MB/s ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 34.7MB/s ± 4% 45.4MB/s ± 1% +30.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 93.4MB/s ± 2% 90.5MB/s ± 1% -3.17% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 63.8MB/s ± 3% 62.9MB/s ± 1% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 33.4MB/s ± 1% 42.9MB/s ± 2% +28.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 37.2MB/s ± 0% 36.3MB/s ± 1% -2.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 24.1MB/s ± 2% 23.6MB/s ± 2% -1.84% (p=0.032 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 15.9MB/s ± 3% 17.6MB/s ± 3% +10.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 11.1MB/s ± 1% 11.1MB/s ± 1% ~ (p=0.635 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 9.09MB/s ± 2% 9.07MB/s ± 2% ~ (p=0.643 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 6.63MB/s ± 2% 6.94MB/s ± 3% +4.68% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 179MB/s ± 1% 172MB/s ± 1% -4.16% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 121MB/s ± 2% 117MB/s ± 1% -3.16% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 84.5MB/s ± 1% 92.6MB/s ± 1% +9.56% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 129MB/s ± 2% 126MB/s ± 3% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 84.4MB/s ± 1% 82.3MB/s ± 1% -2.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 66.1MB/s ± 2% 70.8MB/s ± 1% +7.04% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 43.7MB/s ± 4% 42.7MB/s ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 27.2MB/s ± 2% 27.3MB/s ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 21.6MB/s ± 5% 22.0MB/s ± 2% ~ (p=0.135 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 12.5MB/s ± 3% 12.6MB/s ± 3% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 10.0MB/s ± 2% 10.1MB/s ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 7.89MB/s ± 3% 8.04MB/s ± 5% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 180MB/s ± 1% 190MB/s ± 1% +5.94% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 120MB/s ± 1% 125MB/s ± 2% +4.06% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 101MB/s ± 1% 102MB/s ± 1% +1.60% (p=0.016 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 130MB/s ± 2% 131MB/s ± 1% ~ (p=1.000 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 86.3MB/s ± 1% 88.2MB/s ± 1% +2.14% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 75.5MB/s ± 1% 76.0MB/s ± 1% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 44.7MB/s ± 3% 44.4MB/s ± 1% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 28.2MB/s ± 2% 28.3MB/s ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 23.2MB/s ± 3% 22.9MB/s ± 3% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 12.4MB/s ± 1% 12.7MB/s ± 5% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 10.0MB/s ± 5% 10.2MB/s ± 5% ~ (p=0.643 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 7.69MB/s ± 7% 7.60MB/s ± 4% ~ (p=0.841 n=5+5) ``` Close cockroachdb#1829. Informs cockroachdb/cockroach#83049.

93723: storage: use NextPrefix r=jbowens a=jbowens Update pebbleIterator to use the new NextPrefix method exposed by Pebble Iterators (cockroachdb/pebble#1860). NextPrefix implements semanatics analgous to MVCCIterator.NextKey and is able to make use of low-level optimizations to avoid much of the work of a full seek. Additionally in the case where the very next key is a new MVCC user key, the pebbleMVCCScanner is able to use NextPrefix to avoid a key copy and a key comparison. ``` name old speed new speed delta MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 6.20MB/s ± 2% 6.24MB/s ± 1% ~ (p=0.524 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 3.71MB/s ± 1% 3.90MB/s ± 1% +5.01% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 376kB/s ± 2% 670kB/s ± 0% +78.19% (p=0.016 n=5+4) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 4.87MB/s ± 0% 5.00MB/s ± 2% +2.71% (p=0.032 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 3.08MB/s ± 1% 3.18MB/s ± 1% +3.38% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 420kB/s ± 0% 758kB/s ± 2% +80.48% (p=0.016 n=4+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 3.21MB/s ± 1% 3.27MB/s ± 2% +1.99% (p=0.024 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 2.11MB/s ± 2% 2.23MB/s ± 2% +5.89% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 410kB/s ± 2% 688kB/s ± 2% +67.80% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 1.55MB/s ± 1% 1.65MB/s ± 2% +6.19% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 1.26MB/s ± 2% 1.33MB/s ± 3% +5.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 460kB/s ± 0% 536kB/s ± 3% +16.52% (p=0.016 n=4+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 41.4MB/s ± 2% 41.2MB/s ± 2% ~ (p=0.516 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 26.5MB/s ± 2% 27.1MB/s ± 1% +2.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 5.37MB/s ± 2% 6.17MB/s ± 1% +14.74% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 32.7MB/s ± 2% 31.5MB/s ± 3% -3.51% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 21.4MB/s ± 0% 21.6MB/s ± 1% +1.18% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 5.88MB/s ± 1% 6.74MB/s ± 0% +14.51% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 17.2MB/s ± 2% 18.5MB/s ± 1% +7.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 11.6MB/s ± 2% 13.2MB/s ± 2% +13.93% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 4.56MB/s ± 1% 5.58MB/s ± 1% +22.36% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 6.79MB/s ± 3% 7.50MB/s ± 2% +10.45% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 5.53MB/s ± 2% 6.31MB/s ± 2% +13.95% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 2.94MB/s ± 1% 3.54MB/s ± 1% +20.27% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 125MB/s ± 1% 124MB/s ± 1% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 84.2MB/s ± 3% 86.1MB/s ± 2% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 33.7MB/s ± 3% 38.0MB/s ± 1% +12.83% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 92.7MB/s ± 1% 94.5MB/s ± 1% +1.90% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 62.5MB/s ± 1% 65.4MB/s ± 1% +4.75% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 32.0MB/s ± 1% 36.4MB/s ± 1% +13.51% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 36.5MB/s ± 3% 41.3MB/s ± 4% +13.05% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 23.7MB/s ± 2% 30.8MB/s ± 2% +29.93% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 15.8MB/s ± 1% 21.3MB/s ± 2% +34.67% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 11.1MB/s ± 1% 12.6MB/s ± 2% +13.08% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 9.06MB/s ± 2% 11.08MB/s ± 2% +22.29% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 6.65MB/s ± 1% 8.91MB/s ± 2% +33.95% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 175MB/s ± 2% 176MB/s ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 120MB/s ± 1% 124MB/s ± 1% +3.59% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 81.3MB/s ± 2% 87.5MB/s ± 1% +7.62% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 122MB/s ± 1% 132MB/s ± 2% +7.88% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 82.5MB/s ± 2% 90.5MB/s ± 2% +9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 65.2MB/s ± 1% 72.0MB/s ± 1% +10.41% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 42.9MB/s ± 1% 50.2MB/s ± 2% +17.02% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 27.3MB/s ± 1% 36.7MB/s ± 1% +34.49% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 21.4MB/s ± 3% 31.4MB/s ± 4% +46.71% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 12.5MB/s ± 3% 14.6MB/s ± 5% +16.55% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 10.3MB/s ± 4% 13.2MB/s ± 2% +28.04% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 8.00MB/s ± 4% 11.47MB/s ± 4% +43.25% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 193MB/s ± 2% 197MB/s ± 1% +2.33% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 130MB/s ± 2% 133MB/s ± 1% +2.05% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 104MB/s ± 2% 108MB/s ± 1% +3.41% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 137MB/s ± 1% 143MB/s ± 2% +4.14% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 89.4MB/s ± 2% 95.8MB/s ± 0% +7.10% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 77.3MB/s ± 2% 82.3MB/s ± 2% +6.47% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 44.9MB/s ± 1% 52.7MB/s ± 3% +17.30% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 28.6MB/s ± 2% 39.0MB/s ± 5% +36.19% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 22.6MB/s ± 7% 34.5MB/s ± 5% +52.68% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 13.2MB/s ± 3% 15.2MB/s ± 4% +15.51% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 10.5MB/s ± 4% 13.4MB/s ± 2% +27.11% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 8.13MB/s ± 6% 11.87MB/s ± 3% +45.98% (p=0.008 n=5+5) ``` Epic: None Informs #83049. Release note: None 94815: ci: fix unit_tests_impl.sh r=rickystewart a=srosenberg Previous PR forgot to source teamcity-support.sh which defines tc_release_branch(). Epic: none Release note: None 94840: randgen: ensure template does not become stale r=postamar a=postamar This commit adds a unit test that ensures that the hard-coded table template is not stale in the face of RunPostDeserializationChanges. Informs #94026. Release note: None Co-authored-by: Jackson Owens <[email protected]> Co-authored-by: Stan Rosenberg <[email protected]> Co-authored-by: Marius Posta <[email protected]>

Alter the semantics of SeekGE and SeekLT on FragmentIterator. Previously, FragmentIterator's seek operations were defined only in terms of span start keys. This commit changes the seek operations to be defined in terms of the keys contained by the span. A SeekGE now seeks to the first span containing a key ≥ the seek key, and a SeekLT now seeks to the last span containing a key < seek key. These new semantics match the typical top-level iterator use. With these new semantics, SeekLT can still be implemented in terms of a simple span start key seek. Seeking to the last span containing a key < seek key is equivalent to seeking to the last span with a start key less the given key. However, SeekGE implementations now require an extra key comparison and sometimes a Next. Since top-level iterator requires the containment semantics anyways, this key comparison and Next is only being moved down the stack into the interface implementation. When using the keyspan merging iterator, the keyspan.MergingIter's SeekGE implementation performs a SeekLT per-level, which suffers no additional overhead. With the MergingIter and DefragmentingIter implementations, these new semantics reduce the amount of work performed during a seek. The previous iterator stack's SeekGE looked like (left-to-right, top-down): InterleavingIter.SeekGE │ ╭────────────────┴───────────────╮ │ │ DefragmentingIter.SeekLT DefragmentingIter.Next() │ │ ╭───────────┴───╮ │ │ │ │ MergingIter.SeekLT ├── defragmentFwd ├── defragmentFwd │ │ │ │ ╰── defragmentBwd ╰── defragmentFwd ╰───────────╮ │ ╭───────────┴───────────╮ │ │ MergingIter.SeekGE MergingIter.Prev │ ╰─╶╶ per level╶╶ ─╮ │ ╭───────────┴───────────╮ │ │ <?>.SeekLT <?>.Next The new iterator stack's SeekGE, assuming it doesn't hit the new defragmenting fast path, looks like: InterleavingIter.SeekGE │ DefragmentingIter.SeekGE │ ╭────────────────┴───────────────╮ │ ├── defragmentBwd* MergingIter.SeekGE │ │ ╰── defragmentFwd ╰─╶╶ per level╶╶ ─╮ │ │ ├── <?>.SeekLT │ ╰── <?>.Next * — The call to defragmentBackward during SeekGE may now sometimes be elided, specifically if the span discovered by MergingIter.SeekGE does not contain the seek key within its bounds. Note that in this interface, there are no calls to any of the leaf FragmentIterator's SeekGE methods which would suffer the extra key comparison and Next. Instead, the MergingIter calls SeekLT and unconditionally Nexts each of the leafs as a part of its logic to fragment bounds across levels. This reduced work for seeks has a large impact on the MVCCGet and MVCCScan microbenchmarks in the presence of range keys. ``` name old time/op new time/op delta MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=0-24 6.30µs ± 1% 6.22µs ± 2% ~ (p=0.095 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=1-24 11.5µs ± 1% 10.3µs ± 1% -9.95% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=100-24 118µs ± 1% 79µs ± 2% -33.14% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=0-24 23.9µs ± 1% 24.1µs ± 2% ~ (p=0.310 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=1-24 31.7µs ± 2% 29.6µs ± 1% -6.65% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=100-24 109µs ± 1% 69µs ± 2% -36.58% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=0-24 100µs ± 1% 99µs ± 3% ~ (p=0.310 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=1-24 110µs ± 1% 106µs ± 2% -3.24% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=100-24 197µs ± 2% 153µs ± 1% -22.75% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 3.74µs ± 1% 3.57µs ± 1% -4.47% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 6.01µs ± 1% 4.93µs ± 2% -17.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=100-24 66.1µs ± 1% 28.8µs ± 1% -56.35% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=0-24 20.4µs ± 1% 20.4µs ± 1% ~ (p=0.690 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=1-24 25.9µs ± 1% 23.9µs ± 3% -7.79% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=100-24 89.3µs ± 1% 50.2µs ± 2% -43.76% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=0-24 98.7µs ± 1% 97.9µs ± 1% ~ (p=0.151 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=1-24 106µs ± 1% 103µs ± 1% -2.63% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=100-24 179µs ± 3% 131µs ± 2% -26.75% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 10.9µs ± 3% 10.7µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 17.9µs ± 1% 16.1µs ± 2% -10.35% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 172µs ± 1% 94µs ± 2% -45.23% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 13.0µs ± 1% 13.1µs ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 21.1µs ± 1% 19.0µs ± 2% -9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 158µs ± 1% 83µs ± 3% -47.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 20.3µs ± 1% 20.1µs ± 2% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 30.6µs ± 2% 27.6µs ± 1% -9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 160µs ± 2% 88µs ± 3% -45.10% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 41.5µs ± 1% 41.1µs ± 1% -0.97% (p=0.048 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 50.9µs ± 1% 48.6µs ± 2% -4.67% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 140µs ± 2% 94µs ± 1% -32.43% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 15.6µs ± 2% 16.1µs ± 1% +3.21% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 24.0µs ± 1% 23.1µs ± 2% -3.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 117µs ± 1% 78µs ± 2% -33.17% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 20.1µs ± 1% 20.4µs ± 1% +1.30% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 30.1µs ± 1% 28.5µs ± 1% -5.25% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 109µs ± 2% 70µs ± 1% -36.07% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 37.7µs ± 2% 38.1µs ± 1% ~ (p=0.056 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 55.5µs ± 2% 53.9µs ± 1% -2.79% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 140µs ± 2% 101µs ± 1% -27.99% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 97.5µs ± 3% 96.1µs ± 2% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 117µs ± 4% 115µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 216µs ± 1% 176µs ± 4% -18.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 50.9µs ± 1% 53.2µs ± 2% +4.37% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 75.3µs ± 2% 74.8µs ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 184µs ± 3% 141µs ± 1% -23.61% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 68.5µs ± 2% 70.7µs ± 1% +3.27% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 100µs ± 3% 102µs ± 1% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 192µs ± 1% 149µs ± 2% -22.12% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 172µs ± 0% 176µs ± 1% +2.48% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 266µs ± 2% 271µs ± 2% +1.88% (p=0.032 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 404µs ± 3% 364µs ± 3% -9.69% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 579µs ± 1% 578µs ± 1% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 704µs ± 1% 706µs ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 965µs ± 2% 923µs ± 3% -4.45% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 357µs ± 1% 372µs ± 1% +4.34% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 529µs ± 2% 546µs ± 1% +3.26% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 757µs ± 1% 691µs ± 1% -8.72% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 496µs ± 2% 507µs ± 2% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 758µs ± 1% 778µs ± 1% +2.63% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 968µs ± 2% 904µs ± 1% -6.58% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 1.46ms ± 4% 1.50ms ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 2.36ms ± 2% 2.35ms ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 2.97ms ± 5% 2.91ms ± 2% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 5.12ms ± 3% 5.08ms ± 3% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 6.38ms ± 2% 6.34ms ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 8.11ms ± 3% 7.97ms ± 5% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 3.56ms ± 1% 3.37ms ± 1% -5.61% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 5.32ms ± 1% 5.12ms ± 2% -3.90% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 6.35ms ± 1% 6.25ms ± 1% -1.59% (p=0.016 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 4.91ms ± 2% 4.90ms ± 1% ~ (p=1.000 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 7.41ms ± 1% 7.26ms ± 1% -2.10% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 8.48ms ± 1% 8.42ms ± 1% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 14.3ms ± 3% 14.4ms ± 1% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 22.7ms ± 2% 22.6ms ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 27.7ms ± 3% 28.0ms ± 3% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 51.8ms ± 1% 50.4ms ± 5% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 64.0ms ± 6% 63.0ms ± 4% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 83.4ms ± 7% 84.3ms ± 4% ~ (p=0.841 n=5+5) name old speed new speed delta MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=0-24 1.27MB/s ± 2% 1.28MB/s ± 2% ~ (p=0.119 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=1-24 696kB/s ± 1% 774kB/s ± 1% +11.21% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=100-24 70.0kB/s ± 0% 100.0kB/s ± 0% +42.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=0-24 336kB/s ± 2% 330kB/s ± 0% ~ (p=0.095 n=5+4) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=1-24 250kB/s ± 0% 270kB/s ± 0% +8.00% (p=0.016 n=4+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=100-24 70.0kB/s ± 0% 114.0kB/s ± 5% +62.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=0-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=1-24 70.0kB/s ± 0% 76.0kB/s ± 8% ~ (p=0.167 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=100-24 40.0kB/s ± 0% 50.0kB/s ± 0% +25.00% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 2.14MB/s ± 1% 2.24MB/s ± 1% +4.68% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 1.33MB/s ± 1% 1.62MB/s ± 2% +21.77% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=100-24 120kB/s ± 0% 280kB/s ± 0% +133.33% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=0-24 390kB/s ± 0% 390kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=1-24 310kB/s ± 0% 340kB/s ± 0% +9.68% (p=0.016 n=5+4) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=100-24 90.0kB/s ± 0% 160.0kB/s ± 0% +77.78% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=0-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=1-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=100-24 44.0kB/s ±14% 60.0kB/s ± 0% +36.36% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 5.90MB/s ± 3% 6.00MB/s ± 1% ~ (p=0.119 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 3.57MB/s ± 1% 3.98MB/s ± 2% +11.53% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 370kB/s ± 0% 678kB/s ± 2% +83.24% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 4.91MB/s ± 1% 4.90MB/s ± 2% ~ (p=0.730 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 3.04MB/s ± 1% 3.36MB/s ± 2% +10.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 404kB/s ± 1% 772kB/s ± 3% +91.09% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 3.15MB/s ± 1% 3.19MB/s ± 2% ~ (p=0.167 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 2.09MB/s ± 2% 2.32MB/s ± 1% +10.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 400kB/s ± 0% 730kB/s ± 3% +82.50% (p=0.016 n=4+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 1.54MB/s ± 1% 1.56MB/s ± 1% +1.17% (p=0.048 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 1.26MB/s ± 1% 1.32MB/s ± 2% +4.93% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 460kB/s ± 2% 680kB/s ± 0% +47.83% (p=0.016 n=5+4) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 41.0MB/s ± 2% 39.7MB/s ± 1% -3.13% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 26.6MB/s ± 1% 27.7MB/s ± 2% +4.03% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 5.46MB/s ± 1% 8.17MB/s ± 2% +49.56% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 31.8MB/s ± 1% 31.4MB/s ± 1% -1.28% (p=0.024 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 21.3MB/s ± 1% 22.5MB/s ± 1% +5.52% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 5.85MB/s ± 2% 9.15MB/s ± 1% +56.37% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 17.0MB/s ± 2% 16.8MB/s ± 1% ~ (p=0.056 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 11.5MB/s ± 2% 11.9MB/s ± 1% +2.82% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 4.56MB/s ± 2% 6.33MB/s ± 1% +38.89% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 6.57MB/s ± 3% 6.66MB/s ± 2% ~ (p=0.087 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 5.47MB/s ± 4% 5.58MB/s ± 1% ~ (p=0.135 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 2.97MB/s ± 1% 3.65MB/s ± 4% +22.98% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 126MB/s ± 1% 120MB/s ± 2% -4.18% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 85.0MB/s ± 3% 85.6MB/s ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 34.7MB/s ± 4% 45.4MB/s ± 1% +30.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 93.4MB/s ± 2% 90.5MB/s ± 1% -3.17% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 63.8MB/s ± 3% 62.9MB/s ± 1% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 33.4MB/s ± 1% 42.9MB/s ± 2% +28.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 37.2MB/s ± 0% 36.3MB/s ± 1% -2.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 24.1MB/s ± 2% 23.6MB/s ± 2% -1.84% (p=0.032 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 15.9MB/s ± 3% 17.6MB/s ± 3% +10.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 11.1MB/s ± 1% 11.1MB/s ± 1% ~ (p=0.635 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 9.09MB/s ± 2% 9.07MB/s ± 2% ~ (p=0.643 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 6.63MB/s ± 2% 6.94MB/s ± 3% +4.68% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 179MB/s ± 1% 172MB/s ± 1% -4.16% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 121MB/s ± 2% 117MB/s ± 1% -3.16% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 84.5MB/s ± 1% 92.6MB/s ± 1% +9.56% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 129MB/s ± 2% 126MB/s ± 3% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 84.4MB/s ± 1% 82.3MB/s ± 1% -2.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 66.1MB/s ± 2% 70.8MB/s ± 1% +7.04% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 43.7MB/s ± 4% 42.7MB/s ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 27.2MB/s ± 2% 27.3MB/s ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 21.6MB/s ± 5% 22.0MB/s ± 2% ~ (p=0.135 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 12.5MB/s ± 3% 12.6MB/s ± 3% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 10.0MB/s ± 2% 10.1MB/s ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 7.89MB/s ± 3% 8.04MB/s ± 5% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 180MB/s ± 1% 190MB/s ± 1% +5.94% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 120MB/s ± 1% 125MB/s ± 2% +4.06% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 101MB/s ± 1% 102MB/s ± 1% +1.60% (p=0.016 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 130MB/s ± 2% 131MB/s ± 1% ~ (p=1.000 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 86.3MB/s ± 1% 88.2MB/s ± 1% +2.14% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 75.5MB/s ± 1% 76.0MB/s ± 1% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 44.7MB/s ± 3% 44.4MB/s ± 1% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 28.2MB/s ± 2% 28.3MB/s ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 23.2MB/s ± 3% 22.9MB/s ± 3% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 12.4MB/s ± 1% 12.7MB/s ± 5% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 10.0MB/s ± 5% 10.2MB/s ± 5% ~ (p=0.643 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 7.69MB/s ± 7% 7.60MB/s ± 4% ~ (p=0.841 n=5+5) ``` Close cockroachdb#1829. Informs cockroachdb/cockroach#83049.

Alter the semantics of SeekGE and SeekLT on FragmentIterator. Previously, FragmentIterator's seek operations were defined only in terms of span start keys. This commit changes the seek operations to be defined in terms of the keys contained by the span. A SeekGE now seeks to the first span containing a key ≥ the seek key, and a SeekLT now seeks to the last span containing a key < seek key. These new semantics match the typical top-level iterator use. With these new semantics, SeekLT can still be implemented in terms of a simple span start key seek. Seeking to the last span containing a key < seek key is equivalent to seeking to the last span with a start key less the given key. However, SeekGE implementations now require an extra key comparison and sometimes a Next. Since top-level iterator requires the containment semantics anyways, this key comparison and Next is only being moved down the stack into the interface implementation. When using the keyspan merging iterator, the keyspan.MergingIter's SeekGE implementation performs a SeekLT per-level, which suffers no additional overhead. With the MergingIter and DefragmentingIter implementations, these new semantics reduce the amount of work performed during a seek. The previous iterator stack's SeekGE looked like (left-to-right, top-down): InterleavingIter.SeekGE │ ╭────────────────┴───────────────╮ │ │ DefragmentingIter.SeekLT DefragmentingIter.Next() │ │ ╭───────────┴───╮ │ │ │ │ MergingIter.SeekLT ├── defragmentFwd ├── defragmentFwd │ │ │ │ ╰── defragmentBwd ╰── defragmentFwd ╰───────────╮ │ ╭───────────┴───────────╮ │ │ MergingIter.SeekGE MergingIter.Prev │ ╰─╶╶ per level╶╶ ─╮ │ ╭───────────┴───────────╮ │ │ <?>.SeekLT <?>.Next The new iterator stack's SeekGE, assuming it doesn't hit the new defragmenting fast path, looks like: InterleavingIter.SeekGE │ DefragmentingIter.SeekGE │ ╭────────────────┴───────────────╮ │ ├── defragmentBwd* MergingIter.SeekGE │ │ ╰── defragmentFwd ╰─╶╶ per level╶╶ ─╮ │ │ ├── <?>.SeekLT │ ╰── <?>.Next * — The call to defragmentBackward during SeekGE may now sometimes be elided, specifically if the span discovered by MergingIter.SeekGE does not contain the seek key within its bounds. Note that in this interface, there are no calls to any of the leaf FragmentIterator's SeekGE methods which would suffer the extra key comparison and Next. Instead, the MergingIter calls SeekLT and unconditionally Nexts each of the leafs as a part of its logic to fragment bounds across levels. This reduced work for seeks has a large impact on the MVCCGet and MVCCScan microbenchmarks in the presence of range keys. ``` name old time/op new time/op delta MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=0-24 6.30µs ± 1% 6.22µs ± 2% ~ (p=0.095 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=1-24 11.5µs ± 1% 10.3µs ± 1% -9.95% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=100-24 118µs ± 1% 79µs ± 2% -33.14% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=0-24 23.9µs ± 1% 24.1µs ± 2% ~ (p=0.310 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=1-24 31.7µs ± 2% 29.6µs ± 1% -6.65% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=100-24 109µs ± 1% 69µs ± 2% -36.58% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=0-24 100µs ± 1% 99µs ± 3% ~ (p=0.310 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=1-24 110µs ± 1% 106µs ± 2% -3.24% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=100-24 197µs ± 2% 153µs ± 1% -22.75% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 3.74µs ± 1% 3.57µs ± 1% -4.47% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 6.01µs ± 1% 4.93µs ± 2% -17.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=100-24 66.1µs ± 1% 28.8µs ± 1% -56.35% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=0-24 20.4µs ± 1% 20.4µs ± 1% ~ (p=0.690 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=1-24 25.9µs ± 1% 23.9µs ± 3% -7.79% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=100-24 89.3µs ± 1% 50.2µs ± 2% -43.76% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=0-24 98.7µs ± 1% 97.9µs ± 1% ~ (p=0.151 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=1-24 106µs ± 1% 103µs ± 1% -2.63% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=100-24 179µs ± 3% 131µs ± 2% -26.75% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 10.9µs ± 3% 10.7µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 17.9µs ± 1% 16.1µs ± 2% -10.35% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 172µs ± 1% 94µs ± 2% -45.23% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 13.0µs ± 1% 13.1µs ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 21.1µs ± 1% 19.0µs ± 2% -9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 158µs ± 1% 83µs ± 3% -47.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 20.3µs ± 1% 20.1µs ± 2% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 30.6µs ± 2% 27.6µs ± 1% -9.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 160µs ± 2% 88µs ± 3% -45.10% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 41.5µs ± 1% 41.1µs ± 1% -0.97% (p=0.048 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 50.9µs ± 1% 48.6µs ± 2% -4.67% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 140µs ± 2% 94µs ± 1% -32.43% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 15.6µs ± 2% 16.1µs ± 1% +3.21% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 24.0µs ± 1% 23.1µs ± 2% -3.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 117µs ± 1% 78µs ± 2% -33.17% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 20.1µs ± 1% 20.4µs ± 1% +1.30% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 30.1µs ± 1% 28.5µs ± 1% -5.25% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 109µs ± 2% 70µs ± 1% -36.07% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 37.7µs ± 2% 38.1µs ± 1% ~ (p=0.056 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 55.5µs ± 2% 53.9µs ± 1% -2.79% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 140µs ± 2% 101µs ± 1% -27.99% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 97.5µs ± 3% 96.1µs ± 2% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 117µs ± 4% 115µs ± 1% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 216µs ± 1% 176µs ± 4% -18.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 50.9µs ± 1% 53.2µs ± 2% +4.37% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 75.3µs ± 2% 74.8µs ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 184µs ± 3% 141µs ± 1% -23.61% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 68.5µs ± 2% 70.7µs ± 1% +3.27% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 100µs ± 3% 102µs ± 1% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 192µs ± 1% 149µs ± 2% -22.12% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 172µs ± 0% 176µs ± 1% +2.48% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 266µs ± 2% 271µs ± 2% +1.88% (p=0.032 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 404µs ± 3% 364µs ± 3% -9.69% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 579µs ± 1% 578µs ± 1% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 704µs ± 1% 706µs ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 965µs ± 2% 923µs ± 3% -4.45% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 357µs ± 1% 372µs ± 1% +4.34% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 529µs ± 2% 546µs ± 1% +3.26% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 757µs ± 1% 691µs ± 1% -8.72% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 496µs ± 2% 507µs ± 2% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 758µs ± 1% 778µs ± 1% +2.63% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 968µs ± 2% 904µs ± 1% -6.58% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 1.46ms ± 4% 1.50ms ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 2.36ms ± 2% 2.35ms ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 2.97ms ± 5% 2.91ms ± 2% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 5.12ms ± 3% 5.08ms ± 3% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 6.38ms ± 2% 6.34ms ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 8.11ms ± 3% 7.97ms ± 5% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 3.56ms ± 1% 3.37ms ± 1% -5.61% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 5.32ms ± 1% 5.12ms ± 2% -3.90% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 6.35ms ± 1% 6.25ms ± 1% -1.59% (p=0.016 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 4.91ms ± 2% 4.90ms ± 1% ~ (p=1.000 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 7.41ms ± 1% 7.26ms ± 1% -2.10% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 8.48ms ± 1% 8.42ms ± 1% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 14.3ms ± 3% 14.4ms ± 1% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 22.7ms ± 2% 22.6ms ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 27.7ms ± 3% 28.0ms ± 3% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 51.8ms ± 1% 50.4ms ± 5% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 64.0ms ± 6% 63.0ms ± 4% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 83.4ms ± 7% 84.3ms ± 4% ~ (p=0.841 n=5+5) name old speed new speed delta MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=0-24 1.27MB/s ± 2% 1.28MB/s ± 2% ~ (p=0.119 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=1-24 696kB/s ± 1% 774kB/s ± 1% +11.21% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=1/valueSize=8/numRangeKeys=100-24 70.0kB/s ± 0% 100.0kB/s ± 0% +42.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=0-24 336kB/s ± 2% 330kB/s ± 0% ~ (p=0.095 n=5+4) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=1-24 250kB/s ± 0% 270kB/s ± 0% +8.00% (p=0.016 n=4+5) MVCCGet_Pebble/batch=false/versions=10/valueSize=8/numRangeKeys=100-24 70.0kB/s ± 0% 114.0kB/s ± 5% +62.86% (p=0.008 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=0-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=1-24 70.0kB/s ± 0% 76.0kB/s ± 8% ~ (p=0.167 n=5+5) MVCCGet_Pebble/batch=false/versions=100/valueSize=8/numRangeKeys=100-24 40.0kB/s ± 0% 50.0kB/s ± 0% +25.00% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=0-24 2.14MB/s ± 1% 2.24MB/s ± 1% +4.68% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=1-24 1.33MB/s ± 1% 1.62MB/s ± 2% +21.77% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=1/valueSize=8/numRangeKeys=100-24 120kB/s ± 0% 280kB/s ± 0% +133.33% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=0-24 390kB/s ± 0% 390kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=1-24 310kB/s ± 0% 340kB/s ± 0% +9.68% (p=0.016 n=5+4) MVCCGet_Pebble/batch=true/versions=10/valueSize=8/numRangeKeys=100-24 90.0kB/s ± 0% 160.0kB/s ± 0% +77.78% (p=0.008 n=5+5) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=0-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=1-24 80.0kB/s ± 0% 80.0kB/s ± 0% ~ (all equal) MVCCGet_Pebble/batch=true/versions=100/valueSize=8/numRangeKeys=100-24 44.0kB/s ±14% 60.0kB/s ± 0% +36.36% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=0-24 5.90MB/s ± 3% 6.00MB/s ± 1% ~ (p=0.119 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=1-24 3.57MB/s ± 1% 3.98MB/s ± 2% +11.53% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=1/valueSize=64/numRangeKeys=100-24 370kB/s ± 0% 678kB/s ± 2% +83.24% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=0-24 4.91MB/s ± 1% 4.90MB/s ± 2% ~ (p=0.730 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=1-24 3.04MB/s ± 1% 3.36MB/s ± 2% +10.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=2/valueSize=64/numRangeKeys=100-24 404kB/s ± 1% 772kB/s ± 3% +91.09% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=0-24 3.15MB/s ± 1% 3.19MB/s ± 2% ~ (p=0.167 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=1-24 2.09MB/s ± 2% 2.32MB/s ± 1% +10.70% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=10/valueSize=64/numRangeKeys=100-24 400kB/s ± 0% 730kB/s ± 3% +82.50% (p=0.016 n=4+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=0-24 1.54MB/s ± 1% 1.56MB/s ± 1% +1.17% (p=0.048 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=1-24 1.26MB/s ± 1% 1.32MB/s ± 2% +4.93% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1/versions=100/valueSize=64/numRangeKeys=100-24 460kB/s ± 2% 680kB/s ± 0% +47.83% (p=0.016 n=5+4) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=0-24 41.0MB/s ± 2% 39.7MB/s ± 1% -3.13% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=1-24 26.6MB/s ± 1% 27.7MB/s ± 2% +4.03% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=1/valueSize=64/numRangeKeys=100-24 5.46MB/s ± 1% 8.17MB/s ± 2% +49.56% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=0-24 31.8MB/s ± 1% 31.4MB/s ± 1% -1.28% (p=0.024 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=1-24 21.3MB/s ± 1% 22.5MB/s ± 1% +5.52% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=2/valueSize=64/numRangeKeys=100-24 5.85MB/s ± 2% 9.15MB/s ± 1% +56.37% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=0-24 17.0MB/s ± 2% 16.8MB/s ± 1% ~ (p=0.056 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=1-24 11.5MB/s ± 2% 11.9MB/s ± 1% +2.82% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=10/valueSize=64/numRangeKeys=100-24 4.56MB/s ± 2% 6.33MB/s ± 1% +38.89% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=0-24 6.57MB/s ± 3% 6.66MB/s ± 2% ~ (p=0.087 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=1-24 5.47MB/s ± 4% 5.58MB/s ± 1% ~ (p=0.135 n=5+5) MVCCScan_Pebble/rows=10/versions=100/valueSize=64/numRangeKeys=100-24 2.97MB/s ± 1% 3.65MB/s ± 4% +22.98% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=0-24 126MB/s ± 1% 120MB/s ± 2% -4.18% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=1-24 85.0MB/s ± 3% 85.6MB/s ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=100/versions=1/valueSize=64/numRangeKeys=100-24 34.7MB/s ± 4% 45.4MB/s ± 1% +30.87% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=0-24 93.4MB/s ± 2% 90.5MB/s ± 1% -3.17% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=1-24 63.8MB/s ± 3% 62.9MB/s ± 1% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=100/versions=2/valueSize=64/numRangeKeys=100-24 33.4MB/s ± 1% 42.9MB/s ± 2% +28.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=0-24 37.2MB/s ± 0% 36.3MB/s ± 1% -2.42% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=1-24 24.1MB/s ± 2% 23.6MB/s ± 2% -1.84% (p=0.032 n=5+5) MVCCScan_Pebble/rows=100/versions=10/valueSize=64/numRangeKeys=100-24 15.9MB/s ± 3% 17.6MB/s ± 3% +10.73% (p=0.008 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=0-24 11.1MB/s ± 1% 11.1MB/s ± 1% ~ (p=0.635 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=1-24 9.09MB/s ± 2% 9.07MB/s ± 2% ~ (p=0.643 n=5+5) MVCCScan_Pebble/rows=100/versions=100/valueSize=64/numRangeKeys=100-24 6.63MB/s ± 2% 6.94MB/s ± 3% +4.68% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=0-24 179MB/s ± 1% 172MB/s ± 1% -4.16% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=1-24 121MB/s ± 2% 117MB/s ± 1% -3.16% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=1/valueSize=64/numRangeKeys=100-24 84.5MB/s ± 1% 92.6MB/s ± 1% +9.56% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=0-24 129MB/s ± 2% 126MB/s ± 3% ~ (p=0.222 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=1-24 84.4MB/s ± 1% 82.3MB/s ± 1% -2.57% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=2/valueSize=64/numRangeKeys=100-24 66.1MB/s ± 2% 70.8MB/s ± 1% +7.04% (p=0.008 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=0-24 43.7MB/s ± 4% 42.7MB/s ± 2% ~ (p=0.421 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=1-24 27.2MB/s ± 2% 27.3MB/s ± 1% ~ (p=0.841 n=5+5) MVCCScan_Pebble/rows=1000/versions=10/valueSize=64/numRangeKeys=100-24 21.6MB/s ± 5% 22.0MB/s ± 2% ~ (p=0.135 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=0-24 12.5MB/s ± 3% 12.6MB/s ± 3% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=1-24 10.0MB/s ± 2% 10.1MB/s ± 2% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=1000/versions=100/valueSize=64/numRangeKeys=100-24 7.89MB/s ± 3% 8.04MB/s ± 5% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=0-24 180MB/s ± 1% 190MB/s ± 1% +5.94% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=1-24 120MB/s ± 1% 125MB/s ± 2% +4.06% (p=0.008 n=5+5) MVCCScan_Pebble/rows=10000/versions=1/valueSize=64/numRangeKeys=100-24 101MB/s ± 1% 102MB/s ± 1% +1.60% (p=0.016 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=0-24 130MB/s ± 2% 131MB/s ± 1% ~ (p=1.000 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=1-24 86.3MB/s ± 1% 88.2MB/s ± 1% +2.14% (p=0.032 n=5+5) MVCCScan_Pebble/rows=10000/versions=2/valueSize=64/numRangeKeys=100-24 75.5MB/s ± 1% 76.0MB/s ± 1% ~ (p=0.095 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=0-24 44.7MB/s ± 3% 44.4MB/s ± 1% ~ (p=0.310 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=1-24 28.2MB/s ± 2% 28.3MB/s ± 2% ~ (p=0.690 n=5+5) MVCCScan_Pebble/rows=10000/versions=10/valueSize=64/numRangeKeys=100-24 23.2MB/s ± 3% 22.9MB/s ± 3% ~ (p=0.548 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=0-24 12.4MB/s ± 1% 12.7MB/s ± 5% ~ (p=0.151 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=1-24 10.0MB/s ± 5% 10.2MB/s ± 5% ~ (p=0.643 n=5+5) MVCCScan_Pebble/rows=10000/versions=100/valueSize=64/numRangeKeys=100-24 7.69MB/s ± 7% 7.60MB/s ± 4% ~ (p=0.841 n=5+5) ``` Close #1829. Informs cockroachdb/cockroach#83049.

jbowens · 2023-01-30T22:36:46Z

Need to re-run these benchmarks to verify the performance from recent changes.

nicktrav · 2023-05-10T22:36:43Z

@jbowens - shall we close this now?

erikgrinaker · 2023-05-10T22:43:27Z

Do we no longer see the 3000% penalty on point gets? What are we down to?

jbowens · 2024-08-15T20:41:06Z

Keyspan columnar blocks are expected to help here.

cockroachdb/pebble#3782

jbowens · 2024-11-07T21:23:16Z

Columnar blocks significantly reduced the overhead from keyspan iteration.

erikgrinaker added C-performance Perf of queries or internals. Solution not expected to change functional behavior. A-storage Relating to our storage engine (Pebble) on-disk storage. T-kv-replication labels Jun 18, 2022

blathers-crl bot added the A-kv-replication Relating to Raft, consensus, and coordination. label Jun 18, 2022

mwang1026 mentioned this issue Jun 22, 2022

perf: add range key benchmarks and address performance cockroachdb/pebble#1444

Closed

erikgrinaker mentioned this issue Jun 24, 2022

storage: support MVCC range tombstones in MVCCExportToSST #82873

Merged

This was referenced Jul 13, 2022

storage: optimize new SST iterators #83051

Closed

storage: benchmark and optimize ComputeStatsForRange #84544

Closed

This was referenced Aug 13, 2022

storage: optimize pointSynthesizingIter for MVCCGet #86093

Merged

storage: optimize pointSynthesizingIter for MVCCScan #86109

Merged

tbg mentioned this issue Aug 15, 2022

rangefeed: benchmark catch-up with tombstones #86128

Closed

This was referenced Aug 15, 2022

storage: add rangedels to BenchmarkMVCCExportToSST #86140

Closed

storage: add benchmark for MVCCIncrementalIterator with MVCC range dels #86444

Closed

exalate-issue-sync bot added T-storage Storage Team and removed T-kv-replication labels Oct 4, 2022

erikgrinaker removed the A-kv-replication Relating to Raft, consensus, and coordination. label Oct 4, 2022

jbowens self-assigned this Oct 10, 2022

jbowens mentioned this issue Nov 20, 2022

internal/keyspan: modify FragmentIterator seek semantics cockroachdb/pebble#2146

Merged

jbowens mentioned this issue Dec 5, 2022

db: add NextPrefix to Iterator cockroachdb/pebble#1860

Merged

jbowens mentioned this issue Dec 15, 2022

storage: use NextPrefix #93723

Merged

jbowens added this to [Deprecated] Storage Jun 4, 2024

jbowens moved this to Backlog in [Deprecated] Storage Jun 4, 2024

jbowens closed this as completed Nov 7, 2024

github-project-automation bot moved this from Backlog to Done in [Deprecated] Storage Nov 7, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

storage: optimize range key iteration #83049

storage: optimize range key iteration #83049

erikgrinaker commented Jun 18, 2022 •

edited by exalate-issue-sync bot

Loading

blathers-crl bot commented Jun 18, 2022

jbowens commented Jun 22, 2022

jbowens commented Jun 29, 2022

erikgrinaker commented Aug 15, 2022

jbowens commented Jan 30, 2023

nicktrav commented May 10, 2023

erikgrinaker commented May 10, 2023 •

edited

Loading

jbowens commented Aug 15, 2024 •

edited

Loading

jbowens commented Nov 7, 2024

storage: optimize range key iteration #83049

storage: optimize range key iteration #83049

Comments

erikgrinaker commented Jun 18, 2022 • edited by exalate-issue-sync bot Loading

blathers-crl bot commented Jun 18, 2022

jbowens commented Jun 22, 2022

jbowens commented Jun 29, 2022

erikgrinaker commented Aug 15, 2022

jbowens commented Jan 30, 2023

nicktrav commented May 10, 2023

erikgrinaker commented May 10, 2023 • edited Loading

jbowens commented Aug 15, 2024 • edited Loading

jbowens commented Nov 7, 2024

erikgrinaker commented Jun 18, 2022 •

edited by exalate-issue-sync bot

Loading

erikgrinaker commented May 10, 2023 •

edited

Loading

jbowens commented Aug 15, 2024 •

edited

Loading