Index capacity and cost in DynamoDB - Time & Space Complexity

Time Complexity: Index capacity and cost

O(n)

Understanding Time Complexity

When using indexes in DynamoDB, it's important to understand how the cost and capacity scale as data grows.

We want to know how adding more data affects the work DynamoDB does when using indexes.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query 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 code queries the "Orders" table using a GSI on CustomerId to find all orders for a customer.

Identify Repeating Operations

Look for repeated work done by DynamoDB when processing the query.

• Primary operation: Reading index entries matching CustomerId.
• How many times: Once per matching item in the index.

How Execution Grows With Input

As the number of orders for a customer grows, DynamoDB must read more index entries.

Input Size (n)	Approx. Operations
10	Reads 10 index entries
100	Reads 100 index entries
1000	Reads 1000 index entries

Pattern observation: The work grows directly with the number of matching items.

Final Time Complexity

Time Complexity: O(n)

This means the time to query grows linearly with the number of matching items in the index.

Common Mistake

[X] Wrong: "Using an index makes queries always super fast regardless of data size."

[OK] Correct: Even with indexes, DynamoDB reads each matching item, so more matches mean more work.

Interview Connect

Understanding how index queries scale helps you design efficient data access patterns and explain your choices clearly.

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 reason to use indexes in DynamoDB?

easy

A. To speed up query performance by allowing efficient data access

B. To reduce the storage size of the table

C. To automatically backup data

D. To encrypt data at rest

Solution

1. Step 1: Understand the purpose of indexes

   Indexes in DynamoDB are designed to speed up queries by providing alternate ways to access data efficiently.

2. Step 2: Eliminate unrelated options

   Options about storage size, backup, and encryption are unrelated to index functionality.

3. Final Answer:

   To speed up query performance by allowing efficient data access -> Option A

4. Quick Check:

   Indexes improve query speed = B [OK]

Hint: Indexes speed queries, not reduce storage or backup [OK]

Common Mistakes:

• Thinking indexes reduce storage cost
• Confusing indexes with backup features
• Assuming indexes encrypt data

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

easy

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

B. {
"GlobalSecondaryIndexes": [
{
"IndexName": "MyGSI",
"KeySchema": [
{"AttributeName": "UserId", "KeyType": "HASH"}
],
"Projection": {"ProjectionType": "ALL"},
"ProvisionedThroughput": {"ReadCapacityUnits": 5, "WriteCapacityUnits": 5}
}
]
}

C. {
"GlobalSecondaryIndexes": {
"IndexName": "MyGSI"
}
}

D. {
"Indexes": [
{
"Name": "MyGSI"
}
]
}

Solution

1. Step 1: Identify correct GSI syntax

   Global Secondary Indexes require an array under "GlobalSecondaryIndexes" with full details: IndexName, KeySchema, Projection, and ProvisionedThroughput.

2. Step 2: Compare options

   { "GlobalSecondaryIndexes": [ { "IndexName": "MyGSI", "KeySchema": [ {"AttributeName": "UserId", "KeyType": "HASH"} ], "Projection": {"ProjectionType": "ALL"}, "ProvisionedThroughput": {"ReadCapacityUnits": 5, "WriteCapacityUnits": 5} } ] } correctly uses "GlobalSecondaryIndexes" as an array with all required fields. Others use wrong keys or incomplete structures.

3. Final Answer:

   { "GlobalSecondaryIndexes": [ { "IndexName": "MyGSI", "KeySchema": [ {"AttributeName": "UserId", "KeyType": "HASH"} ], "Projection": {"ProjectionType": "ALL"}, "ProvisionedThroughput": {"ReadCapacityUnits": 5, "WriteCapacityUnits": 5} } ] } -> Option B

4. Quick Check:

   GSI syntax requires array with full details = A [OK]

Hint: GSIs need full details in GlobalSecondaryIndexes array [OK]

Common Mistakes:

• Using LocalSecondaryIndexes instead of GlobalSecondaryIndexes
• Providing object instead of array for GSIs
• Omitting ProvisionedThroughput for GSIs

3. Given a DynamoDB table with a provisioned write capacity of 10 units and a Global Secondary Index (GSI) with 5 write capacity units, what is the total write capacity units consumed when writing one item to the table and the GSI?

medium

A. 5 units

B. 10 units

C. 15 units

D. 20 units

Solution

1. Step 1: Understand write capacity consumption

   Writing one item consumes write capacity units on the main table plus on each index that is updated.

2. Step 2: Add main table and GSI write units

   Main table uses 10 units, GSI uses 5 units, total = 10 + 5 = 15 units.

3. Final Answer:

   15 units -> Option C

4. Quick Check:

   Total write capacity = main + GSI = 15 [OK]

Hint: Add main table and index write units for total cost [OK]

Common Mistakes:

• Counting only main table write units
• Counting only GSI write units
• Multiplying instead of adding capacities

4. You notice your DynamoDB table's write capacity is being exceeded even though your application writes only a few items per second. Which of the following is the most likely cause related to indexes?

medium

A. You have a Global Secondary Index with high write capacity units causing extra cost

B. You forgot to create any indexes

C. Your table has no read capacity units set

D. You are using Local Secondary Indexes which do not affect write capacity

Solution

1. Step 1: Analyze write capacity usage

   Writes to the table also consume write capacity on GSIs, increasing total usage.

2. Step 2: Identify cause of exceeded capacity

   If GSIs have high write capacity or many writes, they can cause capacity to be exceeded even if main table writes are low.

3. Final Answer:

   You have a Global Secondary Index with high write capacity units causing extra cost -> Option A

4. Quick Check:

   GSIs increase write capacity usage = C [OK]

Hint: Check GSIs for hidden write capacity usage [OK]

Common Mistakes:

• Assuming no indexes means no extra capacity
• Confusing read and write capacity units
• Thinking Local Secondary Indexes increase write capacity

5. You want to optimize costs for a DynamoDB table with a Global Secondary Index (GSI). The table has 20 write capacity units and the GSI has 10 write capacity units. If your application writes 5 items per second, how can you reduce costs without affecting query performance on the GSI?

hard

A. Disable the table's write capacity units

B. Remove the GSI to save all index costs

C. Increase the table write capacity units to 30

D. Reduce the GSI write capacity units to 5 and enable auto scaling

Solution

1. Step 1: Understand cost drivers

   Write capacity units on both table and GSI affect cost. Reducing GSI units lowers cost but must still handle write load.

2. Step 2: Apply auto scaling and adjust capacity

   Reducing GSI write units to match actual writes (5) and enabling auto scaling balances cost and performance.

3. Final Answer:

   Reduce the GSI write capacity units to 5 and enable auto scaling -> Option D

4. Quick Check:

   Lower GSI units + auto scaling = cost optimization [OK]

Hint: Match GSI capacity to writes and use auto scaling [OK]

Common Mistakes:

• Removing GSI and losing query performance
• Increasing table capacity unnecessarily
• Disabling write capacity causing failures