Creating GSI in DynamoDB - Performance & Efficiency

Time Complexity: Creating GSI

O(n)

Understanding Time Complexity

When we create a Global Secondary Index (GSI) in DynamoDB, we want to know how the time to build and use it changes as data grows.

We ask: How does the work increase when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB GSI creation snippet.

    UpdateTable {
      TableName: "Orders",
      AttributeDefinitions: [
        { AttributeName: "OrderId", AttributeType: "S" },
        { AttributeName: "CustomerId", AttributeType: "S" }
      ],
      GlobalSecondaryIndexes: [{
        IndexName: "CustomerIndex",
        KeySchema: [{ AttributeName: "CustomerId", KeyType: "HASH" }],
        Projection: { ProjectionType: "ALL" }
      }]
    }
    

This code adds a GSI on CustomerId to the Orders table to allow fast queries by customer.

Identify Repeating Operations

Look for repeated work during GSI creation and usage.

• Primary operation: Scanning or writing each item to the GSI.
• How many times: Once per item in the main table, as each item is copied or indexed.

How Execution Grows With Input

As the number of items grows, the work to build and maintain the GSI grows too.

Input Size (n)	Approx. Operations
10	10 writes to GSI
100	100 writes to GSI
1000	1000 writes to GSI

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

Final Time Complexity

Time Complexity: O(n)

This means the time to create and update the GSI grows linearly with the number of items.

Common Mistake

[X] Wrong: "Creating a GSI is instant and does not depend on table size."

[OK] Correct: Each item must be processed to build the GSI, so more items mean more work and time.

Interview Connect

Understanding how GSI creation scales helps you explain database design choices clearly and confidently.

Self-Check

"What if we added multiple GSIs? How would the time complexity change?"