Deletion via Tombstones and the Delete Bitvector

A user clicks “delete” on a document, and the search system promises it will no longer appear in results. But the postings for that document are compressed into immutable segments, and segments cannot be mutated in place. The resolution is a two-step protocol: deletion marks the document dead with a tombstone, and a later merge physically removes its postings. Almost all of the subtlety in search-system deletion lives in the gap between those two steps.

Why not remove eagerly

Removing a posting eagerly would mean rewriting the list it lives in, and that list is part of an immutable segment. The only structure that could support eager removal is a mutable list, which the whole segment design exists to avoid. So deletion is split in time: the delete operation is cheap and immediate, and the expensive removal is folded into the merge that would happen anyway. This is the same defer-and-amortize logic that makes the segment merge economical.

The tombstone is just a record saying “document D is dead.” It is stored where it can be consulted quickly at query time: either as a bitvector over document ids, with a bit per document, or as a sorted list of deleted ids. The bitvector form is the common one because it is compact, one bit per document, and answers “is D dead?” in a single load. For a corpus of a million documents, a delete bitvector is about 128 kilobytes, small enough to keep resident.

The tombstone exists because the alternative, physically removing postings at delete time, would require the index to support in-place mutation, and in-place mutation is the exact property the immutable-segment design gave up to get cheap, safe, concurrent writes. The tombstone is therefore not a workaround for a limitation but the direct cost of the immutability decision: deletion becomes a mark instead of an erase, and the erase is deferred to the one place in the system that already rewrites data, the merge. This is the same pattern a log-structured filesystem uses, where overwrites become appends and old blocks are garbage-collected later rather than rewritten in place.

What a query does with a tombstone

A query that traverses a postings list encounters dead postings and must skip them. The walk through a list therefore checks every candidate id against the delete bitvector and ignores documents whose bit is set. This check is not free: it adds a branch and a memory access to the hottest loop in the system, and it means a heavily deleted list still costs as much to scan as a live one, because the dead postings occupy space and cache lines just as live ones do.

The check has a measurable structure. The delete bitvector is one bit per document id, so checking document id D reads the byte at offset D divided by eight and tests the bit D mod eight. For a list walk that touches millions of ids, these bit tests are a steady, cache-friendly stream of reads into a compact array, which is why the bitvector is deliberately kept small enough to stay resident: a resident bitvector turns the delete check into a single cache line load, while a paged-out bitvector turns every test into a potential disk fault. The choice of a bitvector over a sorted list of deleted ids is exactly this locality argument, trading a little bit-level arithmetic for the guarantee that the structure is always in memory.

The scorer also needs to know the true length of a document to normalize scores. A document whose postings are partially dead still has a live document length recorded elsewhere, and the scorer reads that live value rather than reconstructing it from the dead postings. The tombstone and the document-length map are therefore distinct structures, and they must agree: a document that is dead must not contribute a score, even if its length map entry survives.

Delete during a merge

The merge is where tombstones become removal. When a merge reads its input segments, it consults the delete bitvector and simply does not copy dead postings to the output. This is why deletion eventually reduces index size: a term whose every posting is dead produces no list in the merged segment, and the dictionary entry for that term disappears.

The ordering hazard is the resurrected document. If a delete arrives for document D while a merge is already running over the segment containing D, the merge might not see the new tombstone and would copy D’s postings into the output as live. The result is that D reappears in results after having been deleted. Systems prevent this by giving deletes a sequence number or generation: a merge may only drop a document if it has consumed every delete up to some generation, and any delete that arrives after the merge read its inputs must be replayed against the merged segment afterward.

Deletes can also target a whole term or query rather than a document id. A “delete by query” resolves the query against the current segment set, produces the matching document id set, and then records those ids as tombstones. The resolution is done once, at delete time, so a document that would match the query in the future but does not now is not deleted; delete-by-query is a snapshot operation, not a standing predicate.

Delete-by-query has a size edge case. The id set it produces is itself the size of the matched documents, and for a broad predicate that matches most of the corpus, the delete is a bulk operation: the tombstone set is nearly as large as the index, and the next merge will drop most of the postings. This is why bulk deletes are often expressed as “drop everything matching a predicate” rather than “record a million ids,” because a standing predicate evaluated at merge time is cheaper to store and apply than a million-entry tombstone set.

Failure modes and edge cases

The delete bitvector has a hard failure mode: it is per-segment, and a document id is only meaningful within its segment. A delete that references a document in a segment that has since been merged into a larger one must be translated or re-targeted, which is why deletions are often expressed against the global document id and then mapped per-segment at query time.

An update is a delete plus an add, so every update doubles the tombstone load for the changed document’s old postings. A document that is edited frequently therefore accumulates a long run of dead postings, and until a merge runs, queries over its terms scan all of them. This is the concrete cost of the append-only design and the reason merge frequency has a direct effect on update-heavy workloads.

Deleting a document that was never indexed is a no-op, but deleting by an id that does not exist can be harmless or an error depending on the system; the bitvector simply has a bit that was never set. And deletion of an entire segment’s worth of documents is the cheapest case: the merge drops the whole segment rather than filtering it, which is why bulk deletes are dramatically cheaper than point deletes.

Deletion is the clearest illustration of the immutability bargain. The mark is nearly free, the removal is deferred, and the entire cost is paid later, in merge I/O and in the query-time skip work that dead postings impose until that merge runs.