Subqueries vs JOINs comparison in MySQL - Performance Comparison

Time Complexity: Subqueries vs JOINs comparison

O(n x m)

Understanding Time Complexity

When we use subqueries or JOINs in SQL, the way the database processes data can change how long it takes to get results.

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 find orders with customer details.

-- Using a subquery
SELECT order_id, customer_name
FROM orders
WHERE customer_id IN (
  SELECT customer_id FROM customers WHERE country = 'USA'
);

-- 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.country = 'USA';
    

Both queries get orders from customers in the USA but use different methods.

Identify Repeating Operations

Look at what repeats as data grows:

• Primary operation: Scanning and matching rows between orders and customers tables.
• How many times: For each order, the database checks matching customers (either via subquery or join).

How Execution Grows With Input

As the number of orders (n) and customers (m) grow, the work to find matches changes:

Input Size (orders n, customers m)	Approx. Operations
10, 10	About 100 checks
100, 100	About 10,000 checks
1000, 1000	About 1,000,000 checks

Pattern observation: The number of operations grows roughly with the product of the two table sizes.

Final Time Complexity

Time Complexity: O(n x m)

This means the time to run the query grows roughly with how many orders and customers there are multiplied together.

Common Mistake

[X] Wrong: "JOINs always run faster than subqueries because they look simpler."

[OK] Correct: Both can have similar time costs depending on indexes and data size; the database engine decides the best way to run them.

Interview Connect

Understanding how subqueries and JOINs scale helps you write efficient queries and explain your choices clearly in real projects and interviews.

Self-Check

What if we added an index on customer_id in both tables? How would the time complexity change?