LSI vs GSI comparison in DynamoDB - Performance Comparison

Time Complexity: LSI vs GSI comparison

O(n)

Understanding Time Complexity

When using DynamoDB, we often add indexes to find data faster. Local Secondary Indexes (LSI) and Global Secondary Indexes (GSI) help with this.

We want to understand how the time to get data changes as the data grows when using LSI or GSI.

Scenario Under Consideration

Analyze the time complexity of querying data using LSI and GSI.

// Query using LSI
const paramsLSI = {
  TableName: "Orders",
  IndexName: "OrderDateIndex", // LSI
  KeyConditionExpression: "CustomerId = :cid",
  ExpressionAttributeValues: { ":cid": { S: "123" } }
};

// Query using GSI
const paramsGSI = {
  TableName: "Orders",
  IndexName: "StatusIndex", // GSI
  KeyConditionExpression: "OrderStatus = :status",
  ExpressionAttributeValues: { ":status": { S: "SHIPPED" } }
};

This code queries orders by customer using an LSI and by status using a GSI.

Identify Repeating Operations

Both queries scan matching items in the index to return results.

• Primary operation: Scanning index entries matching the query condition.
• How many times: Once per matching item in the index.

How Execution Grows With Input

As the number of matching items grows, the query reads more entries.

Input Size (matching items)	Approx. Operations
10	10 reads
100	100 reads
1000	1000 reads

Pattern observation: The work grows directly with how many items match the query.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "LSI queries are always faster than GSI queries because they are local."

[OK] Correct: Both LSI and GSI queries scan matching items, so speed depends on how many items match, not just index type.

Interview Connect

Understanding how query time grows with data size helps you design better DynamoDB tables and indexes, a key skill for real projects.

Self-Check

What if we added a filter after the query to reduce results? How would that affect the time complexity?