How does Lucene's TieredMergePolicy decide which segments to merge?

## What a merge policy is for Because Lucene segments are immutable, every flush adds a segment and every delete leaves a tombstone. Without merging, an index drifts toward thousands of small segments full of dead documents, and query latency degrades because every query pays a fixed cost per segment. A **merge policy** is the component that looks at the current segment list and decides which groups of segments should be rewritten into one. It does not perform the merge — the `MergeScheduler` runs the selected merges on background threads. ## Why tiered, not logarithmic The older `LogByteSizeMergePolicy` merged runs of *adjacent* segments in index order, which keeps documents roughly in insertion order but constrains which merges are possible. `TieredMergePolicy`, the default since Lucene 3.x, drops the adjacency requirement: it may merge any set of segments. That freedom is what lets it pick well-balanced merges and target the segments carrying the most deleted documents. ## The selection algorithm Roughly, on each invocation: 1. **Measure.** Each segment's size is taken in bytes and reduced in proportion to its deleted documents, so a segment that is half tombstones counts as roughly half its on-disk size. 2. **Floor.** Segments smaller than `floorSegmentMB` are all treated as that size. Without this, the policy would chase an unbounded number of ever-tinier tiers; flooring lumps all the small fry together so they get merged as a group. 3. **Budget.** From the total index size and `segmentsPerTier`, the policy computes how many segments the index is allowed to have. `segmentsPerTier` is the knob that trades merge work against search cost: a lower value means fewer segments and faster searches, paid for with more merging. 4. **Enumerate candidates.** Segments are sorted largest-first, and the policy slides a window over that list, considering each group of up to `maxMergeAtOnce` segments as a candidate merge. 5. **Score.** Each candidate gets a score dominated by **skew** — the ratio of the largest segment in the candidate to the total candidate size. A merge of five similarly-sized segments scores far better than one that folds four tiny segments into a huge one, because the latter rewrites a lot of bytes for very little reduction in segment count. The score is then adjusted to favour candidates that reclaim more deleted documents and, mildly, smaller total size. 6. **Cap.** Any candidate whose merged output would exceed `maxMergedSegmentBytes` (default 5 GB) is rejected or trimmed. This is why a healthy large index ends up with a number of multi-gigabyte segments rather than one enormous one. 7. **Schedule.** The best-scoring candidate is returned and the loop repeats until the index is inside its budget or nothing worthwhile is left. ## The deletes path Selection above already discounts deleted documents, but there is also an explicit rule: `deletesPctAllowed` (default 20) bounds the fraction of the whole index that may be deleted documents. When the index exceeds it, the policy schedules merges aimed at reclaiming, and since Lucene 8 it may merge a single segment on its own — rewriting one oversized, heavily-deleted segment into a clean one — even though that segment is above the normal maximum merged size. This matters because it is the mechanism that eventually cleans up a segment produced by an earlier `forceMerge`. `forceMergeDeletes()` is the manual version, driven by `forceMergeDeletesPctAllowed`: rewrite any segment whose deleted percentage exceeds the threshold, leaving segment count otherwise alone. ## Running the merges `ConcurrentMergeScheduler` executes selected merges on background threads, with `setMaxMergesAndThreads(maxMergeCount, maxThreadCount)` controlling concurrency and an auto-I/O-throttle that slows merge threads when indexing is keeping up and releases the brakes when merges fall behind. If pending merges exceed `maxMergeCount`, the scheduler deliberately stalls the indexing threads. That back-pressure is a feature — it prevents an index from accumulating an unrecoverable merge backlog — but it presents as sudden, puzzling indexing slowdowns if you do not know to look for it. ## How to reason about the knobs The practical mental model is a single tradeoff dial. `segmentsPerTier` and `maxMergeAtOnce` set how aggressively the index is compacted: lower values buy faster queries with more background I/O and write amplification; higher values buy cheaper indexing with more segments to search. `maxMergedSegmentBytes` bounds the worst-case duration and disk headroom of any one merge — raising it means fewer, larger segments but longer, riskier merges. `floorSegmentMB` decides how small a segment has to be before it is treated as noise. In most systems the correct action is to leave these alone and instead give merges enough I/O; the common real failure is not a bad policy but starved merge threads on slow storage.