Subqueries with EXISTS in PostgreSQL - Time & Space Complexity

Time Complexity: Subqueries with EXISTS

O(n)

Understanding Time Complexity

When using EXISTS in SQL, we want to know how the query time changes as the data grows.

We ask: How many checks does the database do as tables get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT customer_id
FROM customers c
WHERE EXISTS (
  SELECT 1
  FROM orders o
  WHERE o.customer_id = c.customer_id
);

This query finds customers who have at least one order by checking if orders exist for each customer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each customer, the database checks if there is at least one matching order.
• How many times: Once per customer row in the outer query.

How Execution Grows With Input

As the number of customers grows, the database does more checks for orders.

Input Size (n customers)	Approx. Operations
10	Checks for orders 10 times
100	Checks for orders 100 times
1000	Checks for orders 1000 times

Pattern observation: The number of checks grows directly with the number of customers.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of customers checked.

Common Mistake

[X] Wrong: "EXISTS checks all orders for every customer, so it's always very slow."

[OK] Correct: The database stops checking orders as soon as it finds one match, so it doesn't always scan all orders.

Interview Connect

Understanding how EXISTS works helps you explain query efficiency clearly and shows you know how databases handle checks smartly.

Self-Check

"What if we replaced EXISTS with IN? How would the time complexity change?"