INNER JOIN with multiple conditions in SQL - Time & Space Complexity

Time Complexity: INNER JOIN with multiple conditions

O(n * m)

Understanding Time Complexity

When we use INNER JOIN with multiple conditions, we want to know how the work grows as the tables get bigger.

We ask: How does the time to join tables change when there are more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.name
FROM tableA a
INNER JOIN tableB b
  ON a.key1 = b.key1
  AND a.key2 = b.key2
  AND a.status = b.status;
    

This query joins two tables using three conditions to match rows.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing rows from tableA to rows in tableB to find matches.
• How many times: Potentially every row in tableA is compared to every row in tableB.

How Execution Grows With Input

As the number of rows in each table grows, the number of comparisons grows quickly.

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

Pattern observation: Doubling the rows causes the work to grow much faster, because each row in one table checks many rows in the other.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly by multiplying the number of rows in both tables.

Common Mistake

[X] Wrong: "Adding more conditions in the JOIN makes it faster because it narrows matches early."

[OK] Correct: More conditions do not reduce the number of comparisons by themselves; the database still checks pairs of rows. The conditions just filter matches after comparing.

Interview Connect

Understanding how JOINs scale helps you explain query performance clearly and shows you can think about data size effects in real projects.

Self-Check

"What if one of the tables has an index on the join keys? How would the time complexity change?"