sql - 内置 SQL 函数的时间复杂度，例如 sum、count、avg

Question

mysql、sql server、oracle 等中的计数、求和、avg 或任何其他内置“数学”函数的时间复杂度是多少？

有人会认为调用 sum(myColumn) 是线性的。

但是 count(1) 不是。实时复杂度是怎么来的？

在一个完美的世界中，我希望总和、平均和计数为 O(1)。但我们并不住在其中之一，对吗？

Answer 1

What is the time complexity of a function such as count, sum, avg or any other of the built in "math"-functions in mysql, sql server, oracle and others?

• 在带有 MyISAM 的 MySQL 中，没有 GROUP BY 的 COUNT(*) 是 O(1)(常量)

  它存储在表元数据中。

• 在所有系统中，MAX 和MIN 没有GROUP BY 的索引表达式是O(log(n) )(对数)。

  它们是通过一次索引查找获取的。

• 聚合函数是 O(n)(线性)，当不使用 GROUP BY 或 GROUP BY 使用 哈希值

• 当 GROUP BY 使用 SORT 时，聚合函数是 O(n log(n))。

应获取、计算所有值并将其存储在状态变量中(可能存储在哈希表中)。

另外，在使用SORT时，也要对它们进行排序。