Search-as-you-type field in Elasticsearch - Time & Space Complexity

Time Complexity: Search-as-you-type field

O(k)

Understanding Time Complexity

When using a search-as-you-type field in Elasticsearch, it is important to understand how the search speed changes as the data grows.

We want to know how the number of operations grows when more documents or longer queries are involved.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch query using a search-as-you-type field.

GET /my_index/_search
{
  "query": {
    "match": {
      "name.search_as_you_type": "appl"
    }
  }
}
    

This query searches the "name" field with a search-as-you-type mapping, matching documents as the user types partial input.

Identify Repeating Operations

Look at what repeats when this query runs.

• Primary operation: Elasticsearch scans inverted index terms matching the typed prefix.
• How many times: It checks terms that start with the input prefix, then fetches matching documents for each term.

How Execution Grows With Input

As the input prefix gets longer, fewer terms match, so fewer documents are checked.

Input Size (prefix length)	Approx. Operations
1 (e.g., "a")	Many terms match, many documents checked
3 (e.g., "app")	Fewer terms, fewer documents
5 (e.g., "apple")	Very few terms, minimal documents

Pattern observation: The longer the typed prefix, the fewer terms and documents Elasticsearch processes, so execution cost decreases with input length.

Final Time Complexity

Time Complexity: O(k)

This means the search cost grows roughly with the number of matching terms and documents for the typed prefix, which depends on prefix length and index size.

Common Mistake

[X] Wrong: "The search cost is always the same no matter how long the typed input is."

[OK] Correct: Actually, longer prefixes narrow down matches, so fewer terms and documents are checked, reducing cost.

Interview Connect

Understanding how search-as-you-type queries scale helps you explain real-world search performance and design better user experiences.

Self-Check

What if we changed the search-as-you-type field to a standard text field? How would the time complexity change?

Practice

1. What is the main purpose of a search_as_you_type field in Elasticsearch?

easy

A. To provide instant search results as the user types each character

B. To store large binary files efficiently

C. To perform complex aggregations on numeric data

D. To index documents only after full text is entered

Solution

1. Step 1: Understand the purpose of search_as_you_type

   The search_as_you_type field is designed to help users get search results instantly as they type, improving user experience.

2. Step 2: Compare with other options

   Options B, C, and D describe unrelated Elasticsearch features like binary storage, aggregations, or delayed indexing, which are not related to search_as_you_type.

3. Final Answer:

   To provide instant search results as the user types each character -> Option A

4. Quick Check:

   search_as_you_type = instant search while typing [OK]

Hint: Remember: search_as_you_type means live search suggestions [OK]

Common Mistakes:

• Confusing search_as_you_type with binary or numeric fields
• Thinking it delays indexing until full input
• Assuming it is for aggregations

2. Which is the correct way to define a search_as_you_type field in an Elasticsearch mapping?

easy

A. "title": { "type": "text" }

B. "title": { "type": "completion" }

C. "title": { "type": "keyword" }

D. "title": { "type": "search_as_you_type" }

Solution

1. Step 1: Identify the correct field type for search-as-you-type

   The search_as_you_type field type must be explicitly set as "type": "search_as_you_type" in the mapping.

2. Step 2: Eliminate other field types

   "title": { "type": "text" } uses text, which is for full text search but not optimized for search-as-you-type. "title": { "type": "keyword" } uses keyword, which is for exact matches. "title": { "type": "completion" } uses completion, which is for autocomplete but different from search_as_you_type.

3. Final Answer:

   "title": { "type": "search_as_you_type" } -> Option D

4. Quick Check:

   Mapping type for search-as-you-type = search_as_you_type [OK]

Hint: Use type "search_as_you_type" exactly in mapping [OK]

Common Mistakes:

• Using "text" instead of "search_as_you_type"
• Confusing with "completion" type
• Omitting the type field

3. Given this mapping snippet:

{
  "mappings": {
    "properties": {
      "name": { "type": "search_as_you_type" }
    }
  }
}

Which query will correctly search for documents where the name field starts with "mic"?

medium

A. { "match": { "name": "mic" } }

B. { "multi_match": { "query": "mic", "type": "bool_prefix", "fields": ["name", "name._2gram", "name._3gram"] } }

C. { "term": { "name": "mic" } }

D. { "prefix": { "name": "mic" } }

Solution

1. Step 1: Understand how to query search_as_you_type fields

   Search-as-you-type fields require a multi_match query with type: bool_prefix and fields including the base field and its n-gram subfields.

2. Step 2: Analyze each query option

   { "match": { "name": "mic" } } uses simple match, which does not support prefix matching well. { "term": { "name": "mic" } } uses term query, which requires exact match. { "prefix": { "name": "mic" } } uses prefix query, which is not optimized for search_as_you_type. { "multi_match": { "query": "mic", "type": "bool_prefix", "fields": ["name", "name._2gram", "name._3gram"] } } correctly uses multi_match with bool_prefix and the required fields.

3. Final Answer:

   { "multi_match": { "query": "mic", "type": "bool_prefix", "fields": ["name", "name._2gram", "name._3gram"] } } -> Option B

4. Quick Check:

   Use multi_match + bool_prefix + ngram fields [OK]

Hint: Use multi_match with bool_prefix and ngram fields [OK]

Common Mistakes:

• Using term or prefix queries alone
• Not including ngram subfields in fields list
• Using simple match query for prefix search

4. You wrote this query to search a search_as_you_type field but get no results:

{ "multi_match": { "query": "app", "type": "bool_prefix", "fields": ["title"] } }

What is the likely problem?

medium

A. The field 'title' must be of type 'keyword' for this query

B. The 'bool_prefix' type is invalid for multi_match queries

C. The query should include ngram subfields like 'title._2gram' and 'title._3gram'

D. The query string 'app' is too short to match anything

Solution

1. Step 1: Check query fields for search_as_you_type

   Search-as-you-type fields generate subfields with ngrams like '_2gram' and '_3gram' that must be included in the query fields for prefix matching.

2. Step 2: Identify missing ngram subfields in the query

   The query only searches 'title' field, missing 'title._2gram' and 'title._3gram', so it won't match prefixes properly.

3. Final Answer:

   The query should include ngram subfields like 'title._2gram' and 'title._3gram' -> Option C

4. Quick Check:

   Include ngram subfields in fields list for prefix search [OK]

Hint: Always add _2gram and _3gram subfields in multi_match fields [OK]

Common Mistakes:

• Omitting ngram subfields in fields list
• Thinking bool_prefix is invalid
• Assuming keyword type is needed
• Blaming query length

5. You want to implement a search-as-you-type feature for a product catalog with a name field. Which of the following mapping and query combinations will correctly support prefix matching as the user types?

hard

A. Mapping: { "name": { "type": "search_as_you_type" } }Query: { "multi_match": { "query": "lap", "type": "bool_prefix", "fields": ["name", "name._2gram", "name._3gram"] } }

B. Mapping: { "name": { "type": "text" } }Query: { "match": { "name": "lap" } }

C. Mapping: { "name": { "type": "keyword" } }Query: { "prefix": { "name": "lap" } }

D. Mapping: { "name": { "type": "completion" } }Query: { "term": { "name": "lap" } }

Solution

1. Step 1: Choose the correct mapping for search-as-you-type

   The search_as_you_type type is designed for prefix matching and instant search as the user types.

2. Step 2: Use the correct query for prefix matching

   The multi_match query with bool_prefix type and fields including the base field and its ngram subfields is required for effective prefix matching.

3. Step 3: Evaluate other options

   Mapping: { "name": { "type": "text" } }
   Query: { "match": { "name": "lap" } } uses text with simple match, which does not support prefix search well. Mapping: { "name": { "type": "keyword" } }
   Query: { "prefix": { "name": "lap" } } uses keyword with prefix query, which is less flexible. Mapping: { "name": { "type": "completion" } }
   Query: { "term": { "name": "lap" } } uses completion with term query, which is incorrect usage.

4. Final Answer:

   Mapping: { "name": { "type": "search_as_you_type" } } and Query: { "multi_match": { "query": "lap", "type": "bool_prefix", "fields": ["name", "name._2gram", "name._3gram"] } } -> Option A

5. Quick Check:

   search_as_you_type + multi_match bool_prefix + ngram fields = correct [OK]

Hint: Combine search_as_you_type mapping with multi_match bool_prefix query [OK]

Common Mistakes:

• Using text type with match query for prefix search
• Using keyword type with prefix query only
• Confusing completion type with search_as_you_type
• Using term query for prefix matching