Why single-table design matters in DynamoDB - Performance Analysis

Time Complexity: Why single-table design matters

O(n)

Understanding Time Complexity

When using DynamoDB, how we organize data affects how fast queries run.

We want to see how single-table design changes the work DynamoDB does as data grows.

Scenario Under Consideration

Analyze the time complexity of querying data in a single-table design.

    {
      TableName: "MyTable",
      KeyConditionExpression: "PK = :pkValue",
      ExpressionAttributeValues: {
        ":pkValue": "USER#123"
      }
    }
    

This query fetches all items with a partition key for one user in a single table.

Identify Repeating Operations

Look at what repeats when DynamoDB runs this query.

• Primary operation: Reading items with the same partition key.
• How many times: Once per item matching the key, sequentially.

How Execution Grows With Input

As the number of items for a user grows, the work grows too.

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

Pattern observation: The work grows directly with the number of items for that key.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all items grows in a straight line with how many items match the key.

Common Mistake

[X] Wrong: "Using a single table means queries are always faster no matter what."

[OK] Correct: Even with one table, reading many items for a key takes more time because each item must be read.

Interview Connect

Understanding how data layout affects query speed shows you think about real database work and efficiency.

Self-Check

What if we added a sort key to narrow queries? How would that change the time complexity?