Search code examples
sqldatabasecomplexity-theorydata-warehouse

What is the complexity of the CUBE operator in SQL?

What is the complexity (Big O notation) of a CUBE operation in SQL (Microsoft) or Oracle?

e.g.

SELECT x1, x2, SUM(x3)
FROM xyz
GROUP BY CUBE (x1, x2)
Solution

  • The complexity is:

    2^c * n log(n)

    where:

    c = number of columns in the cube
n = number of rows in the table

    The 2^c is for all combinations of the columns. n log(n) is for the aggregation operator -- which is generally equivalent to a sort in the absence of an index.

    Because c is never really that big -- for instance, 10 would generate a lot of rows -- we could treat it as a constant (in that case 1,000,000) and say the operation is essentially n log(n).