HAVING for filtering groups in PostgreSQL - Time & Space Complexity

Time Complexity: HAVING for filtering groups

O(n)

Understanding Time Complexity

When we use HAVING in SQL, we filter groups after grouping data. Understanding how this affects time helps us know how query speed changes as data grows.

We want to see how the time to run a query with HAVING changes when the number of rows or groups increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT department, COUNT(*) AS employee_count
FROM employees
GROUP BY department
HAVING COUNT(*) > 10;
    

This query groups employees by their department and then filters to keep only departments with more than 10 employees.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all employee rows once to group them by department.
• How many times: Each employee row is processed once during grouping.
• Secondary operation: After grouping, filtering groups with HAVING condition is done once per group.
• How many times: Number of groups depends on distinct departments, usually much smaller than total rows.

How Execution Grows With Input

As the number of employees grows, the time to scan and group them grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 row scans and grouping steps
100	About 100 row scans and grouping steps
1000	About 1000 row scans and grouping steps

Filtering groups with HAVING happens after grouping, so its cost depends on the number of groups, which usually grows slower than total rows.

Overall, the main work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in direct proportion to the number of rows in the table.

Common Mistake

[X] Wrong: "HAVING filters rows one by one before grouping, so it reduces the work early."

[OK] Correct: HAVING filters after grouping, so all rows must be processed first to form groups before filtering happens.

Interview Connect

Understanding how grouping and filtering with HAVING affects query time helps you explain database performance clearly and shows you know how data size impacts operations.

Self-Check

"What if we added an index on the department column? How would the time complexity change?"

Practice

1. What is the main purpose of the HAVING clause in a PostgreSQL query?

easy

A. To join two tables

B. To filter rows before grouping

C. To sort the result set

D. To filter groups after aggregation

Solution

1. Step 1: Understand the role of HAVING

   The HAVING clause is used to filter groups created by GROUP BY based on aggregate conditions.

2. Step 2: Differentiate HAVING from WHERE

   WHERE filters rows before grouping, HAVING filters groups after aggregation.

3. Final Answer:

   To filter groups after aggregation -> Option D

4. Quick Check:

   HAVING filters groups = D [OK]

Hint: Remember HAVING filters groups, WHERE filters rows [OK]

Common Mistakes:

• Confusing HAVING with WHERE clause
• Thinking HAVING sorts data
• Using HAVING without GROUP BY

2. Which of the following is the correct syntax to filter groups having a total sales greater than 1000 using HAVING?

easy

A. SELECT store, SUM(sales) FROM sales_data HAVING SUM(sales) > 1000 GROUP BY store;

B. SELECT store, SUM(sales) FROM sales_data GROUP BY store HAVING SUM(sales) > 1000;

C. SELECT store, SUM(sales) FROM sales_data WHERE SUM(sales) > 1000 GROUP BY store;

D. SELECT store, SUM(sales) FROM sales_data GROUP BY store WHERE SUM(sales) > 1000;

Solution

1. Step 1: Identify correct order of clauses

   GROUP BY must come before HAVING in SQL syntax.

2. Step 2: Check aggregate usage in HAVING

   HAVING uses aggregate functions like SUM(sales) to filter groups.

3. Final Answer:

   SELECT store, SUM(sales) FROM sales_data GROUP BY store HAVING SUM(sales) > 1000; -> Option B

4. Quick Check:

   GROUP BY before HAVING = B [OK]

Hint: HAVING always follows GROUP BY clause [OK]

Common Mistakes:

• Placing HAVING before GROUP BY
• Using WHERE with aggregate functions
• Incorrect clause order

3. Given the table orders with columns customer_id and amount, what will this query return?

SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id HAVING COUNT(*) > 2;

medium

A. All customers with more than 2 orders

B. All customers with exactly 2 orders

C. All customers with less than 2 orders

D. Syntax error due to HAVING clause

Solution

1. Step 1: Understand the GROUP BY and COUNT(*)

   The query groups rows by customer_id and counts orders per customer.

2. Step 2: Apply HAVING filter

   HAVING COUNT(*) > 2 keeps only customers with more than 2 orders.

3. Final Answer:

   All customers with more than 2 orders -> Option A

4. Quick Check:

   HAVING COUNT(*) > 2 filters groups with >2 rows [OK]

Hint: HAVING filters groups by aggregate results [OK]

Common Mistakes:

• Confusing > 2 with = 2
• Thinking HAVING causes syntax error
• Ignoring GROUP BY effect

4. Identify the error in this query:

SELECT department, AVG(salary) FROM employees HAVING AVG(salary) > 50000 GROUP BY department;

medium

A. HAVING clause used before GROUP BY

B. AVG() cannot be used in HAVING

C. Missing WHERE clause before HAVING

D. No error, query is correct

Solution

1. Step 1: Check clause order

   SQL requires GROUP BY before HAVING clause.

2. Step 2: Identify error in query

   HAVING appears before GROUP BY, which is invalid syntax.

3. Final Answer:

   HAVING clause used before GROUP BY -> Option A

4. Quick Check:

   GROUP BY must precede HAVING [OK]

Hint: GROUP BY comes before HAVING always [OK]

Common Mistakes:

• Placing HAVING before GROUP BY
• Assuming AVG() not allowed in HAVING
• Confusing WHERE and HAVING

5. You have a sales table with columns region, salesperson, and amount. Write a query to find regions where the total sales exceed 10,000 but only include salespeople who individually sold more than 3,000. Which query correctly applies HAVING to achieve this?

hard

A. SELECT region, salesperson, SUM(amount) FROM sales GROUP BY region, salesperson HAVING SUM(amount) > 3000 AND SUM(amount) > 10000;

B. SELECT region, SUM(amount) FROM sales GROUP BY region HAVING SUM(amount) > 10000 AND salesperson IN (SELECT salesperson FROM sales GROUP BY salesperson HAVING SUM(amount) > 3000);

C. SELECT region, salesperson, SUM(amount) FROM sales GROUP BY region, salesperson HAVING SUM(amount) > 3000 AND region IN (SELECT region FROM sales GROUP BY region HAVING SUM(amount) > 10000);

D. SELECT region, salesperson, SUM(amount) FROM sales WHERE SUM(amount) > 3000 GROUP BY region, salesperson HAVING SUM(amount) > 10000;

Solution

1. Step 1: Understand filtering conditions

   We want regions with total sales > 10,000 and salespeople with sales > 3,000.

2. Step 2: Analyze correct logic

   Group by region and salesperson, filter salespeople with >3000 sales using HAVING SUM(amount) > 3000, and filter regions with total sales > 10000 using a subquery in HAVING: region IN (SELECT region FROM sales GROUP BY region HAVING SUM(amount) > 10000).

3. Step 3: Check HAVING usage

   This correctly applies HAVING on both salesperson and region aggregates using subquery.

4. Final Answer:

   SELECT region, salesperson, SUM(amount) FROM sales GROUP BY region, salesperson HAVING SUM(amount) > 3000 AND region IN (SELECT region FROM sales GROUP BY region HAVING SUM(amount) > 10000); -> Option C

5. Quick Check:

   Use HAVING with subqueries for multi-level group filters [OK]

Hint: Use HAVING with subqueries for multi-level group filters [OK]

Common Mistakes:

• Using WHERE with aggregate functions
• Incorrect clause order
• Combining unrelated HAVING conditions without subqueries