Completion suggester in Elasticsearch - Time & Space Complexity

Time Complexity: Completion suggester

O(k)

Understanding Time Complexity

When using the completion suggester in Elasticsearch, it's important to understand how the time to find suggestions changes as the number of indexed entries grows.

We want to know how the search speed changes when we add more data to the suggester.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch completion suggester query.

POST /products/_search
{
  "suggest": {
    "product-suggest": {
      "prefix": "iph",
      "completion": {
        "field": "name_suggest"
      }
    }
  }
}
    

This query asks Elasticsearch to suggest product names starting with "iph" using the completion suggester on the "name_suggest" field.

Identify Repeating Operations

In the completion suggester, the main repeating operation is traversing the prefix tree (trie) built from all indexed suggestions.

• Primary operation: Navigating the trie nodes matching the prefix characters.
• How many times: Once per character in the prefix, not per total entries.

How Execution Grows With Input

The time to find suggestions grows mostly with the length of the prefix typed, not the total number of suggestions stored.

Input Size (n)	Approx. Operations
10 suggestions	Few steps, depends on prefix length
1000 suggestions	Still about the same steps, depends on prefix length
100,000 suggestions	Still about the same steps, depends on prefix length

Pattern observation: The search time stays roughly the same as more suggestions are added, because it depends on prefix length, not total suggestions.

Final Time Complexity

Time Complexity: O(k)

This means the time to get suggestions grows linearly with the length of the prefix typed, not with the total number of suggestions stored.

Common Mistake

[X] Wrong: "The more suggestions stored, the slower the completion suggester will be."

[OK] Correct: The completion suggester uses a prefix tree, so it jumps directly to the prefix node. The total number of suggestions does not slow down the search much.

Interview Connect

Understanding how the completion suggester scales helps you explain efficient search features in real applications, showing you know how data structures affect performance.

Self-Check

What if we changed the prefix to a very common short string? How would that affect the time complexity and the number of results returned?

Practice

1. What is the main purpose of the completion suggester in Elasticsearch?

easy

A. To update documents in bulk

B. To perform full-text search on documents

C. To aggregate data based on terms

D. To provide fast autocomplete suggestions as users type

Solution

1. Step 1: Understand the role of completion suggester

   The completion suggester is designed to quickly suggest words or phrases as a user types input.

2. Step 2: Differentiate from other Elasticsearch features

   Full-text search, aggregation, and bulk updates serve different purposes unrelated to autocomplete suggestions.

3. Final Answer:

   To provide fast autocomplete suggestions as users type -> Option D

4. Quick Check:

   Completion suggester = autocomplete suggestions [OK]

Hint: Completion suggester = fast autocomplete feature [OK]

Common Mistakes:

• Confusing completion suggester with full-text search
• Thinking it aggregates data
• Assuming it updates documents

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

easy

A. {
"properties": {
"suggest": { "type": "completion" }
}
}

B. {
"properties": {
"suggest": { "type": "text" }
}
}

C. {
"mappings": {
"suggest": { "type": "completion" }
}
}

D. {
"fields": {
"suggest": { "type": "keyword" }
}
}

Solution

1. Step 1: Identify correct mapping structure

   The completion field must be defined inside properties with type set to completion.

2. Step 2: Compare options

   { "properties": { "suggest": { "type": "completion" } } } correctly uses properties and type: completion. { "properties": { "suggest": { "type": "text" } } } uses text type, which is incorrect. { "mappings": { "suggest": { "type": "completion" } } } wrongly places suggest directly under mappings. { "fields": { "suggest": { "type": "keyword" } } } uses fields and keyword type, which is incorrect.

3. Final Answer:

   { "properties": { "suggest": { "type": "completion" } } } -> Option A

4. Quick Check:

   Completion field in properties with type completion = { "properties": { "suggest": { "type": "completion" } } } [OK]

Hint: Completion field must be under properties with type 'completion' [OK]

Common Mistakes:

• Placing completion field outside properties
• Using text or keyword type instead of completion
• Misnaming mapping keys

3. Given the following suggest query, what will be the expected output if the index contains documents with suggest fields 'apple', 'applet', and 'application'?

{
  "suggest": {
    "fruit-suggest": {
      "prefix": "app",
      "completion": {
        "field": "suggest"
      }
    }
  }
}

medium

A. ["apple", "applet", "application"]

B. ["app", "apple", "applet"]

C. ["application"]

D. []

Solution

1. Step 1: Understand the prefix and completion suggester

   The prefix 'app' matches all suggest entries starting with 'app', which includes 'apple', 'applet', and 'application'.

2. Step 2: Predict the output list

   The completion suggester returns all matching suggestions starting with the prefix, so all three words will be suggested.

3. Final Answer:

   ["apple", "applet", "application"] -> Option A

4. Quick Check:

   Prefix 'app' matches all three suggestions [OK]

Hint: Prefix matches all suggestions starting with it [OK]

Common Mistakes:

• Expecting partial matches inside words
• Thinking prefix must be exact full word
• Assuming empty or partial results

4. Identify the error in this suggest query:

{
  "suggest": {
    "my-suggest": {
      "prefix": "ban",
      "completion": {
        "field": "suggestion"
      }
    }
  }
}

Assuming the mapping defines the completion field as suggest (not suggestion).

medium

A. The prefix value 'ban' is invalid

B. The suggest name 'my-suggest' is not allowed

C. The field name in completion should be 'suggest', not 'suggestion'

D. The suggest query must be inside 'query' key

Solution

1. Step 1: Check field name in completion suggester

   The completion suggester must reference the correct field name defined in the mapping. Here, the mapping uses 'suggest', but the query uses 'suggestion'.

2. Step 2: Validate other parts of the query

   The prefix 'ban' is valid, suggest name 'my-suggest' is allowed, and suggest queries do not require a 'query' key.

3. Final Answer:

   The field name in completion should be 'suggest', not 'suggestion' -> Option C

4. Quick Check:

   Field name mismatch causes error [OK]

Hint: Field name in query must match mapping exactly [OK]

Common Mistakes:

• Using wrong field name in completion query
• Thinking prefix value is invalid
• Expecting suggest query inside 'query' key

5. You want to implement a completion suggester that suggests city names but excludes any suggestions that start with the letter 'x'. Which approach correctly applies this filter in the suggest query?

hard

A. {
"suggest": {
"city-suggest": {
"prefix": "",
"completion": {
"field": "city_suggest",
"skip_duplicates": true
}
}
}
}

B. {
"suggest": {
"city-suggest": {
"prefix": "",
"completion": {
"field": "city_suggest",
"contexts": {
"first_letter": ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "y", "z"]
}
}
}
}
}

C. {
"suggest": {
"city-suggest": {
"prefix": "",
"completion": {
"field": "city_suggest",
"contexts": {
"first_letter": ["!x"]
}
}
}
}
}

D. {
"suggest": {
"city-suggest": {
"prefix": "",
"completion": {
"field": "city_suggest",
"filter": {
"term": { "first_letter": "x" }
}
}
}
}
}

Solution

1. Step 1: Understand filtering with contexts in completion suggester

   Completion suggester supports filtering using contexts. To exclude suggestions starting with 'x', you include all allowed first letters except 'x' in the context filter.

2. Step 2: Analyze each option

   { "suggest": { "city-suggest": { "prefix": "", "completion": { "field": "city_suggest", "skip_duplicates": true } } } } has no filtering. { "suggest": { "city-suggest": { "prefix": "", "completion": { "field": "city_suggest", "contexts": { "first_letter": ["!x"] } } } } } tries to exclude 'x' with '!x' which is invalid syntax. { "suggest": { "city-suggest": { "prefix": "", "completion": { "field": "city_suggest", "contexts": { "first_letter": ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "y", "z"] } } } } } explicitly lists all letters except 'x' in contexts, correctly filtering out 'x'. { "suggest": { "city-suggest": { "prefix": "", "completion": { "field": "city_suggest", "filter": { "term": { "first_letter": "x" } } } } } } uses a 'filter' key which is not supported in completion suggester.

3. Final Answer:

   { "suggest": { "city-suggest": { "prefix": "", "completion": { "field": "city_suggest", "contexts": { "first_letter": ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "y", "z"] } } } } } -> Option B

4. Quick Check:

   Use contexts with allowed letters excluding 'x' [OK]

Hint: Use contexts with allowed letters, exclude 'x' by omission [OK]

Common Mistakes:

• Using invalid '!x' syntax in contexts
• Trying to use 'filter' inside completion suggester
• Not applying context filtering at all