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

Practice

1. What does the EXISTS keyword do in a SQL query?

easy

A. Checks if a subquery returns any rows and returns true or false

B. Counts the total number of rows in a table

C. Joins two tables based on a condition

D. Deletes rows from a table

Solution

1. Step 1: Understand the purpose of EXISTS

   The EXISTS keyword is used to check if a subquery returns any rows. It returns true if there is at least one row, otherwise false.

2. Step 2: Compare with other options

   Counting rows, joining tables, or deleting rows are different SQL operations unrelated to EXISTS.

3. Final Answer:

   Checks if a subquery returns any rows and returns true or false -> Option A

4. Quick Check:

   EXISTS = true if subquery has rows [OK]

Hint: EXISTS means: 'Is there at least one row?' [OK]

Common Mistakes:

• Confusing EXISTS with COUNT
• Thinking EXISTS joins tables
• Assuming EXISTS deletes data

2. Which of the following is the correct syntax to use EXISTS in a WHERE clause?

easy

A. WHERE EXISTS IN (SELECT * FROM orders WHERE customer_id = customers.id)

B. WHERE EXISTS SELECT * FROM orders WHERE customer_id = customers.id

C. WHERE EXISTS (SELECT * FROM orders WHERE customer_id = customers.id)

D. WHERE EXISTS = (SELECT * FROM orders WHERE customer_id = customers.id)

Solution

1. Step 1: Check correct EXISTS syntax

   The correct syntax requires EXISTS followed by a subquery enclosed in parentheses.

2. Step 2: Validate each option

   WHERE EXISTS (SELECT * FROM orders WHERE customer_id = customers.id) uses parentheses correctly. The other options have syntax errors or incorrect keywords.

3. Final Answer:

   WHERE EXISTS (SELECT * FROM orders WHERE customer_id = customers.id) -> Option C

4. Quick Check:

   EXISTS needs parentheses around subquery [OK]

Hint: EXISTS always followed by parentheses with a subquery [OK]

Common Mistakes:

• Omitting parentheses after EXISTS
• Using '=' or 'IN' with EXISTS
• Writing subquery outside parentheses

3. Given tables customers(id, name) and orders(id, customer_id), what does this query return?

SELECT name FROM customers WHERE EXISTS (SELECT 1 FROM orders WHERE orders.customer_id = customers.id);

medium

A. All customers including those without orders

B. All customers who have placed at least one order

C. All orders with customer names

D. An error because of invalid subquery

Solution

1. Step 1: Understand the EXISTS subquery

   The subquery checks if there is at least one order with customer_id matching the customer's id.

2. Step 2: Determine the main query result

   The main query selects customer names only if the subquery returns rows, meaning the customer has orders.

3. Final Answer:

   All customers who have placed at least one order -> Option B

4. Quick Check:

   EXISTS filters customers with orders [OK]

Hint: EXISTS filters rows having matching related rows [OK]

Common Mistakes:

• Thinking it returns all customers
• Confusing with JOIN returning orders
• Assuming syntax error in subquery

4. Identify the error in this query:

SELECT id FROM customers WHERE EXISTS SELECT * FROM orders WHERE orders.customer_id = customers.id;

medium

A. Incorrect table alias usage

B. Using SELECT * instead of SELECT 1 in EXISTS

C. Missing WHERE clause in subquery

D. Missing parentheses around the subquery after EXISTS

Solution

1. Step 1: Check EXISTS syntax

   The EXISTS keyword must be followed by a subquery enclosed in parentheses.

2. Step 2: Identify the error in the query

   The query misses parentheses around the subquery, causing a syntax error.

3. Final Answer:

   Missing parentheses around the subquery after EXISTS -> Option D

4. Quick Check:

   EXISTS requires parentheses around subquery [OK]

Hint: Always put parentheses after EXISTS [OK]

Common Mistakes:

• Omitting parentheses after EXISTS
• Thinking SELECT * is invalid in EXISTS
• Confusing alias usage

5. You want to find all customers who have placed orders only in the last 30 days. Which query correctly uses EXISTS to achieve this?

A) SELECT name FROM customers WHERE EXISTS (SELECT 1 FROM orders WHERE orders.customer_id = customers.id AND order_date >= CURRENT_DATE - INTERVAL '30 days');
B) SELECT name FROM customers WHERE EXISTS (SELECT 1 FROM orders WHERE orders.customer_id = customers.id AND order_date <= CURRENT_DATE - INTERVAL '30 days');
C) SELECT name FROM customers WHERE EXISTS (SELECT 1 FROM orders WHERE orders.customer_id = customers.id);
D) SELECT name FROM customers WHERE EXISTS (SELECT 1 FROM orders WHERE order_date >= CURRENT_DATE - INTERVAL '30 days');

hard

A. Select customers with orders in last 30 days using correct date filter

B. Select customers with orders older than 30 days

C. Select customers with any orders regardless of date

D. Select customers if any order in last 30 days ignoring customer link

Solution

1. Step 1: Understand the date filter requirement

   We want customers with orders placed in the last 30 days, so the order date must be >= current date minus 30 days.

2. Step 2: Analyze each query option

   Select customers with orders in last 30 days using correct date filter correctly filters orders by customer and date. Select customers with orders older than 30 days filters orders older than 30 days. Select customers with any orders regardless of date ignores date. Select customers if any order in last 30 days ignoring customer link ignores customer link.

3. Final Answer:

   Select customers with orders in last 30 days using correct date filter -> Option A

4. Quick Check:

   EXISTS with date filter and customer match [OK]

Hint: Add date condition inside EXISTS subquery with customer match [OK]

Common Mistakes:

• Using wrong date comparison operator
• Forgetting to link orders to customers
• Filtering orders without customer condition