Sort key purpose and usage in DynamoDB - Time & Space Complexity

Time Complexity: Sort key purpose and usage

O(n)

Understanding Time Complexity

When using a sort key in DynamoDB, it helps organize data within a partition. Understanding how time grows when querying with a sort key is important.

We want to know how the number of operations changes as more items share the same partition key but have different sort keys.

Scenario Under Consideration

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

    const params = {
      TableName: "Orders",
      KeyConditionExpression: "CustomerId = :cid AND OrderDate > :date",
      ExpressionAttributeValues: {
        ":cid": "12345",
        ":date": "2023-01-01"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code fetches orders for one customer where the order date is after a certain date, using the sort key to filter.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Checking items with the same partition key and evaluating the sort key condition.
• How many times: Once for each item with that partition key until the condition is met or all are checked.

How Execution Grows With Input

As more orders exist for the same customer, the query checks more items to find those matching the date condition.

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

Pattern observation: The number of operations 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: "Using a sort key means queries always run in constant time regardless of data size."

[OK] Correct: The sort key helps organize data, but if many items share the partition key, the query still checks each relevant item, so time grows with that number.

Interview Connect

Knowing how sort keys affect query time shows you understand how DynamoDB organizes data and how to write efficient queries. This skill helps you design tables that scale well.

Self-Check

"What if we added a filter on a non-key attribute after the query? How would that affect the time complexity?"

Practice

1. What is the main purpose of a sort key in a DynamoDB table?

easy

A. To store large binary data efficiently

B. To uniquely identify each item across all partitions

C. To organize and order items within the same partition key

D. To encrypt data at rest automatically

Solution

1. Step 1: Understand partition and sort keys roles

   The partition key groups items, and the sort key orders items within that group.

2. Step 2: Identify the sort key's purpose

   The sort key organizes related items so they can be retrieved in order and filtered efficiently.

3. Final Answer:

   To organize and order items within the same partition key -> Option C

4. Quick Check:

   Sort key = Organize items in partition [OK]

Hint: Sort key orders items inside a partition [OK]

Common Mistakes:

• Confusing sort key with partition key uniqueness
• Thinking sort key encrypts data
• Assuming sort key stores large binary data

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 Timestamp using AWS CLI?

easy

A. aws dynamodb create-table --table-name MyTable --attribute-definitions AttributeName=Timestamp,AttributeType=N --key-schema AttributeName=Timestamp,KeyType=HASH --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5

B. aws dynamodb create-table --table-name MyTable --attribute-definitions AttributeName=UserID,AttributeType=S AttributeName=Timestamp,AttributeType=N --key-schema AttributeName=UserID,KeyType=HASH AttributeName=Timestamp,KeyType=HASH --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5

C. aws dynamodb create-table --table-name MyTable --attribute-definitions AttributeName=UserID,AttributeType=S --key-schema AttributeName=UserID,KeyType=RANGE --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5

D. aws dynamodb create-table --table-name MyTable --attribute-definitions AttributeName=UserID,AttributeType=S AttributeName=Timestamp,AttributeType=N --key-schema AttributeName=UserID,KeyType=HASH AttributeName=Timestamp,KeyType=RANGE --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5

Solution

1. Step 1: Check attribute definitions and key schema

   Partition key must have KeyType=HASH and sort key must have KeyType=RANGE.

2. Step 2: Verify aws dynamodb create-table --table-name MyTable --attribute-definitions AttributeName=UserID,AttributeType=S AttributeName=Timestamp,AttributeType=N --key-schema AttributeName=UserID,KeyType=HASH AttributeName=Timestamp,KeyType=RANGE --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5 matches correct key types

   aws dynamodb create-table --table-name MyTable --attribute-definitions AttributeName=UserID,AttributeType=S AttributeName=Timestamp,AttributeType=N --key-schema AttributeName=UserID,KeyType=HASH AttributeName=Timestamp,KeyType=RANGE --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5 uses UserID as HASH and Timestamp as RANGE, which is correct.

3. Final Answer:

   aws dynamodb create-table --table-name MyTable --attribute-definitions AttributeName=UserID,AttributeType=S AttributeName=Timestamp,AttributeType=N --key-schema AttributeName=UserID,KeyType=HASH AttributeName=Timestamp,KeyType=RANGE --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5 -> Option D

4. Quick Check:

   Partition=HASH, Sort=RANGE in CLI [OK]

Hint: Sort key uses KeyType=RANGE in key schema [OK]

Common Mistakes:

• Using KeyType=HASH for both keys
• Missing sort key in key schema
• Defining only partition key without sort key

3. Given a DynamoDB table with partition key UserID and sort key OrderDate, what will the following query return?

aws dynamodb query --table-name Orders --key-condition-expression "UserID = :uid AND OrderDate > :date" --expression-attribute-values '{":uid":{"S":"user123"}, ":date":{"S":"2023-01-01"}}'

medium

A. All orders for user123 with OrderDate after 2023-01-01, sorted by OrderDate

B. All orders for user123 regardless of OrderDate

C. All orders with OrderDate after 2023-01-01 for all users

D. Syntax error due to missing partition key in condition

Solution

1. Step 1: Analyze the key condition expression

   The query filters items where UserID equals 'user123' and OrderDate is greater than '2023-01-01'.

2. Step 2: Understand query behavior with partition and sort keys

   Query returns items for one partition key, ordered by sort key, filtered by the condition on sort key.

3. Final Answer:

   All orders for user123 with OrderDate after 2023-01-01, sorted by OrderDate -> Option A

4. Quick Check:

   Query filters by partition and sort key conditions [OK]

Hint: Query needs partition key equality and sort key condition [OK]

Common Mistakes:

• Expecting query to filter across all partitions
• Ignoring sort key condition in query
• Confusing query with scan operation

4. You wrote this DynamoDB query but it returns an error:

aws dynamodb query --table-name Sales --key-condition-expression "OrderID > :oid" --expression-attribute-values '{":oid":{"S":"1000"}}'

What is the likely cause?

medium

A. Using > operator on partition key is allowed

B. Missing partition key equality condition in key-condition-expression

C. Incorrect data type for expression attribute value

D. Missing sort key in attribute definitions

Solution

1. Step 1: Recall query key condition requirements

   DynamoDB query requires partition key equality condition in key-condition-expression.

2. Step 2: Identify error cause

   Query uses only 'OrderID > :oid' without partition key equality, causing error.

3. Final Answer:

   Missing partition key equality condition in key-condition-expression -> Option B

4. Quick Check:

   Partition key equality is mandatory in query [OK]

Hint: Query must have partition key equality condition [OK]

Common Mistakes:

• Using range operators on partition key
• Omitting partition key in query condition
• Confusing query with scan operation

5. You want to model a one-to-many relationship where each CustomerID can have multiple Invoices sorted by InvoiceDate. Which DynamoDB table design best uses the sort key to achieve this?

hard

A. Partition key: CustomerID, Sort key: InvoiceDate

B. Partition key: InvoiceDate, Sort key: CustomerID

C. Partition key: CustomerID only, no sort key

D. Partition key: InvoiceID, Sort key: InvoiceDate

Solution

1. Step 1: Understand one-to-many modeling in DynamoDB

   Use partition key for the 'one' side and sort key to order the 'many' items.

2. Step 2: Apply to CustomerID and Invoices

   CustomerID as partition key groups invoices; InvoiceDate as sort key orders them.

3. Final Answer:

   Partition key: CustomerID, Sort key: InvoiceDate -> Option A

4. Quick Check:

   Sort key models one-to-many order [OK]

Hint: Partition key = one side, sort key = many side order [OK]

Common Mistakes:

• Swapping partition and sort keys
• Not using sort key for ordering
• Using only partition key losing order info