GSI overloading technique in DynamoDB - Time & Space Complexity

Time Complexity: GSI overloading technique

O(n)

Understanding Time Complexity

When using Global Secondary Indexes (GSIs) in DynamoDB, it's important to understand how query time grows as data increases.

We want to see how the GSI overloading technique affects the speed of queries as more items are stored.

Scenario Under Consideration

Analyze the time complexity of this DynamoDB query using a GSI with overloading.

// Query using GSI with overloaded partition key
const params = {
  TableName: "Orders",
  IndexName: "GSI1",
  KeyConditionExpression: "GSI1PK = :gsiKey",
  ExpressionAttributeValues: {
    ":gsiKey": "USER#123"
  }
};
const result = await dynamodb.query(params).promise();
    

This code queries the GSI where the partition key is overloaded to group multiple item types under one key.

Identify Repeating Operations

Look for repeated work inside the query process.

• Primary operation: Scanning items with the same GSI partition key.
• How many times: Once per query, but the number of items returned depends on how many share the overloaded key.

How Execution Grows With Input

As more items share the same overloaded GSI key, the query must process more data.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the query time grows directly with the number of items that share the overloaded GSI key.

Common Mistake

[X] Wrong: "Using a GSI with an overloaded key always makes queries fast regardless of data size."

[OK] Correct: When many items share the same overloaded key, the query must scan all of them, so time grows with that number.

Interview Connect

Understanding how GSI overloading affects query time helps you design better DynamoDB tables and answer questions about scaling data access.

Self-Check

"What if we split the overloaded GSI key into multiple keys? How would that change the query time complexity?"

Practice

1. What is the main benefit of using the GSI overloading technique in DynamoDB?

easy

A. It allows using a single Global Secondary Index for multiple query patterns.

B. It automatically encrypts data stored in the table.

C. It increases the size limit of DynamoDB items.

D. It enables multi-region replication without extra setup.

Solution

1. Step 1: Understand GSI overloading purpose

   GSI overloading is designed to let one index serve many query types by using prefixes and composite keys.

2. Step 2: Identify the main benefit

   This reduces the number of GSIs needed, saving costs and improving query flexibility.

3. Final Answer:

   It allows using a single Global Secondary Index for multiple query patterns. -> Option A

4. Quick Check:

   GSI overloading = single index, multiple queries [OK]

Hint: Remember: one GSI, many queries saves cost and complexity [OK]

Common Mistakes:

• Thinking GSI overloading encrypts data
• Confusing GSI overloading with item size limits
• Assuming it enables multi-region replication

2. Which of the following is the correct way to define a partition key for a GSI using overloading with prefixes?

easy

A. PartitionKey = "USER#" + UserId

B. PartitionKey = UserId + "#USER"

C. PartitionKey = UserId

D. PartitionKey = "#" + UserId + "USER"

Solution

1. Step 1: Understand prefix usage in GSI keys

   Prefixes like "USER#" help separate different entity types in the same GSI.

2. Step 2: Check correct concatenation

   The prefix should come first, then the unique identifier, so "USER#" + UserId is correct.

3. Final Answer:

   PartitionKey = "USER#" + UserId -> Option A

4. Quick Check:

   Prefix before ID = "USER#" + UserId [OK]

Hint: Prefix always goes before the ID in composite keys [OK]

Common Mistakes:

• Putting prefix after the ID
• Using no prefix at all
• Adding extra symbols incorrectly

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

Query:
PK = "ORDER#123"
SK begins_with "ITEM#"

medium

A. Returns no results because SK cannot be filtered

B. Returns all orders with PK starting with "ORDER#"

C. Returns all items with SK exactly equal to "ITEM#"

D. Returns all items related to order 123 with SK starting with "ITEM#"

Solution

1. Step 1: Understand the query keys

   The query filters on PK = "ORDER#123" and SK begins with "ITEM#" which targets items under order 123.

2. Step 2: Interpret begins_with on SK

   Using begins_with on SK returns all sort keys starting with "ITEM#", so all order items are returned.

3. Final Answer:

   Returns all items related to order 123 with SK starting with "ITEM#" -> Option D

4. Quick Check:

   PK exact + SK begins_with = filtered order items [OK]

Hint: begins_with on SK filters items under one PK [OK]

Common Mistakes:

• Thinking begins_with applies to PK
• Assuming SK must be exact match
• Believing SK cannot be filtered in query

4. You have a GSI with partition key GSI_PK and sort key GSI_SK. You want to query all "USER" entities but your query returns no results. Which of the following is the most likely cause?

medium

A. You used begins_with on the partition key instead of the sort key.

B. You forgot to add the prefix "USER#" to the partition key value in the query.

C. You queried the base table instead of the GSI.

D. You used a filter expression instead of a key condition.

Solution

1. Step 1: Check prefix usage in GSI overloading

   GSI overloading requires prefixes like "USER#" in the partition key to separate entity types.

2. Step 2: Identify missing prefix impact

   If the query omits the prefix, it won't match any items because keys are stored with prefixes.

3. Final Answer:

   You forgot to add the prefix "USER#" to the partition key value in the query. -> Option B

4. Quick Check:

   Missing prefix in PK = no results [OK]

Hint: Always include prefixes in GSI key queries [OK]

Common Mistakes:

• Using begins_with on partition key
• Querying base table instead of GSI
• Using filter instead of key condition

5. You want to design a GSI overloading scheme to support queries for both USER and ORDER entities in the same index. Which key design below best supports efficient queries for:
1) All orders by a user
2) All users by status

Choose the best partition key and sort key combination.

hard

A. Partition Key: "TYPE#" + EntityType, Sort Key: "ID#" + EntityId

B. Partition Key: "USER#" + UserId for orders, "USER#" + UserId for users; Sort Key: "ORDER#" + OrderId for orders, "USER#" + UserId for users

C. Partition Key: "USER#" + UserId for orders, "STATUS#" + Status for users; Sort Key: "ORDER#" + OrderId for orders, "USER#" + UserId for users

D. Partition Key: EntityId, Sort Key: EntityType

Solution

1. Step 1: Analyze query requirements

   Query 1 needs all orders by a user, so partition key should be "USER#" + UserId for orders.
   Query 2 needs all users by status, so partition key should be "STATUS#" + Status for users.

2. Step 2: Check sort key design

   Sort keys differentiate entities: "ORDER#" + OrderId for orders, "USER#" + UserId for users to keep uniqueness and sorting.

3. Step 3: Evaluate options

   Partition Key: "USER#" + UserId for orders, "STATUS#" + Status for users; Sort Key: "ORDER#" + OrderId for orders, "USER#" + UserId for users matches these requirements by overloading the GSI with different prefixes for partition keys and sort keys.

4. Final Answer:

   Partition Key: "USER#" + UserId for orders, "STATUS#" + Status for users; Sort Key: "ORDER#" + OrderId for orders, "USER#" + UserId for users -> Option C

5. Quick Check:

   Use different prefixes per entity and query need [OK]

Hint: Use distinct prefixes per entity and query type in keys [OK]

Common Mistakes:

• Using same prefix for all entities
• Not differentiating partition keys by query type
• Using entity ID as partition key without prefix