ROLLUP for subtotals in MySQL - Time & Space Complexity

Time Complexity: ROLLUP for subtotals

O(n + g)

Understanding Time Complexity

When using ROLLUP in SQL, we want to know how the time to get subtotals grows as the data grows.

We ask: How does adding more rows or grouping levels affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT category, subcategory, SUM(sales) AS total_sales
FROM sales_data
GROUP BY category, subcategory WITH ROLLUP;
    

This query groups sales by category and subcategory, then adds subtotal rows for each category and a grand total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows to aggregate sales.
• How many times: Once over all rows, then grouping and subtotal calculations for each group level.

How Execution Grows With Input

As the number of rows grows, the database scans more data. Also, more groups mean more subtotal calculations.

Input Size (n rows)	Approx. Operations
10	Scan 10 rows + subtotal for groups
100	Scan 100 rows + subtotal for groups
1000	Scan 1000 rows + subtotal for groups

Pattern observation: The scan grows linearly with rows, and subtotal steps grow with number of groups, which depends on distinct categories and subcategories.

Final Time Complexity

Time Complexity: O(n + g)

This means the work grows with the number of rows plus the number of groups for subtotals.

Common Mistake

[X] Wrong: "ROLLUP just adds a fixed small cost regardless of data size."

[OK] Correct: The subtotal calculations depend on how many groups exist, which can grow with data size, so cost is not fixed.

Interview Connect

Understanding how grouping and subtotals affect query time helps you explain performance in real projects and shows you think about data size impact.

Self-Check

"What if we added more grouping columns to the ROLLUP? How would the time complexity change?"