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?

Practice

1. What is the main purpose of a Local Secondary Index (LSI) in DynamoDB?

easy

A. To store data in a separate table

B. To allow querying data with the same partition key but different sort keys

C. To create a new partition key for faster queries

D. To backup data automatically

Solution

1. Step 1: Understand LSI functionality

   LSI lets you query items with the same partition key but sorted by an alternate sort key.

2. Step 2: Compare options

   Only To allow querying data with the same partition key but different sort keys correctly describes this feature; others describe unrelated features.

3. Final Answer:

   To allow querying data with the same partition key but different sort keys -> Option B

4. Quick Check:

   LSI = alternate sort key with same partition key [OK]

Hint: LSI changes sort key, not partition key [OK]

Common Mistakes:

• Thinking LSI creates new partition keys
• Confusing LSI with Global Secondary Index
• Believing LSI stores data separately

2. Which of the following is the correct way to define a Local Secondary Index (LSI) when creating a DynamoDB table?

easy

A. Define the LSI with a different partition key than the main table

B. Define the LSI with a new partition key and no sort key

C. Define the LSI after the table is created using updateTable API

D. Define the LSI with the same partition key but a different sort key

Solution

1. Step 1: Recall LSI definition rules

   LSIs must use the same partition key as the main table but can have a different sort key.

2. Step 2: Check options

   Only Define the LSI with the same partition key but a different sort key matches this rule; others violate partition key or timing constraints.

3. Final Answer:

   Define the LSI with the same partition key but a different sort key -> Option D

4. Quick Check:

   LSI = same partition key + different sort key [OK]

Hint: LSI shares partition key, differs in sort key [OK]

Common Mistakes:

• Trying to create LSI after table creation
• Using different partition keys for LSI
• Omitting sort key in LSI definition

3. Given a DynamoDB table with partition key UserID and sort key Timestamp, and an LSI with sort key OrderStatus, what will the following query return?

Query: KeyConditionExpression = UserID = '123' AND OrderStatus = 'Pending'

medium

A. All items with OrderStatus 'Pending' regardless of UserID

B. All items with UserID '123' sorted by Timestamp

C. All items with UserID '123' and OrderStatus 'Pending' sorted by OrderStatus

D. Syntax error because OrderStatus cannot be used in KeyConditionExpression

Solution

1. Step 1: Understand query with LSI

   Query on LSI uses same partition key but different sort key (OrderStatus). The query filters UserID = '123' and OrderStatus = 'Pending'.

2. Step 2: Analyze query result

   It returns items with UserID '123' and OrderStatus 'Pending', sorted by OrderStatus.

3. Final Answer:

   All items with UserID '123' and OrderStatus 'Pending' sorted by OrderStatus -> Option C

4. Quick Check:

   Query on LSI filters by partition and LSI sort key [OK]

Hint: LSI query filters by partition key + LSI sort key [OK]

Common Mistakes:

• Assuming LSI changes partition key
• Thinking query returns all items with OrderStatus only
• Believing syntax error occurs using LSI sort key

4. You created a DynamoDB table with an LSI but your query using the LSI's sort key returns no results even though matching items exist. What is the most likely cause?

medium

A. The partition key value in the query is incorrect

B. You used the LSI's partition key instead of the main table's partition key

C. The LSI's sort key attribute is missing in some items

D. The LSI was not defined at table creation time

Solution

1. Step 1: Check LSI query requirements

   Queries on LSI require the correct partition key value; wrong partition key returns no results.

2. Step 2: Evaluate options

   The partition key value in the query is incorrect explains no results due to incorrect partition key; other options are less likely or invalid.

3. Final Answer:

   The partition key value in the query is incorrect -> Option A

4. Quick Check:

   Correct partition key needed for LSI query [OK]

Hint: Always verify partition key value in LSI queries [OK]

Common Mistakes:

• Trying to add LSI after table creation
• Ignoring missing sort key attributes
• Confusing LSI partition key with main table partition key

5. You have a DynamoDB table with partition key CustomerID and sort key OrderDate. You want to query all orders for a customer sorted by OrderStatus instead of OrderDate. How should you design the Local Secondary Index (LSI) to achieve this?

hard

A. Create an LSI with partition key CustomerID and sort key OrderStatus defined at table creation

B. Create an LSI with partition key OrderStatus and sort key OrderDate after table creation

C. Create a Global Secondary Index (GSI) with partition key CustomerID and sort key OrderStatus

D. Add OrderStatus as a new partition key in the main table

Solution

1. Step 1: Understand LSI design rules

   LSI must use the same partition key as the main table but can have a different sort key.

2. Step 2: Apply to problem

   To sort by OrderStatus for the same CustomerID, create an LSI with partition key CustomerID and sort key OrderStatus at table creation.

3. Step 3: Eliminate wrong options

   Create an LSI with partition key OrderStatus and sort key OrderDate after table creation is invalid because LSI cannot be created after table creation; Create a Global Secondary Index (GSI) with partition key CustomerID and sort key OrderStatus is about GSI, not LSI; Add OrderStatus as a new partition key in the main table changes partition key, which is not allowed.

4. Final Answer:

   Create an LSI with partition key CustomerID and sort key OrderStatus defined at table creation -> Option A

5. Quick Check:

   LSI = same partition key + new sort key at creation [OK]

Hint: LSI must be defined at table creation with same partition key [OK]

Common Mistakes:

• Trying to create LSI after table creation
• Confusing LSI with GSI
• Changing partition key in LSI