Scan pagination in DynamoDB - Time & Space Complexity

Time Complexity: Scan pagination

O(n)

Understanding Time Complexity

When we use scan pagination in DynamoDB, we want to understand how the time to get data grows as we ask for more pages.

We ask: How does the work increase when we read more pages of data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code reads a DynamoDB table in pages of 100 items until all items are read.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning a page of items from the table.
• How many times: Once per page, until all items are read.

How Execution Grows With Input

Each page reads a fixed number of items (100). As the total items grow, the number of pages grows roughly proportionally.

Input Size (n)	Approx. Operations (pages)
10	1 (less than one full page)
100	1 page
1000	10 pages

Pattern observation: The number of scan calls grows linearly with the total items.

Final Time Complexity

Time Complexity: O(n)

This means the time to scan all items grows directly with how many items are in the table.

Common Mistake

[X] Wrong: "Scan pagination time stays the same no matter how many items are in the table."

[OK] Correct: Each page reads a fixed number of items, so more items mean more pages and more scan calls, increasing total time.

Interview Connect

Understanding how scan pagination scales helps you explain how to handle large datasets efficiently and shows you know how to reason about costs in real systems.

Self-Check

"What if we changed the page size from 100 to 1000? How would the time complexity change?"

Practice

1. What is the main purpose of using Scan pagination in DynamoDB?

easy

A. To speed up writes to the database

B. To delete items in batches

C. To create indexes automatically

D. To break a large scan into smaller parts for easier processing

Solution

1. Step 1: Understand Scan Pagination Concept

   Scan pagination is used to divide a large scan operation into smaller chunks to avoid timeouts and manage resource use.

2. Step 2: Identify the Purpose

   The main goal is to process big scans in parts, not to speed writes or create indexes.

3. Final Answer:

   To break a large scan into smaller parts for easier processing -> Option D

4. Quick Check:

   Scan pagination = break large scan into parts [OK]

Hint: Scan pagination splits big scans into smaller chunks [OK]

Common Mistakes:

• Thinking pagination speeds up writes
• Confusing scan with index creation
• Assuming pagination deletes items

2. Which of the following is the correct way to continue a paginated scan in DynamoDB?

easy

A. Use LastEvaluatedKey as the ExclusiveStartKey in the next scan

B. Use Limit as the ExclusiveStartKey

C. Use ScanIndexForward to continue scanning

D. Use StartKey to begin the scan

Solution

1. Step 1: Identify Pagination Parameters

   In DynamoDB, LastEvaluatedKey from the previous scan is used as ExclusiveStartKey to continue scanning.

2. Step 2: Eliminate Incorrect Options

   Limit sets chunk size, not start key. ScanIndexForward is for queries, not scans. StartKey is not a valid parameter.

3. Final Answer:

   Use LastEvaluatedKey as the ExclusiveStartKey in the next scan -> Option A

4. Quick Check:

   Continue scan = ExclusiveStartKey = LastEvaluatedKey [OK]

Hint: Use LastEvaluatedKey as ExclusiveStartKey to continue scan [OK]

Common Mistakes:

• Using Limit as ExclusiveStartKey
• Confusing scan with query parameters
• Using invalid parameter names

3. Given the following scan code snippet, what will be the output if the table has 15 items and Limit is set to 5?

response = table.scan(Limit=5)
items = response['Items']
last_key = response.get('LastEvaluatedKey')
print(len(items), last_key is not None)

medium

A. 5 False

B. 15 False

C. 5 True

D. 15 True

Solution

1. Step 1: Understand Limit Effect on Scan

   Setting Limit=5 returns up to 5 items in one scan call, not all 15.

2. Step 2: Check LastEvaluatedKey Presence

   Since there are more items after 5, LastEvaluatedKey will be present (not None), indicating more data.

3. Final Answer:

   5 True -> Option C

4. Quick Check:

   Limit=5 returns 5 items and LastEvaluatedKey exists [OK]

Hint: Limit controls items returned; LastEvaluatedKey shows more data [OK]

Common Mistakes:

• Assuming all items return ignoring Limit
• Expecting LastEvaluatedKey to be None always
• Confusing item count with total table size

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

response = table.scan(Limit=3)
items = response['Items']
while 'LastEvaluatedKey' in response:
    response = table.scan(Limit=3)
    items.extend(response['Items'])
print(len(items))

What is the error?

medium

A. Missing ExclusiveStartKey in the subsequent scan calls

B. Limit should be increased to get all items

C. Items list should be reset inside the loop

D. LastEvaluatedKey should be deleted after each scan

Solution

1. Step 1: Analyze Pagination Loop

   The loop calls scan repeatedly but does not pass ExclusiveStartKey, so it always scans from start.

2. Step 2: Identify Missing Parameter

   To continue scanning, ExclusiveStartKey must be set to previous LastEvaluatedKey in each call.

3. Final Answer:

   Missing ExclusiveStartKey in the subsequent scan calls -> Option A

4. Quick Check:

   Pagination needs ExclusiveStartKey to continue [OK]

Hint: Pass ExclusiveStartKey to continue scan pages [OK]

Common Mistakes:

• Not passing ExclusiveStartKey in loop
• Increasing Limit instead of fixing pagination
• Resetting items list inside loop

5. You want to scan a DynamoDB table with 1000 items but only want to process 100 items at a time to avoid timeouts. Which approach correctly implements scan pagination to achieve this?

hard

A. Set ExclusiveStartKey to null and scan with Limit=100 once

B. Use a loop with Limit=100 and pass ExclusiveStartKey from LastEvaluatedKey until no more keys

C. Use ScanIndexForward=true with Limit=100 to paginate

D. Scan once with Limit=1000 and split results in code

Solution

1. Step 1: Understand Pagination Requirements

   To process 100 items at a time, scan must be done in chunks with Limit=100 and continue using ExclusiveStartKey.

2. Step 2: Evaluate Options

   Use a loop with Limit=100 and pass ExclusiveStartKey from LastEvaluatedKey until no more keys correctly loops with Limit=100 and uses ExclusiveStartKey from LastEvaluatedKey. Scan once with Limit=1000 and split results in code fetches all at once, risking timeout. Use ScanIndexForward=true with Limit=100 to paginate uses wrong parameter for scan. Set ExclusiveStartKey to null and scan with Limit=100 once scans only once without continuation.

3. Final Answer:

   Use a loop with Limit=100 and pass ExclusiveStartKey from LastEvaluatedKey until no more keys -> Option B

4. Quick Check:

   Paginate with Limit and ExclusiveStartKey loop [OK]

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

Common Mistakes:

• Fetching all items at once risking timeout
• Using query parameters for scan
• Not looping to continue scan