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?"

Practice

1. Which DynamoDB index projection type copies all attributes from the base table to the index?

easy

A. ALL

B. KEYS_ONLY

C. INCLUDE

D. PARTIAL

Solution

1. Step 1: Understand projection types

   ALL copies every attribute from the base table to the index.

2. Step 2: Compare with other types

   KEYS_ONLY copies only keys; INCLUDE copies keys plus selected attributes.

3. Final Answer:

   ALL -> Option A

4. Quick Check:

   ALL = copies all attributes [OK]

Hint: ALL means every attribute is copied to the index [OK]

Common Mistakes:

• Confusing INCLUDE with ALL
• Thinking KEYS_ONLY copies all attributes
• Assuming PARTIAL is a valid projection type

2. Which of the following is the correct way to specify a KEYS_ONLY projection in a DynamoDB index definition?

easy

A. "ProjectionType": "ALL"

B. "ProjectionType": "KEYS_ONLY"

C. "ProjectionType": "INCLUDE"

D. "ProjectionType": "KEYS"

Solution

1. Step 1: Recall correct syntax for KEYS_ONLY

   The projection type must be exactly "KEYS_ONLY" in quotes.

2. Step 2: Eliminate incorrect options

   ALL and INCLUDE are valid but not KEYS_ONLY; "KEYS" is invalid syntax.

3. Final Answer:

   "ProjectionType": "KEYS_ONLY" -> Option B

4. Quick Check:

   KEYS_ONLY syntax = "KEYS_ONLY" [OK]

Hint: Use exact string "KEYS_ONLY" for keys-only projection [OK]

Common Mistakes:

• Using "KEYS" instead of "KEYS_ONLY"
• Confusing INCLUDE with KEYS_ONLY syntax
• Omitting quotes around projection type

3. Given a DynamoDB table with attributes id, name, age, and city, and a Global Secondary Index (GSI) with projection type INCLUDE and non-key attributes age and city, which attributes will be available in the index?

medium

A. id, age, and city

B. id, name, age, and city

C. Only age and city

D. Only id and name

Solution

1. Step 1: Identify keys and included attributes

   Index always includes keys; INCLUDE adds specified non-key attributes.

2. Step 2: Determine which attributes are keys

   Assuming id is the partition key, name is not a key.

3. Step 3: Combine keys and included attributes

   Index has id (key), plus age and city (included).

4. Final Answer:

   id, age, and city -> Option A

5. Quick Check:

   INCLUDE = keys + chosen attributes [OK]

Hint: INCLUDE = keys plus only specified extra attributes [OK]

Common Mistakes:

• Including non-key attributes not specified in INCLUDE
• Assuming all attributes are included
• Confusing keys with non-key attributes

4. You defined a DynamoDB index with projection type INCLUDE but forgot to specify any non-key attributes. What will happen when you try to create this index?

medium

A. The index will include keys plus all attributes by default.

B. The index will include only the keys, ignoring INCLUDE.

C. The index will include all attributes from the base table.

D. The index creation will fail with a validation error.

Solution

1. Step 1: Understand INCLUDE projection requirements

   INCLUDE requires specifying at least one non-key attribute.

2. Step 2: Check behavior when no attributes specified

   Omitting non-key attributes causes a validation error during index creation.

3. Final Answer:

   The index creation will fail with a validation error. -> Option D

4. Quick Check:

   INCLUDE needs attributes; missing causes error [OK]

Hint: INCLUDE must list attributes; empty list causes error [OK]

Common Mistakes:

• Assuming INCLUDE defaults to ALL attributes
• Thinking index silently defaults to KEYS_ONLY
• Ignoring validation errors on index creation

5. You want to optimize a DynamoDB Global Secondary Index (GSI) to reduce storage costs but still need to query by email and retrieve phone and address attributes quickly. Which projection type should you choose?

hard

A. ALL

B. KEYS_ONLY

C. INCLUDE with phone and address

D. INCLUDE with email only

Solution

1. Step 1: Understand storage cost vs attribute needs

   ALL copies all attributes but costs more storage; KEYS_ONLY copies only keys.

2. Step 2: Identify needed attributes for queries

   You need email as key and phone, address for quick retrieval.

3. Step 3: Choose INCLUDE projection with needed attributes

   INCLUDE lets you copy keys plus only phone and address, saving storage.

4. Final Answer:

   INCLUDE with phone and address -> Option C

5. Quick Check:

   INCLUDE = keys + needed attributes saves cost [OK]

Hint: Use INCLUDE to add only needed attributes, saving space [OK]

Common Mistakes:

• Choosing ALL and increasing storage unnecessarily
• Using KEYS_ONLY and missing needed attributes
• Including only email but not phone or address