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?

Practice

1. What is the main difference between object and nested types in Elasticsearch?

easy

A. Both types store data the same way but nested type is faster.

B. Object type stores arrays of objects separately, while nested type stores grouped fields as one JSON object.

C. Nested type is used only for numeric fields, object type for text fields.

D. Nested type stores arrays of objects separately to keep their fields linked during searches, while object type stores grouped fields as one JSON object.

Solution

1. Step 1: Understand object type storage

   Object type stores grouped fields as a single JSON object inside a document, meaning all fields are flattened and stored together.

2. Step 2: Understand nested type storage

   Nested type stores arrays of objects separately to maintain the relationship between fields within each object during searches.

3. Final Answer:

   Nested type stores arrays of objects separately to keep their fields linked during searches, while object type stores grouped fields as one JSON object. -> Option D

4. Quick Check:

   Nested keeps object fields linked = C [OK]

Hint: Nested keeps object arrays linked; object flattens fields [OK]

Common Mistakes:

• Confusing object and nested storage behavior
• Thinking nested is only for numeric fields
• Assuming both types store data the same way

2. Which of the following is the correct way to define a nested type field in an Elasticsearch mapping?

easy

A. "comments": { "type": "object" }

B. "comments": { "type": "keyword" }

C. "comments": { "type": "nested" }

D. "comments": { "type": "text" }

Solution

1. Step 1: Recall nested type syntax

   To define a nested field, the type must be explicitly set to "nested" in the mapping.

2. Step 2: Check options

   "comments": { "type": "nested" } correctly sets "comments" field type to "nested". Other options use incorrect types for nested data.

3. Final Answer:

   "comments": { "type": "nested" } -> Option C

4. Quick Check:

   Nested type requires "type": "nested" [OK]

Hint: Use "type": "nested" to define nested fields [OK]

Common Mistakes:

• Using "object" instead of "nested" for nested arrays
• Confusing text or keyword types with nested
• Omitting the type field

3. Given this mapping with a nested field comments and this document:

{"title": "Post", "comments": [{"user": "alice", "message": "Hi"}, {"user": "bob", "message": "Hello"}]}

Which query will correctly find documents where comments.user is "alice" and comments.message is "Hello" in the same comment object?

medium

A. { "query": { "nested": { "path": "comments", "query": { "bool": { "must": [ { "match": { "comments.user": "alice" } }, { "match": { "comments.message": "Hello" } } ] } } } } }

B. { "query": { "bool": { "must": [ { "match": { "comments.user": "alice" } }, { "match": { "comments.message": "Hello" } } ] } } }

C. { "query": { "term": { "comments.user": "alice" } } }

D. { "query": { "nested": { "path": "comments", "query": { "term": { "comments.message": "Hi" } } } } }

Solution

1. Step 1: Understand nested query usage

   To search inside nested fields and keep field relationships, use a nested query with the correct path and combined conditions inside it.

2. Step 2: Analyze options

   { "query": { "nested": { "path": "comments", "query": { "bool": { "must": [ { "match": { "comments.user": "alice" } }, { "match": { "comments.message": "Hello" } } ] } } } } } uses a nested query on "comments" with a bool must for both user "alice" and message "Hello" in the same nested object. { "query": { "bool": { "must": [ { "match": { "comments.user": "alice" } }, { "match": { "comments.message": "Hello" } } ] } } } searches flattened fields, losing the link. { "query": { "term": { "comments.user": "alice" } } } only matches user. { "query": { "nested": { "path": "comments", "query": { "term": { "comments.message": "Hi" } } } } } searches for message "Hi" only.

3. Final Answer:

   Uses nested query to match both conditions in the same nested object. -> Option A

4. Quick Check:

   Nested query with bool must inside = A [OK]

Hint: Use nested query with bool must for multiple nested conditions [OK]

Common Mistakes:

• Using bool query without nested for nested fields
• Searching fields separately losing object linkage
• Using term query without nested path

4. You wrote this mapping for a nested field:

{ "properties": { "tags": { "type": "nested", "properties": { "name": { "type": "keyword" } } } } }

But your nested query returns no results even though documents have matching tags. What is the likely mistake?

medium

A. You forgot to use a nested query; used a regular bool query instead.

B. You defined tags as object type instead of nested.

C. You used match query on keyword field instead of term query.

D. You indexed tags as text instead of keyword.

Solution

1. Step 1: Check mapping correctness

   The mapping correctly defines "tags" as nested with keyword "name" field, so mapping is fine.

2. Step 2: Identify query mistake

   If nested query returns no results, often the cause is using a regular bool query instead of a nested query to search nested fields, losing the link between nested objects.

3. Final Answer:

   You forgot to use a nested query; used a regular bool query instead. -> Option A

4. Quick Check:

   Nested fields require nested queries [OK]

Hint: Always use nested query for nested fields [OK]

Common Mistakes:

• Using bool query without nested for nested fields
• Confusing object and nested types in mapping
• Using match query on keyword fields

5. You have documents with a nested field orders containing product and quantity. You want to find documents where there is an order with product "apple" and quantity greater than 10, but also an order with product "banana" and quantity less than 5. Which query structure correctly finds such documents?

hard

A. { "query": { "nested": { "path": "orders", "query": { "bool": { "must": [ { "term": { "orders.product": "apple" } }, { "range": { "orders.quantity": { "gt": 10 } } }, { "term": { "orders.product": "banana" } }, { "range": { "orders.quantity": { "lt": 5 } } } ] } } } }

B. { "query": { "bool": { "must": [ { "nested": { "path": "orders", "query": { "bool": { "must": [ { "term": { "orders.product": "apple" } }, { "range": { "orders.quantity": { "gt": 10 } } } ] } } } }, { "nested": { "path": "orders", "query": { "bool": { "must": [ { "term": { "orders.product": "banana" } }, { "range": { "orders.quantity": { "lt": 5 } } } ] } } } } ] } } }

C. { "query": { "bool": { "must": [ { "term": { "orders.product": "apple" } }, { "range": { "orders.quantity": { "gt": 10 } } }, { "term": { "orders.product": "banana" } }, { "range": { "orders.quantity": { "lt": 5 } } } ] } } }

D. { "query": { "nested": { "path": "orders", "query": { "term": { "orders.product": "apple" } } } } }

Solution

1. Step 1: Understand nested query for multiple conditions

   Each nested object must be queried separately to keep conditions linked inside the same nested object.

2. Step 2: Analyze query options

   { "query": { "bool": { "must": [ { "nested": { "path": "orders", "query": { "bool": { "must": [ { "term": { "orders.product": "apple" } }, { "range": { "orders.quantity": { "gt": 10 } } } ] } } } }, { "nested": { "path": "orders", "query": { "bool": { "must": [ { "term": { "orders.product": "banana" } }, { "range": { "orders.quantity": { "lt": 5 } } } ] } } } } ] } } } uses two nested queries combined with bool must, one for "apple" orders with quantity > 10, another for "banana" orders with quantity < 5, correctly matching documents with both conditions in different nested objects.

3. Step 3: Identify incorrect options

   { "query": { "nested": { "path": "orders", "query": { "bool": { "must": [ { "term": { "orders.product": "apple" } }, { "range": { "orders.quantity": { "gt": 10 } } }, { "term": { "orders.product": "banana" } }, { "range": { "orders.quantity": { "lt": 5 } } } ] } } } } tries to combine all conditions in one nested query, which requires all conditions in the same nested object (impossible for different products). { "query": { "bool": { "must": [ { "term": { "orders.product": "apple" } }, { "range": { "orders.quantity": { "gt": 10 } } }, { "term": { "orders.product": "banana" } }, { "range": { "orders.quantity": { "lt": 5 } } } ] } } } ignores nested queries, losing object linkage. { "query": { "nested": { "path": "orders", "query": { "term": { "orders.product": "apple" } } } } } only queries for "apple" product.

4. Final Answer:

   Uses separate nested queries for each product condition. -> Option B

5. Quick Check:

   Separate nested queries for each condition = A [OK]

Hint: Use separate nested queries for different nested object conditions [OK]

Common Mistakes:

• Combining multiple product conditions in one nested query
• Not using nested queries for nested fields
• Assuming all conditions apply to the same nested object