Key condition expressions in DynamoDB - Time & Space Complexity

Time Complexity: Key condition expressions

O(n)

Understanding Time Complexity

When using key condition expressions in DynamoDB, we want to know how the time to get data changes as the amount of data grows.

We ask: How does the query time grow when we have more items in the table or partition?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query using a key condition expression.

const params = {
  TableName: "Music",
  KeyConditionExpression: "Artist = :artistName",
  ExpressionAttributeValues: {
    ":artistName": "No One You Know"
  }
};
const result = await dynamodb.query(params).promise();
    

This code queries the "Music" table for all items where the Artist equals "No One You Know" using a key condition expression.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Scanning items in the partition matching the key condition.
• How many times: Once per matching item in the partition.

How Execution Grows With Input

As the number of items with the same key grows, the query checks each matching item.

Input Size (n)	Approx. Operations
10	About 10 item checks
100	About 100 item checks
1000	About 1000 item checks

Pattern observation: The time grows roughly in direct proportion to the number of matching items.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of items that match the key condition.

Common Mistake

[X] Wrong: "The query always takes the same time no matter how many items match."

[OK] Correct: The query must read each matching item, so more matches mean more work and longer time.

Interview Connect

Understanding how query time grows with data size helps you explain efficient data access in DynamoDB, a key skill for working with real databases.

Self-Check

"What if we added a sort key condition to narrow results? How would the time complexity change?"

Practice

1. What is the required part of a key condition expression in DynamoDB?

easy

A. Sort key condition

B. Partition key condition

C. Both partition and sort key conditions

D. Neither partition nor sort key condition

Solution

1. Step 1: Understand key condition expression components

   Key condition expressions must always include the partition key condition to identify the partition to query.

2. Step 2: Identify optional parts

   The sort key condition is optional and used to refine the query within the partition.

3. Final Answer:

   Partition key condition -> Option B

4. Quick Check:

   Partition key condition = required [OK]

Hint: Partition key condition is always required in key condition expressions [OK]

Common Mistakes:

• Thinking sort key condition is mandatory
• Using only sort key condition without partition key
• Confusing key condition with filter expressions

2. Which of the following is the correct syntax for a key condition expression to find items with partition key 'UserID' equal to '123'?

easy

A. UserID = '123'

B. partition_key = 'UserID' AND sort_key = '123'

C. UserID == 123

D. Key('UserID').eq('123')

Solution

1. Step 1: Identify correct key condition syntax

   In DynamoDB, key condition expressions use attribute names and operators like '=' with values in quotes for strings.

2. Step 2: Evaluate each option

   UserID = '123' uses correct syntax: UserID = '123'. partition_key = 'UserID' AND sort_key = '123' uses wrong attribute names and syntax. UserID == 123 uses '==' which is invalid. Key('UserID').eq('123') is not valid DynamoDB syntax.

3. Final Answer:

   UserID = '123' -> Option A

4. Quick Check:

   Correct syntax uses '=' and quotes for strings [OK]

Hint: Use single '=' and quotes for string values in key condition expressions [OK]

Common Mistakes:

• Using '==' instead of '='
• Confusing attribute names with keywords
• Using function syntax not supported in key conditions

3. Given a DynamoDB table with partition key 'UserID' and sort key 'Timestamp', what will this key condition expression return?
UserID = 'user1' AND Timestamp BETWEEN 100 AND 200

medium

A. All items with UserID 'user1' only

B. All items with Timestamp between 100 and 200 regardless of UserID

C. All items with UserID 'user1' and Timestamp between 100 and 200 inclusive

D. Syntax error due to BETWEEN usage

Solution

1. Step 1: Analyze partition key condition

   The expression requires UserID to be 'user1', so only items with this partition key are considered.

2. Step 2: Analyze sort key condition with BETWEEN

   The sort key Timestamp must be between 100 and 200 inclusive, filtering items within that range.

3. Final Answer:

   All items with UserID 'user1' and Timestamp between 100 and 200 inclusive -> Option C

4. Quick Check:

   Partition key + BETWEEN on sort key filters correctly [OK]

Hint: BETWEEN filters sort key range within partition key [OK]

Common Mistakes:

• Ignoring partition key condition
• Thinking BETWEEN applies to partition key
• Assuming syntax error with BETWEEN

4. You wrote this key condition expression:
begins_with(UserID, :uid) AND Timestamp = :ts
But your query returns an error. What is the likely cause?

medium

A. Using begins_with on the partition key

B. Missing partition key condition

C. begins_with function used on sort key is valid, so no error

D. Incorrect use of AND operator

Solution

1. Step 1: Identify key condition expression rules

   Partition key condition must use '=' operator; functions like begins_with are not allowed on partition key.

2. Step 2: Check usage of begins_with

   begins_with is valid only on sort key, not partition key. If used on partition key, it causes an error.

3. Final Answer:

   Using begins_with on the partition key -> Option A

4. Quick Check:

   begins_with only valid on sort key [OK]

Hint: begins_with only works on sort key, not partition key [OK]

Common Mistakes:

• Using begins_with on partition key
• Omitting partition key condition
• Misusing AND operator syntax

5. You want to query a DynamoDB table with partition key 'Category' and sort key 'Date'. You need all items where Category is 'Books' and Date starts with '2023-06'. Which key condition expression should you use?

hard

A. begins_with(Category, 'Books') AND Date = '2023-06'

B. Category = 'Books' AND Date BETWEEN '2023-06-01' AND '2023-06-30'

C. Category = 'Books' OR begins_with(Date, '2023-06')

D. Category = 'Books' AND begins_with(Date, '2023-06')

Solution

1. Step 1: Identify partition key condition

   Category must be exactly 'Books', so use equality operator on partition key.

2. Step 2: Use begins_with on sort key

   Date starts with '2023-06' means use begins_with function on sort key Date.

3. Step 3: Evaluate options

   Category = 'Books' AND begins_with(Date, '2023-06') correctly combines equality on partition key and begins_with on sort key. Category = 'Books' AND Date BETWEEN '2023-06-01' AND '2023-06-30' uses BETWEEN but requires exact date range, which is more complex. Category = 'Books' OR begins_with(Date, '2023-06') uses OR which is invalid in key condition expressions. begins_with(Category, 'Books') AND Date = '2023-06' incorrectly uses begins_with on partition key.

4. Final Answer:

   Category = 'Books' AND begins_with(Date, '2023-06') -> Option D

5. Quick Check:

   Partition key = value AND begins_with on sort key [OK]

Hint: Use '=' for partition key and begins_with() for sort key prefix [OK]

Common Mistakes:

• Using OR instead of AND
• Using begins_with on partition key
• Using BETWEEN without exact date range