Nested queries for nested objects in Elasticsearch - Time & Space Complexity

Time Complexity: Nested queries for nested objects

O(n)

Understanding Time Complexity

When searching nested objects in Elasticsearch, understanding how query time grows helps us write efficient searches.

We want to know how the search time changes as the number of nested objects grows.

Scenario Under Consideration

Analyze the time complexity of the following nested query.

{
  "query": {
    "nested": {
      "path": "comments",
      "query": {
        "match": { "comments.message": "great" }
      }
    }
  }
}
    

This query searches for documents where any nested comment has the word "great" in its message.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Checking each nested comment's message for a match.
• How many times: Once for every nested comment inside each document.

How Execution Grows With Input

As the number of nested comments grows, the query checks more items.

Input Size (n)	Approx. Operations
10 nested comments	About 10 checks
100 nested comments	About 100 checks
1000 nested comments	About 1000 checks

Pattern observation: The number of checks grows directly with the number of nested comments.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows in a straight line as the number of nested objects increases.

Common Mistake

[X] Wrong: "Nested queries run in constant time no matter how many nested objects there are."

[OK] Correct: Each nested object must be checked, so more nested objects mean more work and longer search time.

Interview Connect

Knowing how nested queries scale helps you explain search performance and design better queries in real projects.

Self-Check

What if we added a filter to limit nested objects before matching? How would the time complexity change?