Single-table design methodology in DynamoDB - Time & Space Complexity

Time Complexity: Single-table design methodology

O(n)

Understanding Time Complexity

When using single-table design in DynamoDB, it's important to understand how the number of operations changes as your data grows.

We want to know how the time to get or write data changes when the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query using single-table design.

    const params = {
      TableName: "MySingleTable",
      KeyConditionExpression: "PK = :pkValue",
      ExpressionAttributeValues: {
        ":pkValue": "USER#123"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries all items with a partition key of "USER#123" from a single table that stores many entity types together.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Querying items by partition key.
• How many times: The query reads all items matching the partition key, which depends on how many related items the user has.

How Execution Grows With Input

As the number of items for a user grows, the query reads more data.

Input Size (n)	Approx. Operations
10	Reads 10 items
100	Reads 100 items
1000	Reads 1000 items

Pattern observation: The time grows roughly in direct proportion to the number of items matching the partition key.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all items grows linearly with how many items share the same partition key.

Common Mistake

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

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

Interview Connect

Understanding how single-table design affects query time helps you explain your choices clearly and shows you know how data size impacts performance.

Self-Check

"What if we added a sort key condition to limit results? How would that change the time complexity?"

Practice

1. What is the main advantage of using single-table design in DynamoDB?

easy

A. It requires multiple tables for each data type to keep data separate.

B. It allows storing different types of related data in one table for faster queries.

C. It automatically creates indexes for all attributes without setup.

D. It stores data only in JSON format for easy reading.

Solution

1. Step 1: Understand single-table design purpose

   Single-table design stores multiple related data types in one table to reduce the number of queries needed.

2. Step 2: Compare options with this purpose

   It allows storing different types of related data in one table for faster queries. matches this purpose. Options B, C, and D describe incorrect or unrelated features.

3. Final Answer:

   It allows storing different types of related data in one table for faster queries. -> Option B

4. Quick Check:

   Single-table design = faster queries with one table [OK]

Hint: Single-table design means one table for related data [OK]

Common Mistakes:

• Thinking single-table means multiple tables
• Assuming automatic index creation
• Confusing data format with design method

2. Which of the following is the correct way to define a partition key in a DynamoDB table using single-table design?

easy

A. PartitionKey: orderId, SortKey: userId

B. PartitionKey: userId#orderId

C. PartitionKey: userId, SortKey: orderId

D. PartitionKey: orderId#userId

Solution

1. Step 1: Recall key structure in single-table design

   Single-table design uses a partition key and a sort key to organize data efficiently.

2. Step 2: Identify correct key assignment

   PartitionKey: userId, SortKey: orderId correctly assigns userId as partition key and orderId as sort key, which is common for grouping orders by user.

3. Final Answer:

   PartitionKey: userId, SortKey: orderId -> Option C

4. Quick Check:

   Partition and sort keys = userId and orderId [OK]

Hint: Partition key groups items; sort key orders them [OK]

Common Mistakes:

• Using combined keys as partition key only
• Swapping partition and sort keys incorrectly
• Using concatenated keys without sort key

3. Given a DynamoDB table with partition key PK and sort key SK, which query will fetch all orders for user with ID 'user123' if orders are stored with PK = 'USER#user123' and SK = 'ORDER#orderId'?

medium

A. Query with KeyConditionExpression: PK = 'ORDER#orderId' AND SK = 'USER#user123'

B. Query with KeyConditionExpression: PK = 'USER#user123' AND SK = 'ORDER#orderId'

C. Scan with FilterExpression: PK = 'USER#user123'

D. Query with KeyConditionExpression: PK = 'USER#user123' AND SK begins_with 'ORDER#'

Solution

1. Step 1: Understand key structure for orders

   Orders have PK as 'USER#user123' and SK starting with 'ORDER#', so all orders share the same PK but different SKs.

2. Step 2: Identify query to fetch all orders for user

   Query with KeyConditionExpression: PK = 'USER#user123' AND SK begins_with 'ORDER#' queries PK equal to 'USER#user123' and SK that begins with 'ORDER#', which fetches all orders for that user.

3. Final Answer:

   Query with KeyConditionExpression: PK = 'USER#user123' AND SK begins_with 'ORDER#' -> Option D

4. Quick Check:

   PK fixed, SK prefix filter = all user orders [OK]

Hint: Use begins_with on sort key to get related items [OK]

Common Mistakes:

• Swapping PK and SK in query
• Using scan instead of query
• Filtering SK with exact match instead of prefix

4. You wrote this query to get all comments for a post in a single-table design DynamoDB table:

KeyConditionExpression: PK = 'POST#123' AND SK = 'COMMENT#'

Why does this query return no results?

medium

A. Because SK uses '=' instead of 'begins_with' to match multiple comments.

B. Because PK should be 'COMMENT#' and SK should be 'POST#123'.

C. Because the table does not support queries on SK.

D. Because the query syntax is missing a FilterExpression.

Solution

1. Step 1: Analyze the KeyConditionExpression

   The query uses SK = 'COMMENT#', which looks for an exact match on SK.

2. Step 2: Understand why no results appear

   Comments likely have SK starting with 'COMMENT#' plus an ID, so exact match fails. Using 'begins_with' on SK is needed to get all comments.

3. Final Answer:

   Because SK uses '=' instead of 'begins_with' to match multiple comments. -> Option A

4. Quick Check:

   Use begins_with for multiple SK matches [OK]

Hint: Use begins_with for partial sort key matches [OK]

Common Mistakes:

• Using '=' instead of begins_with on SK
• Swapping PK and SK in query
• Assuming FilterExpression fixes key condition

5. You want to design a single DynamoDB table to store users, their orders, and order items. Which key design best supports fetching all orders and items for a user efficiently?

hard

A. PartitionKey: USER#userId, SortKey: ORDER#orderId for orders; PartitionKey: ORDER#orderId, SortKey: ITEM#itemId for items

B. PartitionKey: userId, SortKey: orderId#itemId for all data types

C. PartitionKey: USER#userId, SortKey: ORDER#orderId#ITEM#itemId for all items and orders

D. PartitionKey: ITEM#itemId, SortKey: ORDER#orderId for all data

Solution

1. Step 1: Understand data grouping needs

   We want to fetch all orders and items for a user efficiently, so grouping orders by user and items by order is key.

2. Step 2: Evaluate key designs

   PartitionKey: USER#userId, SortKey: ORDER#orderId for orders; PartitionKey: ORDER#orderId, SortKey: ITEM#itemId for items uses USER#userId as partition key for orders and ORDER#orderId as partition key for items, allowing efficient queries by user and order. Other options mix keys or combine too much, making queries inefficient.

3. Final Answer:

   PartitionKey: USER#userId, SortKey: ORDER#orderId for orders; PartitionKey: ORDER#orderId, SortKey: ITEM#itemId for items -> Option A

4. Quick Check:

   Group orders by user, items by order = PartitionKey: USER#userId, SortKey: ORDER#orderId for orders; PartitionKey: ORDER#orderId, SortKey: ITEM#itemId for items [OK]

Hint: Group data by parent keys for efficient queries [OK]

Common Mistakes:

• Using one partition key for all data types
• Combining all keys into one long sort key
• Using item ID as partition key for all data