Atlas search overview in MongoDB - Time & Space Complexity

Time Complexity: Atlas search overview

O(log n + k)

Understanding Time Complexity

When using Atlas Search in MongoDB, it's important to understand how the time to find results changes as your data grows.

We want to know how the search time changes when there are more documents to look through.

Scenario Under Consideration

Analyze the time complexity of the following Atlas Search query.

db.collection.aggregate([
  {
    $search: {
      index: 'default',
      text: {
        query: 'coffee',
        path: 'description'
      }
    }
  }
])
    

This query searches the 'description' field of documents for the word 'coffee' using an Atlas Search index.

Identify Repeating Operations

Look for repeated work done during the search.

• Primary operation: Searching the inverted index for matching terms.
• How many times: Once per query, but the index lookup touches entries related to the query term.

How Execution Grows With Input

As the number of documents grows, the index grows too, but searching the index stays efficient.

Input Size (n)	Approx. Operations
10	Few index lookups
100	More index lookups, still fast
1000	More index lookups, but still efficient

Pattern observation: The search time grows slowly compared to the number of documents because the index helps find matches quickly.

Final Time Complexity

Time Complexity: O(log n + k)

This means the search time grows slowly as the data grows, thanks to the index structure, plus a term proportional to the number of results returned.

Common Mistake

[X] Wrong: "Searching with Atlas Search takes as long as scanning every document."

[OK] Correct: Atlas Search uses indexes that let it jump directly to matching documents, so it doesn't check every document one by one.

Interview Connect

Understanding how indexes speed up search is a valuable skill. It shows you know how databases handle large data efficiently.

Self-Check

"What if we removed the Atlas Search index and searched without it? How would the time complexity change?"

Practice

1. What is the primary purpose of the $search stage in MongoDB Atlas Search?

easy

A. To update documents in a collection

B. To perform text search queries on collections

C. To delete documents based on a condition

D. To create indexes on collections

Solution

1. Step 1: Understand the role of $search

   The $search stage is used in aggregation pipelines to perform text search queries on MongoDB collections.

2. Step 2: Differentiate from other operations

   Updating, deleting, or creating indexes are not functions of $search. It is specifically for searching text.

3. Final Answer:

   To perform text search queries on collections -> Option B

4. Quick Check:

   $search = text search [OK]

Hint: Remember: $search is for finding text, not modifying data [OK]

Common Mistakes:

• Confusing $search with update or delete operations
• Thinking $search creates indexes
• Assuming $search works outside aggregation

2. Which of the following is the correct syntax to use the $search stage in an aggregation pipeline?

easy

A. { $search: { find: { query: "apple", field: "name" } } }

B. { $search: { text: { search: "apple", field: "name" } } }

C. { $search: { query: "apple", path: "name" } }

D. { $search: { text: { query: "apple", path: "name" } } }

Solution

1. Step 1: Recall the correct $search syntax

   The $search stage uses a text operator with query and path fields to specify the search term and field.

2. Step 2: Compare options to syntax

   { $search: { text: { query: "apple", path: "name" } } } matches the correct syntax. Other options use incorrect keys like find, missing text, or wrong field names.

3. Final Answer:

   { $search: { text: { query: "apple", path: "name" } } } -> Option D

4. Quick Check:

   Correct keys: text, query, path [OK]

Hint: Look for keys: text, query, and path in $search [OK]

Common Mistakes:

• Using 'find' instead of 'text' inside $search
• Omitting 'text' operator
• Using 'field' instead of 'path'

3. Given the following aggregation pipeline, what documents will be returned if the collection has documents with names: ['apple', 'banana', 'pineapple']?

[{ $search: { text: { query: "apple", path: "name" } } }]

medium

A. Only the document with name 'apple'

B. Documents with names 'apple' and 'pineapple'

C. Documents with names 'banana' and 'pineapple'

D. All documents in the collection

Solution

1. Step 1: Understand text search behavior

   The $search with text operator performs full-text search matching whole terms after tokenization. It does not perform substring matching by default.

2. Step 2: Apply to given names

   'apple' matches the query term exactly. 'pineapple' is tokenized as a single term "pineapple", which does not match "apple". 'banana' does not match.

3. Final Answer:

   Only the document with name 'apple' -> Option A

4. Quick Check:

   Whole term matches only [OK]

Hint: Text search matches whole terms, not substrings [OK]

Common Mistakes:

• Assuming substring matches like 'pineapple' for 'apple'
• Including documents without the query term
• Thinking $search returns all documents

4. Identify the error in this aggregation pipeline using Atlas Search:

[{ $search: { text: { query: "apple" } } }]

medium

A. Missing the 'path' field specifying which field to search

B. The 'query' field should be named 'search'

C. The $search stage cannot be used inside aggregation

D. The 'text' operator is invalid inside $search

Solution

1. Step 1: Check required fields in $search text operator

   The 'text' operator requires both 'query' and 'path' fields to specify the search term and the field to search.

2. Step 2: Identify missing field

   The pipeline is missing the 'path' field, so MongoDB does not know which field to search.

3. Final Answer:

   Missing the 'path' field specifying which field to search -> Option A

4. Quick Check:

   Always include 'path' with 'query' in $search text [OK]

Hint: Always specify 'path' when using $search text operator [OK]

Common Mistakes:

• Omitting 'path' field
• Renaming 'query' to 'search'
• Thinking $search can't be in aggregation

5. You want to search for documents where either the 'title' or 'description' fields contain the word 'mongodb'. Which $search operator should you use in your aggregation pipeline?

hard

A. { $search: { text: { query: "mongodb", path: "title" }, text: { query: "mongodb", path: "description" } } }

B. { $search: { compound: { must: [{ text: { query: "mongodb", path: "title" } }, { text: { query: "mongodb", path: "description" } }] } } }

C. { $search: { text: { query: "mongodb", path: ["title", "description"] } } }

D. { $search: { text: { query: "mongodb", path: "title" } }, filter: { text: { query: "mongodb", path: "description" } } }

Solution

1. Step 1: Understand searching multiple fields

   The text operator allows specifying multiple fields by passing an array to the path parameter.

2. Step 2: Evaluate options for multiple field search

   { $search: { text: { query: "mongodb", path: ["title", "description"] } } } correctly uses an array for path to search both 'title' and 'description' (OR semantics). { $search: { text: { query: "mongodb", path: "title" }, text: { query: "mongodb", path: "description" } } } has invalid syntax with duplicate text keys. { $search: { compound: { must: [{ text: { query: "mongodb", path: "title" } }, { text: { query: "mongodb", path: "description" } }] } } } uses compound with must requiring both fields to match (AND). { $search: { text: { query: "mongodb", path: "title" } }, filter: { text: { query: "mongodb", path: "description" } } } has invalid syntax.

3. Final Answer:

   { $search: { text: { query: "mongodb", path: ["title", "description"] } } } -> Option C

4. Quick Check:

   Use array in path for multiple fields [OK]

Hint: Use array in 'path' to search multiple fields [OK]

Common Mistakes:

• Using compound must instead of array for either/or
• Repeating text operator keys incorrectly
• Misusing filter stage inside $search