Partition key and sort key in AWS - Time & Space Complexity

Time Complexity: Partition key and sort key

O(n)

Understanding Time Complexity

When using a partition key and sort key in AWS databases, it is important to understand how the number of operations grows as you add more data.

We want to know how the time to find or store items changes when the data size increases.

Scenario Under Consideration

Analyze the time complexity of querying items using a partition key and sort key.

// Query items in DynamoDB table
const params = {
  TableName: "MyTable",
  KeyConditionExpression: "PartitionKey = :pk and SortKey > :sk",
  ExpressionAttributeValues: {
    ":pk": { S: "User123" },
    ":sk": { N: "100" }
  }
};
const result = await dynamodb.query(params).promise();
    

This operation fetches items for one partition key and filters by sort key range.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: DynamoDB Query API call
• How many times: Once per query, but returns multiple items
• Data transfer: Number of items returned depends on sort key range size

How Execution Grows With Input

As the number of items with the same partition key grows, the query returns more items matching the sort key condition.

Input Size (n)	Approx. Items Returned
10	10 items
100	100 items
1000	1000 items

Pattern observation: The time and data returned grow linearly with the number of items matching the sort key range.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows directly with how many items match the sort key condition within one partition.

Common Mistake

[X] Wrong: "Querying by partition and sort key always takes the same time no matter how many items match."

[OK] Correct: The query time depends on how many items match the sort key filter; more matching items mean more data to read and return.

Interview Connect

Understanding how partition and sort keys affect query time helps you design efficient data access patterns and answer questions about scaling in cloud databases.

Self-Check

"What if we removed the sort key condition and only queried by partition key? How would the time complexity change?"