Match phrase query in Elasticsearch - Time & Space Complexity

Time Complexity: Match phrase query

O(n)

Understanding Time Complexity

When we use a match phrase query in Elasticsearch, it looks for exact sequences of words in documents.

We want to understand how the time to find these phrases grows as we search more documents or longer texts.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch match phrase query.

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

This query searches for documents where the words "quick brown fox" appear together in that exact order in the "content" field.

Identify Repeating Operations

Look at what repeats when Elasticsearch runs this query.

• Primary operation: Scanning each document's "content" field to find the phrase.
• How many times: Once per document in the search scope.

How Execution Grows With Input

As the number of documents grows, Elasticsearch checks more texts for the phrase.

Input Size (n documents)	Approx. Operations
10	10 phrase checks
100	100 phrase checks
1000	1000 phrase checks

Pattern observation: The work grows directly with the number of documents checked.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the phrase grows linearly with the number of documents searched.

Common Mistake

[X] Wrong: "The phrase query checks only a few documents, so it is always very fast."

[OK] Correct: Even if the phrase is rare, Elasticsearch must scan many documents to find matches, so time grows with document count.

Interview Connect

Understanding how phrase queries scale helps you explain search performance clearly and shows you know how search engines work under the hood.

Self-Check

"What if we changed the match phrase query to a simple match query? How would the time complexity change?"