Why subqueries are needed in PostgreSQL - Performance Analysis

Time Complexity: Why subqueries are needed

O(m + n)

Understanding Time Complexity

We want to understand how the time to run a query changes when it uses subqueries.

Specifically, we ask: How does adding a subquery affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of this SQL query using a subquery.

SELECT employee_id, name
FROM employees
WHERE department_id IN (
  SELECT department_id
  FROM departments
  WHERE location = 'New York'
);
    

This query finds employees who work in departments located in New York by using a subquery to get those department IDs first.

Identify Repeating Operations

Look for repeated steps in the query execution.

• Primary operation: The subquery runs first to find matching department IDs.
• How many times: The subquery runs once, then the main query checks each employee against the subquery result.

How Execution Grows With Input

As the number of departments and employees grows, the work changes like this:

Input Size (n)	Approx. Operations
10 departments, 100 employees	Subquery: 10 checks, Main query: 100 checks
100 departments, 1,000 employees	Subquery: 100 checks, Main query: 1,000 checks
1,000 departments, 10,000 employees	Subquery: 1,000 checks, Main query: 10,000 checks

Pattern observation: The subquery work grows with departments, and the main query work grows with employees.

Final Time Complexity

Time Complexity: O(m + n)

This means the total work grows roughly by adding the size of the subquery input (departments) and the main query input (employees).

Common Mistake

[X] Wrong: "The subquery runs once for each employee, so time grows like m x n."

[OK] Correct: In this case, the subquery runs only once, and its results are used to filter employees, so the work adds up, not multiplies.

Interview Connect

Understanding how subqueries affect query time helps you write efficient database queries and explain your choices clearly in real projects or interviews.

Self-Check

"What if the subquery was correlated to the main query? How would the time complexity change?"

Practice

1. Why do we use subqueries in PostgreSQL?
SELECT * FROM employees WHERE department_id IN (SELECT id FROM departments WHERE location = 'NY');

easy

A. To change data types of columns

B. To speed up the database server automatically

C. To ask a question inside another query and filter results based on it

D. To create new tables from existing ones

Solution

1. Step 1: Understand the role of the subquery

   The subquery (SELECT id FROM departments WHERE location = 'NY') finds department IDs located in NY.

2. Step 2: See how the main query uses the subquery

   The main query selects employees whose department_id matches any ID from the subquery result.

3. Final Answer:

   To ask a question inside another query and filter results based on it -> Option C

4. Quick Check:

   Subqueries filter data using inner query results [OK]

Hint: Subqueries answer inner questions to filter outer query [OK]

Common Mistakes:

• Thinking subqueries speed up queries automatically
• Confusing subqueries with table creation
• Using subqueries to change data types

2. Which of the following is the correct syntax for a subquery in PostgreSQL?

easy

A. SELECT * FROM table WHERE column == (SELECT MAX(column) FROM table);

B. SELECT * FROM table WHERE column = (SELECT MAX(column) FROM table);

C. SELECT * FROM table WHERE column = SELECT MAX(column) FROM table;

D. SELECT * FROM table WHERE column IN SELECT MAX(column) FROM table;

Solution

1. Step 1: Identify correct subquery syntax

   Subqueries must be enclosed in parentheses and used with comparison operators like = or IN.

2. Step 2: Check each option

   SELECT * FROM table WHERE column = (SELECT MAX(column) FROM table); correctly uses parentheses and = with a subquery. The other options have syntax errors like using == instead of =, omitting parentheses entirely, or missing them after IN.

3. Final Answer:

   SELECT * FROM table WHERE column = (SELECT MAX(column) FROM table); -> Option B

4. Quick Check:

   Subqueries need parentheses and proper operators [OK]

Hint: Subqueries always go inside parentheses [OK]

Common Mistakes:

• Using double equals (==) instead of single equals (=)
• Omitting parentheses around subqueries
• Using IN without parentheses

3. What will be the output of this query?

SELECT name FROM employees WHERE salary > (SELECT AVG(salary) FROM employees);

medium

A. Syntax error due to subquery

B. Names of employees earning less than the average salary

C. All employee names

D. Names of employees earning more than the average salary

Solution

1. Step 1: Understand the subquery

   The subquery (SELECT AVG(salary) FROM employees) calculates the average salary of all employees.

2. Step 2: Apply the condition in the main query

   The main query selects employee names where their salary is greater than this average.

3. Final Answer:

   Names of employees earning more than the average salary -> Option D

4. Quick Check:

   Subquery returns average; main query filters salaries above it [OK]

Hint: Subqueries can return single values to compare in main query [OK]

Common Mistakes:

• Thinking it returns employees below average
• Assuming syntax error due to subquery
• Confusing AVG with SUM

4. Identify the error in this query:

SELECT name FROM employees WHERE department_id = SELECT id FROM departments WHERE name = 'Sales';

medium

A. Missing parentheses around the subquery

B. Wrong comparison operator used

C. Subquery returns multiple rows causing error

D. Incorrect table name used

Solution

1. Step 1: Check subquery syntax

   The subquery must be enclosed in parentheses to be valid in the WHERE clause.

2. Step 2: Identify the missing parentheses

   The query misses parentheses around SELECT id FROM departments WHERE name = 'Sales', causing syntax error.

3. Final Answer:

   Missing parentheses around the subquery -> Option A

4. Quick Check:

   Subqueries need parentheses to be valid [OK]

Hint: Always put subqueries inside parentheses [OK]

Common Mistakes:

• Forgetting parentheses around subqueries
• Assuming wrong operator causes error
• Thinking table name is incorrect

5. You want to find employees who earn more than the average salary in their own department. Which query correctly uses a subquery to achieve this?

hard

A. SELECT name, salary, department_id FROM employees WHERE salary > (SELECT AVG(salary) FROM employees WHERE department_id = employees.department_id);

B. SELECT name, salary FROM employees WHERE salary > (SELECT AVG(salary) FROM employees);

C. SELECT name FROM employees WHERE salary > ALL (SELECT salary FROM employees);

D. SELECT name FROM employees WHERE salary > ANY (SELECT AVG(salary) FROM employees GROUP BY department_id);

Solution

1. Step 1: Understand the requirement

   We need to compare each employee's salary to the average salary of their own department.

2. Step 2: Analyze each option

   SELECT name, salary, department_id FROM employees WHERE salary > (SELECT AVG(salary) FROM employees WHERE department_id = employees.department_id); uses a correlated subquery that calculates average salary per employee's department. SELECT name, salary FROM employees WHERE salary > (SELECT AVG(salary) FROM employees); compares to overall average, ignoring departments. SELECT name FROM employees WHERE salary > ALL (SELECT salary FROM employees); compares salary to all salaries, not averages. SELECT name FROM employees WHERE salary > ANY (SELECT AVG(salary) FROM employees GROUP BY department_id); compares to a list of averages but uses ANY incorrectly.

3. Final Answer:

   SELECT name, salary, department_id FROM employees WHERE salary > (SELECT AVG(salary) FROM employees WHERE department_id = employees.department_id); -> Option A

4. Quick Check:

   Correlated subquery compares salary to department average [OK]

Hint: Use correlated subqueries to compare within groups [OK]

Common Mistakes:

• Comparing to overall average instead of department average
• Using ALL or ANY incorrectly with averages
• Not correlating subquery with outer query