ROLLUP and CUBE for hierarchical totals in PostgreSQL - Time & Space Complexity

Time Complexity: ROLLUP and CUBE for hierarchical totals

O(n log n)

Understanding Time Complexity

When using ROLLUP and CUBE in SQL, we want to know how the time to get results changes as the data grows.

We ask: How does adding more data or grouping columns affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of this SQL query using ROLLUP.

SELECT region, product, SUM(sales) AS total_sales
FROM sales_data
GROUP BY ROLLUP(region, product);
    

This query calculates sales totals for each region and product, plus subtotals and a grand total.

Identify Repeating Operations

Look for repeated work done by the database.

• Primary operation: Scanning all rows in the sales_data table to sum sales.
• How many times: Once for the full data, but grouping creates multiple subtotal calculations.

How Execution Grows With Input

As the number of rows (n) grows, the database must process more data to sum.

Input Size (n)	Approx. Operations
10	About 10 sums plus grouping overhead
100	About 100 sums plus grouping overhead
1000	About 1000 sums plus grouping overhead

Pattern observation: The work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to run the query grows roughly in proportion to n log n as the data size increases, due to grouping overhead.

Common Mistake

[X] Wrong: "ROLLUP or CUBE makes the query take exponentially longer because it does many groupings."

[OK] Correct: The database efficiently computes subtotals during one pass, so the main cost is still scanning all rows once plus grouping overhead.

Interview Connect

Understanding how grouping with ROLLUP or CUBE affects performance helps you explain query costs clearly and shows you know how databases handle summaries.

Self-Check

"What if we add more columns to the ROLLUP list? How would that change the time complexity?"

Practice

1. What does the ROLLUP operator do in a PostgreSQL GROUP BY clause?

easy

A. It filters rows based on a condition before grouping.

B. It creates hierarchical subtotals from left to right for the grouped columns.

C. It generates all possible combinations of grouped columns for totals.

D. It sorts the result set after grouping.

Solution

1. Step 1: Understand ROLLUP purpose

   ROLLUP creates subtotals that roll up from the first column to the last in the GROUP BY list.

2. Step 2: Compare with other options

   CUBE creates all combinations, filtering and sorting are unrelated to ROLLUP.

3. Final Answer:

   It creates hierarchical subtotals from left to right for the grouped columns. -> Option B

4. Quick Check:

   ROLLUP = hierarchical subtotals [OK]

Hint: ROLLUP = subtotals in order of columns [OK]

Common Mistakes:

• Confusing ROLLUP with CUBE
• Thinking ROLLUP filters rows
• Assuming ROLLUP sorts results

2. Which of the following is the correct syntax to use CUBE in a PostgreSQL query?

easy

A. SELECT col1, col2, SUM(sales) FROM table CUBE BY (col1, col2);

B. SELECT col1, col2, SUM(sales) FROM table GROUP BY CUBE col1, col2;

C. SELECT col1, col2, SUM(sales) FROM table GROUP BY ROLLUP(col1, col2);

D. SELECT col1, col2, SUM(sales) FROM table GROUP BY CUBE(col1, col2);

Solution

1. Step 1: Recall correct GROUP BY syntax with CUBE

   The correct syntax is GROUP BY CUBE(col1, col2) with parentheses around columns.

2. Step 2: Identify incorrect options

   SELECT col1, col2, SUM(sales) FROM table CUBE BY (col1, col2); uses invalid 'CUBE BY', C uses ROLLUP, D misses parentheses.

3. Final Answer:

   SELECT col1, col2, SUM(sales) FROM table GROUP BY CUBE(col1, col2); -> Option D

4. Quick Check:

   GROUP BY CUBE(columns) syntax [OK]

Hint: Use GROUP BY CUBE(col1, col2) with parentheses [OK]

Common Mistakes:

• Omitting parentheses in CUBE
• Using 'CUBE BY' instead of 'GROUP BY CUBE'
• Confusing ROLLUP and CUBE syntax

3. Given the table sales with columns region, product, and amount, what will be the output rows count of this query?

SELECT region, product, SUM(amount) FROM sales GROUP BY ROLLUP(region, product);

medium

A. Number of distinct (region, product) pairs plus one subtotal per region plus one grand total row.

B. Number of distinct (region, product) pairs only.

C. Number of distinct regions only.

D. Number of distinct products only.

Solution

1. Step 1: Understand ROLLUP output rows

   ROLLUP(region, product) returns all (region, product) groups, plus subtotals per region, plus a grand total row.

2. Step 2: Count rows

   Total rows = distinct (region, product) + distinct regions (subtotals) + 1 (grand total).

3. Final Answer:

   Number of distinct (region, product) pairs plus one subtotal per region plus one grand total row. -> Option A

4. Quick Check:

   ROLLUP adds subtotals and grand total [OK]

Hint: ROLLUP adds subtotals and grand total rows [OK]

Common Mistakes:

• Ignoring subtotal and grand total rows
• Counting only distinct pairs
• Confusing ROLLUP with CUBE output

4. Identify the error in this query using CUBE:

SELECT region, product, SUM(amount) FROM sales GROUP BY CUBE region, product;

medium

A. GROUP BY cannot use CUBE with more than one column.

B. SUM(amount) cannot be used with CUBE.

C. Missing parentheses around columns in CUBE function.

D. region and product must be in ORDER BY, not GROUP BY.

Solution

1. Step 1: Check CUBE syntax

   CUBE requires parentheses around the columns: CUBE(region, product).

2. Step 2: Validate other parts

   SUM(amount) is valid, multiple columns allowed, ORDER BY is unrelated.

3. Final Answer:

   Missing parentheses around columns in CUBE function. -> Option C

4. Quick Check:

   CUBE syntax needs parentheses [OK]

Hint: Always use parentheses with CUBE columns [OK]

Common Mistakes:

• Omitting parentheses in CUBE
• Thinking SUM is invalid with CUBE
• Confusing GROUP BY and ORDER BY

5. You want to generate a report showing sales totals by region, product, and year, including all subtotals and grand totals. Which query correctly uses CUBE to achieve this?

hard

A. SELECT region, product, year, SUM(amount) FROM sales GROUP BY CUBE(region, product, year);

B. SELECT region, product, year, SUM(amount) FROM sales GROUP BY region, product, year;

C. SELECT region, product, year, SUM(amount) FROM sales GROUP BY GROUPING SETS(region, product, year);

D. SELECT region, product, year, SUM(amount) FROM sales GROUP BY ROLLUP(region, product, year);

Solution

1. Step 1: Understand the requirement

   All subtotals and grand totals for region, product, and year means all combinations of these columns.

2. Step 2: Choose correct grouping method

   CUBE generates all combinations, ROLLUP only hierarchical totals, GROUPING SETS needs explicit sets, simple GROUP BY no subtotals.

3. Final Answer:

   SELECT region, product, year, SUM(amount) FROM sales GROUP BY CUBE(region, product, year); -> Option A

4. Quick Check:

   CUBE = all combinations subtotals [OK]

Hint: Use CUBE for all subtotal combinations [OK]

Common Mistakes:

• Using ROLLUP instead of CUBE for all subtotals
• Confusing GROUPING SETS with CUBE
• Forgetting subtotals with simple GROUP BY