We currently expose two main MVCC methods for deleting key spans, i.e. [key0, key1):

• MVCCDeleteRange: iterates over visible keys and writes an MVCC tombstone for each one, in O(n).
• Writer.ClearMVCCRangeAndIntents: removes all MVCC keys and versions via Pebble.DeleteRange, without any MVCC record, in <O(n).

However, for reasons outlined in #69380, we need a MVCC-compliant mechanism to delete a key span in < O(n). By this, we mean a mechanism that leaves an MVCC record of the range deletion and allows readers to read before it using an appropriate timestamp. To satisfy this, we will implement MVCC range tombstones, written either in MVCCDeleteRange() or as a separate method.

• Primitives (data structures, mutation, iteration)
• MVCC stats (both for garbage below and the tombstones themselves, with full-range fast path)
• Conflict handling (WriteTooOld, collisions, uncertainty, etc)
• Scans and gets (point tombstone synthesis, GC threshold)
• MVCC iterator validity/error checking
• Benchmarks

For more details, see the (currently internal) design document and tech note.

Epic CRDB-2624

Jira issue: CRDB-10062