ALL, ANY, SOME with subqueries in PostgreSQL - Time & Space Complexity

Time Complexity: ALL, ANY, SOME with subqueries

O(n * m)

Understanding Time Complexity

When using ALL, ANY, or SOME with subqueries, the database checks multiple values to decide if a condition is true.

We want to understand how the time needed grows as the number of values in the subquery grows.

Scenario Under Consideration

Analyze the time complexity of the following SQL query using ANY.

SELECT employee_id, salary
FROM employees
WHERE salary > ANY (
  SELECT salary
  FROM employees
  WHERE department_id = 10
);
    

This query finds employees whose salary is greater than at least one salary in department 10.

Identify Repeating Operations

The query compares each employee's salary to multiple salaries from the subquery.

• Primary operation: Comparing one salary to each salary returned by the subquery.
• How many times: For each employee, it checks against all salaries in department 10.

How Execution Grows With Input

As the number of employees (n) and the number of salaries in the subquery (m) grow, the comparisons increase.

Input Size (employees n)	Subquery Size (m)	Approx. Operations
10	5	About 50 comparisons
100	20	About 2,000 comparisons
1000	100	About 100,000 comparisons

Pattern observation: The total checks grow roughly by multiplying the number of outer rows by the number of subquery rows.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of rows checked times the number of values in the subquery.

Common Mistake

[X] Wrong: "The query only checks one value from the subquery, so it runs in constant time."

[OK] Correct: The query compares each outer row to all values returned by the subquery, so the number of comparisons grows with both sizes.

Interview Connect

Understanding how ALL, ANY, and SOME work with subqueries helps you explain query performance clearly and shows you can think about how databases handle multiple comparisons.

Self-Check

"What if the subquery used DISTINCT to reduce duplicate salaries? How would that affect the time complexity?"

Practice

1. What does the ALL keyword do in a PostgreSQL query with a subquery?

easy

A. Returns all rows from the main query regardless of the subquery.

B. Checks if a condition is true for at least one value returned by the subquery.

C. Checks if a condition is true for every value returned by the subquery.

D. Joins the main query with the subquery on matching columns.

Solution

1. Step 1: Understand the role of ALL

   The ALL keyword compares a value to every value returned by a subquery.

2. Step 2: Interpret the condition

   It returns true only if the condition holds for all values from the subquery.

3. Final Answer:

   Checks if a condition is true for every value returned by the subquery. -> Option C

4. Quick Check:

   ALL means every value must satisfy condition [OK]

Hint: ALL means every value must meet the condition [OK]

Common Mistakes:

• Confusing ALL with ANY or SOME
• Thinking ALL returns all rows without condition
• Assuming ALL works like a JOIN

2. Which of the following is the correct syntax to use ANY with a subquery in PostgreSQL?

easy

A. SELECT * FROM table WHERE column = ANY (SELECT col FROM othertable);

B. SELECT * FROM table WHERE column ANY = (SELECT col FROM othertable);

C. SELECT * FROM table WHERE ANY column = (SELECT col FROM othertable);

D. SELECT * FROM table WHERE column = (ANY SELECT col FROM othertable);

Solution

1. Step 1: Recall correct ANY syntax

   ANY is used as: column operator ANY (subquery), e.g., column = ANY (subquery).

2. Step 2: Check each option

   SELECT * FROM table WHERE column = ANY (SELECT col FROM othertable); matches correct syntax. Others have misplaced ANY or wrong order.

3. Final Answer:

   SELECT * FROM table WHERE column = ANY (SELECT col FROM othertable); -> Option A

4. Quick Check:

   ANY goes after operator and before subquery in parentheses [OK]

Hint: Use operator = ANY (subquery) syntax [OK]

Common Mistakes:

• Placing ANY before the column name
• Omitting parentheses around subquery
• Using ANY without an operator

3. Given the tables:
products(id, price)
and
discounts(min_price)
What does this query return?

SELECT id FROM products WHERE price > ALL (SELECT min_price FROM discounts);

medium

A. All product ids regardless of price.

B. Product ids with price greater than every min_price in discounts.

C. Product ids with price equal to any min_price in discounts.

D. Product ids with price greater than at least one min_price in discounts.

Solution

1. Step 1: Understand the ALL condition

   The condition price > ALL (subquery) means price must be greater than every min_price returned.

2. Step 2: Interpret the query result

   Only products with price higher than all discount min_prices are selected.

3. Final Answer:

   Product ids with price greater than every min_price in discounts. -> Option B

4. Quick Check:

   price > ALL means greater than all values [OK]

Hint: ALL means condition holds for every subquery value [OK]

Common Mistakes:

• Confusing ALL with ANY or SOME
• Thinking it returns products with price greater than some min_price
• Assuming it returns all products

4. Identify the error in this query:

SELECT name FROM employees WHERE salary > ANY SELECT bonus FROM bonuses;

medium

A. Using ANY instead of ALL causes syntax error.

B. Incorrect use of > operator with ANY.

C. Subquery should be in FROM clause, not WHERE.

D. Missing parentheses around the subquery after ANY.

Solution

1. Step 1: Check ANY syntax

   ANY must be followed by a subquery enclosed in parentheses.

2. Step 2: Identify missing parentheses

   The query lacks parentheses around SELECT bonus FROM bonuses after ANY.

3. Final Answer:

   Missing parentheses around the subquery after ANY. -> Option D

4. Quick Check:

   ANY requires parentheses around subquery [OK]

Hint: Always put subquery in parentheses after ANY [OK]

Common Mistakes:

• Omitting parentheses around subquery
• Misplacing ANY keyword
• Confusing ANY with ALL syntax

5. You want to find all customers whose order total is less than the maximum order total of any customer in the 'orders' table. Which query correctly uses ANY to achieve this?

hard

A. SELECT customer_id FROM orders WHERE total < ANY (SELECT total FROM orders);

B. SELECT customer_id FROM orders WHERE total < ALL (SELECT total FROM orders);

C. SELECT customer_id FROM orders WHERE total > ANY (SELECT total FROM orders);

D. SELECT customer_id FROM orders WHERE total = ANY (SELECT MAX(total) FROM orders);

Solution

1. Step 1: Understand the goal

   We want customers with order total less than the maximum order total of any customer.

2. Step 2: Analyze options

   SELECT customer_id FROM orders WHERE total < ANY (SELECT total FROM orders); checks if total is less than any total in orders, which includes the maximum, so it works.

3. Step 3: Why others are wrong

   SELECT customer_id FROM orders WHERE total < ALL (SELECT total FROM orders); uses ALL, meaning less than every total, which is too strict. SELECT customer_id FROM orders WHERE total > ANY (SELECT total FROM orders); checks greater than any total, wrong direction. SELECT customer_id FROM orders WHERE total = ANY (SELECT MAX(total) FROM orders); compares to MAX(total) with ANY, which is redundant and incorrect.

4. Final Answer:

   SELECT customer_id FROM orders WHERE total < ANY (SELECT total FROM orders); -> Option A

5. Quick Check:

   Use ANY to compare with multiple values including max [OK]

Hint: Use ANY to compare with multiple values including max [OK]

Common Mistakes:

• Using ALL instead of ANY for less than max
• Comparing with MAX inside ANY incorrectly
• Confusing > and < operators