Percolate queries (reverse search) in Elasticsearch - Time & Space Complexity

Time Complexity: Percolate queries (reverse search)

O(n)

Understanding Time Complexity

When using percolate queries in Elasticsearch, we want to know how the search time changes as we add more stored queries.

We ask: How does the number of stored queries affect the time to find matches?

Scenario Under Consideration

Analyze the time complexity of this percolate query example.

POST /my-index/_search
{
  "query": {
    "percolate": {
      "field": "query",
      "document": {
        "message": "A new message to match"
      }
    }
  }
}
    

This query checks which stored queries in the index match the given document.

Identify Repeating Operations

Look for repeated work inside the percolate query process.

• Primary operation: Matching the input document against each stored query.
• How many times: Once per stored query in the index.

How Execution Grows With Input

As the number of stored queries grows, the work to check each one grows too.

Input Size (n)	Approx. Operations
10 stored queries	10 matches checked
100 stored queries	100 matches checked
1000 stored queries	1000 matches checked

Pattern observation: The work grows directly with the number of stored queries.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows in a straight line as you add more stored queries.

Common Mistake

[X] Wrong: "Percolate queries run in constant time no matter how many stored queries exist."

[OK] Correct: Each stored query must be checked against the document, so more stored queries mean more work.

Interview Connect

Understanding how percolate queries scale helps you explain search performance and design efficient systems.

Self-Check

What if we indexed the stored queries differently or used filters? How would that affect the time complexity?