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?"

Practice

1. What is the main difference between a Local Secondary Index (LSI) and a Global Secondary Index (GSI) in DynamoDB?

easy

A. LSI can have a different partition key, but GSI must use the main table's partition key.

B. LSI uses the same partition key as the main table, but GSI can use a different partition key.

C. LSI and GSI both require the same partition and sort keys as the main table.

D. LSI is only for read operations, while GSI is only for write operations.

Solution

1. Step 1: Understand LSI key structure

   LSI shares the same partition key as the main table but allows a different sort key.

2. Step 2: Understand GSI key structure

   GSI can have a completely different partition key and sort key from the main table.

3. Final Answer:

   LSI uses the same partition key as the main table, but GSI can use a different partition key. -> Option B

4. Quick Check:

   LSI shares partition key, GSI can differ [OK]

Hint: LSI shares partition key; GSI can change both keys [OK]

Common Mistakes:

• Thinking LSI can have a different partition key
• Assuming GSI must use main table keys
• Confusing read/write capabilities of indexes

2. Which of the following is the correct syntax to define a Global Secondary Index (GSI) in a DynamoDB table using AWS CloudFormation?

easy

A. "GlobalSecondaryIndexes": [{"IndexName": "GSI1", "KeySchema": [{"AttributeName": "UserId", "KeyType": "HASH"}], "Projection": {"ProjectionType": "KEYS_ONLY"}}]

B. "LocalSecondaryIndexes": [{"IndexName": "GSI1", "KeySchema": [{"AttributeName": "UserId", "KeyType": "HASH"}], "Projection": {"ProjectionType": "ALL"}}]

C. "GlobalSecondaryIndexes": [{"IndexName": "GSI1", "KeySchema": [{"AttributeName": "UserId", "KeyType": "RANGE"}], "Projection": {"ProjectionType": "ALL"}}]

D. "GlobalSecondaryIndexes": [{"IndexName": "GSI1", "KeySchema": [{"AttributeName": "UserId", "KeyType": "HASH"}], "Projection": {"ProjectionType": "ALL"}}]

Solution

1. Step 1: Identify correct index type and key schema

   GlobalSecondaryIndexes is the correct property for GSI, and the partition key must have KeyType "HASH".

2. Step 2: Check projection type and syntax

   ProjectionType "ALL" is valid and commonly used; syntax matches CloudFormation format.

3. Final Answer:

   "GlobalSecondaryIndexes": [{"IndexName": "GSI1", "KeySchema": [{"AttributeName": "UserId", "KeyType": "HASH"}], "Projection": {"ProjectionType": "ALL"}}] -> Option D

4. Quick Check:

   GSI uses GlobalSecondaryIndexes with HASH key [OK]

Hint: GSI uses GlobalSecondaryIndexes with HASH key [OK]

Common Mistakes:

• Using LocalSecondaryIndexes for GSI
• Setting KeyType to RANGE for partition key
• Incorrect projection types or syntax errors

3. Given a DynamoDB table with a Global Secondary Index (GSI) on attribute Category as partition key and Price as sort key, what will the following query return?

Query on GSI where Category = 'Books' and Price between 10 and 20

medium

A. All items with Category 'Books' and Price between 10 and 20

B. All items with Price between 10 and 20 regardless of Category

C. All items with Category 'Books' regardless of Price

D. An error because Price cannot be used in query conditions

Solution

1. Step 1: Understand GSI query conditions

   Query on GSI requires specifying the partition key (Category = 'Books') and can filter by sort key range (Price between 10 and 20).

2. Step 2: Interpret the query result

   The query returns all items matching Category 'Books' with Price in the specified range.

3. Final Answer:

   All items with Category 'Books' and Price between 10 and 20 -> Option A

4. Quick Check:

   GSI query filters partition and sort keys correctly [OK]

Hint: Query GSI with partition key + sort key range filters [OK]

Common Mistakes:

• Ignoring partition key in query
• Thinking sort key can't be filtered
• Expecting error on valid query

4. You created a Local Secondary Index (LSI) on a DynamoDB table but your query on the LSI returns no results even though matching items exist. What is the most likely cause?

medium

A. The LSI was created with a different partition key than the main table.

B. The query used a filter expression instead of a key condition.

C. The query did not specify the same partition key as the main table.

D. LSIs do not support queries, only scans.

Solution

1. Step 1: Recall LSI key requirements

   LSI shares the same partition key as the main table, so queries must specify that partition key.

2. Step 2: Analyze query behavior

   If the query does not specify the partition key, no results will be returned because partition key is mandatory for queries on LSI.

3. Final Answer:

   The query did not specify the same partition key as the main table. -> Option C

4. Quick Check:

   LSI queries require main table partition key [OK]

Hint: LSI queries must include main table partition key [OK]

Common Mistakes:

• Assuming LSI can have different partition key
• Using filter instead of key condition for partition key
• Believing LSI does not support queries

5. You have a DynamoDB table with a partition key UserId and sort key OrderDate. You want to efficiently query all orders by Status and sort them by OrderAmount. Which secondary index should you create and how?

hard

A. Create a Global Secondary Index with partition key Status and sort key OrderAmount.

B. Create a Local Secondary Index with partition key UserId and sort key Status.

C. Create a Global Secondary Index with partition key UserId and sort key Status.

D. Create a Local Secondary Index with partition key Status and sort key OrderAmount.

Solution

1. Step 1: Identify query requirements

   You want to query by Status (different from main partition key) and sort by OrderAmount.

2. Step 2: Choose index type and keys

   Since Status is different from main partition key, use a Global Secondary Index with Status as partition key and OrderAmount as sort key.

3. Final Answer:

   Create a Global Secondary Index with partition key Status and sort key OrderAmount. -> Option A

4. Quick Check:

   GSI allows different partition and sort keys [OK]

Hint: Use GSI when partition key differs from main table [OK]

Common Mistakes:

• Trying to use LSI with different partition key
• Swapping partition and sort keys incorrectly
• Choosing wrong index type for query pattern