First search query in Elasticsearch - Time & Space Complexity

Time Complexity: First search query

O(k)

Understanding Time Complexity

When we run a search query in Elasticsearch, we want to know how the time it takes changes as we add more data.

We ask: How does the search time grow when the number of documents increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /my-index/_search
{
  "query": {
    "match": {
      "title": "elasticsearch"
    }
  }
}
    

This query searches for documents in "my-index" where the "title" field contains the word "elasticsearch".

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Elasticsearch scans the inverted index entries for the word "elasticsearch".
• How many times: It processes postings for each document containing that word, which depends on how many documents match.

How Execution Grows With Input

As the number of documents grows, Elasticsearch looks up the word in its index and checks matching documents.

Input Size (n)	Approx. Operations
10	Checks a few postings for "elasticsearch"
100	Checks more postings, roughly 10 times more
1000	Checks many postings, about 100 times more than 10 docs

Pattern observation: The work grows roughly with the number of documents that contain the search word.

Final Time Complexity

Time Complexity: O(k)

This means the search time grows in proportion to the number of documents matching the query term.

Common Mistake

[X] Wrong: "The search time depends on the total number of documents in the index."

[OK] Correct: Elasticsearch uses an index to jump directly to matching documents, so it does not scan all documents, only those containing the search term.

Interview Connect

Understanding how search time grows helps you explain how Elasticsearch handles queries efficiently, a useful skill for real-world search applications.

Self-Check

"What if we changed the query to search for multiple words combined with AND? How would the time complexity change?"

Practice

1.

What does a match query do in an Elasticsearch search?

easy

A. It finds documents where the specified field contains the search text.

B. It deletes documents matching the search text.

C. It updates documents with the search text.

D. It creates a new index with the search text.

Solution

1. Step 1: Understand the purpose of match query

   The match query is used to find documents where a field contains the given text.

2. Step 2: Differentiate from other operations

   Deleting, updating, or creating indexes are different Elasticsearch operations, not done by match.

3. Final Answer:

   It finds documents where the specified field contains the search text. -> Option A

4. Quick Check:

   match query = find documents [OK]

Hint: Match query searches text in fields, not modify data [OK]

Common Mistakes:

• Confusing search with delete or update operations
• Thinking match creates or modifies indexes
• Assuming match returns all documents regardless of content

2.

Which of the following is the correct syntax for a basic Elasticsearch match query to search for "apple" in the field "fruit"?

{
  "query": {
    "match": {
      "fruit": "apple"
    }
  }
}

easy

A. { "query": { "match": { "fruit": "apple" } } }

B. { "match": { "query": { "fruit": "apple" } } }

C. { "query": { "fruit": { "match": "apple" } } }

D. { "query": { "match": { "apple": "fruit" } } }

Solution

1. Step 1: Identify the correct JSON structure for a match query

   The correct structure places match inside query, with the field name as key and search text as value.

2. Step 2: Compare options to this structure

   { "query": { "match": { "fruit": "apple" } } } matches the correct syntax exactly. Others misplace keys or swap field and text.

3. Final Answer:

   { "query": { "match": { "fruit": "apple" } } } -> Option A

4. Quick Check:

   Correct JSON structure = { "query": { "match": { "fruit": "apple" } } } [OK]

Hint: Match query is inside query, field name as key, text as value [OK]

Common Mistakes:

• Swapping field name and search text
• Placing match outside query
• Using wrong nesting of JSON keys

3.

Given this Elasticsearch query, what will it search for?

{
  "query": {
    "match": {
      "title": "quick brown fox"
    }
  }
}

medium

A. Documents where the title field contains the exact phrase "quick brown fox".

B. Documents where the title field contains only the word "fox".

C. Documents where the title field is empty.

D. Documents where the title field contains any of the words "quick", "brown", or "fox".

Solution

1. Step 1: Understand how match query works with multiple words

   The match query analyzes the text and searches for documents containing any of the words, not necessarily the exact phrase.

2. Step 2: Compare options with this behavior

   Documents where the title field contains any of the words "quick", "brown", or "fox". correctly states it searches for any of the words. Documents where the title field contains the exact phrase "quick brown fox". is phrase match, which requires a different query type.

3. Final Answer:

   Documents where the title field contains any of the words "quick", "brown", or "fox". -> Option D

4. Quick Check:

   match = any word match [OK]

Hint: Match finds any word in text, not exact phrase [OK]

Common Mistakes:

• Thinking match does exact phrase search
• Assuming match finds only one word
• Confusing match with match_phrase query

4.

Identify the error in this Elasticsearch query:

{
  "query": {
    "match": {
      "content": apple
    }
  }
}

medium

A. The match query should be outside the query object.

B. The field name content should be in quotes.

C. The search text apple should be in quotes.

D. The query object is missing a closing brace.

Solution

1. Step 1: Check JSON syntax for values

   In JSON, string values must be enclosed in double quotes. Here, apple is unquoted.

2. Step 2: Verify other parts of the query

   The field name and braces are correctly quoted and closed. The match query is correctly inside query.

3. Final Answer:

   The search text apple should be in quotes. -> Option C

4. Quick Check:

   Strings need quotes in JSON [OK]

Hint: Always quote string values in JSON queries [OK]

Common Mistakes:

• Leaving string values unquoted
• Misplacing match outside query
• Forgetting closing braces

5.

You want to find documents where the field "description" contains the word "fresh" but only if the field "category" equals "fruit". Which Elasticsearch query correctly combines these conditions?

hard

A. { "query": { "match": { "description": "fresh" }, "match": { "category": "fruit" } } }

B. { "query": { "bool": { "must": [ { "match": { "description": "fresh" } }, { "match": { "category": "fruit" } } ] } } }

C. { "query": { "term": { "description": "fresh" }, "term": { "category": "fruit" } } }

D. { "query": { "match": { "description": "fresh fruit" } } }

Solution

1. Step 1: Understand combining multiple conditions in Elasticsearch

   To require both conditions, use a bool query with must array containing each match query.

2. Step 2: Evaluate each option's structure

   { "query": { "bool": { "must": [ { "match": { "description": "fresh" } }, { "match": { "category": "fruit" } } ] } } } correctly uses bool with must for both matches. { "query": { "match": { "description": "fresh fruit" } } } searches combined text in one field. Options A and C have invalid JSON or incorrect query structure.

3. Final Answer:

   { "query": { "bool": { "must": [ { "match": { "description": "fresh" } }, { "match": { "category": "fruit" } } ] } } } -> Option B

4. Quick Check:

   Use bool must to combine queries [OK]

Hint: Use bool must array to combine multiple match queries [OK]

Common Mistakes:

• Combining terms incorrectly in one match
• Using invalid JSON with repeated keys
• Not using bool query for multiple conditions