Subquery with EXISTS operator in SQL - Time & Space Complexity

Time Complexity: Subquery with EXISTS operator

O(n)

Understanding Time Complexity

We want to understand how the time needed to run a query with an EXISTS subquery changes as the data grows.

Specifically, how does checking for existence inside a subquery affect performance?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_id, employee_name
FROM employees e
WHERE EXISTS (
  SELECT 1
  FROM sales s
  WHERE s.employee_id = e.employee_id
);
    

This query finds all employees who have made at least one sale by checking if a matching record exists in the sales table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each employee, the database checks the sales table to see if a matching sale exists.
• How many times: This check happens once per employee row.

How Execution Grows With Input

As the number of employees grows, the database performs more existence checks.

Input Size (n employees)	Approx. Operations
10	About 10 existence checks in sales
100	About 100 existence checks in sales
1000	About 1000 existence checks in sales

Pattern observation: The number of checks grows roughly in direct proportion to the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in a straight line as the number of employees increases.

Common Mistake

[X] Wrong: "The EXISTS subquery runs once and checks all sales at the same time."

[OK] Correct: Actually, the EXISTS check runs separately for each employee, so the work grows with the number of employees.

Interview Connect

Understanding how subqueries with EXISTS scale helps you write efficient queries and explain your reasoning clearly in interviews.

Self-Check

"What if we replaced EXISTS with IN? How would the time complexity change?"

Practice

1. What does the EXISTS operator do in an SQL query?

easy

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

B. Counts the number of rows in a table.

C. Joins two tables based on a condition.

D. Deletes rows from a table.

Solution

1. Step 1: Understand the purpose of EXISTS

   The EXISTS operator checks if the subquery returns at least one row.

2. Step 2: Compare with other options

   Counting rows, joining tables, or deleting rows are different SQL operations unrelated to EXISTS.

3. Final Answer:

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

4. Quick Check:

   EXISTS = TRUE if rows found [OK]

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

Common Mistakes:

• Thinking EXISTS counts rows instead of checking existence
• Confusing EXISTS with JOIN operations
• Assuming EXISTS deletes or modifies data

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 LIKE (SELECT column FROM table2);

Solution

1. Step 1: Review correct EXISTS syntax

   EXISTS is used as EXISTS (subquery) without any operator like =, IN, or LIKE.

2. Step 2: Identify incorrect options

   Options B, C, and D misuse operators (=, IN, LIKE) with EXISTS, causing syntax errors.

3. Final Answer:

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

4. Quick Check:

   EXISTS uses only parentheses for subquery [OK]

Hint: EXISTS always followed by (subquery) without operators [OK]

Common Mistakes:

• Adding = or IN after EXISTS
• Using LIKE with EXISTS
• Forgetting parentheses around subquery

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

SELECT name FROM Customers c WHERE EXISTS (SELECT 1 FROM Orders o WHERE o.customer_id = c.id);

medium

A. All customers including those without orders.

B. All customers who have placed at least one order.

C. All orders with customer names.

D. An error because of incorrect subquery.

Solution

1. Step 1: Understand the EXISTS subquery condition

   The subquery checks if there is at least one order with customer_id matching the customer's id.

2. Step 2: Determine which customers are returned

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

3. Final Answer:

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

4. Quick Check:

   EXISTS filters customers with orders [OK]

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

Common Mistakes:

• Thinking it returns all customers regardless of orders
• Confusing with JOIN that returns all orders
• Assuming syntax error due to subquery

4. Identify the error in this query:

SELECT * FROM Employees e WHERE EXISTS SELECT * FROM Salaries s WHERE s.emp_id = e.id;

medium

A. EXISTS cannot be used in WHERE clause.

B. Using SELECT * inside EXISTS is not allowed.

C. Missing parentheses around the subquery after EXISTS.

D. The alias 'e' is not defined.

Solution

1. Step 1: Check EXISTS syntax

   EXISTS requires the subquery to be enclosed in parentheses.

2. Step 2: Identify the missing parentheses

   The query lacks parentheses around the subquery after EXISTS, causing a syntax error.

3. Final Answer:

   Missing parentheses around the subquery after EXISTS. -> Option C

4. Quick Check:

   EXISTS (subquery) needs parentheses [OK]

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

Common Mistakes:

• Omitting parentheses around subquery
• Thinking SELECT * is invalid inside EXISTS
• Misunderstanding alias 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 find these products?

hard

A. SELECT name FROM Products p WHERE NOT IN (SELECT product_id FROM Orders);

B. SELECT name FROM Products p WHERE EXISTS (SELECT 1 FROM Orders o WHERE o.product_id = p.id);

C. SELECT name FROM Products p WHERE EXISTS NOT (SELECT 1 FROM Orders o WHERE o.product_id = p.id);

D. SELECT name FROM Products p WHERE NOT EXISTS (SELECT 1 FROM Orders o WHERE o.product_id = p.id);

Solution

1. Step 1: Understand the goal

   We want products with no matching orders, so the subquery should check for orders and we want those where no such orders exist.

2. Step 2: Use NOT EXISTS correctly

   NOT EXISTS with a subquery checking orders for the product returns products never ordered.

3. Step 3: Evaluate other options

   SELECT name FROM Products p WHERE EXISTS (SELECT 1 FROM Orders o WHERE o.product_id = p.id); returns products with orders, C has invalid syntax, D uses NOT IN which can cause issues with NULLs.

4. Final Answer:

   SELECT name FROM Products p WHERE NOT EXISTS (SELECT 1 FROM Orders o WHERE o.product_id = p.id); -> Option D

5. Quick Check:

   NOT EXISTS finds missing related rows [OK]

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

Common Mistakes:

• Using EXISTS instead of NOT EXISTS for missing data
• Incorrect syntax like EXISTS NOT
• Using NOT IN which may fail with NULLs