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?

Practice

1. Which statement correctly describes the difference between a Local Secondary Index (LSI) and a Global Secondary Index (GSI) in DynamoDB?

easy

A. LSI uses the same partition key but a different sort key; GSI uses different partition and sort keys.

B. LSI uses different partition keys; GSI uses the same partition key but different sort keys.

C. LSI and GSI both use the same partition and sort keys but differ in storage location.

D. LSI uses different partition and sort keys; GSI uses the same partition key and sort key.

Solution

1. Step 1: Analyze LSI key schema

   LSI shares the same partition key as the base table but allows a different sort key for alternate sorting within that partition.

2. Step 2: Analyze GSI key schema

   GSI allows both partition key and sort key to be different from the base table, enabling flexible query patterns across partitions.

3. Final Answer:

   LSI uses the same partition key but a different sort key; GSI uses different partition and sort keys. -> Option A

4. Quick Check:

   LSI = same partition key, different sort key; GSI = different keys [OK]

Hint: LSI = same partition key, GSI = different partition key [OK]

Common Mistakes:

• Confusing which keys LSI and GSI use
• Thinking LSI can have different partition keys
• Assuming GSI uses the same keys as the base table

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

easy

A. {
"IndexName": "LSI1",
"KeySchema": [
{"AttributeName": "UserId", "KeyType": "HASH"},
{"AttributeName": "OrderDate", "KeyType": "RANGE"}
],
"Projection": {"ProjectionType": "INCLUDE"}
}

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

C. {
"IndexName": "GSI1",
"KeySchema": [
{"AttributeName": "OrderDate", "KeyType": "RANGE"}
],
"Projection": {"ProjectionType": "INCLUDE", "NonKeyAttributes": ["Status"]}
}

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

Solution

1. Step 1: Check key schema order for GSI

   GSI requires a partition key (HASH) and optionally a sort key (RANGE). The partition key must come first in the KeySchema array.

2. Step 2: Validate attribute roles and projection

   { "IndexName": "GSI1", "KeySchema": [ {"AttributeName": "UserId", "KeyType": "HASH"}, {"AttributeName": "OrderDate", "KeyType": "RANGE"} ], "Projection": {"ProjectionType": "ALL"} } correctly defines UserId as HASH and OrderDate as RANGE with ProjectionType ALL, which is valid for GSI.

3. Final Answer:

   {\n \"IndexName\": \"GSI1\",\n \"KeySchema\": [\n {\"AttributeName\": \"UserId\", \"KeyType\": \"HASH\"},\n {\"AttributeName\": \"OrderDate\", \"KeyType\": \"RANGE\"}\n ],\n \"Projection\": {\"ProjectionType\": \"ALL\"}\n} -> Option B

4. Quick Check:

   GSI KeySchema starts with HASH key [OK]

Hint: GSI KeySchema starts with HASH key, then RANGE key [OK]

Common Mistakes:

• Swapping HASH and RANGE key types
• Using LSI name for GSI definition
• Missing required HASH key in KeySchema

3. Given a DynamoDB table with a partition key 'UserId' and sort key 'Timestamp', and an LSI defined with the same partition key 'UserId' but sort key 'OrderStatus', what will be the result of this query?

Query on LSI where UserId = '123' and OrderStatus = 'Pending'

medium

A. Returns all items with UserId '123' and Timestamp 'Pending'.

B. Query fails because LSI cannot be queried on OrderStatus.

C. Returns all items with UserId '123' regardless of OrderStatus.

D. Returns all items with UserId '123' and OrderStatus 'Pending' sorted by OrderStatus.

Solution

1. Step 1: Recall LSI query keys

   LSI uses the same partition key as the base table but allows querying by the alternate sort key, here 'OrderStatus'.

2. Step 2: Analyze query conditions

   The query filters on UserId = '123' (partition key) and OrderStatus = 'Pending' (LSI sort key), so it returns matching items sorted by OrderStatus.

3. Final Answer:

   Returns all items with UserId '123' and OrderStatus 'Pending' sorted by OrderStatus. -> Option D

4. Quick Check:

   LSI query uses same partition key + LSI sort key [OK]

Hint: LSI queries use same partition key, different sort key [OK]

Common Mistakes:

• Confusing sort key names between base and LSI
• Assuming LSI cannot be queried on alternate sort key
• Thinking query returns all UserId items ignoring sort key

4. You defined a GSI with partition key 'Category' and sort key 'Price'. Your query on the GSI with KeyConditionExpression 'Category = :cat and Price < :maxPrice' returns no results, but you know matching items exist. What is the most likely cause?

medium

A. The GSI was not properly populated because the base table items lack the 'Category' or 'Price' attributes.

B. The query syntax is invalid because GSI queries cannot use sort key conditions.

C. LSI should be used instead of GSI for this query pattern.

D. The base table partition key must be included in the query condition.

Solution

1. Step 1: Check attribute presence for GSI indexing

   GSI indexes only items that have the specified partition and sort key attributes. Missing attributes mean no index entry.

2. Step 2: Understand query behavior on GSI

   If items lack 'Category' or 'Price', they won't appear in the GSI, causing queries to return no results despite existing base table items.

3. Final Answer:

   The GSI was not properly populated because the base table items lack the 'Category' or 'Price' attributes. -> Option A

4. Quick Check:

   Missing GSI keys in items = no query results [OK]

Hint: GSI needs all key attributes in items to index them [OK]

Common Mistakes:

• Assuming GSI queries can't filter on sort key
• Confusing LSI and GSI usage
• Thinking base table keys must be in GSI query

5. You have a DynamoDB table with partition key 'UserId' and sort key 'Timestamp'. You want to support queries to find all orders by 'UserId' sorted by 'Timestamp', and also queries to find all orders by 'Status' sorted by 'OrderDate'. Which index setup is best?

hard

A. Use a GSI with partition key 'UserId' and sort key 'Timestamp' only.

B. Use an LSI with partition key 'Status' and sort key 'OrderDate'.

C. Use the base table and a GSI with partition key 'Status' and sort key 'OrderDate'.

D. Use only the base table keys; no indexes needed.

Solution

1. Step 1: Base table supports UserId-Timestamp query

   Queries by 'UserId' sorted by 'Timestamp' use base table keys directly.

2. Step 2: GSI supports Status-OrderDate query

   Queries by 'Status' sorted by 'OrderDate' require a different partition key ('Status'), so a GSI with partition key 'Status' and sort key 'OrderDate' is needed.

3. Final Answer:

   Use the base table and a GSI with partition key 'Status' and sort key 'OrderDate'. -> Option C

4. Quick Check:

   LSI = same partition key, GSI = different partition key [OK]

Hint: LSI for alternate sort key; GSI for different partition key [OK]

Common Mistakes:

• Trying to use LSI with different partition key
• Using only base table keys for all queries
• Confusing which index supports which query pattern