Scalar subquery in SELECT in SQL - Time & Space Complexity

Time Complexity: Scalar subquery in SELECT

O(n)

Understanding Time Complexity

When using a scalar subquery inside a SELECT statement, it is 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 code snippet.

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

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The scalar subquery runs once for each employee row.
• How many times: It runs as many times as there are employees (n times).

How Execution Grows With Input

Each employee causes the subquery to run once, so the total work grows directly with the number of employees.

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 increases linearly as the number of employees increases.

Final Time Complexity

Time Complexity: O(n)

This means the total time grows in direct proportion to the number of employees processed.

Common Mistake

[X] Wrong: "The subquery runs only once for all employees."

[OK] Correct: The subquery is inside the SELECT for each employee, so it runs separately for each row, not just once.

Interview Connect

Understanding how scalar subqueries affect query time helps you write efficient database queries and shows you can think about performance clearly.

Self-Check

"What if the scalar subquery was replaced by a JOIN? How would the time complexity change?"