Sparse index pattern in DynamoDB - Time & Space Complexity

Time Complexity: Sparse index pattern

O(m)

Understanding Time Complexity

When using a sparse index in DynamoDB, we want to know how the time to find data changes as the data grows.

We ask: How does the search time grow when the table and index get bigger?

Scenario Under Consideration

Analyze the time complexity of this sparse index query.

    const params = {
      TableName: "Orders",
      IndexName: "StatusIndex", // sparse index on 'status'
      KeyConditionExpression: "status = :s",
      ExpressionAttributeValues: {
        ":s": "SHIPPED"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries only items with status "SHIPPED" using a sparse index that stores only those items.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Scanning the sparse index entries matching the status.
• How many times: Once per matching item in the sparse index, not the whole table.

How Execution Grows With Input

As the number of items with status "SHIPPED" grows, the query takes longer.

Input Size (n)	Approx. Operations
10 shipped items	10 reads
100 shipped items	100 reads
1000 shipped items	1000 reads

Pattern observation: The time grows linearly with the number of matching items, not the total table size.

Final Time Complexity

Time Complexity: O(m)

This means the query time grows in direct proportion to the number of items matching the sparse index condition.

Common Mistake

[X] Wrong: "Querying a sparse index is as slow as scanning the whole table."

[OK] Correct: The sparse index only contains items with the indexed attribute, so the query touches fewer items, making it faster.

Interview Connect

Understanding sparse indexes helps you explain how to efficiently query subsets of data, a useful skill in real projects.

Self-Check

"What if the sparse index included multiple attributes for filtering? How would that affect the time complexity?"