Subquery vs JOIN performance trade-off in SQL - Performance Comparison

Time Complexity: Subquery vs JOIN performance trade-off

O(n * m)

Understanding Time Complexity

When working with databases, we often choose between subqueries and JOINs to combine data from tables.

We want to understand how the time to run these queries grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of these two queries that get orders with customer info.

-- Using a subquery
SELECT order_id, customer_name
FROM orders
WHERE customer_id IN (SELECT customer_id FROM customers WHERE active = 1);

-- Using a JOIN
SELECT o.order_id, c.customer_name
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id
WHERE c.active = 1;
    

Both queries find orders from active customers, but use different ways to combine tables.

Identify Repeating Operations

Look at what repeats as data grows:

• Primary operation: Checking each order against customers.
• How many times: Once for each order row, plus scanning customers.

How Execution Grows With Input

As the number of orders and customers grows, the work increases.

Input Size (orders n)	Approx. Operations
10	About 10 checks plus customer scans
100	About 100 checks plus customer scans
1000	About 1000 checks plus customer scans

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

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly by multiplying the number of orders (n) by the number of customers (m).

Common Mistake

[X] Wrong: "JOINs are always faster than subqueries."

[OK] Correct: Sometimes subqueries can be optimized by the database to run as fast or faster, depending on indexes and query structure.

Interview Connect

Understanding how query time grows helps you write better database code and explain your choices clearly in conversations.

Self-Check

"What if we add an index on customer_id in both tables? How would that affect the time complexity?"