Secondary indexes (GSI, LSI) in AWS - Time & Space Complexity

Time Complexity: Secondary indexes (GSI, LSI)

O(n)

Understanding Time Complexity

When using secondary indexes in DynamoDB, it is important to understand how the time to get data grows as you ask for more items.

We want to know how the number of operations changes when querying with Global Secondary Indexes (GSI) or Local Secondary Indexes (LSI).

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

// Querying a DynamoDB table using a Global Secondary Index (GSI)
const params = {
  TableName: "Orders",
  IndexName: "CustomerIndex",
  KeyConditionExpression: "CustomerId = :cid",
  ExpressionAttributeValues: {
    ":cid": { S: "12345" }
  }
};
const result = await dynamodb.query(params).promise();

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

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Query API call on the GSI to fetch matching items.
• How many times: The query may be called multiple times if results are paginated due to size limits.

How Execution Grows With Input

As the number of matching items grows, the number of query calls grows roughly in proportion to the total items returned.

Input Size (n)	Approx. API Calls/Operations
10	1 query call (all results fit in one response)
100	1-2 query calls (may need pagination)
1000	Multiple query calls (several pages of results)

Pattern observation: The number of query calls grows linearly with the number of items returned because each call returns a limited page of results.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all matching items grows directly with how many items you want to retrieve.

Common Mistake

[X] Wrong: "Querying a GSI always takes the same time regardless of how many items match."

[OK] Correct: The query returns results in pages, so more matching items mean more calls and more time.

Interview Connect

Understanding how query time grows with data size helps you design efficient data access patterns and explain your choices clearly in discussions.

Self-Check

"What if we changed from querying a GSI to scanning the whole table? How would the time complexity change?"