Query with sort key conditions in DynamoDB - Time & Space Complexity

Time Complexity: Query with sort key conditions

O(n)

Understanding Time Complexity

When we query a DynamoDB table using a sort key condition, we want to know how the time it takes changes as the data grows.

We ask: How does the number of items affect the work DynamoDB does to find matching results?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const params = {
  TableName: "Orders",
  KeyConditionExpression: "CustomerId = :cid AND OrderDate > :date",
  ExpressionAttributeValues: {
    ":cid": { S: "12345" },
    ":date": { S: "2023-01-01" }
  }
};

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

This code queries the "Orders" table for all orders by a customer with ID "12345" where the order date is after January 1, 2023.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning through the items with the matching CustomerId and checking the OrderDate condition.
• How many times: Once for each item with that CustomerId until all matching dates are found or the query limit is reached.

How Execution Grows With Input

As the number of orders for the customer grows, DynamoDB checks more items to find those after the given date.

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

Pattern observation: The work grows roughly in direct proportion to the number of items with the same CustomerId.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the query grows linearly with the number of items that share the same partition key.

Common Mistake

[X] Wrong: "The query will always be fast no matter how many items match the partition key because DynamoDB is fast."

[OK] Correct: While DynamoDB is optimized, the query still needs to check each item with the matching partition key to apply the sort key condition, so more items mean more work.

Interview Connect

Understanding how queries scale with data size helps you design efficient DynamoDB tables and write queries that perform well in real projects.

Self-Check

"What if we added a filter expression after the query? How would that affect the time complexity?"

Practice

1. In DynamoDB, when you use a Query operation with a sort key condition, which of the following is always required?

easy

A. Specify only the sort key condition without the partition key

B. Use a scan operation instead of query

C. Specify the partition key with '=' and a condition on the sort key

D. Specify only the partition key without any sort key condition

Solution

1. Step 1: Understand Query requirements

   A DynamoDB Query must always specify the partition key with '=' to identify the partition.

2. Step 2: Add sort key condition

   You can add conditions on the sort key to filter items within that partition.

3. Final Answer:

   Specify the partition key with '=' and a condition on the sort key -> Option C

4. Quick Check:

   Partition key '=' + sort key condition = required [OK]

Hint: Partition key '=' is mandatory in Query with sort key condition [OK]

Common Mistakes:

• Trying to query without specifying partition key
• Using scan instead of query for sort key filtering
• Specifying only sort key condition without partition key

2. Which of the following is the correct syntax for a DynamoDB Query with a sort key condition to find items where the sort key Timestamp is greater than 1000?

easy

A. KeyConditionExpression: 'PartitionKey > :pk AND Timestamp > :ts', ExpressionAttributeValues: { ':pk': 'User1', ':ts': 1000 }

B. KeyConditionExpression: 'PartitionKey = :pk OR Timestamp > :ts', ExpressionAttributeValues: { ':pk': 'User1', ':ts': 1000 }

C. KeyConditionExpression: 'PartitionKey = :pk AND Timestamp == :ts', ExpressionAttributeValues: { ':pk': 'User1', ':ts': 1000 }

D. KeyConditionExpression: 'PartitionKey = :pk AND Timestamp > :ts', ExpressionAttributeValues: { ':pk': 'User1', ':ts': 1000 }

Solution

1. Step 1: Use '=' for partition key

   The partition key must be compared with '=' in the KeyConditionExpression.

2. Step 2: Use '>' for sort key condition

   The sort key condition can use operators like '>' to filter items.

3. Final Answer:

   KeyConditionExpression: 'PartitionKey = :pk AND Timestamp > :ts' -> Option D

4. Quick Check:

   PartitionKey '=' and sort key '>' correct syntax [OK]

Hint: Partition key '=' and sort key condition combined with AND [OK]

Common Mistakes:

• Using OR instead of AND in KeyConditionExpression
• Using '>' for partition key instead of '='
• Using '==' instead of '=' for partition key

3. Given a DynamoDB table with partition key UserID and sort key OrderDate, what will the following query return?

KeyConditionExpression: 'UserID = :uid AND OrderDate BETWEEN :start AND :end'
ExpressionAttributeValues: { ':uid': 'user123', ':start': '2023-01-01', ':end': '2023-01-31' }

medium

A. All orders for 'user123' placed between January 1 and January 31, 2023 inclusive

B. All orders for all users placed between January 1 and January 31, 2023

C. All orders for 'user123' placed before January 1, 2023

D. Syntax error due to BETWEEN usage in KeyConditionExpression

Solution

1. Step 1: Partition key '=' filters user

   The query filters items where UserID equals 'user123'.

2. Step 2: Sort key BETWEEN filters date range

   The BETWEEN operator selects OrderDate values from '2023-01-01' to '2023-01-31' inclusive.

3. Final Answer:

   All orders for 'user123' placed between January 1 and January 31, 2023 inclusive -> Option A

4. Quick Check:

   Partition key '=' + sort key BETWEEN returns filtered range [OK]

Hint: BETWEEN filters sort key range within one partition [OK]

Common Mistakes:

• Assuming query returns all users' orders
• Thinking BETWEEN excludes boundary dates
• Believing BETWEEN is invalid in KeyConditionExpression

4. You wrote this DynamoDB query but it returns no results:

KeyConditionExpression: 'UserID = :uid AND OrderDate > :date'
ExpressionAttributeValues: { ':uid': 'user123', ':date': '2023-12-31' }

What is the most likely reason?

medium

A. No items exist with OrderDate after 2023-12-31 for user123

B. Using '>' operator is not allowed in KeyConditionExpression

C. Partition key UserID should use '>' instead of '='

D. ExpressionAttributeValues keys must not start with ':'

Solution

1. Step 1: Check operator validity

   The '>' operator is valid for sort key conditions in DynamoDB queries.

2. Step 2: Consider data existence

   If no items have OrderDate after '2023-12-31' for 'user123', query returns empty.

3. Final Answer:

   No items exist with OrderDate after 2023-12-31 for user123 -> Option A

4. Quick Check:

   Valid syntax but no matching data = empty result [OK]

Hint: Empty results often mean no matching data, not syntax error [OK]

Common Mistakes:

• Thinking '>' is invalid in KeyConditionExpression
• Using '>' for partition key instead of '='
• Misunderstanding ExpressionAttributeValues syntax

5. You want to query a DynamoDB table with partition key CustomerID and sort key InvoiceDate. You need to find all invoices for CustomerID = 'C123' where InvoiceDate is either before '2023-01-01' or after '2023-12-31'. Which approach correctly achieves this?

hard

A. Use KeyConditionExpression with BETWEEN operator for the two date ranges

B. Run two separate queries: one with InvoiceDate < '2023-01-01' and another with InvoiceDate > '2023-12-31', then combine results

C. Use a scan operation with filter expression for the date conditions

D. Use a single query with KeyConditionExpression: CustomerID = :cid AND InvoiceDate < '2023-01-01' OR InvoiceDate > '2023-12-31'

Solution

1. Step 1: Understand KeyConditionExpression limits

   DynamoDB KeyConditionExpression supports only AND between partition key and sort key conditions, no OR.

2. Step 2: Query with OR on sort key requires multiple queries

   To get items before '2023-01-01' OR after '2023-12-31', run two queries and merge results.

3. Final Answer:

   Run two separate queries: one with InvoiceDate < '2023-01-01' and another with InvoiceDate > '2023-12-31', then combine results -> Option B

4. Quick Check:

   OR on sort key = multiple queries combined [OK]

Hint: DynamoDB Query KeyConditionExpression uses AND only; split OR into queries [OK]

Common Mistakes:

• Trying to use OR in KeyConditionExpression
• Using BETWEEN for non-continuous ranges
• Using scan instead of efficient queries