Subqueries with EXISTS in MySQL - Time & Space Complexity

Time Complexity: Subqueries with EXISTS

O(n * m)

Understanding Time Complexity

When using subqueries with EXISTS, we want to know how the time to run the query changes as the data grows.

We ask: How many checks does the database do as the tables get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT customer_id, customer_name
FROM customers c
WHERE EXISTS (
  SELECT 1
  FROM orders o
  WHERE o.customer_id = c.customer_id
);
    

This query finds all customers who have at least one order by checking if an order exists for each customer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each customer, the database checks the orders table to find a matching order.
• How many times: This check happens once per customer, so as many times as there are customers.

How Execution Grows With Input

As the number of customers grows, the database does more checks in the orders table for each customer.

Input Size (n customers)	Approx. Operations
10	Checks orders for 10 customers
100	Checks orders for 100 customers
1000	Checks orders for 1000 customers

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

Final Time Complexity

Time Complexity: O(n * m)

This means the time to run the query grows linearly with the number of customers and the number of orders per customer.

Common Mistake

[X] Wrong: "The EXISTS subquery runs once and then applies to all customers."

[OK] Correct: The subquery runs separately for each customer to check if an order exists, so it repeats many times.

Interview Connect

Understanding how EXISTS works helps you explain query performance clearly and shows you can think about how databases handle data step by step.

Self-Check

"What if we added an index on orders.customer_id? How would the time complexity change?"

Practice

1. What does the EXISTS keyword do in a MySQL query?

easy

A. Counts the total number of rows in a table

B. Deletes rows from a table based on a condition

C. Checks if a subquery returns any rows and returns TRUE or FALSE

D. Joins two tables together

Solution

1. Step 1: Understand the purpose of EXISTS

   EXISTS checks if the subquery returns at least one row.

2. Step 2: Compare with other options

   Counting rows, deleting rows, and joining tables are different operations.

3. Final Answer:

   Checks if a subquery returns any rows and returns TRUE or FALSE -> Option C

4. Quick Check:

   EXISTS means row presence check = B [OK]

Hint: EXISTS means "is there at least one row?" [OK]

Common Mistakes:

• Confusing EXISTS with COUNT
• Thinking EXISTS deletes rows
• Mixing EXISTS with JOIN

2. Which of the following is the correct syntax to use EXISTS in a WHERE clause?

easy

A. SELECT * FROM table WHERE EXISTS = (SELECT column FROM table2);

B. SELECT * FROM table WHERE EXISTS SELECT column FROM table2;

C. SELECT * FROM table WHERE EXISTS IN (SELECT column FROM table2);

D. SELECT * FROM table WHERE EXISTS (SELECT column FROM table2);

Solution

1. Step 1: Recall EXISTS syntax

   EXISTS must be followed by a subquery in parentheses.

2. Step 2: Check each option

   SELECT * FROM table WHERE EXISTS (SELECT column FROM table2); uses correct syntax with parentheses; others have syntax errors.

3. Final Answer:

   SELECT * FROM table WHERE EXISTS (SELECT column FROM table2); -> Option D

4. Quick Check:

   EXISTS needs parentheses around subquery = C [OK]

Hint: EXISTS always uses parentheses for the subquery [OK]

Common Mistakes:

• Omitting parentheses after EXISTS
• Using '=' or 'IN' with EXISTS
• Writing subquery without parentheses

3. Given tables customers(id, name) and orders(id, customer_id), what does this query return?

SELECT name FROM customers WHERE EXISTS (SELECT 1 FROM orders WHERE orders.customer_id = customers.id);

medium

A. An error because of invalid subquery

B. All customers who have placed at least one order

C. All orders with matching customer names

D. All customers including those without orders

Solution

1. Step 1: Understand the EXISTS subquery

   The subquery checks if there is at least one order with customer_id matching customers.id.

2. Step 2: Interpret the WHERE clause effect

   Only customers with matching orders exist, so only those customers are returned.

3. Final Answer:

   All customers who have placed at least one order -> Option B

4. Quick Check:

   EXISTS filters customers with orders = D [OK]

Hint: EXISTS filters rows with matching related data [OK]

Common Mistakes:

• Thinking it returns all customers
• Confusing orders with customers
• Assuming syntax error in subquery

4. Identify the error in this query:

SELECT * FROM employees WHERE EXISTS SELECT * FROM departments WHERE departments.id = employees.dept_id;

medium

A. Missing parentheses around the subquery after EXISTS

B. Using SELECT * inside EXISTS is not allowed

C. The WHERE clause inside subquery is invalid

D. EXISTS cannot be used with multiple tables

Solution

1. Step 1: Check EXISTS syntax

   EXISTS requires the subquery to be enclosed in parentheses.

2. Step 2: Verify other parts

   SELECT * is allowed inside EXISTS; WHERE clause is valid; EXISTS works with multiple tables.

3. Final Answer:

   Missing parentheses around the subquery after EXISTS -> Option A

4. Quick Check:

   EXISTS needs parentheses = A [OK]

Hint: Always put subquery in parentheses after EXISTS [OK]

Common Mistakes:

• Omitting parentheses after EXISTS
• Thinking SELECT * is invalid inside EXISTS
• Misunderstanding WHERE clause usage

5. You want to find all products that have never been ordered. Given tables products(id, name) and orders(id, product_id), which query correctly uses EXISTS to achieve this?

hard

A. SELECT name FROM products WHERE NOT EXISTS (SELECT 1 FROM orders WHERE orders.product_id = products.id);

B. SELECT name FROM products WHERE EXISTS (SELECT 1 FROM orders WHERE orders.product_id = products.id);

C. SELECT name FROM products WHERE EXISTS (SELECT 1 FROM orders WHERE orders.id = products.id);

D. SELECT name FROM products WHERE NOT EXISTS (SELECT 1 FROM orders WHERE orders.id = products.id);

Solution

1. Step 1: Understand the goal

   We want products with no matching orders, so use NOT EXISTS with matching product_id.

2. Step 2: Analyze each option

   SELECT name FROM products WHERE NOT EXISTS (SELECT 1 FROM orders WHERE orders.product_id = products.id); correctly uses NOT EXISTS with orders.product_id = products.id. SELECT name FROM products WHERE EXISTS (SELECT 1 FROM orders WHERE orders.product_id = products.id); finds products with orders. Options C and D compare wrong columns.

3. Final Answer:

   SELECT name FROM products WHERE NOT EXISTS (SELECT 1 FROM orders WHERE orders.product_id = products.id); -> Option A

4. Quick Check:

   NOT EXISTS filters products without orders = A [OK]

Hint: Use NOT EXISTS to find items with no related rows [OK]

Common Mistakes:

• Using EXISTS instead of NOT EXISTS
• Comparing wrong columns in subquery
• Confusing product_id with order id