Multikey indexes for arrays in MongoDB - Time & Space Complexity

Time Complexity: Multikey indexes for arrays

O(n)

Understanding Time Complexity

When MongoDB uses multikey indexes on arrays, it creates index entries for each element in the array. Understanding how this affects query time is important.

We want to know how the number of array elements changes the work MongoDB does when searching.

Scenario Under Consideration

Analyze the time complexity of querying a collection with a multikey index on an array field.

    db.products.createIndex({ tags: 1 })
    db.products.find({ tags: "organic" })
    

This code creates a multikey index on the 'tags' array field and then queries for documents containing the tag "organic".

Identify Repeating Operations

Look at what repeats when MongoDB uses a multikey index.

• Primary operation: Index entries are created for each element in every array in the collection.
• How many times: For each document, once per array element in the indexed field.

How Execution Grows With Input

As the number of array elements grows, the index size and search work grow too.

Input Size (n)	Approx. Operations
10 elements per array	About 10 index entries checked
100 elements per array	About 100 index entries checked
1000 elements per array	About 1000 index entries checked

Pattern observation: The work grows roughly in direct proportion to the number of array elements.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of elements in the array field being indexed.

Common Mistake

[X] Wrong: "Multikey indexes make queries run in constant time regardless of array size."

[OK] Correct: Each array element creates an index entry, so more elements mean more entries to check, increasing query time.

Interview Connect

Knowing how multikey indexes scale helps you explain database performance clearly and shows you understand how data structure affects query speed.

Self-Check

"What if the array field contained nested arrays? How would that affect the time complexity of queries using multikey indexes?"

Practice

1. What is the main purpose of a multikey index in MongoDB when applied to an array field?

easy

A. To index each element inside the array separately for faster queries

B. To store the entire array as a single indexed value

C. To prevent duplicate values inside the array

D. To convert arrays into strings before indexing

Solution

1. Step 1: Understand what a multikey index does

   A multikey index indexes each element of an array field separately, allowing efficient queries on any element inside the array.

2. Step 2: Compare options with this behavior

   Only To index each element inside the array separately for faster queries describes indexing each element separately. Other options describe incorrect behaviors.

3. Final Answer:

   To index each element inside the array separately for faster queries -> Option A

4. Quick Check:

   Multikey index = indexes array elements separately [OK]

Hint: Multikey indexes each array element, not the whole array [OK]

Common Mistakes:

• Thinking multikey indexes the whole array as one value
• Confusing multikey with unique constraints
• Assuming arrays are converted to strings before indexing

2. Which of the following is the correct syntax to create a multikey index on the tags array field in a MongoDB collection named posts?

easy

A. db.posts.createIndex({ tags: [1] })

B. db.posts.createIndex({ tags: 1 })

C. db.posts.createIndex({ tags: 'multikey' })

D. db.posts.createIndex({ tags: { $each: 1 } })

Solution

1. Step 1: Recall MongoDB index creation syntax

   To create an index on a field, use createIndex({ field: 1 }) for ascending order.

2. Step 2: Understand multikey index creation

   MongoDB automatically creates a multikey index if the field is an array. No special keyword is needed.

3. Final Answer:

   db.posts.createIndex({ tags: 1 }) -> Option B

4. Quick Check:

   Index array field normally = multikey index [OK]

Hint: Just index the array field normally; MongoDB handles multikey [OK]

Common Mistakes:

• Using special keywords like 'multikey' in index definition
• Trying to pass array syntax in index keys
• Misusing MongoDB operators inside createIndex

3. Given the collection products with documents like { _id: 1, categories: ["electronics", "gadgets"] }, what will be the result of the query db.products.find({ categories: "gadgets" }) if a multikey index exists on categories?

medium

A. [{ _id: 1, categories: ["electronics"] }]

B. [] (empty array)

C. Error: Cannot query array field

D. [{ _id: 1, categories: ["electronics", "gadgets"] }]

Solution

1. Step 1: Understand query on array field with multikey index

   The query searches for documents where the array contains "gadgets". The multikey index allows fast lookup of such elements.

2. Step 2: Check the document matching the query

   The document with _id 1 has "gadgets" in its categories array, so it matches and will be returned.

3. Final Answer:

   [{ _id: 1, categories: ["electronics", "gadgets"] }] -> Option D

4. Quick Check:

   Query array element with multikey index returns matching docs [OK]

Hint: Query matches docs with array containing the value [OK]

Common Mistakes:

• Expecting empty result because array is indexed
• Thinking query errors on array fields
• Confusing partial array matches with exact matches

4. You created a multikey index on the tags array field, but your query db.articles.find({ tags: "news" }) is slow. What is a likely reason?

medium

A. The index was created on a different field, not tags

B. Multikey indexes do not support queries on array elements

C. You must use $elemMatch to query array fields

D. MongoDB does not index array fields automatically

Solution

1. Step 1: Check index field correctness

   If the index is on a different field, queries on tags won't use the index, causing slowness.

2. Step 2: Verify multikey index behavior

   Multikey indexes do support queries on array elements without special operators like $elemMatch.

3. Final Answer:

   The index was created on a different field, not tags -> Option A

4. Quick Check:

   Index on correct field = fast query [OK]

Hint: Ensure index is on the queried array field [OK]

Common Mistakes:

• Believing multikey indexes don't support element queries
• Thinking $elemMatch is always required
• Assuming MongoDB indexes arrays automatically without createIndex

5. You have a collection users with documents containing an array field roles. You want to create a multikey index on roles but only for users who are active (active: true). Which is the correct way to create a partial multikey index for this?

hard

A. db.users.createIndex({ roles: 1 }, { condition: { active: true } })

B. db.users.createIndex({ roles: 1, active: true })

C. db.users.createIndex({ roles: 1 }, { partialFilterExpression: { active: true } })

D. db.users.createIndex({ roles: 1 }, { filter: { active: true } })

Solution

1. Step 1: Understand partial indexes in MongoDB

   Partial indexes use partialFilterExpression to index only documents matching a filter.

2. Step 2: Apply partialFilterExpression with multikey index

   Creating an index on roles with partialFilterExpression: { active: true } indexes only active users' roles.

3. Final Answer:

   db.users.createIndex({ roles: 1 }, { partialFilterExpression: { active: true } }) -> Option C

4. Quick Check:

   Use partialFilterExpression for conditional multikey index [OK]

Hint: Use partialFilterExpression option for conditional indexes [OK]

Common Mistakes:

• Using invalid options like filter or condition
• Trying to include filter in index key object
• Not knowing partialFilterExpression syntax