Scan with filter expressions in DynamoDB - Time & Space Complexity

Time Complexity: Scan with filter expressions

O(n)

Understanding Time Complexity

When using DynamoDB's scan with filter expressions, we want to know how the time to get results changes as the table grows.

We ask: How does the scan operation's cost grow when the table has more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const params = {
  TableName: "Products",
  FilterExpression: "Price > :minPrice",
  ExpressionAttributeValues: {
    ":minPrice": { N: "100" }
  }
};

const result = await dynamodb.scan(params).promise();

This code scans the entire "Products" table and returns only items where the Price is greater than 100.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each item in the table to check the filter condition.
• How many times: Once for every item in the table, regardless of the filter.

How Execution Grows With Input

As the number of items in the table grows, the scan checks each item once.

Input Size (n)	Approx. Operations
10	10 item checks
100	100 item checks
1000	1000 item checks

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 linearly as the table gets bigger.

Common Mistake

[X] Wrong: "The filter expression makes the scan only look at matching items, so it's fast even for big tables."

[OK] Correct: The scan still reads every item; the filter only removes items after reading them, so the work grows with table size.

Interview Connect

Understanding how scan with filters works helps you explain performance trade-offs clearly, a useful skill when designing or troubleshooting databases.

Self-Check

"What if we replaced scan with a query using a key condition? How would the time complexity change?"

Practice

1. What does a Scan operation with a filter expression do in DynamoDB?

easy

A. It deletes items that do not match the filter condition.

B. It reads only the items that match the filter condition directly.

C. It updates items that match the filter condition.

D. It reads all items but returns only those matching the filter condition.

Solution

1. Step 1: Understand Scan operation

   A Scan reads every item in the table regardless of any condition.

2. Step 2: Apply filter expression effect

   The filter expression is applied after reading all items, so only matching items are returned.

3. Final Answer:

   It reads all items but returns only those matching the filter condition. -> Option D

4. Quick Check:

   Scan + filter = read all, return filtered [OK]

Hint: Scan reads all, filter returns matching items only [OK]

Common Mistakes:

• Thinking Scan reads only filtered items
• Confusing Scan with Query
• Assuming filter modifies data

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

easy

A. scan(TableName='MyTable', Filter='Name = "John"')

B. scan(TableName='MyTable', ConditionExpression='Name = "John"')

C. scan(TableName='MyTable', FilterExpression='attribute_exists(Name)')

D. scan(TableName='MyTable', FilterCondition='Name = "John"')

Solution

1. Step 1: Identify correct parameter name

   The correct parameter for filtering in Scan is FilterExpression.

2. Step 2: Check syntax correctness

   scan(TableName='MyTable', FilterExpression='attribute_exists(Name)') uses FilterExpression with a valid condition attribute_exists(Name).

3. Final Answer:

   scan(TableName='MyTable', FilterExpression='attribute_exists(Name)') -> Option C

4. Quick Check:

   FilterExpression is correct parameter [OK]

Hint: Use FilterExpression parameter for scan filters [OK]

Common Mistakes:

• Using ConditionExpression instead of FilterExpression
• Using Filter or FilterCondition which are invalid
• Incorrect syntax for filter condition

3. Given a DynamoDB table with items: [{"Name": "Alice", "Age": 30}, {"Name": "Bob", "Age": 25}, {"Name": "Carol", "Age": 35}], what will be the result of a Scan with filter expression Age > 30?

medium

A. [{"Name": "Alice", "Age": 30}]

B. [{"Name": "Carol", "Age": 35}]

C. [{"Name": "Bob", "Age": 25}]

D. [{"Name": "Alice", "Age": 30}, {"Name": "Carol", "Age": 35}]

Solution

1. Step 1: Understand filter condition

   The filter expression Age > 30 means only items with Age greater than 30 are returned.

2. Step 2: Check each item against condition

   Alice has Age 30 (not greater), Bob 25 (not greater), Carol 35 (greater). Only Carol matches.

3. Final Answer:

   [{"Name": "Carol", "Age": 35}] -> Option B

4. Quick Check:

   Age > 30 returns Carol only [OK]

Hint: Filter returns only items strictly matching condition [OK]

Common Mistakes:

• Including items with Age equal to 30
• Confusing greater than with greater or equal
• Returning all items ignoring filter

4. You wrote this Scan code with filter expression: FilterExpression='Age > :val' and ExpressionAttributeValues={':val': 30}, but it returns no items. What is the likely error?

medium

A. ExpressionAttributeValues must be a dictionary with DynamoDB types, e.g., {':val': {'N': '30'}}.

B. FilterExpression should use '>' not '>'.

C. ExpressionAttributeValues key should be ':val' as a string, not a number.

D. Scan does not support FilterExpression.

Solution

1. Step 1: Check ExpressionAttributeValues format

   DynamoDB expects attribute values in a typed format, e.g., numbers as {'N': '30'}.

2. Step 2: Identify why no items returned

   Providing raw number 30 instead of typed value causes filter to fail matching any item.

3. Final Answer:

   ExpressionAttributeValues must be a dictionary with DynamoDB types, e.g., {':val': {'N': '30'}}. -> Option A

4. Quick Check:

   Use typed values in ExpressionAttributeValues [OK]

Hint: Use DynamoDB typed values in ExpressionAttributeValues [OK]

Common Mistakes:

• Passing raw Python values instead of typed dict
• Using HTML entities like > in code instead of >
• Thinking Scan does not support filters

5. You want to scan a DynamoDB table to find items where Status is 'Active' and Score is greater than 80. Which filter expression and attribute values are correct?

hard

A. FilterExpression='Status = :s AND Score > :sc', ExpressionAttributeValues={':s': {'S': 'Active'}, ':sc': {'N': '80'}}

B. FilterExpression='Status == :s AND Score > :sc', ExpressionAttributeValues={':s': 'Active', ':sc': 80}

C. FilterExpression='Status = :s OR Score > :sc', ExpressionAttributeValues={':s': {'S': 'Active'}, ':sc': {'N': '80'}}

D. FilterExpression='Status = :s AND Score > :sc', ExpressionAttributeValues={':s': 'Active', ':sc': '80'}

Solution

1. Step 1: Check filter expression logic

   The condition requires both Status equals 'Active' AND Score greater than 80, so use 'AND' and '=' operators correctly.

2. Step 2: Verify ExpressionAttributeValues format

   Values must be typed: strings as {'S': 'Active'} and numbers as {'N': '80'}.

3. Final Answer:

   FilterExpression='Status = :s AND Score > :sc', ExpressionAttributeValues={':s': {'S': 'Active'}, ':sc': {'N': '80'}} -> Option A

4. Quick Check:

   Correct logic and typed values [OK]

Hint: Use AND and typed values for multiple conditions [OK]

Common Mistakes:

• Using '==' instead of '=' in filter expression
• Using OR instead of AND
• Passing untyped values in ExpressionAttributeValues