Currently, there's an intricate coordination dance performed between mergingIter and levelIter in order to make range deletions work. This dance has several complexities that make it fragile and difficult to grok. The introduction of range-key masking and "truthful" block-property filters also forces us into some awkward contortions to deal with the fact that a file's point iterator and range deletion iterator may become exhausted at different times.
I suspect we could significantly clean things up by using the keyspan.InterleavingIter within the levelIter implementation. It would work something like:
If a file has range deletions, the levelIter initializes a keyspan.InterleavingIter with the file's point iterator and rangedel iterator. It configures the InterleavingIter to interleave both start and end boundaries of range deletions.
The levelIter keeps a file open until it exhausts the InterleavingIter. Since range deletions' start/end boundaries are interleaved, this ensures that we don't prematurely close the range deletion iterator during iteration. We can remove the code that manufactures "ignorable boundary keys." The interleaving iterator handles interleaving the rangedel end boundary if necessary.
The merging iterator no longer keeps a direct handle on a file's range deletion iterator. Instead, every mergingIterLevel has a getRangeDel() *keyspan.Span func that returns the range deletion covering that level's iterator's current position, if any. When a levelIter is setup, this is set to levelIter.Span which in turn calls InterelavingIter.Span.
The filteredIter interface and related tracking within the sstable iterator is removed. It's no longer necessary because range deletions are unconditionally interleaved, which ensures we never miss a range deletion due to block-property filters excluding point keys that exist beyond the smallest/largest range deletion bound.
The merging iterator iteration is adjusted to skip over range deletion boundaries that are interleaved and rise to the top of the heap, much like the existing code skips over the "ignorable boundary keys".
The mechanisms of applying range deletions also change. The mergingIterLevel no longer buffers a tombstone. It instead calls getRangeDel() which accesses the InterleavingIter's buffered tombstone instead. We remove mergingIter.init[Min,Max]RangeDelIters, because the InterleavingIter is transparently ensuring the range deletion iterators are appropriately positioned.
The memtable and indexed batch levels will also have to be adjusted to make use of a keyspan.InterleavingIter.
jbowens
commented
1 year ago
Currently, there's an intricate coordination dance performed between
mergingIterandlevelIterin order to make range deletions work. This dance has several complexities that make it fragile and difficult to grok. The introduction of range-key masking and "truthful" block-property filters also forces us into some awkward contortions to deal with the fact that a file's point iterator and range deletion iterator may become exhausted at different times.I suspect we could significantly clean things up by using the
keyspan.InterleavingIterwithin thelevelIterimplementation. It would work something like:levelIterinitializes akeyspan.InterleavingIterwith the file's point iterator and rangedel iterator. It configures theInterleavingIterto interleave both start and end boundaries of range deletions.levelIterkeeps a file open until it exhausts theInterleavingIter. Since range deletions' start/end boundaries are interleaved, this ensures that we don't prematurely close the range deletion iterator during iteration. We can remove the code that manufactures "ignorable boundary keys." The interleaving iterator handles interleaving the rangedel end boundary if necessary.mergingIterLevelhas agetRangeDel() *keyspan.Spanfunc that returns the range deletion covering that level's iterator's current position, if any. When alevelIteris setup, this is set tolevelIter.Spanwhich in turn callsInterelavingIter.Span.filteredIterinterface and related tracking within the sstable iterator is removed. It's no longer necessary because range deletions are unconditionally interleaved, which ensures we never miss a range deletion due to block-property filters excluding point keys that exist beyond the smallest/largest range deletion bound.mergingIterLevelno longer buffers a tombstone. It instead callsgetRangeDel()which accesses theInterleavingIter's buffered tombstone instead. We removemergingIter.init[Min,Max]RangeDelIters, because theInterleavingIteris transparently ensuring the range deletion iterators are appropriately positioned.The memtable and indexed batch levels will also have to be adjusted to make use of a
keyspan.InterleavingIter.Jira issue: PEBBLE-82