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