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?