The metamorphic tests fail on this branch because compactions currently depend on total key stability of spans surfaced by MergingIter, which this does not implement. I'm going to dig a little deeper for an alternative structure that avoids any copying at all. I believe it's possible, it's just more work to step the heap correctly.

Reviewable status: 0 of 6 files reviewed, all discussions resolved

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

internal/keyspan/merging_iter.go, line 78 at r2 (raw file):

// Each level (i0, i1, ...) has a user-provided input FragmentIterator. The
// merging iterator steps through individual boundaries of the underlying
// fspans separately. If the underlying FragmentIterator has fragments

typo: "fspans"

internal/keyspan/merging_iter.go, line 581 at r2 (raw file):

		// boundary, then we need to copy the start key before advancing the
		// underlying iterator to the next Span.
		if m.heap.items[0].boundKey.kind == boundKindFragmentEnd {

nit: could use m.start here instead? Same comment for the reverse iteration case.

internal/keyspan/merging_iter.go, line 582 at r2 (raw file):

		// underlying iterator to the next Span.
		if m.heap.items[0].boundKey.kind == boundKindFragmentEnd {
			m.buf = append(m.buf[:0], m.start...)

I wonder if this is going to end up showing up as a hotspot in the benchmarking. I don't have any good suggestions - maybe it's just unavoidable :/

edit: I just saw your comment about the tests failing. Disregard.

internal/keyspan/iter_test.go, line 102 at r2 (raw file):

// zeroed by sbubsequent iterator positioning calls. This is intended to help
// surface bugs in improper lifetime expectations of Spans.
type invalidatingIter struct {

Nice.

We're in a bit of an awkward pickle right now. Compactions requires total key stability of spans and their keys for range deletions. We should eventually be able to lift that requirement, but not until 23.1. User iteration only requires key stability until the next op.

I added an awkward hack to make this behavior configurable by passing a KeyStability enum for now, but I'm open to alternatives.

Reviewable status: 4 of 12 files reviewed, 2 unresolved discussions (waiting on @nicktrav)

internal/keyspan/merging_iter.go, line 581 at r2 (raw file):

m.start is just the byte slice without access to the kind

internal/keyspan/merging_iter.go, line 582 at r2 (raw file):

Unfortunately, that didn't pan out and this seems unavoidable. I'm not too worried about this particular key-copy right now, because we already perform a bunch of key copies across the range key iterator stack (eg, defragmenting iter, saving range keys in Iterator.saveRangeKey, etc). I think it will likely be helpful to remove as many of them as we reasonably can.

The metamorphic tests fail on this branch because compactions currently depend on total key stability of spans surfaced by MergingIter, which this does not implement.

Just to make sure I'm understanding this part - prior to this change, there is no mutation of keys slices, as we're not wrapping an iterator that mutates slices for keys (the defragmenting iter reuses slices, and that's where things are getting fouled up). However, if we make the change here to reuse slices in the merging iter to solve the issue in #1663, we're just pushing that instability up into this iter, which will then foul up things elsewhere that rely on stability for the duration the iterator's lifetime. A pickle indeed! Hopefully I got that right.

A thought - given that the contract of the FragmentIter is stated as:

// A Span returned by a FragmentIterator is only valid until the next
// positioning method. Some implementations (eg, keyspan.Iter) may provide
// longer lifetimes but implementations need only guarantee stability until the
// next positioning method.

I wonder if an alternative would be to adapt the call sites where we use keys returned by a FragmentIter and rely on longer lifetimes to do the key copies, as they are the one's asking for a "stronger guarantee"? I think that would prevent having to worry about lugging around the KeyStability.

The other advantage to inverting the dependency is that those call sites are, iiuc, limited only to situations where we're handling range dels catering for the pre-split user keys scenario (i.e. range keys will not have this issue)? And this situation should clean up nicely for range dels in 23.1, as you mention.

Thoughts?

Reviewed 8 of 8 files at r3, all commit messages.
Reviewable status: complete! all files reviewed, all discussions resolved (waiting on @jbowens)

internal/keyspan/merging_iter.go, line 581 at r2 (raw file):

Woops. Mistook key and kind.

Yeah, that's right, and placing the burden on the caller is okay by me. We should make sure we benchmark range deletions (and range keys) in compactions before 22.2 release, and finish off the TODO to prevent the clone if necessary.

Reviewable status: 3 of 14 files reviewed, all discussions resolved (waiting on @nicktrav)

Nice. This feels like a decent compromise for now.

Reviewed 11 of 11 files at r5, all commit messages.
Reviewable status: complete! all files reviewed, all discussions resolved (waiting on @jbowens)

TFTR!

Reviewable status: complete! all files reviewed, all discussions resolved (waiting on @jbowens)