EXCEPT equivalent in MySQL - Time & Space Complexity

Time Complexity: EXCEPT equivalent

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to find differences between two sets of data grows as the data gets bigger.

Specifically, how does the cost change when using an EXCEPT equivalent in MySQL?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT column1 FROM tableA
WHERE column1 NOT IN (SELECT column1 FROM tableB);
    

This query finds all values in tableA that are not present in tableB, similar to EXCEPT.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in tableA, check if its value exists in tableB.
• How many times: This check happens once for every row in tableA.

How Execution Grows With Input

As the number of rows in tableA grows, the number of checks grows too.

Input Size (rows in tableA)	Approx. Operations
10	10 checks against tableB
100	100 checks against tableB
1000	1000 checks against tableB

Pattern observation: The number of operations grows directly with the size of tableA.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly by multiplying the size of tableA (n) by the size of tableB (m), because each row in tableA is checked against all rows in tableB.

Common Mistake

[X] Wrong: "The query only looks at tableA, so time depends only on its size."

[OK] Correct: Each row in tableA must be compared against tableB, so the size of tableB also affects the time.

Interview Connect

Understanding how queries compare data sets helps you explain performance and choose better solutions in real projects.

Self-Check

"What if we add an index on tableB.column1? How would the time complexity change?"

Practice

1. What does the SQL EXCEPT operation do?

easy

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

B. Returns rows common to both queries

C. Returns all rows from both queries combined

D. Deletes rows from the first table

Solution

1. Step 1: Understand the purpose of EXCEPT

   The EXCEPT operation returns rows that appear in the first query but do not appear in the second query.

2. Step 2: Compare with other set operations

   Unlike INTERSECT which returns common rows, EXCEPT excludes rows found in the second set.

3. Final Answer:

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

4. Quick Check:

   EXCEPT = unique rows in first set [OK]

Hint: EXCEPT means "first minus second" rows [OK]

Common Mistakes:

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

2. Which of the following is the correct MySQL syntax to simulate EXCEPT using NOT EXISTS?

easy

A. SELECT * FROM table1 WHERE NOT EXISTS (SELECT * FROM table2 WHERE table2.id = table1.id);

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

C. SELECT * FROM table1 JOIN table2 ON table1.id = table2.id WHERE table2.id IS NULL;

D. SELECT * FROM table1 WHERE id IN (SELECT id FROM table2);

Solution

1. Step 1: Identify how NOT EXISTS works

   NOT EXISTS checks if a row in table1 has no matching row in table2 based on the condition.

2. Step 2: Match syntax to EXCEPT behavior

   The query selects rows from table1 where no matching id exists in table2, simulating EXCEPT.

3. Final Answer:

   SELECT * FROM table1 WHERE NOT EXISTS (SELECT * FROM table2 WHERE table2.id = table1.id); -> Option A

4. Quick Check:

   NOT EXISTS filters out matching rows [OK]

Hint: Use NOT EXISTS with matching condition for EXCEPT [OK]

Common Mistakes:

• Using EXCEPT directly in MySQL (unsupported)
• Confusing JOIN with NOT EXISTS logic
• Using IN instead of NOT EXISTS

3. Given tables:
table1(id): 1, 2, 3, 4
table2(id): 3, 4, 5
What is the result of this query?

SELECT id FROM table1 WHERE NOT EXISTS (SELECT 1 FROM table2 WHERE table2.id = table1.id);

medium

A. [3, 4]

B. [1, 2]

C. [5]

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

Solution

1. Step 1: Identify ids in table1 not in table2

   table1 has 1,2,3,4; table2 has 3,4,5. IDs 1 and 2 are missing in table2.

2. Step 2: Understand NOT EXISTS filtering

   The query returns ids from table1 where no matching id exists in table2, so 1 and 2 are returned.

3. Final Answer:

   [1, 2] -> Option B

4. Quick Check:

   table1 minus table2 = [1, 2] [OK]

Hint: Find ids in first table missing in second [OK]

Common Mistakes:

• Including ids present in both tables
• Confusing NOT EXISTS with EXISTS
• Returning ids from table2 instead

4. Identify the error in this MySQL query intended to simulate EXCEPT:

SELECT * FROM table1 LEFT JOIN table2 ON table1.id = table2.id WHERE table2.id = NULL;

medium

A. LEFT JOIN should be INNER JOIN

B. Missing ON condition in JOIN

C. Using '=' to compare with NULL instead of IS NULL

D. No error, query is correct

Solution

1. Step 1: Understand NULL comparison in SQL

   In SQL, NULL cannot be compared using '='; use IS NULL instead.

2. Step 2: Identify the mistake in WHERE clause

   The condition table2.id = NULL is always false; it should be table2.id IS NULL to find unmatched rows.

3. Final Answer:

   Using '=' to compare with NULL instead of IS NULL -> Option C

4. Quick Check:

   NULL comparison requires IS NULL [OK]

Hint: Use IS NULL, not = NULL, to check for NULL values [OK]

Common Mistakes:

• Using '=' instead of IS NULL
• Confusing JOIN types
• Omitting ON clause in JOIN

5. You want to find customers who placed orders last month but did NOT place orders this month. Which query correctly simulates EXCEPT in MySQL?

hard

A. SELECT customer_id FROM orders LEFT JOIN orders o2 ON orders.customer_id = o2.customer_id WHERE o2.order_date BETWEEN '2024-06-01' AND '2024-06-30';

B. SELECT customer_id FROM orders WHERE order_date BETWEEN '2024-06-01' AND '2024-06-30' EXCEPT SELECT customer_id FROM orders WHERE order_date BETWEEN '2024-05-01' AND '2024-05-31';

C. SELECT customer_id FROM orders WHERE order_date BETWEEN '2024-05-01' AND '2024-06-30';

D. SELECT customer_id FROM orders WHERE order_date BETWEEN '2024-05-01' AND '2024-05-31' AND NOT EXISTS (SELECT 1 FROM orders o2 WHERE o2.customer_id = orders.customer_id AND o2.order_date BETWEEN '2024-06-01' AND '2024-06-30');

Solution

1. Step 1: Identify the time frames and logic

   We want customers who ordered in May but not in June.

2. Step 2: Use NOT EXISTS to exclude June customers

   The query selects May customers and excludes those with June orders using NOT EXISTS subquery.

3. Step 3: Check other options

   SELECT customer_id FROM orders WHERE order_date BETWEEN '2024-06-01' AND '2024-06-30' EXCEPT SELECT customer_id FROM orders WHERE order_date BETWEEN '2024-05-01' AND '2024-05-31'; uses EXCEPT which MySQL does not support; C returns all customers in both months; D returns June customers only.

4. Final Answer:

   SELECT customer_id FROM orders WHERE order_date BETWEEN '2024-05-01' AND '2024-05-31' AND NOT EXISTS (SELECT 1 FROM orders o2 WHERE o2.customer_id = orders.customer_id AND o2.order_date BETWEEN '2024-06-01' AND '2024-06-30'); -> Option D

5. Quick Check:

   NOT EXISTS excludes June orders [OK]

Hint: Use NOT EXISTS with date ranges to exclude recent orders [OK]

Common Mistakes:

• Using EXCEPT directly in MySQL
• Selecting all orders without filtering
• Confusing LEFT JOIN logic