Ah right, makes sense. I'll go back to an earlier iteration that hid mutations between absolute positioning calls. I was hoping we could get away with the stricter behavior to avoid accidental stale reads, but it'll be straightforward to hide the mutations rather than error.

Reviewable status: 0 of 5 files reviewed, all discussions resolved (waiting on @erikgrinaker and @sumeerbhola)

The iterator operates on a consistent snapshot. Iterators created on top of batches are the only way the data underlying an iterator can change. We could add some explicit facility that 'refreshes' iterators created on top of batches, instead of the implicit refreshes on seeks.

Reviewable status: 0 of 5 files reviewed, all discussions resolved (waiting on @erikgrinaker and @sumeerbhola)

Reviewed 1 of 5 files at r1, 5 of 5 files at r2, all commit messages.
Reviewable status: all files reviewed, 3 unresolved discussions (waiting on @erikgrinaker, @jbowens, and @sumeerbhola)

iterator.go, line 1873 at r2 (raw file):

// operation. If the iterator includes iteration over an indexed batch, the
// batch's counts of range deletions and range keys are consulted to determine
// if new range deletions or range keys were written to the batch since the last
// seek.

Is this comment outdated? My understanding is that the condition is more general now in that any mutation on the batch updates the "seqnum" which is being used to determine whether to re-init the iter - i.e. not limited to just range del / range key counts.

testdata/indexed_batch_mutation, line 52 at r2 (raw file):

mutate
del-range f g

Can we drop in two prev's on the iter here to prove that the range del op isn't yet visible?

testdata/indexed_batch_mutation, line 72 at r2 (raw file):

should error

We don't expect an error do we? Just that the two previous ops aren't yet visible.

Optimizing away SetOptions is also used in the underlying pebble.Iterator to optimize consecutive Seeks.
This is used in trySeekUsingNext optimization which is selectively ignored by parts of the iterator stack that know they are mutable, and not ignored by sstables. For example, batchIter.SeekGE has the following comment

	// Ignore trySeekUsingNext since the batch may have changed, so using Next
	// would be incorrect.

This is helpful in that most of the data when working with a pebble.Iterator over a batch is not in the mutable part.
We should preserve such optimizations. If we don't want the refresh to be implicit via an absolute positioning operation, we can add a RefreshIfMutable that can be passed down the InternalIterator stack.

Reviewable status: 1 of 8 files reviewed, 3 unresolved discussions (waiting on @erikgrinaker, @jbowens, and @nicktrav)

Optimizing away SetOptions is also used in the underlying pebble.Iterator to optimize consecutive Seeks.

Can you remind me why we can't compare old and new bounds in SetBounds/SetOptions to determine whether they've changed? If we could do that and move the bounds-change noop optimization into Pebble and not require a separate method in the public interface.

we can add a RefreshIfMutable that can be passed down the InternalIterator stack.

I think we would need to remove the optimization that empty point/rangedel/rangekey batch iterators are omitted from the iterator stack altogether, but that seems alright.

Reviewable status: 1 of 8 files reviewed, 3 unresolved discussions (waiting on @erikgrinaker, @jbowens, and @nicktrav)

We moved the noop optimization from Pebble up to CockroachDB since we can't correctly make the noop choice in Pebble since the slices may start getting mutated from under the internal iterators. The following pair of PRs made that change #1073 cockroachdb/cockroach#61194

Reviewable status: 1 of 8 files reviewed, 3 unresolved discussions (waiting on @erikgrinaker, @jbowens, and @nicktrav)

Reviewed 1 of 7 files at r3, 14 of 15 files at r4, 1 of 1 files at r5, all commit messages.
Reviewable status: all files reviewed, 10 unresolved discussions (waiting on @erikgrinaker and @jbowens)

batch.go, line 842 at r5 (raw file):

		return newErrorKeyspanIter(ErrNotIndexed), func() {}
	}
	iter := new(keyspan.Iter)

Can you add a code comment stating that we create an iterator even if rangeDelIndex is nil, since it is allowed to refresh later, so we need the "container" to exist.

batch.go, line 843 at r5 (raw file):

	}
	iter := new(keyspan.Iter)
	refresh = func() { b.initRangeDelIter(iter) }

Can there be a fast-path if b.tombstones has not changed? By tracking the count of elements in the b.rangeDelIndex?
A code comment about a future optimization is fine.

db.go, line 962 at r5 (raw file):

	if dbi.batch != nil && dbi.batch.nextSeqNum() != dbi.batchSeqNum {
		dbi.batchSeqNum = dbi.batch.nextSeqNum()
		if dbi.batchRefreshPointKeys != nil {

when will these funcs be nil despite dbi.batch != nil?

iterator.go, line 1881 at r5 (raw file):

// The iterator will always be invalidated and must be repositioned with a call
// to SeekGE, SeekPrefixGE, SeekLT, First, or Last.
func (i *Iterator) RefreshBatchSnapshot() {

So CockroachDB reusing an Iterator will need to call this since it can not rely on absolute positioning calls alone and because SetOptions can be elided by it, yes?

testdata/indexed_batch_mutation, line 76 at r5 (raw file):

bar: (bar, .)

# Write a range key del and a point key.

range key set?

testdata/indexed_batch_mutation, line 123 at r5 (raw file):

a: (., [a-c) @1=boop)
.

nice!

testdata/rangekeys, line 177 at r5 (raw file):

set-options
seek-ge b
next

what is this trying to test?

However, this must be significantly cheaper than SetOptions(), otherwise there's no point in omitting the call.

This will be tricky. If any of the batch's internal iterators (1 for rangedels, 1 for rangekeys, 1 for points) go from empty to non-empty, we'll need to reconstruct the whole iterator stack.

I see. We'll need to run some benchmarks to determine the impact on various workloads. It doesn't affect the CRDB read-path in any case -- not only because there are no mutations, but also because it doesn't use a batch at all.

We moved the noop optimization from Pebble up to CockroachDB since we can't correctly make the noop choice in Pebble since the slices may start getting mutated from under the internal iterators.

I don't really understand why we can't do this in Pebble either. The current CRDB optimization copies the given bounds, so we're already paying that cost. If we copy the bounds inside Pebble instead then we don't have to worry about what the caller is doing to them afterwards.

Reviewable status: all files reviewed, 10 unresolved discussions (waiting on @jbowens)

We moved the noop optimization from Pebble up to CockroachDB since we can't correctly make the noop choice in Pebble since the slices may start getting mutated from under the internal iterators.

I don't really understand why we can't do this in Pebble either. The current CRDB optimization copies the given bounds, so we're already paying that cost. If we copy the bounds inside Pebble instead then we don't have to worry about what the caller is doing to them afterwards.

Hm, I guess this might be to avoid allocations: pebble.Iterator.Clone() doesn't deep-copy the bounds, so we'd need to put the dual bound buffers into the pebble.iterAlloc pool or some such to reuse the allocations, similarly to what pebbleIterator does. I do think it might be worthwhile to move this down though, to avoid the coupling and complexity.

Reviewable status: all files reviewed, 10 unresolved discussions (waiting on @jbowens)

I think the addition of the zero byte would require us to perform two copies, one to synthesize the new bound with a nul terminator, and one within Pebble to copy the bound. Or the interface would need to be complicated to avoid the second copy.

Hm, that's slightly annoying. It isn't clear to me why we can't let Pebble do the options comparisons inside SetOptions() with the current semantics though. I.e. CRDB keeps doing the dual buffer shuffle, but unconditionally calls SetOptions(). As long as Pebble unconditionally switches the internal byte buffers to the ones given by the caller, but otherwise keeps as much internal state as possible when the contents of the old/new buffers don't change, that should give us these benefits without the additional copy, no?

Reviewable status: 12 of 16 files reviewed, 7 unresolved discussions (waiting on @jbowens and @sumeerbhola)

As long as Pebble unconditionally switches the internal byte buffers to the ones given by the caller, but otherwise keeps as much internal state as possible when the contents of the old/new buffers don't change, that should give us these benefits without the additional copy, no?

Yeah, that's a good point. Pebble's internal iterators have their own SetBounds methods that need to record the new buffer pointers and sometimes clear state to invalidate themselves. We could add a flag to this internal SetBounds method indicating whether the logical bounds changed or just the buffer holding the bounds. If the bounds are logically equivalent, we omit the invalidation. I don't see any reason why that wouldn't work.

Reviewable status: 12 of 16 files reviewed, 7 unresolved discussions (waiting on @jbowens and @sumeerbhola)

Had a look at this again on a branch using this PR and unconditionally calling SetOptions in CRDB (which should refresh the batch view). Branch here:

cockroachdb/cockroach@mvcc-range-tombstones...erikgrinaker:mvcc-range-tombstones-primitives-setoptions

TestEngineConsistentIterators tests what I believe are the correct semantics, but it fails in a couple of ways. This is all from the MVCCIterator point of view.

• An existing batch iterator sees new batch writes, i.e. iterOldsees a3 here:

  https://github.com/cockroachdb/cockroach/blob/b90605ec68c933523bc3ccfda7ecfeac3f0454e5/pkg/storage/engine_test.go#L1829

• A new batch iterator sees new engine range key writes from after the batch (and thus cloned iterator) was created, i.e. iterOwn sees bc2 here:

  https://github.com/cockroachdb/cockroach/blob/b90605ec68c933523bc3ccfda7ecfeac3f0454e5/pkg/storage/engine_test.go#L1845

Hope that gives you something to go by.

Reviewable status: 6 of 16 files reviewed, 7 unresolved discussions (waiting on @jbowens and @sumeerbhola)

@sumeerbhola — do you mind giving this another review? I made some material changes, including preserving the same view of the batch across a Clone which I think is more inline with the spirit of Clone. Also, I replaced the refresh closures with direct access to the batchIter and keyspan.Iters.

An existing batch iterator sees new batch writes, i.e. iterOld sees a3 here:

Thanks, this is fixed.

A new batch iterator sees new engine range key writes from after the batch (and thus cloned iterator) was created, i.e. iterOwn sees bc2 here:

This one I think is expected as long as SetOptions refreshes the view of the batch. The new iterator is created by calling Clone and thenSetOptions, which refreshes the batch view.

Reviewable status: 0 of 16 files reviewed, 7 unresolved discussions (waiting on @jbowens and @sumeerbhola)

This one I think is expected as long as SetOptions refreshes the view of the batch. The new iterator is created by calling Clone and thenSetOptions, which refreshes the batch view.

It's supposed to refresh the batch view, but not the engine view. This breaks the ConsistentIterators() contract in CRDB.

Reviewable status: 0 of 16 files reviewed, 7 unresolved discussions (waiting on @jbowens and @sumeerbhola)

Sorry I misunderstood. The second commit contains a fix for the bug that allowed an iterator to see committed range keys at sequence numbers higher than the iterator's sequence number if there was an overlapping range key in the indexed batch.

Reviewable status: 0 of 19 files reviewed, 7 unresolved discussions (waiting on @jbowens, @nicktrav, and @sumeerbhola)

Sorry I misunderstood. The second commit contains a fix for the bug that allowed an iterator to see committed range keys at sequence numbers higher than the iterator's sequence number if there was an overlapping range key in the indexed batch.

Thanks! Can confirm that this PR has the correct semantics both for point keys and range keys.

Reviewable status: 0 of 19 files reviewed, 7 unresolved discussions (waiting on @jbowens, @nicktrav, and @sumeerbhola)

Reviewed 1 of 4 files at r6, 1 of 8 files at r7, 1 of 4 files at r8, 11 of 13 files at r9, 1 of 2 files at r10, 4 of 4 files at r11.
Reviewable status: all files reviewed (commit messages unreviewed), 11 unresolved discussions (waiting on @jbowens and @sumeerbhola)

iterator.go line 210 at r11 (raw file):

	batchPointIter    batchIter
	batchRangeDelIter keyspan.Iter
	batchRangeKeyIter keyspan.Iter

I like this explicitness instead of the closure.

internal/keyspan/span.go line 146 at r11 (raw file):

	// ordered by sequence number, so ordinarily we can return the trailing
	// subslice containing keys with sequence numbers less than `seqNum`.
	// However, if batch keys are present, they must always be visible. This can

I am assuming batch keys are "always visible", even if the iterator has not refreshed its view of the batch using SetOptions, because our implementation of range keys/deletes for a batch iterator is structurally constructing the fragmented keys and using those, so future mutations are automatically excluded. Is my understanding correct? Which is why we don't use to pass batchIter.snapshot as a parameter too.
Maybe a code comment would be useful.

internal/keyspan/span.go line 170 at r11 (raw file):

	switch {
	case lastNonVisibleIdx == -1:
		// All keys are visible.

Can you add to this comment that v represents visible and h is hidden.

testdata/indexed_batch_mutation line 168 at r11 (raw file):

.

# Clone i1 to create i2.

clone semantics make sense.
and these newly added test cases are nice.

TFTR!

Reviewable status: 18 of 19 files reviewed, 11 unresolved discussions (waiting on @jbowens and @sumeerbhola)

internal/keyspan/span.go line 146 at r11 (raw file):

Yeah, that's right. Added a comment.

internal/keyspan/span.go line 170 at r11 (raw file):

Done.