Querying GSI in DynamoDB - Time & Space Complexity

Time Complexity: Querying GSI

O(n)

Understanding Time Complexity

When we ask how fast a DynamoDB query runs on a Global Secondary Index (GSI), we want to know how the work grows as the data grows.

We are trying to see how the number of items in the GSI affects the time it takes to get results.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const params = {
  TableName: "Orders",
  IndexName: "CustomerIndex",
  KeyConditionExpression: "CustomerId = :cid",
  ExpressionAttributeValues: {
    ":cid": { S: "12345" }
  }
};

const result = await dynamodb.query(params).promise();
    

This code queries the GSI named "CustomerIndex" to find all orders for a specific customer ID.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning through matching items in the GSI for the given customer ID.
• How many times: Once for each matching item found in the GSI.

How Execution Grows With Input

As the number of orders for a customer grows, the query takes longer because it reads more matching items.

Input Size (n)	Approx. Operations
10	Reads about 10 items
100	Reads about 100 items
1000	Reads about 1000 items

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 the number of matching items in the GSI.

Common Mistake

[X] Wrong: "Querying a GSI always takes constant time regardless of data size."

[OK] Correct: The query time depends on how many items match the key condition, so more matches mean more work.

Interview Connect

Understanding how query time grows with data size shows you know how databases handle indexes and why efficient queries matter.

Self-Check

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

Practice

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

easy

A. To delete items from the table

B. To create a backup of the table

C. To update the primary key of items

D. To find items using an alternate key without scanning the whole table

Solution

1. Step 1: Understand what a GSI is used for

   A GSI allows querying data using a different key than the primary key.

2. Step 2: Identify the main benefit of querying a GSI

   Querying a GSI helps find items quickly without scanning the entire table.

3. Final Answer:

   To find items using an alternate key without scanning the whole table -> Option D

4. Quick Check:

   Query GSI = alternate key search [OK]

Hint: GSI lets you search by different keys fast [OK]

Common Mistakes:

• Confusing GSI query with table scan
• Thinking GSI is for deleting or updating keys
• Assuming GSI creates backups

2. Which of the following is the correct way to specify a GSI name in a DynamoDB query using AWS SDK?

easy

A. query({ TableName: 'MyTable', Index: 'MyGSI', KeyConditionExpression: 'GSIKey = :val', ExpressionAttributeValues: { ':val': '123' } })

B. query({ TableName: 'MyTable', KeyName: 'MyGSI', KeyConditionExpression: 'GSIKey = :val', ExpressionAttributeValues: { ':val': '123' } })

C. query({ TableName: 'MyTable', IndexName: 'MyGSI', KeyConditionExpression: 'GSIKey = :val', ExpressionAttributeValues: { ':val': '123' } })

D. query({ TableName: 'MyTable', GSIName: 'MyGSI', KeyConditionExpression: 'GSIKey = :val', ExpressionAttributeValues: { ':val': '123' } })

Solution

1. Step 1: Recall the correct parameter name for GSI in DynamoDB query

   The correct parameter to specify a GSI is 'IndexName'.

2. Step 2: Check the options for correct syntax

   Only query({ TableName: 'MyTable', IndexName: 'MyGSI', KeyConditionExpression: 'GSIKey = :val', ExpressionAttributeValues: { ':val': '123' } }) uses 'IndexName' correctly with other required fields.

3. Final Answer:

   query({ TableName: 'MyTable', IndexName: 'MyGSI', KeyConditionExpression: 'GSIKey = :val', ExpressionAttributeValues: { ':val': '123' } }) -> Option C

4. Quick Check:

   Use IndexName to specify GSI [OK]

Hint: Use 'IndexName' to specify GSI in query params [OK]

Common Mistakes:

• Using 'KeyName' or 'GSIName' instead of 'IndexName'
• Omitting ExpressionAttributeValues
• Wrong key condition syntax

3. Given a DynamoDB table with a GSI named 'StatusIndex' on attribute 'status', what will the following query return?

query({ TableName: 'Orders', IndexName: 'StatusIndex', KeyConditionExpression: 'status = :s', ExpressionAttributeValues: { ':s': 'shipped' } })

medium

A. All orders with status 'shipped' using the GSI

B. All orders regardless of status

C. An error because 'status' is not the primary key

D. No results because GSI queries are not supported

Solution

1. Step 1: Understand the query parameters

   The query uses 'StatusIndex' GSI with a key condition on 'status' = 'shipped'.

2. Step 2: Determine what the query returns

   It returns all items where 'status' attribute equals 'shipped' using the GSI, which is designed for this attribute.

3. Final Answer:

   All orders with status 'shipped' using the GSI -> Option A

4. Quick Check:

   Query GSI by status = shipped returns matching items [OK]

Hint: Query GSI with key condition returns matching items [OK]

Common Mistakes:

• Thinking GSI query returns all items
• Assuming GSI query causes error if attribute not primary key
• Believing GSI queries are unsupported

4. You wrote this DynamoDB query to use a GSI but get an error:

query({ TableName: 'Products', IndexName: 'CategoryIndex', KeyConditionExpression: 'category = :c', ExpressionAttributeValues: { ':c': 'books' } })

What is the most likely cause of the error?

medium

A. You cannot query a GSI in DynamoDB

B. The attribute 'category' is not the partition key of the GSI 'CategoryIndex'

C. ExpressionAttributeValues is missing a value

D. The table name 'Products' is incorrect

Solution

1. Step 1: Understand GSI key requirements

   When querying a GSI, the KeyConditionExpression must use the GSI's partition key attribute.

2. Step 2: Identify the error cause

   If 'category' is not the partition key of 'CategoryIndex', the query will fail with an error.

3. Final Answer:

   The attribute 'category' is not the partition key of the GSI 'CategoryIndex' -> Option B

4. Quick Check:

   GSI query key must be GSI partition key [OK]

Hint: GSI query key must match GSI partition key [OK]

Common Mistakes:

• Using a non-key attribute in KeyConditionExpression
• Assuming table name typo causes this error
• Believing GSI queries are unsupported

5. You have a DynamoDB table 'Employees' with a GSI named 'DeptIndex' where the partition key is 'department' and sort key is 'hireDate'. You want to find all employees in 'Sales' hired after '2023-01-01'. Which query is correct?

hard

A. query({ TableName: 'Employees', IndexName: 'DeptIndex', KeyConditionExpression: 'department = :d AND hireDate > :h', ExpressionAttributeValues: { ':d': 'Sales', ':h': '2023-01-01' } })

B. query({ TableName: 'Employees', IndexName: 'DeptIndex', KeyConditionExpression: 'department = :d OR hireDate > :h', ExpressionAttributeValues: { ':d': 'Sales', ':h': '2023-01-01' } })

C. query({ TableName: 'Employees', KeyConditionExpression: 'department = :d AND hireDate > :h', ExpressionAttributeValues: { ':d': 'Sales', ':h': '2023-01-01' } })

D. query({ TableName: 'Employees', IndexName: 'DeptIndex', FilterExpression: 'department = :d AND hireDate > :h', ExpressionAttributeValues: { ':d': 'Sales', ':h': '2023-01-01' } })

Solution

1. Step 1: Use the GSI name and correct key condition

   Query must specify 'IndexName' as 'DeptIndex' and use KeyConditionExpression with partition key and sort key conditions.

2. Step 2: Check logical operators and expressions

   KeyConditionExpression supports 'AND' for partition key and sort key conditions; 'OR' is invalid here.

3. Step 3: Verify FilterExpression usage

   FilterExpression filters after query; it cannot replace KeyConditionExpression for keys.

4. Final Answer:

   query({ TableName: 'Employees', IndexName: 'DeptIndex', KeyConditionExpression: 'department = :d AND hireDate > :h', ExpressionAttributeValues: { ':d': 'Sales', ':h': '2023-01-01' } }) -> Option A

5. Quick Check:

   Use KeyConditionExpression with AND on GSI keys [OK]

Hint: Use AND in KeyConditionExpression for partition and sort keys [OK]

Common Mistakes:

• Using OR instead of AND in KeyConditionExpression
• Omitting IndexName for GSI query
• Using FilterExpression instead of KeyConditionExpression for keys