Identifying access patterns first in DynamoDB - Time & Space Complexity

Time Complexity: Identifying access patterns first

O(n)

Understanding Time Complexity

When working with DynamoDB, knowing how you will access your data helps you understand how fast your queries will run.

We want to see how the number of operations changes as your data grows, based on your access patterns.

Scenario Under Consideration

Analyze the time complexity of this DynamoDB query using a primary key.

    const params = {
      TableName: "Users",
      KeyConditionExpression: "UserId = :id",
      ExpressionAttributeValues: {
        ":id": "12345"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code fetches all items with a specific UserId from the Users table.

Identify Repeating Operations

Look for repeated steps that affect performance.

• Primary operation: Reading items with the matching UserId.
• How many times: Once per matching item in the partition.

How Execution Grows With Input

As the number of items with the same UserId grows, the query takes longer.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of items matching the key.

Common Mistake

[X] Wrong: "Querying by primary key always takes the same time no matter how many items match."

[OK] Correct: The query time depends on how many items share the key; more items mean more work.

Interview Connect

Understanding how access patterns affect query speed shows you can design efficient databases and predict performance.

Self-Check

"What if we added a filter expression after the query? How would that affect the time complexity?"

Practice

1. Why is it important to identify access patterns before designing a DynamoDB table?

easy

A. Because it tells how many users will use the app.

B. Because it helps to choose the right programming language for the app.

C. Because access patterns determine the keys and indexes needed for efficient queries.

D. Because it decides the color scheme of the app interface.

Solution

1. Step 1: Understand the role of access patterns

   Access patterns describe how the app will retrieve data, which guides table design.

2. Step 2: Connect access patterns to keys and indexes

   Keys and indexes in DynamoDB are chosen based on these patterns to make queries fast and efficient.

3. Final Answer:

   Because access patterns determine the keys and indexes needed for efficient queries. -> Option C

4. Quick Check:

   Access patterns = keys/indexes choice [OK]

Hint: Access patterns guide key/index design for fast queries [OK]

Common Mistakes:

• Thinking access patterns affect UI design
• Confusing access patterns with user count
• Believing access patterns decide programming language

2. Which of the following is the correct way to describe an access pattern in DynamoDB?

easy

A. A list of all table columns.

B. A query that the app will run to get data.

C. The number of items in the table.

D. The size of the database backup.

Solution

1. Step 1: Define what an access pattern is

   An access pattern is a way the app queries or retrieves data from the database.

2. Step 2: Match the options to this definition

   Only "A query that the app will run to get data." describes a query the app will run, which fits the access pattern meaning.

3. Final Answer:

   A query that the app will run to get data. -> Option B

4. Quick Check:

   Access pattern = app query [OK]

Hint: Access pattern means how app queries data [OK]

Common Mistakes:

• Confusing access pattern with table schema
• Thinking access pattern is about data size
• Mixing access pattern with backup info

3. Given an app needs to get user orders by user ID and order date, which access pattern should be planned first?

medium

A. Query orders by user ID and sort by order date.

B. Scan all orders and filter by user ID.

C. Get orders by order date only.

D. Query orders by product ID.

Solution

1. Step 1: Identify the required data retrieval

   The app needs orders filtered by user ID and sorted by order date.

2. Step 2: Choose the access pattern matching this need

   Querying by user ID and sorting by order date matches the requirement and is efficient.

3. Final Answer:

   Query orders by user ID and sort by order date. -> Option A

4. Quick Check:

   Access pattern = query by user ID + order date [OK]

Hint: Match access pattern to app's data retrieval need [OK]

Common Mistakes:

• Using scan instead of query causes slow performance
• Ignoring sorting by order date
• Querying by unrelated keys like product ID

4. You designed a DynamoDB table without identifying access patterns first. Your app queries are slow. What is the likely cause?

medium

A. The table keys and indexes do not support the app's query needs.

B. The app has too many users.

C. The table has too many columns.

D. The app is using the wrong programming language.

Solution

1. Step 1: Understand the impact of missing access pattern planning

   Without access patterns, keys and indexes may not match query needs, causing slow queries.

2. Step 2: Eliminate unrelated causes

   User count, column number, or programming language do not directly cause slow DynamoDB queries.

3. Final Answer:

   The table keys and indexes do not support the app's query needs. -> Option A

4. Quick Check:

   Missing access patterns = wrong keys/indexes = slow queries [OK]

Hint: Slow queries often mean keys/indexes mismatch access patterns [OK]

Common Mistakes:

• Blaming app user count for query speed
• Thinking table columns affect query speed directly
• Assuming programming language affects DynamoDB speed

5. An app needs to retrieve customer profiles by email and also list all customers in a city. How should you identify access patterns to design the DynamoDB table?

hard

A. Store all customers in one table without keys and scan for queries.

B. Create separate tables for email and city queries.

C. Use email as the only key and ignore city queries.

D. Plan one access pattern to query by email and another to query by city using a secondary index.

Solution

1. Step 1: Identify the two access patterns

   The app needs to get customers by email and also list customers by city.

2. Step 2: Design keys and indexes accordingly

   Use email as the primary key and create a secondary index on city to support both queries efficiently.

3. Final Answer:

   Plan one access pattern to query by email and another to query by city using a secondary index. -> Option D

4. Quick Check:

   Multiple access patterns = primary key + secondary index [OK]

Hint: Use secondary indexes for multiple access patterns [OK]

Common Mistakes:

• Ignoring secondary indexes for city queries
• Using scans instead of queries
• Creating separate tables unnecessarily