INNER JOIN in MySQL - Time & Space Complexity

Time Complexity: INNER JOIN

O(n x m)

Understanding Time Complexity

When we use INNER JOIN in SQL, we combine rows from two tables based on matching values. Understanding how the time it takes grows as tables get bigger helps us write better queries.

We want to know: How does the work increase when the tables have more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT orders.order_id, customers.customer_name
FROM orders
INNER JOIN customers
ON orders.customer_id = customers.customer_id;
    

This query finds all orders and matches each order with the customer who made it by comparing customer IDs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in the orders table, the database looks for matching rows in the customers table.
• How many times: This matching happens once for every order row, so the number of operations depends on the size of the orders table and the customers table.

How Execution Grows With Input

As the number of orders and customers grows, the database does more work to find matches.

Input Size (orders x customers)	Approx. Operations
10 x 10	About 100 checks
100 x 100	About 10,000 checks
1000 x 1000	About 1,000,000 checks

Pattern observation: The work grows quickly as both tables get bigger, roughly multiplying their sizes.

Final Time Complexity

Time Complexity: O(n x m)

This means the time to run the join grows roughly by multiplying the number of rows in the first table (n) by the number of rows in the second table (m).

Common Mistake

[X] Wrong: "The join only looks at one table, so time grows with just one table's size."

[OK] Correct: The join must compare rows from both tables, so the total work depends on both tables' sizes together, not just one.

Interview Connect

Knowing how joins scale helps you explain your choices clearly and shows you understand how databases handle data. This skill is useful anytime you work with data or build apps that use databases.

Self-Check

"What if we added an index on the join column? How would the time complexity change?"