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

Practice

1. What does an INNER JOIN do in MySQL?

easy

A. Combines rows from two tables where matching values exist in both tables.

B. Returns all rows from the first table regardless of matches.

C. Returns all rows from the second table regardless of matches.

D. Combines rows even if there is no matching value in either table.

Solution

1. Step 1: Understand INNER JOIN purpose

   INNER JOIN returns rows only when there is a match in both tables based on the join condition.

2. Step 2: Compare options with definition

   Combines rows from two tables where matching values exist in both tables. correctly describes this behavior. Options A, C, and D describe other join types or incorrect behavior.

3. Final Answer:

   Combines rows from two tables where matching values exist in both tables. -> Option A

4. Quick Check:

   INNER JOIN = matching rows only [OK]

Hint: INNER JOIN returns only rows with matching keys in both tables [OK]

Common Mistakes:

• Confusing INNER JOIN with LEFT or RIGHT JOIN
• Thinking INNER JOIN returns unmatched rows
• Assuming INNER JOIN returns all rows from one table

2. Which of the following is the correct syntax for an INNER JOIN in MySQL?

easy

A. SELECT * FROM table1 INNER JOIN table2 ON table1.id = table2.id;

B. SELECT * FROM table1 INNER JOIN table2 WHERE table1.id = table2.id;

C. SELECT * FROM table1 INNER JOIN table2 USING table1.id;

D. SELECT * FROM table1 INNER JOIN table2 ON table1.id == table2.id;

Solution

1. Step 1: Review INNER JOIN syntax

   The correct syntax uses INNER JOIN with ON and a single equals sign (=) for comparison.

2. Step 2: Analyze each option

   SELECT * FROM table1 INNER JOIN table2 ON table1.id = table2.id; uses correct syntax. SELECT * FROM table1 INNER JOIN table2 WHERE table1.id = table2.id; uses WHERE instead of ON, which is incorrect for JOIN conditions. SELECT * FROM table1 INNER JOIN table2 USING table1.id; uses USING with table prefix which is invalid; USING requires unqualified column names. SELECT * FROM table1 INNER JOIN table2 ON table1.id == table2.id; uses double equals (==) which is invalid in SQL.

3. Final Answer:

   SELECT * FROM table1 INNER JOIN table2 ON table1.id = table2.id; -> Option A

4. Quick Check:

   INNER JOIN syntax uses ON with = [OK]

Hint: Use ON with single = for INNER JOIN conditions [OK]

Common Mistakes:

• Using WHERE instead of ON for join condition
• Using double equals (==) instead of single equals (=)
• Confusing USING syntax with ON syntax

3. Given two tables:
Employees(id, name, dept_id)
Departments(dept_id, dept_name)
What will this query return?

SELECT Employees.name, Departments.dept_name FROM Employees INNER JOIN Departments ON Employees.dept_id = Departments.dept_id;

medium

A. All departments with employees, even if no employees exist.

B. All employees, even if they have no department.

C. An error because dept_id is ambiguous.

D. All employees with their department names, only if department exists.

Solution

1. Step 1: Understand INNER JOIN effect on these tables

   The INNER JOIN returns rows where Employees.dept_id matches Departments.dept_id, so only employees with existing departments appear.

2. Step 2: Analyze query output

   The query selects employee names and their department names only for matching dept_id pairs. Employees without a department are excluded.

3. Final Answer:

   All employees with their department names, only if department exists. -> Option D

4. Quick Check:

   INNER JOIN filters to matching dept_id rows [OK]

Hint: INNER JOIN shows only matching rows from both tables [OK]

Common Mistakes:

• Thinking all employees appear even without departments
• Confusing INNER JOIN with LEFT JOIN
• Assuming ambiguous column error without aliasing

4. Identify the error in this query:

SELECT e.name, d.dept_name FROM Employees e INNER JOIN Departments d ON e.dept_id = d.id;

medium

A. Missing WHERE clause for join condition.

B. Column d.id does not exist; should be d.dept_id.

C. Alias 'e' is not allowed in INNER JOIN.

D. Using INNER JOIN without SELECT * causes error.

Solution

1. Step 1: Check join condition columns

   The join condition uses d.id, but Departments table has dept_id column, not id.

2. Step 2: Identify correct column name

   It should be d.dept_id to match Employees.dept_id. Other options are incorrect because aliasing is allowed, WHERE is not needed for JOIN, and SELECT * is not mandatory.

3. Final Answer:

   Column d.id does not exist; should be d.dept_id. -> Option B

4. Quick Check:

   Join columns must exist and match [OK]

Hint: Check column names in JOIN condition carefully [OK]

Common Mistakes:

• Using wrong column names in ON clause
• Thinking WHERE is required for JOIN
• Believing aliases are not allowed

5. You have two tables:
Orders(order_id, customer_id, amount)
Customers(customer_id, name)
You want to find customers who placed orders over 100 dollars. Which query correctly uses INNER JOIN to get customer names and order amounts over 100?

hard

A. SELECT Customers.name, Orders.amount FROM Orders INNER JOIN Customers ON Orders.customer_id = Customers.customer_id WHERE Orders.amount < 100;

B. SELECT Customers.name, Orders.amount FROM Customers LEFT JOIN Orders ON Customers.customer_id = Orders.customer_id WHERE Orders.amount > 100;

C. SELECT Customers.name, Orders.amount FROM Customers INNER JOIN Orders ON Customers.customer_id = Orders.customer_id WHERE Orders.amount > 100;

D. SELECT Customers.name, Orders.amount FROM Orders INNER JOIN Customers ON Orders.customer_id = Customers.customer_id WHERE Orders.amount >= 100;

Solution

1. Step 1: Understand the requirement

   We want customers with orders over 100 dollars, so filter Orders.amount > 100.

2. Step 2: Check INNER JOIN usage and filter

   SELECT Customers.name, Orders.amount FROM Customers INNER JOIN Orders ON Customers.customer_id = Orders.customer_id WHERE Orders.amount > 100; correctly joins Customers and Orders on customer_id and filters orders with amount > 100. SELECT Customers.name, Orders.amount FROM Customers LEFT JOIN Orders ON Customers.customer_id = Orders.customer_id WHERE Orders.amount > 100; uses LEFT JOIN instead of INNER JOIN. SELECT Customers.name, Orders.amount FROM Orders INNER JOIN Customers ON Orders.customer_id = Customers.customer_id WHERE Orders.amount >= 100; uses >= 100 which includes 100, not strictly over 100. SELECT Customers.name, Orders.amount FROM Orders INNER JOIN Customers ON Orders.customer_id = Customers.customer_id WHERE Orders.amount < 100; filters for amount < 100, opposite of requirement.

3. Final Answer:

   SELECT Customers.name, Orders.amount FROM Customers INNER JOIN Orders ON Customers.customer_id = Orders.customer_id WHERE Orders.amount > 100; -> Option C

4. Quick Check:

   INNER JOIN + filter amount > 100 = SELECT Customers.name, Orders.amount FROM Customers INNER JOIN Orders ON Customers.customer_id = Orders.customer_id WHERE Orders.amount > 100; [OK]

Hint: Use INNER JOIN with WHERE to filter matching rows [OK]

Common Mistakes:

• Using LEFT JOIN instead of INNER JOIN
• Using wrong comparison operator in WHERE
• Filtering on wrong table or column