Query by partition key in DynamoDB - Time & Space Complexity

Time Complexity: Query by partition key

O(n)

Understanding Time Complexity

When we ask DynamoDB to find items by their partition key, we want to know how the time it takes changes as the data grows.

We are trying to see how fast or slow the query runs when there are more items in the table.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const params = {
  TableName: "Users",
  KeyConditionExpression: "UserId = :uid",
  ExpressionAttributeValues: {
    ":uid": { S: "123" }
  }
};

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

This code asks DynamoDB to find all items where the partition key UserId equals "123".

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DynamoDB looks up the partition key index to find matching items.
• How many times: It reads only the items with the matching partition key, no full table scan.

How Execution Grows With Input

As the number of items with the same partition key grows, the query reads more items.

Input Size (n)	Approx. Operations
10	Reads about 10 items
100	Reads about 100 items
1000	Reads about 1000 items

Pattern observation: The time grows roughly in direct proportion to how many items share the partition key.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with the number of items that have the same partition key.

Common Mistake

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

[OK] Correct: The query is fast because it uses the index, but if many items share the partition key, DynamoDB must read each one, so time grows with that number.

Interview Connect

Understanding how DynamoDB queries scale helps you explain how to design tables for fast lookups and predict performance as data grows.

Self-Check

"What if we added a sort key and queried by both partition and sort key? How would the time complexity change?"