Unprocessed items handling in DynamoDB - Time & Space Complexity

Time Complexity: Unprocessed items handling

O(k)

Understanding Time Complexity

When working with DynamoDB batch operations, some items may not process immediately and need retrying.

We want to understand how the time to finish depends on how many items are unprocessed.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

let unprocessedItems = initialBatch;
while (unprocessedItems && Object.keys(unprocessedItems).length > 0) {
  const response = await dynamodb.batchWrite({ RequestItems: unprocessedItems });
  unprocessedItems = response.UnprocessedItems || {};
}
    

This code sends a batch write request and retries only the items that were not processed until all are done.

Identify Repeating Operations

• Primary operation: The while loop that retries unprocessed items.
• How many times: It repeats until no unprocessed items remain, which depends on how many fail each time.

How Execution Grows With Input

Each batch can process many items at once, but some may fail and need retry.

Input Size (n)	Approx. Operations
10	1 to a few retries
100	1 to several retries
1000	Multiple retries, depending on failures

Pattern observation: The total retries grow roughly with how many items remain unprocessed each time, so more unprocessed items mean more retries.

Final Time Complexity

Time Complexity: O(k)

This means the time grows linearly with the number of retry rounds needed to process all unprocessed items.

Common Mistake

[X] Wrong: "All items are processed in one batch call, so time is always constant."

[OK] Correct: Some items may fail and need retries, so the total time depends on how many unprocessed items appear and how many retries happen.

Interview Connect

Understanding how retries affect time helps you explain real-world batch processing behavior clearly and confidently.

Self-Check

"What if the batch size limit changes? How would the time complexity change?"

Practice

1. What does DynamoDB return when some items in a batch write are not processed immediately?

easy

A. An error stopping the entire batch operation

B. A partial success with no retry information

C. A success message without details

D. A list of unprocessed items to retry later

Solution

1. Step 1: Understand batch write behavior

   DynamoDB may not process all items in a batch due to throttling or limits.

2. Step 2: Identify returned data for unprocessed items

   It returns unprocessed items so the client can retry sending them.

3. Final Answer:

   A list of unprocessed items to retry later -> Option D

4. Quick Check:

   Unprocessed items = retry list [OK]

Hint: Unprocessed items mean retry those items later [OK]

Common Mistakes:

• Thinking DynamoDB throws an error instead
• Assuming all items are processed without feedback
• Ignoring unprocessed items in code

2. Which of the following is the correct way to check for unprocessed items in a DynamoDB BatchWriteItem response in Python?

easy

A. if 'UnprocessedItems' in response and response['UnprocessedItems']:

B. if response['UnprocessedItems'] == None:

C. if response['UnprocessedItems'] is False:

D. if 'UnprocessedItems' not in response:

Solution

1. Step 1: Understand response structure

   The response includes 'UnprocessedItems' key if any items were not processed.

2. Step 2: Correctly check for unprocessed items

   Check if 'UnprocessedItems' exists and is not empty to retry those items.

3. Final Answer:

   if 'UnprocessedItems' in response and response['UnprocessedItems']: -> Option A

4. Quick Check:

   Check key exists and is not empty [OK]

Hint: Check key exists and is not empty to find unprocessed items [OK]

Common Mistakes:

• Checking for None instead of empty dict
• Using 'not in' which misses unprocessed items
• Checking for False which is incorrect

3. Given this Python snippet handling DynamoDB batch write:

response = client.batch_write_item(RequestItems=batch)
if response.get('UnprocessedItems'):
    retry_items = response['UnprocessedItems']
else:
    retry_items = None
print(retry_items)

What will be printed if all items were processed successfully?

medium

A. List of all items

B. {}

C. None

D. An error

Solution

1. Step 1: Understand response when all items processed

   If all items are processed, 'UnprocessedItems' key is empty or missing.

2. Step 2: Analyze code behavior

   response.get('UnprocessedItems') returns None or empty dict; if empty dict is falsy, else branch sets retry_items to None.

3. Final Answer:

   None -> Option C

4. Quick Check:

   No unprocessed items means retry_items = None [OK]

Hint: If no unprocessed items, retry_items is None [OK]

Common Mistakes:

• Expecting empty dict instead of None
• Assuming an error is raised
• Thinking retry_items contains all items

4. You wrote this code to resend unprocessed items but it never stops retrying:

while True:
    response = client.batch_write_item(RequestItems=items)
    items = response.get('UnprocessedItems', {})
    if not items:
        break

What is the likely bug causing infinite retries?

medium

A. Missing a delay between retries causing throttling

B. Using 'break' inside the loop incorrectly

C. Not updating 'items' with the new unprocessed items correctly

D. Not checking for empty dictionary properly

Solution

1. Step 1: Analyze the retry loop

   The code updates items correctly but retries immediately without delay.

2. Step 2: Identify the cause of infinite retries

   Missing delay or exponential backoff leads to rapid retries, causing persistent throttling. DynamoDB continually returns the same unprocessed items.

3. Final Answer:

   Missing a delay between retries causing throttling -> Option A

4. Quick Check:

   Add sleep/backoff between retries [OK]

Hint: Add delay or backoff between batch retries to avoid throttling [OK]

Common Mistakes:

• Blaming item update logic instead of throttling
• Assuming empty dict check prevents infinite loops
• Overlooking need for backoff in tight retry loops

5. You want to ensure all items in a large batch are saved in DynamoDB without loss. Which approach best handles unprocessed items efficiently?

hard

A. Split items into single writes to avoid unprocessed items

B. Check for unprocessed items after each batch write and retry them until none remain

C. Send all items once and ignore unprocessed items since they are rare

D. Use batch write once and log unprocessed items without retrying

Solution

1. Step 1: Understand batch write limitations

   DynamoDB batch writes can return unprocessed items due to throttling or limits.

2. Step 2: Best practice for data safety

   Retry unprocessed items repeatedly until all are saved to avoid data loss.

3. Final Answer:

   Check for unprocessed items after each batch write and retry them until none remain -> Option B

4. Quick Check:

   Retry unprocessed items until empty for safe writes [OK]

Hint: Always retry unprocessed items until all are saved [OK]

Common Mistakes:

• Ignoring unprocessed items causing data loss
• Writing items one by one causing inefficiency
• Logging without retrying unprocessed items