The Document Add Path into an Inverted Index

An inverted index answers the question “which documents contain this term?” by mapping every term to a list of document identifiers. The operation that keeps that structure correct is the document add: a single incoming document that must be transformed into a set of postings, each inserted into the right list. The add path is the most hot operation a search system runs after the query path itself, and its design determines nearly everything downstream, from how cheaply an index can be updated to how fast a query can traverse a list.

From one document to many postings

The unit of input is a document with a unique identifier and a set of fields. Only some fields are indexed; the ones that are get tokenized by the same analyzer that will later tokenize queries. Symmetry between index-time and query-time tokenization is a hard requirement, because a term is only retrievable if both sides produce the identical byte sequence. A query tokenizer that lowercases and an index tokenizer that does not will silently never match on capitalized input.

Tokenization produces a stream of (term, position) pairs, where position is the ordinal slot of the token within its field. For each distinct term in the document, the index builds a posting: a record carrying the document id, the term frequency (how many times the term occurred), and the list of positions where it occurred. One document with a thousand distinct terms therefore contributes a thousand postings, each destined for a different list. Terms that occur many times in one document collapse into a single posting with a longer position list.

The document id is the load-bearing invariant. In most implementations ids are issued by a monotonically increasing counter, so the first document indexed is id 0 or 1, the next is one larger, and so on. This ordering is not cosmetic. Postings lists are kept sorted in ascending document id order, and almost every compression and query-optimization technique depends on that sortedness.

Appending in document id order

Because ids are issued in order and each document is processed once, a single-threaded add naturally appends to each list in sorted order: the posting for document N+1 always goes after the posting for document N. This is why the add path is fast. No list ever needs to be searched for an insertion point, no element ever shifts, and the list’s sorted invariant is maintained for free.

The consequence of this design shows up when a document is updated rather than added. An update that changes a term rewrites the document’s postings, but the old postings are not found and removed. Instead the system treats an update as a delete of the old document followed by an add of a new document with a fresh, larger id. The old postings stay in their lists, flagged as dead, and the new postings are appended at the end. The reader of a list therefore skips dead postings rather than never seeing them. This “append, never mutate” discipline is what lets many independent writers fill a list without locks: each list is effectively append-only, and the only shared state is the id counter itself.

The trade-off is list length. A frequently edited document accumulates one live posting and several dead ones per term. Dead postings occupy space and must be walked past on every query, so a system that never reclaims them degrades toward a list full of garbage. Reclamation is deferred to a separate process, the segment merge, which is the subject of segment-based indexing and the merge operation.

Buffering the add

Naive per-posting writes are intolerable: a disk seek per posting would make indexing thousands of times slower than the data itself. Every practical index therefore buffers. Documents accumulate in an in-memory buffer, and their postings are appended to in-memory lists. When the buffer reaches a configured size, or when a commit is requested, the buffer is sorted and written to disk as an immutable segment.

The buffer changes the meaning of “indexed.” A document sitting in the buffer is searchable only if the query layer also reads the buffer, which it does by treating the buffer as one more segment. A document that has been flushed to disk is searchable only after a new searcher is opened over the new segment set. The exact boundary between these states is the heart of near-real-time refresh.

Buffering has a second effect on the add path: it batches the per-term overhead. Writing a postings list to disk requires a term dictionary entry, a skip structure, and a block of compressed deltas. Amortizing those fixed costs over many documents in one flush is what turns the add path from a per-document cost into a per-segment cost.

Delta encoding as the write format

The on-disk representation of a list is not an array of raw ids. Consecutive ids are stored as their differences, a technique called delta encoding: the list [101, 115, 120, 122] becomes [101, 14, 5, 2]. Because ids within a term’s list are sorted and tend to arrive close together when a corpus is added in order, the deltas are small, and small integers compress well under variable-byte or bit-packing schemes. The sibling cluster on indexing covers the byte-level encodings; the add path cares only that the format is append-friendly and that the encoder can run in a single pass over sorted input.

One subtlety of delta encoding is that it ties the compressed size to the arrival order of documents, not to the term’s true distribution. A term that appears in every thousandth document compresses beautifully when documents arrive sequentially, but the same list built from documents that arrive in an order uncorrelated with id would produce large deltas. Because real systems control arrival order by issuing ids in indexing order, this pathology is avoided by construction.

Failure modes at the boundary

The add path breaks at predictable edges. A document whose single field exceeds the analyzer’s token limit is truncated, and the truncated tokens are what get indexed, so a query on a token past the limit cannot match. Duplicate terms across fields produce multiple postings that the scorer must combine. And the monotonically increasing id assumption fails the moment documents arrive out of order: an id smaller than the current tail of a list breaks the append-only invariant and forces an insertion, so systems that accept arbitrary ids either renumber or document the restriction.

The position list carries its own boundary: positions are per-field and start at zero, so a term at the start of a field has position 0, and a phrase query that looks backward from a match at position 0 finds nothing before it. Phrase and proximity matching therefore depend on the position lists surviving the entire pipeline intact, which is one reason the add path stores them even though they cost roughly as much as the frequency and id together.

The add path is the narrow door through which every document enters the index. Its two load-bearing decisions, append-only sorted lists and an in-memory buffer flushed to immutable segments, determine how deletes work, how merges work, and how a query stays fast as the index grows. The next mechanisms in this cluster, the segment merge and the tombstone, exist precisely to undo the side effects this path accumulates.