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?

Practice

1.

What is the main purpose of a percolate query in Elasticsearch?

easy

A. To find stored queries that match a new document

B. To update documents in an index

C. To delete documents based on a condition

D. To aggregate data by terms

Solution

1. Step 1: Understand percolate query concept

   A percolate query is used to find stored queries that match a new document, reversing the usual search direction.

2. Step 2: Compare options with concept

   The other options describe other Elasticsearch operations, not percolate queries.

3. Final Answer:

   To find stored queries that match a new document -> Option A

4. Quick Check:

   Percolate query = find matching stored queries [OK]

Hint: Percolate queries match queries to documents, not documents to queries [OK]

Common Mistakes:

• Confusing percolate query with regular search
• Thinking it updates or deletes documents
• Mixing it with aggregation queries

2.

Which mapping type must be included in an Elasticsearch index to use percolate queries?

{
  "mappings": {
    "properties": {
      "query": {
        "type": "???"
      }
    }
  }
}

easy

A. "percolator"

B. "text"

C. "keyword"

D. "nested"

Solution

1. Step 1: Identify required field type for percolate queries

   Elasticsearch requires a special field type called "percolator" to store queries for percolate queries.

2. Step 2: Match options with required type

   Only "percolator" uses "percolator" type; others are for different purposes.

3. Final Answer:

   "percolator" -> Option A

4. Quick Check:

   Percolate field type = "percolator" [OK]

Hint: Use "percolator" type for storing queries in mapping [OK]

Common Mistakes:

• Using "text" or "keyword" instead of "percolator"
• Confusing nested type with percolator
• Omitting the percolator field in mapping

3.

Given the following percolate query, what will it return?

{
  "query": {
    "percolate": {
      "field": "query",
      "document": {
        "message": "Elasticsearch alerting"
      }
    }
  }
}

Assuming the index has stored queries matching documents containing "alerting".

medium

A. Documents containing the word "alerting"

B. An error because "document" is missing an ID

C. All documents in the index

D. Stored queries that match the document with message "Elasticsearch alerting"

Solution

1. Step 1: Understand percolate query behavior

   The percolate query matches stored queries against the provided document, returning matching stored queries.

2. Step 2: Analyze the given query

   The query uses "document" with a message field; it will find stored queries matching this document's content.

3. Final Answer:

   Stored queries that match the document with message "Elasticsearch alerting" -> Option D

4. Quick Check:

   Percolate query returns matching stored queries [OK]

Hint: Percolate queries return stored queries matching the input document [OK]

Common Mistakes:

• Thinking it returns documents instead of queries
• Assuming document ID is required for percolate query
• Confusing percolate with regular search

4.

Identify the error in this percolate query:

{
  "query": {
    "percolate": {
      "field": "query"
      "document": {
        "content": "Test document"
      }
    }
  }
}

medium

A. "field" should be "query_field"

B. Missing comma between "field" and "document" fields

C. "document" must include an "id" field

D. Percolate query cannot use 'content' field in document

Solution

1. Step 1: Check JSON syntax in query

   Between "field" and "document" keys, a comma is missing, causing invalid JSON.

2. Step 2: Validate other parts

   "field" name is correct, "document" can omit "id", and "content" is valid as document content.

3. Final Answer:

   Missing comma between "field" and "document" fields -> Option B

4. Quick Check:

   JSON syntax error = missing comma [OK]

Hint: Check commas between JSON fields carefully [OK]

Common Mistakes:

• Forgetting commas between JSON keys
• Assuming document must have an ID
• Changing field names unnecessarily

5.

You want to build an alert system that triggers when new documents match any stored queries. Which steps are necessary to implement this using percolate queries?

hard

A. Use aggregation queries on documents to find alerts

B. Store documents in a normal index, then run a regular search for alerts

C. Create an index with a percolator field, store queries, then percolate new documents against stored queries

D. Create a nested field for queries and filter documents manually

Solution

1. Step 1: Setup index with percolator field

   Define an index mapping with a "percolator" type field to store queries for reverse matching.

2. Step 2: Store queries and percolate new documents

   Index the alert queries into the percolator field, then use percolate queries to check if new documents match any stored queries.

3. Final Answer:

   Create an index with a percolator field, store queries, then percolate new documents against stored queries -> Option C

4. Quick Check:

   Percolate queries enable alerting by matching docs to stored queries [OK]

Hint: Store queries in percolator field, then percolate new docs [OK]

Common Mistakes:

• Using regular search instead of percolate queries
• Not defining percolator field in mapping
• Trying to use aggregations for alerting