Fuzzy matching in Elasticsearch - Time & Space Complexity

Time Complexity: Fuzzy matching

O(n)

Understanding Time Complexity

When using fuzzy matching in Elasticsearch, it is important to understand how the search time changes as the data grows.

We want to know how the search cost grows when we allow for small spelling mistakes or typos.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch fuzzy query.

{
  "query": {
    "fuzzy": {
      "name": {
        "value": "roam",
        "fuzziness": "AUTO"
      }
    }
  }
}
    

This query searches for documents where the "name" field matches "roam" with some allowed typos.

Identify Repeating Operations

Fuzzy matching involves checking many possible variations of the search word.

• Primary operation: Comparing the search term against many indexed terms with small differences allowed.
• How many times: Once for each candidate term in the index that could match.

How Execution Grows With Input

As the number of indexed terms grows, the number of comparisons grows roughly in proportion.

Input Size (n)	Approx. Operations
10	About 10 comparisons
100	About 100 comparisons
1000	About 1000 comparisons

Pattern observation: The work grows roughly in a straight line as the number of terms increases.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the number of terms to check for fuzzy matches.

Common Mistake

[X] Wrong: "Fuzzy matching is always fast no matter how many terms are in the index."

[OK] Correct: Because fuzzy matching must compare against many terms, the time grows as the index grows, so it can slow down with large data.

Interview Connect

Understanding how fuzzy matching scales helps you explain search performance and design better queries in real projects.

Self-Check

What if we changed the fuzziness level from "AUTO" to a fixed number like 2? How would the time complexity change?

Practice

1. What does the fuzziness parameter control in an Elasticsearch fuzzy query?

easy

A. The maximum length of the search term

B. The number of allowed letter changes to match similar words

C. The minimum number of exact matches required

D. The number of search results returned

Solution

1. Step 1: Understand the role of fuzziness

   The fuzziness parameter sets how many letters can be changed, added, or removed to still count as a match.

2. Step 2: Compare options with definition

   Only The number of allowed letter changes to match similar words correctly describes this as controlling allowed letter changes for similar words.

3. Final Answer:

   The number of allowed letter changes to match similar words -> Option B

4. Quick Check:

   Fuzziness = allowed letter changes [OK]

Hint: Fuzziness = allowed letter changes in matching [OK]

Common Mistakes:

• Confusing fuzziness with result count
• Thinking fuzziness limits search term length
• Mixing fuzziness with prefix_length

2. Which of the following is the correct syntax to add fuzziness in an Elasticsearch query DSL?

easy

A. "match": { "field": { "query": "text", "fuzzify": 2 } }

B. "match": { "field": { "query": "text", "fuzzy": true } }

C. "match": { "field": { "query": "text", "fuzziness": "AUTO" } }

D. "match": { "field": { "query": "text", "fuzzy_level": "high" } }

Solution

1. Step 1: Recall correct fuzziness syntax

   Elasticsearch uses the fuzziness parameter inside the match query with values like "AUTO" or a number.

2. Step 2: Check each option

   Only "match": { "field": { "query": "text", "fuzziness": "AUTO" } } uses the correct key "fuzziness" and proper structure.

3. Final Answer:

   "match": { "field": { "query": "text", "fuzziness": "AUTO" } } -> Option C

4. Quick Check:

   Correct fuzziness syntax = "match": { "field": { "query": "text", "fuzziness": "AUTO" } } [OK]

Hint: Use "fuzziness" key with "AUTO" or number [OK]

Common Mistakes:

• Using incorrect keys like fuzzy or fuzzify
• Setting fuzziness outside the match query
• Using boolean true instead of fuzziness value

3. Given this Elasticsearch fuzzy query snippet:

{ "match": { "name": { "query": "roam", "fuzziness": 0, "prefix_length": 1 } } }

Which of these terms will match the query?

medium

A. "roam"

B. "foam"

C. "roams"

D. "roan"

Solution

1. Step 1: Understand fuzziness and prefix_length

   Fuzziness 0 allows no letter differences (exact match). Prefix_length 1 means first letter must match exactly.

2. Step 2: Check each option against rules

   "roam" matches exactly. "foam" differs in first letter (prefix_length=1), so no. "roams" has extra letter, no exact match. "roan" differs by one letter after prefix ('m' vs 'n'), but fuzziness=0 allows no changes, so no.

3. Final Answer:

   "roam" -> Option A

4. Quick Check:

   Exact match with prefix_length = "roam" [OK]

Hint: Prefix_length fixes first letters; fuzziness=0 requires exact match [OK]

Common Mistakes:

• Ignoring prefix_length effect on first letter
• Assuming all similar words match regardless of prefix
• Confusing fuzziness with allowed extra letters

4. You wrote this fuzzy query:

{ "match": { "title": { "query": "elastic", "fuzziness": "2", "prefix_length": 3 } } }

But it returns no results even though documents with "plastics" and "elustics" exist. What is the likely problem?

medium

A. prefix_length is too high, blocking matches with differences in first 3 letters

B. fuzziness value must be a boolean, not a number

C. query string "elastic" is misspelled

D. match query does not support fuzziness parameter

Solution

1. Step 1: Analyze prefix_length effect

   Prefix_length 3 means first 3 letters must match exactly. If documents differ in those letters, they won't match.

2. Step 2: Check fuzziness and query validity

   Fuzziness accepts numbers; "2" is valid. Query "elastic" is correct. Match query supports fuzziness.

3. Final Answer:

   prefix_length is too high, blocking matches with differences in first 3 letters -> Option A

4. Quick Check:

   High prefix_length blocks fuzzy matches = prefix_length is too high, blocking matches with differences in first 3 letters [OK]

Hint: High prefix_length blocks fuzzy matches early [OK]

Common Mistakes:

• Thinking fuzziness must be boolean
• Ignoring prefix_length effect
• Assuming match query disallows fuzziness

5. You want to find documents with names similar to "johnson" allowing up to 2 letter changes but want to speed up search by requiring the first 2 letters to match exactly. Which query is best?

hard

A. { "match": { "name": { "query": "johnson", "fuzziness": "AUTO", "prefix_length": 3 } } }

B. { "match": { "name": { "query": "johnson", "fuzziness": 1, "prefix_length": 0 } } }

C. { "match": { "name": { "query": "johnson", "fuzziness": 3, "prefix_length": 1 } } }

D. { "match": { "name": { "query": "johnson", "fuzziness": 2, "prefix_length": 2 } } }

Solution

1. Step 1: Match requirements to parameters

   Allow up to 2 letter changes means fuzziness = 2. Speed up by requiring first 2 letters exact means prefix_length = 2.

2. Step 2: Evaluate each option

   { "match": { "name": { "query": "johnson", "fuzziness": 2, "prefix_length": 2 } } } matches both requirements exactly. { "match": { "name": { "query": "johnson", "fuzziness": 1, "prefix_length": 0 } } } allows only 1 change and no prefix. { "match": { "name": { "query": "johnson", "fuzziness": "AUTO", "prefix_length": 3 } } } uses AUTO fuzziness and prefix_length 3, which is more restrictive. { "match": { "name": { "query": "johnson", "fuzziness": 3, "prefix_length": 1 } } } allows 3 changes but only 1 prefix letter.

3. Final Answer:

   { "match": { "name": { "query": "johnson", "fuzziness": 2, "prefix_length": 2 } } } -> Option D

4. Quick Check:

   Fuzziness 2 + prefix_length 2 = { "match": { "name": { "query": "johnson", "fuzziness": 2, "prefix_length": 2 } } } [OK]

Hint: Match fuzziness and prefix_length to requirements exactly [OK]

Common Mistakes:

• Using wrong fuzziness number
• Setting prefix_length too high or too low
• Confusing AUTO with exact fuzziness number