INTERSECT equivalent in MySQL - Time & Space Complexity

Time Complexity: INTERSECT equivalent

O(n)

Understanding Time Complexity

We want to understand how the time needed to find common rows between two tables grows as the tables get bigger.

How does the cost change when we find the intersection of two sets of data?

Scenario Under Consideration

Analyze the time complexity of this MySQL query that finds common rows using JOIN.

SELECT a.id, a.value
FROM tableA a
INNER JOIN tableB b ON a.id = b.id;
    

This query returns rows where the id exists in both tableA and tableB.

Identify Repeating Operations

Look for repeated work done by the database engine.

• Primary operation: Matching each row in tableA with rows in tableB by id.
• 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 the tables grows, the work to find matches grows too.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows roughly in direct proportion to the number of rows in the first table.

Final Time Complexity

Time Complexity: O(n)

This means the time to find common rows grows linearly with the size of the input tables, assuming proper indexing.

Common Mistake

[X] Wrong: "The database checks every possible pair of rows between the two tables."

[OK] Correct: With proper indexes, the database looks up matches quickly instead of comparing all pairs, so it does not do a full cross-check.

Interview Connect

Understanding how joins work and their time cost helps you explain how databases handle common tasks efficiently, a useful skill in many real projects.

Self-Check

"What if we replaced the INNER JOIN with a subquery using EXISTS? How would the time complexity change?"