Trigger policy: when should maintenance fire?

When should maintenance fire, and why is the best interval a square root?

Three kinds of trigger exist:

Threshold-based: file count above a limit, bytes written since the last run, fraction of rows deleted.
Cost-based: run when the estimated read savings are larger than the rewrite cost.
Scheduled: every night, every hour.

The cost-based reasoning has a clean answer. Let C be the cost of one rewrite, and r the rate at which degradation grows (the extra read cost per unit of time that adds up for every unit of time since the last rewrite). If you run maintenance every T time units:

rewrite cost per unit of time = C / T
average extra read cost per unit of time = r · T / 2 (the extra cost grows from 0 up to r·T, so the average is half)

total cost per unit of time = C / T + r · T / 2, which is smallest at T = √(2C / r).

RelationshipThe square-root rule →

\frac{C}{T} + \frac{r T}{2}, T^{*} = \frac{2 C}{r}

T (interval): $x$ — how long you wait (or how much you gather) before paying the fixed cost
C (one rewrite): $b$ — cost paid once per interval (a rewrite, an fsync)
r/2 (degradation): $a$ — cost per unit of interval that accumulates while you wait (reads slowed by deltas, time spent waiting)

Stated in 6 places →Principle: Fixed cost per operation →

This formula has the same shape as the economic order quantity (how much stock to order at a time), as the best checkpoint interval for a database, and as batch sizing. The right compaction cadence scales with the square root of the write rate. That is why "compact constantly" and "compact nightly" are never right.