When Scan is acceptable in DynamoDB - Time & Space Complexity

Time Complexity: When Scan is acceptable

O(n)

Understanding Time Complexity

We want to understand how the time to run a Scan operation in DynamoDB changes as the amount of data grows.

How does scanning many items affect the work DynamoDB does?

Scenario Under Consideration

Analyze the time complexity of the following Scan operation.

    const params = {
      TableName: "Products",
      FilterExpression: "Price > :minPrice",
      ExpressionAttributeValues: { ":minPrice": 100 }
    };
    
    const data = await dynamodb.scan(params).promise();
    console.log(data.Items);
    

This code scans the entire "Products" table and filters items with Price greater than 100.

Identify Repeating Operations

Look for repeated work inside the Scan.

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

How Execution Grows With Input

As the number of items grows, the Scan reads more and more data.

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

Pattern observation: The work grows directly with the number of items. More items mean more reading.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the Scan grows linearly 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 large, it takes longer.

Interview Connect

Understanding when Scan is acceptable shows you know how to balance simplicity and performance in real projects.

Self-Check

"What if we replaced Scan with Query using a partition key? How would the time complexity change?"

Practice

1. Which situation is best suited for using a Scan operation in DynamoDB?

easy

A. When you want to update an item quickly.

B. When you want to retrieve a single item by its primary key.

C. When you need to read all items from a small table.

D. When you want to delete an item by its key.

Solution

1. Step 1: Understand Scan operation purpose

   Scan reads every item in the table, which is simple but slow for large tables.

2. Step 2: Match Scan use case

   Scan is acceptable when the table is small and you need all data, not a specific item by key.

3. Final Answer:

   When you need to read all items from a small table. -> Option C

4. Quick Check:

   Scan = small table full read [OK]

Hint: Use Scan only for small tables or full data needs [OK]

Common Mistakes:

• Using Scan to get a single item by key
• Using Scan for updates or deletes
• Ignoring performance impact on large tables

2. Which of the following is the correct syntax to perform a Scan operation with a filter expression in DynamoDB?

easy

A. Scan(TableName='Users', ConditionExpression='Age > :age')

B. Scan(TableName='Users', KeyConditionExpression='Age > :age', ExpressionAttributeValues={':age': 30})

C. Scan(TableName='Users', Filter='Age > 30')

D. Scan(TableName='Users', FilterExpression='Age > :age', ExpressionAttributeValues={':age': 30})

Solution

1. Step 1: Identify correct Scan parameters

   Scan uses FilterExpression to filter results after scanning all items.

2. Step 2: Check syntax correctness

   Scan(TableName='Users', FilterExpression='Age > :age', ExpressionAttributeValues={':age': 30}) uses FilterExpression and ExpressionAttributeValues correctly for filtering.

3. Final Answer:

   Scan(TableName='Users', FilterExpression='Age > :age', ExpressionAttributeValues={':age': 30}) -> Option D

4. Quick Check:

   FilterExpression syntax = Scan(TableName='Users', FilterExpression='Age > :age', ExpressionAttributeValues={':age': 30}) [OK]

Hint: FilterExpression filters after Scan, not KeyConditionExpression [OK]

Common Mistakes:

• Using KeyConditionExpression with Scan
• Using wrong parameter names like Filter or ConditionExpression
• Not providing ExpressionAttributeValues for placeholders

3. Given a DynamoDB table 'Products' with 3 items: {"ID":1, "Category":"Book"}, {"ID":2, "Category":"Toy"}, {"ID":3, "Category":"Book"}, what will be the result of this Scan operation?

Scan(TableName='Products', FilterExpression='Category = :cat', ExpressionAttributeValues={':cat': 'Book'})

medium

A. [{"ID":1, "Category":"Book"}, {"ID":3, "Category":"Book"}]

B. [{"ID":2, "Category":"Toy"}]

C. [{"ID":1, "Category":"Book"}, {"ID":2, "Category":"Toy"}, {"ID":3, "Category":"Book"}]

D. []

Solution

1. Step 1: Understand Scan with FilterExpression

   Scan reads all items, then returns only those matching the filter Category = 'Book'.

2. Step 2: Apply filter to items

   Items with Category 'Book' are ID 1 and ID 3, so only these are returned.

3. Final Answer:

   [{"ID":1, "Category":"Book"}, {"ID":3, "Category":"Book"}] -> Option A

4. Quick Check:

   Filter returns matching items only [OK]

Hint: Scan returns all, filter narrows results after [OK]

Common Mistakes:

• Expecting Scan to return only filtered items without FilterExpression
• Confusing Scan with Query operation
• Ignoring that Scan reads all items first

4. You wrote this Scan code but it returns all items without filtering:

Scan(TableName='Orders', FilterExpression='Status = :s')

What is the most likely error?

medium

A. Missing ExpressionAttributeValues for ':s'.

B. Using FilterExpression instead of KeyConditionExpression.

C. Scan does not support FilterExpression.

D. Table name is incorrect.

Solution

1. Step 1: Check FilterExpression usage

   FilterExpression uses placeholders like ':s' which must be defined in ExpressionAttributeValues.

2. Step 2: Identify missing ExpressionAttributeValues

   Code lacks ExpressionAttributeValues, so filter cannot apply and returns all items.

3. Final Answer:

   Missing ExpressionAttributeValues for ':s'. -> Option A

4. Quick Check:

   Filter needs ExpressionAttributeValues [OK]

Hint: Always provide ExpressionAttributeValues for FilterExpression [OK]

Common Mistakes:

• Confusing FilterExpression with KeyConditionExpression
• Forgetting ExpressionAttributeValues
• Assuming Scan ignores missing values silently

5. You have a large DynamoDB table with millions of items but no suitable key for your query. You need to find all items where Status = 'Active'. Which approach is best?

hard

A. Use Scan with FilterExpression 'Status = :status' and paginate results.

B. Create a Global Secondary Index on 'Status' and use Query.

C. Use Query with KeyConditionExpression on 'Status'.

D. Use Scan without any filter to get all items.

Solution

1. Step 1: Understand limitations of Scan on large tables

   Scan reads all items and is slow and costly on large tables, even with filters.

2. Step 2: Use Global Secondary Index (GSI) for efficient queries

   Creating a GSI on 'Status' allows Query operation, which is fast and efficient for filtering by 'Status'.

3. Final Answer:

   Create a Global Secondary Index on 'Status' and use Query. -> Option B

4. Quick Check:

   GSI + Query = efficient large table filter [OK]

Hint: Use GSI for filtering large tables, not Scan [OK]

Common Mistakes:

• Using Scan on large tables causing slow performance
• Trying Query without suitable key or index
• Ignoring cost and speed implications