---
title: 'Segment Merging'
source: 'https://academia.sh/en/courses/search-engines/segment-merging'
course: 'Search Engines and Text Retrieval'
language: en
updated: '2026-08-23T07:00:51+00:00'
license: 'CC BY-SA 4.0'
---

# Segment Merging

The cost every batch's leftover segments charge a query: how segment count affects dictionary lookups, scanned postings, and index size, clearing delete markers, the bytes a merge copies, and comparing two factor settings of the tiered merge policy.

Bulk indexing raised write throughput: documents entered the index in batches, not one at a
time. That gain has a quiet byproduct. Every batch leaves a new **segment** in the index: a
unit with its own dictionary, its own posting lists, and its own document count, never
changed again once written. Because a segment is immutable, a deleted document does not
move; it only receives a **delete marker** and keeps sitting there.

After forty-six batches the index is forty-six separate segments, and every query has to
search each one individually. This lesson has two questions. What exactly does segment count
charge a query, and how much of that does a background **merge** claw back, at what cost in
copied bytes.

## Setting Up the Segment Stack

For this measurement, the catalog corpus, the segmented inverted index, and the merge itself
are self-written. The corpus is 12,000 book records, seed 20260731; forty batches of 300
documents enter the index, then six correction batches rewrite records already indexed and
mark their old copies deleted.

**CO10.** Because each segment is searched independently, scoring uses that segment's own
document count and document frequency. This is how a real segmented index behaves: a global
statistic only emerges once segments merge.

**CO11.** A segment's on-disk size is its dictionary and posting lists serialized as text. A
real implementation compresses this; the ratio changes, the direction of the measurement
does not.

**CO12.** A merge's cost is the sum of the input bytes read and the output bytes written.

```js
// corpus.mjs — seeded catalog corpus, segmented inverted index, and tiered merging
export function rng(seed) {                  // deterministic pseudo-random generator
  let a = seed >>> 0;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

const ADJ = 'silent distant broken lost white black thin deep yellow long late final old new lonely'.split(' ');
const NOUN = 'door sea road house city garden island notebook river well clock forest bridge tower spring'.split(' ');
const TOPIC = ['juvenile fiction', 'short story', 'novel', 'essay', 'poetry', 'history', 'geography',
  'philosophy', 'psychology', 'economics', 'architecture', 'music', 'cinema', 'travel', 'biography',
  'memoir', 'science fiction', 'mystery', 'folklore', 'linguistics'];
const ROOT = ('book author narrative story child city memory journey generation war migration family ' +
  'sea winter morning letter photograph train street school library wind silence hope island rain ' +
  'forest village mountain river border century woman soldier teacher doctor painter song verse cover edition').split(' ');
const FIRST = 'Adam Zoe Matthew Ella Cole Alice Martin Sylvia Kyle Dean Nadia Owen'.split(' ');
const LAST = 'Miller Steel Stone Frost Hawke Bright Turner Lyon Fowler Cole'.split(' ');

function form(root, i) {                      // surface form: eight suffix variants
  const SUF = ['', 's', "'s", 'less', 'like', 'ish', 'ward', 'ful'];
  return root + SUF[i];
}

export function corpusBuild(count, seed) {    // library catalog book record
  const r = rng(seed), list = [];
  for (let i = 0; i < count; i++) {
    const summary = [];
    for (let j = 0; j < 16; j++)              // frequent roots occur more often: skewed pick
      summary.push(form(ROOT[Math.floor(r() ** 2 * ROOT.length)], Math.floor(r() ** 2 * 8)));
    const topics = [TOPIC[Math.floor(r() * 20)]];
    if (r() < 0.45) topics.push(TOPIC[Math.floor(r() * 20)]);
    list.push({
      id: 'k' + String(i).padStart(5, '0'), summary: summary.join(' '), topics,
      title: `${ADJ[Math.floor(r() * 15)]} ${NOUN[Math.floor(r() * 15)]}`,
      author: `${FIRST[Math.floor(r() * 12)]} ${LAST[Math.floor(r() * 10)]}`,
      year: 1990 + Math.floor(r() * 35),
      shelf: 'pl' + (100 + Math.floor(r() * 900)) + '.' + (1 + Math.floor(r() * 40)),
    });
  }
  return list;
}

export const text = (b) => `${b.title} ${b.summary} ${b.topics.join(' ')} ${b.author} ${b.year} ${b.shelf}`;
export const tokenize = (s) =>                // lowercase, split on non-letter/non-number
  s.toLocaleLowerCase('en').split(/[^\p{L}\p{N}]+/u).filter((t) => t.length > 1);

export class Segment {                        // an immutable segment born from one batch
  constructor(docs) {
    this.dict = new Map();                    // term -> [[document id, term frequency], ...]
    this.docs = new Set();
    this.deleted = new Set();
    for (const b of docs) {
      this.docs.add(b.id);
      const count = new Map();
      for (const t of tokenize(text(b))) count.set(t, (count.get(t) || 0) + 1);
      for (const [t, tf] of count) {
        if (!this.dict.has(t)) this.dict.set(t, []);
        this.dict.get(t).push([b.id, tf]);
      }
    }
  }
  serialize() {                               // the form written to disk: dictionary + posting lists
    let s = '';
    for (const [t, g] of this.dict) s += t + '\t' + g.map(([i, f]) => i + ':' + f).join(' ') + '\n';
    for (const id of this.deleted) s += '-\t' + id + '\n';
    return s;
  }
  get bytes() { return Buffer.byteLength(this.serialize()); }
}

// search over segments: each segment is searched separately, scores come from the segment's own statistics
export function search(segments, terms, k = 10) {
  const scores = new Map();
  let lookups = 0, scanned = 0, dropped = 0;
  for (const sg of segments) {
    const N = sg.docs.size;                   // a deleted document still counts in the segment's statistics
    for (const t of terms) {
      lookups++;
      const g = sg.dict.get(t);
      if (!g) continue;
      const idf = Math.log(1 + N / g.length);
      for (const [id, tf] of g) {
        scanned++;
        if (sg.deleted.has(id)) { dropped++; continue; }
        scores.set(id, (scores.get(id) || 0) + tf * idf);
      }
    }
  }
  const order = [...scores].sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1));
  return { top: order.slice(0, k).map(([id]) => id), matched: order.length, lookups, scanned, dropped };
}

export function merge(segments) {             // drops deleted documents, reduces to one segment
  const out = new Segment([]);
  for (const sg of segments) {
    for (const id of sg.docs) if (!sg.deleted.has(id)) out.docs.add(id);
    for (const [t, g] of sg.dict) {
      const kept = g.filter(([id]) => !sg.deleted.has(id));
      if (kept.length === 0) continue;
      if (!out.dict.has(t)) out.dict.set(t, []);
      for (const p of kept) out.dict.get(t).push(p);
    }
  }
  return out;
}

// tiered policy: once `factor` segments accumulate in the same tier, they all merge into the tier above
export function buildTiers(factor, count = 12000, seed = 20260731) {
  const corpus = corpusBuild(count, seed);
  const tier = [], location = new Map();
  let copied = 0, merges = 0, totalSegments = 0, batches = 0;
  const total = () => tier.reduce((n, t) => n + t.length, 0);
  const place = (b, k) => {
    while (tier.length <= k) tier.push([]);
    tier[k].push(b);
    if (tier[k].length < factor) return;
    const group = tier[k].splice(0, factor), merged = merge(group);
    for (const g of group) copied += g.bytes;         // read
    copied += merged.bytes;                           // written
    merges++;
    for (const id of merged.docs) location.set(id, merged);
    place(merged, k + 1);
  };
  const add = (docs) => {
    const b = new Segment(docs);
    for (const id of b.docs) location.set(id, b);
    place(b, 0);
    totalSegments += total(); batches++;
  };
  for (let i = 0; i < count; i += 300) add(corpus.slice(i, i + 300));
  const r = rng(907);
  for (let p = 0; p < 6; p++) {                // correction batch: a record is reindexed
    const correction = [];
    while (correction.length < 300) {
      const b = corpus[Math.floor(r() * count)], old = location.get(b.id);
      if (!old || old.deleted.has(b.id)) continue;
      old.deleted.add(b.id);                   // the old copy is marked deleted
      correction.push(b);
    }
    add(correction);
  }
  return { corpus, segments: tier.flat(), copied, merges, average: totalSegments / batches };
}
```

## What Segment Count Charges a Query

The same stack is searched under three placements: forty-six unmerged segments, reduced to
five segments, and a single segment. Five catalog questions run; each placement counts
dictionary lookups, scanned postings, postings dropped for a delete marker, and matched
documents. The top ten result is then compared against the single-segment placement.

```js
// segments.mjs — the effect of segment count on query cost, the set, and the order
import { search, merge, buildTiers } from './corpus.mjs';

const QUERIES = [
  ['juvenile', 'fiction', 'short', 'story'], ['lost', 'door'],
  ['library', 'memory', 'journey'], ['sea', 'island', 'rain'], ['mystery', 'city'],
];
const { segments } = buildTiers(Infinity);    // Infinity: no merging happens
const group = (sg, n) => {                    // reduces consecutive segments to n groups
  const step = Math.ceil(sg.length / n), c = [];
  for (let i = 0; i < sg.length; i += step) c.push(merge(sg.slice(i, i + step)));
  return c;
};
const placements = [['no merging', segments], ['five segments', group(segments, 5)],
  ['one segment', group(segments, 1)]];

console.log('corpus: 12000 documents, seed 20260731 | 300-document x 40 batches + 6 correction batches');
console.log('placement       segments  dict entries  index bytes  lookups  scanned  dropped  matched');
const topResults = new Map();
for (const [name, sg] of placements) {
  let dict = 0, bytes = 0, lk = 0, sc = 0, dr = 0, ma = 0;
  for (const s of sg) { dict += s.dict.size; bytes += s.bytes; }
  const top = [];
  for (const q of QUERIES) {
    const c = search(sg, q);
    lk += c.lookups; sc += c.scanned; dr += c.dropped; ma += c.matched; top.push(c.top);
  }
  topResults.set(name, top);
  console.log(name.padEnd(15), String(sg.length).padStart(5), String(dict).padStart(13),
    String(bytes).padStart(11), String(lk).padStart(15), String(sc).padStart(8),
    String(dr).padStart(7), String(ma).padStart(8));
}

console.log('\ntop ten result, relative to the one-segment placement (5 queries, 50 ranks)');
console.log('placement       dropped from top 10  rank shifted  queries with a different first result');
const reference = topResults.get('one segment');
for (const [name, top] of topResults) {
  let dropped = 0, shifted = 0, first = 0;
  for (let q = 0; q < QUERIES.length; q++) {
    const t = reference[q], y = top[q];
    for (const id of t) if (!y.includes(id)) dropped++;
    for (let i = 0; i < t.length; i++) if (y[i] !== t[i]) shifted++;
    if (y[0] !== t[0]) first++;
  }
  console.log(name.padEnd(15), String(dropped).padStart(20), String(shifted).padStart(13),
    String(first).padStart(37));
}
```

```
corpus: 12000 documents, seed 20260731 | 300-document x 40 batches + 6 correction batches
placement       segments  dict entries  index bytes  lookups  scanned  dropped  matched
no merging         46         31075     3111596             644    28767    3768    20637
five segments       5          6238     2532371              70    24999       0    20637
one segment         1          1320     2498875              14    24999       0    20637

top ten result, relative to the one-segment placement (5 queries, 50 ranks)
placement       dropped from top 10  rank shifted  queries with a different first result
no merging                        15            33                                     1
five segments                     12            29                                     1
one segment                        0             0                                     0
```

The first column is the source of both numbers. The corpus has 1,320 distinct terms; spread
across forty-six segments, the dictionary holds 31,075 entries. The same term is rewritten
in every segment, because each segment must be searchable on its own. This is the main
reason index size climbs from 2,498,875 bytes to 3,111,596 bytes: roughly a quarter more
space for the same data.

There are two separate costs on the query side. Dictionary lookups grow linearly with
segment count: the fourteen-term query set does 14 lookups at one segment and 644 at
forty-six. This is a fixed cost paid per lookup, and it is paid even when the posting list
comes back empty. Scanned postings, in turn, rise from 24,999 to 28,767; the 3,768-entry gap
is records whose old, delete-marked copies still sit in the posting lists. They are scanned,
dropped before scoring, and still force the scan to do its work.

The last column shows the most important side of the decision: matched documents come out
at **20,637 in all three placements**. Segment count does not change the returned set;
because delete-marked copies are filtered out, the answer is the same answer. What changes
is the order. In the forty-six-segment placement, 33 of the top ten result's fifty ranks
carry a document different from the single-segment placement, and 15 documents drop out of
the top ten entirely. The reason is CO10: each segment computes inverse document frequency
by looking only at its own 300 documents, so the same term looks rare in one segment and
ordinary in another. Merging down to five segments narrows this distortion — 12 documents
drop out instead of 15, and 29 ranks shift instead of 33 — but does not remove it. A global
statistic only emerges once every segment collapses into one; merging does not correct the
order gradually, it corrects it once it crosses that threshold.

## Two Settings of the Merge Policy

The merge decision is not made by hand; a policy runs continuously. The **tiered policy**
places segments into tiers by size: once `factor` segments accumulate in the same tier, all
of them merge into a single segment, and the result lands in the tier above. Factor is the
only setting. The same forty-six batches are replayed under two factors.

```js
// policy.mjs — two settings of the tiered merge policy: factor 3 and factor 10
import { search, buildTiers } from './corpus.mjs';

const QUERIES = [
  ['juvenile', 'fiction', 'short', 'story'], ['lost', 'door'],
  ['library', 'memory', 'journey'], ['sea', 'island', 'rain'], ['mystery', 'city'],
];
console.log('same 46 batches, same seed: 12000 documents, seed 20260731');
console.log('factor  merges  bytes copied  avg. segments  final segments  index bytes  lookups  scanned');

for (const factor of [3, 10]) {
  const y = buildTiers(factor);
  let bytes = 0, lk = 0, sc = 0;
  for (const b of y.segments) bytes += b.bytes;
  for (const q of QUERIES) { const c = search(y.segments, q); lk += c.lookups; sc += c.scanned; }
  console.log(String(factor).padStart(6), String(y.merges).padStart(7),
    String(y.copied).padStart(13), y.average.toFixed(1).padStart(15),
    String(y.segments.length).padStart(15), String(bytes).padStart(12),
    String(lk).padStart(9), String(sc).padStart(8));
}
```

```
same 46 batches, same seed: 12000 documents, seed 20260731
factor  merges  bytes copied  avg. segments  final segments  index bytes  lookups  scanned
     3      21      15009319             3.3               4      2860909        56    28323
    10       4       5216558             6.3              10      2944442       140    28767
```

The difference between the two settings is measurable on the query side but small:
dictionary lookups fall from 140 to 56, scanned postings from 28,767 to 28,323. Index size
drops from 2,944,442 bytes to 2,860,909 bytes. The difference paid in the background,
though, is large: factor 3 runs twenty-one merges and copies 15,009,319 bytes, factor 10
runs four merges and copies 5,216,558 bytes. Turning the measurement into a ratio sharpens
the contrast. Factor 3 reads and writes 15.0 MB to end up with an index that holds 2.9 MB:
**write amplification of 5.25x**. For factor 10 the same ratio is 1.77x.

This is the real trade-off of merging. The write throughput bulk indexing gains can be
clawed back by the merge running in the background; while bytes written per batch stay low,
bytes copied can climb to several times that. Incoming batches and merging draw on the same
disk and the same channel. Lowering the factor speeds up the query a little, shrinks the
index a little, and triples the background load; the query cost's real drop happened
earlier, in the first measurement's fall from 644 to 140 — between **no merging at all** and
**merging at all**.

## Summary

- Every batch leaves one segment; because a segment is immutable, a deleted document stays
  in place and only receives a delete marker.
- At forty-six segments the dictionary holds 31,075 entries, at one segment 1,320; for the
  same data, index size falls from 3,111,596 bytes to 2,498,875 bytes.
- Segment count does not change the set (20,637 matched documents in all three placements);
  it changes the order: 33 of the top ten result's fifty ranks differ from the
  single-segment placement, because each segment computes inverse document frequency from
  its own 300 documents.
- Merging removes 3,768 delete-marked entries from the scan and drops dictionary lookups
  from 644 to 14.
- In the tiered policy, factor 3 drops dictionary lookups to 56 from factor 10's 140, but
  raises copied bytes from 5.2 MB to 15.0 MB: write amplification rises from 1.77x to 5.25x.

## Next Step

Merging controls segment count, but it does not control the index's **growth**. The 12,000
records in this measurement are a fixed catalog; in an index with a constant stream of new
records, each merge recopies an ever-larger segment, and the cost of deleting old data ties
back to that same copying. The next lesson stops treating the index as a single, endlessly
growing object: opening a new index at a fixed threshold — a **rollover** — changes how many
indexes a query must reach and how many bytes deleting old data costs. What gets measured is
rollover's effect on query scope over time, the cost gap between deleting documents in one
large index and dropping an entire index, and the memory a hot–warm–cold tier placement
holds.