Denormalization and when to use it in SQL - Time & Space Complexity

Time Complexity: Denormalization and when to use it

O(n)

Understanding Time Complexity

When we denormalize a database, we add extra copies of data to reduce the number of joins needed in queries.

We want to understand how this affects the time it takes to run queries as data grows.

Scenario Under Consideration

Analyze the time complexity of this query.

SELECT orders.id, orders.date, customers.name, customers.email
FROM orders
JOIN customers ON orders.customer_id = customers.id
WHERE orders.date > '2024-01-01';
    

This query fetches orders after a date, including customer details, using a join between two tables.

Identify Repeating Operations

Look at what repeats as data grows.

• Primary operation: Scanning orders and joining with customers.
• How many times: Once per order after the date filter.

How Execution Grows With Input

As the number of orders grows, the query checks more rows and joins more customers.

Input Size (orders)	Approx. Operations
10	About 10 order checks and joins
100	About 100 order checks and joins
1000	About 1000 order checks and joins

Pattern observation: The work grows roughly in direct proportion to the number of orders.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of orders.

Common Mistake

[X] Wrong: "Denormalization always makes queries faster with no downsides."

[OK] Correct: Denormalization can speed up reads but may slow down updates and increase storage, so it's a trade-off.

Interview Connect

Understanding when denormalization helps shows you can balance speed and data design, a key skill in real projects.

Self-Check

"What if we added more denormalized columns to avoid the join? How would the time complexity change for reads and writes?"

Practice

1. What is the main purpose of denormalization in a database?

easy

A. To split data into many small tables

B. To remove all duplicate data for storage efficiency

C. To enforce strict data integrity rules

D. To add redundant data to speed up read operations

Solution

1. Step 1: Understand denormalization goal and compare options

   Denormalization means adding repeated data to reduce complex joins and speed up reading. Only "To add redundant data to speed up read operations" describes adding redundant data to improve read speed, which matches denormalization.

2. Final Answer:

   To add redundant data to speed up read operations -> Option D

3. Quick Check:

   Denormalization = add redundant data for faster reads [OK]

Hint: Denormalization means adding data to read faster, not removing it [OK]

Common Mistakes:

• Confusing denormalization with normalization
• Thinking denormalization removes duplicates
• Believing denormalization enforces stricter rules

2. Which of the following best represents a denormalized table structure?

easy

A. Separate tables for customers and orders linked by customer_id

B. A table with repeated customer address fields in each order record

C. A table with only unique keys and no repeated data

D. A table with foreign keys but no repeated columns

Solution

1. Step 1: Identify denormalized structure and match to options

   Denormalized tables store repeated data, like customer address repeated in each order. "A table with repeated customer address fields in each order record" shows repeated fields in one table, which is denormalization. Others show normalized forms.

2. Final Answer:

   A table with repeated customer address fields in each order record -> Option B

3. Quick Check:

   Repeated fields in one table = denormalized [OK]

Hint: Look for repeated fields in one table to spot denormalization [OK]

Common Mistakes:

• Choosing normalized table structures
• Confusing foreign keys with denormalization
• Ignoring repeated data presence

3. Given a denormalized table Orders with columns OrderID, CustomerName, and CustomerAddress repeated in every row, what is a likely effect when updating a customer's address?

medium

A. You must update the address in every order row for that customer

B. Updating one row automatically updates all related rows

C. No update is needed because address is stored separately

D. The database prevents duplicate addresses

Solution

1. Step 1: Understand denormalized update effects and analyze options

   In denormalized tables, repeated data means updates must be applied to all copies to keep consistency. Only "You must update the address in every order row for that customer" correctly states that all rows must be updated manually.

2. Final Answer:

   You must update the address in every order row for that customer -> Option A

3. Quick Check:

   Repeated data requires multiple updates [OK]

Hint: Repeated data means multiple updates needed for consistency [OK]

Common Mistakes:

• Assuming one update changes all rows automatically
• Thinking address is stored separately in denormalized tables
• Believing database prevents duplicates in denormalized data

4. You have a denormalized table where customer phone numbers are repeated in many rows. You run this update:

UPDATE Orders SET CustomerPhone = '123-4567' WHERE CustomerID = 5;

but some rows still show old phone numbers. What is the most likely problem?

medium

A. The WHERE clause did not match all rows for CustomerID 5

B. Denormalization prevents updates to repeated data

C. CustomerPhone is a computed column and cannot be updated

D. The database automatically updates all rows, so this is impossible

Solution

1. Step 1: Analyze update query symptom and identify cause

   The update targets rows with CustomerID = 5, but some rows still have old data, meaning some rows were missed. Most likely, some rows have incorrect or missing CustomerID values, so the WHERE clause did not match them.

2. Final Answer:

   The WHERE clause did not match all rows for CustomerID 5 -> Option A

3. Quick Check:

   Update misses rows if WHERE condition is incomplete [OK]

Hint: Check WHERE clause matches all repeated rows in denormalized tables [OK]

Common Mistakes:

• Thinking denormalization blocks updates
• Assuming computed columns without checking
• Believing database auto-updates all duplicates

5. You want to speed up reporting queries that join Orders and Customers tables frequently. Which denormalization approach is best to improve read speed while managing data consistency?

hard

A. Remove customer details from Orders and query Customers each time

B. Keep separate tables and add more indexes on join keys

C. Add customer name and address columns directly into the Orders table

D. Duplicate Orders table for each customer

Solution

1. Step 1: Identify denormalization for faster reads and evaluate options

   Adding customer info directly into Orders reduces joins, speeding up queries. "Add customer name and address columns directly into the Orders table" adds repeated data for speed and requires careful updates, fitting denormalization best.

2. Final Answer:

   Add customer name and address columns directly into the Orders table -> Option C

3. Quick Check:

   Denormalize by adding repeated data to reduce joins [OK]

Hint: Denormalize by adding repeated fields to reduce joins for faster reads [OK]

Common Mistakes:

• Thinking indexing replaces denormalization
• Removing data increases joins and slows queries
• Duplicating entire tables causes complexity