Multi-match query in Elasticsearch - Time & Space Complexity

Time Complexity: Multi-match query

O(n * f)

Understanding Time Complexity

When using a multi-match query in Elasticsearch, it is important to understand how the search time changes as the amount of data grows.

We want to know how the number of operations increases when searching across multiple fields.

Scenario Under Consideration

Analyze the time complexity of the following multi-match query.

{
  "query": {
    "multi_match": {
      "query": "search text",
      "fields": ["title", "description", "content"]
    }
  }
}
    

This query searches the text "search text" across three fields in each document.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Searching the query text in each specified field of every document.
• How many times: For each document, the search runs once per field listed (here 3 fields), so it repeats for all documents times number of fields.

How Execution Grows With Input

As the number of documents grows, the search checks more entries. Also, more fields mean more checks per document.

Input Size (n documents)	Approx. Operations
10	30 (10 docs x 3 fields)
100	300 (100 docs x 3 fields)
1000	3000 (1000 docs x 3 fields)

Pattern observation: The operations grow directly with the number of documents and fields checked.

Final Time Complexity

Time Complexity: O(n * f)

This means the search time grows linearly with the number of documents (n) and the number of fields (f) searched.

Common Mistake

[X] Wrong: "Searching multiple fields does not affect the search time much because it's just one query."

[OK] Correct: Each field adds a separate search operation per document, so more fields mean more work and longer search time.

Interview Connect

Understanding how multi-field searches scale helps you explain performance considerations clearly and shows you grasp how search engines work under the hood.

Self-Check

"What if we added more fields to the multi-match query? How would the time complexity change?"