Relational model mental model in SQL - Time & Space Complexity

Time Complexity: Relational model mental model

O(n)

Understanding Time Complexity

We want to understand how the time to run queries grows as the amount of data grows in a relational database.

How does the database handle more rows and tables when we ask questions?

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT e.name, d.department_name
FROM employees e
JOIN departments d ON e.department_id = d.id
WHERE e.salary > 50000;
    

This query finds employees earning more than 50,000 and shows their department names by joining two tables.

Identify Repeating Operations

Look for repeated steps the database must do to answer the query.

• Primary operation: Scanning the employees table and matching each employee to a department.
• How many times: Once for each employee row, the database checks the salary and then finds the matching department.

How Execution Grows With Input

As the number of employees grows, the work grows too because each employee must be checked and matched.

Input Size (n)	Approx. Operations
10	About 10 checks and matches
100	About 100 checks and matches
1000	About 1000 checks and matches

Pattern observation: The work grows roughly in direct proportion to the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of employee rows.

Common Mistake

[X] Wrong: "Joining tables always takes the same time no matter how big the tables are."

[OK] Correct: The database must look at each row in the main table and find matching rows in the joined table, so more rows mean more work.

Interview Connect

Understanding how query time grows helps you explain how databases handle more data, a useful skill when discussing real-world data problems.

Self-Check

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