db: tombstone density compaction picking is O(n log(n))

[jbowens]

Picking a tombstone density compaction is likely too expensive in LSMs with high sstable counts. For every level, we traverse over all n sstables and for any eligible sstables search the lower level for overlaps:

pebble/compaction_picker.go

Lines 1528 to 1553 in 3ec779d

	for l := numLevels - 2; l >= 0; l-- {
	iter := p.vers.Levels[l].Iter()
	for f := iter.First(); f != nil; f = iter.Next() {
	if f.IsCompacting() || !f.StatsValid() || f.Size == 0 {
	continue
	}
	if f.Stats.TombstoneDenseBlocksRatio < p.opts.Experimental.TombstoneDenseCompactionThreshold {
	continue
	}
	overlaps := p.vers.Overlaps(lastNonEmptyLevel, f.UserKeyBounds())
	if float64(overlaps.SizeSum())/float64(f.Size) > maxOverlappingRatio {
	continue
	}
	if candidate == nil || candidate.Stats.TombstoneDenseBlocksRatio < f.Stats.TombstoneDenseBlocksRatio {
	candidate = f
	level = l
	}
	}
	// We prefer lower level (ie. L5) candidates over higher level (ie. L4) ones.
	if candidate != nil {
	break
	}
	if !p.vers.Levels[l].Empty() {
	lastNonEmptyLevel = l
	}
	}

We did this to enable a write-amp calculation based on overlap in fcb941e There's likely an algorithmic improvement we can make.

Jira issue: PEBBLE-309