Denormalization for speed in Redis - Time & Space Complexity

Time Complexity: Denormalization for speed

O(n)

Understanding Time Complexity

Denormalization means storing data in a way that avoids extra lookups. This helps speed up reading data in Redis.

We want to see how the time to get data changes when we use denormalization.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands for fetching user info.

# Normalized approach
HGETALL user:1000
HGETALL profile:1000

# Denormalized approach
HGETALL user_profile:1000
    

This code shows fetching user data from two hashes separately versus one combined hash.

Identify Repeating Operations

Look at what repeats when fetching data.

• Primary operation: Reading hash fields with HGETALL.
• How many times: Normalized reads two hashes separately; denormalized reads one combined hash once.

How Execution Grows With Input

As the number of fields grows, the time to read grows too.

Input Size (fields)	Normalized Reads (2 hashes)	Denormalized Read (1 hash)
10	~20 field reads	~10 field reads
100	~200 field reads	~100 field reads
1000	~2000 field reads	~1000 field reads

Pattern observation: Normalized approach doubles the work because it reads two hashes; denormalized reads once, so work grows linearly with fields.

Final Time Complexity

Time Complexity: O(n)

This means the time to read data grows directly with the number of fields you fetch.

Common Mistake

[X] Wrong: "Denormalization always makes data fetching instant regardless of size."

[OK] Correct: Even with denormalization, reading more fields takes more time because Redis reads each field once.

Interview Connect

Understanding how denormalization affects read speed helps you design fast Redis queries and shows you think about real-world data access patterns.

Self-Check

"What if we split the denormalized hash into three smaller hashes instead of one big one? How would the time complexity change?"

Practice

1. What is the main benefit of denormalization in Redis?

easy

A. Faster data retrieval by storing related data together

B. Reducing memory usage by splitting data into many keys

C. Ensuring data is always normalized for consistency

D. Automatically backing up data to disk

Solution

1. Step 1: Understand denormalization purpose

   Denormalization means storing related data together to avoid multiple lookups.

2. Step 2: Identify main benefit in Redis context

   This reduces the number of Redis calls, making data retrieval faster.

3. Final Answer:

   Faster data retrieval by storing related data together -> Option A

4. Quick Check:

   Denormalization = Faster access [OK]

Hint: Denormalization means fewer lookups, so speed improves [OK]

Common Mistakes:

• Confusing denormalization with normalization
• Thinking it reduces memory usage
• Assuming it automatically backs up data

2. Which Redis data structure is best suited for denormalization to store related user info together?

easy

A. Hash

B. List

C. Set

D. Sorted Set

Solution

1. Step 1: Review Redis data structures

   Lists store ordered values, Sets store unique unordered values, Sorted Sets store ordered unique values, Hashes store field-value pairs.

2. Step 2: Choose structure for related fields

   Hashes allow storing multiple fields (like name, email) under one key, ideal for denormalized user info.

3. Final Answer:

   Hash -> Option A

4. Quick Check:

   Hash = field-value pairs for related data [OK]

Hint: Use Hash for grouped related fields in one key [OK]

Common Mistakes:

• Choosing List which is just ordered values
• Using Set which stores unique values without fields
• Picking Sorted Set which is for ordered unique elements

3. Given these Redis commands for denormalized user data:

HSET user:1000 name "Alice" age 30 city "NY"

What does HGETALL user:1000 return?

medium

A. ["name", "Alice", "age", "30"]

B. ["name", "Alice", "age", "30", "city", "NY"]

C. ["name", "Alice", "age", 30, "city", "NY"]

D. ["user:1000", "Alice", "30", "NY"]

Solution

1. Step 1: Understand HSET command

   HSET stores fields and values under key 'user:1000' as strings: name=Alice, age=30, city=NY.

2. Step 2: Understand HGETALL output format

   HGETALL returns an array of field-value pairs as strings in order stored.

3. Final Answer:

   ["name", "Alice", "age", "30", "city", "NY"] -> Option B

4. Quick Check:

   HGETALL returns all fields and values as strings [OK]

Hint: HGETALL returns flat list of field-value strings [OK]

Common Mistakes:

• Expecting numeric types instead of strings
• Confusing key name with fields
• Partial field-value pairs returned

4. You try to denormalize user data with:

HSET user:2000 name "Bob" age 25 city "LA"

But later HGET user:2000 age returns nil. What is the likely cause?

medium

A. HSET command was not executed properly

B. The field name is misspelled in HGET

C. The age field was overwritten or deleted

D. The key user:2000 does not exist

Solution

1. Step 1: Check if key exists

   If key did not exist, all fields would be missing, but only age is missing.

2. Step 2: Consider field deletion or overwrite

   Age field might have been deleted or overwritten after initial HSET, causing nil return.

3. Final Answer:

   The age field was overwritten or deleted -> Option C

4. Quick Check:

   Missing field means deleted or overwritten [OK]

Hint: Missing field usually means it was deleted or overwritten [OK]

Common Mistakes:

• Assuming key does not exist when other fields exist
• Misspelling field name in HGET
• Thinking HSET failed without error

5. You want to speed up a Redis app by denormalizing product and category data. Which approach is best?

hard

A. Use a sorted set for categories and a list for products

B. Store product and category in separate keys and join at runtime

C. Normalize data fully to avoid duplication

D. Store product info and category name together in one hash key per product

Solution

1. Step 1: Understand denormalization goal

   Denormalization stores related data together to reduce lookups and speed access.

2. Step 2: Evaluate options for product-category data

   Storing product info and category name together in one hash avoids extra lookups, speeding queries.

3. Step 3: Compare other options

   Separate keys require joins (slower), sorted sets/lists don't group related fields, full normalization slows access.

4. Final Answer:

   Store product info and category name together in one hash key per product -> Option D

5. Quick Check:

   Denormalize related data together for speed [OK]

Hint: Put related data in one hash to avoid joins [OK]

Common Mistakes:

• Keeping data normalized causing slow joins
• Using sorted sets/lists without grouping fields
• Duplicating data without grouping properly