HAVING clause for filtering groups in SQL - Time & Space Complexity

Time Complexity: HAVING clause for filtering groups

O(n)

Understanding Time Complexity

We want to understand how the time to run a query with a HAVING clause changes as the data grows.

Specifically, how filtering groups after aggregation affects the work done.

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(*) > 5;
    

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

Identify Repeating Operations

• Primary operation: Scanning all employee rows once to group them by department.
• How many times: Once for all rows (n times, where n is number of employees).
• Secondary operation: Checking each group to apply the HAVING filter.
• How many times: Once per group (g times, where g is number of departments).

How Execution Grows With Input

The query scans every employee once, so if employees double, work roughly doubles.

Input Size (n)	Approx. Operations
10	About 10 row scans + groups checked
100	About 100 row scans + groups checked
1000	About 1000 row scans + groups checked

Pattern observation: 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 linearly with the number of rows in the table.

Common Mistake

[X] Wrong: "The HAVING clause makes the query run slower by checking every row again."

[OK] Correct: The HAVING clause only filters after grouping, so it checks groups, not every row again.

Interview Connect

Understanding how grouping and filtering groups affects query time helps you explain database performance clearly and confidently.

Self-Check

"What if we added an ORDER BY clause after HAVING? How would the time complexity change?"