Label Matchers, Posting Lists, and How a Series Is Selected

Every query begins with a selection: which series are candidates for the expression that follows. In a metrics store the number of series is large and the query touches a small fraction of them, so the selection step determines whether the query takes milliseconds or minutes. The structure that makes selection fast is an inverted index, and the way a query uses it depends on the shape of the label matchers, not on the size of the result.

The index is a mapping from label pairs to the series that carry them. A matcher that names an exact pair can be answered by a lookup. A matcher that names a set of pairs can be answered by unioning lookups. A matcher that constrains a value by pattern may not be answerable by lookup at all, and the query planner has to decide between scanning the index and scanning the series.

The index is a three-level map

The structure is a mapping from label name to the set of values that name takes, and from each value to a posting list: the identifiers of the series carrying that pair. Series identifiers are assigned at ingestion and are dense integers within a block, which is what makes the posting lists compressible and the set operations cheap.

A posting list for a common pair is long. In a fleet where every series carries job="api", that posting list contains every series of that job, which can be most of the index. A posting list for a rare pair is short. The asymmetry is the whole reason the index is useful: intersecting a long list with a short one yields the short one, and the work is proportional to the smaller input.

The three levels also carry the distinct value count per label, which is the cardinality measurement described in Cardinality Explosion and Where It Comes From. That count is available without touching any posting list, which is why cardinality can be monitored cheaply.

Matchers, and which ones the index can answer

Four matcher types exist: equality, inequality, set membership, and pattern match.

Equality is a direct lookup. Set membership is a union of lookups, one per value in the set. Inequality, meaning the label is not a given value, is the complement of a lookup, and it is answered as the set difference between the full series set and the matching posting list. That is cheap when the excluded value is common, because the complement is small, and expensive when the excluded value is rare, because the complement is nearly everything. A query with only inequality matchers has no small list to intersect against, so it degenerates into reading most of the index.

Pattern matching splits into two cases. A pattern anchored at both ends, with wildcards only in the middle, is still a finite set of candidate values if the index stores values as strings, but finding those candidates requires scanning the value list for the label rather than a hash lookup. A pattern anchored at neither end, such as a substring match, cannot be answered from the value list without reading every value, and its cost is proportional to the number of distinct values of that label, not to the number of matching series.

The planner’s job is to order these. It selects the most selective matcher available, materialises that posting list, and intersects the remaining matchers against it. Intersecting a pattern matcher against a small candidate set is cheap, because the pattern is tested against candidate series rather than against every series. Intersecting it against a large candidate set is a scan with extra steps.

Intersection order and the cost model

The cost of an intersection is dominated by the size of the smallest list and the cost of each membership test. When the lists are sorted integers, the intersection can be computed by a merge that advances both cursors, which costs time proportional to the sum of the lengths. When one list is much shorter, the better strategy is to test each element of the short list for membership in the long one, which costs time proportional to the short list times the cost of a membership test, which is a binary search or a galloping search that exploits locality.

Implementations typically switch between merge and galloping based on the ratio of lengths, with a threshold somewhere around a factor of ten to a hundred. Below the threshold, merging is better because both cursors advance sequentially and the memory access pattern is friendly. Above it, galloping wins because it skips long runs of the long list without touching them.

The planner applies the same reasoning to the choice of which matcher to start from. A plan that starts from a list of ten series and intersects five more matchers against it does five membership tests per candidate. A plan that starts from a list of a million does a million. Both produce the same answer, and the difference in work is five orders of magnitude.

There is a subtlety when a matcher has no index entry at all. A label that no series carries has an empty value list, and a positive matcher against it selects nothing, which is a fast and correct answer. A negative matcher against it selects everything, which is the expensive degenerate case and is also correct. The distinction between “label absent” and “label present with an empty value” does not exist in the index, which is why absence is expressed as a negative matcher and why such matchers are the ones to avoid in a selection.

The index is per block, and that changes the plan

A store that partitions time into blocks builds an index per block. A query over a long range touches many block indexes, and the planner can skip blocks whose index cannot satisfy the matchers at all: a block written before a label was introduced has no series carrying it, so the block contributes nothing.

This is the mechanism that makes long-range queries affordable despite the index being rebuilt per block. It also means the cost of a query is not uniform across its range: the blocks written while a high-cardinality label was in use are expensive, and the blocks written before or after are cheap. A query over a year that appears to be slow is often slow because of one month of data, and the per-block breakdown is what shows it.

Block-level indexes also make the query’s cost depend on the time dimension of the label schema, which is a kind of dependency that is easy to overlook. Renaming a label, or adding one, splits the series history into periods with different schemas, and any query that selects on the new label silently returns nothing for the old blocks. The absence is indistinguishable from “the value never occurred”, which is a correctness hazard rather than a performance one.

Caching the selection, not the result

Because selection is the expensive part and its result is small, many systems cache posting lists rather than query results. The cache key is the matcher set, and the value is the series identifiers that satisfy it. Two queries that differ only in their aggregation or their range selector share the cached selection, which is why caching at this layer has a higher hit rate than caching final results.

The cache is invalidated by new blocks, since a new block can introduce series that satisfy a previously cached matcher. A cache that is not invalidated on block creation returns stale selections, and the failure is silent: the query returns a result that omits the newest data, which looks like a delay rather than a bug.

What the index cannot do

The index knows labels, not values. A query that filters on a sample value, such as “series where latency exceeded a threshold at some point”, cannot use the index at all, because the index has no information about samples. Such a query must read every candidate series and scan its samples, which is a full scan of the candidate set regardless of how selective the label matchers were.

The same limitation applies to functions that need to look across series before deciding what to return, such as a top-k selection. The planner can use the index to narrow the candidates, but the top-k computation itself is linear in the candidates’ sample count. This is why queries that rank across a high-cardinality label set are the ones that most often exceed a timeout, and why pre-aggregating them, as described in Recording Rules, Pre-Aggregation, and the Cost of Evaluating at Read Time, is the usual remedy.

The index is also blind to time within a block. It records that a series exists in the block, not which timestamps it occupies. A series that appears only at the end of a block still forces the block to be read for any range overlapping it. This is a deliberate trade: a per-sample index would be larger than the samples it indexes, and the block size is chosen so that the waste is bounded by one block per series.