Query and Filter Caches in a Search Engine

A search engine receives millions of queries a day, and a large fraction of them are repeats or near-repeats: the same filter, the same phrase, the same faceted drill-down. Caching exploits that repetition, but only the parts of a query that are deterministic can be cached, and every cached value must be invalidated when the index changes. The design of a search cache is therefore mostly the design of its keys and its invalidation rules.

What can and cannot be cached

The fundamental split is between scoring and matching. The score of a document depends on corpus-wide statistics such as inverse document frequency and average document length, which change as the index changes. The set of documents that match a filter, by contrast, is a pure function of the filter and the index. This distinction yields three cache tiers with different safety properties.

The reason the split exists is that a match is a boolean fact about the index while a score is a real number derived from aggregate statistics. A boolean fact survives the addition of unrelated documents unchanged: adding a document about weather does not change whether a document matches “category = electronics”. But the score of that same electronics document shifts, because the new weather document moves the inverse document frequency of “electronics” and the average document length that BM25 normalizes against. Matching is additive and local; scoring is global and sensitive to the whole corpus.

A filter cache stores the document id set produced by evaluating a filter, such as “category = electronics AND price < 100”. The key is the filter expression itself, and the value is a bitset of matching document ids. Because a filter has no notion of ranking, the cached bitset is reusable by any query that contains the same filter, which is why filters are cached far more aggressively than scored queries.

A query result cache stores the top-ranked document ids for an entire query. This is the least reusable tier, because the key must capture every part of the query, including parameters like the requested offset and size, and the value is tied to a particular ranking. It is also the most fragile tier, because any index change can invalidate the ranking even when the matching set is unchanged.

The third tier caches the terms that appear in queries, keeping their dictionary entries and postings warm in memory rather than recomputing a result. This is not a result cache at all; it is a locality mechanism that reduces the cost of the cold terms described in the query-time cost walk.

The filter cache and its keys

A filter cache keys on the filter, but “the filter” is a data structure, not a string. Two semantically identical filters written differently, one as a conjunction and one as nested boolean clauses, should hit the same cache entry, so the key is a canonicalized form of the filter’s parse tree. Canonicalization sorts commutative operands and folds constants, turning “a AND b” and “b AND a” into the same key. A cache that keys on the raw query string misses on every trivial rewrite.

The value stored for a filter is typically a bitset indexed by document id, so a later query can test membership in a single bit operation and even combine cached bitsets with boolean operations. A drill-down facet that narrows an existing filter can reuse the parent’s cached bitset and only evaluate the additional clause, which is why faceted search is so much faster than a naive re-evaluation of the full filter on every refinement.

The cost of the filter cache is invalidation. A bitset is valid only for the segment set it was built against, and a refresh that adds a segment changes that set. The standard approach is to key the cache entry by a segment generation number: when a new segment appears, entries for the old generation are not deleted but simply stop being looked up, and they age out under memory pressure. This avoids the thundering herd of recomputing every cached filter on every refresh.

Result caches and the ranking hazard

A result cache stores ranked lists, and the hazard is that a score is a function of the whole index. A refresh that adds a single document changes the inverse document frequency of every term and the average document length, which shifts the score of every document, not just the new one. A result cache is therefore either invalidated wholesale on every refresh, which makes it nearly useless for a high-refresh index, or it is accepted as approximate, serving slightly stale rankings for a configurable window.

This is why result caches are keyed to the segment generation and treated as best-effort: they reduce latency at the cost of a bounded staleness in ranking, and they are tuned down or disabled when ranking freshness matters more than latency. The filter cache, by contrast, is exact within a generation, because the matching set of a filter does not drift with corpus statistics in the same way.

Failure modes

The classic cache failure is a poisoned entry: a value cached under a key that does not actually correspond to the current index state, served to a user as if it were fresh. The common cause is a key that does not capture enough, such as omitting the segment generation or omitting a query parameter, so two queries that should differ collide on one key. The reverse failure is key over-capture, where a key includes a volatile detail such as a timestamp, so every query misses and the cache fills with entries that are never read twice.

Memory is the other axis. A cache that is too small thrashes, evicting entries before their second use and paying the evaluation cost twice, while a cache that is too large steals memory from the page cache that keeps postings lists resident, trading a small reduction in repeated-query cost for a large increase in cold-query cost. The correct cache size is therefore measured against the working set of unique filters, not against total index size, and the eviction policy favors entries with high hit rate over entries with high cost, because a rarely-hit expensive entry is still a net loss.

A third failure is specific to the filter cache: the cheap bitset is only cheap if the filter itself is cheap to resolve into a bitset, and a filter that is a heavy disjunction of rare terms is nearly as expensive to evaluate as the query it was meant to shortcut. The cache then stores an expensive result that is rarely reused, and the memory spent holding it would have been better spent on postings. The rule of thumb is that the filter cache pays off for selective filters, the ones that cut the candidate set down by orders of magnitude, and is wasted on filters that leave most of the corpus intact, because re-evaluating a broad filter is nearly free anyway.

The interaction with the refresh cycle is the subtlest failure. A filter bitset built against segment generation N is served to a query running against generation N+1, which is correct for the unchanged segments but misses documents in the new segment. The standard fix is to evaluate the filter against only the new, un-cached segments and OR the result into the cached bitset, which keeps the cache exact at the cost of re-evaluating the filter on the delta. A cache that skips this delta evaluation serves incomplete results, and the error is invisible until a user notices that a document indexed seconds ago does not appear in a filter that should match it.