Basic scan operation in DynamoDB - Time & Space Complexity

Time Complexity: Basic scan operation

O(n)

Understanding Time Complexity

When we use a scan operation in DynamoDB, it looks through all the items in a table. Understanding how long this takes helps us know how it will behave as the table grows.

We want to find out how the time needed changes when the number of items increases.

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" and returns all items found.

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 number of items grows, the scan must look at each item, so the work grows steadily.

Input Size (n)	Approx. Operations
10	10 reads
100	100 reads
1000	1000 reads

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

Final Time Complexity

Time Complexity: O(n)

This means the time to scan grows in a straight line with the number of items in the table.

Common Mistake

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

[OK] Correct: Scan reads every item in the table, so if the table is big, it takes longer.

Interview Connect

Knowing how scan time grows helps you explain why it's better to use queries or indexes when possible. This shows you understand how database operations scale.

Self-Check

"What if we added a filter expression to the scan? How would the time complexity change?"

Practice

1. What does the scan operation do in DynamoDB?

easy

A. Reads all items in a table

B. Reads only one item by key

C. Deletes items from a table

D. Updates items in a table

Solution

1. Step 1: Understand the scan operation

   The scan operation reads every item in the DynamoDB table without filtering by key.

2. Step 2: Compare with other operations

   Unlike get or query, scan reads all items, not just specific keys.

3. Final Answer:

   Reads all items in a table -> Option A

4. Quick Check:

   Scan = Reads all items [OK]

Hint: Scan reads entire table, not just keys [OK]

Common Mistakes:

• Confusing scan with get or query
• Thinking scan deletes or updates data
• Assuming scan reads only filtered items

2. Which of the following is the correct syntax to perform a scan operation using AWS SDK for JavaScript v3?

easy

A. const data = await client.get({ TableName: 'MyTable' });

B. const data = await client.query({ TableName: 'MyTable' });

C. const data = await client.scan({ TableName: 'MyTable' });

D. const data = await client.delete({ TableName: 'MyTable' });

Solution

1. Step 1: Identify scan method usage

   The scan method is called on the DynamoDB client with parameters including TableName.

2. Step 2: Check other methods

   Get, query, and delete are different operations and do not perform scan.

3. Final Answer:

   const data = await client.scan({ TableName: 'MyTable' }); -> Option C

4. Quick Check:

   Scan syntax uses client.scan() [OK]

Hint: Scan uses client.scan() with TableName [OK]

Common Mistakes:

• Using get or query instead of scan
• Missing await keyword
• Wrong method names like delete

3. Given a DynamoDB table with 3 items: {id:1, name:'A'}, {id:2, name:'B'}, {id:3, name:'C'}, what will the scan operation return?

medium

A. [{id:1, name:'A'}, {id:2, name:'B'}, {id:3, name:'C'}]

B. Error: No items found

C. []

D. [{id:1, name:'A'}]

Solution

1. Step 1: Understand scan returns all items

   Scan reads every item in the table, so all 3 items will be returned.

2. Step 2: Check options for completeness

   Only [{id:1, name:'A'}, {id:2, name:'B'}, {id:3, name:'C'}] lists all 3 items; others are incomplete or errors.

3. Final Answer:

   [{id:1, name:'A'}, {id:2, name:'B'}, {id:3, name:'C'}] -> Option A

4. Quick Check:

   Scan returns all items [OK]

Hint: Scan returns full table items list [OK]

Common Mistakes:

• Expecting scan to return only one item
• Thinking scan returns empty if no filter
• Confusing scan with query results

4. You wrote this code to scan a DynamoDB table but get no results:

const params = { TableName: 'MyTable', FilterExpression: 'age > :val', ExpressionAttributeValues: { ':val': 30 } };
const data = await client.scan(params);

What is the likely problem?

medium

A. TableName is missing in params

B. FilterExpression syntax is incorrect, causing scan to fail

C. Scan does not support FilterExpression

D. FilterExpression is applied after scan reads all items, so no items match age > 30

Solution

1. Step 1: Understand FilterExpression in scan

   FilterExpression filters results after scanning all items; if no items match, result is empty.

2. Step 2: Check syntax and params

   Syntax is correct, TableName is present, and scan supports FilterExpression.

3. Final Answer:

   FilterExpression is applied after scan reads all items, so no items match age > 30 -> Option D

4. Quick Check:

   FilterExpression filters after scan [OK]

Hint: FilterExpression filters after scan reads all items [OK]

Common Mistakes:

• Thinking FilterExpression prevents scanning items
• Assuming scan fails with FilterExpression
• Missing TableName parameter

5. You want to scan a large DynamoDB table but only retrieve items where status is 'active'. Which approach is best to reduce data returned and improve performance?

hard

A. Use scan with FilterExpression 'status = :s' and ExpressionAttributeValues { ':s': 'active' }

B. Use query operation with status as partition key

C. Use scan without filters and filter results in application code

D. Use scan with ProjectionExpression to get only 'status' attribute

Solution

1. Step 1: Understand scan vs query

   Scan reads entire table; query reads items by key, more efficient for filtering.

2. Step 2: Check if status can be partition key

   If status is partition key, query can efficiently get only 'active' items without scanning all.

3. Step 3: Evaluate other options

   FilterExpression filters after scan, so less efficient; filtering in app wastes bandwidth; ProjectionExpression only limits attributes, not items.

4. Final Answer:

   Use query operation with status as partition key -> Option B

5. Quick Check:

   Query with key filters efficiently [OK]

Hint: Query by key is faster than scan with filters [OK]

Common Mistakes:

• Relying on scan with filters for large tables
• Filtering data in application instead of query
• Confusing ProjectionExpression with filtering items