GROUPING SETS for multiple groupings in PostgreSQL - Time & Space Complexity

Time Complexity: GROUPING SETS for multiple groupings

O(n * k)

Understanding Time Complexity

When using GROUPING SETS in SQL, we want to know how the query time changes as the data grows.

We ask: How does the number of rows and grouping sets affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of this GROUPING SETS query.

SELECT department, role, COUNT(*)
FROM employees
GROUP BY GROUPING SETS (
  (department),
  (role),
  (department, role)
);

This query counts employees grouped by department, by role, and by both together.

Identify Repeating Operations

Look for repeated work in the query.

• Primary operation: Scanning all employee rows once.
• How many times: The database processes each row once but computes aggregates for each grouping set.

How Execution Grows With Input

As the number of employees grows, the database reads more rows.

Input Size (n)	Approx. Operations
10	About 30 grouping operations (10 rows x 3 grouping sets)
100	About 300 grouping operations
1000	About 3000 grouping operations

Pattern observation: The work grows roughly linearly with the number of rows and the number of grouping sets.

Final Time Complexity

Time Complexity: O(n * k)

This means the time grows with the number of rows (n) times the number of grouping sets (k).

Common Mistake

[X] Wrong: "GROUPING SETS only scan the data once, so time is always O(n)."

[OK] Correct: While the data is scanned once, the database must compute aggregates for each grouping set, multiplying the work by the number of sets.

Interview Connect

Understanding how GROUPING SETS affect query time helps you explain performance in real projects and shows you can think about how SQL scales.

Self-Check

What if we added more grouping sets to the query? How would the time complexity change?