Bool query (must, should, must_not, filter) in Elasticsearch - Time & Space Complexity

Time Complexity: Bool query (must, should, must_not, filter)

O(n)

Understanding Time Complexity

When using a bool query in Elasticsearch, it's important to know how the search time changes as we add more conditions.

We want to understand how the number of conditions affects the work Elasticsearch does.

Scenario Under Consideration

Analyze the time complexity of the following bool query.

{
  "query": {
    "bool": {
      "must": [ { "match": { "title": "search" } } ],
      "should": [ { "term": { "status": "published" } } ],
      "must_not": [ { "range": { "date": { "lt": "2023-01-01" } } } ],
      "filter": [ { "term": { "category": "books" } } ]
    }
  }
}
    

This query combines several conditions to find documents matching all must, some should, excluding must_not, and applying filters.

Identify Repeating Operations

Look at how many times Elasticsearch checks each condition.

• Primary operation: Checking each document against all conditions in must, should, must_not, and filter.
• How many times: Once per document for each condition group.

How Execution Grows With Input

As the number of documents grows, Elasticsearch checks each document against the bool query conditions.

Input Size (n)	Approx. Operations
10	About 10 document checks
100	About 100 document checks
1000	About 1000 document checks

Pattern observation: The work grows roughly in direct proportion to the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of documents to check.

Common Mistake

[X] Wrong: "Adding more conditions in must, should, or filter does not affect query time much."

[OK] Correct: Each added condition means more checks per document, so the total work increases with more conditions.

Interview Connect

Understanding how bool queries scale helps you explain how search engines handle complex filters efficiently.

Self-Check

What if we added nested bool queries inside must? How would the time complexity change?

Practice

1. Which clause in an Elasticsearch bool query is used to exclude documents that match a condition?

easy

A. must

B. must_not

C. should

D. filter

Solution

1. Step 1: Understand bool query clauses

   The bool query has four main clauses: must (required), should (optional), must_not (exclude), and filter (limit without scoring).

2. Step 2: Identify exclusion clause

   The must_not clause excludes documents that match its conditions from the results.

3. Final Answer:

   must_not -> Option B

4. Quick Check:

   Exclude = must_not [OK]

Hint: Exclude with must_not clause in bool query [OK]

Common Mistakes:

• Confusing must_not with must
• Using should to exclude documents
• Thinking filter excludes documents

2. Which of the following is the correct syntax to add a must clause inside a bool query in Elasticsearch?

easy

A. "bool": { "must": [ { "match": { "field": "value" } } ] }

B. "bool": { "must": ( { "match": { "field": "value" } } ) }

C. "bool": { "must": "match": { "field": "value" } }

D. "bool": { "must": { "match": { "field": "value" } } }

Solution

1. Step 1: Recall bool must clause syntax

   The must clause expects an array of query objects inside the bool query.

2. Step 2: Check each option's syntax

   "bool": { "must": [ { "match": { "field": "value" } } ] } correctly uses an array with one match query object. The other options use incorrect types or missing brackets.

3. Final Answer:

   "bool": { "must": [ { "match": { "field": "value" } } ] } -> Option A

4. Quick Check:

   Must clause = array of queries [OK]

Hint: Must clause requires an array of query objects [OK]

Common Mistakes:

• Using object instead of array for must
• Missing brackets around match query
• Using parentheses instead of brackets

3. Given this bool query snippet, which documents will be matched?

{
  "bool": {
    "must": [{ "term": { "status": "active" }}],
    "should": [{ "term": { "role": "admin" }}],
    "must_not": [{ "term": { "banned": true }}]
  }
}

medium

A. Documents with status 'active' and role 'admin', excluding banned ones

B. Documents with status 'active' or role 'admin', including banned ones

C. Documents with role 'admin' only, excluding banned ones

D. Documents with status 'active', optionally role 'admin', excluding banned ones

Solution

1. Step 1: Analyze must clause effect

   The must clause requires documents to have status: active.

2. Step 2: Analyze should and must_not clauses

   The should clause means documents with role: admin are preferred but not required. The must_not clause excludes documents where banned is true.

3. Final Answer:

   Documents with status 'active', optionally role 'admin', excluding banned ones -> Option D

4. Quick Check:

   Must + optional should + exclude must_not = Documents with status 'active', optionally role 'admin', excluding banned ones [OK]

Hint: Must is required, should is optional, must_not excludes [OK]

Common Mistakes:

• Thinking should is required
• Ignoring must_not exclusion
• Confusing must and should roles

4. Identify the error in this bool query:

{
  "bool": {
    "must": { "match": { "title": "Elasticsearch" } },
    "filter": { "term": { "status": "published" } },
    "must_not": [ { "term": { "archived": true } } ]
  }
}

medium

A. "must" should be an array, not an object

B. "filter" cannot be used with "must_not"

C. "must_not" should be an object, not an array

D. The query is correct as is

Solution

1. Step 1: Check must clause format

   The must clause expects an array of query objects, but here it is given as a single object.

2. Step 2: Validate other clauses

   The filter and must_not clauses are correctly formatted as an object and an array respectively.

3. Final Answer:

   "must" should be an array, not an object -> Option A

4. Quick Check:

   Must clause = array required [OK]

Hint: Must clause must always be an array [OK]

Common Mistakes:

• Using object instead of array for must
• Thinking filter and must_not conflict
• Using array for must_not incorrectly

5. You want to find documents where the category is 'books' and the price is less than 20, but exclude those that are out of stock. Which bool query correctly implements this?

hard

A. { "bool": { "should": [ { "term": { "category": "books" } }, { "range": { "price": { "lt": 20 } } } ], "must_not": [ { "term": { "stock": "out" } } ] } }

B. { "bool": { "filter": [ { "term": { "category": "books" } }, { "range": { "price": { "lt": 20 } } } ], "must_not": { "term": { "stock": "out" } } } }

C. { "bool": { "must": [ { "term": { "category": "books" } }, { "range": { "price": { "lt": 20 } } } ], "must_not": [ { "term": { "stock": "out" } } ] } }

D. { "bool": { "must": { "term": { "category": "books" } }, "filter": { "range": { "price": { "lt": 20 } } }, "must_not": [ { "term": { "stock": "out" } } ] } }

Solution

1. Step 1: Identify required conditions

   Documents must have category: books and price < 20. Both are required, so they go in must as an array.

2. Step 2: Exclude out of stock documents

   Documents with stock: out must be excluded, so use must_not with an array of term queries.

3. Step 3: Check each option

   { "bool": { "must": [ { "term": { "category": "books" } }, { "range": { "price": { "lt": 20 } } } ], "must_not": [ { "term": { "stock": "out" } } ] } } correctly uses must array for required conditions and must_not array for exclusion. { "bool": { "filter": [ { "term": { "category": "books" } }, { "range": { "price": { "lt": 20 } } } ], "must_not": { "term": { "stock": "out" } } } } uses filter which is okay but must_not is an object, not array. { "bool": { "should": [ { "term": { "category": "books" } }, { "range": { "price": { "lt": 20 } } } ], "must_not": [ { "term": { "stock": "out" } } ] } } uses should which makes conditions optional, wrong here. { "bool": { "must": { "term": { "category": "books" } }, "filter": { "range": { "price": { "lt": 20 } } }, "must_not": [ { "term": { "stock": "out" } } ] } } uses must as object and filter as object, mixing styles incorrectly.

4. Final Answer:

   { "bool": { "must": [ { "term": { "category": "books" } }, { "range": { "price": { "lt": 20 } } } ], "must_not": [ { "term": { "stock": "out" } } ] } } -> Option C

5. Quick Check:

   Must array + must_not array for exclusion [OK]

Hint: Use must array for required, must_not array to exclude [OK]

Common Mistakes:

• Using should instead of must for required filters
• Using object instead of array for must or must_not
• Mixing filter and must incorrectly