My review was fairly mechanical. Probably worth another look from someone with additional context on the original revert.

Reviewed 2 of 14 files at r2, 24 of 25 files at r3, 2 of 2 files at r4, 1 of 2 files at r5, 11 of 11 files at r6, all commit messages.
Reviewable status: 34 of 36 files reviewed, 1 unresolved discussion (waiting on @jbowens and @nicktrav)

iterator.go line 1783 at r3 (raw file):

// SetBounds sets the lower and upper bounds for the iterator.
//
// The slices provided in this SetBounds must not be changed by the caller until

nit: "provided to SetBounds"?

Reviewed 12 of 25 files at r3, 1 of 2 files at r5, 1 of 11 files at r6.
Reviewable status: 34 of 38 files reviewed, 6 unresolved discussions (waiting on @jbowens, @nicktrav, and @sumeerbhola)

iterator.go line 1668 at r6 (raw file):

// and false otherwise.
func (i *Iterator) Valid() bool {
	return i.iterValidityState == IterValid && !i.requiresReposition

is this a semantic change, switching from non-deterministic behavior to deterministically exhausted?

iterator.go line 1820 at r6 (raw file):

		// should call a repositioning method. We could have arbitrarily set i.pos
		// to one of the values. But it results in more intuitive behavior in
		// tests, which do not always reposition.

is this comment stale due to the introduction of requiresReposition?

internal/arenaskl/iterator.go line 227 at r6 (raw file):

}

// SetBounds sets the lower and upper bounds for the iterator. If equal is true,

false?

internal/base/iterator.go line 211 at r6 (raw file):

	// SetBounds sets the lower and upper bounds for the iterator. If equal is
	// true, the provided bounds are logically equal to the previous bounds. If
	// equal, the iterator replaces its internal bounds with the new bounds.

In either case it needs to replace its internal bounds with the new bounds, yes?

sstable/reader.go line 1069 at r6 (raw file):

		return
	}

We've already set i.lower and lower to be equal, and same for the upper slices. So the comparisons below are no longer doing what they were intended to do.

Reviewable status: 30 of 38 files reviewed, 5 unresolved discussions (waiting on @nicktrav and @sumeerbhola)

iterator.go line 1668 at r6 (raw file):

not sure if I'm understanding the question correctly, but this ensures that SetBounds() itself always results in an exhausted iterator. Without it, the validity of the iterator after a SetBounds is still deterministic (a function of the previous bounds and the new bounds), but it's confusingly inconsistent. I wanted to keep the equal bounds optimization an internal optimization that doesn't leak through the interface.

iterator.go line 1820 at r6 (raw file):

i think it's still necessary (see my comment on requiresReposition

internal/arenaskl/iterator.go line 227 at r6 (raw file):

Done.

internal/base/iterator.go line 211 at r6 (raw file):

Done.

sstable/reader.go line 1069 at r6 (raw file):

Good catch, thanks

The metamorphic test extension I added in the second commit revealed a problem: The interleaving iterator needs to truncate spans to the configured bounds. This can result in the interleaving iterator returning the user-provided bound as a synthetic marker for the start bound. The top-level pebble.Iterator may have a key or iterKey that is still using the stale lower bound.

@sumeerbhola @erikgrinaker I'm tempted to endure the copy at each SetBounds. Thoughts?

Reviewable status: 30 of 38 files reviewed, 5 unresolved discussions (waiting on @erikgrinaker, @nicktrav, and @sumeerbhola)

This can result in the interleaving iterator returning the user-provided bound as a synthetic marker for the start bound. The top-level pebble.Iterator may have a key or iterKey that is still using the stale lower bound. [...] I'm tempted to endure the copy at each SetBounds. Thoughts?

Aren't we calling SetOptions/SetBounds on the top-level iterator too, so it can invalidate/update its key or iterKey? And any byte buffers that have been returned to the original caller will no longer be valid after a SetOptions/SetBounds call, right?

Reviewed 18 of 25 files at r3, 1 of 2 files at r4, 1 of 11 files at r6, 6 of 6 files at r8, 1 of 2 files at r9, 1 of 1 files at r10, all commit messages.
Reviewable status: 36 of 38 files reviewed, 6 unresolved discussions (waiting on @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

internal/base/iterator.go line 210 at r8 (raw file):

	// SetBounds sets the lower and upper bounds for the iterator. If equal is
	// true, the provided bounds are logically equal to the previous bounds.

Consider mentioning why this is needed.

so it can invalidate/update its key or iterKey?

We could, but it'd require two additional key comparisons and seems brittle. Once these keys are interleaved, it's easy to leak them all over.

Reviewable status: 36 of 38 files reviewed, 6 unresolved discussions (waiting on @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

so it can invalidate/update its key or iterKey?

We could, but it'd require two additional key comparisons and seems brittle. Once these keys are interleaved, it's easy to leak them all over.

I see. Don't we have the same problem with the bound slices that the caller passes, when the caller changes them after the second SetBounds() call?

I suppose copying might work, it'll come down to performance. Can we do the copy while reusing the byte buffer, or will that have similar problems? Want to do some quick benchmarks, or alternatively prepare a patch that I can benchmark in CRDB?

Reviewable status: 36 of 38 files reviewed, 6 unresolved discussions (waiting on @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

The metamorphic test extension I added in the second commit revealed a problem

So this would have been a bug even with the optimization being done in CockroachDB, and we're actually in a better place now since we can control the lifetime inside Pebble?
Does this also mean we cannot use the 2 slice optimization to reduce allocations or use a sync.Pool since we have no control over the lifetime of the slice? Any ideas on how to have control over the lifetime?

Reviewable status: 36 of 38 files reviewed, 6 unresolved discussions (waiting on @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

sstable/reader.go line 1069 at r6 (raw file):

Do we have a test that would have caught this bug?

Don't we have the same problem with the bound slices that the caller passes, when the caller changes them after the second SetBounds() call?

I think it's not a problem as long as we're not applying the equal bounds optimization. If we're invalidating the iterator, the caller is required to re-seek which clears any state that might reference the mangled bound. A SetBounds is documented as invalidating the iterator, so as soon as the caller calls SetBounds they can't rely on the return value of Key().

Can we do the copy while reusing the byte buffer, or will that have similar problems?

Yeah, I think we should be able to avoid the allocation and reuse a byte buffer pooled on the iterAlloc struct.

So this would have been a bug even with the optimization being done in CockroachDB, and we're actually in a better place now since we can control the lifetime inside Pebble?

I think we would be fine if we continued performing the optimization in CockroachDB. If CockroachDB refrains from calling SetBounds/SetOptions, the existing bound is unchanged.

The options I see are:

1. Adjust this PR as-written to update iterKey if equal to the lower bound, only during the optimized case. I believe this would work, it's just more subtle and brittle than I'd like. Maybe the metamorphic test extension in the second commit is sufficient to give us confidence that we'd notice if the old bound was leaked beyond an optimized SetBounds/SetOptions.
2. Keep the optimization in CockroachDB. This adds code duplication between CockroachDB's iterator reuse and SetOptions, since both functions need to compute the delta of previous and new options to apply optimizations. Additionally, SetOptions is more limited in the optimizations it can apply, since it can't ever apply the bounds optimization even if it would otherwise apply (eg, the IterOptions are only adding a new key type to the iterator).
3. Copy the new bounds into iterAlloc-pooled key buffers. In CockroachDB this would result in writing bounds twice when changing the bounds: once to formulate the bounds with the NUL terminator and once when copying them into a buffer with a Pebble-controlled lifetime. In the case that bounds don't change, this would avoid recursively propagating the new bound buffers down the iterator tree. In the case the bounds have not changed, the copy can be omitted.

The metamorphic test extension is picking up additional problems: one with i.span in interleaving iterator, and another yet to be identified. I think this speaks to the brittleness of this path. I'll put together a chance for the third option so that we can evaluate it.

Reviewable status: 36 of 38 files reviewed, 5 unresolved discussions (waiting on @erikgrinaker, @nicktrav, and @sumeerbhola)

sstable/reader.go line 1069 at r6 (raw file):

We don't and I'm open to suggestions here. This bug manifested as i.boundsCmp always set to zero, disabling this optimization.

The metamorphic test extension is picking up additional problems: one with i.span in interleaving iterator, and another yet to be identified. I think this speaks to the brittleness of this path. I'll put together a chance for the third option so that we can evaluate it.

I agree, let's give the copy option a shot and see if it's viable. If not, we can go with the existing CRDB bounds handling and RefreshBatchSnapshot() for now, and revisit later.

Reviewable status: 36 of 38 files reviewed, 5 unresolved discussions (waiting on @erikgrinaker, @nicktrav, and @sumeerbhola)

Put up #1675 with bounds-copying. @sumeerbhola voiced concerns about places in CockroachDB where we repeatedly set bounds and seek, like geospatial code paths. I was able to reuse buffers pooled on the iterAlloc, so allocations should be minimal.

I also fixed up all the known issues on this pull request. I'm running the metamorphic tests in the background to see if they shake out any additional issues.

Reviewable status: 33 of 38 files reviewed, 5 unresolved discussions (waiting on @erikgrinaker, @nicktrav, and @sumeerbhola)

Reviewable status: 33 of 38 files reviewed, 5 unresolved discussions (waiting on @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

sstable/reader.go line 1069 at r6 (raw file):

Does the InternalIteratorStats show any difference? I can't think of anything else. We could add number of next and seek calls to InternalIteratorStats, but it seems overkill for testing. Feel free to leave a TODO if we can't distinguish now. Even better, we should create an issue -- we have enough of these performance optimizations that we need some unit testing so we don't regress.

There's a remaining metamorphic test failure that appears to be a consequence of the metamorphic tests allowing relative positioning methods to be called after changing bounds/options without first seeking. Specifically, a level iterator may have returned a synthetic iterator bounds key that uses one of the user-provided bounds as a user key.

If we go this direction, I think we should refrain from expecting determinism in these cases that violate the Pebble Iterator's contract.

Reviewable status: 32 of 38 files reviewed, 5 unresolved discussions (waiting on @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)