sql - SQL中CUBE运算符的复杂度是多少？

Question

(大 O 表示法) SQL (Microsoft) 或 Oracle 中的 CUBE 操作的复杂性是多少？

例如

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).