Saved searches and filters in Elasticsearch - Time & Space Complexity

Time Complexity: Saved searches and filters

O(n)

Understanding Time Complexity

When using saved searches and filters in Elasticsearch, it's important to understand how the time to get results changes as your data grows.

We want to know how the search and filter operations scale with more data and saved queries.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch query using a saved filter.

GET /products/_search
{
  "query": {
    "bool": {
      "filter": [
        { "term": { "category": "electronics" } },
        { "range": { "price": { "lte": 1000 } } }
      ]
    }
  }
}
    

This query searches the products index, applying filters for category and price range.

Identify Repeating Operations

Let's find the repeated steps in this search with filters.

• Primary operation: Elasticsearch scans matching documents using the filters.
• How many times: It checks each document in the filtered index segments.

How Execution Grows With Input

As the number of documents grows, the search engine must check more entries to apply filters.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the saved search with filters grows linearly as the number of documents increases.

Common Mistake

[X] Wrong: "Using saved filters makes the search time constant no matter how many documents there are."

[OK] Correct: Saved filters help reuse queries but the search still needs to check documents, so time grows with data size.

Interview Connect

Understanding how saved searches and filters affect performance shows you can think about real data growth and system behavior, a valuable skill in many projects.

Self-Check

What if we added an index on the category field? How would that change the time complexity of the filtered search?