Bool query in depth in Elasticsearch - Time & Space Complexity

Time Complexity: Bool query in depth

O(n)

Understanding Time Complexity

When using a bool query in Elasticsearch, it is important to understand how the query's execution time changes as the number of conditions grows.

We want to know how the cost of combining multiple queries with AND, OR, and NOT changes with more clauses.

Scenario Under Consideration

Analyze the time complexity of the following bool query.

{
  "query": {
    "bool": {
      "must": [
        { "match": { "field1": "value1" } },
        { "term": { "field2": "value2" } }
      ],
      "should": [
        { "range": { "field3": { "gte": 10 } } }
      ],
      "must_not": [
        { "exists": { "field": "field4" } }
      ]
    }
  }
}
    

This query combines multiple conditions using must (AND), should (OR), and must_not (NOT) clauses.

Identify Repeating Operations

Look at how many times the query engine processes each clause.

• Primary operation: Evaluating each clause in the bool query.
• How many times: Once per clause inside must, should, and must_not arrays.

How Execution Grows With Input

As you add more clauses, the query engine must check each one separately.

Input Size (n)	Approx. Operations
3 clauses	3 checks
10 clauses	10 checks
100 clauses	100 checks

Pattern observation: The number of operations grows directly with the number of clauses.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the bool query grows linearly with the number of clauses.

Common Mistake

[X] Wrong: "Adding more clauses won't affect query speed much because Elasticsearch is fast."

[OK] Correct: Each clause adds work, so more clauses mean more checks and longer execution time.

Interview Connect

Understanding how bool queries scale helps you write efficient search queries and shows you can think about performance in real projects.

Self-Check

What if we replaced the must array with nested bool queries? How would that affect the time complexity?

Practice

1. Which clause in an Elasticsearch bool query is used to exclude documents from the search results?

easy

A. must

B. should

C. must_not

D. filter

Solution

1. Step 1: Understand bool query clauses

   The bool query has four main clauses: must (required matches), filter (fast filtering), should (optional matches), and must_not (exclusions).

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 C

4. Quick Check:

   Exclusion = must_not [OK]

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

Common Mistakes:

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

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

easy

A. "bool": { "must": [ { "term": { "status": "active" } } ] }

B. "bool": { "must_not": { "term": { "status": "active" } } }

C. "bool": { "should": { "term": { "status": "active" } } }

D. "bool": { "filter": [ { "term": { "status": "active" } } ] }

Solution

1. Step 1: Recall bool query syntax for filter

   The filter clause expects an array of queries inside the bool query, e.g., "filter": [ { ... } ].

2. Step 2: Match correct syntax

   "bool": { "filter": [ { "term": { "status": "active" } } ] } correctly uses "filter": [ { "term": { "status": "active" } } ] which is valid syntax.

3. Final Answer:

   "bool": { "filter": [ { "term": { "status": "active" } } ] } -> Option D

4. Quick Check:

   Filter clause uses array syntax [OK]

Hint: Filter clause always uses an array of queries [OK]

Common Mistakes:

• Using object instead of array for filter
• Confusing must_not or should syntax
• Missing brackets around filter queries

3. Given this bool query snippet, what documents will it match?

{ "bool": { "must": [ { "match": { "title": "python" } } ], "should": [ { "term": { "tags": "programming" } } ], "must_not": [ { "term": { "status": "draft" } } ] } }

medium

A. Documents with title containing 'python', optionally tagged 'programming', excluding drafts

B. Documents tagged 'programming' only, ignoring title and status

C. Documents with status 'draft' and title 'python'

D. Documents with title 'python' or status 'draft'

Solution

1. Step 1: Analyze must clause

   The must clause requires documents to have 'python' in the title.

2. Step 2: Analyze should and must_not clauses

   The should clause boosts documents tagged 'programming' but is optional. The must_not clause excludes documents with status 'draft'.

3. Final Answer:

   Documents with title containing 'python', optionally tagged 'programming', excluding drafts -> Option A

4. Quick Check:

   Must + should + must_not = Documents with title containing 'python', optionally tagged 'programming', excluding drafts [OK]

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

Common Mistakes:

• Thinking should is required
• Including documents with status 'draft'
• Ignoring must clause

4. Identify the error in this bool query snippet:

{ "bool": { "must": { "term": { "user": "kimchy" } }, "filter": { "term": { "status": "active" } } } }

medium

A. Missing "should" clause

B. "must" and "filter" should be arrays, not single objects

C. Using "term" inside bool is invalid

D. The query is correct as is

Solution

1. Step 1: Check bool clause types

   In bool queries, must and filter expect arrays of queries, not single objects.

2. Step 2: Identify syntax error

   Here, both must and filter are single objects, which is invalid syntax.

3. Final Answer:

   "must" and "filter" should be arrays, not single objects -> Option B

4. Quick Check:

   Bool clauses require arrays [OK]

Hint: Bool clauses must and filter need arrays [OK]

Common Mistakes:

• Using single object instead of array
• Forgetting to wrap queries in []
• Assuming should is mandatory

5. You want to find documents where the category is 'books' and either the author is 'Alice' or the year is after 2015, but exclude any documents marked as archived. Which bool query structure correctly implements this?

hard

A. { "bool": { "must": [ { "term": { "category": "books" } } ], "should": [ { "term": { "author": "Alice" } }, { "range": { "year": { "gt": 2015 } } } ], "must_not": [ { "term": { "status": "archived" } } ] } }

B. { "bool": { "filter": [ { "term": { "category": "books" } }, { "term": { "author": "Alice" } } ], "must_not": [ { "term": { "status": "archived" } } ], "should": [ { "range": { "year": { "gt": 2015 } } } ] } }

C. { "bool": { "must": [ { "term": { "category": "books" } }, { "term": { "author": "Alice" } } ], "must_not": [ { "term": { "status": "archived" } } ], "should": [ { "range": { "year": { "gt": 2015 } } } ] } }

D. { "bool": { "must": [ { "term": { "category": "books" } } ], "filter": [ { "term": { "author": "Alice" } }, { "range": { "year": { "gt": 2015 } } } ], "must_not": [ { "term": { "status": "archived" } } ] } }

Solution

1. Step 1: Identify required and optional conditions

   The category must be 'books' (required), and either author is 'Alice' or year > 2015 (optional, so use should).

2. Step 2: Exclude archived documents

   Use must_not to exclude documents with status 'archived'.

3. Step 3: Match query structure

   { "bool": { "must": [ { "term": { "category": "books" } } ], "should": [ { "term": { "author": "Alice" } }, { "range": { "year": { "gt": 2015 } } } ], "must_not": [ { "term": { "status": "archived" } } ] } } correctly uses must for category, should for author or year, and must_not for exclusion.

4. Final Answer:

   Option A's bool query structure -> Option A

5. Quick Check:

   Must + should + must_not for conditions [OK]

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

Common Mistakes:

• Putting author and year in must (both required)
• Using filter instead of should for alternatives
• Missing must_not for exclusion