INNER JOIN with ON condition in SQL - Time & Space Complexity

Time Complexity: INNER JOIN with ON condition

O(n x m)

Understanding Time Complexity

When we use INNER JOIN with an ON condition, we combine rows from two tables based on matching values. Understanding how the time to do this grows helps us write faster queries.

We want to know how the work needed changes as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employees.name, departments.name
FROM employees
INNER JOIN departments
ON employees.department_id = departments.id;
    

This query finds all employees and their matching departments by joining on department IDs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each employee, the database looks for matching department rows.
• How many times: This happens once for every employee row.

How Execution Grows With Input

As the number of employees and departments grows, the work to find matches grows too.

Input Size (employees x departments)	Approx. Operations
10 x 5	About 50 checks
100 x 20	About 2,000 checks
1000 x 100	About 100,000 checks

Pattern observation: The number of checks grows roughly by multiplying the sizes of both tables.

Final Time Complexity

Time Complexity: O(n x m)

This means the work grows by multiplying the number of rows in the first table (n) by the number in the second table (m).

Common Mistake

[X] Wrong: "The join only looks at one table's rows, so it grows linearly with one table size."

[OK] Correct: The join must compare rows from both tables, so the total work depends on both sizes multiplied together.

Interview Connect

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

Self-Check

"What if the departments table has an index on the id column? How would that change the time complexity?"

Practice

1. What does an INNER JOIN do in SQL when used with an ON condition?

easy

A. It returns all rows from the first table regardless of matches.

B. It returns all rows from both tables, matching or not.

C. It returns all rows from the second table regardless of matches.

D. It returns only rows where the join condition matches in both tables.

Solution

1. Step 1: Understand INNER JOIN behavior

   INNER JOIN returns rows only when the join condition matches rows in both tables.

2. Step 2: Compare with other join types

   Unlike LEFT or RIGHT JOIN, INNER JOIN excludes rows without matches.

3. Final Answer:

   It returns only rows where the join condition matches in both tables. -> Option D

4. Quick Check:

   INNER JOIN = matching rows only [OK]

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

Common Mistakes:

• Thinking INNER JOIN returns unmatched rows
• Confusing INNER JOIN with LEFT JOIN
• Ignoring the ON condition effect

2. Which of the following is the correct syntax for an INNER JOIN with an ON condition between tables Employees and Departments on DepartmentID?

easy

A. SELECT * FROM Employees INNER JOIN Departments ON Employees.DepartmentID = Departments.DepartmentID;

B. SELECT * FROM Employees INNER JOIN Departments ON Employees.ID = Departments.ID;

C. SELECT * FROM Employees JOIN Departments USING DepartmentID;

D. SELECT * FROM Employees INNER JOIN Departments WHERE Employees.DepartmentID = Departments.DepartmentID;

Solution

1. Step 1: Identify correct INNER JOIN syntax

   The INNER JOIN requires the ON keyword followed by the join condition.

2. Step 2: Check the join condition correctness

   The join should be on Employees.DepartmentID = Departments.DepartmentID, not just ID or WHERE clause.

3. Final Answer:

   SELECT * FROM Employees INNER JOIN Departments ON Employees.DepartmentID = Departments.DepartmentID; -> Option A

4. Quick Check:

   INNER JOIN uses ON with condition [OK]

Hint: Use ON keyword with join condition for INNER JOIN [OK]

Common Mistakes:

• Using WHERE instead of ON for join condition
• Joining on wrong columns
• Omitting ON keyword

3. Given these tables:

Employees
ID | Name | DeptID
1 | Alice | 10
2 | Bob | 20
3 | Carol | 30

Departments
DeptID | DeptName
10 | Sales
20 | HR
40 | IT

What is the result of this query?

SELECT Employees.Name, Departments.DeptName FROM Employees INNER JOIN Departments ON Employees.DeptID = Departments.DeptID;

medium

A. [('Alice', 'Sales'), ('Bob', 'HR')]

B. [('Alice', 'Sales'), ('Bob', 'HR'), ('Carol', 'IT')]

C. [('Alice', 'Sales'), ('Carol', 'IT')]

D. [('Bob', 'HR'), ('Carol', 'IT')]

Solution

1. Step 1: Match Employees.DeptID with Departments.DeptID

   Employees have DeptIDs 10, 20, 30; Departments have 10, 20, 40.

2. Step 2: Find matching DeptIDs

   Matches are 10 and 20 only; 30 (Carol) has no matching department.

3. Final Answer:

   [('Alice', 'Sales'), ('Bob', 'HR')] -> Option A

4. Quick Check:

   INNER JOIN returns only matching DeptIDs [OK]

Hint: Only rows with matching DeptID appear in INNER JOIN result [OK]

Common Mistakes:

• Including unmatched rows like Carol's
• Confusing DeptID with ID
• Assuming all departments join

4. Consider this query:

SELECT e.Name, d.DeptName FROM Employees e INNER JOIN Departments d ON e.DeptID = d.ID;

Given Departments has column DeptID but no ID column, what is the issue?

medium

A. The query will join on wrong columns but still return rows.

B. The query will run but return no rows.

C. The query will cause a syntax error due to wrong column name.

D. The query will join correctly because aliases fix column names.

Solution

1. Step 1: Check column names in ON condition

   The query uses d.ID but Departments table has DeptID, not ID.

2. Step 2: Understand SQL error on invalid column

   Referencing a non-existent column causes a syntax or runtime error.

3. Final Answer:

   The query will cause a syntax error due to wrong column name. -> Option C

4. Quick Check:

   Wrong column in ON causes error [OK]

Hint: Verify column names in ON condition to avoid errors [OK]

Common Mistakes:

• Assuming aliases rename columns automatically
• Using wrong column names in ON clause
• Expecting empty result instead of error

5. You have two tables:

Orders
OrderID | CustomerID | Amount
1 | 101 | 50
2 | 102 | 75
3 | 103 | 100
4 | 101 | 25

Customers
CustomerID | Name
101 | John
102 | Jane
104 | Mike

Write an INNER JOIN query to find total order amount per customer name, including only customers with orders. Which query is correct?

hard

A. SELECT c.Name, SUM(o.Amount) FROM Customers c INNER JOIN Orders o ON c.CustomerID = o.CustomerID GROUP BY c.CustomerID;

B. SELECT c.Name, SUM(o.Amount) FROM Orders o INNER JOIN Customers c ON o.CustomerID = c.CustomerID GROUP BY c.Name;

C. SELECT c.Name, SUM(o.Amount) FROM Customers c LEFT JOIN Orders o ON c.CustomerID = o.CustomerID GROUP BY c.Name;

D. SELECT c.Name, SUM(o.Amount) FROM Orders o INNER JOIN Customers c ON o.CustomerID = c.CustomerID GROUP BY o.CustomerID;

Solution

1. Step 1: Understand requirement - total per customer with orders only

   INNER JOIN keeps only customers with matching orders; GROUP BY customer name to sum amounts.

2. Step 2: Check query correctness

   SELECT c.Name, SUM(o.Amount) FROM Orders o INNER JOIN Customers c ON o.CustomerID = c.CustomerID GROUP BY c.Name; joins Orders to Customers on CustomerID and groups by c.Name, matching requirement exactly.

3. Step 3: Compare other options

   SELECT c.Name, SUM(o.Amount) FROM Customers c INNER JOIN Orders o ON c.CustomerID = o.CustomerID GROUP BY c.CustomerID; groups by CustomerID but c.Name not grouped (SQL error). SELECT c.Name, SUM(o.Amount) FROM Customers c LEFT JOIN Orders o ON c.CustomerID = o.CustomerID GROUP BY c.Name; uses LEFT JOIN (includes customers without orders). SELECT c.Name, SUM(o.Amount) FROM Orders o INNER JOIN Customers c ON o.CustomerID = c.CustomerID GROUP BY o.CustomerID; groups by o.CustomerID (not customer name).

4. Final Answer:

   SELECT c.Name, SUM(o.Amount) FROM Orders o INNER JOIN Customers c ON o.CustomerID = c.CustomerID GROUP BY c.Name; -> Option B

5. Quick Check:

   INNER JOIN with GROUP BY customer name sums orders [OK]

Hint: Join Orders to Customers, group by customer name for totals [OK]

Common Mistakes:

• Using LEFT JOIN includes customers without orders
• Grouping by wrong column
• Joining tables in wrong order causing confusion