Mentioned in #48 (comment):

Note that CRDB also know marks any sstable containing a range deletion tombstone as requiring compaction, which will tend to result in range deletion tombstones quickly compacting down to the bottom of the LSM and thus freeing up space. Incorporating better heuristics around range deletion tombstones into compaction is worth investigating.

@ajkr and I both recall discussing this in the past and feel that something akin to the "compensated size" adjustment RocksDB performs for point deletions should be done for range tombstones. For a tombstone at Ln, we could estimate the number of bytes that tombstone covers in Ln+1 using something like RocksDB's GetApproximateSizes. This would be cheapish and would only need to be done when an sstable is created.