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?"

Practice

1. What is the main purpose of joining tables on a primary key to a foreign key in SQL?

easy

A. To create a new table with all columns from both tables without conditions

B. To delete duplicate rows from a table

C. To combine related data from two tables based on a unique identifier

D. To update values in one table using values from another unrelated table

Solution

1. Step 1: Understand primary and foreign keys

   A primary key uniquely identifies each record in a table, and a foreign key points to that primary key in another table.

2. Step 2: Purpose of joining on these keys

   Joining on primary key to foreign key connects related records from two tables, combining their data meaningfully.

3. Final Answer:

   To combine related data from two tables based on a unique identifier -> Option C

4. Quick Check:

   Join on primary to foreign key = combine related data [OK]

Hint: Primary key links uniquely; join combines related rows [OK]

Common Mistakes:

• Thinking join deletes duplicates
• Assuming join creates unrelated combinations
• Confusing join with update or delete operations

2. Which of the following SQL JOIN statements correctly joins table Orders with Customers on the primary key CustomerID and foreign key CustomerID?

easy

A. SELECT * FROM Orders JOIN Customers ON Orders.OrderID = Customers.CustomerID;

B. SELECT * FROM Orders JOIN Customers ON Orders.OrderDate = Customers.CustomerID;

C. SELECT * FROM Orders JOIN Customers ON Orders.CustomerID = Customers.OrderID;

D. SELECT * FROM Orders JOIN Customers ON Orders.CustomerID = Customers.CustomerID;

Solution

1. Step 1: Identify correct keys for join

   The primary key in Customers is CustomerID, and Orders has CustomerID as foreign key.

2. Step 2: Match keys in JOIN condition

   The join must be ON Orders.CustomerID = Customers.CustomerID to link related records.

3. Final Answer:

   SELECT * FROM Orders JOIN Customers ON Orders.CustomerID = Customers.CustomerID; -> Option D

4. Quick Check:

   Join on matching CustomerID keys = SELECT * FROM Orders JOIN Customers ON Orders.CustomerID = Customers.CustomerID; [OK]

Hint: Join ON foreign key = primary key column names [OK]

Common Mistakes:

• Mixing up primary and foreign key columns
• Joining on unrelated columns like OrderDate
• Using wrong table columns in ON clause

3. Given tables Employees (primary key EmployeeID) and Departments (foreign key ManagerID referencing EmployeeID), what will this query return?

SELECT Employees.Name, Departments.DepartmentName FROM Employees JOIN Departments ON Employees.EmployeeID = Departments.ManagerID;

medium

A. Syntax error due to wrong join condition

B. List of employee names who manage departments with their department names

C. List of departments without any employee names

D. List of all employees with all departments regardless of manager

Solution

1. Step 1: Understand join condition

   The join matches Employees.EmployeeID to Departments.ManagerID, linking managers to their departments.

2. Step 2: Result of the join

   The query returns names of employees who are managers and the names of the departments they manage.

3. Final Answer:

   List of employee names who manage departments with their department names -> Option B

4. Quick Check:

   Join on manager ID returns managers with departments [OK]

Hint: Join foreign key to primary key shows related records [OK]

Common Mistakes:

• Thinking it returns all employees regardless of management
• Assuming syntax error due to join condition
• Expecting departments without managers

4. Consider these tables:
Products(ProductID PK, Name)
Sales(ProductID FK, Quantity)
Why does this query cause an error?

SELECT * FROM Products JOIN Sales ON Products.ID = Sales.ProductID;

medium

A. Column Products.ID does not exist, causing an error

B. Foreign key cannot be used in JOIN condition

C. JOIN syntax is incorrect, missing JOIN type

D. Sales table must be listed first in FROM clause

Solution

1. Step 1: Check column names in JOIN condition

   The Products table has ProductID as primary key, not ID.

2. Step 2: Identify cause of error

   Using Products.ID causes an error because that column does not exist.

3. Final Answer:

   Column Products.ID does not exist, causing an error -> Option A

4. Quick Check:

   Wrong column name in JOIN = error [OK]

Hint: Verify column names exactly before joining [OK]

Common Mistakes:

• Using wrong or misspelled column names
• Thinking foreign keys can't be joined
• Assuming JOIN type is mandatory

5. You have two tables:
Authors(AuthorID PK, Name)
Books(BookID PK, Title, AuthorID FK)
Write a query to list each author with the count of books they wrote, including authors with zero books.

hard

A. SELECT Authors.Name, COUNT(Books.BookID) FROM Authors LEFT JOIN Books ON Authors.AuthorID = Books.AuthorID GROUP BY Authors.Name;

B. SELECT Authors.Name, COUNT(Books.BookID) FROM Authors JOIN Books ON Authors.AuthorID = Books.AuthorID GROUP BY Authors.Name;

C. SELECT Authors.Name, COUNT(*) FROM Books JOIN Authors ON Books.AuthorID = Authors.AuthorID GROUP BY Authors.Name;

D. SELECT Authors.Name, COUNT(Books.BookID) FROM Books LEFT JOIN Authors ON Books.AuthorID = Authors.AuthorID GROUP BY Authors.Name;

Solution

1. Step 1: Use LEFT JOIN to include all authors

   LEFT JOIN keeps all authors even if they have no matching books.

2. Step 2: Count books per author

   COUNT(Books.BookID) counts books; NULLs for authors without books count as zero.

3. Final Answer:

   SELECT Authors.Name, COUNT(Books.BookID) FROM Authors LEFT JOIN Books ON Authors.AuthorID = Books.AuthorID GROUP BY Authors.Name; -> Option A

4. Quick Check:

   LEFT JOIN + COUNT on foreign key = authors with book counts [OK]

Hint: Use LEFT JOIN to include all from primary key table [OK]

Common Mistakes:

• Using INNER JOIN excludes authors with zero books
• Counting * instead of foreign key column
• Joining tables in wrong order