Key-value and document store model in DynamoDB - Time & Space Complexity

Time Complexity: Key-value and document store model

O(1)

Understanding Time Complexity

When using DynamoDB's key-value and document store model, it's important to understand how the time to get or put data changes as the amount of data grows.

We want to know: How does the time to find or save an item change when the database gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB GetItem operation.

    const params = {
      TableName: "Users",
      Key: { "UserId": "12345" }
    };
    
    dynamodb.get(params, function(err, data) {
      if (err) console.log(err);
      else console.log(data.Item);
    });
    

This code fetches a single user item by its unique key from the DynamoDB table.

Identify Repeating Operations

In this example, there are no loops or repeated scans over multiple items.

• Primary operation: Direct lookup by key.
• How many times: Exactly once per request.

How Execution Grows With Input

Because DynamoDB uses a key to directly find the item, the time to get the item stays about the same no matter how many items are in the table.

Input Size (n)	Approx. Operations
10	1 lookup
100	1 lookup
1000	1 lookup

Pattern observation: The number of operations does not increase as the table grows.

Final Time Complexity

Time Complexity: O(1)

This means the time to get an item by key stays constant, no matter how big the database is.

Common Mistake

[X] Wrong: "Getting an item by key takes longer as the table gets bigger because there are more items to look through."

[OK] Correct: DynamoDB uses an index on the key to jump directly to the item, so it does not scan through all items.

Interview Connect

Understanding that key-value lookups are constant time helps you explain how databases handle large data efficiently. This skill shows you know how data retrieval scales in real systems.

Self-Check

"What if we used a Scan operation instead of GetItem? How would the time complexity change?"

Practice

1. What is the main feature of a key-value store in DynamoDB?

easy

A. It uses a unique key to quickly find data.

B. It requires complex joins between tables.

C. It stores data only in fixed columns.

D. It only supports relational data models.

Solution

1. Step 1: Understand key-value store basics

   A key-value store uses a unique key to store and retrieve data quickly without complex relations.

2. Step 2: Compare options with key-value features

   Options A, C, and D describe relational or fixed schema models, not key-value stores.

3. Final Answer:

   It uses a unique key to quickly find data. -> Option A

4. Quick Check:

   Key-value store = unique key fast access [OK]

Hint: Key-value means unique key for fast lookup [OK]

Common Mistakes:

• Confusing key-value with relational databases
• Thinking key-value needs fixed columns
• Assuming key-value supports joins

2. Which of the following is the correct way to define a composite primary key in a DynamoDB table?

easy

A. PrimaryKey: { PartitionKey: 'UserId', SortKey: 'Timestamp' }

B. PrimaryKey = UserId, SortKey = Timestamp

C. PrimaryKey: { PartitionKey: 'UserId' }

D. PrimaryKey: UserId, ForeignKey: Timestamp

Solution

1. Step 1: Recall DynamoDB primary key syntax

   DynamoDB primary key can be simple (partition key) or composite (partition + sort key) defined as an object with keys PartitionKey and SortKey.

2. Step 2: Check each option's syntax

   PrimaryKey: { PartitionKey: 'UserId', SortKey: 'Timestamp' } correctly shows both PartitionKey and SortKey in an object. PrimaryKey: { PartitionKey: 'UserId' } misses SortKey, B uses wrong assignment syntax, D uses ForeignKey which is invalid in DynamoDB.

3. Final Answer:

   PrimaryKey: { PartitionKey: 'UserId', SortKey: 'Timestamp' } -> Option A

4. Quick Check:

   Primary key = PartitionKey + SortKey object [OK]

Hint: Primary key uses PartitionKey and optional SortKey keys [OK]

Common Mistakes:

• Using equal sign instead of colon in definitions
• Confusing foreign key with sort key
• Omitting sort key when needed

3. Given a DynamoDB table with items: {UserId: '123', Name: 'Alice'}, {UserId: '456', Name: 'Bob'}, what will the query return if you request the item with UserId '123'?

medium

A. [{UserId: '456', Name: 'Bob'}]

B. Error: Item not found

C. []

D. [{UserId: '123', Name: 'Alice'}]

Solution

1. Step 1: Understand query by primary key

   Querying by UserId '123' returns the item with that key if it exists.

2. Step 2: Match UserId '123' in given items

   The item {UserId: '123', Name: 'Alice'} matches the query.

3. Final Answer:

   [{UserId: '123', Name: 'Alice'}] -> Option D

4. Quick Check:

   Query by key returns matching item [OK]

Hint: Query by key returns exact matching item [OK]

Common Mistakes:

• Expecting multiple items for a unique key
• Confusing query result with scan result
• Assuming error if item not found instead of empty

4. You wrote this DynamoDB query but it returns no results: Table.query(KeyConditionExpression='UserId = :uid', ExpressionAttributeValues={':uid': '789'}). What is the likely problem?

medium

A. KeyConditionExpression must use '==' instead of '='.

B. ExpressionAttributeValues should not use colons in keys.

C. The key name 'UserId' is incorrect or missing in the table.

D. Query requires a ScanIndexForward parameter.

Solution

1. Step 1: Check key name correctness

   If the key name 'UserId' does not exist or is misspelled in the table schema, the query returns no results.

2. Step 2: Validate syntax and parameters

   Using ':' in ExpressionAttributeValues keys is correct. '=' is valid in KeyConditionExpression. ScanIndexForward is optional for sorting, not required for results.

3. Final Answer:

   The key name 'UserId' is incorrect or missing in the table. -> Option C

4. Quick Check:

   Correct key name needed for query success [OK]

Hint: Check key names match table schema exactly [OK]

Common Mistakes:

• Removing colons from ExpressionAttributeValues keys
• Using '==' instead of '=' in expressions
• Adding unnecessary parameters

5. You want to store user profiles with flexible nested data like addresses and preferences in DynamoDB. Which model best fits this need?

hard

A. Use a relational model with multiple tables and foreign keys.

B. Use a document store model to save JSON-like nested objects.

C. Use a key-value store with only simple string values.

D. Use a graph database to store nested user data.

Solution

1. Step 1: Identify data flexibility needs

   Nested and flexible data like addresses and preferences require a document model that supports JSON-like structures.

2. Step 2: Match model to DynamoDB capabilities

   DynamoDB supports document store model allowing nested objects. Relational and graph models are not native to DynamoDB. Simple key-value stores do not support nested data well.

3. Final Answer:

   Use a document store model to save JSON-like nested objects. -> Option B

4. Quick Check:

   Nested data = document store model [OK]

Hint: Nested JSON data fits document store model best [OK]

Common Mistakes:

• Choosing relational model for flexible nested data
• Assuming key-value stores handle nested objects well
• Confusing graph databases with DynamoDB