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

Question

一个函数，如count，sum，avg或mysql，sql -functions，oracle等中任何其他内置的“数学”函数的时间复杂度是多少？

有人会认为调用和(MyColumn)应该是线性的。

但是count(1)不是，它的真正的时间复杂度是什么？

在一个完美的世界里，我希望sum，avg和count是O(1)。但我们不是住在那里面，对吧？

Answer 1

在SQL中，聚合的数学函数复杂度是完全无关的。真正重要的是数据访问的复杂性:选择什么访问路径(表扫描、索引范围扫描、索引查找等)以及读取多少页。每个聚合的内部结构可能略有不同，但它们的工作方式几乎相同(保持运行状态并计算每个输入值的运行聚合)，并且绝对不存在两次查看输入的聚合，因此它们都是O(n)作为内部实现，其中'n‘是馈送到聚合的记录数(不一定是表中的记录数！)。

一些聚合有内部快捷方式，例如。如果可能，COUNT(*)可能会从某些系统上的元数据返回计数。

Answer 2

一个函数，如count，sum，avg或mysql，sql -functions，oracle等中任何其他内置的“数学”函数的时间复杂度是多少？

• In MySQL with MyISAM，COUNT(*) without GROUP BY is O(1) (常量)

它存储在表元数据中。

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

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

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

时

当使用SORT.时，GROUP BY

• 聚合函数为O(n log(n))

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

此外，在使用SORT时，也应该对它们进行排序。

Answer 3

注意:这是基于我对SQL查询规划器如何工作的理解的推测，可能并不完全准确。

我相信所有的聚合函数，或者至少是你上面提到的“数学”函数，都应该是O(n)。查询将大致按如下方式执行：

根据GROUP BY子句，WHERE row-GROUP匹配连接谓词和过滤谓词(即"WHERE clause")

• Create

1. -GROUP“)。为没有group BY
2. 的查询创建单个行组对于每个行组，请将聚合函数应用于该组中的行。对于像SUM，AVG，MIN，MAX这样的函数，以及像CONCAT这样的非数值函数，都有简单的O(n)算法，我怀疑这些都是用到的。在输出集中为步骤#2
3. 中创建的每个行组创建一行。如果存在HAVING谓词，请使用

过滤输出行

但是，请注意，即使聚合函数是O(n)，操作也可能不是。如果您创建一个笛卡尔连接表到其自身的查询，您将看到O(n*n)最小值，只是为了创建初始行集合(步骤#1)。排序以创建行组(步骤#2)可能是O(n lg n)，并且可能需要磁盘存储来进行排序操作(而不是仅在内存中操作)，因此如果您正在操作许多行，那么您的查询可能仍然表现不佳。