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

Practice

1. What does querying by partition key in DynamoDB do?

easy

A. Updates all items with the same partition key value

B. Deletes all items with the same partition key value

C. Fetches all items with the same partition key value

D. Creates a new item with the partition key value

Solution

1. Step 1: Understand partition key role

   The partition key uniquely identifies the partition where items are stored.

2. Step 2: Query by partition key fetches items

   Querying by partition key returns all items that share that key value.

3. Final Answer:

   Fetches all items with the same partition key value -> Option C

4. Quick Check:

   Query by partition key = fetch items [OK]

Hint: Partition key query fetches matching items only [OK]

Common Mistakes:

• Thinking it deletes or updates items
• Confusing partition key with sort key
• Assuming it creates new items

2. Which of the following is the correct syntax to query items by partition key 'UserID' with value '123' in DynamoDB?

easy

A. Table.query(KeyConditionExpression: 'UserID = 123')

B. Table.query(KeyConditionExpression: 'UserID = :val', ExpressionAttributeValues: {':val': '123'})

C. Table.query(FilterExpression: 'UserID = 123')

D. Table.query(KeyConditionExpression: 'UserID == 123')

Solution

1. Step 1: Identify correct query syntax

   DynamoDB requires KeyConditionExpression with placeholders and ExpressionAttributeValues.

2. Step 2: Check each option

   Table.query(KeyConditionExpression: 'UserID = :val', ExpressionAttributeValues: {':val': '123'}) uses correct syntax with placeholder ':val' and value mapping. Others misuse operators or omit placeholders.

3. Final Answer:

   Table.query(KeyConditionExpression: 'UserID = :val', ExpressionAttributeValues: {':val': '123'}) -> Option B

4. Quick Check:

   Use placeholders and ExpressionAttributeValues [OK]

Hint: Use placeholders (:val) and ExpressionAttributeValues [OK]

Common Mistakes:

• Using '==' instead of '=' in KeyConditionExpression
• Not using ExpressionAttributeValues for values
• Using FilterExpression instead of KeyConditionExpression

3. Given a DynamoDB table with items: {UserID: '123', Name: 'Alice'}, {UserID: '123', Name: 'Bob'}, {UserID: '456', Name: 'Carol'}, what will the query by partition key 'UserID' = '123' return?

medium

A. [{UserID: '123', Name: 'Alice'}, {UserID: '123', Name: 'Bob'}]

B. [{UserID: '456', Name: 'Carol'}]

C. [{UserID: '123', Name: 'Alice'}]

D. [] (empty list)

Solution

1. Step 1: Identify items with partition key '123'

   Items with UserID '123' are Alice and Bob.

2. Step 2: Query returns all matching items

   Query returns both Alice and Bob items as they share the partition key.

3. Final Answer:

   [{UserID: '123', Name: 'Alice'}, {UserID: '123', Name: 'Bob'}] -> Option A

4. Quick Check:

   Query by '123' returns Alice and Bob [OK]

Hint: Query returns all items with matching partition key [OK]

Common Mistakes:

• Expecting only one item returned
• Confusing partition key with sort key filtering
• Assuming query returns items with different partition keys

4. You wrote this query to get items with partition key 'OrderID' = '789': Table.query(KeyConditionExpression: 'OrderID = 789'). It returns an error. What is the problem?

medium

A. Partition key name is case-sensitive and should be 'orderid'

B. Using wrong operator '==' instead of '='

C. Query method does not support KeyConditionExpression

D. Missing ExpressionAttributeValues for the value '789'

Solution

1. Step 1: Check query syntax requirements

   DynamoDB requires placeholders and ExpressionAttributeValues for values in KeyConditionExpression.

2. Step 2: Identify missing part

   The query uses 'OrderID = 789' directly without placeholder or ExpressionAttributeValues, causing error.

3. Final Answer:

   Missing ExpressionAttributeValues for the value '789' -> Option D

4. Quick Check:

   Use placeholders and ExpressionAttributeValues [OK]

Hint: Always use placeholders and ExpressionAttributeValues [OK]

Common Mistakes:

• Using raw values instead of placeholders
• Assuming case-insensitivity for partition key
• Using '==' operator instead of '='

5. You want to query a DynamoDB table for all items with partition key 'Category' = 'Books' and sort key 'Price' less than 20. Which approach correctly uses query by partition key with a condition on sort key?

hard

A. Use KeyConditionExpression: 'Category = :cat AND Price < :price' with ExpressionAttributeValues {':cat': 'Books', ':price': 20}

B. Use FilterExpression: 'Category = :cat AND Price < :price' with ExpressionAttributeValues {':cat': 'Books', ':price': 20}

C. Use KeyConditionExpression: 'Category = :cat' and FilterExpression: 'Price < :price' with ExpressionAttributeValues {':cat': 'Books', ':price': 20}

D. Use FilterExpression: 'Category = :cat' and KeyConditionExpression: 'Price < :price' with ExpressionAttributeValues {':cat': 'Books', ':price': 20}

Solution

1. Step 1: Understand query conditions

   KeyConditionExpression must include partition key equality and supports sort key conditions like <. FilterExpression filters results after the query.

2. Step 2: Analyze options

   Use KeyConditionExpression: 'Category = :cat AND Price < :price' with ExpressionAttributeValues {':cat': 'Books', ':price': 20} correctly uses KeyConditionExpression: 'Category = :cat AND Price < :price', which efficiently queries the partition with a sort key range condition. Use KeyConditionExpression: 'Category = :cat' and FilterExpression: 'Price < :price' with ExpressionAttributeValues {':cat': 'Books', ':price': 20} uses FilterExpression for Price (valid but less efficient). B lacks KeyConditionExpression. D omits partition key from KeyConditionExpression.

3. Final Answer:

   Use KeyConditionExpression: 'Category = :cat AND Price < :price' with ExpressionAttributeValues {':cat': 'Books', ':price': 20} -> Option A

4. Quick Check:

   KeyConditionExpression: partition = AND sort < [OK]

Hint: KeyConditionExpression: partition = AND sort condition [OK]

Common Mistakes:

• Using FilterExpression for partition key
• Using FilterExpression instead of KeyConditionExpression for sort key range
• Mixing KeyConditionExpression and FilterExpression incorrectly