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?"