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?