Cost estimation for access patterns in DynamoDB - Time & Space Complexity

Time Complexity: Cost estimation for access patterns

O(n)

Understanding Time Complexity

When using DynamoDB, it is important to understand how the cost of accessing data grows as your data or requests increase.

We want to know how the number of operations changes when we use different ways to get data.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB access pattern.

// Query items by partition key
const params = {
  TableName: "Orders",
  KeyConditionExpression: "CustomerId = :cid",
  ExpressionAttributeValues: {
    ":cid": { S: "12345" }
  }
};
const result = await dynamodb.query(params).promise();
    

This code fetches all orders for one customer using their ID as the partition key.

Identify Repeating Operations

Look for repeated actions that affect cost.

• Primary operation: Reading items matching the partition key.
• How many times: Once per item returned in the query result.

How Execution Grows With Input

As the number of orders for a customer grows, the work to fetch them grows too.

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

Pattern observation: The number of reads grows directly with the number of items returned.

Final Time Complexity

Time Complexity: O(n)

This means the time to get data grows in a straight line with the number of matching items.

Common Mistake

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

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

Interview Connect

Understanding how data access cost grows helps you design better queries and explain your choices clearly in real projects.

Self-Check

"What if we changed the query to use a filter after fetching all partition keys? How would the time complexity change?"

Practice

1. In DynamoDB, what primarily determines the cost of your database usage?

easy

A. The number of read and write operations per second

B. The number of tables you create

C. The size of your database backup files

D. The number of indexes you define

Solution

1. Step 1: Understand DynamoDB cost factors

   DynamoDB charges mainly based on how many read and write requests you perform per second.

2. Step 2: Identify the main cost driver

   While backups and indexes can affect cost, the primary cost is from read/write capacity usage.

3. Final Answer:

   The number of read and write operations per second -> Option A

4. Quick Check:

   Cost depends on read/write operations [OK]

Hint: Focus on read/write operations for cost estimation [OK]

Common Mistakes:

• Thinking table count directly affects cost
• Confusing backup size with operational cost
• Assuming indexes alone drive cost

2. Which of the following is the correct way to calculate the read capacity units (RCUs) for a strongly consistent read of a 3 KB item in DynamoDB?

easy

A. 4 RCUs per 3 KB read

B. 2 RCUs per 3 KB read

C. 0.5 RCU per 3 KB read

D. 1 RCU per 3 KB read

Solution

1. Step 1: Recall RCU calculation for strongly consistent reads

   One RCU allows reading up to 4 KB per second for strongly consistent reads.

2. Step 2: Calculate RCUs for 3 KB item

   Since 3 KB is less than 4 KB, it requires 1 RCU.

3. Final Answer:

   1 RCU per 3 KB read -> Option D

4. Quick Check:

   Strongly consistent read 4 KB = 1 RCU [OK]

Hint: 1 RCU per 4 KB strongly consistent read [OK]

Common Mistakes:

• Confusing strongly consistent with eventually consistent reads
• Miscalculating item size rounding
• Assuming 1 RCU per KB

3. You have a DynamoDB table with items of size 6 KB. You perform 100 eventually consistent reads per second. How many read capacity units (RCUs) do you need?

medium

A. 150 RCUs

B. 100 RCUs

C. 300 RCUs

D. 200 RCUs

Solution

1. Step 1: Calculate RCUs per read for eventually consistent reads

   One RCU allows reading 8 KB per second for eventually consistent reads, which is half the cost of strongly consistent reads.

2. Step 2: Calculate RCUs needed for 6 KB item

   6 KB item requires 2 RCUs for strongly consistent reads (since 6 KB > 4 KB, round up to 2). For eventually consistent reads, it costs half, so 1 RCU per read.

3. Step 3: Calculate total RCUs for 100 reads

   100 reads x 1 RCU = 100 RCUs.

4. Step 4: Correct calculation

   Since 6 KB is more than 4 KB, for eventually consistent reads, each read consumes ceil(6/4) = 2 RCUs * 0.5 = 1 RCU per read. So total 100 RCUs.

5. Final Answer:

   100 RCUs -> Option B

6. Quick Check:

   6 KB item eventually consistent read = 1 RCU per read [OK]

Hint: Eventually consistent reads cost half RCUs [OK]

Common Mistakes:

• Using strongly consistent read calculation for eventually consistent
• Not rounding up item size to nearest 4 KB
• Multiplying incorrectly by number of reads

4. A developer estimates write capacity units (WCUs) for 1 KB items but forgets to account for item size correctly. The code calculates 1 WCU per write regardless of size. What is the likely issue?

medium

A. Incorrectly calculating read capacity units instead

B. Overestimating WCUs for items smaller than 1 KB

C. Underestimating WCUs for items larger than 1 KB

D. No issue, 1 WCU per write is always correct

Solution

1. Step 1: Understand WCU calculation for item size

   One WCU allows writing 1 KB per second. Larger items require more WCUs, rounded up.

2. Step 2: Identify problem with fixed 1 WCU per write

   If item size > 1 KB, fixed 1 WCU underestimates needed capacity, causing throttling or errors.

3. Final Answer:

   Underestimating WCUs for items larger than 1 KB -> Option C

4. Quick Check:

   WCU depends on item size, fixed 1 WCU is wrong [OK]

Hint: Always multiply WCU by item size in KB rounded up [OK]

Common Mistakes:

• Assuming 1 WCU fits all item sizes
• Confusing read and write capacity units
• Ignoring item size when estimating capacity

5. You want to estimate the monthly cost of a DynamoDB table with 50 writes per second of 2 KB items and 100 strongly consistent reads per second of 3 KB items. The price per WCU is $0.00065 and per RCU is $0.00013. What is the approximate monthly cost (30 days)?

hard

A. $56.16

B. $18.72

C. $28.08

D. $36.00

Solution

1. Step 1: Calculate WCUs needed

   Each 2 KB write requires 2 WCUs (ceil(2/1 KB)). 50 writes/sec x 2 = 100 WCUs.

2. Step 2: Calculate RCUs needed

   Each 3 KB strongly consistent read requires 1 RCU (ceil(3/4 KB)). 100 reads/sec x 1 = 100 RCUs.

3. Step 3: Hourly cost

   WCUs: 100 x $0.00065 = $0.065. RCUs: 100 x $0.00013 = $0.013. Total: $0.078/hr.

4. Step 4: Monthly cost

   $0.078 x 24 hrs/day x 30 days = $56.16.

5. Final Answer:

   $56.16 -> Option A

6. Quick Check:

   Calculate WCUs and RCUs x price x time [OK]

Hint: Multiply capacity units by price and hours in month [OK]

Common Mistakes:

• Not rounding item size to nearest KB
• Mixing hourly and monthly rates
• Ignoring strongly consistent read cost