Index projection types (ALL, KEYS_ONLY, INCLUDE) in DynamoDB - Time & Space Complexity

Time Complexity: Index projection types (ALL, KEYS_ONLY, INCLUDE)

O(n)

Understanding Time Complexity

When using DynamoDB indexes, how fast queries run depends on what data the index holds.

We want to see how the choice of projection type affects query speed as data grows.

Scenario Under Consideration

Analyze the time complexity of querying a Global Secondary Index with different projection types.

    QueryRequest queryRequest = new QueryRequest()
        .withTableName("Orders")
        .withIndexName("CustomerIndex")
        .withKeyConditionExpression("CustomerId = :cid")
        .withExpressionAttributeValues(Map.of(":cid", new AttributeValue().withS("123")));
    
    QueryResult result = dynamoDB.query(queryRequest);
    

This code queries an index that projects data using ALL, KEYS_ONLY, or INCLUDE types.

Identify Repeating Operations

Look at what happens repeatedly during the query.

• Primary operation: Reading each matching item's projected attributes from the index.
• How many times: Once per matching item returned by the query.

How Execution Grows With Input

As more items match the query, more data is read from the index.

Input Size (n)	Approx. Operations
10	Read 10 items with projected attributes
100	Read 100 items with projected attributes
1000	Read 1000 items with projected attributes

Pattern observation: The time grows linearly with the number of matching items.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows directly with how many items the index returns.

Common Mistake

[X] Wrong: "Choosing ALL projection always makes queries faster because all data is in the index."

[OK] Correct: Reading more data per item can slow queries, so ALL projection may increase read time compared to KEYS_ONLY or INCLUDE.

Interview Connect

Understanding how index projection affects query speed helps you design efficient databases and answer questions about scaling data access.

Self-Check

"What if the index projection changed from KEYS_ONLY to INCLUDE with several attributes? How would the time complexity change when querying many items?"