Compaction as bin-packing

How much rewriting does compaction cost to reach a target file size?

Here, compaction is not the same as merging sorted runs inside an LSM-tree. The files in a table are independent of each other, and each carries min/max statistics. Compaction becomes bin-packing: choose a group of small files and rewrite them as one bigger file near the target size.

What carries over from LSM-trees is the amplification arithmetic. If each rewrite step multiplies file size by a growth factor g, then a byte is rewritten:

log_g (s_target / s_initial) times.

Larger steps mean less amplification, but they also mean a longer wait before data is compacted, and bigger jobs that clash more often with writers (Running maintenance safely). The choice between tiered and leveled compaction in an LSM-tree (merge often in small groups versus keep strictly sorted levels) is the same dial as small step versus big step here.