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?"

Practice

1. Which statement best describes the performance difference between a JOIN and a subquery in SQL?

easy

A. JOINs generally perform better because they combine tables in a single step.

B. Subqueries always perform better because they run separately.

C. JOINs and subqueries have the same performance in all cases.

D. Subqueries are faster because they use less memory.

Solution

1. Step 1: Understand how JOINs work

   JOINs combine rows from two or more tables in one operation, which is often optimized by the database engine.

2. Step 2: Compare with subqueries

   Subqueries run separately and then feed results to the main query, which can be slower especially with large data.

3. Final Answer:

   JOINs generally perform better because they combine tables in a single step. -> Option A

4. Quick Check:

   JOIN performance > Subquery performance [OK]

Hint: JOINs usually run faster than subqueries [OK]

Common Mistakes:

• Thinking subqueries always run faster
• Assuming JOINs and subqueries are always equal
• Believing subqueries use less memory

2. Which of the following SQL queries correctly uses a JOIN to get all customers and their orders?

easy

A. SELECT customers.name, orders.id FROM customers JOIN orders ON customers.id = orders.customer_id;

B. SELECT customers.name, orders.id FROM customers WHERE customers.id = orders.customer_id;

C. SELECT customers.name, orders.id FROM customers, orders WHERE customers.id == orders.customer_id;

D. SELECT customers.name, orders.id FROM customers JOIN orders ON customers.customer_id = orders.id;

Solution

1. Step 1: Check JOIN syntax

   Correct JOIN syntax uses ON with matching keys: customers.id = orders.customer_id.

2. Step 2: Validate each option

   SELECT customers.name, orders.id FROM customers JOIN orders ON customers.id = orders.customer_id; uses correct JOIN and ON condition. SELECT customers.name, orders.id FROM customers WHERE customers.id = orders.customer_id; uses WHERE without JOIN, which is invalid here. SELECT customers.name, orders.id FROM customers, orders WHERE customers.id == orders.customer_id; uses double equals (==) which is invalid in SQL. SELECT customers.name, orders.id FROM customers JOIN orders ON customers.customer_id = orders.id; reverses keys incorrectly.

3. Final Answer:

   SELECT customers.name, orders.id FROM customers JOIN orders ON customers.id = orders.customer_id; -> Option A

4. Quick Check:

   Correct JOIN syntax = SELECT customers.name, orders.id FROM customers JOIN orders ON customers.id = orders.customer_id; [OK]

Hint: JOIN uses ON with matching keys, not WHERE or == [OK]

Common Mistakes:

• Using WHERE instead of ON for JOIN condition
• Using == instead of = in SQL
• Mixing up key columns in ON clause

3. Given the tables employees(id, name) and departments(id, name, manager_id), what will this query return?

SELECT e.name FROM employees e WHERE e.id IN (SELECT d.manager_id FROM departments d);

medium

A. Syntax error due to subquery.

B. Names of all employees regardless of department.

C. Names of employees who are not managers.

D. Names of employees who are managers of any department.

Solution

1. Step 1: Understand the subquery

   The subquery SELECT d.manager_id FROM departments d returns all manager IDs from departments.

2. Step 2: Analyze the main query

   The main query selects employee names where their ID is in the list of manager IDs, so it returns employees who manage departments.

3. Final Answer:

   Names of employees who are managers of any department. -> Option D

4. Quick Check:

   Subquery filters managers = Names of employees who are managers of any department. [OK]

Hint: IN with subquery filters matching IDs [OK]

Common Mistakes:

• Thinking it returns all employees
• Confusing managers with non-managers
• Assuming syntax error in subquery

4. Identify the error in this SQL query that uses a JOIN:

SELECT c.name, o.amount FROM customers c JOIN orders o WHERE c.id = o.customer_id;

medium

A. Incorrect table aliases used.

B. Using WHERE instead of HAVING for condition.

C. Missing ON keyword before join condition.

D. No error; query is correct.

Solution

1. Step 1: Review JOIN syntax

   JOIN requires an ON clause to specify join condition, not WHERE.

2. Step 2: Check the query

   The query uses WHERE for join condition, which is incorrect syntax for explicit JOIN.

3. Final Answer:

   Missing ON keyword before join condition. -> Option C

4. Quick Check:

   JOIN needs ON, not WHERE [OK]

Hint: JOIN must have ON clause for conditions [OK]

Common Mistakes:

• Using WHERE instead of ON for JOIN
• Confusing HAVING with WHERE
• Assuming aliases cause error

5. You want to list all products and their category names. The products table has category_id, and the categories table has id and name. Which approach is better for performance and why?

Options:
A) Use a JOIN to combine products and categories.
B) Use a subquery in SELECT to get category name for each product.
C) Use a subquery in WHERE to filter products by category name.
D) Use UNION to combine products and categories.

hard

A. Subquery in SELECT is better because it runs once per product.

B. JOIN is better because it retrieves all data in one step efficiently.

C. Subquery in WHERE is better because it filters early.

D. UNION is better because it merges tables.

Solution

1. Step 1: Understand the data retrieval goal

   You want product info with category names, which requires combining data from two tables.

2. Step 2: Compare approaches

   JOIN combines tables in one efficient operation. Subqueries in SELECT run once per row, causing slower performance. Subquery in WHERE filters but doesn't retrieve category names. UNION merges rows, not related here.

3. Final Answer:

   JOIN is better because it retrieves all data in one step efficiently. -> Option B

4. Quick Check:

   JOIN efficiency > subqueries for this task [OK]

Hint: JOIN combines tables efficiently for related data [OK]

Common Mistakes:

• Using subquery in SELECT causing slow per-row lookup
• Confusing UNION with JOIN
• Using subquery in WHERE without retrieving needed data