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?"