First search query in Elasticsearch - Time & Space Complexity

Time Complexity: First search query

O(k)

Understanding Time Complexity

When we run a search query in Elasticsearch, we want to know how the time it takes changes as we add more data.

We ask: How does the search time grow when the number of documents increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /my-index/_search
{
  "query": {
    "match": {
      "title": "elasticsearch"
    }
  }
}
    

This query searches for documents in "my-index" where the "title" field contains the word "elasticsearch".

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Elasticsearch scans the inverted index entries for the word "elasticsearch".
• How many times: It processes postings for each document containing that word, which depends on how many documents match.

How Execution Grows With Input

As the number of documents grows, Elasticsearch looks up the word in its index and checks matching documents.

Input Size (n)	Approx. Operations
10	Checks a few postings for "elasticsearch"
100	Checks more postings, roughly 10 times more
1000	Checks many postings, about 100 times more than 10 docs

Pattern observation: The work grows roughly with the number of documents that contain the search word.

Final Time Complexity

Time Complexity: O(k)

This means the search time grows in proportion to the number of documents matching the query term.

Common Mistake

[X] Wrong: "The search time depends on the total number of documents in the index."

[OK] Correct: Elasticsearch uses an index to jump directly to matching documents, so it does not scan all documents, only those containing the search term.

Interview Connect

Understanding how search time grows helps you explain how Elasticsearch handles queries efficiently, a useful skill for real-world search applications.

Self-Check

"What if we changed the query to search for multiple words combined with AND? How would the time complexity change?"