Sparse index pattern in DynamoDB - Time & Space Complexity

Time Complexity: Sparse index pattern

O(m)

Understanding Time Complexity

When using a sparse index in DynamoDB, we want to know how the time to find data changes as the data grows.

We ask: How does the search time grow when the table and index get bigger?

Scenario Under Consideration

Analyze the time complexity of this sparse index query.

    const params = {
      TableName: "Orders",
      IndexName: "StatusIndex", // sparse index on 'status'
      KeyConditionExpression: "status = :s",
      ExpressionAttributeValues: {
        ":s": "SHIPPED"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries only items with status "SHIPPED" using a sparse index that stores only those items.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Scanning the sparse index entries matching the status.
• How many times: Once per matching item in the sparse index, not the whole table.

How Execution Grows With Input

As the number of items with status "SHIPPED" grows, the query takes longer.

Input Size (n)	Approx. Operations
10 shipped items	10 reads
100 shipped items	100 reads
1000 shipped items	1000 reads

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

Final Time Complexity

Time Complexity: O(m)

This means the query time grows in direct proportion to the number of items matching the sparse index condition.

Common Mistake

[X] Wrong: "Querying a sparse index is as slow as scanning the whole table."

[OK] Correct: The sparse index only contains items with the indexed attribute, so the query touches fewer items, making it faster.

Interview Connect

Understanding sparse indexes helps you explain how to efficiently query subsets of data, a useful skill in real projects.

Self-Check

"What if the sparse index included multiple attributes for filtering? How would that affect the time complexity?"

Practice

1. What is the main benefit of using a sparse index pattern in DynamoDB?

easy

A. It indexes all items regardless of attributes, increasing storage.

B. It indexes only items with a specific attribute, making queries faster and cheaper.

C. It duplicates all data to another table for backup.

D. It automatically deletes items without a key attribute.

Solution

1. Step 1: Understand sparse index purpose

   Sparse index only includes items that have the indexed attribute, skipping others.

2. Step 2: Identify benefit of selective indexing

   This selective indexing reduces query cost and speeds up queries for that subset.

3. Final Answer:

   It indexes only items with a specific attribute, making queries faster and cheaper. -> Option B

4. Quick Check:

   Sparse index = selective fast queries [OK]

Hint: Sparse index targets only items with the attribute [OK]

Common Mistakes:

• Thinking sparse index includes all items
• Confusing sparse index with full table scan
• Assuming sparse index duplicates data

2. Which of the following is the correct way to define a sparse index in DynamoDB?

easy

A. Create a Global Secondary Index (GSI) with a partition key only on items having the attribute.

B. Create a Local Secondary Index (LSI) on all items regardless of attribute presence.

C. Create a GSI with a partition key that is always null.

D. Create a GSI with a partition key that duplicates the primary key.

Solution

1. Step 1: Identify sparse index creation method

   Sparse indexes use GSIs with keys only on items having the attribute.

2. Step 2: Check options for correctness

   Create a Global Secondary Index (GSI) with a partition key only on items having the attribute. matches this method; others either index all items or use invalid keys.

3. Final Answer:

   Create a Global Secondary Index (GSI) with a partition key only on items having the attribute. -> Option A

4. Quick Check:

   Sparse index = GSI with selective keys [OK]

Hint: Sparse index uses GSI with keys only on some items [OK]

Common Mistakes:

• Confusing LSI with sparse index
• Using null keys in GSI partition key
• Duplicating primary key in GSI

3. Given a DynamoDB table with items where only some have attribute status, and a sparse GSI on status, what will this query return?

Query on GSI where status = 'active'

medium

A. Only items without the status attribute.

B. All items in the table regardless of status.

C. All items in the table with status 'active'.

D. An error because status is not a primary key.

Solution

1. Step 1: Understand sparse GSI query behavior

   The sparse GSI includes only items with the status attribute, so querying status='active' returns those items.

2. Step 2: Eliminate incorrect options

   All items in the table regardless of status. is wrong because items without status are not in GSI; C is wrong because query targets status='active'; D is wrong because GSI keys can be queried.

3. Final Answer:

   All items in the table with status 'active'. -> Option C

4. Quick Check:

   Query sparse GSI = items with attribute value [OK]

Hint: Query sparse GSI returns only items with that attribute [OK]

Common Mistakes:

• Expecting all table items in result
• Thinking query fails without primary key
• Confusing sparse index with full scan

4. You created a sparse GSI on attribute category, but your query returns no results even though items have category. What is a likely cause?

medium

A. Sparse indexes do not support queries.

B. The table has no items at all.

C. You queried the base table instead of the GSI.

D. The GSI partition key is not set to category.

Solution

1. Step 1: Check GSI key configuration

   If the GSI partition key is not category, the index won't include those items properly.

2. Step 2: Evaluate other options

   Table having no items is unlikely if items exist; querying base table returns items but not via GSI; sparse indexes do support queries.

3. Final Answer:

   The GSI partition key is not set to category. -> Option D

4. Quick Check:

   Wrong GSI key = no results [OK]

Hint: Check GSI partition key matches attribute queried [OK]

Common Mistakes:

• Querying base table instead of GSI
• Assuming sparse index can't be queried
• Ignoring GSI key setup

5. You want to quickly find all orders with a deliveryDate attribute set, but most orders don't have this attribute. How can you use a sparse index pattern to optimize queries?

hard

A. Create a GSI with deliveryDate as the partition key; only orders with this attribute appear in the index.

B. Add deliveryDate as a sort key in the main table to speed up queries.

C. Create a GSI with a constant partition key for all items and deliveryDate as sort key.

D. Scan the entire table filtering on deliveryDate attribute.

Solution

1. Step 1: Use sparse index with deliveryDate attribute

   Creating a GSI with deliveryDate as partition key includes only items having that attribute, making queries efficient.

2. Step 2: Evaluate other options

   A constant partition key approach requires adding an extra attribute to all items, incurring write costs; main table sort key doesn't filter missing attributes; full table scan is inefficient.

3. Final Answer:

   Create a GSI with deliveryDate as the partition key; only orders with this attribute appear in the index. -> Option A

4. Quick Check:

   Sparse GSI on attribute = fast filtered queries [OK]

Hint: Sparse GSI on attribute filters only items having it [OK]

Common Mistakes:

• Using scan instead of sparse index
• Indexing all items losing sparsity
• Misusing sort key for filtering