Partial indexes with filter in MongoDB - Time & Space Complexity

Time Complexity: Partial indexes with filter

O(m)

Understanding Time Complexity

When using partial indexes with filters in MongoDB, we want to know how fast queries run as data grows.

We ask: How does the filter affect the number of operations MongoDB does?

Scenario Under Consideration

Analyze the time complexity of the following MongoDB partial index creation and query.

db.orders.createIndex(
  { status: 1 },
  { partialFilterExpression: { status: { $eq: "pending" } } }
)

db.orders.find({ status: "pending" })
    

This code creates an index only on documents where status is "pending" and then queries those documents.

Identify Repeating Operations

Look for repeated work MongoDB does when using this partial index.

• Primary operation: Scanning the partial index entries matching the filter.
• How many times: Once per matching document with status "pending".

How Execution Grows With Input

As the number of "pending" documents grows, the work grows too, but only for those documents.

Input Size (m)	Approx. Operations
10 (pending docs)	About 10 index lookups
100 (pending docs)	About 100 index lookups
1000 (pending docs)	About 1000 index lookups

Pattern observation: The cost grows linearly with the number of documents matching the filter, not total documents.

Final Time Complexity

Time Complexity: O(m)

This means the query time grows in a straight line with the number of documents that match the filter, not all documents.

Common Mistake

[X] Wrong: "The partial index speeds up queries on all documents equally."

[OK] Correct: The partial index only covers documents matching the filter, so queries on other documents don't benefit from it.

Interview Connect

Understanding how partial indexes limit work to relevant data shows you can write efficient queries and indexes that scale well.

Self-Check

"What if we changed the filter to include more fields? How would that affect the time complexity?"

Practice

1. What is the main purpose of a partial index in MongoDB?

easy

A. To index only documents that match a specific filter condition

B. To index all documents in a collection

C. To create a backup of the index

D. To speed up writes by disabling indexing

Solution

1. Step 1: Understand what partial indexes do

   Partial indexes only include documents that meet a filter condition, unlike normal indexes that include all documents.

2. Step 2: Compare options

   To index only documents that match a specific filter condition correctly describes this behavior. Options A, B, and D describe other unrelated or incorrect behaviors.

3. Final Answer:

   To index only documents that match a specific filter condition -> Option A

4. Quick Check:

   Partial index = filtered indexing [OK]

Hint: Partial indexes filter documents before indexing [OK]

Common Mistakes:

• Thinking partial indexes index all documents
• Confusing partial indexes with backups
• Assuming partial indexes disable indexing

2. Which of the following is the correct syntax to create a partial index on the status field where status equals 'active'?

easy

A. db.collection.createIndex({status: 1}, {filter: {status: 'active'}})

B. db.collection.createIndex({status: 1}, {partialFilterExpression: {status: 'active'}})

C. db.collection.createPartialIndex({status: 1}, {status: 'active'})

D. db.collection.createIndex({status: 1}, {partialIndex: {status: 'active'}})

Solution

1. Step 1: Recall the correct option name for partial indexes

   The option to specify a filter for partial indexes is partialFilterExpression.

2. Step 2: Match syntax with options

   db.collection.createIndex({status: 1}, {partialFilterExpression: {status: 'active'}}) uses partialFilterExpression correctly. Options B, C, and D use incorrect option names or methods.

3. Final Answer:

   db.collection.createIndex({status: 1}, {partialFilterExpression: {status: 'active'}}) -> Option B

4. Quick Check:

   Use partialFilterExpression for partial indexes [OK]

Hint: Use partialFilterExpression option to filter index documents [OK]

Common Mistakes:

• Using 'filter' instead of partialFilterExpression
• Trying to use createPartialIndex method (doesn't exist)
• Using partialIndex option instead of partialFilterExpression

3. Given the following partial index creation:

db.users.createIndex({age: 1}, {partialFilterExpression: {age: {$gte: 18}}})

Which documents will be included in this index?

medium

A. All documents regardless of age

B. Only documents where age is less than 18

C. Only documents where age is 18 or older

D. Documents where age is exactly 18

Solution

1. Step 1: Understand the filter condition

   The filter {age: {$gte: 18}} means age greater than or equal to 18.

2. Step 2: Determine which documents match

   Only documents with age 18 or older satisfy this condition and will be indexed.

3. Final Answer:

   Only documents where age is 18 or older -> Option C

4. Quick Check:

   Filter {$gte: 18} means age ≥ 18 [OK]

Hint: Partial index includes only documents matching filter [OK]

Common Mistakes:

• Thinking all documents are indexed
• Confusing $gte with $lt
• Assuming only exact matches are indexed

4. You tried to create a partial index with this command:

db.orders.createIndex({price: 1}, {partialFilterExpression: {price: {$gt: 100}}})

But you get an error. What is the most likely cause?

medium

A. The filter expression uses an unsupported operator

B. The field name in the index is missing

C. Partial indexes cannot use comparison operators

D. The partialFilterExpression option is misspelled or misplaced

Solution

1. Step 1: Check syntax correctness

   The syntax shown is correct if partialFilterExpression is spelled and placed properly.

2. Step 2: Identify common mistakes

   Errors often happen if partialFilterExpression is misspelled or placed outside the options object.

3. Final Answer:

   The partialFilterExpression option is misspelled or misplaced -> Option D

4. Quick Check:

   Check spelling and placement of partialFilterExpression [OK]

Hint: Check spelling and position of partialFilterExpression [OK]

Common Mistakes:

• Misspelling partialFilterExpression
• Placing filter outside options object
• Assuming comparison operators are unsupported

5. You want to speed up queries on a collection products where only documents with stock greater than zero are frequently queried. Which partial index creation command is best?

hard

A. db.products.createIndex({stock: 1}, {partialFilterExpression: {stock: {$gt: 0}}})

B. db.products.createIndex({stock: 1})

C. db.products.createIndex({stock: 1}, {partialFilterExpression: {stock: 0}})

D. db.products.createIndex({stock: 1}, {filter: {stock: {$gt: 0}}})

Solution

1. Step 1: Identify the filter condition for partial index

   The goal is to index only documents where stock is greater than zero.

2. Step 2: Match the correct syntax and filter

   db.products.createIndex({stock: 1}, {partialFilterExpression: {stock: {$gt: 0}}}) uses partialFilterExpression with {stock: {$gt: 0}}, which matches the requirement.

3. Step 3: Evaluate other options

   db.products.createIndex({stock: 1}) indexes all documents (not partial). db.products.createIndex({stock: 1}, {partialFilterExpression: {stock: 0}}) filters only stock equal to zero, which is wrong. db.products.createIndex({stock: 1}, {filter: {stock: {$gt: 0}}}) uses incorrect option name filter.

4. Final Answer:

   db.products.createIndex({stock: 1}, {partialFilterExpression: {stock: {$gt: 0}}}) -> Option A

5. Quick Check:

   Use partialFilterExpression with correct filter [OK]

Hint: Use partialFilterExpression with correct filter condition [OK]

Common Mistakes:

• Indexing all documents instead of partial
• Using wrong filter values
• Using incorrect option names like 'filter'