Why secondary indexes enable flexible queries in DynamoDB - Performance Analysis

Time Complexity: Why secondary indexes enable flexible queries

O(m)

Understanding Time Complexity

When using secondary indexes in DynamoDB, we want to know how query speed changes as data grows.

We ask: How does adding more data affect the time to find items using these indexes?

Scenario Under Consideration

Analyze the time complexity of querying a DynamoDB table using a secondary index.

const params = {
  TableName: "Products",
  IndexName: "CategoryIndex",
  KeyConditionExpression: "Category = :cat",
  ExpressionAttributeValues: {
    ":cat": "Books"
  }
};
const result = await dynamodb.query(params).promise();
    

This code queries items in the "Products" table by category using a secondary index called "CategoryIndex".

Identify Repeating Operations

Look for repeated steps that affect time.

• Primary operation: Searching the secondary index for matching keys.
• How many times: Depends on how many items match the category; the index lets DynamoDB jump directly to matches.

How Execution Grows With Input

As the total data grows, the query time grows mainly with the number of matching items, not the whole table.

Input Size (n)	Approx. Operations
10	About 10 matching items scanned
100	About 100 matching items scanned
1000	About 1000 matching items scanned

Pattern observation: Query time grows with the number of matching items, not total table size.

Final Time Complexity

Time Complexity: O(m)

This means query time grows in proportion to the number of matching items, making queries flexible and efficient.

Common Mistake

[X] Wrong: "Querying with a secondary index takes time proportional to the whole table size."

[OK] Correct: Secondary indexes let DynamoDB jump directly to matching items, so time depends on matches, not total data.

Interview Connect

Understanding how secondary indexes affect query time shows you can design flexible, fast queries in real projects.

Self-Check

What if the secondary index included a sort key? How would that change the time complexity of queries?

Practice

1. What is the main benefit of using secondary indexes in DynamoDB?

easy

A. They allow querying data using different keys without changing the main table

B. They automatically backup your data

C. They increase the storage capacity of the table

D. They encrypt data for security

Solution

1. Step 1: Understand the role of secondary indexes

   Secondary indexes let you query the table using keys other than the primary key.

2. Step 2: Compare other options

   Options A, B, and C describe features unrelated to secondary indexes.

3. Final Answer:

   They allow querying data using different keys without changing the main table -> Option A

4. Quick Check:

   Secondary indexes = flexible queries [OK]

Hint: Secondary indexes = new query keys without table changes [OK]

Common Mistakes:

• Confusing secondary indexes with backups
• Thinking indexes increase storage size
• Assuming indexes encrypt data

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

easy

A. {"IndexName": "GSI1", "KeySchema": [{"AttributeName": "Category", "KeyType": "RANGE"}], "Projection": {"ProjectionType": "KEYS_ONLY"}}

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

C. {"IndexName": "GSI1", "KeySchema": [{"AttributeName": "Category", "KeyType": "PRIMARY"}], "Projection": {"ProjectionType": "ALL"}}

D. {"IndexName": "GSI1", "KeySchema": [{"AttributeName": "Category", "KeyType": "SORT"}], "Projection": {"ProjectionType": "INCLUDE"}}

Solution

1. Step 1: Identify correct KeyType for GSI partition key

   For a GSI, the partition key uses KeyType 'HASH'. {"IndexName": "GSI1", "KeySchema": [{"AttributeName": "Category", "KeyType": "HASH"}], "Projection": {"ProjectionType": "ALL"}} uses 'HASH'.

2. Step 2: Check Projection type

   {"IndexName": "GSI1", "KeySchema": [{"AttributeName": "Category", "KeyType": "HASH"}], "Projection": {"ProjectionType": "ALL"}} uses 'ALL', which is valid. Other options use invalid KeyTypes like 'PRIMARY' or 'SORT'.

3. Final Answer:

   {"IndexName": "GSI1", "KeySchema": [{"AttributeName": "Category", "KeyType": "HASH"}], "Projection": {"ProjectionType": "ALL"}} -> Option B

4. Quick Check:

   GSI partition key = HASH [OK]

Hint: GSI partition key must be 'HASH' not 'RANGE' or others [OK]

Common Mistakes:

• Using 'PRIMARY' or 'SORT' as KeyType
• Confusing partition key with sort key
• Wrong ProjectionType values

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

Query({
  TableName: 'Products',
  IndexName: 'CategoryIndex',
  KeyConditionExpression: 'Category = :cat',
  ExpressionAttributeValues: { ':cat': 'Books' }
})

medium

A. All items where the primary key equals 'Books'

B. All items in the table regardless of Category

C. An error because the query does not specify the primary key

D. All items where the Category attribute equals 'Books' using the GSI

Solution

1. Step 1: Understand the use of IndexName in the query

   Specifying IndexName means the query uses the GSI on 'Category'.

2. Step 2: Analyze KeyConditionExpression

   The query filters items where 'Category' equals 'Books' using the GSI.

3. Final Answer:

   All items where the Category attribute equals 'Books' using the GSI -> Option D

4. Quick Check:

   Query with GSI filters by Category = 'Books' [OK]

Hint: Query with IndexName uses that index's keys [OK]

Common Mistakes:

• Assuming query filters primary key without IndexName
• Expecting error without primary key in main table
• Thinking query returns all items

4. You tried to query a DynamoDB table using a secondary index but got an error: ValidationException: Query condition missed key schema element. What is the most likely cause?

medium

A. You forgot to create the secondary index before querying

B. You used the primary key instead of the secondary index name

C. You did not specify the partition key attribute of the secondary index in the query

D. You used a Scan operation instead of Query

Solution

1. Step 1: Understand the error message

   The error means the query is missing a required key attribute from the index's key schema.

2. Step 2: Identify the missing key

   When querying a secondary index, you must specify its partition key attribute in the KeyConditionExpression.

3. Final Answer:

   You did not specify the partition key attribute of the secondary index in the query -> Option C

4. Quick Check:

   Missing index partition key causes ValidationException [OK]

Hint: Always include index partition key in query condition [OK]

Common Mistakes:

• Using primary key attributes instead of index keys
• Querying before index creation
• Confusing Scan with Query operation

5. You have a DynamoDB table with a primary key on UserId and a Global Secondary Index (GSI) on Email. You want to efficiently find users by their email address. Which approach best uses the GSI to achieve this?

hard

A. Query the table using the GSI with KeyConditionExpression 'Email = :emailValue'

B. Scan the entire table filtering items where Email equals the value

C. Query the table using the primary key UserId with the email value

D. Create a new table with Email as the primary key

Solution

1. Step 1: Identify the best way to find users by Email

   The GSI on Email allows querying by Email efficiently without scanning.

2. Step 2: Compare options

   Query the table using the GSI with KeyConditionExpression 'Email = :emailValue' uses the GSI query correctly. Scan the entire table filtering items where Email equals the value scans, which is slow. Query the table using the primary key UserId with the email value uses UserId, which won't help find by Email. Create a new table with Email as the primary key is unnecessary duplication.

3. Final Answer:

   Query the table using the GSI with KeyConditionExpression 'Email = :emailValue' -> Option A

4. Quick Check:

   Use GSI query for efficient Email lookup [OK]

Hint: Use GSI query, not scan or primary key, for alternate keys [OK]

Common Mistakes:

• Using Scan instead of Query on GSI
• Querying primary key with wrong attribute
• Creating redundant tables instead of indexes