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?"