BatchGetItem in DynamoDB - Time & Space Complexity

Time Complexity: BatchGetItem

O(n)

Understanding Time Complexity

When using BatchGetItem in DynamoDB, it's important to know how the time it takes grows as you ask for more items.

We want to understand how the number of requested items affects the work DynamoDB does.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const params = {
  RequestItems: {
    'MyTable': {
      Keys: [
        { id: '1' },
        { id: '2' },
        { id: '3' }
      ]
    }
  }
};

dynamodb.batchGetItem(params, (err, data) => {
  if (err) console.log(err);
  else console.log(data.Responses.MyTable);
});
    

This code requests multiple items from a DynamoDB table in one batch call.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Fetching each item by its key from the table.
• How many times: Once for each key in the batch request.

How Execution Grows With Input

As you ask for more items, DynamoDB does more work roughly proportional to the number of items requested.

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

Pattern observation: The work grows in a straight line as you add more items.

Final Time Complexity

Time Complexity: O(n)

This means the time to get items grows directly with how many items you ask for.

Common Mistake

[X] Wrong: "BatchGetItem fetches all items instantly no matter how many."

[OK] Correct: Each item still needs to be retrieved, so more items mean more work and more time.

Interview Connect

Understanding how batch operations scale helps you design efficient data access and shows you can think about performance clearly.

Self-Check

"What if we split the batch request into multiple smaller batches? How would the time complexity change?"

Practice

1. What is the main purpose of the BatchGetItem operation in DynamoDB?

easy

A. To update multiple items in a table at once.

B. To retrieve multiple items from one or more tables using their primary keys in a single request.

C. To delete multiple items from a table in one call.

D. To scan the entire table and return all items.

Solution

1. Step 1: Understand BatchGetItem functionality

   BatchGetItem is designed to fetch multiple items quickly by specifying their primary keys.

2. Step 2: Compare with other operations

   Unlike update or delete, BatchGetItem only retrieves data, not modifies it.

3. Final Answer:

   To retrieve multiple items from one or more tables using their primary keys in a single request. -> Option B

4. Quick Check:

   BatchGetItem = fetch multiple items [OK]

Hint: BatchGetItem fetches multiple items by keys in one call [OK]

Common Mistakes:

• Confusing BatchGetItem with update or delete operations
• Thinking it scans the whole table
• Assuming it modifies data

2. Which of the following is the correct syntax snippet to specify keys in a BatchGetItem request in DynamoDB?

easy

A. "RequestItems": { "TableName": { "FilterExpression": "Id = :id" } }

B. "RequestItems": { "TableName": { "AttributesToGet": ["Id"] } }

C. "RequestItems": { "TableName": { "Keys": [{ "Id": { "S": "123" } }] } }

D. "RequestItems": { "TableName": { "UpdateExpression": "SET Name = :name" } }

Solution

1. Step 1: Identify BatchGetItem key specification

   BatchGetItem requires a "Keys" array with primary key objects for each item to fetch.

2. Step 2: Check each option

   "RequestItems": { "TableName": { "Keys": [{ "Id": { "S": "123" } }] } } correctly uses "Keys" with primary key format. Snippets using "AttributesToGet", "FilterExpression", or "UpdateExpression" are not valid for BatchGetItem keys.

3. Final Answer:

   "RequestItems": { "TableName": { "Keys": [{ "Id": { "S": "123" } }] } } -> Option C

4. Quick Check:

   Keys array = correct syntax [OK]

Hint: BatchGetItem keys go inside "Keys" array per table [OK]

Common Mistakes:

• Using FilterExpression instead of Keys
• Confusing AttributesToGet with Keys
• Trying to use UpdateExpression in BatchGetItem

3. Given the following BatchGetItem request, what will be the output if the table contains items with Ids 101 and 102 only?

{
  "RequestItems": {
    "Products": {
      "Keys": [
        { "Id": { "N": "101" } },
        { "Id": { "N": "103" } }
      ]
    }
  }
}

medium

A. Returns only item with Id 101

B. Returns all items in the Products table

C. Returns no items because 103 does not exist

D. Returns items with Id 101 and 103

Solution

1. Step 1: Understand BatchGetItem behavior with missing keys

   BatchGetItem returns only items that exist for the specified keys. Missing keys are ignored.

2. Step 2: Analyze given keys

   Id 101 exists, so it will be returned. Id 103 does not exist, so it will be skipped.

3. Final Answer:

   Returns only item with Id 101 -> Option A

4. Quick Check:

   Only existing keys returned [OK]

Hint: BatchGetItem skips missing keys, returns existing only [OK]

Common Mistakes:

• Expecting error if key not found
• Assuming all keys must exist
• Thinking it returns all table items

4. You wrote this BatchGetItem request but it returns a syntax error:

{
  "RequestItems": {
    "Orders": {
      "Keys": {
        "OrderId": { "S": "A123" }
      }
    }
  }
}

What is the error and how to fix it?

medium

A. RequestItems key name is misspelled.

B. OrderId should be a number, not a string.

C. BatchGetItem does not support multiple tables.

D. Keys must be an array of key objects, not a single object.

Solution

1. Step 1: Identify the Keys format error

   Keys must be an array of objects, but here it is a single object, causing syntax error.

2. Step 2: Correct the Keys format

   Wrap the key object inside an array: "Keys": [{ "OrderId": { "S": "A123" } }]

3. Final Answer:

   Keys must be an array of key objects, not a single object. -> Option D

4. Quick Check:

   Keys = array of key objects [OK]

Hint: Keys must always be an array, even for one item [OK]

Common Mistakes:

• Using object instead of array for Keys
• Wrong data type for key attribute
• Misspelling RequestItems

5. You want to fetch items from two tables, "Users" and "Orders", using BatchGetItem. You have 3 user IDs and 2 order IDs. Which of the following request structures correctly fetches all these items in one call?

hard

A. { "RequestItems": { "Users": { "Keys": [ { "UserId": { "S": "U1" } }, { "UserId": { "S": "U2" } }, { "UserId": { "S": "U3" } } ] }, "Orders": { "Keys": [ { "OrderId": { "S": "O1" } }, { "OrderId": { "S": "O2" } } ] } } }

B. { "RequestItems": { "Users": { "Keys": { "UserId": ["U1", "U2", "U3"] } }, "Orders": { "Keys": { "OrderId": ["O1", "O2"] } } } }

C. { "RequestItems": { "Users": { "FilterExpression": "UserId IN (:u1, :u2, :u3)" }, "Orders": { "FilterExpression": "OrderId IN (:o1, :o2)" } } }

D. { "RequestItems": { "Users": { "AttributesToGet": ["UserId"] }, "Orders": { "AttributesToGet": ["OrderId"] } } }

Solution

1. Step 1: Understand BatchGetItem multi-table request format

   BatchGetItem requires "RequestItems" with each table name mapping to a "Keys" array of key objects.

2. Step 2: Evaluate each option

   { "RequestItems": { "Users": { "Keys": [ { "UserId": { "S": "U1" } }, { "UserId": { "S": "U2" } }, { "UserId": { "S": "U3" } } ] }, "Orders": { "Keys": [ { "OrderId": { "S": "O1" } }, { "OrderId": { "S": "O2" } } ] } } } correctly uses arrays of key objects for both tables. Formats using arrays inside objects, FilterExpression, or AttributesToGet are invalid for BatchGetItem keys.

3. Final Answer:

   { "RequestItems": { "Users": { "Keys": [ { "UserId": { "S": "U1" } }, { "UserId": { "S": "U2" } }, { "UserId": { "S": "U3" } } ] }, "Orders": { "Keys": [ { "OrderId": { "S": "O1" } }, { "OrderId": { "S": "O2" } } ] } } } -> Option A

4. Quick Check:

   Keys array per table = correct multi-table BatchGetItem [OK]

Hint: Use Keys array per table for multi-table BatchGetItem [OK]

Common Mistakes:

• Using FilterExpression instead of Keys
• Passing keys as arrays inside objects incorrectly
• Using AttributesToGet instead of Keys