PostgreSQLquery~5 mins

Correlated subqueries execution model in PostgreSQL - Time & Space Complexity

Choose your learning style9 modes available

Time Complexity: Correlated subqueries execution model

O(n * m)

Understanding Time Complexity

When using correlated subqueries, the database runs a small query repeatedly for each row of the main query.

We want to understand how the total work grows as the main table gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT e.employee_id, e.name
FROM employees e
WHERE e.salary > (
  SELECT AVG(salary)
  FROM employees
  WHERE department_id = e.department_id
);

This query finds employees whose salary is above the average salary in their department using a correlated subquery.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

Primary operation: For each employee row, the subquery calculates the average salary for that employee's department.
How many times: The subquery runs once per employee in the main query.

How Execution Grows With Input

As the number of employees grows, the subquery runs more times, once per employee.

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

Final Time Complexity

Time Complexity: O(n * m)

This means the total work grows linearly with the number of rows in the main table times the average number of employees per department.

Common Mistake

[X] Wrong: "The subquery runs only once, so the query is very fast regardless of table size."

[OK] Correct: Because the subquery depends on each row of the main query, it runs repeatedly, increasing total work as the table grows.

Interview Connect

Understanding how correlated subqueries scale helps you write efficient queries and explain performance in real projects.

Self-Check

"What if we replaced the correlated subquery with a join and group by? How would the time complexity change?"