Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals

In one breath — the whole paper, compressed

Analysts summarize data along many dimensions at once, but SQL's five aggregate functions and GROUP BY produce only zero-dimensional or one-dimensional aggregates, so a six-dimensional cross-tab had to be hand-written as a 64-way union of 64 GROUP BY queries. This paper defines CUBE, an operator that computes the aggregate for every subset of the N grouping columns in a single statement, and ROLLUP, its asymmetric degenerate form that produces only the successively coarser sub-totals and adds N successively coarser grouping levels to the core group-by. Super-aggregate rows are kept relational by overloading every grouping column with an extra ALL value that denotes the set the aggregate ranged over, so a cube is an ordinary relation that composes with the rest of SQL. For computation, the paper classifies aggregate functions as distributive, algebraic, or holistic, and shows that the first two classes let super-aggregates be folded up from the core group-by's scratchpads instead of rescanning the base table. The design was adopted almost immediately: SQL Server 6.5 had already shipped CUBE and ROLLUP, and the SQL standard absorbed the syntax.

Before this paper — the world it landed in

By the mid-1990s decision-support work ran as an extract-visualize-analyze loop: pull aggregated data out of a SQL database into a file or table, render it in a spreadsheet or visualization tool, then formulate the next query. The visual end of that loop already thought in N-dimensional terms - Excel pivot tables, report writers with built-in cross-tabs, the TRANSFORM-PIVOT operator of Microsoft Access, Essbase's multidimensional arrays - while the database end offered only COUNT, SUM, MIN, MAX, AVG and a GROUP BY that returns exactly one row per group. Vendors were patching the gap incompatibly: Red Brick added Rank, N_tile, Ratio_To_Total and cumulative aggregates, while Informix Illustra and IBM's DB2 Common Server let users register new aggregate functions through Init, Iter and Final callbacks. Aggregation was not a niche concern either - the paper's own survey of standard benchmarks found 27 aggregates and 15 GROUP BYs across TPC-D's 16 queries, and aggregates even inside the OLTP benchmarks. What was missing was a relational operator with the same N-dimensional shape as the tools consuming its output.

The problem — what was actually breaking

The standard GROUP BY partitions a relation into disjoint tuple sets and returns exactly one aggregate per set, so SQL can express only zero-dimensional or one-dimensional aggregates while data analysis wants the N-dimensional generalization.
SQL92 cannot group by a computed category, so a histogram - grouping timestamps into days, or latitude and longitude into nations - has to be written indirectly by wrapping the computation in a table-valued subquery and grouping over that.
A printed roll-up report with sub-totals at each level is not relational: the empty cells under Model and Year are presumably NULLs, and NULLs cannot form a key.
The obvious repair of adding one answer column per aggregation level, as Chris Date recommended, makes the number of columns grow as the power set of the aggregated attributes - 64 columns for a 6-dimensional TPC-D query - creating difficult naming problems and very long names.
Spreadsheet pivot tables build columns out of column values rather than column names, so pivoting two columns of cardinality N and M produces N x M columns, an even larger explosion.
Writing the symmetric cross-tab in conventional SQL means unioning one GROUP BY per subset of dimensions; six dimensions require a 64-way union, and that expression is too complex for the optimizer to analyze, so most systems perform 64 scans of the data and 64 sorts or hashes.

Core ideas — the contributions, and why they work

CUBE as an N-dimensional GROUP BY

The cube operator treats each of the N aggregation attributes as a dimension of N-space: the ordinary GROUP BY computes the core, and the operator then unions in every super-aggregate obtained by replacing some subset of grouping columns with ALL. That subset structure is the power set of the aggregation columns, giving 2^N groupings of which 2^N - 1 are super-aggregates. Crucially the answer is a relation with the same schema as the core, so cube results can be selected from, joined and embedded in larger non-procedural analysis programs instead of living inside a report writer. Because the result has the product of (Ci + 1) rows, it is only slightly larger than the core group-by whenever the dimension cardinalities are large.

The ALL value as a set

Rather than exploding the schema into 2^N columns, the paper overloads each dimension's domain with one extra value, ALL, which marks a row as a super-aggregate. Following a suggestion from Joe Hellerstein, ALL is read not as an unknown but as the set the aggregate was computed over, so Model.ALL is exactly the set {Chevy, Ford}. That reading is what fixes the semantics of the relational operators on cube output - equality, ordering comparisons and IN - and an ALL() function returns the underlying set, yielding NULL when applied to any ordinary value. The authors are candid that this drags SQL into nested relations, where relations become values, and call that a major step for relational systems rather than pretending it is free.

ROLLUP for asymmetric drill-down

The full cube is overkill for a drill-down report, and parts of it can be meaningless: when the grouping attributes are functionally dependent, as year, week and day are, most cube cells make no sense. ROLLUP therefore emits only the linear chain of super-aggregates, replacing trailing columns with ALL one at a time down to the grand total, so an N-dimensional roll-up adds only N super-aggregate grouping levels instead of the exponential number of groupings in a cube. Its answer set is naturally sequential, which is exactly what cumulative aggregates like running sum and running average require, whereas a full cube is inherently non-linear and multidimensional. This is precisely the shape of the classic Sales by Model by Year by Color report the paper opens with.

An algebra of grouping operators

GROUP BY, ROLLUP and CUBE compose in a simple algebra: the CUBE of a ROLLUP is a CUBE, and the ROLLUP of a GROUP BY is a ROLLUP. The paper therefore arranges them in one compound clause with the most powerful operator innermost - group by some columns, roll up others, cube the rest - so a single statement can group on manufacturer, roll up year, month and day, and cube color and model. Because this is a syntactic extension of GROUP BY rather than a new statement, the optimizer sees one aggregation operator instead of a 64-way union of unrelated queries. The same extension generalizes the grouping list to expressions with AS correlation names, which is what finally makes histograms directly expressible.

The distributive, algebraic, holistic taxonomy

The paper's most durable contribution is a classification of aggregate functions by how much state a partial aggregate must carry. A function is distributive if there is a G such that aggregating the sub-aggregates gives the right answer, which covers COUNT, SUM, MIN and MAX, with G being SUM in the case of COUNT. It is algebraic if a fixed-size M-tuple summarizes a sub-aggregate and a final function H finishes it - average carries a sum and a count, and standard deviation, MaxN, MinN and center of mass behave the same way. It is holistic if no constant bound on the size of that state exists, as with median, mode and rank. Only the first two classes allow super-aggregates to be computed from lower-dimensional results rather than from the raw data, and the same property is what makes partitioned and parallel aggregation work.

GROUPING() and the minimalist NULL design

The authors concede that veteran SQL implementers will be terrified of a second non-value alongside NULL, since ALL requires a new keyword, an ALL NOT ALLOWED column attribute in the system catalogs, and special cases through the comparison operators. So they offer a minimalist alternative: put NULL where ALL would go, do not implement ALL(), and add a Boolean GROUPING() function that returns true exactly when a select-list element is a super-aggregate placeholder. The grand total of the running example then comes back as (NULL, NULL, NULL, 941, TRUE, TRUE, TRUE) rather than (ALL, ALL, ALL, 941). This is the design Microsoft SQL Server 6.5 actually shipped, and it is the design the SQL standard ultimately took.

Decorations, star and snowflake schemas

Cube answers usually want columns that are neither grouping columns nor aggregates - a department name sitting next to a department number - which current SQL forbids. The paper proposes allowing such decorations whenever they are functionally dependent on the aggregation columns, and returning NULL for a decoration when the super-aggregate tuple no longer determines it: continent is filled in for a specific nation, but is NULL on the rows where nation is ALL. It then names the surrounding design pattern - a central fact table of detailed events plus side tables giving each dimension's attributes and aggregation granularities, called a star schema when there is one table per dimension and a snowflake schema when the granularities are themselves broken out. The paper also warns that these granularities really form a lattice rather than a pure hierarchy, since days nest in weeks but weeks do not nest cleanly in months, quarters or years.

How it works — the mechanism, concretely

Semantics of GROUP BY CUBE

CUBE first aggregates over all the select-list attributes exactly as a standard GROUP BY does, producing the core of the cube. It then unions in each super-aggregate of the global cube, substituting ALL for the columns being collapsed, which for N attributes yields 2^N - 1 super-aggregate groupings. If the dimensions have cardinalities C1 through CN, the result relation has the product of (Ci + 1) rows, the extra value in each domain being ALL: the 18-row SALES table of the running example, with 2 models, 3 years and 3 colors, becomes a 48-row cube of 3 x 4 x 4. ROLLUP is the same construction restricted to the chain of tuples that replaces trailing columns with ALL one position at a time.

The aggregate function interface

Aggregates are pluggable through three callbacks over a private scratchpad handle, a design taken from Informix Illustra and IBM's DB2 Common Server: Init or start allocates and initializes the handle, Iter or next folds one value into it, and Final or end computes the result from the saved state and deallocates the handle. Average, for instance, initializes count and sum to zero, increments count and adds to sum for each non-null value, and divides sum by count at the end. More sophisticated systems also let an aggregate declare a computation cost so the query optimizer knows to minimize calls to expensive functions. This callback design, minus the cost declaration, became part of the proposed SQL standard, and it is what makes user-defined aggregates over cubes possible at all.

The naive 2^N algorithm

The simplest cube algorithm allocates one handle for every cube cell up front. When a tuple (x1, x2, ..., xN, v) arrives, Iter(handle, v) is called 2^N times, once for each cell whose coordinate in every position is either xi or ALL. After all input tuples are consumed, Final is invoked on each of the product-of-(Ci + 1) cells in the cube. On a base table of cardinality T this makes T x 2^N calls to Iter, and it is the only method the paper knows for holistic aggregates; roll-up has a corresponding order-N algorithm.

Computing super-aggregates from the core

For distributive functions it is far cheaper to derive super-aggregates from the core group-by than from the base table, cutting the number of Iter calls by approximately a factor of T. Hold the core as an N-dimensional array whose axes have size Ci + 1, then produce each lower-dimensional slab by projecting one dimension away: CUBE(ALL, x2, ..., xN) = F({CUBE(i, x2, ..., xN) | i = 1..C1}). N such computations give all the (N-1)-dimensional super-aggregates, and the procedure repeats one dimension at a time until the all-ALL cell is reached. Where a lower-dimensional cell can be derived from either of two slabs - aggregating the bottom row or the right column of a cross tab - both give the same answer, so the algorithm should aggregate along the axis with the smaller cardinality.

Folding scratchpads for algebraic aggregates

An algebraic aggregate cannot be built from finished sub-aggregate values, because the super-aggregate needs the intermediate state - the sum and count behind an average, not the average itself. The cube algorithm therefore keeps a handle for every cell of the core, which the group-by operation already does, and when the core completes it passes that set of handles into each (N-1)-dimensional super-aggregate. This requires one new callback, Iter_super(&handle, &handle), which folds the sub-aggregate scratchpad on the right into the super-aggregate scratchpad on the left. The handles of each level are then passed up to the super-super-aggregates, repeating until the (ALL, ALL, ..., ALL) cell has been computed, and the smallest-cardinality-first ordering rule applies at every level.

Memory, sparsity and parallelism

If the aggregates fit in memory, use arrays or hashing keyed on the aggregation columns with one aggregate value per entry, and if dimension values are large strings, keep a hashed symbol table mapping each string to an integer so values become dense and the cube can be stored as an N-dimensional array. If the cube does not fit, fall back on the standard group-by machinery - sorting or hybrid hashing to bring equal values together, then aggregating with a sequential scan; sorting suits ROLLUP anyway because users usually want the answer ordered. Super-aggregates are likely to be orders of magnitude smaller than the core, so they will very probably fit in memory even when the core does not. A sparse core should materialize only its non-null cells, indexed by hashing or a B-tree, and when the source data spans many disks or nodes each partition is aggregated in parallel and the partial results are combined by exactly the same logic as the algebraic and distributive fold.

Maintaining a materialized cube

Roughly six months of SQL Server 6.5 field experience showed customers computing and storing cubes, then defining triggers on the underlying tables so the cube is updated dynamically - which raises a question the computation sections do not answer. Insert is easy for max: visit the 2^N super-aggregate cells covering the new record and take the max of the current and new value, and the work can be shortened because a value that loses one comparison will lose in all lower dimensions. Delete is not: removing the current largest value forces 2^N cells to find a new global maximum, which seems to require recomputing the entire cube, so max is distributive for SELECT and INSERT but holistic for DELETE. The paper therefore posits orthogonal distributive, algebraic and holistic hierarchies for SELECT, INSERT and DELETE, notes that COUNT and SUM are algebraic under all three and hence cheap to maintain, and leaves the rest as open work.

What the paper showed — measurements and proofs

A survey of standard benchmarks shows aggregation is pervasive, not exotic: TPC-D's 16 queries contain 27 aggregates and 15 GROUP BYs, including one 6-dimensional and three 3-dimensional GROUP BYs; AS3AP has 20 aggregates in 23 queries; Wisconsin has 3 aggregates and 2 GROUP BYs in 18 queries; even the OLTP benchmark TPC-C contains 4 aggregates across 18 queries.
The size of a cube is the product of (Ci + 1) over the N dimensions: the 18-row SALES table with 2 models, 3 years and 3 colors yields a 48-row cube of 3 x 4 x 4. If every dimension has cardinality 4, a 4-dimensional cube is 2.4 times larger than the base GROUP BY, and since real cardinalities run to tens or hundreds the cube is normally only a little larger than the core, while an N-dimensional roll-up adds only N super-aggregate grouping levels.
Expressing a six-dimensional cross-tab in conventional SQL requires a 64-way union of 64 different GROUP BY operators, and because the result is too complex to analyze for optimization, most SQL systems will execute 64 scans of the data and 64 sorts or hashes.
The naive cube algorithm invokes Iter T x 2^N times on a base table of cardinality T and then Final once per cube cell; computing the super-aggregates from the core group-by instead reduces the number of calls by approximately a factor of T.
The taxonomy is stated with its conditions: distributive means there is a G with F({Xij}) = G({F({Xij | i = 1..I}) | j = 1..J}), holding for COUNT, SUM, MIN and MAX with G = SUM for COUNT; algebraic means a fixed M-tuple valued G plus a finishing H, covering average, standard deviation, MaxN, MinN and center of mass; holistic means no constant M bounds the sub-aggregate state, as for median, mode and rank, for which the paper knows no method better than the 2^N algorithm.
The proposal was not hypothetical at publication: Microsoft SQL Server 6.5 had supported CUBE and ROLLUP for about six months using the NULL plus GROUPING() encoding, customers were already materializing cubes and refreshing them with triggers, and the paper reports that many of these features were being added to the SQL Standard.

Limits and trade-offs — conceded and discovered

Conceded by the paper: ALL is a second non-value alongside NULL, and adding it touches many aspects of the language - a new keyword, an ALL NOT ALLOWED clause in column definitions and system catalogs, special rules for =, <, <=, >=, > and IN, and the rule that ALL participates in no aggregate except COUNT. The authors themselves retreat to the NULL plus GROUPING() encoding, which is what shipped and what the standard adopted, so the paper's most elegant idea is the one the world declined to implement.
Conceded: holistic aggregates such as median, mode and rank have no computation better than the T x 2^N naive algorithm, and the paper explicitly says it will not say more about cubes of holistic functions, arguing that users avoid them by approximating medians and quartiles statistically. That is an appeal to practice rather than a result, and it was later sketch data structures, not this paper, that gave those functions bounded state.
Conceded: the cube is exponential in the number of dimensions and can be meaningless when grouping attributes are functionally dependent, as with a cube over year, week and day. The authors investigated letting the programmer specify the exact list of super-aggregates wanted, but hit complexities related to collation, correlation and expressions and abandoned it, betting that ROLLUP and CUBE would serve most applications; later SQL added GROUPING SETS to supply precisely the arbitrary subset they gave up on.
Conceded and left open: incrementally maintaining a materialized cube is a different and harder problem than computing it, because a function's class differs per operation - max is distributive for SELECT and INSERT but delete-holistic, so deleting the current maximum can force 2^N cells and effectively the whole cube to be recomputed. The paper says only that these ideas deserve more study.
Exposed by later work: the paper gives no cost model for choosing which sub-cubes to precompute, no algorithm for sharing sorts and hash tables across the 2^N group-bys, and no treatment of the dimension granularity lattice it admits is more complex than a hierarchy. Those gaps were filled by the view-selection and multidimensional-aggregate research it can only cite in passing, and by later cube algorithms such as PipeSort, Overlap and BUC, and by storage-estimation work for aggregates in the presence of hierarchies.

What it became — the systems that inherited it

CUBE, ROLLUP, GROUPING SETS and the GROUPING() function entered SQL:1999 essentially as proposed here, and ship today in DB2, Oracle (which added GROUPING_ID for multi-column disambiguation), SQL Server, PostgreSQL since 9.5, MySQL's WITH ROLLUP, Hive, Spark SQL, BigQuery, Snowflake and DuckDB - the syntax in this paper is the syntax analysts still type. The distributive, algebraic and holistic taxonomy escaped OLAP entirely and became the standard way to reason about partial aggregation and aggregate pushdown: MapReduce combiners, Spark's reduceByKey and aggregateByKey, and Flink's AggregateFunction with createAccumulator, add, merge and getResult are the Init, Iter, Iter_super and Final interface of this paper under new names. Approximate sketches such as HyperLogLog for distinct counts and t-digest or KLL for quantiles are best read as the industry's answer to the holistic class the paper declined to solve, converting holistic functions into algebraic ones with bounded state. The materialization question raised in the maintenance section launched a whole literature: Harinarayan, Rajaraman and Ullman's greedy view selection, the PipeSort and Overlap algorithms of Agrawal et al., BUC and Dwarf, and the general theory of incremental materialized-view maintenance. Commercially the cube abstraction became a product category, from Arbor Essbase and Microsoft OLAP Services through Apache Kylin and Apache Druid, which precompute cuboids much as described here. Even the column-store warehouses that abandoned precomputed cubes kept the vocabulary this paper standardized: dimension, measure, roll-up, drill-down, star schema and snowflake schema.

In the paper’s words — verbatim

“The novelty is that cubes are relations. Consequently, the cube operator can be imbedded in more complex non-procedural data analysis programs.”

Abstract

“A six dimension cross-tab requires a 64-way union of 64 different GROUP BY operators to build the underlying representation.”

§2

“Aggregate function F() is holistic if there is no constant bound on the size of the storage needed to describe a sub-aggregate.”

§5

Vocabulary — as this paper uses it

Data cube (CUBE operator): The relation produced by aggregating a table over every subset of its N grouping columns, so each combination of dimension values, including the collapsed ones, appears as one row. The paper's point is that this is a relation, not a report format.
ALL value: A distinguished value placed in a grouping column of a super-aggregate row to mark that the column was aggregated away. The paper reads it as the set the aggregate ranged over, for example ALL(Model) = {Chevy, Ford}, rather than as an unknown like NULL.
Super-aggregate: Any cube row containing at least one ALL, that is, an aggregate over a lower-dimensional subspace of the cube. N grouping columns produce 2^N - 1 super-aggregate groupings on top of the core group-by.
ROLLUP: The asymmetric degenerate form of CUBE that replaces trailing grouping columns with ALL one at a time, producing the successively coarser sub-totals of a drill-down report. An N-dimensional roll-up adds N super-aggregate grouping levels to the core answer set; each level may contain many rows.
Cross tab: A symmetric two-dimensional aggregation displayed with row totals, column totals and a grand total. The paper shows the compact array form is exactly equivalent to the relational form that uses the ALL value, and that both generalize to N dimensions.
Distributive aggregate function: An aggregate F for which some G satisfies F({Xij}) = G({F({Xij | i}) | j}), so sub-aggregates can simply be aggregated again. COUNT, SUM, MIN and MAX are distributive, with F = G for all but COUNT, where G is SUM.
Algebraic aggregate function: An aggregate whose sub-aggregate can be summarized by a fixed-size M-tuple and completed by a function H. Average keeps a sum and a count; standard deviation, MaxN, MinN and center of mass are the paper's other examples.
Holistic aggregate function: An aggregate for which no constant bound M exists on the storage needed to describe a sub-aggregate, so super-aggregates cannot be derived from partial results. Median, mode (MostFrequent) and rank are the paper's examples.
GROUPING(): A Boolean function proposed by the paper that returns TRUE when a select-list element is a super-aggregate placeholder and FALSE otherwise. It lets a system encode ALL as NULL while still distinguishing it from a genuine NULL in the data.

On the timeline — where this sits in the story

Year1995–1997

MilestoneData Cube and OLAP relational aggregation

Problem solvedSQL GROUP BY was too limited for multidimensional roll-up, drill-down, subtotals, and cross-tabs.

How it solved itThe cube operator generalized aggregation for multidimensional OLAP queries.

Why it matteredInfluenced SQL extensions, OLAP engines, and business-intelligence query semantics.

DDIACh. 4: Storage & Retrieval

View on the timeline