TTL behavior and timing in DynamoDB - Time & Space Complexity

Time Complexity: TTL behavior and timing

O(n)

Understanding Time Complexity

We want to understand how the time it takes for DynamoDB to remove expired items grows as more items have TTL set.

How does the system handle many items expiring, and how does that affect timing?

Scenario Under Consideration

Analyze the time complexity of DynamoDB's TTL expiration process.

// DynamoDB TTL process (conceptual):
// 1. Scan table for items with TTL attribute set and expired.
// 2. Mark expired items for deletion.
// 3. Delete expired items asynchronously.
// 4. Repeat periodically.
    

This process checks items with TTL timestamps and deletes those expired in batches over time.

Identify Repeating Operations

Look at what repeats during TTL expiration.

• Primary operation: Scanning items to find expired ones.
• How many times: Once per periodic TTL check, scanning many items.

How Execution Grows With Input

As the number of items with TTL grows, the scan to find expired items takes longer.

Input Size (n)	Approx. Operations
10	Scan 10 items for expiration
100	Scan 100 items for expiration
1000	Scan 1000 items for expiration

Pattern observation: The time to find expired items grows roughly in proportion to the number of items checked.

Final Time Complexity

Time Complexity: O(n)

This means the time to process TTL expiration grows linearly with the number of items having TTL.

Common Mistake

[X] Wrong: "TTL expiration happens instantly for each item as soon as it expires."

[OK] Correct: TTL expiration is a background process that scans items periodically, so there can be a delay and the time depends on how many items need checking.

Interview Connect

Understanding how background expiration processes scale helps you reason about system performance and delays in real-world databases.

Self-Check

"What if DynamoDB used an index to track only expired items instead of scanning all? How would the time complexity change?"