Composite sort key pattern in DynamoDB - Time & Space Complexity

Time Complexity: Composite sort key pattern

O(n)

Understanding Time Complexity

When using a composite sort key in DynamoDB, we want to understand how the time to find data changes as we add more items.

We ask: How does the number of operations grow when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query using a composite sort key.

    const params = {
      TableName: "Orders",
      KeyConditionExpression: "CustomerId = :cid AND begins_with(OrderDate, :datePrefix)",
      ExpressionAttributeValues: {
        ":cid": "12345",
        ":datePrefix": "2024-06"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries orders for one customer, filtering by order dates starting with a given prefix.

Identify Repeating Operations

Look at what repeats when this query runs.

• Primary operation: Scanning items with the same CustomerId and matching the date prefix in the sort key.
• How many times: Once per matching item in the queried range.

How Execution Grows With Input

As more orders exist for the customer in the date range, the query checks more items.

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

Pattern observation: The work grows roughly in direct proportion to how many items match the prefix.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with the number of matching items in the sort key range.

Common Mistake

[X] Wrong: "Using a composite sort key means the query always runs in constant time."

[OK] Correct: The query time depends on how many items match the sort key condition, so it grows with that number, not fixed.

Interview Connect

Understanding how composite sort keys affect query time helps you design efficient DynamoDB tables and answer questions about scaling data access.

Self-Check

What if we changed the sort key condition from begins_with to an exact match? How would the time complexity change?