Scalar subqueries in PostgreSQL - Time & Space Complexity

Time Complexity: Scalar subqueries

O(n)

Understanding Time Complexity

When using scalar subqueries in SQL, it's important to understand how the query's running time changes as the data grows.

We want to know how many times the subquery runs and how that affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a scalar subquery.

SELECT e.employee_id, e.name,
       (SELECT d.department_name
        FROM departments d
        WHERE d.department_id = e.department_id) AS dept_name
FROM employees e;
    

This query lists employees and uses a scalar subquery to find each employee's department name.

Identify Repeating Operations

Look for repeated actions in the query.

• Primary operation: The scalar subquery runs once for each employee row.
• How many times: Equal to the number of employees (n).

How Execution Grows With Input

As the number of employees grows, the subquery runs more times, increasing total work.

Input Size (n)	Approx. Operations
10	About 10 subquery runs
100	About 100 subquery runs
1000	About 1000 subquery runs

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

Final Time Complexity

Time Complexity: O(n)

This means the query's work grows linearly with the number of employees.

Common Mistake

[X] Wrong: "The scalar subquery runs just once, so it doesn't affect performance much."

[OK] Correct: The subquery runs once for every employee row, so its cost adds up as the data grows.

Interview Connect

Understanding how scalar subqueries scale helps you write efficient queries and explain your reasoning clearly in interviews.

Self-Check

"What if we replaced the scalar subquery with a JOIN? How would that change the time complexity?"