Pagination with SDK in DynamoDB - Time & Space Complexity

Time Complexity: Pagination with SDK

O(n)

Understanding Time Complexity

When using pagination with the DynamoDB SDK, we want to know how the time to get data changes as we ask for more pages.

We ask: How does the number of operations grow when we fetch more pages of results?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB SDK pagination code.

const params = { TableName: "MyTable", Limit: 10 };
let lastEvaluatedKey = null;
do {
  if (lastEvaluatedKey) {
    params.ExclusiveStartKey = lastEvaluatedKey;
  }
  const data = await dynamodbClient.scan(params).promise();
  lastEvaluatedKey = data.LastEvaluatedKey;
  processItems(data.Items);
} while (lastEvaluatedKey);
    

This code fetches items from a DynamoDB table in pages of 10, using the last key from the previous page to get the next.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: Calling the scan method to fetch a page of items.
• How many times: Once per page until no more pages remain.

How Execution Grows With Input

Each page fetch is a separate operation. More pages mean more calls.

Input Size (pages)	Approx. Operations (scan calls)
10	10
100	100
1000	1000

Pattern observation: The number of operations grows directly with the number of pages requested.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of pages you fetch.

Common Mistake

[X] Wrong: "Fetching more pages is just one operation because it's one loop."

[OK] Correct: Each page requires a separate network call and scan operation, so time adds up with each page.

Interview Connect

Understanding how pagination affects time helps you design efficient data fetching in real apps and shows you can think about performance clearly.

Self-Check

"What if we changed the Limit parameter to fetch 100 items per page instead of 10? How would the time complexity change?"

Practice

1. What does the Limit parameter do when paginating results in DynamoDB SDK?

easy

A. It specifies the starting point for the next page.

B. It sets the maximum number of items returned in one page.

C. It filters items based on a condition.

D. It sorts the results in ascending order.

Solution

1. Step 1: Understand the role of Limit in pagination

   The Limit parameter controls how many items DynamoDB returns in a single request, effectively setting the page size.

2. Step 2: Differentiate from other parameters

   ExclusiveStartKey sets the starting point for the next page, not Limit. Filtering and sorting are handled differently.

3. Final Answer:

   It sets the maximum number of items returned in one page. -> Option B

4. Quick Check:

   Limit = page size [OK]

Hint: Limit controls page size, not start or filter [OK]

Common Mistakes:

• Confusing Limit with ExclusiveStartKey
• Thinking Limit filters data
• Assuming Limit sorts results

2. Which of the following is the correct way to continue fetching the next page of results in DynamoDB SDK?

easy

A. Set StartKey to zero.

B. Use Limit with the last item key.

C. Set ExclusiveStartKey to the last evaluated key from previous response.

D. Use NextPageToken parameter.

Solution

1. Step 1: Identify the parameter for pagination continuation

   DynamoDB uses ExclusiveStartKey to tell the query where to start for the next page.

2. Step 2: Verify other options

   Limit sets page size, StartKey is not a valid parameter, and NextPageToken is not used in DynamoDB SDK.

3. Final Answer:

   Set ExclusiveStartKey to the last evaluated key from previous response. -> Option C

4. Quick Check:

   Use ExclusiveStartKey for next page [OK]

Hint: Use ExclusiveStartKey to continue pagination [OK]

Common Mistakes:

• Using Limit to continue pages
• Using invalid parameter StartKey
• Assuming NextPageToken exists in DynamoDB

3. Given the following DynamoDB SDK code snippet, what will be the output if LastEvaluatedKey is not empty?

const params = { TableName: 'Books', Limit: 2 };
const data = await dynamoDbClient.scan(params);
console.log(data.Items.length);
console.log(data.LastEvaluatedKey !== undefined);

medium

A. Error due to missing ExclusiveStartKey

B. All items and false

C. 2 and false

D. 2 and true

Solution

1. Step 1: Understand Limit effect on Items returned

   With Limit: 2, the scan returns at most 2 items, so data.Items.length will be 2.

2. Step 2: Check LastEvaluatedKey presence

   If LastEvaluatedKey is not empty, it means more pages exist, so data.LastEvaluatedKey !== undefined is true.

3. Final Answer:

   2 and true -> Option D

4. Quick Check:

   Limit = 2 items, LastEvaluatedKey present = true [OK]

Hint: Limit caps items; LastEvaluatedKey true means more pages [OK]

Common Mistakes:

• Assuming all items returned ignoring Limit
• Thinking LastEvaluatedKey is false when present
• Expecting error without ExclusiveStartKey

4. You wrote this code to paginate DynamoDB scan results but it returns only the first page repeatedly:

let params = { TableName: 'Users', Limit: 3 };
let data;
do {
  data = await dynamoDbClient.scan(params);
  console.log(data.Items);
} while (data.LastEvaluatedKey);

What is the main issue?

medium

A. Missing update of ExclusiveStartKey in params inside the loop.

B. Limit should be increased to fetch all items.

C. The loop condition should check data.Items instead.

D. The scan method does not support pagination.

Solution

1. Step 1: Analyze loop behavior

   The code calls scan repeatedly but never updates ExclusiveStartKey, so it fetches the same first page each time.

2. Step 2: Identify correct fix

   To get next pages, params.ExclusiveStartKey must be set to data.LastEvaluatedKey inside the loop.

3. Final Answer:

   Missing update of ExclusiveStartKey in params inside the loop. -> Option A

4. Quick Check:

   Update ExclusiveStartKey to paginate [OK]

Hint: Update ExclusiveStartKey each loop to get next page [OK]

Common Mistakes:

• Not updating ExclusiveStartKey inside loop
• Increasing Limit instead of paginating
• Wrong loop condition on Items
• Thinking scan can't paginate

5. You want to fetch all items from a large DynamoDB table using pagination with the SDK. Which approach correctly handles this scenario?

hard

A. Use a loop that calls scan with Limit, updating ExclusiveStartKey each time until LastEvaluatedKey is undefined.

B. Call scan once with a very large Limit to get all items at once.

C. Use scan without Limit and stop when Items array is empty.

D. Call scan repeatedly without ExclusiveStartKey until Items length is zero.

Solution

1. Step 1: Understand DynamoDB pagination for large tables

   Large tables require multiple scan calls with a Limit to avoid timeouts and memory issues.

2. Step 2: Correctly implement pagination loop

   Each scan call should use ExclusiveStartKey from the previous LastEvaluatedKey until it is undefined, indicating no more pages.

3. Final Answer:

   Use a loop that calls scan with Limit, updating ExclusiveStartKey each time until LastEvaluatedKey is undefined. -> Option A

4. Quick Check:

   Loop with Limit and ExclusiveStartKey until done [OK]

Hint: Loop with Limit and ExclusiveStartKey until no LastEvaluatedKey [OK]

Common Mistakes:

• Using huge Limit causing timeouts
• Ignoring ExclusiveStartKey for next pages
• Stopping on empty Items instead of LastEvaluatedKey
• Calling scan repeatedly without pagination