Querying GSI in DynamoDB - Time & Space Complexity

Time Complexity: Querying GSI

O(n)

Understanding Time Complexity

When we ask how fast a DynamoDB query runs on a Global Secondary Index (GSI), we want to know how the work grows as the data grows.

We are trying to see how the number of items in the GSI affects the time it takes to get results.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const params = {
  TableName: "Orders",
  IndexName: "CustomerIndex",
  KeyConditionExpression: "CustomerId = :cid",
  ExpressionAttributeValues: {
    ":cid": { S: "12345" }
  }
};

const result = await dynamodb.query(params).promise();
    

This code queries the GSI named "CustomerIndex" to find all orders for a specific customer ID.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning through matching items in the GSI for the given customer ID.
• How many times: Once for each matching item found in the GSI.

How Execution Grows With Input

As the number of orders for a customer grows, the query takes longer because it reads more matching items.

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

Pattern observation: The time grows roughly in direct proportion to the number of matching items.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Querying a GSI always takes constant time regardless of data size."

[OK] Correct: The query time depends on how many items match the key condition, so more matches mean more work.

Interview Connect

Understanding how query time grows with data size shows you know how databases handle indexes and why efficient queries matter.

Self-Check

"What if we added a filter expression after the query? How would that affect the time complexity?"