Wildcard and prefix queries in Elasticsearch - Time & Space Complexity

Time Complexity: Wildcard and prefix queries

O(m)

Understanding Time Complexity

When searching text in Elasticsearch, wildcard and prefix queries help find words that start or match patterns.

We want to know how the search time changes as the data grows.

Scenario Under Consideration

Analyze the time complexity of this Elasticsearch query using a wildcard and prefix search.

GET /products/_search
{
  "query": {
    "bool": {
      "should": [
        { "wildcard": { "name": "sams*" } },
        { "prefix": { "name": "sam" } }
      ]
    }
  }
}
    

This query looks for product names starting with "sams" or "sam" using wildcard and prefix patterns.

Identify Repeating Operations

Look at what repeats when Elasticsearch runs this query.

• Primary operation: Scanning terms in the index that match the wildcard or prefix pattern.
• How many times: It checks many terms depending on how many start with "sam" or match "sams*".

How Execution Grows With Input

As the number of indexed terms grows, the search checks more terms that match the pattern.

Input Size (n)	Approx. Operations
10	Few terms to check, fast search
100	More terms starting with "sam", more checks
1000	Many terms to scan, search takes longer

Pattern observation: The time grows roughly with how many terms match the prefix or wildcard pattern.

Final Time Complexity

Time Complexity: O(m)

This means the search time grows in proportion to the number of matching terms, not the total data size.

Common Mistake

[X] Wrong: "Wildcard and prefix queries always scan the entire index."

[OK] Correct: They only scan terms that could match the pattern, so the cost depends on matching terms, not all data.

Interview Connect

Understanding how search time grows with pattern matching helps you explain query performance clearly and confidently.

Self-Check

What if we changed the wildcard pattern from "sams*" to "*sam"? How would the time complexity change?

Practice

1. What does a wildcard query with * symbol do in Elasticsearch?

easy

A. Matches terms ending with a specific suffix

B. Matches only the exact search term

C. Matches terms starting with a specific prefix

D. Matches any sequence of characters in the search term

Solution

1. Step 1: Understand the wildcard symbol *

   The * symbol in wildcard queries matches zero or more characters in any position of the term.

2. Step 2: Compare with other options

   Exact match requires no wildcard, prefix queries use a different query type, and suffix matching is not directly done by * alone.

3. Final Answer:

   Matches any sequence of characters in the search term -> Option D

4. Quick Check:

   wildcard * = match any chars [OK]

Hint: Remember * matches any characters, ? matches one character [OK]

Common Mistakes:

• Confusing wildcard * with prefix query
• Thinking * matches only one character
• Assuming wildcard matches exact terms only

2. Which of the following is the correct syntax for a prefix query in Elasticsearch?

easy

A. { "prefix": { "field_name": "pre" } }

B. { "wildcard": { "field_name": "pre*" } }

C. { "match": { "field_name": "pre*" } }

D. { "term": { "field_name": "pre*" } }

Solution

1. Step 1: Identify prefix query syntax

   Prefix queries use the prefix keyword with the field and the prefix string.

2. Step 2: Check other options

   Wildcard queries use wildcard, match and term queries do not support prefix syntax with asterisk.

3. Final Answer:

   { "prefix": { "field_name": "pre" } } -> Option A

4. Quick Check:

   prefix query uses "prefix" keyword [OK]

Hint: Prefix queries use "prefix" keyword, not wildcard or match [OK]

Common Mistakes:

• Using wildcard syntax for prefix query
• Using match query with asterisk
• Confusing term query with prefix query

3. Given the following wildcard query, which documents will match?

{ "query": { "wildcard": { "name": "jo?n*" } } }

Assuming documents have names: "john", "joan", "jonas", "joanathan", "jo".

medium

A. ["joan", "jonas", "joanathan"]

B. ["john", "joan", "jo"]

C. ["john", "joan", "joanathan"]

D. ["john", "joan", "jonas", "joanathan", "jo"]

Solution

1. Step 1: Analyze the wildcard pattern "jo?n*"

   The pattern means: 'jo' followed by any single character (due to '?'), then 'n', then any characters (due to '*').

2. Step 2: Check each name against the pattern

   "john" matches ('h' replaces '?'), "joan" matches ('a' replaces '?'), "joanathan" matches ('a' replaces '?'). "jonas" does not match ('n' replaces '?' but next 'a' ≠ 'n'). "jo" is too short to match.

3. Final Answer:

   ["john", "joan", "joanathan"] -> Option C

4. Quick Check:

   wildcard ? = one char, * = any chars [OK]

Hint: ? matches one char, * matches zero or more chars [OK]

Common Mistakes:

• Assuming ? matches zero characters
• Including too short strings like "jo"
• Confusing wildcard with prefix query

4. You wrote this prefix query but it returns no results:

{ "query": { "prefix": { "title": "prog*" } } }

What is the error?

medium

A. Field name "title" is invalid

B. Prefix query should not include the asterisk (*)

C. Prefix queries require wildcard keyword

D. Prefix query must use match instead of prefix

Solution

1. Step 1: Understand prefix query syntax

   Prefix queries expect a string prefix without wildcards like '*'. The asterisk is not needed and causes no matches.

2. Step 2: Check other options

   Field name is assumed valid, wildcard keyword is different query type, and match query is unrelated to prefix syntax.

3. Final Answer:

   Prefix query should not include the asterisk (*) -> Option B

4. Quick Check:

   Prefix query uses plain prefix string, no * [OK]

Hint: Remove * from prefix query string to fix [OK]

Common Mistakes:

• Including * in prefix query string
• Confusing prefix with wildcard query
• Using match query instead of prefix

5. You want to find all documents where the "username" field starts with "alex" but also want to allow any characters after "alex" including none. Which query is best and why?

{ "query": { "wildcard": { "username": "alex*" } } }

or

{ "query": { "prefix": { "username": "alex" } } }

hard

A. Prefix query is better because it is faster and matches all starting with "alex"

B. Wildcard query is better because it matches "alex" exactly only

C. Wildcard query is better because it matches any characters including none after "alex"

D. Prefix query is better because it requires the * symbol

Solution

1. Step 1: Compare prefix and wildcard queries for this case

   Both queries match terms starting with "alex" and any characters after. Wildcard uses "alex*", prefix uses "alex" without *.

2. Step 2: Consider performance and usage

   Prefix queries are optimized and faster for this use case. Wildcard queries are slower and more flexible but unnecessary here.

3. Final Answer:

   Prefix query is better because it is faster and matches all starting with "alex" -> Option A

4. Quick Check:

   Prefix query faster for starts-with matching [OK]

Hint: Use prefix query for starts-with, wildcard for complex patterns [OK]

Common Mistakes:

• Using wildcard when prefix is enough
• Adding * in prefix query string
• Thinking wildcard matches exact only