Partition key selection in DynamoDB - Time & Space Complexity

Time Complexity: Partition key selection

O(n)

Understanding Time Complexity

Choosing the right partition key in DynamoDB affects how fast your queries run.

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

Scenario Under Consideration

Analyze the time complexity of querying items by partition key.

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

This code fetches all items that share the same partition key value.

Identify Repeating Operations

Look for repeated work done when fetching data.

• Primary operation: Scanning all items within the partition key.
• How many times: Once per item in that partition.

How Execution Grows With Input

As more items share the same partition key, the query takes longer.

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

Pattern observation: The work grows directly with the number of items in the partition.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows in a straight line with how many items share the partition key.

Common Mistake

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

[OK] Correct: The query must read each item 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 efficient databases.

Self-Check

"What if we added a sort key and queried with both partition and sort key? How would the time complexity change?"