Global Secondary Index (GSI) concept in DynamoDB - Time & Space Complexity

Time Complexity: Global Secondary Index (GSI) concept

O(n)

Understanding Time Complexity

When using a Global Secondary Index (GSI) in DynamoDB, we want to know how the time to find data changes as the amount of data grows.

We ask: How does searching with a GSI scale when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of querying a DynamoDB table using a GSI.

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

This code queries the "Orders" table using a GSI named "CustomerIdIndex" to find all orders for a specific customer.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Querying the GSI partitions that match the customer ID.
• How many times: Depends on how many orders the customer has; each matching item is read once.

How Execution Grows With Input

As the number of orders for a customer grows, the time to get all results grows too.

Input Size (n)	Approx. Operations
10 orders	About 10 reads
100 orders	About 100 reads
1000 orders	About 1000 reads

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 how many matching items the GSI returns.

Common Mistake

[X] Wrong: "Using a GSI always makes queries run in constant time, no matter how many items match."

[OK] Correct: The GSI helps find matching items quickly, but reading all matching items still takes time proportional to how many there are.

Interview Connect

Understanding how GSIs affect query time helps you design efficient DynamoDB tables and answer questions about scaling data access.

Self-Check

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