Local Secondary Index (LSI) concept in DynamoDB - Time & Space Complexity

Time Complexity: Local Secondary Index (LSI) concept

O(n)

Understanding Time Complexity

When using a Local Secondary Index (LSI) in DynamoDB, it's important to understand how the time to get your data changes as your data grows.

We want to know how the number of operations grows when we query using an LSI.

Scenario Under Consideration

Analyze the time complexity of this DynamoDB query using an LSI.

    const params = {
      TableName: "Orders",
      IndexName: "CustomerDateIndex", // LSI on CustomerID and OrderDate
      KeyConditionExpression: "CustomerID = :cid",
      ExpressionAttributeValues: {
        ":cid": { S: "12345" }
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries the Orders table using an LSI to find all orders for a specific customer.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Scanning the items with the same partition key (CustomerID) in the LSI.
• How many times: Once per matching item for that customer.

How Execution Grows With Input

As the number of orders for a customer grows, the query checks more items.

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

Pattern observation: The work grows directly with the number of matching items.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with how many items match the query.

Common Mistake

[X] Wrong: "Querying with an LSI always takes the same time no matter how many items match."

[OK] Correct: The query must check each matching item, so more items mean more work and longer time.

Interview Connect

Understanding how queries scale with data size shows you know how to design efficient data access in DynamoDB.

Self-Check

What if we changed the query to use a Global Secondary Index (GSI) instead of an LSI? How would the time complexity change?