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?

Practice

1. What does a scalar subquery return in MySQL?

easy

A. A list of tables

B. A single value that can be used in another query

C. Only column names

D. Multiple rows and columns

Solution

1. Step 1: Understand scalar subquery definition

   A scalar subquery returns exactly one value, not multiple rows or columns.

2. Step 2: Identify usage in queries

   This single value can be used inside another query, like in WHERE or SELECT clauses.

3. Final Answer:

   A single value that can be used in another query -> Option B

4. Quick Check:

   Scalar subquery = single value [OK]

Hint: Scalar subqueries always return one value only [OK]

Common Mistakes:

• Thinking scalar subqueries return multiple rows
• Confusing scalar subqueries with table subqueries
• Assuming scalar subqueries return column names only

2. Which of the following is the correct syntax for a scalar subquery in a SELECT statement?

easy

A. SELECT name, MAX(score) FROM scores FROM students;

B. SELECT name, MAX(score) AS max_score WHERE score > 50;

C. SELECT name, (SELECT MAX(score) FROM scores) AS max_score FROM students;

D. SELECT name, (MAX(score) FROM scores) AS max_score FROM students;

Solution

1. Step 1: Analyze correct scalar subquery syntax

   The scalar subquery must be enclosed in parentheses and return a single value, as in (SELECT MAX(score) FROM scores).

2. Step 2: Check placement in SELECT clause

   SELECT name, (SELECT MAX(score) FROM scores) AS max_score FROM students; correctly places the scalar subquery inside the SELECT list with an alias.

3. Final Answer:

   SELECT name, (SELECT MAX(score) FROM scores) AS max_score FROM students; -> Option C

4. Quick Check:

   Scalar subquery syntax = SELECT name, (SELECT MAX(score) FROM scores) AS max_score FROM students; [OK]

Hint: Scalar subqueries must be in parentheses inside SELECT or WHERE [OK]

Common Mistakes:

• Missing parentheses around subquery
• Incorrect FROM clause placement
• Using aggregate functions without subquery

3. Given the tables:
students(id, name)
scores(student_id, score)
What will this query return?

SELECT name, (SELECT AVG(score) FROM scores WHERE student_id = students.id) AS avg_score FROM students;

medium

A. Each student's name with their average score

B. The overall average score for all students repeated for each name

C. Syntax error due to subquery

D. List of student names only without scores

Solution

1. Step 1: Understand the subquery correlation

   The subquery calculates the average score for each student by matching student_id with students.id.

2. Step 2: Result of the main query

   The main query returns each student's name along with their individual average score from the subquery.

3. Final Answer:

   Each student's name with their average score -> Option A

4. Quick Check:

   Scalar subquery returns per-student average [OK]

Hint: Correlated scalar subqueries return values per row [OK]

Common Mistakes:

• Assuming subquery returns overall average for all rows
• Confusing correlated and uncorrelated subqueries
• Expecting syntax error when none exists

4. Identify the error in this query using a scalar subquery:

SELECT name, (SELECT score FROM scores) AS score FROM students;

medium

A. No error, query runs fine

B. Missing alias for subquery

C. Incorrect table name in subquery

D. Subquery returns multiple rows causing an error

Solution

1. Step 1: Analyze the subquery result

   The subquery SELECT score FROM scores returns multiple rows because no WHERE clause limits it.

2. Step 2: Understand scalar subquery requirement

   Scalar subqueries must return exactly one value; multiple rows cause an error.

3. Final Answer:

   Subquery returns multiple rows causing an error -> Option D

4. Quick Check:

   Scalar subquery must return one value [OK]

Hint: Scalar subqueries must return one value, not many [OK]

Common Mistakes:

• Ignoring multiple rows returned by subquery
• Assuming alias is mandatory for subquery
• Thinking query runs without error

5. You want to find students whose score is above the average score of all students. Which query correctly uses a scalar subquery to achieve this?

hard

A. SELECT name FROM students WHERE score > (SELECT AVG(score) FROM scores);

B. SELECT name FROM students WHERE score > SELECT AVG(score) FROM scores;

C. SELECT name FROM students WHERE (SELECT AVG(score) FROM scores) < (SELECT score FROM scores WHERE student_id = students.id);

D. SELECT name FROM students WHERE score > (SELECT score FROM scores);

Solution

1. Step 1: Understand the goal

   We want students whose individual score is greater than the average score of all students.

2. Step 2: Analyze each option

   SELECT name FROM students WHERE score > (SELECT AVG(score) FROM scores); correctly compares each student's score with the average score using a scalar subquery.

3. Final Answer:

   SELECT name FROM students WHERE score > (SELECT AVG(score) FROM scores); -> Option A

4. Quick Check:

   Scalar subquery compares average with individual score [OK]

Hint: Use scalar subquery for average, correlate for individual score [OK]

Common Mistakes:

• Missing parentheses around subqueries
• Using subquery without correlation for individual scores
• Syntax errors from missing SELECT in WHERE