Scalar subqueries in MySQL - 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 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 selects each employee and uses a scalar subquery to find their 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: 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 executions
100	About 100 subquery executions
1000	About 1000 subquery executions

Pattern observation: The total work grows directly with the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the query's running time grows in a straight line as the number of employees increases.

Common Mistake

[X] Wrong: "The scalar subquery runs only once regardless of employee count."

[OK] Correct: The subquery runs separately for each employee row, so its cost adds up with more employees.

Interview Connect

Understanding how scalar subqueries affect performance 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 the time complexity change?