Object and nested types in Elasticsearch - Time & Space Complexity

Time Complexity: Object and nested types

O(n)

Understanding Time Complexity

When working with object and nested types in Elasticsearch, it's important to understand how query time grows as data size increases.

We want to know how the search cost changes when we have many nested objects inside documents.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch nested query.

GET /my_index/_search
{
  "query": {
    "nested": {
      "path": "comments",
      "query": {
        "match": { "comments.message": "great" }
      }
    }
  }
}
    

This query searches for documents where the nested field comments contains a message matching "great".

Identify Repeating Operations

Look for repeated work inside the nested query.

• Primary operation: Elasticsearch scans each nested object inside every document.
• How many times: Once for each nested object in the documents being searched.

How Execution Grows With Input

As the number of nested objects grows, the query must check more entries.

Input Size (nested objects per doc)	Approx. Operations
10	Checks 10 nested objects per document
100	Checks 100 nested objects per document
1000	Checks 1000 nested objects per document

Pattern observation: The work grows directly with the number of nested objects to check.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of nested objects inside the documents.

Common Mistake

[X] Wrong: "Nested queries are always fast because they only look inside one nested object."

[OK] Correct: The query must check every nested object to find matches, so more nested objects mean more work.

Interview Connect

Understanding how nested queries scale helps you explain search performance clearly and shows you can reason about real data structures.

Self-Check

What if we changed the nested query to a simple object query without nesting? How would the time complexity change?