EXCEPT (MINUS) for differences in SQL - Time & Space Complexity

Time Complexity: EXCEPT (MINUS) for differences

O(n * m)

Understanding Time Complexity

When we use EXCEPT or MINUS in SQL, we want to find rows in one table that are not in another. Understanding how long this takes helps us know how it will perform as data grows.

We ask: How does the time to find differences change when tables get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_id, name
FROM employees
EXCEPT
SELECT employee_id, name
FROM retired_employees;
    

This query finds employees who are currently working but not retired by removing retired employees from the full employee list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing each row in the first table against rows in the second to find differences.
• How many times: For each row in the first table, it checks against rows in the second table.

How Execution Grows With Input

As the number of employees and retired employees grows, the comparisons increase.

Input Size (n)	Approx. Operations
10	About 100 comparisons
100	About 10,000 comparisons
1000	About 1,000,000 comparisons

Pattern observation: The number of operations grows quickly, roughly multiplying as both tables get bigger.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to find differences grows roughly by multiplying the size of the first table by the size of the second.

Common Mistake

[X] Wrong: "The EXCEPT operation only looks at one table, so it runs in linear time."

[OK] Correct: EXCEPT compares rows between two tables, so it depends on both sizes, not just one.

Interview Connect

Understanding how set difference operations scale helps you explain query performance clearly and shows you can think about data size impact in real projects.

Self-Check

"What if we added an index on the columns used in EXCEPT? How would the time complexity change?"

Practice

1. What does the SQL EXCEPT operator do?

easy

A. Returns rows from the first query that are not in the second query

B. Returns rows common to both queries

C. Combines all rows from both queries including duplicates

D. Deletes rows from the first table that exist in the second

Solution

1. Step 1: Understand the purpose of EXCEPT

   The EXCEPT operator compares two query results and returns only those rows that appear in the first query but not in the second.

2. Step 2: Differentiate from other set operations

   Unlike INTERSECT which returns common rows, EXCEPT returns unique rows from the first set only.

3. Final Answer:

   Returns rows from the first query that are not in the second query -> Option A

4. Quick Check:

   EXCEPT = difference = unique first query rows [OK]

Hint: EXCEPT returns what first query has but second does not [OK]

Common Mistakes:

• Confusing EXCEPT with INTERSECT
• Thinking EXCEPT deletes rows
• Assuming EXCEPT returns all combined rows

2. Which of the following is the correct syntax to find rows in table1 not in table2 using EXCEPT?

easy

A. SELECT * FROM table1 WHERE NOT IN table2;

B. SELECT * FROM table1 MINUS table2;

C. SELECT * FROM table1 EXCEPT SELECT * FROM table2;

D. SELECT * FROM table1 JOIN table2 EXCEPT;

Solution

1. Step 1: Recall correct EXCEPT syntax

   The EXCEPT operator is used between two SELECT statements: SELECT ... FROM ... EXCEPT SELECT ... FROM ....

2. Step 2: Check each option

   SELECT * FROM table1 EXCEPT SELECT * FROM table2; uses correct syntax with two SELECT statements separated by EXCEPT. SELECT * FROM table1 MINUS table2; is incorrect because MINUS requires SELECT before both tables. SELECT * FROM table1 WHERE NOT IN table2; is invalid syntax. SELECT * FROM table1 JOIN table2 EXCEPT; misuses JOIN and EXCEPT.

3. Final Answer:

   SELECT * FROM table1 EXCEPT SELECT * FROM table2; -> Option C

4. Quick Check:

   Correct EXCEPT syntax = SELECT ... EXCEPT SELECT ... [OK]

Hint: EXCEPT goes between two SELECT queries, no JOIN needed [OK]

Common Mistakes:

• Using EXCEPT without two SELECT statements
• Confusing MINUS syntax with EXCEPT
• Trying to use EXCEPT with JOIN

3. Given these tables:
table1:
id
1
2
3

table2:
id
2
4
5

What is the result of:
SELECT id FROM table1 EXCEPT SELECT id FROM table2;

medium

A. [1, 3]

B. [2]

C. [4, 5]

D. [1, 2, 3, 4, 5]

Solution

1. Step 1: Identify rows in table1

   table1 has ids 1, 2, 3.

2. Step 2: Identify rows in table2

   table2 has ids 2, 4, 5.

3. Step 3: Apply EXCEPT logic

   EXCEPT returns rows in table1 not in table2, so ids 1 and 3 remain.

4. Final Answer:

   [1, 3] -> Option A

5. Quick Check:

   table1 - table2 = [1, 3] [OK]

Hint: Subtract table2 rows from table1 rows [OK]

Common Mistakes:

• Including ids from table2
• Returning common ids instead
• Confusing EXCEPT with UNION

4. What is wrong with this query?
SELECT name FROM employees EXCEPT name FROM managers;

medium

A. EXCEPT cannot be used with column names

B. Missing SELECT keyword before second query

C. Syntax requires JOIN instead of EXCEPT

D. No error, query is correct

Solution

1. Step 1: Check syntax of EXCEPT usage

   EXCEPT requires two full SELECT statements. The second query must start with SELECT.

2. Step 2: Identify error in given query

   The second part is missing SELECT before name FROM managers, causing syntax error.

3. Final Answer:

   Missing SELECT keyword before second query -> Option B

4. Quick Check:

   EXCEPT needs two SELECTs [OK]

Hint: Always write SELECT before both queries with EXCEPT [OK]

Common Mistakes:

• Omitting SELECT in second query
• Using EXCEPT with columns only
• Confusing EXCEPT with JOIN syntax

5. You have two tables:
orders_2023 and orders_2024, both with columns order_id and customer_id.

You want to find all orders from 2023 that were NOT repeated in 2024.

Which query correctly finds these unique 2023 orders?

hard

A. SELECT order_id, customer_id FROM orders_2023 INTERSECT SELECT order_id, customer_id FROM orders_2024;

B. SELECT order_id, customer_id FROM orders_2024 EXCEPT SELECT order_id, customer_id FROM orders_2023;

C. SELECT order_id, customer_id FROM orders_2023 UNION SELECT order_id, customer_id FROM orders_2024;

D. SELECT order_id, customer_id FROM orders_2023 EXCEPT SELECT order_id, customer_id FROM orders_2024;

Solution

1. Step 1: Understand the requirement

   We want orders in 2023 that do NOT appear in 2024.

2. Step 2: Choose correct set operation

   EXCEPT returns rows in first query not in second, so orders_2023 EXCEPT orders_2024 fits.

3. Step 3: Check other options

   SELECT order_id, customer_id FROM orders_2024 EXCEPT SELECT order_id, customer_id FROM orders_2023; reverses order, giving 2024 unique orders. SELECT order_id, customer_id FROM orders_2023 INTERSECT SELECT order_id, customer_id FROM orders_2024; returns common orders. SELECT order_id, customer_id FROM orders_2023 UNION SELECT order_id, customer_id FROM orders_2024; combines all orders.

4. Final Answer:

   SELECT order_id, customer_id FROM orders_2023 EXCEPT SELECT order_id, customer_id FROM orders_2024; -> Option D

5. Quick Check:

   2023 orders minus 2024 orders = unique 2023 orders [OK]

Hint: Use EXCEPT with 2023 first, 2024 second to find unique 2023 orders [OK]

Common Mistakes:

• Swapping table order in EXCEPT
• Using INTERSECT instead of EXCEPT
• Using UNION which combines all rows