TTL indexes for auto-expiry in MongoDB - Time & Space Complexity

Time Complexity: TTL indexes for auto-expiry

O(log n + m)

Understanding Time Complexity

When using TTL indexes in MongoDB, it's important to understand how the system handles automatic deletion of expired documents.

We want to know how the time to remove expired data grows as the collection gets bigger.

Scenario Under Consideration

Analyze the time complexity of this TTL index setup and expiry process.

// Create TTL index on 'createdAt' field with 3600 seconds expiry
db.collection.createIndex({ createdAt: 1 }, { expireAfterSeconds: 3600 })

// MongoDB background thread periodically removes expired documents
// No explicit query needed; system handles expiry automatically
    

This code creates a TTL index that automatically deletes documents older than one hour.

Identify Repeating Operations

MongoDB runs a background thread that periodically scans for expired documents.

• Primary operation: Scanning documents with the TTL index to find expired ones.
• How many times: This scan repeats regularly, roughly every 60 seconds.

How Execution Grows With Input

The background thread uses the TTL index to quickly find expired documents without scanning the whole collection.

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

Pattern observation: The time to find expired documents grows slowly because the TTL index helps avoid scanning all documents.

Final Time Complexity

Time Complexity: O(log n + m)

This means the time to find expired documents grows slowly as the collection grows, thanks to the index, plus the time to delete the expired documents (m).

Common Mistake

[X] Wrong: "TTL expiry scans every document in the collection each time it runs."

[OK] Correct: MongoDB uses the TTL index to quickly locate expired documents, so it does not scan all documents every time.

Interview Connect

Understanding how TTL indexes work and their time complexity shows you know how databases handle automatic cleanup efficiently.

Self-Check

"What if the TTL index was on a non-indexed field? How would the time complexity change?"