Joining on primary key to foreign key in SQL - Time & Space Complexity

Time Complexity: Joining on primary key to foreign key

O(n)

Understanding Time Complexity

When we join two tables using a primary key and a foreign key, we want to know how the time to get results changes as the tables grow.

We ask: How does the work increase when there are more rows in the tables?

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 joins the orders table with the customers table using the foreign key customer_id in orders that matches the primary key customer_id in customers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in orders, find the matching row in customers.
• 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. Each order needs one lookup in customers.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the join grows linearly with the number of rows in the orders table.

Common Mistake

[X] Wrong: "Joining on keys always takes a long time because it compares every row to every other row."

[OK] Correct: Because the join uses the primary key index, it can find matching rows quickly without checking all rows, so it does not compare every pair.

Interview Connect

Understanding how joins scale helps you explain database performance clearly and shows you know how indexes speed up queries.

Self-Check

"What if the foreign key column in orders was not indexed? How would the time complexity change?"