Full-text search engine concept in Elasticsearch - Time & Space Complexity

Time Complexity: Full-text search engine concept

O(k + r)

Understanding Time Complexity

When using a full-text search engine like Elasticsearch, it is important to understand how the time it takes to find results changes as the amount of data grows.

We want to know how the search speed changes when we add more documents or search terms.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch query.

GET /library/_search
{
  "query": {
    "match": {
      "content": "climate change"
    }
  }
}
    

This query searches the "library" index for documents containing the words "climate change" in the "content" field.

Identify Repeating Operations

In this search, Elasticsearch looks through its inverted index to find documents matching the search words.

• Primary operation: Checking the posting lists for each search term and merging results.
• How many times: Once per search term, then combined across documents containing those terms.

How Execution Grows With Input

As the number of documents grows, the posting lists for common words get longer, so more entries must be checked.

Input Size (n)	Approx. Operations
10 documents	Few entries to check, very fast.
1000 documents	More entries, takes longer but still quick.
1,000,000 documents	Many entries, search takes noticeably more time.

Pattern observation: The work grows roughly in proportion to how many documents contain the search terms.

Final Time Complexity

Time Complexity: O(k + r)

This means the search time grows with the number of search terms (k) plus the number of matching documents (r).

Common Mistake

[X] Wrong: "Searching always takes the same time no matter how many documents exist."

[OK] Correct: The search time depends on how many documents contain the search words, so more data usually means more work.

Interview Connect

Understanding how search time grows helps you explain how search engines handle large data efficiently and why indexing matters.

Self-Check

What if we added a filter to only search documents from the last year? How would the time complexity change?

Practice

1. What is the main purpose of a full-text search engine like Elasticsearch?

easy

A. To create user interfaces for websites

B. To store images and videos efficiently

C. To quickly find words or phrases inside large amounts of text

D. To perform mathematical calculations on numbers

Solution

1. Step 1: Understand full-text search

   Full-text search engines are designed to search text data quickly and efficiently.

2. Step 2: Identify the main use case

   They help find words or phrases inside large text collections, unlike storing media or calculations.

3. Final Answer:

   To quickly find words or phrases inside large amounts of text -> Option C

4. Quick Check:

   Full-text search = find words fast [OK]

Hint: Full-text search = fast text lookup [OK]

Common Mistakes:

• Confusing full-text search with media storage
• Thinking it does math calculations
• Assuming it builds website interfaces

2. Which Elasticsearch query is commonly used to search text fields for matching words?

easy

A. term

B. match

C. range

D. exists

Solution

1. Step 1: Review query types

   Elasticsearch has different queries: term for exact matches, range for numbers, exists for presence.

2. Step 2: Identify text search query

   The match query is designed to find words inside text fields using full-text search.

3. Final Answer:

   match -> Option B

4. Quick Check:

   Text search query = match [OK]

Hint: Use match query for text search in Elasticsearch [OK]

Common Mistakes:

• Using term query for full-text search
• Confusing range query with text search
• Using exists query to find words

3. Given this Elasticsearch query snippet, what does it do?

{
  "query": {
    "match": { "description": "fast car" }
  }
}

medium

A. Searches documents where the description field exists

B. Searches documents where the description contains the exact phrase "fast car"

C. Searches documents where the description contains both words "fast" and "car" in order

D. Searches documents where the description contains either "fast" or "car"

Solution

1. Step 1: Understand match query behavior

   The match query analyzes the input text and searches for documents containing any of the words.

2. Step 2: Analyze the query text "fast car"

   It looks for documents containing "fast" or "car", not necessarily as an exact phrase or order.

3. Final Answer:

   Searches documents where the description contains either "fast" or "car" -> Option D

4. Quick Check:

   Match query finds any matching words [OK]

Hint: Match query finds any word in text [OK]

Common Mistakes:

• Assuming match query searches exact phrase
• Thinking it requires words in order
• Confusing with exists query

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

{
  "query": {
    "match": { "title": "" }
  }
}

What is the likely problem?

medium

A. The match query cannot search empty strings

B. The field name "title" is invalid syntax

C. Elasticsearch requires a range query for text fields

D. The query must use term instead of match

Solution

1. Step 1: Check the query input

   The match query is given an empty string "" to search, which means no words to match.

2. Step 2: Understand match query behavior with empty input

   Match queries need some text to find matches; empty strings return no results.

3. Final Answer:

   The match query cannot search empty strings -> Option A

4. Quick Check:

   Empty match query = no results [OK]

Hint: Match query needs non-empty text [OK]

Common Mistakes:

• Thinking field name syntax is wrong
• Using range query for text fields
• Confusing term and match query roles

5. You want to find documents where the text field "content" contains the word "apple" but not the word "fruit". Which Elasticsearch query structure should you use?

hard

A. { "query": { "bool": { "must": { "match": { "content": "apple" } }, "must_not": { "match": { "content": "fruit" } } } } }

B. { "query": { "match": { "content": "apple fruit" } } }

C. { "query": { "term": { "content": "apple" } } }

D. { "query": { "range": { "content": { "gte": "apple", "lte": "fruit" } } } }

Solution

1. Step 1: Understand the requirement

   You want documents containing "apple" but excluding those containing "fruit" in the same field.

2. Step 2: Use bool query with must and must_not

   The bool query allows combining conditions: must for required matches, must_not to exclude matches.

3. Step 3: Analyze options

   { "query": { "bool": { "must": { "match": { "content": "apple" } }, "must_not": { "match": { "content": "fruit" } } } } } uses bool with must match "apple" and must_not match "fruit", which fits the requirement.

4. Final Answer:

   { "query": { "bool": { "must": { "match": { "content": "apple" } }, "must_not": { "match": { "content": "fruit" } } } } } -> Option A

5. Quick Check:

   Bool must + must_not = include apple, exclude fruit [OK]

Hint: Use bool must and must_not for include/exclude text [OK]

Common Mistakes:

• Using match with both words includes fruit
• Using term query ignores text analysis
• Using range query on text fields is invalid