Why Scan reads the entire table in DynamoDB - Performance Analysis

Time Complexity: Why Scan reads the entire table

O(n)

Understanding Time Complexity

When we use a Scan operation in DynamoDB, it looks through the whole table to find data. Understanding how this affects time helps us know why it can be slow for big tables.

We want to see how the work grows as the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const params = {
  TableName: "MyTable"
};

const data = await dynamodb.scan(params).promise();
console.log(data.Items);
    

This code scans the entire "MyTable" to get all items without filtering.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading each item in the table one by one.
• How many times: Once for every item in the table.

How Execution Grows With Input

As the table gets bigger, the scan reads more items, so the work grows directly with the number of items.

Input Size (n)	Approx. Operations
10	Reads 10 items
100	Reads 100 items
1000	Reads 1000 items

Pattern observation: The work grows evenly as the table size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the scan grows directly with the number of items in the table.

Common Mistake

[X] Wrong: "Scan only reads some items, so it's always fast."

[OK] Correct: Scan reads every item in the table, so it takes longer as the table grows.

Interview Connect

Knowing how Scan works helps you explain why some queries are slow and how to choose better ways to get data. This skill shows you understand how databases handle data behind the scenes.

Self-Check

"What if we used a Query operation with a key condition instead of Scan? How would the time complexity change?"