Subqueries in FROM (derived tables) in PostgreSQL - Time & Space Complexity

Time Complexity: Subqueries in FROM (derived tables)

O(n)

Understanding Time Complexity

When we use subqueries inside the FROM clause, the database runs these smaller queries first before the main query.

We want to understand how the total work grows as the data size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT dt.customer_id, dt.total_orders
FROM (
  SELECT customer_id, COUNT(*) AS total_orders
  FROM orders
  GROUP BY customer_id
) AS dt
WHERE dt.total_orders > 5;
    

This query counts orders per customer in a subquery, then filters customers with more than 5 orders.

Identify Repeating Operations

• Primary operation: Scanning all rows in the orders table to count orders per customer.
• How many times: Once over all orders; then a quick filter over the grouped results.

How Execution Grows With Input

The database reads every order once to count them by customer, so if orders grow, work grows too.

Input Size (n orders)	Approx. Operations
10	About 10 reads and counts
100	About 100 reads and counts
1000	About 1000 reads and counts

Pattern observation: The work grows roughly in direct proportion to the number of orders.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in a straight line as the number of orders increases.

Common Mistake

[X] Wrong: "The subquery runs multiple times, so the time grows much faster than the data size."

[OK] Correct: The subquery runs once to prepare the data, not repeatedly, so time grows mainly with input size, not squared.

Interview Connect

Understanding how subqueries inside FROM work helps you explain query performance clearly and shows you can think about data size effects.

Self-Check

"What if the subquery included a join with another large table? How would the time complexity change?"

Practice

1. What is the main purpose of using a subquery in the FROM clause in PostgreSQL?

easy

A. To create a permanent table in the database

B. To update data in multiple tables at once

C. To delete rows from a table based on a condition

D. To create a temporary table that can be used in the main query

Solution

1. Step 1: Understand the role of subqueries in FROM

   Subqueries in the FROM clause act like temporary tables that exist only during the query execution.

2. Step 2: Compare with other options

   Updating or deleting data and creating permanent tables are not done by subqueries in FROM.

3. Final Answer:

   To create a temporary table that can be used in the main query -> Option D

4. Quick Check:

   Subquery in FROM = temporary table [OK]

Hint: Subquery in FROM = think temporary table [OK]

Common Mistakes:

• Thinking subqueries in FROM create permanent tables
• Confusing subqueries with UPDATE or DELETE statements
• Forgetting subqueries need an alias

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

easy

A. SELECT * FROM (SELECT id FROM users) AS sub;

B. SELECT * FROM users WHERE (SELECT id FROM users);

C. SELECT * FROM users JOIN (SELECT id FROM users);

D. SELECT * FROM users (SELECT id FROM users) AS sub;

Solution

1. Step 1: Identify correct subquery syntax in FROM

   The subquery must be enclosed in parentheses and given an alias using AS.

2. Step 2: Check each option

   SELECT * FROM (SELECT id FROM users) AS sub; correctly uses parentheses and alias. Others either misuse WHERE, JOIN without ON, or lack alias.

3. Final Answer:

   SELECT * FROM (SELECT id FROM users) AS sub; -> Option A

4. Quick Check:

   Subquery in FROM needs parentheses + alias [OK]

Hint: Always alias subqueries in FROM with AS [OK]

Common Mistakes:

• Omitting alias after subquery
• Using subquery in WHERE without proper syntax
• Trying to JOIN without ON condition

3. Given the tables:
users(id, name)
orders(id, user_id, amount)
What will the following query return?

SELECT sub.name, sub.total FROM (SELECT u.name, SUM(o.amount) AS total FROM users u LEFT JOIN orders o ON u.id = o.user_id GROUP BY u.name) AS sub WHERE sub.total > 100;

medium

A. Syntax error due to missing GROUP BY

B. All users with their total order amount including those with zero

C. Names of users with total order amount greater than 100

D. Empty result because no user has orders

Solution

1. Step 1: Analyze the subquery

   The subquery calculates total order amount per user using LEFT JOIN and GROUP BY user name.

2. Step 2: Apply the outer WHERE filter

   The outer query filters users whose total order amount is greater than 100.

3. Final Answer:

   Names of users with total order amount greater than 100 -> Option C

4. Quick Check:

   Subquery sums orders, outer filters total > 100 [OK]

Hint: Subquery computes totals; outer filters results [OK]

Common Mistakes:

• Ignoring GROUP BY causing syntax error
• Confusing LEFT JOIN with INNER JOIN results
• Assuming all users appear without filtering

4. Identify the error in this query:

SELECT sub.name, sub.order_count FROM (SELECT name, COUNT(*) FROM users GROUP BY name) sub;

medium

A. No error, query is correct

B. Missing alias for COUNT(*) column

C. Incorrect table name 'users'

D. Subquery missing parentheses

Solution

1. Step 1: Check subquery SELECT list

   COUNT(*) needs an alias to be referenced outside the subquery.

2. Step 2: Understand outer query references

   Outer query uses sub.order_count, but COUNT(*) column has no alias, causing error.

3. Final Answer:

   Missing alias for COUNT(*) column -> Option B

4. Quick Check:

   Aggregate columns need aliases in subqueries [OK]

Hint: Always alias aggregate columns in subqueries [OK]

Common Mistakes:

• Forgetting to alias aggregate functions
• Assuming subquery columns auto-named
• Ignoring parentheses around subquery

5. You want to find the average order amount per user but only for users who have placed more than 3 orders. Which query correctly uses a subquery in the FROM clause to achieve this?

hard

A. SELECT sub.user_id, sub.avg_amount FROM (SELECT user_id, AVG(amount) AS avg_amount, COUNT(*) AS order_count FROM orders GROUP BY user_id) AS sub WHERE sub.order_count > 3;

B. SELECT user_id, AVG(amount) FROM orders WHERE COUNT(*) > 3 GROUP BY user_id;

C. SELECT user_id, AVG(amount) FROM (SELECT * FROM orders WHERE COUNT(*) > 3) AS sub GROUP BY user_id;

D. SELECT user_id, AVG(amount) FROM orders GROUP BY user_id HAVING AVG(amount) > 3;

Solution

1. Step 1: Understand the requirement

   We need average order amount per user but only for users with more than 3 orders.

2. Step 2: Analyze each option

   SELECT sub.user_id, sub.avg_amount FROM (SELECT user_id, AVG(amount) AS avg_amount, COUNT(*) AS order_count FROM orders GROUP BY user_id) AS sub WHERE sub.order_count > 3; uses a subquery to calculate average and count per user, then filters users with order_count > 3 outside. Others misuse COUNT in WHERE or HAVING incorrectly.

3. Final Answer:

   SELECT sub.user_id, sub.avg_amount FROM (SELECT user_id, AVG(amount) AS avg_amount, COUNT(*) AS order_count FROM orders GROUP BY user_id) AS sub WHERE sub.order_count > 3; -> Option A

4. Quick Check:

   Subquery calculates aggregates; outer filters by count [OK]

Hint: Filter aggregates in outer query after subquery [OK]

Common Mistakes:

• Using COUNT(*) in WHERE clause directly
• Misplacing HAVING clause conditions
• Not aliasing subquery columns properly