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?"

Practice

1. What is the main purpose of a multi-match query in Elasticsearch?

easy

A. To search multiple fields with a single query

B. To update multiple documents at once

C. To delete multiple indexes simultaneously

D. To create multiple indexes in one request

Solution

1. Step 1: Understand the multi-match query concept

   A multi-match query allows searching across several fields in one query, making it easier to find matches in different parts of documents.

2. Step 2: Compare with other options

   The other options describe operations like creating indexes, updating documents, or deleting indexes, which are not the purpose of multi-match queries.

3. Final Answer:

   To search multiple fields with a single query -> Option A

4. Quick Check:

   Multi-match = search multiple fields [OK]

Hint: Multi-match searches many fields at once [OK]

Common Mistakes:

• Confusing multi-match with update or delete operations
• Thinking it creates or deletes indexes
• Assuming it searches only one field

2. Which of the following is the correct syntax to perform a multi-match query searching for the word "apple" in fields "title" and "description"?

easy

A. { "multi_match": { "query": "apple", "fields": ["title", "description"] } }

B. { "match": { "query": "apple", "fields": ["title", "description"] } }

C. { "multi_match": { "fields": ["title", "description"] } }

D. { "multi_match": { "query": "apple" } }

Solution

1. Step 1: Identify required keys in multi-match query

   A multi-match query requires a "query" key with the search term and a "fields" key listing the fields to search.

2. Step 2: Check each option for correct syntax

   { "multi_match": { "query": "apple", "fields": ["title", "description"] } } correctly includes both "query" and "fields" keys. { "match": { "query": "apple", "fields": ["title", "description"] } } uses "match" instead of "multi_match". { "multi_match": { "fields": ["title", "description"] } } misses the "query" key. { "multi_match": { "query": "apple" } } misses the "fields" key.

3. Final Answer:

   { "multi_match": { "query": "apple", "fields": ["title", "description"] } } -> Option A

4. Quick Check:

   multi_match needs query and fields [OK]

Hint: multi_match needs both query and fields keys [OK]

Common Mistakes:

• Using 'match' instead of 'multi_match'
• Omitting the 'query' key
• Omitting the 'fields' key

3. Given this multi-match query, what will be the effect?

{
  "multi_match": {
    "query": "quick fox",
    "fields": ["title", "content"],
    "type": "phrase"
  }
}

medium

A. Searches only the title field for the phrase "quick fox"

B. Searches for documents containing "quick" or "fox" anywhere in title or content

C. Searches for documents where "quick fox" appears as a phrase in either title or content

D. Searches for documents with exact match "quick fox" in all fields

Solution

1. Step 1: Understand the 'type' parameter in multi-match

   The "type": "phrase" option makes the query look for the exact phrase "quick fox" in the specified fields.

2. Step 2: Check fields and matching behavior

   The fields are "title" and "content", so the phrase must appear in either field, not necessarily both.

3. Final Answer:

   Searches for documents where "quick fox" appears as a phrase in either title or content -> Option C

4. Quick Check:

   type phrase = exact phrase match in fields [OK]

Hint: type phrase means exact phrase search [OK]

Common Mistakes:

• Thinking it searches for words separately (not phrase)
• Assuming it searches only one field
• Believing it requires phrase in all fields

4. Identify the error in this multi-match query:

{
  "multi_match": {
    "query": "data",
    "fields": "title, description"
  }
}

medium

A. "query" should be an array of words

B. "fields" should be an array, not a string

C. "multi_match" should be "match"

D. "fields" should be omitted for multi-match

Solution

1. Step 1: Check the type of "fields" value

   The "fields" key must be an array of field names, not a single string with commas.

2. Step 2: Validate other keys

   The "query" key is correctly a string. "multi_match" is the correct query type. "fields" should not be omitted.

3. Final Answer:

   "fields" should be an array, not a string -> Option B

4. Quick Check:

   fields must be array, not comma string [OK]

Hint: Fields must be an array, not a comma string [OK]

Common Mistakes:

• Passing fields as a comma-separated string
• Changing multi_match to match incorrectly
• Thinking query must be an array

5. You want to search for the term "coffee" giving higher importance to the "title" field than "description" and "tags" fields. Which multi-match query correctly applies this weighting?

hard

A. { "multi_match": { "query": "coffee", "fields": ["title", "description", "tags"], "boost": 3 } }

B. { "multi_match": { "query": "coffee", "fields": ["title", "description^3", "tags"] } }

C. { "multi_match": { "query": "coffee", "fields": ["title", "description", "tags"], "type": "boost" } }

D. { "multi_match": { "query": "coffee", "fields": ["title^3", "description", "tags"] } }

Solution

1. Step 1: Understand field boosting syntax

   To give more importance to a field, add a caret (^) and a boost number after the field name, e.g., "title^3".

2. Step 2: Check each option for correct boosting

   { "multi_match": { "query": "coffee", "fields": ["title^3", "description", "tags"] } } boosts "title" by 3, others default. { "multi_match": { "query": "coffee", "fields": ["title", "description^3", "tags"] } } boosts "description" incorrectly. { "multi_match": { "query": "coffee", "fields": ["title", "description", "tags"], "boost": 3 } } tries to boost all fields equally with "boost" key, which is invalid here. { "multi_match": { "query": "coffee", "fields": ["title", "description", "tags"], "type": "boost" } } uses an invalid "type" value.

3. Final Answer:

   { "multi_match": { "query": "coffee", "fields": ["title^3", "description", "tags"] } } -> Option D

4. Quick Check:

   Use ^number to boost fields [OK]

Hint: Boost fields with ^number after field name [OK]

Common Mistakes:

• Boosting wrong field
• Using 'boost' key incorrectly
• Setting invalid 'type' value