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?