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?"

Practice

1. What does a scalar subquery return in PostgreSQL?

easy

A. A single value used inside another query

B. Multiple rows and columns

C. Only table names

D. A list of table columns

Solution

1. Step 1: Understand scalar subquery definition

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

2. Step 2: Compare options with definition

   Only A single value used inside another query describes a single value used inside another query, matching the scalar subquery concept.

3. Final Answer:

   A single value used inside another query -> Option A

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 names
• Assuming scalar subqueries return lists

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

easy

A. SELECT (SELECT MAX(price) FROM products) AS max_price;

B. SELECT MAX(price) FROM products WHERE price = (SELECT);

C. SELECT MAX(price) FROM products SELECT price;

D. SELECT MAX(price) FROM (SELECT price FROM products);

Solution

1. Step 1: Identify correct scalar subquery syntax

   The scalar subquery must be enclosed in parentheses and return a single value, used inside the main SELECT.

2. Step 2: Check each option

   SELECT (SELECT MAX(price) FROM products) AS max_price; correctly uses (SELECT MAX(price) FROM products) as a scalar subquery. Options A, B, and D have syntax errors or misuse subqueries.

3. Final Answer:

   SELECT (SELECT MAX(price) FROM products) AS max_price; -> Option A

4. Quick Check:

   Scalar subquery syntax = SELECT (SELECT MAX(price) FROM products) AS max_price; [OK]

Hint: Scalar subqueries are enclosed in parentheses inside SELECT [OK]

Common Mistakes:

• Omitting parentheses around subquery
• Using incomplete or invalid subquery syntax
• Confusing subqueries with JOINs

3. Given the tables:
products(id, name, price)
and
sales(product_id, quantity)
What will this query return?

SELECT name, (SELECT SUM(quantity) FROM sales WHERE product_id = products.id) AS total_sold FROM products;

medium

A. Syntax error due to subquery

B. Only product names without sales data

C. Sum of all sales quantities for all products

D. Each product's name with total quantity sold

Solution

1. Step 1: Understand the subquery role

   The subquery sums quantity from sales where product_id matches the current product's id, returning total sold per product.

2. Step 2: Analyze the main query output

   The main query selects product name and the scalar subquery result as total_sold for each product row.

3. Final Answer:

   Each product's name with total quantity sold -> Option D

4. Quick Check:

   Scalar subquery sums sales per product = Each product's name with total quantity sold [OK]

Hint: Scalar subquery calculates per-row related value [OK]

Common Mistakes:

• Thinking subquery sums all sales once
• Ignoring WHERE clause linking tables
• Assuming syntax error without checking carefully

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

SELECT name, (SELECT price FROM products) AS product_price FROM products;

medium

A. Missing alias for subquery

B. Incorrect table name in subquery

C. Subquery returns multiple rows causing error

D. No error, query runs fine

Solution

1. Step 1: Check subquery result cardinality

   The subquery SELECT price FROM products returns multiple prices (rows), not a single value.

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 error -> Option C

4. Quick Check:

   Scalar subquery must return one value [OK]

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

Common Mistakes:

• Ignoring multiple rows returned by subquery
• Assuming alias fixes multiple rows error
• Confusing syntax error with runtime error

5. You want to list each product's name and its price difference from the average price of all products. Which query correctly uses a scalar subquery to achieve this?

hard

A. SELECT name, price - AVG(price) FROM products;

B. SELECT name, price - (SELECT AVG(price) FROM products) AS price_diff FROM products;

C. SELECT name, price - (SELECT price FROM products) AS price_diff FROM products;

D. SELECT name, price - (SELECT SUM(price) FROM products) AS price_diff FROM products;

Solution

1. Step 1: Understand the goal

   We want each product's price minus the average price of all products.

2. Step 2: Analyze each option

   SELECT name, price - (SELECT AVG(price) FROM products) AS price_diff FROM products; correctly uses a scalar subquery to get AVG(price) once and subtracts it from each product's price. SELECT name, price - AVG(price) FROM products; lacks GROUP BY and will error. SELECT name, price - (SELECT price FROM products) AS price_diff FROM products; returns multiple prices, causing error. SELECT name, price - (SELECT SUM(price) FROM products) AS price_diff FROM products; subtracts sum, not average, which is incorrect.

3. Final Answer:

   SELECT name, price - (SELECT AVG(price) FROM products) AS price_diff FROM products; -> Option B

4. Quick Check:

   Scalar subquery for AVG(price) = SELECT name, price - (SELECT AVG(price) FROM products) AS price_diff FROM products; [OK]

Hint: Use scalar subquery for single aggregate value [OK]

Common Mistakes:

• Using aggregate without GROUP BY causing error
• Subquery returning multiple rows instead of one
• Confusing SUM with AVG in calculation