2

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

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

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

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

4

4 回答 4

5

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

  • 在MySQLwith MyISAM, COUNT(*)without GROUP BYis O(1)(constant)

    它存储在表元数据中。

  • 在所有系统中，MAX以及在没有are （对数）MIN的索引表达式上。GROUP BYO(log(n))

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

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

  • 聚合函数是O(n log(n))when GROUP BYuses SORT。

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

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

于 2009-10-09T11:14:57.983 回答
3

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

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

于 2009-10-07T21:51:13.333 回答
2

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

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

  1. 获取与连接谓词和过滤谓词匹配的行（即“WHERE 子句”）
  2. 根据 GROUP BY 子句创建行组。为没有 GROUP BY 的查询创建单个行组
  3. 对于每个行组，将聚合函数应用于组中的行。对于像 SUM、AVG、MIN、MAX 以及像 CONCAT 这样的非数字函数，有简单的 O(n) 算法，我怀疑这些算法被使用了。为步骤 #2 中创建的每个行组在输出集中创建一行
  4. 如果存在 HAVING 谓词，则使用此谓词过滤输出行

但是请注意，即使聚合函数是 O(n)，操作也可能不是。如果您创建一个笛卡尔将表连接到自身的查询，您将查看 O(n*n) 最小值以创建初始行集（步骤 #1）。排序以创建行组（步骤 #2）可能是 O(n lg n)，并且可能需要磁盘存储来进行排序操作（与仅内存操作相反），因此如果您是操纵许多行。

于 2009-10-07T21:08:40.000 回答
0

对于大数据仓库式查询，主要数据库可以并行化任务，因此有多个 CPU 处理它。因此，由于协调并行线程的成本与使用多个 CPU 的好处相权衡，因此会有一些阈值点不是很线性。

于 2009-10-09T08:38:25.340 回答