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

Practice

1.

What is the main role of a partition key in AWS DynamoDB?

easy

A. It groups data into partitions for efficient storage and retrieval.

B. It sorts data within a partition in ascending order.

C. It encrypts the data before storing it.

D. It defines the backup schedule for the table.

Solution

1. Step 1: Understand partition key purpose

   The partition key is used to group data into partitions, which helps DynamoDB distribute and store data efficiently.

2. Step 2: Differentiate from sort key

   The sort key orders data inside each partition but does not group data across partitions.

3. Final Answer:

   It groups data into partitions for efficient storage and retrieval. -> Option A

4. Quick Check:

   Partition key = groups data [OK]

Hint: Partition key groups data, sort key orders it inside partitions [OK]

Common Mistakes:

• Confusing partition key with sort key
• Thinking partition key sorts data
• Assuming partition key controls backups

2.

Which of the following is the correct way to define a DynamoDB table with a partition key named UserId and a sort key named OrderDate in AWS CLI?

aws dynamodb create-table --table-name Orders --attribute-definitions AttributeName=UserId,AttributeType=S AttributeName=OrderDate,AttributeType=S --key-schema ...

easy

A. --key-schema AttributeName=UserId,KeyType=HASH AttributeName=OrderDate,KeyType=RANGE

B. --key-schema AttributeName=OrderDate,KeyType=HASH AttributeName=UserId,KeyType=RANGE

C. --key-schema AttributeName=UserId,KeyType=RANGE AttributeName=OrderDate,KeyType=HASH

D. --key-schema AttributeName=OrderDate,KeyType=RANGE AttributeName=UserId,KeyType=HASH

Solution

1. Step 1: Identify partition and sort key roles

   The partition key uses KeyType=HASH and the sort key uses KeyType=RANGE in DynamoDB key schema.

2. Step 2: Match keys to names

   UserId is the partition key (HASH), OrderDate is the sort key (RANGE).

3. Final Answer:

   --key-schema AttributeName=UserId,KeyType=HASH AttributeName=OrderDate,KeyType=RANGE -> Option A

4. Quick Check:

   Partition=HASH, Sort=RANGE [OK]

Hint: Partition key = HASH, sort key = RANGE in key schema [OK]

Common Mistakes:

• Swapping HASH and RANGE key types
• Mixing up partition and sort key names
• Using wrong attribute types

3.

Given a DynamoDB table with CustomerId as partition key and InvoiceDate as sort key, what will the following query return?

Query: KeyConditionExpression = "CustomerId = :cid AND InvoiceDate > :date"

Assuming :cid is '123' and :date is '2023-01-01'.

medium

A. All invoices for customer '123' regardless of date.

B. All invoices for customer '123' with dates after January 1, 2023.

C. All invoices for all customers with dates after January 1, 2023.

D. All invoices with dates before January 1, 2023.

Solution

1. Step 1: Understand KeyConditionExpression

   The query filters items where partition key CustomerId equals '123' and sort key InvoiceDate is greater than '2023-01-01'.

2. Step 2: Interpret the filter effect

   This returns all invoices for customer '123' with InvoiceDate after January 1, 2023.

3. Final Answer:

   All invoices for customer '123' with dates after January 1, 2023. -> Option B

4. Quick Check:

   Partition key = '123' AND sort key > '2023-01-01' [OK]

Hint: Partition key filters customer, sort key filters date range [OK]

Common Mistakes:

• Ignoring partition key filter
• Assuming query returns all customers
• Confusing greater than with less than

4.

What is wrong with this DynamoDB key schema definition?

--attribute-definitions AttributeName=OrderId,AttributeType=S AttributeName=OrderDate,AttributeType=S --key-schema AttributeName=OrderDate,KeyType=HASH AttributeName=OrderId,KeyType=RANGE

medium

A. Attribute names cannot contain uppercase letters.

B. Attribute types must be different for partition and sort keys.

C. KeyType values must both be HASH for composite keys.

D. Partition key and sort key are swapped; OrderId should be HASH, OrderDate RANGE.

Solution

1. Step 1: Check key roles

   Partition key must be HASH and sort key must be RANGE in key schema.

2. Step 2: Identify swapped keys

   OrderId should be the partition key (HASH), but here OrderDate is set as HASH and OrderId as RANGE, which is incorrect.

3. Final Answer:

   Partition key and sort key are swapped; OrderId should be HASH, OrderDate RANGE. -> Option D

4. Quick Check:

   Partition = HASH, Sort = RANGE order matters [OK]

Hint: Partition key always HASH, sort key always RANGE [OK]

Common Mistakes:

• Swapping HASH and RANGE key types
• Assuming attribute types must differ
• Thinking uppercase letters are invalid

5.

You want to design a DynamoDB table to store user activity logs. Each user can have multiple logs per day. Which key design is best to efficiently query all logs for a user on a specific day?

hard

A. Partition key: UserId, Sort key: ActivityDateTime

B. Partition key: ActivityDateTime, Sort key: UserId

C. Partition key: UserId_ActivityDate, Sort key: ActivityTime

D. Partition key: ActivityType, Sort key: UserId

Solution

1. Step 1: Understand query needs

   You want to query logs by user and by specific day efficiently.

2. Step 2: Design keys for efficient queries

   Combining UserId and ActivityDate as partition key groups logs per user per day. Using ActivityTime as sort key orders logs within that day.

3. Final Answer:

   Partition key: UserId_ActivityDate, Sort key: ActivityTime -> Option C

4. Quick Check:

   Composite partition key groups user-day logs [OK]

Hint: Combine user and date in partition key for day queries [OK]

Common Mistakes:

• Using ActivityDateTime as partition key alone
• Swapping partition and sort keys
• Not combining keys to match query pattern