Match query in Elasticsearch - Time & Space Complexity

Time Complexity: Match query

O(m)

Understanding Time Complexity

When using a match query in Elasticsearch, it's important to know how the search time changes as the data grows.

We want to understand how the number of documents affects the time it takes to find matches.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch match query.

GET /my_index/_search
{
  "query": {
    "match": {
      "content": "quick brown fox"
    }
  }
}
    

This query searches the "content" field for documents matching the words "quick brown fox".

Identify Repeating Operations

Look for repeated steps that affect performance.

• Primary operation: Checking the inverted index for matching terms in the "content" field.
• How many times: Once per unique term in the query, then merging results.

How Execution Grows With Input

As the number of documents grows, the search time depends on the number of matching documents and the efficiency of the inverted index.

Input Size (n)	Approx. Operations
10	Depends on matching documents, not all 10 checked
100	Depends on matching documents, not all 100 checked
1000	Depends on matching documents, not all 1000 checked

Pattern observation: The number of operations grows with the number of matching documents, not necessarily all documents.

Final Time Complexity

Time Complexity: O(m), where m is the number of matching documents.

This means the search time grows linearly with the number of matching documents, not the total number of documents.

Common Mistake

[X] Wrong: "The match query checks every document, so it runs in linear time with total documents."

[OK] Correct: Elasticsearch uses an inverted index to quickly find matching documents, so it does not scan all documents.

Interview Connect

Understanding how search time grows with data size helps you explain performance in real projects and shows you can think about scaling.

Self-Check

"What if we added an index on the 'content' field? How would the time complexity change?"

Practice

1. What does the match query in Elasticsearch primarily do?

easy

A. Updates documents with new values

B. Finds documents with text similar to the search words

C. Deletes documents matching the query

D. Creates a new index for the documents

Solution

1. Step 1: Understand the purpose of match query

   The match query is designed to find documents that contain text similar to the search words provided.

2. Step 2: Differentiate from other operations

   Deleting, updating, or creating indexes are not functions of the match query; it only searches text.

3. Final Answer:

   Finds documents with text similar to the search words -> Option B

4. Quick Check:

   Match query = text search [OK]

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

Common Mistakes:

• Confusing match query with delete or update operations
• Thinking match query creates indexes
• Assuming match query returns exact matches only

2. Which of the following is the correct syntax for a basic match query in Elasticsearch?

easy

A. { "match": { "field": "search text" } }

B. { "match": "field": "search text" }

C. { "match": { "field" = "search text" } }

D. { "match": [ "field", "search text" ] }

Solution

1. Step 1: Review correct JSON structure for match query

   The match query requires a JSON object with the field name as key and the search text as value inside another object.

2. Step 2: Identify syntax errors in options

   { "match": { "field": "search text" } } uses correct JSON with colon separators and nested object. Options A, B, and C have syntax errors like missing braces, wrong assignment, or array usage.

3. Final Answer:

   { "match": { "field": "search text" } } -> Option A

4. Quick Check:

   Correct JSON syntax = { "match": { "field": "search text" } } [OK]

Hint: Match query uses nested JSON with field: text inside match [OK]

Common Mistakes:

• Using equal sign instead of colon
• Missing curly braces around field and text
• Using array instead of object for field and text

3. Given this Elasticsearch query:

{ "query": { "match": { "title": { "query": "quick brown fox", "operator": "and" } } } }

What does the operator": "and" do in this match query?

medium

A. Returns documents containing all the words 'quick', 'brown', and 'fox'

B. Returns documents containing any of the words 'quick', 'brown', or 'fox'

C. Returns documents containing the exact phrase 'quick brown fox'

D. Returns documents containing none of the words

Solution

1. Step 1: Understand the operator option in match query

   The operator 'and' means all words in the query must be present in the document for a match.

2. Step 2: Compare with other operators

   Operator 'or' would return documents with any word, but 'and' requires all words.

3. Final Answer:

   Returns documents containing all the words 'quick', 'brown', and 'fox' -> Option A

4. Quick Check:

   Operator 'and' = all words required [OK]

Hint: Operator 'and' means all words must appear [OK]

Common Mistakes:

• Confusing 'and' with 'or' operator
• Thinking 'and' means exact phrase match
• Ignoring operator option defaults

4. Identify the error in this match query:

{ "query": { "match": { "content": { "query": "data science", "operator": "AND" } } } }

medium

A. The field name 'content' is invalid

B. The query string must be an array, not a string

C. The operator value should be lowercase 'and', not uppercase 'AND'

D. The match query cannot have an operator option

Solution

1. Step 1: Check operator value case sensitivity

   Elasticsearch expects the operator value to be lowercase 'and' or 'or'. Uppercase 'AND' is invalid.

2. Step 2: Validate other parts of the query

   The field name 'content' is valid, query string can be a string, and match query supports operator option.

3. Final Answer:

   The operator value should be lowercase 'and', not uppercase 'AND' -> Option C

4. Quick Check:

   Operator values are lowercase [OK]

Hint: Operator values must be lowercase 'and' or 'or' [OK]

Common Mistakes:

• Using uppercase 'AND' or 'OR' for operator
• Assuming query must be an array
• Thinking operator option is not allowed

5. You want to find documents where the description field contains either the word 'fast' or 'quick', but not necessarily both. Which match query is correct?

hard

A. { "match": { "description": { "query": "fast quick", "operator": "not" } } }

B. { "match": { "description": { "query": "fast quick", "operator": "and" } } }

C. { "match": { "description": "fast OR quick" } }

D. { "match": { "description": { "query": "fast quick", "operator": "or" } } }

Solution

1. Step 1: Understand the operator 'or' in match query

   Operator 'or' returns documents containing any of the words, so either 'fast' or 'quick' or both.

2. Step 2: Evaluate other options

   B requires both words, C searches for documents containing 'fast', 'OR', and 'quick' (treating OR as literal text), D uses invalid operator 'not'.

3. Final Answer:

   { "match": { "description": { "query": "fast quick", "operator": "or" } } } -> Option D

4. Quick Check:

   Use operator 'or' for any word match [OK]

Hint: Use operator 'or' to match any word in query [OK]

Common Mistakes:

• Using 'and' when 'or' is needed
• Using 'OR' in the search text instead of operator
• Using invalid operator like 'not'