Why JOINs combine related tables in MySQL - Performance Analysis

Time Complexity: Why JOINs combine related tables

O(n)

Understanding Time Complexity

When we use JOINs in SQL, we combine rows from two tables based on related columns.

We want to understand how the time to run a JOIN grows as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This query combines each order with the matching customer using the customer ID.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in the orders table, find matching rows in the customers table.
• How many times: This happens once for every order row, so as many times as there are orders.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (orders rows)	Approx. Operations
10	About 10 lookups in customers
100	About 100 lookups in customers
1000	About 1000 lookups in customers

Pattern observation: The work grows roughly in direct proportion to the number of orders.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the JOIN grows linearly with the number of rows in the first table.

Common Mistake

[X] Wrong: "JOINs always take the same time no matter how big the tables are."

[OK] Correct: The more rows in the tables, the more matching work the database must do, so time grows with input size.

Interview Connect

Understanding how JOINs scale helps you explain query performance clearly and shows you know how databases handle related data.

Self-Check

"What if the customers table has an index on customer_id? How would the time complexity change?"