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?"

Practice

1. Why does the Scan operation in DynamoDB read the entire table?

easy

A. Because it only reads the first item in the table

B. Because it uses indexes to find items quickly

C. Because it checks every item to find matches without using keys

D. Because it reads only the items with matching partition keys

Solution

1. Step 1: Understand Scan operation behavior

   Scan reads every item in the table one by one to find matching data because it does not use keys or indexes.

2. Step 2: Compare with other operations

   Unlike Query, which uses keys to find items quickly, Scan must read the whole table.

3. Final Answer:

   Because it checks every item to find matches without using keys -> Option C

4. Quick Check:

   Scan reads all items = B [OK]

Hint: Scan reads all items; Query uses keys for speed [OK]

Common Mistakes:

• Thinking Scan reads only some items
• Confusing Scan with Query
• Assuming Scan uses indexes

2. Which of the following is the correct syntax to perform a Scan operation in DynamoDB using AWS SDK?

easy

A. dynamodb.query({ TableName: 'MyTable' }, callback);

B. dynamodb.scan({ TableName: 'MyTable' }, callback);

C. dynamodb.getItem({ TableName: 'MyTable' }, callback);

D. dynamodb.update({ TableName: 'MyTable' }, callback);

Solution

1. Step 1: Identify Scan method usage

   The Scan operation uses the scan method with the table name as a parameter.

2. Step 2: Differentiate from other methods

   query is for key-based queries, getItem fetches a single item, and update modifies items.

3. Final Answer:

   dynamodb.scan({ TableName: 'MyTable' }, callback); -> Option B

4. Quick Check:

   Scan uses scan() method = A [OK]

Hint: Scan uses scan() method, not query() or getItem() [OK]

Common Mistakes:

• Using query() instead of scan()
• Confusing getItem() with scan()
• Using update() for reading data

3. Given a DynamoDB table with 1000 items, what will be the result of a Scan operation without any filter?

medium

A. It returns all 1000 items by reading the entire table

B. It returns only items with a specific partition key

C. It returns no items because no filter is applied

D. It returns only the first 10 items by default

Solution

1. Step 1: Understand Scan without filters

   Scan reads every item in the table and returns all items if no filter is applied.

2. Step 2: Confirm behavior on item count

   Since the table has 1000 items, Scan returns all 1000 items.

3. Final Answer:

   It returns all 1000 items by reading the entire table -> Option A

4. Quick Check:

   Scan without filter returns all items = A [OK]

Hint: Scan returns all items if no filter is set [OK]

Common Mistakes:

• Assuming Scan returns only some items by default
• Confusing Scan with Query filtering
• Thinking Scan returns no items without filter

4. You wrote this code to scan a DynamoDB table but it returns only a few items instead of all. What is the likely issue?

const params = { TableName: 'MyTable' };
dynamodb.scan(params, (err, data) => {
  if (err) console.log(err);
  else console.log(data.Items);
});

medium

A. The scan method is incorrect; it should be query

B. The table is empty, so no items are returned

C. Scan only returns items with a filter, so no filter means no items

D. Scan returns paginated results; you must handle LastEvaluatedKey to get all items

Solution

1. Step 1: Recognize Scan pagination behavior

   Scan returns results in pages. If the table is large, it returns a subset and a LastEvaluatedKey to continue.

2. Step 2: Identify missing pagination handling

   The code does not check for LastEvaluatedKey or continue scanning, so it only logs the first page.

3. Final Answer:

   Scan returns paginated results; you must handle LastEvaluatedKey to get all items -> Option D

4. Quick Check:

   Scan pagination needs LastEvaluatedKey handling = D [OK]

Hint: Handle LastEvaluatedKey to get all Scan results [OK]

Common Mistakes:

• Assuming Scan returns all items in one call
• Confusing Scan with Query filters
• Using query() instead of scan()

5. You want to find all items where the attribute 'status' equals 'active' in a large DynamoDB table. Why might using Scan be inefficient, and what is a better approach?

hard

A. Scan reads the entire table which is slow; better to use Query with a Global Secondary Index on 'status'

B. Scan only reads matching items quickly; no better approach needed

C. Scan automatically uses indexes; Query is slower for this case

D. Scan updates items with 'status'='active'; Query deletes them

Solution

1. Step 1: Understand Scan inefficiency

   Scan reads every item in the table, which is slow and costly for large tables.

2. Step 2: Use Query with indexes

   Creating a Global Secondary Index on 'status' allows Query to quickly find items where 'status'='active' without scanning all items.

3. Final Answer:

   Scan reads the entire table which is slow; better to use Query with a Global Secondary Index on 'status' -> Option A

4. Quick Check:

   Use Query with index, not Scan for filtering = C [OK]

Hint: Use Query with index, not Scan, for filtered searches [OK]

Common Mistakes:

• Thinking Scan is always fast
• Assuming Scan uses indexes automatically
• Confusing Scan with update or delete operations