Filter expressions in DynamoDB - Time & Space Complexity

Time Complexity: Filter expressions

O(n)

Understanding Time Complexity

When using filter expressions in DynamoDB, it's important to know how the time to get results changes as the data grows.

We want to understand how filtering affects the work DynamoDB does behind the scenes.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB scan with a filter expression.

    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 filters items where the price is greater than 100.

Identify Repeating Operations

Look for repeated work done during the scan and filtering.

• Primary operation: Reading each item in the table one by one.
• How many times: Once for every item in the table, because scan reads all items.

How Execution Grows With Input

As the number of items grows, the scan reads more items, checking each against the filter.

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

Pattern observation: The work grows directly with the number of items in the table.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the scan with filter grows linearly as the table size grows.

Common Mistake

[X] Wrong: "Filter expressions make the scan only read matching items."

[OK] Correct: The scan reads every item first, then applies the filter, so all items are processed regardless.

Interview Connect

Understanding how filter expressions affect scan time helps you explain real-world trade-offs when working with large datasets.

Self-Check

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

Practice

1. What is the main purpose of a FilterExpression in a DynamoDB scan or query?

easy

A. To return only items that meet specific conditions after reading all data

B. To reduce the size of the table permanently

C. To speed up the write operations

D. To create new indexes automatically

Solution

1. Step 1: Understand what FilterExpression does

   A FilterExpression is used to specify conditions that items must meet to be returned after the scan or query reads the data.

2. Step 2: Differentiate from other operations

   It does not change the table or speed up writes; it only filters results after reading.

3. Final Answer:

   To return only items that meet specific conditions after reading all data -> Option A

4. Quick Check:

   FilterExpression filters results after reading [OK]

Hint: FilterExpression filters results after reading data [OK]

Common Mistakes:

• Thinking FilterExpression reduces read capacity usage
• Confusing FilterExpression with key condition
• Assuming it changes the table data

2. Which of the following is the correct syntax for a FilterExpression to find items where attribute status equals 'active' in DynamoDB?

easy

A. FilterExpression: "status = 'active'"

B. FilterExpression: "status == 'active'"

C. FilterExpression: "status equals 'active'"

D. FilterExpression: "status === 'active'"

Solution

1. Step 1: Recall DynamoDB FilterExpression syntax

   DynamoDB uses single equals sign (=) for equality in FilterExpressions.

2. Step 2: Check each option

   FilterExpression: "status = 'active'" uses correct syntax. The other options use invalid operators (==, equals, ===) or keywords.

3. Final Answer:

   FilterExpression: "status = 'active'" -> Option A

4. Quick Check:

   Use single equals (=) for equality in FilterExpression [OK]

Hint: Use single '=' for equality in FilterExpression [OK]

Common Mistakes:

• Using double or triple equals (==, ===)
• Writing 'equals' as a word
• Using incorrect operators

3. Given a DynamoDB table with items having attribute age, what will be the result of this scan with FilterExpression age < 30 if the table has ages 25, 30, 35, and 40?

medium

A. Items with ages 25 and 30

B. Items with ages 25 only

C. Items with ages 30, 35, and 40

D. Items with ages 35 and 40

Solution

1. Step 1: Understand the FilterExpression condition

   The condition is age < 30, meaning only items with age less than 30 pass the filter.

2. Step 2: Check which ages satisfy the condition

   From the list (25, 30, 35, 40), only 25 is less than 30.

3. Final Answer:

   Items with ages 25 only -> Option B

4. Quick Check:

   age < 30 means less than 30 [OK]

Hint: Remember < means strictly less than [OK]

Common Mistakes:

• Including age 30 when condition is less than 30
• Confusing < with <= operator
• Assuming filter changes data in table

4. You wrote this FilterExpression: contains(name, 'John') but it returns no results even though some items have 'John' in their name. What is the likely mistake?

medium

A. Using contains() instead of equals()

B. Not using ExpressionAttributeNames for reserved words

C. FilterExpression is case-sensitive and 'John' does not match 'john'

D. FilterExpression must be in uppercase

Solution

1. Step 1: Understand contains() behavior

   contains() checks if the attribute contains the exact substring, including case.

2. Step 2: Consider case sensitivity

   If the data has 'john' lowercase but the filter uses 'John' with uppercase J, no match occurs.

3. Step 3: Check other choices

   Using equals() instead of contains() is not the issue since contains() is appropriate for substrings; reserved words would cause a different error; FilterExpressions are not required to be uppercase.

4. Final Answer:

   FilterExpression is case-sensitive and 'John' does not match 'john' -> Option C

5. Quick Check:

   contains() is case-sensitive [OK]

Hint: Remember contains() is case-sensitive [OK]

Common Mistakes:

• Ignoring case sensitivity in contains()
• Not using ExpressionAttributeNames when needed
• Assuming contains() works like equals()

5. You want to scan a DynamoDB table to find items where score is greater than 50 and status is 'active'. Which FilterExpression correctly applies both conditions?

hard

A. FilterExpression: "score > 50, status = 'active'"

B. FilterExpression: "score > 50 OR status = 'active'"

C. FilterExpression: "score > 50 && status == 'active'"

D. FilterExpression: "score > 50 AND status = 'active'"

Solution

1. Step 1: Understand logical operators in FilterExpression

   DynamoDB uses uppercase AND and OR for combining conditions.

2. Step 2: Check each option's syntax

   FilterExpression: "score > 50 AND status = 'active'" uses correct syntax with AND and single equals. FilterExpression: "score > 50 OR status = 'active'" uses OR which is incorrect for both conditions. FilterExpression: "score > 50, status = 'active'" uses comma which is invalid. FilterExpression: "score > 50 && status == 'active'" uses && and double equals which are invalid.

3. Final Answer:

   FilterExpression: "score > 50 AND status = 'active'" -> Option D

4. Quick Check:

   Use AND in uppercase and single '=' for equality [OK]

Hint: Use uppercase AND and single '=' in FilterExpression [OK]

Common Mistakes:

• Using OR instead of AND for both conditions
• Using commas or && instead of AND
• Using double equals (==) instead of single equals (=)