Why subqueries are needed in SQL - Performance Analysis

Time Complexity: Why subqueries are needed

O(n + m)

Understanding Time Complexity

We want to understand how the time needed to run a query changes when it uses subqueries.

How does adding a subquery affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_id, name
FROM employees
WHERE department_id IN (
  SELECT department_id
  FROM departments
  WHERE location = 'New York'
);

This query finds employees who work in departments located in New York using a subquery.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database first runs the subquery to find matching departments.
• How many times: The subquery runs once, then the main query checks each employee against the subquery results.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 employees, 3 departments	Runs subquery once (3 results), checks 10 employees
100 employees, 10 departments	Runs subquery once (10 results), checks 100 employees
1000 employees, 50 departments	Runs subquery once (50 results), checks 1000 employees

Pattern observation: The subquery runs once, then the main query work grows with the number of employees.

Final Time Complexity

Time Complexity: O(n + m)

This means the total work grows roughly with the size of both the subquery results and the main query rows.

Common Mistake

[X] Wrong: "The subquery runs for every employee row."

[OK] Correct: The database usually runs the subquery once and reuses its results, so it does not repeat the subquery many times.

Interview Connect

Understanding how subqueries affect query time helps you write clear and efficient database queries, a useful skill in many real projects.

Self-Check

"What if the subquery returned a very large list? How would that change the time complexity?"

Practice

1. Why do we use subqueries in SQL?
SELECT * FROM employees WHERE department_id IN (SELECT id FROM departments WHERE location = 'NY');

easy

A. To use the result of one query inside another for filtering or comparison

B. To speed up the database server automatically

C. To create new tables from existing ones

D. To change the database schema

Solution

1. Step 1: Understand the role of subqueries

   The subquery inside the IN clause fetches department IDs located in 'NY'.

2. Step 2: See how the main query uses subquery results

   The main query selects employees whose department_id matches those IDs from the subquery.

3. Final Answer:

   To use the result of one query inside another for filtering or comparison -> Option A

4. Quick Check:

   Subqueries help filter data using other query results [OK]

Hint: Subqueries let queries talk to each other inside SQL [OK]

Common Mistakes:

• Thinking subqueries speed up queries automatically
• Confusing subqueries with table creation
• Believing subqueries change database structure

2. Which of the following is the correct syntax for a subquery in SQL?

easy

A. SELECT name FROM employees WHERE id IN SELECT manager_id FROM departments WHERE id = 5;

B. SELECT name FROM employees WHERE id == (SELECT manager_id FROM departments WHERE id = 5);

C. SELECT name FROM employees WHERE id = SELECT manager_id FROM departments WHERE id = 5;

D. SELECT name FROM employees WHERE id = (SELECT manager_id FROM departments WHERE id = 5);

Solution

1. Step 1: Check correct subquery syntax

   Subqueries must be enclosed in parentheses and use a single equals sign for comparison.

2. Step 2: Identify syntax errors in other options

   SELECT name FROM employees WHERE id == (SELECT manager_id FROM departments WHERE id = 5); uses '==' which is invalid in SQL; C misses parentheses; D misses parentheses around subquery.

3. Final Answer:

   SELECT name FROM employees WHERE id = (SELECT manager_id FROM departments WHERE id = 5); -> Option D

4. Quick Check:

   Subqueries need parentheses and single '=' [OK]

Hint: Subqueries always go inside parentheses with '=' or IN [OK]

Common Mistakes:

• Using '==' instead of '=' for comparison
• Forgetting parentheses around subqueries
• Using subqueries without proper syntax

3. What will be the output of this query?

SELECT name FROM employees WHERE department_id = (SELECT id FROM departments WHERE name = 'Sales');

Assuming the departments table has one row with name 'Sales' and id 3, and employees table has:
id | name | department_id
1 | Alice | 3
2 | Bob | 2
3 | Carol | 3

medium

A. No rows returned

B. Bob only

C. Alice and Carol

D. Alice, Bob, and Carol

Solution

1. Step 1: Find department id for 'Sales'

   The subquery returns id = 3 for 'Sales' department.

2. Step 2: Select employees with department_id = 3

   Employees Alice and Carol have department_id 3, so they are selected.

3. Final Answer:

   Alice and Carol -> Option C

4. Quick Check:

   Subquery returns 3, employees with department_id 3 selected [OK]

Hint: Match subquery result with main query filter [OK]

Common Mistakes:

• Assuming subquery returns multiple rows causing error
• Selecting employees from wrong department
• Ignoring subquery result in main query

4. Identify the error in this SQL query:

SELECT name FROM employees WHERE department_id = SELECT id FROM departments WHERE location = 'LA';

medium

A. Missing parentheses around the subquery

B. Using '=' instead of 'IN' for multiple results

C. Wrong table name 'employees'

D. No error, query is correct

Solution

1. Step 1: Check subquery syntax

   The subquery must be enclosed in parentheses to be valid.

2. Step 2: Confirm other parts

   Using '=' is okay if subquery returns one value; table names are correct.

3. Final Answer:

   Missing parentheses around the subquery -> Option A

4. Quick Check:

   Subqueries need parentheses [OK]

Hint: Always put subqueries inside parentheses [OK]

Common Mistakes:

• Forgetting parentheses around subqueries
• Assuming '=' works for multiple rows
• Misreading table names as errors

5. You want to find all customers who placed orders with a total amount greater than the average order amount. Which query correctly uses a subquery to achieve this?

hard

A. SELECT customer_id FROM orders WHERE total_amount > AVG(total_amount);

B. SELECT customer_id FROM orders WHERE total_amount > (SELECT AVG(total_amount) FROM orders);

C. SELECT customer_id FROM orders WHERE total_amount IN (SELECT AVG(total_amount) FROM orders);

D. SELECT customer_id FROM orders WHERE total_amount = (SELECT total_amount FROM orders WHERE total_amount > AVG(total_amount));

Solution

1. Step 1: Understand the goal

   We want customers with orders greater than the average order amount.

2. Step 2: Check subquery usage

   SELECT customer_id FROM orders WHERE total_amount > (SELECT AVG(total_amount) FROM orders); correctly uses a subquery to calculate average and compares each order's total_amount to it.

3. Step 3: Identify errors in other options

   SELECT customer_id FROM orders WHERE total_amount > AVG(total_amount); misuses AVG without subquery; C uses IN incorrectly; D has wrong comparison logic.

4. Final Answer:

   SELECT customer_id FROM orders WHERE total_amount > (SELECT AVG(total_amount) FROM orders); -> Option B

5. Quick Check:

   Subquery calculates average, main query compares amounts [OK]

Hint: Use subquery to get average, compare in main query [OK]

Common Mistakes:

• Using aggregate functions without subqueries
• Misusing IN for single value comparisons
• Comparing with wrong operators or missing parentheses