Global Secondary Index (GSI) concept in DynamoDB - Time & Space Complexity

Time Complexity: Global Secondary Index (GSI) concept

O(n)

Understanding Time Complexity

When using a Global Secondary Index (GSI) in DynamoDB, we want to know how the time to find data changes as the amount of data grows.

We ask: How does searching with a GSI scale when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of querying a DynamoDB table using a GSI.

    const params = {
      TableName: "Orders",
      IndexName: "CustomerIdIndex",
      KeyConditionExpression: "CustomerId = :cid",
      ExpressionAttributeValues: {
        ":cid": { S: "12345" }
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries the "Orders" table using a GSI named "CustomerIdIndex" to find all orders for a specific customer.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Querying the GSI partitions that match the customer ID.
• How many times: Depends on how many orders the customer has; each matching item is read once.

How Execution Grows With Input

As the number of orders for a customer grows, the time to get all results grows too.

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

Pattern observation: The time grows roughly in direct proportion to the number of matching items.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with how many matching items the GSI returns.

Common Mistake

[X] Wrong: "Using a GSI always makes queries run in constant time, no matter how many items match."

[OK] Correct: The GSI helps find matching items quickly, but reading all matching items still takes time proportional to how many there are.

Interview Connect

Understanding how GSIs affect query time helps you design efficient DynamoDB tables and answer questions about scaling data access.

Self-Check

What if we added a filter expression after querying the GSI? How would that affect the time complexity?

Practice

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

easy

A. To allow queries using alternate keys different from the primary key

B. To store backup copies of the table data

C. To increase the size limit of the table

D. To encrypt data automatically

Solution

1. Step 1: Understand what a GSI does

   A GSI lets you query the table using different keys than the main primary key.

2. Step 2: Compare options to GSI purpose

   Options A, C, and D describe unrelated features like backup, size, or encryption, which are not GSI functions.

3. Final Answer:

   To allow queries using alternate keys different from the primary key -> Option A

4. Quick Check:

   GSI = alternate query keys [OK]

Hint: GSI lets you search by different keys, not backup or encryption [OK]

Common Mistakes:

• Confusing GSI with backups
• Thinking GSI increases table size
• Assuming GSI encrypts data

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

easy

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

B. {
"SecondaryIndexes": [
{
"IndexName": "GSI1",
"KeySchema": [
{"AttributeName": "GSIKey", "KeyType": "RANGE"}
],
"Projection": {"ProjectionType": "KEYS_ONLY"}
}
]
}

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

D. {
"GlobalSecondaryIndexes": [
{
"IndexName": "GSI1",
"KeySchema": [
{"AttributeName": "GSIKey", "KeyType": "HASH"},
{"AttributeName": "SortKey", "KeyType": "RANGE"}
],
"Projection": {"ProjectionType": "INCLUDE", "NonKeyAttributes": ["Attr1"]}
}
]
}

Solution

1. Step 1: Check the correct JSON structure for GSI

   The GlobalSecondaryIndexes must be an array of objects, each with IndexName, KeySchema, and Projection.

2. Step 2: Validate key schema and projection

   { "GlobalSecondaryIndexes": [ { "IndexName": "GSI1", "KeySchema": [ {"AttributeName": "GSIKey", "KeyType": "HASH"}, {"AttributeName": "SortKey", "KeyType": "RANGE"} ], "Projection": {"ProjectionType": "INCLUDE", "NonKeyAttributes": ["Attr1"]} } ] } correctly uses an array, has both HASH and RANGE keys, and a valid projection with included attributes.

3. Final Answer:

   Correct GSI JSON with array, keys, and projection -> Option D

4. Quick Check:

   GSI JSON array with keys and projection = A [OK]

Hint: GSI must be an array with keys and projection defined [OK]

Common Mistakes:

• Using object instead of array for GlobalSecondaryIndexes
• Wrong key types or missing HASH key
• Incorrect property names like SecondaryIndexes

3. Given a DynamoDB table with a GSI on attribute Category (HASH key) and Price (RANGE key), what will the following query return?

Query({ IndexName: 'CategoryPriceIndex', KeyConditionExpression: 'Category = :cat and Price > :minPrice', ExpressionAttributeValues: { ':cat': 'Books', ':minPrice': 20 } })

medium

A. All items where Price is greater than 20 regardless of Category

B. All items where Category is 'Books' or Price is greater than 20

C. All items where Category is 'Books' and Price is greater than 20

D. Syntax error because Price cannot be used in KeyConditionExpression

Solution

1. Step 1: Understand KeyConditionExpression with GSI keys

   The query uses the GSI's HASH key 'Category' with equality and RANGE key 'Price' with a greater than condition, which is valid.

2. Step 2: Interpret the query filter

   The query returns items where Category equals 'Books' AND Price is greater than 20, matching the GSI keys.

3. Final Answer:

   All items where Category is 'Books' and Price is greater than 20 -> Option C

4. Quick Check:

   GSI query with HASH and RANGE keys = All items where Category is 'Books' and Price is greater than 20 [OK]

Hint: GSI query uses HASH = and RANGE with conditions correctly [OK]

Common Mistakes:

• Confusing AND with OR in KeyConditionExpression
• Thinking Price can't be in KeyConditionExpression
• Assuming query returns all items ignoring Category

4. You created a GSI with IndexName: 'UserEmailIndex' on attribute Email as HASH key. Your query on this GSI returns no results even though items with matching emails exist. What is the most likely cause?

medium

A. The GSI was created after the items were inserted and has not yet indexed them

B. You used the primary key instead of the GSI key in the query

C. The Email attribute is not projected to the GSI

D. DynamoDB does not support querying on GSIs

Solution

1. Step 1: Understand GSI indexing timing

   When a GSI is created after data insertion, it takes time to index existing items. Queries may return empty until indexing completes.

2. Step 2: Evaluate other options

   You used the primary key instead of the GSI key in the query is about query keys but question states query is on GSI. The Email attribute is not projected to the GSI is invalid because HASH key attributes must be projected automatically. DynamoDB does not support querying on GSIs is false; DynamoDB supports GSI queries.

3. Final Answer:

   The GSI was created after the items were inserted and has not yet indexed them -> Option A

4. Quick Check:

   New GSI indexing delay causes empty query [OK]

Hint: New GSI needs time to index existing data before queries work [OK]

Common Mistakes:

• Assuming GSI queries always return instantly after creation
• Confusing projection with key attributes
• Believing DynamoDB doesn't support GSI queries

5. You have a DynamoDB table with a primary key UserID (HASH) and a GSI named OrderDateIndex with OrderDate as HASH and Status as RANGE key. You want to efficiently find all orders placed on '2023-05-01' with status 'Shipped'. Which query approach is best?

hard

A. Use a Scan on the GSI with FilterExpression for OrderDate and Status

B. Query the OrderDateIndex with KeyConditionExpression 'OrderDate = :date and Status = :status'

C. Query the main table with KeyConditionExpression 'UserID = :user and Status = :status'

D. Scan the table filtering for OrderDate and Status attributes

Solution

1. Step 1: Identify the best index for the query

   The GSI OrderDateIndex has OrderDate as HASH and Status as RANGE key, matching the query conditions.

2. Step 2: Choose efficient query method

   Querying the GSI with KeyConditionExpression on HASH and RANGE keys is efficient and uses indexes. Scans are less efficient and should be avoided.

3. Final Answer:

   Query the OrderDateIndex with KeyConditionExpression 'OrderDate = :date and Status = :status' -> Option B

4. Quick Check:

   Use GSI query with HASH and RANGE keys for best performance [OK]

Hint: Query GSI with HASH and RANGE keys, avoid scans for efficiency [OK]

Common Mistakes:

• Using Scan instead of Query causing slow performance
• Querying main table with wrong keys
• Filtering after Scan instead of using KeyConditionExpression