GSI key selection strategy in DynamoDB - Time & Space Complexity

Time Complexity: GSI key selection strategy

O(n)

Understanding Time Complexity

When using Global Secondary Indexes (GSIs) in DynamoDB, the way we pick keys affects how fast queries run.

We want to know how the choice of keys changes the work DynamoDB does as data grows.

Scenario Under Consideration

Analyze the time complexity of querying a GSI with a chosen partition key and sort key.

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

This code queries a GSI named CustomerDateIndex using CustomerId as partition key and OrderDate as sort key.

Identify Repeating Operations

Look for repeated work done during the query.

• Primary operation: Scanning items with the same partition key in the GSI.
• How many times: Once per matching partition key group; then filtering by sort key range.

How Execution Grows With Input

As more items share the same partition key, the query checks more items in that group.

Input Size (n)	Approx. Operations
10 items with same key	10 checks
100 items with same key	100 checks
1000 items with same key	1000 checks

Pattern observation: The work grows linearly with the number of items sharing the partition key.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows directly with how many items share the same partition key in the GSI.

Common Mistake

[X] Wrong: "Choosing any partition key for the GSI will always give fast queries regardless of data distribution."

[OK] Correct: If many items share the same partition key, the query must check all those items, making it slower as data grows.

Interview Connect

Understanding how GSI key choices affect query speed shows you can design databases that stay fast even as data grows.

Self-Check

What if we changed the GSI partition key to a more unique attribute? How would the time complexity change?

Practice

1. What is the main purpose of choosing a good partition key for a Global Secondary Index (GSI) in DynamoDB?

easy

A. To evenly distribute data across partitions for faster queries

B. To store large binary objects efficiently

C. To encrypt data at rest automatically

D. To backup data to another region

Solution

1. Step 1: Understand partition key role in GSI

   The partition key determines how data is spread across storage partitions in DynamoDB.

2. Step 2: Importance of even data distribution

   Choosing a partition key that evenly distributes data avoids hot partitions and improves query speed.

3. Final Answer:

   To evenly distribute data across partitions for faster queries -> Option A

4. Quick Check:

   Partition key = data distribution [OK]

Hint: Partition key controls data spread, pick for balance [OK]

Common Mistakes:

• Thinking partition key orders data inside partitions
• Confusing partition key with sort key
• Assuming partition key encrypts data

2. Which of the following is the correct syntax to define a GSI with a partition key named Category and a sort key named Timestamp in a DynamoDB table creation JSON?

easy

A. {
"IndexName": "CategoryTimestampIndex",
"KeySchema": [
{"AttributeName": "Timestamp", "KeyType": "RANGE"},
{"AttributeName": "Category", "KeyType": "HASH"}
],
"Projection": {"ProjectionType": "ALL"}
}

B. {
"IndexName": "CategoryTimestampIndex",
"KeySchema": [
{"AttributeName": "Category", "KeyType": "HASH"},
{"AttributeName": "Timestamp", "KeyType": "RANGE"}
],
"Projection": {"ProjectionType": "ALL"}
}

C. {
"IndexName": "CategoryTimestampIndex",
"KeySchema": [
{"AttributeName": "Category", "KeyType": "RANGE"},
{"AttributeName": "Timestamp", "KeyType": "HASH"}
],
"Projection": {"ProjectionType": "ALL"}
}

D. {
"IndexName": "CategoryTimestampIndex",
"KeySchema": [
{"AttributeName": "Timestamp", "KeyType": "HASH"},
{"AttributeName": "Category", "KeyType": "RANGE"}
],
"Projection": {"ProjectionType": "ALL"}
}

Solution

1. Step 1: Identify partition and sort key roles

   Partition key uses KeyType "HASH" and sort key uses KeyType "RANGE" in DynamoDB.

2. Step 2: Match keys to correct KeyType

   Category is partition key so it must have KeyType "HASH"; Timestamp is sort key so it must have KeyType "RANGE".

3. Final Answer:

   Correct JSON with Category as HASH and Timestamp as RANGE -> Option B

4. Quick Check:

   Partition key = HASH, Sort key = RANGE [OK]

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

Common Mistakes:

• Swapping HASH and RANGE key types
• Using RANGE for partition key
• Incorrect JSON structure for KeySchema

3. Given a DynamoDB table with a GSI where the partition key is UserId and the sort key is OrderDate, what will be the result of this query?

Query on GSI with UserId = 'user123' and OrderDate between '2023-01-01' and '2023-01-31'

medium

A. All orders by user123 in January 2023 sorted by OrderDate

B. All orders by all users in January 2023

C. All orders by user123 regardless of date

D. Syntax error due to missing filter expression

Solution

1. Step 1: Understand query conditions on GSI keys

   Query uses partition key UserId = 'user123' and a range condition on sort key OrderDate between two dates.

2. Step 2: Result filters by UserId and date range

   Only items with UserId 'user123' and OrderDate in January 2023 are returned, sorted by OrderDate.

3. Final Answer:

   All orders by user123 in January 2023 sorted by OrderDate -> Option A

4. Quick Check:

   Partition key + sort key range = filtered query [OK]

Hint: Query filters partition key exactly, sort key by range [OK]

Common Mistakes:

• Thinking query returns all users' data
• Ignoring sort key range condition
• Assuming syntax error without filter expression

4. You created a GSI with partition key Category and sort key Price. Your queries on this GSI are slow and uneven. What is the most likely cause?

medium

A. Price is not indexed as a sort key

B. The table has no primary key

C. You forgot to project attributes

D. Category has very few distinct values causing hot partitions

Solution

1. Step 1: Analyze partition key distribution

   If Category has few distinct values, many items share the same partition key, causing hot partitions and slow queries.

2. Step 2: Understand impact on query performance

   Hot partitions limit throughput and cause uneven query speed despite having a sort key.

3. Final Answer:

   Category has very few distinct values causing hot partitions -> Option D

4. Quick Check:

   Few partition keys = hot partitions = slow queries [OK]

Hint: Few partition key values cause hot partitions [OK]

Common Mistakes:

• Assuming missing sort key causes slowness
• Ignoring partition key cardinality
• Thinking projection affects partitioning

5. You want to design a GSI to efficiently query orders by CustomerId and sort them by OrderStatus and then by OrderDate. Which key selection strategy is best?

hard

A. Partition key: CustomerId; Sort key: OrderDate only

B. Partition key: OrderStatus; Sort key: CustomerId#OrderDate concatenated string

C. Partition key: CustomerId; Sort key: OrderStatus#OrderDate concatenated string

D. Partition key: OrderDate; Sort key: CustomerId

Solution

1. Step 1: Identify query pattern requirements

   You want to query by CustomerId and sort first by OrderStatus, then by OrderDate.

2. Step 2: Design composite sort key for multi-level sorting

   Concatenate OrderStatus and OrderDate into one sort key string (e.g., 'Shipped#2023-06-01') to sort by status then date.

3. Step 3: Assign keys correctly

   Partition key should be CustomerId for grouping orders by customer; sort key is the concatenated string for sorting.

4. Final Answer:

   Partition key: CustomerId; Sort key: OrderStatus#OrderDate concatenated string -> Option C

5. Quick Check:

   Composite sort key enables multi-level sorting [OK]

Hint: Use composite sort key for multi-level sorting [OK]

Common Mistakes:

• Using OrderStatus as partition key causing uneven distribution
• Not combining sort keys for multi-level order
• Using OrderDate as partition key which breaks grouping