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