Composite primary key in DynamoDB - Time & Space Complexity

Time Complexity: Composite primary key

O(n)

Understanding Time Complexity

When using a composite primary key in DynamoDB, it is important to understand how the time to find data changes as the amount of data grows.

We want to know how the database handles queries using the partition key (first part) of the composite primary key and how that affects speed.

Scenario Under Consideration

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

    const params = {
      TableName: "Orders",
      KeyConditionExpression: "CustomerId = :cid",
      ExpressionAttributeValues: {
        ":cid": "12345"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries the "Orders" table for items matching a customer ID, using a composite primary key.

Identify Repeating Operations

Look for repeated steps that affect how long the query takes.

• Primary operation: Searching the partition key (CustomerId) to find matching items.
• How many times: The database looks only inside the partition matching CustomerId.

How Execution Grows With Input

As the number of orders for one customer grows, the query looks through more items with that CustomerId.

Input Size (n)	Approx. Operations
10 orders for one customer	About 10 checks inside that partition
100 orders for one customer	About 100 checks inside that partition
1000 orders for one customer	About 1000 checks inside that partition

Pattern observation: The time grows roughly in direct proportion to the number of items with the same partition key.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of items sharing the same partition key.

Common Mistake

[X] Wrong: "Using a composite key means the query always runs in constant time no matter how many items exist."

[OK] Correct: The partition key lookup is fast, but if many items share the same partition key, the database must scan those items by the sort key, so time grows with that number.

Interview Connect

Understanding how composite keys affect query speed shows you know how DynamoDB organizes data and why choosing keys carefully matters for performance.

Self-Check

"What if we also specify the sort key with an equality condition like OrderDate = :od? How would the time complexity change?"

Practice

1.

What is a composite primary key in DynamoDB?

easy

A. A key that allows duplicate items

B. A key made of only one attribute

C. A key made of two attributes: PartitionKey and SortKey

D. A key used only for indexing

Solution

1. Step 1: Understand primary key types in DynamoDB

   DynamoDB supports simple primary keys (one attribute) and composite primary keys (two attributes).

2. Step 2: Identify composite primary key components

   A composite primary key consists of a PartitionKey and a SortKey to uniquely identify items.

3. Final Answer:

   A key made of two attributes: PartitionKey and SortKey -> Option C

4. Quick Check:

   Composite primary key = PartitionKey + SortKey [OK]

Hint: Composite key always has PartitionKey and SortKey [OK]

Common Mistakes:

• Thinking composite key has only one attribute
• Confusing composite key with secondary indexes
• Believing composite key allows duplicates

2.

Which of the following is the correct way to define a composite primary key in DynamoDB table creation?

{
  "TableName": "Orders",
  "KeySchema": [
    {"AttributeName": "CustomerId", "KeyType": "HASH"},
    {"AttributeName": "OrderDate", "KeyType": "RANGE"}
  ]
}

easy

A. Use KeyType RANGE for both attributes

B. Use KeyType RANGE for PartitionKey and HASH for SortKey

C. Use KeyType HASH for both attributes

D. Use KeyType HASH for PartitionKey and RANGE for SortKey

Solution

1. Step 1: Recall KeyType meanings

   In DynamoDB, HASH means PartitionKey and RANGE means SortKey.

2. Step 2: Match KeyType to attributes

   PartitionKey must be HASH and SortKey must be RANGE for composite keys.

3. Final Answer:

   Use KeyType HASH for PartitionKey and RANGE for SortKey -> Option D

4. Quick Check:

   PartitionKey=HASH, SortKey=RANGE [OK]

Hint: HASH = PartitionKey, RANGE = SortKey in KeySchema [OK]

Common Mistakes:

• Swapping HASH and RANGE roles
• Using same KeyType for both keys
• Confusing attribute names with KeyType

3.

Given a DynamoDB table with composite primary key (UserId as PartitionKey, Timestamp as SortKey), what will this query return?

{
  "TableName": "UserActivity",
  "KeyConditionExpression": "UserId = :uid and Timestamp > :time",
  "ExpressionAttributeValues": {
    ":uid": {"S": "user123"},
    ":time": {"N": "1609459200"}
  }
}

medium

A. All activities of user123 with Timestamp greater than 1609459200

B. All activities of all users with Timestamp greater than 1609459200

C. All activities of user123 regardless of Timestamp

D. Syntax error due to missing SortKey in query

Solution

1. Step 1: Understand KeyConditionExpression

   It filters items by PartitionKey equality and SortKey condition.

2. Step 2: Analyze the query conditions

   UserId = :uid restricts to user123; Timestamp > :time filters timestamps after 1609459200.

3. Final Answer:

   All activities of user123 with Timestamp greater than 1609459200 -> Option A

4. Quick Check:

   PartitionKey + SortKey condition filters items [OK]

Hint: PartitionKey = value AND SortKey condition filters items [OK]

Common Mistakes:

• Thinking query returns all users' data
• Ignoring SortKey condition
• Assuming syntax error without SortKey equality

4.

What is wrong with this DynamoDB query using composite primary key (UserId as PartitionKey, OrderId as SortKey)?

{
  "TableName": "Orders",
  "KeyConditionExpression": "OrderId = :oid",
  "ExpressionAttributeValues": {
    ":oid": {"S": "order789"}
  }
}

medium

A. PartitionKey UserId is missing in KeyConditionExpression

B. SortKey OrderId cannot be used in KeyConditionExpression

C. ExpressionAttributeValues syntax is incorrect

D. TableName is invalid

Solution

1. Step 1: Recall query requirements for composite keys

   Queries must specify PartitionKey equality in KeyConditionExpression.

2. Step 2: Check the given query

   Only SortKey OrderId is used; PartitionKey UserId is missing, causing error.

3. Final Answer:

   PartitionKey UserId is missing in KeyConditionExpression -> Option A

4. Quick Check:

   PartitionKey must be in query condition [OK]

Hint: Always include PartitionKey equality in query [OK]

Common Mistakes:

• Using only SortKey in query condition
• Assuming SortKey alone can identify items
• Ignoring required PartitionKey in queries

5.

You want to store blog posts in DynamoDB. Each post has a AuthorId and a PostDate. You want to quickly find all posts by an author sorted by date. Which composite primary key design is best?

hard

A. PartitionKey: PostDate, SortKey: AuthorId

B. PartitionKey: AuthorId, SortKey: PostDate

C. PartitionKey: AuthorId only, no SortKey

D. PartitionKey: PostDate only, no SortKey

Solution

1. Step 1: Identify query pattern

   You want to find all posts by an author, sorted by date.

2. Step 2: Choose PartitionKey and SortKey accordingly

   PartitionKey should be AuthorId to group posts by author; SortKey should be PostDate to sort posts by date.

3. Final Answer:

   PartitionKey: AuthorId, SortKey: PostDate -> Option B

4. Quick Check:

   Group by author, sort by date = AuthorId + PostDate [OK]

Hint: PartitionKey groups, SortKey sorts related items [OK]

Common Mistakes:

• Swapping PartitionKey and SortKey roles
• Using only one key losing sorting ability
• Choosing SortKey that doesn't support query pattern