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

Practice

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

easy

A. It sets the maximum size of the table.

B. It defines the data type of the table.

C. It determines how data is distributed across storage nodes.

D. It controls the read and write capacity of the table.

Solution

1. Step 1: Understand partition key purpose

   The partition key is used to decide where data is stored in DynamoDB's distributed system.

2. Step 2: Compare options

   Only It determines how data is distributed across storage nodes. correctly describes this role; others describe unrelated features.

3. Final Answer:

   It determines how data is distributed across storage nodes. -> Option C

4. Quick Check:

   Partition key = data distribution [OK]

Hint: Partition key decides data location in storage [OK]

Common Mistakes:

• Confusing partition key with capacity settings
• Thinking partition key sets data type
• Assuming partition key limits table size

2. Which of the following is a valid way to define a partition key in a DynamoDB table creation command?

easy

A. "KeySchema": [{"AttributeName": "UserId", "KeyType": "HASH"}]

B. "KeySchema": [{"AttributeName": "UserId", "KeyType": "RANGE"}]

C. "KeySchema": [{"AttributeName": "UserId", "KeyType": "PRIMARY"}]

D. "KeySchema": [{"AttributeName": "UserId", "KeyType": "INDEX"}]

Solution

1. Step 1: Recall partition key syntax

   Partition key uses KeyType "HASH" in DynamoDB KeySchema.

2. Step 2: Check each option

   Only "KeySchema": [{"AttributeName": "UserId", "KeyType": "HASH"}] uses "HASH" correctly; others use invalid or incorrect KeyType values.

3. Final Answer:

   "KeySchema": [{"AttributeName": "UserId", "KeyType": "HASH"}] -> Option A

4. Quick Check:

   Partition key = KeyType HASH [OK]

Hint: Partition key uses KeyType 'HASH' in schema [OK]

Common Mistakes:

• Using RANGE instead of HASH for partition key
• Confusing PRIMARY or INDEX as KeyType
• Misnaming KeyType values

3. Given a DynamoDB table with partition key UserId having many unique values, and sort key OrderDate, what will happen if you query with UserId = '123' only?

medium

A. The query will fail because sort key is missing.

B. You get all orders for user '123' sorted by OrderDate.

C. You get only one order for user '123' without sorting.

D. You get all orders for all users sorted by OrderDate.

Solution

1. Step 1: Understand query with partition key only

   Querying with partition key returns all items with that key, optionally sorted by sort key.

2. Step 2: Analyze given keys

   Since UserId is partition key and OrderDate is sort key, querying UserId='123' returns all orders for that user sorted by OrderDate.

3. Final Answer:

   You get all orders for user '123' sorted by OrderDate. -> Option B

4. Quick Check:

   Query by partition key returns all matching items [OK]

Hint: Query by partition key returns all matching items [OK]

Common Mistakes:

• Thinking query needs sort key value
• Expecting only one item without sort key
• Assuming query returns all users' data

4. You designed a DynamoDB table with CustomerId as partition key but notice hot partitions causing slow performance. What is the likely cause?

medium

A. CustomerId has too many unique values causing large partitions.

B. CustomerId is used as sort key instead of partition key.

C. CustomerId is missing from the KeySchema.

D. CustomerId has very few unique values causing uneven data distribution.

Solution

1. Step 1: Understand hot partitions

   Hot partitions happen when few partition keys get most traffic, causing uneven load.

2. Step 2: Analyze CustomerId uniqueness

   If CustomerId has few unique values, many requests hit same partitions causing hot spots.

3. Final Answer:

   CustomerId has very few unique values causing uneven data distribution. -> Option D

4. Quick Check:

   Few unique keys = hot partitions [OK]

Hint: Few unique partition keys cause hot partitions [OK]

Common Mistakes:

• Assuming too many unique keys cause hot partitions
• Confusing missing key with performance issue
• Mixing partition key with sort key roles

5. You want to design a DynamoDB table to store IoT sensor data from thousands of devices. Which partition key choice will best support even data distribution and scalability?

hard

A. Use DeviceId as partition key because it has many unique values.

B. Use a constant string like 'SensorData' as partition key for all items.

C. Use Timestamp as partition key to sort data by time.

D. Use DeviceType as partition key since it groups similar devices.

Solution

1. Step 1: Identify key with many unique values

   DeviceId uniquely identifies each device, providing many distinct partition keys.

2. Step 2: Evaluate other options

   Constant string causes hot partition; Timestamp changes too fast for partition key; DeviceType groups few devices causing uneven load.

3. Final Answer:

   Use DeviceId as partition key because it has many unique values. -> Option A

4. Quick Check:

   Many unique keys = good partition key [OK]

Hint: Choose partition key with many unique values [OK]

Common Mistakes:

• Using constant value causing hot partitions
• Choosing timestamp as partition key
• Grouping by device type causing uneven load