One-to-many relationship patterns in DynamoDB - Time & Space Complexity

Time Complexity: One-to-many relationship patterns

O(n)

Understanding Time Complexity

When working with one-to-many relationships in DynamoDB, it is important to understand how the time to get data grows as the number of related items increases.

We want to know how the cost changes when we fetch many related records for one main item.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query pattern.

// Query to get all orders for a single customer
const params = {
  TableName: "Orders",
  KeyConditionExpression: "customerId = :cid",
  ExpressionAttributeValues: {
    ":cid": { S: "123" }
  }
};
const result = await dynamodb.query(params).promise();

This code fetches all orders linked to one customer using a query on the partition key.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Reading each order item for the customer.
• How many times: Once per order item returned by the query.

How Execution Grows With Input

As the number of orders for a customer grows, the query reads more items.

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

Pattern observation: The number of operations grows directly with the number of related items.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all related items grows linearly with how many items there are.

Common Mistake

[X] Wrong: "Querying related items always takes constant time regardless of how many items exist."

[OK] Correct: Each related item must be read, so more items mean more work and longer time.

Interview Connect

Understanding how queries scale with related data helps you design better data models and answer questions confidently in interviews.

Self-Check

"What if we added pagination to limit the number of related items returned at once? How would the time complexity change?"

Practice

1. What is the main purpose of using a PartitionKey in a one-to-many relationship pattern in DynamoDB?

easy

A. To group all related items under one main item

B. To uniquely identify each related item

C. To store the data type of the item

D. To define the size of the table

Solution

1. Step 1: Understand PartitionKey role

   The PartitionKey groups related items together in DynamoDB, acting like a folder for related data.

2. Step 2: Differentiate PartitionKey from SortKey

   The SortKey uniquely identifies each item within the group, but PartitionKey groups them all.

3. Final Answer:

   To group all related items under one main item -> Option A

4. Quick Check:

   PartitionKey groups related items = D [OK]

Hint: PartitionKey groups items; SortKey identifies each item [OK]

Common Mistakes:

• Confusing PartitionKey with SortKey
• Thinking PartitionKey uniquely identifies each item
• Assuming PartitionKey stores data type

2. Which of the following is the correct way to define a SortKey in a DynamoDB table for a one-to-many relationship?

easy

A. SortKey as the PartitionKey

B. SortKey as the same value for all items

C. SortKey as a unique identifier for each related item

D. SortKey as the table name

Solution

1. Step 1: Understand SortKey purpose

   The SortKey uniquely identifies each related item within the same PartitionKey group.

2. Step 2: Eliminate incorrect options

   SortKey cannot be the same for all items or equal to PartitionKey or table name.

3. Final Answer:

   SortKey as a unique identifier for each related item -> Option C

4. Quick Check:

   SortKey uniquely identifies items = C [OK]

Hint: SortKey uniquely identifies related items within a PartitionKey [OK]

Common Mistakes:

• Using same SortKey for all items
• Confusing SortKey with PartitionKey
• Assigning table name as SortKey

3. Given a DynamoDB table with PartitionKey = 'CustomerID' and SortKey = 'OrderID', what will the query Query(CustomerID='123') return?

medium

A. Only the order with OrderID 123

B. All orders for customer with ID 123

C. All customers with OrderID 123

D. An error because SortKey is missing

Solution

1. Step 1: Understand Query with PartitionKey only

   Querying with PartitionKey='123' returns all items sharing that PartitionKey, i.e., all orders for customer 123.

2. Step 2: Clarify SortKey role in query

   SortKey is not specified, so all SortKey values under PartitionKey='123' are returned.

3. Final Answer:

   All orders for customer with ID 123 -> Option B

4. Quick Check:

   Query by PartitionKey returns all related items = A [OK]

Hint: Query by PartitionKey returns all related items [OK]

Common Mistakes:

• Thinking query returns single item without SortKey
• Confusing PartitionKey and SortKey in query
• Expecting error when SortKey is not specified

4. You have a DynamoDB table with PartitionKey = 'PostID' and SortKey = 'CommentID'. You try to insert two comments with the same PostID and CommentID. What is the issue?

medium

A. The second insert overwrites the first comment

B. Both comments are stored separately

C. DynamoDB throws a syntax error

D. PartitionKey must be unique, so insert fails

Solution

1. Step 1: Understand uniqueness of PartitionKey + SortKey

   In DynamoDB, the combination of PartitionKey and SortKey must be unique for each item.

2. Step 2: Analyze inserting duplicate keys

   Inserting an item with the same PartitionKey and SortKey overwrites the existing item.

3. Final Answer:

   The second insert overwrites the first comment -> Option A

4. Quick Check:

   Duplicate keys overwrite existing item = A [OK]

Hint: Duplicate PartitionKey+SortKey overwrites existing item [OK]

Common Mistakes:

• Expecting error on duplicate keys
• Thinking both items are stored separately
• Confusing PartitionKey uniqueness with SortKey

5. You want to model a one-to-many relationship where each customer can have multiple orders, and each order can have multiple items. Which DynamoDB design pattern best fits this scenario?

hard

A. Use PartitionKey as CustomerID and SortKey as OrderID#ItemID

B. Use PartitionKey as OrderID and SortKey as CustomerID#ItemID

C. Use PartitionKey as ItemID and SortKey as CustomerID#OrderID

D. Use PartitionKey as CustomerID#OrderID and SortKey as ItemID

Solution

1. Step 1: Understand the hierarchy

   Customer has many orders, and each order has many items, so two levels of one-to-many.

2. Step 2: Design composite keys for nested relationships

   Using PartitionKey as CustomerID#OrderID groups items by order under each customer; SortKey as ItemID identifies each item.

3. Step 3: Eliminate other options

   Other options mix keys incorrectly, losing the hierarchical grouping.

4. Final Answer:

   Use PartitionKey as CustomerID#OrderID and SortKey as ItemID -> Option D

5. Quick Check:

   Composite PartitionKey groups nested one-to-many = B [OK]

Hint: Use composite PartitionKey for nested one-to-many groups [OK]

Common Mistakes:

• Using wrong key order losing hierarchy
• Not combining keys for nested relationships
• Confusing PartitionKey and SortKey roles