Time Complexity: INTERSECT for common rows
O(n * m)
0
0
INTERSECT for common rows in SQL - Time & Space Complexity
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?"