INTERSECT and EXCEPT in PostgreSQL - Time & Space Complexity

Time Complexity: INTERSECT and EXCEPT

O(n * m)

Understanding Time Complexity

We want to understand how the time it takes to run INTERSECT and EXCEPT queries changes as the size of the data grows.

Specifically, how does the database find common or different rows between two sets?

Scenario Under Consideration

Analyze the time complexity of the following SQL queries using INTERSECT and EXCEPT.

SELECT column1 FROM tableA
INTERSECT
SELECT column1 FROM tableB;

SELECT column1 FROM tableA
EXCEPT
SELECT column1 FROM tableB;
    

These queries find rows common to both tables (INTERSECT) or rows in the first table but not in the second (EXCEPT).

Identify Repeating Operations

Both INTERSECT and EXCEPT require comparing rows from two tables.

• Primary operation: Comparing each row from one table to rows in the other table.
• How many times: For each row in the first table, the database checks for matching rows in the second table.

How Execution Grows With Input

As the number of rows in the tables increases, the number of comparisons grows.

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

Pattern observation: The work grows quickly, roughly by the product of the input sizes.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to run the query grows roughly with the product of the sizes of the two tables.

Common Mistake

[X] Wrong: "INTERSECT and EXCEPT just scan one table, so they are fast regardless of size."

[OK] Correct: Both operations must compare rows between two tables, so the work depends on both table sizes, not just one.

Interview Connect

Understanding how INTERSECT and EXCEPT 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 indexes on the columns used in INTERSECT and EXCEPT? How would the time complexity change?

Practice

1. What does the INTERSECT operator do in PostgreSQL?

easy

A. Returns rows only in the second query

B. Returns all rows from the first query

C. Combines all rows from both queries without duplicates

D. Returns rows common to both queries

Solution

1. Step 1: Understand INTERSECT purpose

   INTERSECT returns only rows that appear in both query results.

2. Step 2: Compare with other set operations

   Unlike UNION or EXCEPT, INTERSECT finds common rows, not all or unique rows.

3. Final Answer:

   Returns rows common to both queries -> Option D

4. Quick Check:

   INTERSECT = common rows [OK]

Hint: INTERSECT = find common rows between two queries [OK]

Common Mistakes:

• Confusing INTERSECT with UNION
• Thinking INTERSECT returns all rows from first query
• Mixing INTERSECT with EXCEPT

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

easy

A. SELECT * FROM table1 INTERSECT SELECT * FROM table2;

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

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

D. SELECT * FROM table1 EXCEPT ALL SELECT * FROM table2;

Solution

1. Step 1: Identify EXCEPT syntax

   The correct syntax is: SELECT ... EXCEPT SELECT ... to get rows in first query not in second.

2. Step 2: Check options for correct usage

   SELECT * FROM table1 EXCEPT SELECT * FROM table2; matches correct syntax; others misuse INTERSECT, UNION, or EXCEPT ALL (which is valid but different).

3. Final Answer:

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

4. Quick Check:

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

Hint: Use EXCEPT between two SELECTs to find rows only in first [OK]

Common Mistakes:

• Using INTERSECT instead of EXCEPT
• Adding UNION incorrectly
• Using EXCEPT ALL when not needed

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

table_b:
id
2
3
4

What is the result of:
SELECT id FROM table_a INTERSECT SELECT id FROM table_b;

medium

A. [1, 2, 3]

B. [1]

C. [2, 3]

D. [4]

Solution

1. Step 1: List rows from both tables

   table_a has ids 1, 2, 3; table_b has ids 2, 3, 4.

2. Step 2: Find common ids using INTERSECT

   Common ids are 2 and 3 only.

3. Final Answer:

   [2, 3] -> Option C

4. Quick Check:

   INTERSECT = common rows = [2, 3] [OK]

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

Common Mistakes:

• Including ids only in one table
• Confusing INTERSECT with UNION
• Expecting all ids combined

4. What is wrong with this query?

SELECT id, name FROM table1 EXCEPT SELECT id FROM table2;

medium

A. The number of columns in both SELECTs differ

B. EXCEPT cannot be used with SELECT statements

C. The query is missing a WHERE clause

D. The table names are invalid

Solution

1. Step 1: Check column counts in both SELECTs

   First SELECT returns two columns (id, name), second returns one column (id).

2. Step 2: Understand EXCEPT requirements

   EXCEPT requires both SELECTs to have the same number and compatible types of columns.

3. Final Answer:

   The number of columns in both SELECTs differ -> Option A

4. Quick Check:

   EXCEPT needs equal columns [OK]

Hint: EXCEPT requires same number of columns in both SELECTs [OK]

Common Mistakes:

• Ignoring column count mismatch
• Thinking EXCEPT needs WHERE clause
• Assuming table names cause error

5. You have two tables:
employees with columns id, name
contractors with columns id, name
You want to find people who are either employees or contractors but not both.
Which query correctly returns this list?

hard

A. SELECT id, name FROM employees EXCEPT SELECT id, name FROM contractors UNION SELECT id, name FROM contractors EXCEPT SELECT id, name FROM employees;

B. SELECT id, name FROM employees INTERSECT SELECT id, name FROM contractors;

C. SELECT id, name FROM employees UNION SELECT id, name FROM contractors;

D. SELECT id, name FROM employees EXCEPT SELECT id, name FROM contractors;

Solution

1. Step 1: Understand the requirement

   We want people in employees or contractors but not in both (symmetric difference).

2. Step 2: Use EXCEPT and UNION to find symmetric difference

   EXCEPT finds those in one table but not the other; UNION combines both exclusive sets.

3. Step 3: Analyze options

   SELECT id, name FROM employees EXCEPT SELECT id, name FROM contractors UNION SELECT id, name FROM contractors EXCEPT SELECT id, name FROM employees; correctly combines EXCEPT in both directions with UNION to get symmetric difference.

4. Final Answer:

   SELECT id, name FROM employees EXCEPT SELECT id, name FROM contractors UNION SELECT id, name FROM contractors EXCEPT SELECT id, name FROM employees; -> Option A

5. Quick Check:

   Symmetric difference = EXCEPT + UNION [OK]

Hint: Symmetric difference = (A EXCEPT B) UNION (B EXCEPT A) [OK]

Common Mistakes:

• Using only INTERSECT or UNION
• Using EXCEPT one way only
• Confusing symmetric difference with intersection