Relevance score (_score) in Elasticsearch - Time & Space Complexity

Time Complexity: Relevance score (_score)

O(n)

Understanding Time Complexity

When Elasticsearch searches documents, it calculates a relevance score called _score to rank results.

We want to understand how the time to calculate these scores grows as we search more documents.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch query snippet.

GET /my_index/_search
{
  "query": {
    "match": {
      "content": "search term"
    }
  }
}
    

This query searches documents matching "search term" and calculates a relevance score for each matched document.

Identify Repeating Operations

Look at what repeats when Elasticsearch processes this query.

• Primary operation: Calculating the _score for each matched document.
• How many times: Once for every document that matches the query.

How Execution Grows With Input

As the number of matched documents grows, the number of score calculations grows too.

Input Size (matched docs)	Approx. Operations (score calculations)
10	10
100	100
1000	1000

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

Final Time Complexity

Time Complexity: O(n)

This means the time to calculate relevance scores grows linearly with the number of matched documents.

Common Mistake

[X] Wrong: "Calculating the _score is constant time no matter how many documents match."

[OK] Correct: Each matched document needs its own score calculation, so more matches mean more work.

Interview Connect

Understanding how scoring scales helps you explain search performance clearly and shows you grasp how Elasticsearch handles queries behind the scenes.

Self-Check

"What if we added a filter that reduces matched documents before scoring? How would that affect the time complexity?"