Why normalization matters in SQL - Performance Analysis

Time Complexity: Why normalization matters

O(n)

Understanding Time Complexity

When we organize data in a database, the way we arrange it affects how fast queries run.

We want to see how the structure of data impacts the work needed to get answers.

Scenario Under Consideration

Analyze the time complexity of the following SQL query on a normalized vs denormalized table.

-- Denormalized table example
SELECT customer_name, order_id, product_name
FROM orders
WHERE customer_id = 123;

-- Normalized tables example
SELECT c.customer_name, o.order_id, p.product_name
FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
JOIN products p ON o.product_id = p.product_id
WHERE c.customer_id = 123;
    

This code fetches customer orders and product details either from one big table or by joining smaller tables.

Identify Repeating Operations

Look at what repeats as data grows.

• Primary operation: Scanning rows and joining tables.
• How many times: Once per matching row in orders.

How Execution Grows With Input

As the number of orders grows, the work to find matching rows grows too.

Input Size (orders)	Approx. Operations
10	About 10 row checks
100	About 100 row checks
1000	About 1000 row checks

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 get results grows linearly as the number of rows grows.

Common Mistake

[X] Wrong: "Joining tables always makes queries slower than using one big table."

[OK] Correct: Normalized tables can reduce repeated data and make searches faster by focusing on smaller sets of data.

Interview Connect

Understanding how data layout affects query speed shows you know how to build efficient databases that grow well.

Self-Check

"What if we added indexes on the join columns? How would the time complexity change?"