Union, intersection, difference in DBMS Theory - Time & Space Complexity

Time Complexity: Union, intersection, difference

O(n * m)

Understanding Time Complexity

When working with sets of data in databases, operations like union, intersection, and difference combine or compare rows from tables.

We want to understand how the time to perform these operations grows as the size of the data increases.

Scenario Under Consideration

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

SELECT * FROM TableA
UNION
SELECT * FROM TableB;

SELECT * FROM TableA
INTERSECT
SELECT * FROM TableB;

SELECT * FROM TableA
EXCEPT
SELECT * FROM TableB;
    

These queries combine or compare two tables to produce a result set with unique rows.

Identify Repeating Operations

Each operation involves scanning rows and comparing them.

• Primary operation: Comparing rows from both tables to find matches or differences.
• How many times: Each row in one table is compared against rows in the other table.

How Execution Grows With Input

As the number of rows in each table grows, the number of comparisons grows roughly with the product of their sizes.

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

Pattern observation: Doubling the size of both tables roughly quadruples the work needed.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly with the number of rows in the first table times the number in the second table.

Common Mistake

[X] Wrong: "These operations only scan one table, so time grows linearly with one table's size."

[OK] Correct: The operations compare rows between two tables, so both sizes affect the total work.

Interview Connect

Understanding how set operations scale helps you reason about database query performance and write efficient queries in real projects.

Self-Check

"What if one table is much smaller than the other? How would that affect the time complexity?"