Multiple table JOINs in MySQL - Time & Space Complexity

Time Complexity: Multiple table JOINs

O(n)

Understanding Time Complexity

When we join tables in a database, the time it takes depends on how many rows each table has.

We want to understand how the work grows as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT orders.id, customers.name, products.title
FROM orders
JOIN customers ON orders.customer_id = customers.id
JOIN products ON orders.product_id = products.id
WHERE customers.country = 'USA';

This query joins three tables: orders, customers, and products, to get order details for customers in the USA.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matching rows between tables during each JOIN.
• How many times: For each row in orders, the database looks up matching rows in customers and products.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 orders	About 10 lookups in customers and products each
100 orders	About 100 lookups in customers and products each
1000 orders	About 1000 lookups in customers and products each

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 query grows roughly in a straight line as the number of orders grows.

Common Mistake

[X] Wrong: "Joining more tables always makes the query take much longer, like multiplying sizes together."

[OK] Correct: Actually, the database uses indexes and smart methods to avoid checking every combination, so the time usually grows with the main table size, not the product of all tables.

Interview Connect

Understanding how joins affect time helps you explain query performance clearly and shows you know how databases handle data efficiently.

Self-Check

"What if we added a JOIN to a fourth table without indexes? How would the time complexity change?"

Practice

1. What is the main purpose of using JOIN with multiple tables in MySQL?

easy

A. To delete rows from multiple tables at once

B. To combine rows from two or more tables based on a related column

C. To create a new table from existing tables

D. To update multiple tables simultaneously

Solution

1. Step 1: Understand the role of JOIN

   JOIN is used to combine rows from two or more tables based on a related column, allowing us to see related data together.

2. Step 2: Compare with other options

   Deleting, creating, or updating tables are different SQL operations and not the main purpose of JOIN.

3. Final Answer:

   To combine rows from two or more tables based on a related column -> Option B

4. Quick Check:

   JOIN combines tables = To combine rows [OK]

Hint: JOIN connects tables by matching columns [OK]

Common Mistakes:

• Confusing JOIN with DELETE or UPDATE operations
• Thinking JOIN creates new tables permanently
• Assuming JOIN works without specifying related columns

2. Which of the following is the correct syntax to join two tables employees and departments on the column department_id?

easy

A. SELECT * FROM employees JOIN departments ON employees.department_id = departments.department_id;

B. SELECT * FROM employees JOIN departments WHERE employees.department_id = departments.department_id;

C. SELECT * FROM employees, departments ON employees.department_id = departments.department_id;

D. SELECT * FROM employees JOIN departments USING employees.department_id;

Solution

1. Step 1: Check JOIN syntax with ON clause

   The correct syntax uses JOIN followed by ON to specify the matching columns: JOIN departments ON employees.department_id = departments.department_id.

2. Step 2: Identify errors in other options

   SELECT * FROM employees JOIN departments WHERE employees.department_id = departments.department_id; uses WHERE instead of ON, which is incorrect for JOIN conditions. SELECT * FROM employees, departments ON employees.department_id = departments.department_id; uses ON without JOIN keyword properly. SELECT * FROM employees JOIN departments USING employees.department_id; uses USING incorrectly with full column name.

3. Final Answer:

   SELECT * FROM employees JOIN departments ON employees.department_id = departments.department_id; -> Option A

4. Quick Check:

   JOIN with ON = SELECT * FROM employees JOIN departments ON employees.department_id = departments.department_id; [OK]

Hint: JOIN needs ON, not WHERE, to link tables [OK]

Common Mistakes:

• Using WHERE instead of ON for JOIN condition
• Using USING with full table.column syntax
• Omitting JOIN keyword or ON clause

3. Given the tables:
students(id, name, class_id)
classes(id, class_name)
What is the output of this query?

SELECT students.name, classes.class_name FROM students JOIN classes ON students.class_id = classes.id WHERE classes.class_name = 'Math';

medium

A. Empty result because of missing WHERE clause

B. List of all students with their class names

C. List of class names only

D. List of student names who are in the Math class

Solution

1. Step 1: Understand the JOIN and WHERE clause

   The JOIN connects students with their classes by matching class_id and id. The WHERE clause filters only classes named 'Math'.

2. Step 2: Determine the output columns and rows

   The SELECT returns student names and class names only for students in 'Math' class, so the output is a list of those students with 'Math' as class_name.

3. Final Answer:

   List of student names who are in the Math class -> Option D

4. Quick Check:

   JOIN + WHERE filters = students in Math [OK]

Hint: WHERE filters after JOIN to limit rows [OK]

Common Mistakes:

• Thinking it returns all students regardless of class
• Confusing output columns with only class names
• Assuming WHERE is missing and causes empty result

4. Identify the error in this query joining orders and customers:

SELECT orders.id, customers.name FROM orders JOIN customers WHERE orders.customer_id = customers.id;

medium

A. Missing ON keyword before join condition

B. Using WHERE instead of HAVING

C. Incorrect table names

D. Missing SELECT keyword

Solution

1. Step 1: Check JOIN syntax

   The JOIN clause must be followed by ON to specify the join condition. Here, WHERE is incorrectly used instead of ON.

2. Step 2: Confirm other parts are correct

   Table names and SELECT keyword are correct. HAVING is not used for join conditions.

3. Final Answer:

   Missing ON keyword before join condition -> Option A

4. Quick Check:

   JOIN needs ON, not WHERE [OK]

Hint: JOIN requires ON before condition, not WHERE [OK]

Common Mistakes:

• Replacing ON with WHERE in JOIN
• Confusing WHERE with HAVING clause
• Ignoring syntax errors in JOIN statements

5. You have three tables:
products(id, name, category_id)
categories(id, category_name)
sales(product_id, quantity)
Which query correctly lists each product's name, its category name, and total quantity sold?

hard

A. SELECT p.name, c.category_name, SUM(s.quantity) FROM products p LEFT JOIN categories c ON p.category_id = c.id LEFT JOIN sales s ON p.id = s.product_id GROUP BY p.name;

B. SELECT p.name, c.category_name, s.quantity FROM products p JOIN categories c ON p.category_id = c.id JOIN sales s ON p.id = s.product_id;

C. SELECT p.name, c.category_name, SUM(s.quantity) FROM products p JOIN categories c ON p.category_id = c.id JOIN sales s ON p.id = s.product_id GROUP BY p.name, c.category_name;

D. SELECT p.name, c.category_name, SUM(s.quantity) FROM products p, categories c, sales s WHERE p.category_id = c.id AND p.id = s.product_id;

Solution

1. Step 1: Understand the requirement

   We need product name, category name, and total quantity sold (sum of sales.quantity) grouped by product and category.

2. Step 2: Analyze each option

   SELECT p.name, c.category_name, SUM(s.quantity) FROM products p JOIN categories c ON p.category_id = c.id JOIN sales s ON p.id = s.product_id GROUP BY p.name, c.category_name; uses JOINs with ON clauses correctly and groups by product and category names, summing quantity. SELECT p.name, c.category_name, s.quantity FROM products p JOIN categories c ON p.category_id = c.id JOIN sales s ON p.id = s.product_id; misses aggregation. SELECT p.name, c.category_name, SUM(s.quantity) FROM products p, categories c, sales s WHERE p.category_id = c.id AND p.id = s.product_id; uses implicit joins but misses GROUP BY. SELECT p.name, c.category_name, SUM(s.quantity) FROM products p LEFT JOIN categories c ON p.category_id = c.id LEFT JOIN sales s ON p.id = s.product_id GROUP BY p.name; uses LEFT JOIN but groups only by product name, missing category grouping.

3. Final Answer:

   SELECT p.name, c.category_name, SUM(s.quantity) FROM products p JOIN categories c ON p.category_id = c.id JOIN sales s ON p.id = s.product_id GROUP BY p.name, c.category_name; -> Option C

4. Quick Check:

   JOIN + GROUP BY + SUM = SELECT p.name, c.category_name, SUM(s.quantity) FROM products p JOIN categories c ON p.category_id = c.id JOIN sales s ON p.id = s.product_id GROUP BY p.name, c.category_name; [OK]

Hint: Use JOIN with GROUP BY and SUM for totals [OK]

Common Mistakes:

• Missing GROUP BY when using SUM
• Using WHERE instead of JOIN ON
• Grouping by only one column when multiple needed