HAVING clause in MySQL - Time & Space Complexity

Time Complexity: HAVING clause

O(n)

Understanding Time Complexity

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

We ask: How does filtering groups after aggregation affect the work the database does?

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 department, counts how many are in each, and then keeps 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: Once for all rows, then once over each group to apply the HAVING filter.

How Execution Grows With Input

The database reads each employee row once to count them per department. Then it checks each department group to see if it meets the HAVING condition.

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

Pattern observation: The 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 as the number of rows increases.

Common Mistake

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

[OK] Correct: HAVING filters after grouping, so the database must first process all rows to form groups before filtering.

Interview Connect

Understanding how HAVING works helps you explain query performance clearly and shows you know how databases handle grouped data.

Self-Check

"What if we replaced HAVING with a WHERE clause before grouping? How would the time complexity change?"