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?

Practice

1. What is the main purpose of a boosting query in Elasticsearch?

easy

A. To filter out documents without a specific field

B. To sort results alphabetically

C. To increase the relevance score of some results and decrease others

D. To aggregate data by terms

Solution

1. Step 1: Understand boosting query purpose

   A boosting query is designed to adjust the relevance scores of search results by raising some and lowering others.

2. Step 2: Compare with other query types

   Sorting alphabetically, filtering, and aggregating are different Elasticsearch features unrelated to boosting.

3. Final Answer:

   To increase the relevance score of some results and decrease others -> Option C

4. Quick Check:

   Boosting query = Adjust relevance scores [OK]

Hint: Boosting changes scores, not sorting or filtering [OK]

Common Mistakes:

• Confusing boosting with sorting
• Thinking boosting filters documents
• Mixing boosting with aggregation

2. Which of the following is the correct syntax snippet for a boosting query in Elasticsearch?

easy

A. { "boosting": { "positive": { "term": { "field": "value" } }, "negative": { "term": { "field": "other" } } } }

B. { "boost": { "match": { "field": "value" }, "boost_factor": 2 } }

C. { "boosting_query": { "positive": { "term": { "field": "value" } }, "negative": { "term": { "field": "other" } } } }

D. { "boosting": { "positive": { "match": { "field": "value" } }, "negative": { "match": { "field": "other" } }, "negative_boost": 0.5 } }

Solution

1. Step 1: Identify correct boosting query structure

   The correct syntax uses the "boosting" key with "positive", "negative", and "negative_boost" fields.

2. Step 2: Check each option

   The snippet using "boosting" with "positive" match query, "negative" match query, and "negative_boost": 0.5 matches the correct structure. Others miss "negative_boost" or use incorrect keys like "boost" or "boosting_query".

3. Final Answer:

   { "boosting": { "positive": { "match": { "field": "value" } }, "negative": { "match": { "field": "other" } }, "negative_boost": 0.5 } } -> Option D

4. Quick Check:

   Boosting query syntax = { "boosting": { "positive": { "match": { "field": "value" } }, "negative": { "match": { "field": "other" } }, "negative_boost": 0.5 } } [OK]

Hint: Look for "boosting" with positive, negative, and negative_boost keys [OK]

Common Mistakes:

• Using wrong key names like "boost" or "boosting_query"
• Omitting "negative_boost"
• Using incorrect query types inside positive/negative

3. Given this boosting query, what will happen to documents matching the negative query?

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

medium

A. Their relevance scores will be increased by 0.3

B. Their relevance scores will be decreased by multiplying by 0.3

C. They will be excluded from results

D. They will have the same score as positive matches

Solution

1. Step 1: Understand negative_boost effect

   The negative_boost value multiplies the score of documents matching the negative query, lowering their relevance.

2. Step 2: Apply to given query

   Documents matching "banana" will have their scores multiplied by 0.3, reducing their rank but not excluding them.

3. Final Answer:

   Their relevance scores will be decreased by multiplying by 0.3 -> Option B

4. Quick Check:

   negative_boost multiplies score down [OK]

Hint: Negative matches get score multiplied by negative_boost < 1 [OK]

Common Mistakes:

• Thinking negative_boost adds to score
• Assuming negative matches are filtered out
• Confusing negative_boost with positive boost

4. Identify the error in this boosting query:

{
  "boosting": {
    "positive": { "match": { "content": "dog" } },
    "negative": { "match": { "content": "cat" } }
  }
}

medium

A. Missing "negative_boost" field

B. Incorrect query type inside positive

C. Wrong key name "boosting" should be "boost"

D. Positive and negative queries cannot use the same field

Solution

1. Step 1: Check required fields in boosting query

   A boosting query requires "positive", "negative", and "negative_boost" fields to work correctly.

2. Step 2: Identify missing element

   The provided query lacks the "negative_boost" field, which defines how much to reduce negative matches.

3. Final Answer:

   Missing "negative_boost" field -> Option A

4. Quick Check:

   Boosting query needs negative_boost [OK]

Hint: Always include negative_boost in boosting queries [OK]

Common Mistakes:

• Omitting negative_boost
• Using wrong key names
• Assuming same field usage is invalid

5. You want to boost documents containing "premium" in the category field and reduce scores of documents containing "basic" in the same field by half. Which boosting query correctly achieves this?

hard

A. { "boosting": { "positive": { "term": { "category": "premium" } }, "negative": { "term": { "category": "basic" } }, "negative_boost": 0.5 } }

B. { "boosting": { "positive": { "match": { "category": "premium" } }, "negative": { "match": { "category": "basic" } }, "negative_boost": 2 } }

C. { "boost": { "term": { "category": "premium" }, "boost_factor": 2 } }

D. { "boosting": { "positive": { "term": { "category": "basic" } }, "negative": { "term": { "category": "premium" } }, "negative_boost": 0.5 } }

Solution

1. Step 1: Identify positive and negative queries

   Positive query should match "premium" category to boost, negative query should match "basic" to reduce score.

2. Step 2: Check negative_boost value

   Negative boost of 0.5 reduces scores of negative matches by half, which matches the requirement.

3. Step 3: Verify options

   { "boosting": { "positive": { "term": { "category": "premium" } }, "negative": { "term": { "category": "basic" } }, "negative_boost": 0.5 } } correctly uses term queries and negative_boost 0.5. Other options either use negative_boost greater than 1, are not boosting queries, or reverse positive and negative.

4. Final Answer:

   { "boosting": { "positive": { "term": { "category": "premium" } }, "negative": { "term": { "category": "basic" } }, "negative_boost": 0.5 } } -> Option A

5. Quick Check:

   Positive = premium, negative = basic, negative_boost = 0.5 [OK]

Hint: Positive boosts, negative reduces with negative_boost < 1 [OK]

Common Mistakes:

• Swapping positive and negative queries
• Using negative_boost greater than 1
• Using boost instead of boosting query