Какова сложность оператора CUBE в SQL?

Question

В чем сложность (обозначение Big O) операции CUBE в SQL (Microsoft) или Oracle?

например,

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

Answer 1

Сложность:

2^c * n log(n)

, где:

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

2^c для всех комбинаций столбцов .n log(n) для оператора агрегирования - который обычно эквивалентен сортировке в отсутствие индекса.

Поскольку c никогда не бывает таким большим - например, 10 будет генерировать многостроки - мы можем рассматривать его как константу (в данном случае 1 000 000) и сказать, что операция по существу n log(n).