Joins in SQL in DBMS Theory - Time & Space Complexity

Time Complexity: Joins in SQL

O(n * m)

Understanding Time Complexity

When working with SQL joins, it is important to understand how the time to get results changes as the size of the tables grows.

We want to know how the number of operations increases when joining two tables.

Scenario Under Consideration

Analyze the time complexity of the following SQL join query.

SELECT *
FROM Employees e
JOIN Departments d ON e.department_id = d.id;
    

This query joins the Employees table with the Departments table using the department ID to match rows.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Matching each employee row with department rows to find matches.
• How many times: For each employee, the database checks department rows to find matching IDs.

How Execution Grows With Input

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

Input Size (Employees n, Departments m)	Approx. Operations
10, 5	About 50 checks
100, 20	About 2,000 checks
1000, 100	About 100,000 checks

Pattern observation: The number of operations grows roughly by multiplying the sizes of the two tables.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to complete the join grows roughly by multiplying the number of rows in both tables.

Common Mistake

[X] Wrong: "Joining two tables always takes time proportional to the size of just one table."

[OK] Correct: The join compares rows from both tables, so the work depends on both table sizes, not just one.

Interview Connect

Understanding how join operations scale helps you explain database performance clearly and shows you know how data size affects query speed.

Self-Check

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

Practice

1. What does an INNER JOIN do in SQL?

easy

A. Returns all rows from the right table, and matched rows from the left

B. Returns all rows from the left table, and matched rows from the right

C. Returns only rows with matching values in both tables

D. Returns all rows from both tables, matching where possible

Solution

1. Step 1: Understand INNER JOIN behavior

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

2. Step 2: Compare with other join types

   LEFT JOIN returns all from left, RIGHT JOIN all from right, FULL JOIN all from both. INNER JOIN only matched rows.

3. Final Answer:

   Returns only rows with matching values in both tables -> Option C

4. Quick Check:

   INNER JOIN = matched rows only [OK]

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

Common Mistakes:

• Confusing INNER JOIN with LEFT JOIN
• Thinking INNER JOIN returns unmatched rows
• Mixing up LEFT and RIGHT JOIN definitions

2. Which of the following is the correct syntax for a LEFT JOIN in SQL?

easy

A. SELECT * FROM table1 LEFT JOIN table2 USING (id);

B. SELECT * FROM table1 JOIN LEFT table2 ON table1.id = table2.id;

C. SELECT * FROM table1 LEFT OUTER JOIN table2 WHERE table1.id = table2.id;

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

Solution

1. Step 1: Recall LEFT JOIN syntax

   The correct syntax is: SELECT columns FROM table1 LEFT JOIN table2 ON condition;

2. Step 2: Check each option

   SELECT * FROM table1 LEFT JOIN table2 ON table1.id = table2.id; matches correct syntax. SELECT * FROM table1 JOIN LEFT table2 ON table1.id = table2.id; has wrong order. SELECT * FROM table1 LEFT OUTER JOIN table2 WHERE table1.id = table2.id; uses WHERE instead of ON. SELECT * FROM table1 LEFT JOIN table2 USING (id); uses correct syntax with parentheses.

3. Final Answer:

   SELECT * FROM table1 LEFT JOIN table2 ON table1.id = table2.id; -> Option D

4. Quick Check:

   LEFT JOIN syntax = FROM table1 LEFT JOIN table2 ON condition [OK]

Hint: LEFT JOIN uses ON, not WHERE, for join condition [OK]

Common Mistakes:

• Using WHERE instead of ON for join condition
• Incorrect order of JOIN keywords
• Confusing USING with ON without matching columns

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

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

medium

A. All employees with their department names, only if dept_id matches

B. All employees, even if they have no department

C. All departments with employees, including departments with no employees

D. All employees and departments, matched or not

Solution

1. Step 1: Analyze INNER JOIN condition

   The INNER JOIN returns rows where Employees.dept_id matches Departments.dept_id.

2. Step 2: Understand result rows

   Only employees with a matching department will appear, showing employee name and department name.

3. Final Answer:

   All employees with their department names, only if dept_id matches -> Option A

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:

• Assuming employees without departments appear
• Confusing INNER JOIN with LEFT JOIN
• Thinking unmatched departments appear

4. Identify the error in this SQL join query:

SELECT * FROM Orders o LEFT JOIN Customers c ON o.customer_id = c.id WHERE c.country = 'USA';

medium

A. The WHERE clause filters out unmatched rows, defeating LEFT JOIN purpose

B. The ON clause should use = instead of LIKE

C. LEFT JOIN should be RIGHT JOIN here

D. Missing GROUP BY clause for aggregation

Solution

1. Step 1: Understand LEFT JOIN with WHERE filter

   LEFT JOIN keeps all rows from Orders, matching Customers or NULL if no match.

2. Step 2: Effect of WHERE on joined table

   WHERE c.country = 'USA' removes rows where c is NULL (no match), so unmatched rows are excluded, negating LEFT JOIN effect.

3. Final Answer:

   The WHERE clause filters out unmatched rows, defeating LEFT JOIN purpose -> Option A

4. Quick Check:

   WHERE on joined table filters NULLs, breaks LEFT JOIN [OK]

Hint: Use ON for join filters, WHERE filters after join [OK]

Common Mistakes:

• Filtering joined table in WHERE instead of ON
• Confusing LEFT JOIN with RIGHT JOIN
• Adding unnecessary GROUP BY

5. You want to list all products and their suppliers, including products without suppliers and suppliers without products. Which join should you use?

hard

A. LEFT JOIN

B. FULL OUTER JOIN

C. RIGHT JOIN

D. INNER JOIN

Solution

1. Step 1: Understand join requirements

   We want all products and all suppliers, even if no matching row exists in the other table.

2. Step 2: Match join type to requirement

   INNER JOIN excludes unmatched rows. LEFT or RIGHT JOIN include unmatched rows from one side only. FULL OUTER JOIN includes unmatched rows from both tables.

3. Final Answer:

   FULL OUTER JOIN -> Option B

4. Quick Check:

   FULL OUTER JOIN returns all rows from both tables [OK]

Hint: Use FULL OUTER JOIN to include unmatched rows from both tables [OK]

Common Mistakes:

• Choosing INNER JOIN which excludes unmatched rows
• Using LEFT or RIGHT JOIN which include only one side unmatched
• Confusing FULL OUTER JOIN syntax