Parallel scan in DynamoDB - Time & Space Complexity

Time Complexity: Parallel scan

O(n / p)

Understanding Time Complexity

When we scan a large DynamoDB table, the time it takes depends on how many items we check. Parallel scan splits this work into parts to do at the same time.

We want to understand how the total work changes when we scan with multiple parts running together.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB parallel scan code.

const params = {
  TableName: "MyTable",
  Segment: segmentNumber,
  TotalSegments: totalSegments
};

const data = await dynamodb.scan(params).promise();
// Repeat for each segment in parallel
    

This code scans one segment of the table. Multiple segments are scanned at the same time to cover the whole table faster.

Identify Repeating Operations

Look at what repeats when scanning in parallel.

• Primary operation: Scanning each segment of the table.
• How many times: Once per segment, all running at the same time.

How Execution Grows With Input

As the table size grows, each segment has more items to scan, so each scan takes longer.

Input Size (n)	Approx. Operations per Segment
10	10 / totalSegments
100	100 / totalSegments
1000	1000 / totalSegments

Pattern observation: The total work is split evenly, so each part does less work as segments increase.

Final Time Complexity

Time Complexity: O(n / p)

This means the time to scan each segment decreases as we increase the number of parallel segments, dividing the total work.

Common Mistake

[X] Wrong: "Parallel scan always makes scanning instant no matter how big the table is."

[OK] Correct: Even with parallel scan, the total work depends on the table size. More segments help, but each segment still scans part of the table, so time reduces but does not disappear.

Interview Connect

Understanding how parallel scan splits work helps you explain how to handle big data efficiently. It shows you can think about dividing tasks to save time, a useful skill in many real projects.

Self-Check

"What if we increase the number of segments beyond the number of CPU cores available? How would that affect the time complexity?"

Practice

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

easy

A. To update multiple items in a table simultaneously

B. To backup data in parallel to another region

C. To create multiple tables for faster access

D. To split a table scan into multiple parts that run at the same time

Solution

1. Step 1: Understand the concept of Parallel Scan

   Parallel Scan divides the scan operation into segments that run concurrently to speed up reading the entire table.

2. Step 2: Identify the main purpose

   The main goal is to speed up scanning by running parts in parallel, not updating or backing up data.

3. Final Answer:

   To split a table scan into multiple parts that run at the same time -> Option D

4. Quick Check:

   Parallel Scan = split scan parts [OK]

Hint: Parallel scan means splitting scan into parts running together [OK]

Common Mistakes:

• Confusing scan with update operations
• Thinking parallel scan creates multiple tables
• Assuming parallel scan is for backup

2. Which two parameters are required to perform a parallel scan in DynamoDB?

easy

A. Segment and TotalSegments

B. PartitionKey and SortKey

C. Limit and FilterExpression

D. IndexName and ProjectionExpression

Solution

1. Step 1: Recall parameters for parallel scan

   Parallel scan requires specifying which segment to scan and how many total segments exist.

2. Step 2: Match parameters to options

   Segment and TotalSegments control the parts of the scan; other options relate to different operations.

3. Final Answer:

   Segment and TotalSegments -> Option A

4. Quick Check:

   Parallel scan params = Segment + TotalSegments [OK]

Hint: Remember: Segment and TotalSegments split the scan [OK]

Common Mistakes:

• Using PartitionKey and SortKey which are for queries
• Confusing Limit with segment control
• Mixing index parameters with scan parameters

3. Given a table with 1000 items and a parallel scan with TotalSegments=5, what does setting Segment=2 do?

medium

A. Scans the first part of the table items

B. Scans all items in the table

C. Scans the third part of the table items

D. Scans only 2 items from the table

Solution

1. Step 1: Understand segment numbering

   Segments are zero-based, so Segment=2 means the third segment out of 5.

2. Step 2: Identify what scanning Segment=2 means

   It scans only the third part of the table, not the whole table or just two items.

3. Final Answer:

   Scans the third part of the table items -> Option C

4. Quick Check:

   Segment=2 means third part scanned [OK]

Hint: Segments start at 0; Segment=2 is third part [OK]

Common Mistakes:

• Thinking Segment=2 scans whole table
• Assuming segments start at 1
• Confusing segment number with item count

4. You wrote this code for parallel scan but it returns incomplete data:

for segment in range(3):
    response = table.scan(Segment=segment, TotalSegments=3)
    print(response['Items'])

What is the likely problem?

medium

A. TotalSegments should be 1 for parallel scan

B. You must combine results from all segments to get full data

C. Segment numbers should start from 1, not 0

D. You cannot use scan with Segment parameter

Solution

1. Step 1: Analyze the code behavior

   The code scans each segment separately but prints results immediately without combining.

2. Step 2: Understand why data is incomplete

   Each segment returns part of data; to get full data, results must be combined from all segments.

3. Final Answer:

   You must combine results from all segments to get full data -> Option B

4. Quick Check:

   Combine all segment results for full scan [OK]

Hint: Combine all segment results to get full table data [OK]

Common Mistakes:

• Starting segments at 1 instead of 0
• Setting TotalSegments to 1 disables parallelism
• Believing scan can't use Segment parameter

5. You want to speed up scanning a large DynamoDB table with 10 million items. You set TotalSegments=10 and run scans in parallel. Which approach ensures you get all items without missing or duplicating data?

hard

A. Run scans for all segments (0 to 9) and combine all results

B. Run scan only on Segment=0 with TotalSegments=10

C. Run scans on segments 1 to 10 (1-based) and combine results

D. Run a single scan without segments to avoid duplicates

Solution

1. Step 1: Understand segment indexing and coverage

   Segments are zero-based, so with TotalSegments=10, segments are 0 through 9.

2. Step 2: Ensure full coverage without overlap

   Running all segments from 0 to 9 and combining results covers entire table exactly once.

3. Step 3: Identify incorrect options

   Running only Segment=0 misses data; segments 1 to 10 are off by one; single scan is slower and not parallel.

4. Final Answer:

   Run scans for all segments (0 to 9) and combine all results -> Option A

5. Quick Check:

   All segments 0-9 combined = full scan [OK]

Hint: Run all zero-based segments and combine results [OK]

Common Mistakes:

• Using 1-based segment numbers instead of 0-based
• Running only one segment expecting full data
• Avoiding parallel scan due to fear of duplicates