INNER JOIN syntax in SQL - Time & Space Complexity

Time Complexity: INNER JOIN syntax

O(n * 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 needed change when the tables have more rows?

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 employees and their department names by matching department IDs in both tables.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each employee against departments to find matching department_id.
• How many times: For each employee row, the database looks for matching department rows.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10 employees, 5 departments	About 50 checks
100 employees, 10 departments	About 1,000 checks
1,000 employees, 100 departments	About 100,000 checks

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

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows by multiplying the number of rows in the first table by the number of rows in the second table.

Common Mistake

[X] Wrong: "INNER JOIN always runs in linear time because it just matches rows once."

[OK] Correct: Actually, the database may need to compare many rows from both tables, so the work grows with both table sizes, not just one.

Interview Connect

Knowing how INNER JOIN scales helps you explain query performance clearly. It shows you understand how databases handle matching data, a useful skill in many real projects.

Self-Check

"What if we add an index on the department_id column? How would the time complexity change?"

Practice

1. What does an INNER JOIN do in SQL?

easy

A. It returns all rows from the first table only.

B. It returns rows that have matching values in both tables.

C. It returns all rows from the second table only.

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

Solution

1. Step 1: Understand the purpose of INNER JOIN

   INNER JOIN combines rows from two tables where the join condition matches in both tables.

2. Step 2: Compare options with INNER JOIN behavior

   Only the description "It returns rows that have matching values in both tables." correctly states that it returns rows with matching values in both tables.

3. Final Answer:

   It returns rows that have matching values in both tables. -> Option B

4. Quick Check:

   INNER JOIN = matching rows only [OK]

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

Common Mistakes:

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

2. Which of the following is the correct syntax for an INNER JOIN between tables Employees and Departments on the column DeptID using the ON clause?

easy

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

B. SELECT * FROM Employees JOIN Departments WHERE Employees.DeptID = Departments.DeptID;

C. SELECT * FROM Employees INNER JOIN Departments USING DeptID;

D. SELECT * FROM Employees INNER JOIN Departments ON Employees.DeptID = Departments.DeptID;

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: Check each option

   SELECT * FROM Employees INNER JOIN Departments ON Employees.DeptID = Departments.DeptID; uses correct INNER JOIN syntax with ON and =. SELECT * FROM Employees JOIN Departments WHERE Employees.DeptID = Departments.DeptID; uses WHERE instead of ON. SELECT * FROM Employees INNER JOIN Departments USING DeptID; uses USING instead of ON. SELECT * FROM Employees INNER JOIN Departments ON Employees.DeptID == Departments.DeptID; uses double equals (==), which is not valid in SQL.

3. Final Answer:

   SELECT * FROM Employees INNER JOIN Departments ON Employees.DeptID = Departments.DeptID; -> Option D

4. Quick Check:

   INNER JOIN syntax = ON with single = [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 (=)
• Using USING instead of ON

3. Given the tables:
Employees(id, name, dept_id)
Departments(dept_id, dept_name)
What is the result of this query?

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

Assuming:
Employees: (1, 'Alice', 10), (2, 'Bob', 20), (3, 'Carol', 30)
Departments: (10, 'HR'), (20, 'Sales')

medium

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

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

C. [('Alice', 'HR'), ('Bob', 'Sales'), ('Carol', NULL)]

D. [('Alice', 'HR'), ('Bob', 'Sales'), ('Carol', 'Finance')]

Solution

1. Step 1: Identify matching rows by dept_id

   Employees with dept_id 10 and 20 match Departments with same dept_id. Carol's dept_id 30 has no match.

2. Step 2: Understand INNER JOIN output

   INNER JOIN returns only rows with matching dept_id in both tables, so Carol is excluded.

3. Final Answer:

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

4. Quick Check:

   INNER JOIN excludes unmatched rows [OK]

Hint: INNER JOIN excludes rows without matching keys [OK]

Common Mistakes:

• Including unmatched rows in result
• Assuming NULL values appear for unmatched rows
• Confusing INNER JOIN with LEFT JOIN behavior

4. Identify the error in this SQL query:

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

medium

A. The join condition uses '==' instead of '='.

B. Using alias names for tables is not allowed.

C. Missing WHERE clause for filtering.

D. INNER JOIN requires USING instead of ON.

Solution

1. Step 1: Check join condition syntax

   SQL uses a single equals sign (=) for comparison, not double equals (==).

2. Step 2: Verify other parts of the query

   Aliases e and d are valid. WHERE clause is optional. INNER JOIN can use ON.

3. Final Answer:

   The join condition uses '==' instead of '='. -> Option A

4. Quick Check:

   Use = for join conditions, not == [OK]

Hint: Use single = in ON clause, not double == [OK]

Common Mistakes:

• Using == instead of = in join condition
• Thinking aliases are disallowed
• Confusing ON with WHERE clause necessity

5. You have two tables:
Orders(order_id, customer_id, amount)
Customers(customer_id, customer_name)
You want to find all customers who have placed orders and the total amount they spent.
Which query correctly uses INNER JOIN and aggregation to get this result?

hard

A. SELECT c.customer_name, SUM(o.amount) AS total_spent FROM Customers c LEFT JOIN Orders o ON c.customer_id = o.customer_id GROUP BY c.customer_name;

B. SELECT c.customer_name, o.amount FROM Customers c INNER JOIN Orders o ON c.customer_id = o.customer_id;

C. SELECT c.customer_name, SUM(o.amount) AS total_spent FROM Customers c INNER JOIN Orders o ON c.customer_id = o.customer_id GROUP BY c.customer_name;

D. SELECT customer_name, amount FROM Customers INNER JOIN Orders ON customer_id = customer_id;

Solution

1. Step 1: Understand the requirement

   We want customers who placed orders and the total amount spent, so INNER JOIN with aggregation is needed.

2. Step 2: Analyze each option

   SELECT c.customer_name, SUM(o.amount) AS total_spent FROM Customers c INNER JOIN Orders o ON c.customer_id = o.customer_id GROUP BY c.customer_name; correctly uses INNER JOIN on customer_id and sums amounts grouped by customer_name. SELECT c.customer_name, SUM(o.amount) AS total_spent FROM Customers c LEFT JOIN Orders o ON c.customer_id = o.customer_id GROUP BY c.customer_name; uses LEFT JOIN, which includes customers without orders. SELECT c.customer_name, o.amount FROM Customers c INNER JOIN Orders o ON c.customer_id = o.customer_id; does not aggregate amounts. SELECT customer_name, amount FROM Customers INNER JOIN Orders ON customer_id = customer_id; has ambiguous join condition and no aggregation.

3. Final Answer:

   SELECT c.customer_name, SUM(o.amount) AS total_spent FROM Customers c INNER JOIN Orders o ON c.customer_id = o.customer_id GROUP BY c.customer_name; -> Option C

4. Quick Check:

   INNER JOIN + GROUP BY + SUM = total spent per customer [OK]

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

Common Mistakes:

• Using LEFT JOIN instead of INNER JOIN when only matching rows needed
• Forgetting GROUP BY with aggregation
• Incorrect join condition syntax