Updating an Index

Keeping an inverted index current as documents arrive, change and disappear. The cost of every merge strategy between never merging and always merging is derived as postings written and indexes consulted, for logarithmic merging with any number of flushes and for tiered and leveled merging with any size ratio. Immutable segments, deletion and its reclaim arithmetic, and the log-structured merge tree with its geometric component sizes proved. Worked problems count the writes of a hundred flushes, size a billion-posting index, price a deletion threshold and choose LSM-tree ratios.

Reuters-21578 arrives one story at a time at an index that can hold 10,000 postings in memory. Index construction ran that stream through two schemes. Merging the memory into one main index at every flush wrote 26.4 million postings for a final index of 725,793. Logarithmic merging wrote 4.47 million, and at times left six separate indexes for a query to consult. Are those the only two choices, and what is the least that an index must pay to stay current? They are two points on a curve. Every merge strategy buys fewer indexes per query with more postings written, and this article derives the price list.

Updating an index, also called dynamic indexing or index maintenance, is the work of keeping an inverted index correct while documents are inserted, deleted and modified, without rebuilding it from scratch. The course text treats it in one section (Manning, Raghavan, and Schütze, 2008, §4.5). The course page Index Construction proves that section's bound for logarithmic merging and simulates it. This article starts where that page stops, and its results are used by the rest of the unit Efficient Query Processing.

Here is the route. First we fix the two costs that every strategy trades, and compute them for the two extremes. Then we return to logarithmic merging and derive its exact cost for any number of flushes, under two ways of counting. Next we let the size ratio between levels be any number $r$, which gives two families, tiered and leveled merging, that join the extremes into one curve. Then we treat deletion, which immutable indexes can only record and later reclaim. Finally we meet the same design in the log-structured merge tree and prove its rule that component sizes should form a geometric progression. The article assumes Index Construction. Its numbers are computed by tools/experiments/query-processing/updating-an-index.py.

Three kinds of statement appear and are kept apart. The costs of the merge strategies, the reclaim rule and the geometric-progression theorem are proved on this page. The designs of real systems and their measured behavior are cited. The Reuters runs and the deletion simulation are experiments, reported as what those runs showed.

Two costs and two extremes

An index that accepts new documents collects their postings in memory, where a list can be extended cheaply. When memory holds $n$ postings it must be emptied to disk. We call that event a flush, number the flushes $1, 2, 3, \ldots$, and write $j$ for the number so far and $T = jn$ for the postings indexed so far. These are the symbols of Index Construction. What happens at a flush is the strategy. Two quantities measure it.

  • Postings written. Every posting written to disk, counted each time it is written, including rewrites by merges. This is the cost of updating. It does not depend on the machine.
  • Indexes consulted. The number of separate on-disk indexes that exist when a query arrives. A term's postings are spread over all of them, so a query pays for each: a dictionary lookup and at least one read per index per term, and a merge of the partial results.

Two strategies sit at the ends.

No merge. Each flush writes the memory out as a new index and touches nothing else. After $j$ flushes there are $j$ indexes, and $T$ postings have been written, once each. No strategy writes less, because every posting must reach the disk at least once. The price is $j = T/n$ indexes per query, which grows without limit.

Merge always. There is one on-disk index, and every flush rewrites it with the memory merged in. This is the auxiliary-index scheme of the course text, which Büttcher and Clarke (2008) call Immediate Merge. Flush $f$ writes $fn$ postings, so after $j$ flushes the total is

$$n\,(1 + 2 + \cdots + j) = \frac{j(j+1)}{2}\,n = \frac{T^2}{2n} + \frac{T}{2}.$$

A query consults one index, the least possible, and the writing grows with the square of the collection. Index Construction derives the same sum.

Back to Reuters. With $n = 10{,}000$ the 725,793 postings cause 72 flushes. No merge writes 0.72 million postings (the last 1,145 are still in memory) and ends with 72 indexes. Merge always writes 26.4 million, which is 36.4 times the final index, and never has more than one index. Everything else in this article lies between those two rows.

A third extreme: updating lists in place

Both extremes, and every strategy below, write new index files and never modify old ones. The alternative is to change the index where it lies. An in-place strategy leaves free space after each postings list on disk, appends new postings into it, and moves the whole list to a larger space when it runs out (Büttcher and Clarke, 2008, §2.4).

Here is the idea of its cost. If the space reserved grows in proportion to the list, a list is moved only when it has multiplied in size. The moves then add up to a constant times its final length. Suppose a list that has outgrown its space is given $g$ times its current size, for a factor $g > 1$. A list that ends with $s$ bytes was last moved when it had at most $s$ bytes, before that when it had at most $s/g$, before that at most $s/g^2$, and so on. The bytes moved are at most

$$s + \frac{s}{g} + \frac{s}{g^2} + \cdots = \frac{s}{1 - 1/g},$$

and each move reads the bytes and writes them, so the transfer is at most $2s/(1 - 1/g)$. For $g = 2$ that is $4s$. This is the bound Büttcher and Clarke give as their equation 6. It makes the total work linear in the size of the index while every list stays in one piece. Their comparison is with Immediate Merge, the merge strategy that also keeps each list in one piece, whose work is quadratic.

The count hides the cost that decides the matter in practice. Lists that have been moved are scattered over the disk in no useful order, so each update of each list is a separate random access. Büttcher and Clarke report, citing experiments by Lester, Zobel and Williams, that an in-place implementation was generally outperformed by Immediate Merge except with very small memory buffers, and they pass on the explanation given for it, the seeks. A seek costs milliseconds, which for a list of a few hundred postings is thousands of times the cost of writing the postings themselves. Their own proposal is a hybrid that keeps the few long lists in place and merges the many short ones. The lesson for this article is the one Index Construction opened with: sequential transfer is cheap and scattered access is not. The strategies below are all sequential, and the count of postings written is a fair measure for them.

Logarithmic merging, counted exactly

Logarithmic merging keeps on-disk indexes $I_0, I_1, I_2, \ldots$ of sizes $n, 2n, 4n, \ldots$, at most one of each size. A flush that finds $I_0$ absent writes the memory as $I_0$. A flush that finds $I_0$ present merges the memory with it, then merges the result with $I_1$ if that is present, and so on until it reaches an absent level. The course text gives the algorithm as its Figure 4.7. Index Construction proves three things about it, which we use without repeating the proofs:

  • after flush $f$ the indexes present are those of the 1 digits of $f$ written in binary;
  • no posting is written more than $\lfloor \log_2 j \rfloor + 1$ times in $j$ flushes;
  • when every intermediate merge result is written to disk, $2^k$ flushes write $2^k\left(k + \tfrac12\right)n$ postings in all.

Two questions are left open there. What is the total for a number of flushes that is not a power of two? And must the intermediate results be written at all?

Any number of flushes

Write $v(f)$ for the number of zeros at the end of $f$ in binary, so that $v(12) = 2$ because 12 is 1100. Flush $f$ finds exactly $I_0, \ldots, I_{v(f)-1}$ present, since those are the trailing 1 digits of $f - 1$. The course page counts the flush as it is written in the textbook's figure: each merge of the chain writes its result. We call this the cascade count. An odd flush writes $n$. A flush with $v(f) = v \ge 1$ writes $2n + 4n + \cdots + 2^v n$.

Here is the plan of the derivation: write the cost of a flush as a sum of powers of two, one for each level it passes, and then count how many flushes pass each level.

Theorem 1 (cascade count). After $j$ flushes the cascade has written

$$W_{\text{cascade}}(j) = n\left(\left\lceil \frac{j}{2} \right\rceil + \sum_{i \ge 1} 2^i \left\lfloor \frac{j}{2^i} \right\rfloor\right) \;\le\; n\left(\left\lceil \frac{j}{2} \right\rceil + j \lfloor \log_2 j \rfloor\right)$$

postings.

Proof. The cost of flush $f$, in units of $n$, is $[f \text{ odd}] + \sum_{i=1}^{v(f)} 2^i$, where the bracket is 1 for odd $f$ and 0 otherwise. For odd $f$ the sum is empty and the cost is 1. For even $f$ the bracket is 0 and the sum is $2 + 4 + \cdots + 2^{v(f)}$, as stated above. Now add over $f = 1, \ldots, j$. The brackets add up to the number of odd $f$, which is $\lceil j/2 \rceil$. The term $2^i$ appears once for every $f \le j$ with $v(f) \ge i$, that is, for every multiple of $2^i$ up to $j$, and there are $\lfloor j/2^i \rfloor$ of those. That gives the formula. For the bound, each term $2^i \lfloor j/2^i \rfloor$ is at most $j$, and the term is zero once $2^i > j$, so at most $\lfloor \log_2 j \rfloor$ terms are nonzero. $\blacksquare$

For $j = 2^k$ every floor is exact, the sum is $k \cdot 2^k$, and the total is $2^k(k + \tfrac12)n$, the course page's closed form. For Reuters, $j = 72$ gives $36 + (72 + 72 + 72 + 64 + 64 + 64) = 444$ units. The 72 flushes averaged 10,065 postings, a little more than $n$ because a flush happens after the story that fills the memory. And $444 \times 10{,}065 = 4.47$ million, the figure measured.

One pass in place of a cascade

The cascade writes more than it needs to. When flush 8 finds $I_0$, $I_1$ and $I_2$ present, the textbook's figure writes a temporary index of $2n$, reads it back to write one of $4n$, and reads that back to write $I_3$. All four inputs are sorted the same way, so one four-way merge can read the memory and the three indexes together and write $I_3$ once. This is the multi-way merge that Index Construction already uses to combine blocks. We call it the one-pass count: flush $f$ merges the memory with $I_0, \ldots, I_{v(f)-1}$ and writes only the result, of size $n + n + 2n + \cdots + 2^{v(f)-1}n = 2^{v(f)}n$.

Flush Indexes before Cascade writes One pass writes Indexes after
1 none $n$ $n$ $I_0$
2 $I_0$ $2n$ $2n$ $I_1$
3 $I_1$ $n$ $n$ $I_0, I_1$
4 $I_0, I_1$ $2n + 4n = 6n$ $4n$ $I_2$
5 $I_2$ $n$ $n$ $I_0, I_2$
6 $I_0, I_2$ $2n$ $2n$ $I_1, I_2$
7 $I_1, I_2$ $n$ $n$ $I_0, I_1, I_2$
8 $I_0, I_1, I_2$ $2n + 4n + 8n = 14n$ $8n$ $I_3$

The indexes after each flush are the same in both columns, so queries see no difference. The totals after eight flushes are $28n$ and $20n$, against $36n$ for merge always.

Theorem 2 (one-pass count). After $j$ flushes one-pass logarithmic merging has written

$$W_{\text{one}}(j) = n\left(j + \sum_{i \ge 1} 2^{i-1} \left\lfloor \frac{j}{2^i} \right\rfloor\right) \;\le\; n\,j\left(1 + \tfrac12 \lfloor \log_2 j \rfloor\right)$$

postings, and for $j = 2^k$ exactly $2^k\left(1 + \tfrac{k}{2}\right)n$.

Proof. The cost of flush $f$ in units of $n$ is $2^{v(f)} = 1 + \sum_{i=1}^{v(f)} 2^{i-1}$, because $1 + 1 + 2 + \cdots + 2^{v-1} = 2^v$. Adding over $f \le j$, the ones give $j$, and the term $2^{i-1}$ appears once for each multiple of $2^i$ up to $j$, as in Theorem 1. Each term $2^{i-1}\lfloor j/2^i \rfloor$ is at most $j/2$, and at most $\lfloor \log_2 j \rfloor$ of them are nonzero. For $j = 2^k$ the terms for $i = 1, \ldots, k$ are each $2^{k-1}$, so the total is $2^k + k\,2^{k-1} = 2^k(1 + k/2)$. $\blacksquare$

With $T = 2^k n$ postings, the one-pass average is $1 + \tfrac12 \log_2(T/n)$ writes per posting, against $\tfrac12 + \log_2(T/n)$ for the cascade. For large collections that is half. The bound on any single posting is unchanged, $\lfloor \log_2 j \rfloor + 1$ writes. The average is half the bound because a posting does not visit every level. The postings of flush $f$ go straight to level $v(f)$: half of all flushes are odd and stop at level 0, a quarter go straight to level 1, and so on.

Example (a common misstatement). "Logarithmic merging writes each posting $\log_2(T/n)$ times." That is the worst case of one posting, and it is also close to the average under the cascade count. It is twice the average of an implementation that merges each chain in one pass. On Reuters the cascade wrote 4.47 million postings, 6.2 times the final index, and the one-pass run wrote 2.78 million, 3.8 times. Theorem 2 predicts $72 + (36 + 36 + 36 + 32 + 32 + 32) = 276$ units, and $276 \times 10{,}065 = 2.78$ million.

Indexes per query

After flush $f$ the number of indexes is the number of 1 digits of $f$. How many is that on average? Over the flushes $1, \ldots, 2^k - 1$ it is exactly $k\,2^{k-1}/(2^k - 1)$, a little over $k/2$. To see it, list the numbers $0, \ldots, 2^k - 1$ in binary with $k$ digits. Each of the $k$ digit positions holds a 1 in exactly half of the $2^k$ numbers, so the list contains $k\,2^{k-1}$ ones, none of them in the number 0. Dividing by the $2^k - 1$ flushes gives the mean. The worst case is $k$, reached at flush $2^k - 1$. So a query against a logarithmically merged index of $T$ postings consults about $\tfrac12 \log_2(T/n)$ indexes on average and at most $\lfloor \log_2 (T/n) \rfloor + 1$. On Reuters the mean over the 10,788 arrivals was 2.9 and the largest number was 6.

Any size ratio: tiered and leveled merging

Logarithmic merging doubles the index size from level to level. Nothing forces the factor to be two. Let the sizes be $n, rn, r^2n, \ldots$ for a whole number $r \ge 2$, the size ratio. A level that is $r$ times the one below can be filled in two ways, and the two ways trade the two costs in opposite directions.

Tiered merging lets a level collect several indexes of the same size and merges them all at once. Level $i$ holds up to $r - 1$ indexes of size $r^i n$. A flush writes the memory as a new index of level 0, unless level 0 already holds $r - 1$. In that case the memory and the $r - 1$ indexes are merged into one index of size $rn$ for level 1. If level 1 is full as well, its indexes join the same merge, and so on, all in one pass.

Leveled merging keeps one index per level and merges each arrival into it. The index of level $i$ has size $r^i n$, $2r^i n$, up to $(r-1)r^i n$. A flush merges the memory into the index of level 0. When that makes it $rn$ long, it leaves level 0 and is merged into the index of level 1, and so on, again in one pass.

Both are logarithmic merging when $r = 2$: a level then holds one index or none, and an arrival that meets one produces an index of the next size.

Here is the idea of both analyses. The state of the index after $f$ flushes is the number $f$ written in base $r$, and a flush is adding 1 on an odometer. Write $v_r(f)$ for the number of zeros at the end of $f$ in base $r$, and $d_r(f)$ for the lowest digit of $f$ that is not zero. For $r = 4$ and $f = 12$, which is 30 in base 4, $v_4 = 1$ and $d_4 = 3$.

Theorem 3 (tiered merging). After $f$ flushes, level $i$ holds as many indexes as the $i$th digit of $f$ in base $r$. Flush $f$ writes $r^{v_r(f)}\,n$ postings, and

$$W_{\text{tiered}}(j) = n\left(j + (r-1)\sum_{i \ge 1} r^{i-1}\left\lfloor \frac{j}{r^i} \right\rfloor\right) \;\le\; n\,j\left(1 + \frac{r-1}{r}\lfloor \log_r j \rfloor\right).$$

For $j = r^k$ the total is exactly $r^k\left(1 + \frac{r-1}{r}k\right)n$. A query consults at most $(r-1)(\lfloor \log_r j \rfloor + 1)$ indexes, and no posting is written more than $\lfloor \log_r j \rfloor + 1$ times.

Proof. By induction on $f$. Before the first flush every level is empty and every digit of 0 is 0. Suppose the claim holds after flush $f - 1$, and let $v = v_r(f)$. Adding 1 to $f - 1$ turns its $v$ trailing digits from $r - 1$ to 0 and raises digit $v$ by one. So by the hypothesis, levels $0, \ldots, v - 1$ each hold $r - 1$ indexes and level $v$ holds fewer than $r - 1$. The flush therefore merges the memory with all the indexes of levels $0, \ldots, v-1$. Their sizes add up to

$$n + \sum_{i=0}^{v-1} (r-1)\,r^i\,n = n + (r^v - 1)\,n = r^v n,$$

which is the size of one index of level $v$. The flush writes it, level $v$ gains one index, and levels below $v$ are empty: the digits of $f$. That proves the state and the cost of a flush.

For the total, $r^v = 1 + (r-1)(1 + r + \cdots + r^{v-1})$, so the cost of flush $f$ is $1 + (r-1)\sum_{i=1}^{v_r(f)} r^{i-1}$ units. Adding over $f \le j$, the term $r^{i-1}$ appears for each multiple of $r^i$ up to $j$, which gives the formula. Each term $r^{i-1}\lfloor j/r^i \rfloor$ is at most $j/r$ and at most $\lfloor \log_r j \rfloor$ terms are nonzero, which gives the bound. For $j = r^k$ each of the terms $i = 1, \ldots, k$ equals $r^{k-1}$. The number of indexes is the sum of the digits of $f$, and $f \le j$ has at most $\lfloor \log_r j \rfloor + 1$ digits, each at most $r - 1$. A posting is written once when it enters a level and never again while it stays there, and it only moves up, so it is written at most once per level. $\blacksquare$

Theorem 4 (leveled merging). After $f$ flushes, level $i$ holds one index of size $d\,r^i n$ if the $i$th digit of $f$ in base $r$ is $d \ge 1$, and none if it is 0. Flush $f$ writes $d_r(f)\,r^{v_r(f)}\,n$ postings. For $j = r^k$,

$$W_{\text{leveled}}(r^k) = r^k\left(1 + \frac{r-1}{2}\,k\right)n,$$

and for every $j$, $W_{\text{leveled}}(j) \le \frac{r}{2}\,n\,j\,(\lfloor \log_r j \rfloor + 1)$. A query consults at most $\lfloor \log_r j \rfloor + 1$ indexes.

Proof. By induction on $f$. Before the first flush every level is empty and every digit of 0 is 0. Suppose the claim holds after flush $f - 1$. Adding 1 to $f - 1$ turns its trailing digits $r - 1$ into zeros and raises the next digit by one. So with $v = v_r(f)$ and $d = d_r(f)$, the last $v$ digits of $f - 1$ are $r - 1$ and its digit at position $v$ is $d - 1$. The hypothesis for $f - 1$ then says that levels $0, \ldots, v-1$ hold indexes of sizes $(r-1)r^i n$ and level $v$ holds one of size $(d-1)r^v n$, or none if $d = 1$. The memory and the levels below $v$ add up to $r^v n$ as before. Each level $i < v$ becomes full, with $r \cdot r^i n$ postings, as the merge passes it, so the chain reaches level $v$. There the result has $(d-1)r^v n + r^v n = d\,r^v n$ postings, which is less than $r^{v+1}n$ because $d \le r - 1$, so the chain stops and that index is written. The digits of $f$ are $d$ at position $v$ and 0 below it.

For $j = r^k$, count the flushes by their pair $(v, d)$. For $v < k$ and each $d$ from 1 to $r - 1$ there are $r^{k-v-1}$ numbers $f \le r^k$ with those values, namely those of the form $(m r + d)\,r^v$ with $0 \le m < r^{k-v-1}$. Their cost is

$$\sum_{d=1}^{r-1} d \cdot r^v \cdot r^{k-v-1} = \frac{r(r-1)}{2}\,r^{k-1} = \frac{r-1}{2}\,r^k$$

units for each of the $k$ values of $v$. The last flush, $f = r^k$, has $v = k$ and $d = 1$ and costs $r^k$. The total is $r^k\left(1 + \frac{r-1}{2}k\right)$ units.

For any $j$, fix $v$. The flushes $f \le j$ with $v_r(f) = v$ are the numbers $m\,r^v$ with $m \le L = \lfloor j/r^v \rfloor$ and $m$ not divisible by $r$, and their lowest digit is the remainder of $m$ on division by $r$. So their cost is $r^v$ times the sum of those remainders over $m = 1, \ldots, L$, where the multiples of $r$ contribute 0. Any $r$ consecutive values of $m$ have remainders $0, 1, \ldots, r-1$ in some order, which sum to $r(r-1)/2$, less than $r/2$ per value. A final incomplete run of $\ell < r$ values has remainders $1, \ldots, \ell$, summing to $\ell(\ell+1)/2 \le \ell\,r/2$. So the sum of remainders is at most $L\,r/2$, and the cost at level $v$ is at most $r^v \cdot (j/r^v) \cdot r/2 = jr/2$ units. There are $\lfloor \log_r j \rfloor + 1$ possible values of $v$. The number of indexes is the number of nonzero digits of $f$. $\blacksquare$

The two theorems put numbers on a plain difference. Tiered merging writes a posting once per level, and for that it keeps up to $r - 1$ indexes on each level. Leveled merging keeps one index per level, and for that it rewrites a level's index at each of the $r - 1$ arrivals it absorbs. With $T = r^k n$ postings:

Writes per posting, average Indexes per query, at most
No merge 1 $T/n$
Tiered, ratio $r$ $1 + \frac{r-1}{r}\log_r(T/n)$ $(r-1)\log_r(T/n)$
Logarithmic (either, $r = 2$) $1 + \frac12\log_2(T/n)$ $\log_2(T/n)$
Leveled, ratio $r$ $1 + \frac{r-1}{2}\log_r(T/n)$ $\log_r(T/n)$
Merge always $\frac12(T/n + 1)$ 1

The last column is the exact maximum over the flushes $1, \ldots, r^k$. For the three merging rows it is reached at flush $r^k - 1$, whose $k$ digits are all $r - 1$, and flush $r^k$ itself leaves one index. Without merging it is reached at the last flush, and merging always leaves one index after every flush. The theorems' bounds with "$+\,1$" are for an arbitrary number of flushes.

The table is one curve. Raising $r$ in the tiered family lowers the writes and raises the indexes, and a ratio larger than the number of flushes never merges at all: that is the first row. Raising $r$ in the leveled family lowers the indexes and raises the writes, and a ratio larger than the number of flushes keeps one index and rewrites it at every flush: that is the last row. Both statements follow from the flush costs of the theorems, since for $r > f$ we have $v_r(f) = 0$ and $d_r(f) = f$, so a tiered flush writes $n$ and a leveled flush writes $fn$. The script checks both against the simulated extremes for every flush up to 4,096. The two families meet at $r = 2$, which is logarithmic merging.

Writes per posting against the mean number of indexes a query consults, after 1,024 flushes, for tiered and leveled merging with size ratios from 2 to 32. Notice that the two families form one curve through logarithmic merging at ratio 2. Moving left along the leveled branch buys fewer indexes with more writing, toward merge always, which lies far above the frame at 512.5 writes. Moving right along the tiered branch buys less writing with more indexes, toward no merge, far to the right at 512.5 indexes.
Writes per posting against the mean number of indexes a query consults, after 1,024 flushes, for tiered and leveled merging with size ratios from 2 to 32. Notice that the two families form one curve through logarithmic merging at ratio 2. Moving left along the leveled branch buys fewer indexes with more writing, toward merge always, which lies far above the frame at 512.5 writes. Moving right along the tiered branch buys less writing with more indexes, toward no merge, far to the right at 512.5 indexes.

For $j = 1{,}024$ flushes the script's simulation, which performs the merges on lists of batches and counts, gives:

Strategy Writes per posting Most indexes Mean indexes
Merge always 512.5 1 1.0
Leveled, $r = 10$ 14.287 3 2.697
Leveled, $r = 4$ 8.5 5 3.751
Logarithmic, cascade count 10.5 10 5.001
Logarithmic, one pass 6.0 10 5.001
Tiered, $r = 4$ 4.75 15 7.501
Tiered, $r = 10$ 3.654 27 13.325
No merge 1 1,024 512.5

The values at $r = 4$ are the closed forms with $k = 5$: $1 + \tfrac34 \cdot 5 = 4.75$ and $1 + \tfrac32 \cdot 5 = 8.5$. One row breaks the pattern, and it is the cascade: it writes more than leveled merging with ratio 4 and can still leave twice as many indexes, 10 against 5 at the most. Writing intermediate results buys nothing.

Lester, Moffat and Zobel (2005) study strategies of this kind under the name geometric partitioning. Their abstract describes a mechanism "based on controlled partitioning that can be adapted to suit different balances of insertion and querying operations". The analysis above is this article's own and is not taken from their paper, of which only the abstract was read. The names tiered and leveled come from the literature on log-structured merge trees, treated below.

The strategies on Reuters

Back to the 10,788 stories and a memory of 10,000 postings. Real flushes are not all the same size, so the theorems apply only approximately, and the simulation is the check.

Strategy Postings written (millions) Times the final index Most indexes Mean indexes
Merge always 26.4 36.4 1 1.0
Leveled, $r = 10$ 6.02 8.3 2 1.7
Leveled, $r = 4$ 3.78 5.2 3 2.2
Logarithmic, cascade count 4.47 6.2 6 2.9
Logarithmic, one pass 2.78 3.8 6 2.9
Tiered, $r = 4$ 2.23 3.1 9 4.3
Tiered, $r = 10$ 1.36 1.9 15 7.6
No merge 0.72 1.0 72 36.0

The means are taken over the arrivals of the 10,788 stories. The unit model predicts the middle rows closely: 222 units for tiered merging with ratio 4 and 376 for leveled, which at 10,065 postings per flush are 2.23 and 3.78 million. Seventy-two flushes is a small number for ratio 10, where the collection has not yet filled its second level, and leveled merging there has spent most of its writing rebuilding one large index.

Postings written while Reuters-21578 is indexed one story at a time with room for 10,000 postings in memory, for seven strategies, and below it the number of on-disk indexes for three of them. Notice the order of the curves at the right edge of the upper panel, which is the reverse of the order of the staircases in the lower panel: the strategies that write least leave the most indexes. Merge always is off the top of the upper panel at 26.4 million.
Postings written while Reuters-21578 is indexed one story at a time with room for 10,000 postings in memory, for seven strategies, and below it the number of on-disk indexes for three of them. Notice the order of the curves at the right edge of the upper panel, which is the reverse of the order of the staircases in the lower panel: the strategies that write least leave the most indexes. Merge always is off the top of the upper panel at 26.4 million.

With five times the memory, $n = 50{,}000$, there are 14 flushes. Merge always writes 5.3 million postings, the cascade 2.1 million and one-pass logarithmic merging 1.6 million. More memory helps every strategy because it lowers $T/n$, the only quantity the costs depend on.

Which row is right depends on the ratio of updates to queries. An index that is written far more often than it is searched, such as a log store, belongs near the bottom. An index that is searched constantly and updated in a trickle belongs near the top. Büttcher and Clarke (2008) start from the top row for exactly that reason. With a high query load they require every postings list to be contiguous at all times, which among these strategies only a single index gives.

Segments, and what deletion costs

Every strategy above writes whole indexes and never changes one after it is written. Lucene calls such an index a segment, and the rest of this article uses the word. Immutability is what makes the merging cheap to run next to queries. A reader can search a fixed set of segments while a merge writes a new one, and switch to the new set when it is complete. The course page describes this for Lucene. The same property makes block-level structures practical: the skip data and block maxima of Block-Max Indexes are computed once when a segment is written and are rebuilt at the next merge, never patched.

Immutability has one direct consequence. A document cannot be removed from a segment. Deletion can only be recorded, and the record applied later.

  • The course text keeps an invalidation bit vector, one bit per document, and filters deleted documents out of results (Manning, Raghavan, and Schütze, 2008, §4.5). Index Construction works an example.
  • A modification is a deletion followed by an insertion. Lucene's documentation says the same of its own update call, which "just deletes and then adds the entire document" (Apache Software Foundation, 2025a).
  • The postings of a deleted document stay on disk until a merge rewrites their segment and leaves them out.

Between the deletion and that merge the dead postings cost space, they are read and skipped by every query that touches their lists, and they distort the statistics, as shown below. How often should the index be rewritten to get rid of them?

The reclaim rule

Here is the idea in one sentence: rewriting a segment costs its live postings and recovers its dead ones, so the cost per posting recovered is the ratio of live to dead, and waiting makes it cheaper.

The formal version. Take a single segment in a steady state: it holds $L$ live postings, and each update kills one live posting and adds a new one elsewhere, so that $L$ stays constant. Let the segment be rewritten whenever the dead postings reach a share $\delta$ of all postings in it, live and dead. If $D$ postings are dead at that moment, then $D/(L + D) = \delta$, so $D = \frac{\delta}{1-\delta}L$. The rewrite writes the $L$ live postings. It happens once every $D$ updates. Each update also writes its own new posting once. So the writes per update are

$$1 + \frac{L}{D} = 1 + \frac{1-\delta}{\delta} = \frac{1}{\delta},$$

and just before a rewrite the segment occupies $L + D = \frac{L}{1-\delta}$ postings of space.

Threshold $\delta$ Writes per update, $1/\delta$ Peak size, $1/(1-\delta)$ times the live postings
0.1 10.0 1.11
0.2 5.0 1.25
1/3 3.0 1.50
0.5 2.0 2.00

The script runs the rule on 36,000 live postings and reproduces each row exactly. A low threshold keeps the index compact and pays for it in rewriting, in inverse proportion. Lucene exposes this dial. Its TieredMergePolicy has a setting for "the maximum percentage of doc id space taken by deleted docs", whose default is 20. The documentation states the trade in the same terms: "Lower values make the index more space efficient at the expense of increased CPU and I/O activity" (Apache Software Foundation, 2025b). At 20 percent the single-segment rule gives five writes per update.

Deletion and merging together

A real index reclaims in two ways at once. Every ordinary merge drops the dead postings of the segments it reads, at no extra cost, and a threshold rule forces a rewrite when that is not enough. The following experiment combines the two. It holds 20,000 live documents of one posting each, at first in one base segment. Each update replaces a document chosen uniformly at random, the memory holds 200 documents, and flushes are merged logarithmically in one pass among themselves, leaving the base segment alone. After each flush, if the dead share of the whole on-disk index has reached $\delta$, everything is rewritten into one segment, which becomes the new base. Each run makes 50,000 updates to settle and measures the next 100,000, for seeds 1 to 30. The table gives the median over seeds. The dead share is the number of dead postings on disk divided by the number of all postings on disk, each summed over the measured updates. The interquartile ranges are under 0.01 writes and under 0.001 of dead share in every row.

Threshold $\delta$ Writes per update Single-segment rule $1/\delta$ Dead share of the index Most segments
0.1 10.68 10 0.056 4
0.2 6.20 5 0.114 5
1/3 4.84 3 0.205 6
0.5 4.09 2 0.335 7
never 3.90 0.645 10

Three things can be read from it. At a low threshold the rewrites dominate and the single-segment rule is close: 10.68 writes against 10. At a high threshold the ordinary merging dominates: the rule's 2 writes are only part of the 4.09 measured. And without any threshold the dead postings are not held in check. In the last row nothing ever rewrites the base segment, so each of its documents that is replaced leaves a dead posting for good. Nearly two thirds of the index was dead on average over the measured window, and the share was still rising: for seed 1 it was 0.639 over updates 50,001 to 100,000 and 0.701 over updates 400,001 to 450,000. Merging by size alone has the same weakness in a milder form, because logarithmic merging creates its largest index $I_k$ at flush $2^k$ and does not rewrite it until flush $2^{k+1}$, an interval that doubles each time. A merge policy for a collection with deletions needs a rule that looks at dead postings, and not only at sizes. These are observations of this simulation, with its uniform updates and one-posting documents.

What dead postings do to the statistics

Dead postings are still counted. A term's document frequency, read from the lengths of its lists, includes deleted documents, and so does the document count if it is taken from the segments. The course page notes that the statistics are approximate between merges. The size of the error can be derived.

Let the index report $N' = N + D$ documents, of which $D$ are dead, and for a term $\mathit{df}' = \mathit{df} + \mathit{dd}$, where $\mathit{dd}$ of the dead documents contained the term. The reported inverse document frequency differs from the true one by

$$\log_{10}\frac{N'}{\mathit{df}'} - \log_{10}\frac{N}{\mathit{df}} = \log_{10}\frac{1 + D/N}{1 + \mathit{dd}/\mathit{df}}.$$

The error is zero exactly when $\mathit{dd}/\mathit{df} = D/N$, that is, when the term's documents have been deleted at the same rate as documents in general. Deletion at random leaves idf nearly unchanged. Deletion that concentrates on one subject does not. If the documents containing a term are revised more often than the rest, the term's reported document frequency is inflated and its idf is too low, by the logarithm above. Worked problem 3 puts numbers on it. One remedy short of merging would be to count live documents: a segment could store each term's document frequency and correct it from the deletion bit vector, at the price of reading the lists. No system is cited here as doing so.

The log-structured merge tree

The same design appears in database systems, for a different kind of index. O'Neil, Cheng, Gawlick and O'Neil (1996) considered a table that receives inserts at a high rate, such as a history of transactions, with an index on it that must stay current. Their abstract says that a standard disk-based index such as the B-tree "will effectively double the I/O cost of the transaction" that inserts a row. Their log-structured merge tree (LSM-tree) replaces that with the pattern above: a small component $C_0$ in memory receives the inserts, and components $C_1, \ldots, C_K$ on disk, each larger than the last, receive them later in bulk. Entries move from $C_{i-1}$ to $C_i$ by what the authors call a rolling merge, which reads a run of entries from both, merges them, and writes the result back into $C_i$ in large sequential blocks.

The correspondence with a search index is direct. $C_0$ is the in-memory index of size $n$. The disk components are the levels. Each has one component, which absorbs what arrives from below, so the scheme is leveled merging in the vocabulary used here. Luo and Carey (2020), in their survey of the designs that followed, describe the original proposal as what "is often referred to as the leveling merge policy". They trace the tiering policy to a parallel proposal, the stepped-merge method, in which a level's components are merged together into one component of the next level when the level is full. The paper also handles deletion as this article has described it. A deletion places a "delete node entry" in $C_0$, which in the authors' words "migrates out to larger components during merge and annihilates the associated entry when it is encountered", and until then finds are filtered through it.

The paper's contribution that concerns us is its answer to a sizing question. Given the memory component's size and the size of the largest component, how large should the components between them be?

Geometric sizes are optimal

Here is the idea. The merge into a component costs in proportion to how many times larger that component is than the one feeding it. The product of those ratios is fixed by the two end sizes. And a sum of numbers with a fixed product is smallest when they are equal.

The formal version. Let component $C_i$ hold $S_i$ bytes, and let $r_i = S_i/S_{i-1}$ for $i = 1, \ldots, K$. Entries arrive at $C_0$ at $R$ bytes per second, and in a steady state they leave every component for the next at the same rate. A page holds $S_p$ bytes. O'Neil and colleagues count the page reads and writes per second of all the rolling merges (their equations 3.7 and 3.8). The merge from $C_{i-1}$ into $C_i$ passes over $r_i$ pages of $C_i$ for each page it takes from $C_{i-1}$. So on component $C_i$ it reads $r_i R/S_p$ pages per second and writes $(r_i + 1)R/S_p$, the extra one being the entries that arrive. The merge out of $C_i$ into $C_{i+1}$ reads a further $R/S_p$ from $C_i$, for every component but the last. Adding these over $i = 1, \ldots, K$,

$$H = \frac{R}{S_p}\Big((2r_1 + 2) + \cdots + (2r_{K-1} + 2) + (2r_K + 1)\Big) = \frac{2R}{S_p}\left(\sum_{i=1}^{K} r_i + K - \tfrac12\right).$$

Theorem 5 (O'Neil, Cheng, Gawlick and O'Neil, 1996, Theorem 3.1). For fixed $S_0$, $S_K$, $R$ and $K$, the total rate $H$ is smallest when all the ratios $r_i$ are equal.

Proof. The product of the ratios telescopes: $r_1 r_2 \cdots r_K = S_K/S_0$, a fixed number that we call $\rho$. By the inequality of the arithmetic and geometric means, for positive numbers

$$\frac{r_1 + \cdots + r_K}{K} \;\ge\; (r_1 \cdots r_K)^{1/K} = \rho^{1/K},$$

with equality exactly when $r_1 = \cdots = r_K$. So $\sum r_i \ge K\rho^{1/K}$, and the bound is reached only by $r_i = \rho^{1/K}$ for every $i$. The rest of $H$ does not depend on the ratios. $\blacksquare$

The paper proves the theorem by setting partial derivatives to zero. The inequality gives the same answer and shows in addition that it is the minimum and that no other choice reaches it. With equal ratios $r$ the sizes are $S_i = r^i S_0$, a geometric progression, and $H = \frac{2R}{S_p}\left(K(1 + r) - \tfrac12\right)$, the paper's equation 3.6.

Example (three components between memory and a thousand times memory). Let $S_K/S_0 = 1{,}000$ and $K = 3$. Equal ratios are $10, 10, 10$, and $\sum r_i + K - \tfrac12 = 32.5$. Ratios of $20, 10, 5$ have the same product and give 37.5. Ratios of $100, 5, 2$ give 109.5, more than three times the minimum. The script draws 20,000 random sets of ratios with a fixed product and finds none below the equal ones, as the proof requires.

Why not more components? With equal ratios, $r = \rho^{1/K}$ falls as $K$ rises, so the question is which $K$ makes $K(1 + r)$ least. For $\rho = 1{,}000$ the values of $K(1+r) - \tfrac12$ are 1,000.5 for one disk component, 64.75 for two, 32.5 for three, 25.99 for four, 24.41 for five and 24.47 for six. The minimum is at five components with a ratio of 3.98. Treating $K$ as continuous, $K = \ln\rho/\ln r$ and the quantity to minimize is $(1 + r)/\ln r$, whose derivative vanishes where $r(\ln r - 1) = 1$, at $r = 3.59$, whatever $\rho$ is. That is the ratio that minimizes merge traffic alone. It is not the ratio systems use, because traffic is not the only cost. Every further component adds a merge to schedule and buffer, and the paper notes that finds in a tree of three or more components suffer somewhat in performance, "typically by one extra page I/O per disk component". The paper's own worked examples use two and three components. Luo and Carey (2020) describe evaluations of later systems against LevelDB and RocksDB configured with "the leveling merge policy with a size ratio of 10".

The formula $H$ also shows how the LSM-tree's leveling differs from the batch leveling of Theorem 4. In the LSM-tree every component stays near its full size, because entries leave it continuously, so each entry that arrives is merged with about $r$ entries already there. In the batch scheme a level empties when it moves up and then refills, so an arrival meets on average half a level, which is the factor $\frac{r-1}{2}$ of Theorem 4 against the $r$ here. Luo and Carey summarize the trade between the two policies in the same direction. Leveling merges more often and incurs "a higher write cost by a factor of $T$", their symbol for the size ratio, while tiering keeps up to $T$ components per level and pays in query performance and space. The agreement is in direction and order of magnitude. In the batch model of Theorems 3 and 4 the factor between the two is $r/2$, and a tiered level here holds up to $r - 1$ indexes where theirs holds up to $T$.

The same design in search engines

Lucene's merge policies sit on the tiered side. The documentation of its TieredMergePolicy describes a policy that "merges segments of approximately equal size, subject to an allowed number of segments per tier", with a default of 10 segments merged at once and a default of 8 allowed per tier (Apache Software Foundation, 2025b). It adds two refinements that the unit model lacks. It caps the size of a merged segment, so the largest segments are no longer rewritten by ordinary merges. And it weighs each candidate merge by the dead documents it would reclaim, which is the reclaim rule above applied segment by segment. These are statements about Lucene 10.3.0, released in September 2025, from its documentation as read in November 2026. Later releases exist (10.6.0 as of November 2026) and their documentation was not checked.

The trade is the same one at every scale. The site's own search index is at the far end of it: it is built whole from the Markdown pages for each version of the content and is never updated in place, which is the reconstruction-from-scratch strategy. The course text says that some large search engines adopt it as well, in their case because of the complexity of dynamic indexing. For a collection of several hundred pages a rebuild is simply the cheapest correct method.

Worked problems

The course text's exercise on logarithmic merging is solved on the course page, so these four problems are posed on this article's own results: the two counts, the size ratio, the reclaim rule and the LSM-tree. The script recomputes every number.

Problem 1 (a hundred flushes). An index with room for $n$ postings in memory uses logarithmic merging. After 100 flushes, which indexes are on disk, and how many postings have been written under the cascade count, under the one-pass count, and by merge always?

Solution. The indexes are $I_2$, $I_5$ and $I_6$, of sizes $4n$, $32n$ and $64n$, because 100 is 1100100 in binary. The totals are $602n$, $376n$ and $5{,}050n$.

For the cascade, Theorem 1 needs $\lceil 100/2 \rceil = 50$ and the terms $2^i\lfloor 100/2^i \rfloor$ for $i = 1, \ldots, 6$:

$i$ 1 2 3 4 5 6
$\lfloor 100/2^i \rfloor$ 50 25 12 6 3 1
$2^i\lfloor 100/2^i \rfloor$ 100 100 96 96 96 64
$2^{i-1}\lfloor 100/2^i \rfloor$ 50 50 48 48 48 32

The third row sums to 552, so $W_{\text{cascade}} = (50 + 552)n = 602n$, which is 6.02 writes per posting. The bound of Theorem 1 is $(50 + 100 \times 6)n = 650n$. The fourth row sums to 276, so by Theorem 2, $W_{\text{one}} = (100 + 276)n = 376n$, which is 3.76 writes per posting, under the bound $100\,(1 + 6/2)\,n = 400n$. Merge always writes $100 \times 101/2 = 5{,}050$ units. The script's simulation, which merges lists of batches and counts what it writes, gives the same three totals.

Problem 2 (a billion postings). A collection of $10^9$ postings is indexed with room for $10^6$ in memory, which is 1,000 flushes. Compare logarithmic merging in one pass with tiered and leveled merging at ratios 4 and 10, by writes per posting and by the largest number of indexes a query ever consults.

Solution. From the simulation of 1,000 equal flushes:

Strategy Writes per posting Most indexes at any time Indexes after flush 1,000
Merge always 500.5 1 1
Leveled, $r = 10$ 14.500 3 1
Leveled, $r = 4$ 7.560 5 4
Logarithmic, one pass 5.060 9 6
Tiered, $r = 4$ 3.790 14 10
Tiered, $r = 10$ 3.700 27 1

The last column is read from the digits of 1,000. In binary it is 1111101000, with six ones. In base 4 it is 33220: the digits sum to 10, the tiered count, and four of them are nonzero, the leveled count. In base 10 it is 1000, one index either way. For ratio 10, $1{,}000 = 10^3$ and the closed forms apply exactly: $1 + \tfrac{9}{10} \cdot 3 = 3.7$ for tiered and $1 + \tfrac92 \cdot 3 = 14.5$ for leveled. Merge always writes $\tfrac12(1{,}000 + 1) = 500.5$ times per posting.

The choice is between rows. Going from logarithmic merging to tiered merging with ratio 10 saves about a quarter of the writing and triples the worst number of indexes. Going to leveled merging with ratio 10 cuts the worst number of indexes to a third and nearly triples the writing. Every row is at least a factor of thirty below merge always.

Problem 3 (a deletion threshold, and a skewed idf). (a) A segment is rewritten when a quarter of its postings are dead. How many postings are written per update in the steady state of the reclaim rule, and how large does the segment get? (b) An index reports $N'$ and $\mathit{df}'$ that include dead documents. It has one million live documents, and a quarter of all its documents are dead. A term occurs in 1,000 live documents. Find the reported idf if deletions struck documents at random, and if instead every document containing the term has been replaced once.

Solution. (a) Four writes per update, and a peak size of 1.33 times the live postings. With $\delta = \tfrac14$: $1/\delta = 4$, made up of one write for the new posting and $(1-\delta)/\delta = 3$ for its share of the rewrite. The peak is $1/(1 - \delta) = 4/3$. With 30,000 live postings, a rewrite happens every 10,000 updates and writes 30,000 postings, which is 3 per update, and the script's run confirms the total of 4.

(b) The true idf is $\log_{10}(10^6/10^3) = 3.000$. A quarter of all documents dead means $D/(N + D) = \tfrac14$, so $D = N/3 = 333{,}333$ and $N' = 1{,}333{,}333$. If deletion was at random, the term's lists hold dead postings in the same proportion, $\mathit{dd} = \mathit{df}/3$, and the reported idf is $\log_{10}\frac{1{,}333{,}333}{1{,}333.3} = 3.000$, unchanged. If every one of the term's 1,000 documents has been replaced once, the lists hold 1,000 live and 1,000 dead postings, $\mathit{df}' = 2{,}000$, and the reported idf is $\log_{10}\frac{1{,}333{,}333}{2{,}000} = 2.824$. By the formula, the error is $\log_{10}\frac{1 + 1/3}{1 + 1} = \log_{10}\tfrac23 = -0.176$. The term looks more common than it is, and a ranking function gives it less weight than it deserves until a merge removes the dead postings.

Problem 4 (sizing an LSM-tree). An LSM-tree has a memory component of size $S_0$ and a largest component of $1{,}000\,S_0$, with three disk components. Compare the merge traffic $H$ for ratios $10, 10, 10$ and for ratios $100, 5, 2$. Then find the number of disk components that minimizes $H$.

Solution. In units of $R/S_p$ page transfers per second, $H = 2\left(\sum r_i + K - \tfrac12\right)$. For $10, 10, 10$: $2(30 + 2.5) = 65$. For $100, 5, 2$: $2(107 + 2.5) = 219$. Both have product 1,000, and Theorem 5 says the equal ratios are the minimum for three components. The unequal design does more than three times the transfer, nearly all of it in the first merge, which rewrites 100 pages of $C_1$ for every page that arrives.

For the best $K$, equal ratios give $r = 1{,}000^{1/K}$ and $H/2 = K(1 + r) - \tfrac12$: 32.5 at $K = 3$, 25.99 at $K = 4$, 24.41 at $K = 5$ and 24.47 at $K = 6$, after which it rises. Five components with ratio 3.98 minimize the traffic, close to the continuous optimum $r = 3.59$, for which $K = \ln 1{,}000/\ln 3.59 = 5.4$. Going from three components to five saves a quarter of the merge traffic and adds two components to every lookup, which is the trade of this whole article in the paper's own units.

What we have learned

An index stays current by collecting new postings in memory and writing them out in batches, and the strategies differ in what they merge at each flush. Never merging writes each posting once and leaves $T/n$ indexes. Always merging leaves one index and writes each posting $\tfrac12(T/n + 1)$ times on average. Logarithmic merging in one pass writes each posting $1 + \tfrac12\log_2(T/n)$ times on average, half of what a cascade of pairwise merges writes, for the same indexes. A size ratio $r$ gives tiered merging, with $1 + \frac{r-1}{r}\log_r(T/n)$ writes and up to $r - 1$ indexes per level, and leveled merging, with $1 + \frac{r-1}{2}\log_r(T/n)$ writes and one index per level. The two families meet at $r = 2$ and reach the two extremes as $r$ grows. Deletion in immutable segments is recorded and reclaimed later, at $1/\delta$ writes per update for a threshold $\delta$ in the simplest case, and dead postings bias idf by $\log_{10}\frac{1 + D/N}{1 + \mathit{dd}/\mathit{df}}$ until then. The log-structured merge tree is the same design, and its component sizes should form a geometric progression, by the inequality of the arithmetic and geometric means.

Merging decides how much work an update costs. The next article turns to the work a query costs and to the oldest way of avoiding it, which is to remember the answer: Caching in Search Engines.

References