INTERSECT equivalent in MySQL - Time & Space Complexity

Time Complexity: INTERSECT equivalent

O(n)

Understanding Time Complexity

We want to understand how the time needed to find common rows between two tables grows as the tables get bigger.

How does the cost change when we find the intersection of two sets of data?

Scenario Under Consideration

Analyze the time complexity of this MySQL query that finds common rows using JOIN.

SELECT a.id, a.value
FROM tableA a
INNER JOIN tableB b ON a.id = b.id;
    

This query returns rows where the id exists in both tableA and tableB.

Identify Repeating Operations

Look for repeated work done by the database engine.

• Primary operation: Matching each row in tableA with rows in tableB by id.
• How many times: For each row in tableA, the database checks for matching rows in tableB.

How Execution Grows With Input

As the number of rows in the tables grows, the work to find matches grows too.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows roughly in direct proportion to the number of rows in the first table.

Final Time Complexity

Time Complexity: O(n)

This means the time to find common rows grows linearly with the size of the input tables, assuming proper indexing.

Common Mistake

[X] Wrong: "The database checks every possible pair of rows between the two tables."

[OK] Correct: With proper indexes, the database looks up matches quickly instead of comparing all pairs, so it does not do a full cross-check.

Interview Connect

Understanding how joins work and their time cost helps you explain how databases handle common tasks efficiently, a useful skill in many real projects.

Self-Check

"What if we replaced the INNER JOIN with a subquery using EXISTS? How would the time complexity change?"

Practice

1. In MySQL, which of the following is the best way to find rows common to two tables table1 and table2 when INTERSECT is not supported?

easy

A. Use SELECT * FROM table1 JOIN table2 ON table1.column = table2.column

B. Use SELECT * FROM table1 UNION SELECT * FROM table2

C. Use SELECT * FROM table1 WHERE column IN (SELECT column FROM table2)

D. Use SELECT * FROM table1 EXCEPT SELECT * FROM table2

Solution

1. Step 1: Understand INTERSECT purpose

   INTERSECT returns rows common to both queries or tables.

2. Step 2: Use WHERE ... IN to mimic INTERSECT

   MySQL lacks INTERSECT, but WHERE column IN (subquery) returns rows in table1 that also appear in table2.

3. Final Answer:

   Use SELECT * FROM table1 WHERE column IN (SELECT column FROM table2) -> Option C

4. Quick Check:

   INTERSECT equivalent = WHERE ... IN [OK]

Hint: Use WHERE ... IN (subquery) to find common rows [OK]

Common Mistakes:

• Using UNION returns all unique rows, not common ones
• JOIN returns combined rows, not just common rows alone
• EXCEPT is not supported in MySQL and finds differences

2. Which of the following is the correct syntax to find common id values between tableA and tableB in MySQL?

easy

A. SELECT id FROM tableA INTERSECT SELECT id FROM tableB;

B. SELECT id FROM tableA WHERE id IN (SELECT id FROM tableB);

C. SELECT id FROM tableA UNION SELECT id FROM tableB;

D. SELECT id FROM tableA EXCEPT SELECT id FROM tableB;

Solution

1. Step 1: Recognize MySQL lacks INTERSECT and EXCEPT

   MySQL does not support INTERSECT or EXCEPT keywords.

2. Step 2: Use WHERE ... IN syntax for intersection

   The correct syntax is SELECT id FROM tableA WHERE id IN (SELECT id FROM tableB); to get common ids.

3. Final Answer:

   SELECT id FROM tableA WHERE id IN (SELECT id FROM tableB); -> Option B

4. Quick Check:

   Correct syntax for INTERSECT equivalent = WHERE ... IN [OK]

Hint: Use WHERE ... IN (subquery) syntax, not INTERSECT [OK]

Common Mistakes:

• Trying to use INTERSECT or EXCEPT directly in MySQL
• Using UNION which combines all unique rows
• Confusing JOIN with intersection

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

table2:
id
2
3
4

What is the output of this query?

SELECT id FROM table1 WHERE id IN (SELECT id FROM table2);

medium

A. [1, 2, 3]

B. [] (empty set)

C. [4]

D. [2, 3]

Solution

1. Step 1: Identify ids in table1

   table1 has ids 1, 2, 3.

2. Step 2: Identify ids in table2

   table2 has ids 2, 3, 4.

3. Step 3: Find common ids using WHERE ... IN

   The query returns ids from table1 that are also in table2: 2 and 3.

4. Final Answer:

   [2, 3] -> Option D

5. Quick Check:

   Common ids = [2, 3] [OK]

Hint: Check which ids appear in both tables [OK]

Common Mistakes:

• Including ids only in one table (like 1 or 4)
• Confusing UNION with intersection
• Expecting all ids from table1

4. You wrote this query to find common user_id values:

SELECT user_id FROM users WHERE user_id IN (SELECT user_id FROM orders);

But it returns an error. What is the most likely cause?

medium

A. The subquery returns multiple columns instead of one

B. The IN clause is not supported in MySQL

C. The user_id column does not exist in orders

D. You need to use INTERSECT instead of IN

Solution

1. Step 1: Check subquery column count

   The subquery inside IN must return exactly one column.

2. Step 2: Identify error cause

   If the subquery returns multiple columns, MySQL throws an error.

3. Final Answer:

   The subquery returns multiple columns instead of one -> Option A

4. Quick Check:

   Subquery must return single column [OK]

Hint: Ensure subquery returns only one column for IN clause [OK]

Common Mistakes:

• Using multiple columns in subquery for IN
• Assuming INTERSECT exists in MySQL
• Ignoring column existence in tables

5. You want to find all product_id values that appear in both sales and returns tables. Both tables have product_id and date columns. You only want products sold and returned on the same date. Which query correctly finds this intersection?

hard

A. SELECT product_id FROM sales WHERE (product_id, date) IN (SELECT product_id, date FROM returns);

B. SELECT product_id FROM sales WHERE product_id IN (SELECT product_id FROM returns);

C. SELECT product_id FROM sales JOIN returns ON sales.product_id = returns.product_id AND sales.date = returns.date;

D. SELECT product_id FROM sales INTERSECT SELECT product_id FROM returns WHERE sales.date = returns.date;

Solution

1. Step 1: Understand requirement for matching product_id and date

   We need products sold and returned on the same date, so both columns must match.

2. Step 2: Use tuple comparison in WHERE ... IN

   MySQL supports tuple comparisons like (product_id, date) IN (SELECT product_id, date FROM returns) to find exact matches.

3. Step 3: Evaluate other options

   SELECT product_id FROM sales WHERE product_id IN (SELECT product_id FROM returns); ignores date, SELECT product_id FROM sales JOIN returns ON sales.product_id = returns.product_id AND sales.date = returns.date; can produce duplicate product_id values if multiple returns match the same product and date, SELECT product_id FROM sales INTERSECT SELECT product_id FROM returns WHERE sales.date = returns.date; uses unsupported INTERSECT with conditions.

4. Final Answer:

   SELECT product_id FROM sales WHERE (product_id, date) IN (SELECT product_id, date FROM returns); -> Option A

5. Quick Check:

   Tuple IN matches multiple columns [OK]

Hint: Use tuple IN (subquery) for multiple column intersection [OK]

Common Mistakes:

• Ignoring date column in intersection
• Using INTERSECT which MySQL lacks
• Using JOIN which can produce duplicate product_ids