Time Complexity: Dis max query
O(n)
0
0
Dis max query in Elasticsearch - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time taken by a Dis max query changes as we add more queries inside it.
How does the number of queries affect the work Elasticsearch does?
Scenario Under Consideration
Analyze the time complexity of the following Dis max query.
{
"dis_max": {
"queries": [
{ "match": { "title": "apple" } },
{ "match": { "description": "apple" } },
{ "match": { "content": "apple" } }
],
"tie_breaker": 0.7
}
}
This query searches multiple fields and picks the best score among them, adding a small bonus from others.
Identify Repeating Operations
Look at what repeats when this query runs.
- Primary operation: Running each subquery (match) on the documents.
- How many times: Once per subquery inside the "queries" list.
How Execution Grows With Input
As we add more subqueries, Elasticsearch runs more searches to find the best score.
| Number of Subqueries (n) | Approx. Operations |
|---|---|
| 3 | 3 searches on documents |
| 10 | 10 searches on documents |
| 100 | 100 searches on documents |
Pattern observation: The work grows directly with the number of subqueries.
Final Time Complexity
Time Complexity: O(n)
This means the time grows linearly with the number of subqueries inside the Dis max query.
Common Mistake
[X] Wrong: "Adding more subqueries won't affect performance much because only the best score is used."
[OK] Correct: Even though only the best score is kept, Elasticsearch still runs all subqueries fully, so more subqueries mean more work.
Interview Connect
Understanding how query parts add up helps you explain search performance clearly and shows you can think about scaling queries well.
Self-Check
What if we replaced the Dis max query with a bool query using "should" clauses? How would the time complexity change?