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?

Practice

1. What is the main purpose of a nested query in Elasticsearch?

easy

A. To aggregate numeric values across documents

B. To search inside objects stored within other objects

C. To perform full-text search on string fields

D. To update documents in bulk

Solution

1. Step 1: Understand nested objects

   Nested objects are objects stored inside other objects in Elasticsearch documents.

2. Step 2: Purpose of nested query

   The nested query lets you search inside these nested objects specifically.

3. Final Answer:

   To search inside objects stored within other objects -> Option B

4. Quick Check:

   Nested query = search inside nested objects [OK]

Hint: Nested queries search inside nested objects only [OK]

Common Mistakes:

• Confusing nested query with full-text search
• Using nested query on non-nested fields
• Thinking nested query updates documents

2. Which of the following is the correct syntax to specify the path in a nested query?

easy

A. "nested": { "path": "comments", "query": { ... } }

B. "nested": { "field": "comments", "query": { ... } }

C. "nested": { "location": "comments", "query": { ... } }

D. "nested": { "object": "comments", "query": { ... } }

Solution

1. Step 1: Identify the correct key for nested path

   The nested query requires the key path to specify the nested object location.

2. Step 2: Match syntax with options

   Only "nested": { "path": "comments", "query": { ... } } uses "path": "comments" correctly.

3. Final Answer:

   "nested": { "path": "comments", "query": { ... } } -> Option A

4. Quick Check:

   Nested query uses "path" key [OK]

Hint: Use "path" key to specify nested object location [OK]

Common Mistakes:

• Using "field" instead of "path"
• Using incorrect keys like "location" or "object"
• Omitting the "path" key entirely

3. Given this nested mapping for comments and this query:

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

What documents will this query return?

medium

A. Documents without any comments

B. Documents where all comments contain the word "great"

C. Documents with the word "great" anywhere in the document

D. Documents with at least one comment containing the word "great"

Solution

1. Step 1: Understand nested query behavior

   The nested query matches documents where at least one nested object matches the query condition.

2. Step 2: Analyze the match condition

   The query matches if any comment's message contains "great".

3. Final Answer:

   Documents with at least one comment containing the word "great" -> Option D

4. Quick Check:

   Nested query matches any nested object meeting condition [OK]

Hint: Nested query matches if any nested object matches [OK]

Common Mistakes:

• Thinking all nested objects must match
• Confusing nested query with top-level match
• Ignoring the nested path requirement

4. Identify the error in this nested query:

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

medium

A. The field "message" should be prefixed with the nested path "comments.message"

B. The "path" key is missing

C. The nested query cannot use match queries

D. The query should be inside a bool query

Solution

1. Step 1: Check field names in nested query

   Fields inside nested queries must be fully qualified with the nested path prefix.

2. Step 2: Identify the missing prefix

   The query uses "message" instead of "comments.message" which is incorrect.

3. Final Answer:

   The field "message" should be prefixed with the nested path "comments.message" -> Option A

4. Quick Check:

   Nested query fields need full path prefix [OK]

Hint: Prefix nested fields with path in queries [OK]

Common Mistakes:

• Omitting nested path prefix in field names
• Assuming nested query disallows match queries
• Forgetting to include the "path" key

5. You have documents with a nested field reviews containing rating and comment. You want to find documents with at least one review having rating >= 4 and comment containing "excellent". Which nested query correctly achieves this?

hard

A. { "bool": { "must": [ { "range": { "reviews.rating": { "gte": 4 } } }, { "match": { "reviews.comment": "excellent" } } ] } }

B. { "nested": { "path": "reviews", "query": { "match": { "reviews.comment": "excellent" } } } }

C. { "nested": { "path": "reviews", "query": { "bool": { "must": [ { "range": { "reviews.rating": { "gte": 4 } } }, { "match": { "reviews.comment": "excellent" } } ] } } } }

D. { "nested": { "path": "reviews", "query": { "range": { "reviews.rating": { "gte": 4 } } } } }

Solution

1. Step 1: Combine conditions inside nested query

   Both rating and comment conditions must be inside the nested query to match the same nested object.

2. Step 2: Use bool must to combine conditions

   Use a bool query with must array to require both conditions.

3. Step 3: Verify field names and structure

   { "nested": { "path": "reviews", "query": { "bool": { "must": [ { "range": { "reviews.rating": { "gte": 4 } } }, { "match": { "reviews.comment": "excellent" } } ] } } } } correctly uses "reviews.rating" and "reviews.comment" inside nested query with bool must.

4. Final Answer:

   { "nested": { "path": "reviews", "query": { "bool": { "must": [ { "range": { "reviews.rating": { "gte": 4 } } }, { "match": { "reviews.comment": "excellent" } } ] } } } } -> Option C

5. Quick Check:

   Combine conditions inside nested bool query [OK]

Hint: Use bool must inside nested query to combine conditions [OK]

Common Mistakes:

• Putting conditions outside nested query
• Using only one condition inside nested query
• Not prefixing fields with nested path