Regex queries in MongoDB - Time & Space Complexity

Time Complexity: Regex queries in MongoDB

O(n)

Understanding Time Complexity

When using regex queries in MongoDB, it is important to understand how the search time changes as the data grows.

We want to know how the cost of searching with a pattern grows when there are more documents.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.users.find({
  name: { $regex: /^A/ }
})
.limit(10)

This query finds users whose names start with the letter 'A' and returns up to 10 results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: MongoDB checks each document's 'name' field against the regex pattern.
• How many times: This check happens once for every document in the collection unless an index helps.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 10 regex checks
100	About 100 regex checks
1000	About 1000 regex checks

Pattern observation: The number of regex checks grows directly with the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the regex query grows linearly as the number of documents increases.

Common Mistake

[X] Wrong: "Regex queries always use indexes and are very fast."

[OK] Correct: Regex queries often scan many documents unless the regex starts with a fixed prefix that matches an index.

Interview Connect

Understanding how regex queries scale helps you explain database performance clearly and shows you know how to handle real data search challenges.

Self-Check

"What if we changed the regex to a pattern without a fixed prefix? How would the time complexity change?"

Practice

1. What does the $regex operator do in a MongoDB query?

easy

A. It searches for documents where a field matches a text pattern.

B. It sorts documents in ascending order.

C. It updates documents with new values.

D. It deletes documents matching a condition.

Solution

1. Step 1: Understand the purpose of $regex

   The $regex operator is used to find text patterns inside string fields in MongoDB documents.

2. Step 2: Compare with other operations

   Sorting, updating, and deleting are different operations and do not use $regex.

3. Final Answer:

   It searches for documents where a field matches a text pattern. -> Option A

4. Quick Check:

   $regex = pattern search [OK]

Hint: Remember: $regex means 'match pattern' in text fields [OK]

Common Mistakes:

• Confusing $regex with sorting or updating operations
• Thinking $regex modifies data instead of searching
• Assuming $regex works on non-string fields

2. Which of the following is the correct syntax to find documents where the field name starts with 'A' using regex in MongoDB?

easy

A. {"name": {"$regex": "A$"}}

B. {"name": {"$regex": "A*"}}

C. {"name": {"$regex": "^A"}}

D. {"name": {"$regex": "[A]"}}

Solution

1. Step 1: Understand regex anchors

   The caret ^ means the start of the string, so ^A matches strings starting with 'A'.

2. Step 2: Check other options

   A$ matches strings ending with 'A', A* matches zero or more 'A's anywhere, and [A] matches any 'A' character anywhere.

3. Final Answer:

   {"name": {"$regex": "^A"}} -> Option C

4. Quick Check:

   Start with 'A' = ^A [OK]

Hint: Use ^ at start of pattern to match beginning of string [OK]

Common Mistakes:

• Using $ instead of ^ to match start
• Misunderstanding * as 'starts with'
• Using character class [] without anchors

3. Given the collection documents: [{"city": "London"}, {"city": "london"}, {"city": "Londonderry"}], what will the query {"city": {"$regex": "^London$", "$options": "i"}} return?

medium

A. []

B. [{"city": "London"}]

C. [{"city": "Londonderry"}]

D. [{"city": "London"}, {"city": "london"}]

Solution

1. Step 1: Analyze the regex pattern and options

   The pattern ^London$ matches exactly 'London' from start to end. The option i makes it case-insensitive.

2. Step 2: Check which documents match

   "London" matches exactly, "london" matches ignoring case, but "Londonderry" does not match because it has extra characters.

3. Final Answer:

   [{"city": "London"}, {"city": "london"}] -> Option D

4. Quick Check:

   Exact match ignoring case = [{"city": "London"}, {"city": "london"}] [OK]

Hint: Use ^ and $ for exact match; 'i' option ignores case [OK]

Common Mistakes:

• Ignoring case option and missing lowercase match
• Assuming partial matches without anchors
• Confusing $regex with substring search

4. Identify the error in this MongoDB query to find documents where title contains 'book' case-insensitive: {"title": {"$regex": "/book/i"}}

medium

A. The $regex operator cannot be used with strings.

B. The regex pattern should not be enclosed in slashes.

C. The $options field is missing.

D. The field name should be $pattern, not $regex.

Solution

1. Step 1: Understand MongoDB regex syntax

   In MongoDB, the regex pattern is a string without enclosing slashes. Options like 'i' go in a separate $options field.

2. Step 2: Identify the mistake in the query

   The pattern "/book/i" incorrectly includes slashes and option inside the string. It should be {"$regex": "book", "$options": "i"}.

3. Final Answer:

   The regex pattern should not be enclosed in slashes. -> Option B

4. Quick Check:

   MongoDB regex no slashes, use $options [OK]

Hint: Do not use /slashes/ in MongoDB regex patterns [OK]

Common Mistakes:

• Including slashes around regex pattern
• Putting options inside the pattern string
• Using wrong field names like $pattern

5. You want to find all documents where the description field contains either 'cat' or 'dog' (case-insensitive). Which MongoDB query correctly uses regex to achieve this?

hard

A. {"description": {"$regex": "cat|dog", "$options": "i"}}

B. {"description": {"$regex": "[cat|dog]", "$options": "i"}}

C. {"description": {"$regex": "(cat|dog)", "$options": "g"}}

D. {"description": {"$regex": "cat|dog"}}

Solution

1. Step 1: Understand regex alternation and options

   The pattern cat|dog matches either 'cat' or 'dog'. The i option makes it case-insensitive.

2. Step 2: Evaluate each option

   {"description": {"$regex": "cat|dog", "$options": "i"}} correctly uses the pattern and case-insensitive option. {"description": {"$regex": "[cat|dog]", "$options": "i"}} uses character class incorrectly, matching any single character 'c', 'a', 't', '|', 'd', 'o', or 'g'. {"description": {"$regex": "(cat|dog)", "$options": "g"}} uses g which is not a valid MongoDB regex option. {"description": {"$regex": "cat|dog"}} misses the case-insensitive option.

3. Final Answer:

   {"description": {"$regex": "cat|dog", "$options": "i"}} -> Option A

4. Quick Check:

   Use | for OR and 'i' for ignore case [OK]

Hint: Use | inside regex and $options: 'i' for case-insensitive [OK]

Common Mistakes:

• Using character classes [] instead of alternation |
• Using invalid regex options like 'g' in MongoDB
• Forgetting $options for case-insensitive search