Composite sort key pattern in DynamoDB - Time & Space Complexity

Time Complexity: Composite sort key pattern

O(n)

Understanding Time Complexity

When using a composite sort key in DynamoDB, we want to understand how the time to find data changes as we add more items.

We ask: How does the number of operations grow when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query using a composite sort key.

    const params = {
      TableName: "Orders",
      KeyConditionExpression: "CustomerId = :cid AND begins_with(OrderDate, :datePrefix)",
      ExpressionAttributeValues: {
        ":cid": "12345",
        ":datePrefix": "2024-06"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries orders for one customer, filtering by order dates starting with a given prefix.

Identify Repeating Operations

Look at what repeats when this query runs.

• Primary operation: Scanning items with the same CustomerId and matching the date prefix in the sort key.
• How many times: Once per matching item in the queried range.

How Execution Grows With Input

As more orders exist for the customer in the date range, the query checks more items.

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

Pattern observation: The work grows roughly in direct proportion to how many items match the prefix.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with the number of matching items in the sort key range.

Common Mistake

[X] Wrong: "Using a composite sort key means the query always runs in constant time."

[OK] Correct: The query time depends on how many items match the sort key condition, so it grows with that number, not fixed.

Interview Connect

Understanding how composite sort keys affect query time helps you design efficient DynamoDB tables and answer questions about scaling data access.

Self-Check

What if we changed the sort key condition from begins_with to an exact match? How would the time complexity change?

Practice

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

easy

A. To create a unique partition key for each item

B. To increase the read capacity of the table

C. To encrypt data stored in the table

D. To combine multiple attributes into one key for better sorting and grouping

Solution

1. Step 1: Understand composite sort key concept

   A composite sort key combines multiple values into one string to organize data efficiently.

2. Step 2: Identify its main use

   This helps group related items and sort them within the same partition key.

3. Final Answer:

   To combine multiple attributes into one key for better sorting and grouping -> Option D

4. Quick Check:

   Composite sort key = combine attributes [OK]

Hint: Composite sort keys combine values to sort and group data [OK]

Common Mistakes:

• Confusing composite sort key with partition key
• Thinking it encrypts data
• Assuming it increases capacity

2. Which of the following is a correct example of a composite sort key format?

easy

A. 2023-04-01_Customer123_Order

B. Customer123|Order|2023-04-01

C. Order:2023-04-01:Customer123

D. Order#2023-04-01#Customer123

Solution

1. Step 1: Identify proper delimiter usage

   Composite sort keys use clear delimiters like colons to separate parts for easy parsing.

2. Step 2: Check each option's delimiter consistency

   Order:2023-04-01:Customer123 uses colons consistently, making it a clear composite key format.

3. Final Answer:

   Order:2023-04-01:Customer123 -> Option C

4. Quick Check:

   Clear delimiters = Order:2023-04-01:Customer123 [OK]

Hint: Use consistent delimiters like ':' in composite keys [OK]

Common Mistakes:

• Using inconsistent or unclear delimiters
• Mixing delimiters without pattern
• Not separating parts clearly

3. Given a DynamoDB table with partition key UserID and composite sort key OrderDate#OrderID, what will be the result of querying for UserID = 'U123' and sort key begins with '2023-05-'?

medium

A. All orders by user U123 placed in May 2023

B. All orders by user U123 regardless of date

C. Orders from all users placed in May 2023

D. No results because sort key format is invalid

Solution

1. Step 1: Understand the composite sort key structure

   The sort key combines OrderDate and OrderID separated by '#', so prefix '2023-05-' matches May 2023 orders.

2. Step 2: Query with partition key and sort key prefix

   Querying UserID='U123' and sort key begins with '2023-05-' returns all U123's orders in May 2023.

3. Final Answer:

   All orders by user U123 placed in May 2023 -> Option A

4. Quick Check:

   Partition + sort key prefix = filtered orders [OK]

Hint: Use sort key prefix to filter by date in composite keys [OK]

Common Mistakes:

• Ignoring partition key in query
• Assuming all users' data is returned
• Misunderstanding sort key prefix filtering

4. You wrote a composite sort key as OrderDate-OrderID but your queries using begins_with('2023-06') return no results. What is the likely problem?

medium

A. The sort key should use a consistent delimiter like ':' or '#' instead of '-'

B. The query must use contains instead of begins_with

C. The delimiter '-' is missing in the query filter

D. The partition key is incorrect

Solution

1. Step 1: Check delimiter consistency in composite keys

   Using '-' as delimiter can cause confusion if date format also contains '-'.

2. Step 2: Understand query prefix matching

   Because date and delimiter both use '-', the prefix '2023-06' may not match correctly; consistent delimiters like ':' or '#' avoid this.

3. Final Answer:

   The sort key should use a consistent delimiter like ':' or '#' instead of '-' -> Option A

4. Quick Check:

   Delimiter confusion breaks prefix queries [OK]

Hint: Avoid delimiters that appear in data parts [OK]

Common Mistakes:

• Using delimiters that clash with data format
• Wrong query function for prefix
• Ignoring partition key correctness

5. You want to design a DynamoDB table to store chat messages with partition key ChatRoomID and composite sort key combining MessageDate and MessageID. Which composite sort key format is best to efficiently query messages by date and maintain uniqueness?

hard

A. MessageID#MessageDate with date in any format

B. MessageDate#MessageID with date in ISO format (YYYY-MM-DDTHH:mm:ss)

C. MessageDate-MessageID with date in MM/DD/YYYY

D. MessageDate_MessageID with date as Unix timestamp

Solution

1. Step 1: Choose delimiter and date format for sorting

   Using '#' as delimiter is clear and ISO date format sorts lexicographically by date/time.

2. Step 2: Ensure uniqueness and query efficiency

   Placing MessageDate first allows range queries by date; MessageID ensures uniqueness within same timestamp.

3. Final Answer:

   MessageDate#MessageID with date in ISO format (YYYY-MM-DDTHH:mm:ss) -> Option B

4. Quick Check:

   ISO date + clear delimiter = best composite key [OK]

Hint: Use ISO date + clear delimiter for sortable composite keys [OK]

Common Mistakes:

• Using ambiguous delimiters
• Placing unique ID before date
• Using non-lexicographically sortable date formats