Partition key distribution in DynamoDB - Time & Space Complexity

Time Complexity: Partition key distribution

O(n)

Understanding Time Complexity

When using DynamoDB, how your data is spread across partitions affects how fast your queries run.

We want to understand how the choice of partition keys changes the work DynamoDB does as data grows.

Scenario Under Consideration

Analyze the time complexity of querying items with a given partition key.

    const params = {
      TableName: "Orders",
      KeyConditionExpression: "PartitionKey = :pk",
      ExpressionAttributeValues: {
        ":pk": { S: "USER#123" }
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code fetches all items that share the same partition key "USER#123" from the Orders table.

Identify Repeating Operations

Look for repeated work done when fetching data.

• Primary operation: Scanning all items within one partition matching the key.
• How many times: Once per query, but the number of items in that partition can vary.

How Execution Grows With Input

As more items share the same partition key, the query must read more data.

Input Size (items in partition)	Approx. Operations
10	10 reads
100	100 reads
1000	1000 reads

Pattern observation: The work grows directly with how many items share the partition key.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with the number of items in the chosen partition.

Common Mistake

[X] Wrong: "Querying by partition key always takes the same time no matter how many items it has."

[OK] Correct: The query reads all items in that partition, so more items mean more work and longer time.

Interview Connect

Understanding how partition key choice affects query speed shows you know how to design scalable databases.

Self-Check

"What if the partition key is very unique and only has one item each? How would that change the time complexity?"