COUNT, SUM, AVG, MIN, MAX in PostgreSQL - Time & Space Complexity

Time Complexity: COUNT, SUM, AVG, MIN, MAX

O(n)

Understanding Time Complexity

When using aggregate functions like COUNT, SUM, AVG, MIN, and MAX in a database, it's important to understand how the time to get results changes as the data grows.

We want to know how the work done by these functions grows when the number of rows increases.

Scenario Under Consideration

Analyze the time complexity of the following SQL query using aggregate functions.

SELECT COUNT(*), SUM(price), AVG(price), MIN(price), MAX(price)
FROM sales;
    

This query calculates the total number of sales, the sum and average of prices, and the minimum and maximum price from the sales table.

Identify Repeating Operations

Look for repeated actions in the query execution.

• Primary operation: Scanning each row in the sales table once.
• How many times: Exactly once for all rows, since all aggregates can be computed in a single pass.

How Execution Grows With Input

As the number of rows increases, the database reads each row once to update the aggregate values.

Input Size (n)	Approx. Operations
10	10 reads and updates
100	100 reads and updates
1000	1000 reads and updates

Pattern observation: The work grows directly with the number of rows; doubling rows doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute these aggregates grows linearly with the number of rows in the table.

Common Mistake

[X] Wrong: "Aggregate functions like COUNT or SUM run instantly no matter how big the table is."

[OK] Correct: The database must look at each row to include it in the calculation, so more rows mean more work and more time.

Interview Connect

Understanding how aggregate functions scale helps you explain query performance clearly and shows you know how databases handle data as it grows.

Self-Check

"What if we added a WHERE clause that filters most rows before aggregation? How would the time complexity change?"