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?"

Practice

1. What is the main purpose of a partition key in DynamoDB?

easy

A. To create backups of the database

B. To store large files in the database

C. To encrypt data automatically

D. To divide data into parts for faster access

Solution

1. Step 1: Understand the role of partition key

   The partition key is used to split data into different sections called partitions.

2. Step 2: Recognize the benefit of partitioning

   This splitting helps DynamoDB access data faster by looking in smaller parts instead of the whole table.

3. Final Answer:

   To divide data into parts for faster access -> Option D

4. Quick Check:

   Partition key divides data = faster access [OK]

Hint: Partition key splits data to speed up access [OK]

Common Mistakes:

• Thinking partition key stores files
• Confusing partition key with encryption
• Assuming partition key creates backups

2. Which of the following is the correct way to define a partition key in a DynamoDB table using AWS CLI?

easy

A. aws dynamodb create-table --table-name MyTable --key-schema AttributeName=UserId,KeyType=HASH --attribute-definitions AttributeName=UserId,AttributeType=S --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5

B. aws dynamodb create-table --table-name MyTable --partition-key UserId --attribute-type String

C. aws dynamodb create-table --table-name MyTable --key UserId --type HASH

D. aws dynamodb create-table --table-name MyTable --primary-key UserId STRING

Solution

1. Step 1: Review AWS CLI syntax for creating table with partition key

   The correct syntax uses --key-schema with AttributeName and KeyType=HASH for partition key.

2. Step 2: Check attribute definitions and throughput

   Attribute definitions must specify AttributeName and AttributeType, and provisioned throughput is required.

3. Final Answer:

   aws dynamodb create-table --table-name MyTable --key-schema AttributeName=UserId,KeyType=HASH --attribute-definitions AttributeName=UserId,AttributeType=S --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5 -> Option A

4. Quick Check:

   Correct AWS CLI syntax = aws dynamodb create-table --table-name MyTable --key-schema AttributeName=UserId,KeyType=HASH --attribute-definitions AttributeName=UserId,AttributeType=S --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5 [OK]

Hint: Use --key-schema with KeyType=HASH for partition key [OK]

Common Mistakes:

• Using --partition-key instead of --key-schema
• Missing attribute definitions
• Incorrect key type syntax

3. Given a DynamoDB table with partition key 'UserId' having only two values: 'A' and 'B', what is the likely impact on partition key distribution?

medium

A. Good distribution because two keys are enough

B. Poor distribution causing hot partitions

C. No impact because DynamoDB balances automatically

D. Table will reject writes due to low key variety

Solution

1. Step 1: Understand partition key uniqueness importance

   Partition keys with few unique values cause data to cluster in few partitions.

2. Step 2: Recognize effect of low unique keys

   This clustering leads to hot partitions, slowing down performance and limiting scalability.

3. Final Answer:

   Poor distribution causing hot partitions -> Option B

4. Quick Check:

   Few unique keys = hot partitions [OK]

Hint: Few keys cause hot partitions, hurting performance [OK]

Common Mistakes:

• Assuming two keys are enough for good distribution
• Believing DynamoDB auto-balances all cases
• Thinking table rejects writes for low key variety

4. You notice your DynamoDB table has uneven partition key distribution causing slow queries. Which change will fix this?

medium

A. Change partition key to a field with many unique values

B. Increase read capacity units only

C. Add a sort key with the same values as partition key

D. Delete and recreate the table without changes

Solution

1. Step 1: Identify cause of uneven distribution

   Uneven distribution happens when partition key has few unique values.

2. Step 2: Choose a partition key with high uniqueness

   Changing to a key with many unique values spreads data evenly across partitions, improving performance.

3. Final Answer:

   Change partition key to a field with many unique values -> Option A

4. Quick Check:

   High uniqueness partition key = even distribution [OK]

Hint: Pick partition key with many unique values to fix distribution [OK]

Common Mistakes:

• Only increasing capacity without fixing key
• Adding sort key with same values doesn't help
• Recreating table without changing key

5. You have a DynamoDB table storing orders with partition key 'CustomerId'. Some customers place thousands of orders daily, others only a few. How can you improve partition key distribution to avoid hot partitions?

hard

A. Use 'OrderId' alone as partition key

B. Keep 'CustomerId' as partition key and add 'OrderId' as sort key

C. Use a composite key combining 'CustomerId' and 'OrderDate' as partition key

D. Use a random number as partition key for all orders

Solution

1. Step 1: Identify problem with current partition key

   Using only 'CustomerId' causes hot partitions for customers with many orders.

2. Step 2: Improve distribution by combining keys

   Combining 'CustomerId' and 'OrderDate' creates more unique partition keys, spreading load better.

3. Step 3: Understand why other options fail

   Keep 'CustomerId' as partition key and add 'OrderId' as sort key keeps same partition key, so hot partitions remain; Use 'OrderId' alone as partition key loses customer grouping; Use a random number as partition key for all orders breaks data organization.

4. Final Answer:

   Use a composite key combining 'CustomerId' and 'OrderDate' as partition key -> Option C

5. Quick Check:

   Composite key increases uniqueness, reduces hot partitions [OK]

Hint: Combine keys to increase uniqueness and spread load [OK]

Common Mistakes:

• Adding sort key but not changing partition key
• Using only order ID loses customer grouping
• Random keys break data access patterns