Inverted Index Construction and Query Planning for Log Search

Search over logs is a constrained instance of full-text retrieval: the corpus is enormous, the documents are small and highly repetitive, the query is usually a conjunction of a time range and a handful of terms, and the result is almost always read in time order. Those constraints allow an index that is much simpler than a general-purpose search engine, and they also make the wrong index design actively harmful, because a large index over a high-cardinality field costs more to maintain than the queries it accelerates.

What is indexed and what is only stored

A record has fields, and each field has a policy: indexed, stored, or both. Indexing a field means adding its values to a structure that supports lookup; storing it means keeping the value available for output. They are independent, and conflating them is the first design error.

Time and a small set of declared dimensions are indexed. The message body is usually indexed as text, or not at all. Fields that are high-cardinality and rarely filtered, such as a request identifier or a user identifier, are stored but not indexed, because the index for such a field has as many distinct terms as the corpus has values, and a posting list for each term of length one.

The size consequence is direct: an inverted index has one entry per distinct term, and the number of distinct terms is bounded by the vocabulary, not by the document count. A field whose values are arbitrary strings has a vocabulary equal to the number of distinct values, so the index grows in proportion to the data. A field drawn from a small domain has a vocabulary of that size and a posting list per value whose length is proportional to the frequency of the value.

Tokenization decides the vocabulary. Splitting on whitespace and punctuation, lowercasing, and dropping very short tokens is the usual text analysis chain. For logs there are two specific problems. First, the tokens that matter are often punctuation-laden: an IP address, a UUID, a path with slashes, or a timestamp. A tokenizer that strips punctuation destroys them, so a log index usually keeps the raw value in a separate field and tokenizes the message body with a rule that preserves internal punctuation. Second, log messages contain a small number of constant templates and a large number of variable values, so the vocabulary is dominated by the variable values, which are exactly the terms nobody searches for by exact match.

Posting lists and the encoding that makes them small

For each term the index stores the identifiers of the documents containing it. A naive representation is a list of 64-bit document identifiers, which for a term appearing in a million documents costs eight megabytes. Two transformations reduce this by roughly an order of magnitude, and both depend on ordering.

Sort the identifiers ascending and store the gaps between consecutive values rather than the values. For a term that appears in many consecutive documents, most gaps are 1, and a small integer can be stored in one byte. Then encode each gap as a variable-length integer: seven bits per byte with the high bit marking continuation, so values below 128 take one byte, below 16,384 take two, and so on. The combination of delta encoding and varint is the standard posting list format, and its efficiency is a direct consequence of the term being common. A rare term has large gaps and pays more per entry, which is acceptable because a rare term has few entries.

Decompression is sequential and cheap: read bytes, shift, accumulate. The cost is that random access into a posting list requires decoding from the start, so queries that need to skip ahead use a skip structure: an auxiliary list of every k-th document identifier with a byte offset, letting the reader jump to a block boundary. Choosing k trades skip-list size against the number of postings decoded per jump; a block of a few hundred postings is a common compromise because it keeps the skip structure small relative to the list.

For conjunction queries, the planner processes terms in order of increasing posting list length and intersects them, using the skip structure to advance the longer lists. The cost is proportional to the shortest list plus the number of skips taken, not to the sum of all lists. This is why term order matters and why a query engine reorders terms automatically rather than trusting the query text.

Time partitioning as the primary pruning mechanism

The dominant filter in a log query is a time range, and almost every log store partitions by time, into hourly or daily segments, each with its own index. A query with a time range touches only the segments that overlap it, so the effective corpus for a one-hour query against a year of data is one hour of segments.

Partitioning has three costs. First, a segment has a fixed overhead: its own term dictionary, its own posting lists, its own metadata. Many small segments multiply that overhead, so the partition size cannot be arbitrarily small. Second, a query that spans many segments pays the overhead repeatedly, which is why queries over a long range are slower per byte than short ones. Third, merging segments to reduce their count costs a rewrite of the data, and the write amplification of that rewrite is the price of a compact index.

The partition boundary is chosen at write time and cannot be changed without a rewrite, so the choice encodes an assumption about query shape. Partitioning by hour assumes queries are hour-scale or shorter. Partitioning by day assumes queries span days. A store that partitions by hour and is queried over months spends its time opening and closing segments; a store that partitions by day and is queried over minutes reads a day of data to answer a minute of it.

Within a segment, the record identifier is assigned in arrival order, so a posting list is naturally sorted by time as well as by identifier. That property allows a range predicate on time to be applied during posting list traversal rather than as a separate filter, which saves a pass over the candidates.

When the index loses

An index is a bet that queries are selective and repeated. Both halves can fail.

Selectivity fails when a predicate matches a large fraction of the corpus. A term appearing in most records has a posting list nearly as long as the segment, so the index lookup reads almost the whole list and then reads almost every document; a sequential scan with an early filter would have cost less, because it reads the compressed blocks in order and never materializes identifiers. Query planners use a threshold on estimated selectivity, derived from posting list lengths, to switch to a scan. The estimate is available cheaply because the list length is stored with the term.

Repetition fails when each query is unique, because the index is maintained on write regardless of whether it is ever used. An index over a field that is filtered once a month is pure cost. The usual resolution is a two-tier policy: index the fields that appear in routine queries and keep the rest as stored columns that a scan can filter. This is the same trade as the schema decision in Structured Fields Versus Formatted Message Strings, applied to the storage layer.

The third loss is index bloat from a high-cardinality text field. If the message body is tokenized and every variable value becomes a term, the vocabulary grows without bound and the term dictionary becomes the largest part of the index. A common mitigation is to index only the constant part of the message, which requires knowing the template, the mechanism described in Repeat Suppression and Template Fingerprints, and to treat the variable part as stored payload.

Compression, storage layout, and the interaction with the index

The index is compressed differently from the payload. Posting lists use delta and varint because their values are sorted integers. Payload blocks use a general-purpose compressor or a columnar encoding because their values are text and numbers with local repetition. The two are stored separately, and the ratio between them determines the cost of a query: a selective query reads a few postings and a few blocks, while a broad query reads many.

A columnar layout changes the calculus. If fields are stored column by column, a query that filters on one field and returns another reads only those two columns, and a predicate can be evaluated against a compressed column with vectorized comparisons. The index then becomes an optional accelerator for exact-match predicates rather than the primary access path. The trade is that assembling a full record requires gathering values from many columns, which is expensive for a query that returns whole records.

The practical consequence for a log store is that the index should be sized to the queries actually issued, and the storage layout should match the retrieval pattern: scans of a time range returning whole records favor row-oriented blocks, while aggregations over one field favor columns. Most stores pick one and expose the other as a slower path. The compression mechanics behind the payload blocks are covered in Block Compression and Columnar Layout for Log Storage, and the retention boundary that determines how many segments remain queryable is set by Retention Policy as a Storage Budget.

One further constraint deserves mention: the index is only as fresh as the last committed segment. Records in an uncommitted buffer are searchable only by scanning that buffer, so a query issued immediately after a write may not see the write. The visibility delay is a deliberate trade between write throughput and query freshness, and its size is a property of the commit interval rather than of the index structure. A store that commits every second has near-real-time visibility and pays for frequent small segments; one that commits every minute has fewer segments and a minute of invisible data.