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

Question

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

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

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

在一个完美的世界中，我希望 sum、avg 和 count 为 O(1)。但我们并不生活在其中之一，对吗？

Answer 1

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

• 在MySQL有MyISAM，COUNT(*)没有GROUP BY是O(1)（常数）

  它存储在表元数据中。

• 在所有系统中，MAX并且MIN对索引的表达式，而不GROUP BY是O(log(n))（对数）。

  它们是通过单个索引查找来获取的。

• 聚合函数是O(n)（线性的），当不使用GROUP BY或GROUP BY使用时HASH

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

所有值都应该被获取、计算并存储在状态变量中（可以存储在哈希表中）。

另外，在使用的时候SORT，也应该进行排序。