Cache management (query, request, field data) in Elasticsearch - Time & Space Complexity

Time Complexity: Cache management (query, request, field data)

O(1)

Understanding Time Complexity

When Elasticsearch uses caches, it speeds up repeated searches by storing results or data. We want to understand how the time to get results changes as the data or queries grow.

How does caching affect the work Elasticsearch does when handling queries and field data?

Scenario Under Consideration

Analyze the time complexity of this cache usage example in Elasticsearch.

GET /my_index/_search
{
  "query": {
    "term": { "user": "kimchy" }
  },
  "request_cache": true
}

// Field data cache is used for sorting or aggregations on fields
// Query cache stores results of frequent queries
    

This snippet runs a term query with request cache enabled, which stores query results for reuse.

Identify Repeating Operations

Look at what repeats when Elasticsearch handles caching.

• Primary operation: Checking if the query result is in the cache.
• How many times: Once per query execution, but repeated queries reuse cached results without full search.

How Execution Grows With Input

When cache is cold (empty), Elasticsearch does a full search, which grows with data size. When cache is warm, it returns results quickly.

Input Size (n)	Approx. Operations
10	Full search or quick cache lookup
100	Full search or quick cache lookup
1000	Full search or quick cache lookup

Pattern observation: Without cache, work grows with data size; with cache, work stays small regardless of data size.

Final Time Complexity

Time Complexity: O(1) when cache hits, otherwise O(n) for full search.

This means if the cache has the data, Elasticsearch quickly returns results without extra work; if not, it searches through all data.

Common Mistake

[X] Wrong: "Cache always makes queries run instantly no matter what."

[OK] Correct: Cache only helps if the query or field data was seen before and stored; new or unique queries still need full processing.

Interview Connect

Understanding caching shows you how systems save time by reusing work. This skill helps you explain performance in real projects and shows you think about efficiency clearly.

Self-Check

"What if we disabled the request cache? How would the time complexity change for repeated queries?"