Time Complexity: Why aggregation summarizes data
O(n)
0
0
Why aggregation summarizes data in MySQL - Performance Analysis
Understanding Time Complexity
When we use aggregation in SQL, we combine many rows into fewer summary results.
We want to understand how the work grows as the data size grows.
Scenario Under Consideration
Analyze the time complexity of the following aggregation query.
SELECT department, COUNT(*) AS employee_count
FROM employees
GROUP BY department;
This query counts how many employees are in each department by grouping rows.
Identify Repeating Operations
Look for repeated work done by the query.
- Primary operation: Scanning each employee row once to assign it to a group.
- How many times: Once per row in the employees table.
How Execution Grows With Input
The query looks at every employee once to count them by department.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 row checks |
| 100 | About 100 row checks |
| 1000 | About 1000 row checks |
Pattern observation: The work grows directly with the number of rows.
Final Time Complexity
Time Complexity: O(n)
This means the time to summarize grows in a straight line with the number of rows.
Common Mistake
[X] Wrong: "Aggregation is instant no matter how many rows there are."
[OK] Correct: The database must still look at each row to count or summarize it, so more rows mean more work.
Interview Connect
Understanding how aggregation scales helps you explain query performance clearly and confidently.
Self-Check
"What if we added a WHERE clause to filter rows before aggregation? How would the time complexity change?"