Composite primary key in DynamoDB - Time & Space Complexity

Time Complexity: Composite primary key

O(n)

Understanding Time Complexity

When using a composite primary key in DynamoDB, it is important to understand how the time to find data changes as the amount of data grows.

We want to know how the database handles queries using the partition key (first part) of the composite primary key and how that affects speed.

Scenario Under Consideration

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

    const params = {
      TableName: "Orders",
      KeyConditionExpression: "CustomerId = :cid",
      ExpressionAttributeValues: {
        ":cid": "12345"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries the "Orders" table for items matching a customer ID, using a composite primary key.

Identify Repeating Operations

Look for repeated steps that affect how long the query takes.

• Primary operation: Searching the partition key (CustomerId) to find matching items.
• How many times: The database looks only inside the partition matching CustomerId.

How Execution Grows With Input

As the number of orders for one customer grows, the query looks through more items with that CustomerId.

Input Size (n)	Approx. Operations
10 orders for one customer	About 10 checks inside that partition
100 orders for one customer	About 100 checks inside that partition
1000 orders for one customer	About 1000 checks inside that partition

Pattern observation: The time grows roughly in direct proportion to the number of items with the same partition key.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of items sharing the same partition key.

Common Mistake

[X] Wrong: "Using a composite key means the query always runs in constant time no matter how many items exist."

[OK] Correct: The partition key lookup is fast, but if many items share the same partition key, the database must scan those items by the sort key, so time grows with that number.

Interview Connect

Understanding how composite keys affect query speed shows you know how DynamoDB organizes data and why choosing keys carefully matters for performance.

Self-Check

"What if we also specify the sort key with an equality condition like OrderDate = :od? How would the time complexity change?"