Boosting query in Elasticsearch - Time & Space Complexity

Time Complexity: Boosting query

O(n)

Understanding Time Complexity

When using a boosting query in Elasticsearch, we want to know how the search time changes as the data grows.

We ask: How does adding boosting affect the work Elasticsearch does?

Scenario Under Consideration

Analyze the time complexity of the following boosting query.

{
  "query": {
    "boosting": {
      "positive": { "match": { "title": "apple" } },
      "negative": { "match": { "title": "banana" } },
      "negative_boost": 0.2
    }
  }
}
    

This query finds documents with "apple" in the title and lowers the score of those with "banana".

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Elasticsearch searches the index twice--once for the positive match and once for the negative match.
• How many times: Each search scans relevant documents independently.

How Execution Grows With Input

As the number of documents grows, Elasticsearch does more work for each part of the boosting query.

Input Size (n)	Approx. Operations
10	About 20 document checks (10 for positive + 10 for negative)
100	About 200 document checks
1000	About 2000 document checks

Pattern observation: The work roughly doubles because it runs two searches, one positive and one negative.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the number of documents because it runs two simple searches.

Common Mistake

[X] Wrong: "Boosting queries run twice as slow as a single search because they do double the work."

[OK] Correct: While boosting runs two searches, Elasticsearch optimizes by using indexes and caching, so the slowdown is not always exactly double and depends on data and query complexity.

Interview Connect

Understanding how boosting affects search time helps you explain trade-offs in search design and shows you can think about query performance clearly.

Self-Check

What if we changed the negative query to a more complex filter? How would the time complexity change?