INTERSECT for common rows in SQL - Time & Space Complexity

Time Complexity: INTERSECT for common rows

O(n * m)

Understanding Time Complexity

We want to understand how the time it takes to find common rows between two tables changes as the tables get bigger.

How does the work grow when we use INTERSECT to find shared data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT column1, column2
FROM tableA
INTERSECT
SELECT column1, column2
FROM tableB;
    

This query finds rows that appear in both tableA and tableB based on column1 and column2.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing each row from tableA with rows in tableB to find matches.
• 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 each table grows, the work to find common rows grows too.

Input Size (rows in each table)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The number of checks grows quickly as tables get bigger, roughly multiplying the sizes.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to find common rows grows roughly by multiplying the number of rows in the first table by the number in the second.

Common Mistake

[X] Wrong: "INTERSECT just looks at one table, so time grows only with one table's size."

[OK] Correct: INTERSECT compares rows from both tables, so the work depends on both sizes together, not just one.

Interview Connect

Understanding how INTERSECT scales helps you explain how databases find shared data efficiently, a useful skill for real projects and interviews.

Self-Check

"What if one table has an index on the columns used in INTERSECT? How would that affect the time complexity?"

Practice

1. What does the SQL INTERSECT operator do?

easy

A. Combines rows from both queries including duplicates.

B. Returns all rows from the first SELECT query.

C. Returns all rows from the second SELECT query.

D. Returns only the rows common to both SELECT queries.

Solution

1. Step 1: Understand the purpose of INTERSECT

   The INTERSECT operator compares two SELECT queries and returns only the rows that appear in both results.

2. Step 2: Compare with other set operators

   Unlike UNION or UNION ALL, INTERSECT excludes rows not common to both queries.

3. Final Answer:

   Returns only the rows common to both SELECT queries. -> Option D

4. Quick Check:

   INTERSECT = common rows [OK]

Hint: INTERSECT keeps only shared rows between two queries [OK]

Common Mistakes:

• Confusing INTERSECT with UNION which combines all rows
• Thinking INTERSECT returns rows from only one query
• Assuming INTERSECT includes duplicates

2. Which of the following is the correct syntax to find common rows between two tables TableA and TableB with the same columns id and name?

easy

A. SELECT id, name FROM TableA JOIN TableB ON TableA.id = TableB.id;

B. SELECT id, name FROM TableA UNION SELECT id, name FROM TableB;

C. SELECT id, name FROM TableA INTERSECT SELECT id, name FROM TableB;

D. SELECT id, name FROM TableA WHERE id IN TableB;

Solution

1. Step 1: Identify correct INTERSECT syntax

   The INTERSECT operator is used between two SELECT statements with matching columns and types.

2. Step 2: Check each option

   SELECT id, name FROM TableA INTERSECT SELECT id, name FROM TableB; uses INTERSECT correctly. SELECT id, name FROM TableA UNION SELECT id, name FROM TableB; uses UNION which combines rows. SELECT id, name FROM TableA JOIN TableB ON TableA.id = TableB.id; uses JOIN which is different. SELECT id, name FROM TableA WHERE id IN TableB; has incorrect WHERE syntax.

3. Final Answer:

   SELECT id, name FROM TableA INTERSECT SELECT id, name FROM TableB; -> Option C

4. Quick Check:

   Correct INTERSECT syntax = SELECT id, name FROM TableA INTERSECT SELECT id, name FROM TableB; [OK]

Hint: Use INTERSECT between two SELECTs with matching columns [OK]

Common Mistakes:

• Using UNION instead of INTERSECT
• Trying to use WHERE with IN incorrectly
• Confusing JOIN with INTERSECT

3. Given two tables:
Employees1:
id | name
1 | Alice
2 | Bob
3 | Carol

Employees2:
id | name
2 | Bob
3 | Carol
4 | Dave

What is the result of this query?

SELECT id, name FROM Employees1 INTERSECT SELECT id, name FROM Employees2;

medium

A. Rows with Bob and Carol only

B. Rows with Alice, Bob, Carol, and Dave

C. Rows with Alice only

D. Rows with Dave only

Solution

1. Step 1: List rows from both tables

   Employees1 has (1, Alice), (2, Bob), (3, Carol). Employees2 has (2, Bob), (3, Carol), (4, Dave).

2. Step 2: Find common rows

   Common rows are those present in both: (2, Bob) and (3, Carol).

3. Final Answer:

   Rows with Bob and Carol only -> Option A

4. Quick Check:

   INTERSECT returns common rows = Bob, Carol [OK]

Hint: INTERSECT returns only rows present in both tables [OK]

Common Mistakes:

• Including rows unique to one table
• Confusing UNION with INTERSECT
• Ignoring column matching in rows

4. Consider this SQL query:

SELECT id, name FROM Customers INTERSECT SELECT id, name FROM Orders;

It returns an error. What is the most likely cause?

medium

A. The columns selected have different data types in Customers and Orders.

B. INTERSECT cannot be used with SELECT statements.

C. The tables Customers and Orders do not exist.

D. INTERSECT requires a WHERE clause.

Solution

1. Step 1: Understand INTERSECT requirements

   INTERSECT requires both SELECT queries to have the same number of columns with compatible data types.

2. Step 2: Analyze error causes

   If columns differ in type (e.g., id is integer in one table and string in another), the query errors. Other options are incorrect because INTERSECT is valid syntax, tables must exist to run, and WHERE is optional.

3. Final Answer:

   The columns selected have different data types in Customers and Orders. -> Option A

4. Quick Check:

   Matching column types required for INTERSECT [OK]

Hint: Check column types match for INTERSECT queries [OK]

Common Mistakes:

• Assuming INTERSECT needs WHERE clause
• Thinking INTERSECT is invalid syntax
• Ignoring data type mismatches

5. You have two tables:
ProductsA with columns product_id, name, price
ProductsB with columns product_id, name, price

You want to find products that exist in both tables with the same product_id and name, ignoring price differences.

Which query correctly uses INTERSECT to achieve this?

hard

A. SELECT product_id, name, price FROM ProductsA INTERSECT SELECT product_id, name, price FROM ProductsB;

B. SELECT product_id, name FROM ProductsA INTERSECT SELECT product_id, name FROM ProductsB;

C. SELECT product_id FROM ProductsA INTERSECT SELECT product_id FROM ProductsB;

D. SELECT * FROM ProductsA INTERSECT SELECT * FROM ProductsB;

Solution

1. Step 1: Identify columns to compare

   You want to compare only product_id and name, ignoring price differences.

2. Step 2: Use INTERSECT on matching columns

   SELECT product_id, name FROM ProductsA INTERSECT SELECT product_id, name FROM ProductsB; selects product_id and name from both tables and intersects them, returning only products common by those two columns.

3. Step 3: Analyze other options

   SELECT product_id, name, price FROM ProductsA INTERSECT SELECT product_id, name, price FROM ProductsB; includes price, so products with different prices won't match. SELECT product_id FROM ProductsA INTERSECT SELECT product_id FROM ProductsB; compares only product_id, ignoring name. SELECT * FROM ProductsA INTERSECT SELECT * FROM ProductsB; compares all columns, including price, which is not desired.

4. Final Answer:

   SELECT product_id, name FROM ProductsA INTERSECT SELECT product_id, name FROM ProductsB; -> Option B

5. Quick Check:

   INTERSECT on selected columns matches desired fields [OK]

Hint: Select only columns to compare before INTERSECT [OK]

Common Mistakes:

• Including extra columns that cause mismatches
• Selecting * when columns differ
• Comparing only one column when two are needed