1

我想知道以下两个操作的复杂性是什么。第一种情况是计数，我按我有索引的列排序，并询问低于或高于某个数字的所有值的计数，如下所示：

SELECT count(*) FROM tbl WHERE col1 > 10 ORDER BY col1;

另一种情况是关于中位数操作。中位数是指找到 (int)n/2 的行值，其中 n 是表中的行数。这方面的一个例子可能如下（再次在 col1 上有一个索引）：

SELECT median(col1) FROM tbl ORDER BY col1;

这些案例中最坏的案例复杂度是多少？

4

1 回答 1

2

这些ORDER BY条款是不必要的 - 或令人困惑的，或两者兼而有之。

SELECT COUNT(*)将返回一行（通常）。因为你有一个搜索条件，优化器可能必须对 col1 进行索引扫描（如果有一个索引以 col1 作为索引的前导列），或者进行表扫描。这是一个 O(N) 操作，其中 N 是表中的行数。

SELECT MEDIAN(col1)还将返回一行（通常）。这将是一个 O(N) 操作，再次使用索引扫描或表扫描。

'normally' 限定词在那里，因为我不确定优化器将如何处理这些ORDER BY子句。一种可能性是优化器将确定它是多余的并忽略它。另一种可能性是它会以某种方式将col1您添加ORDER BY到投影列中，将其包含在其他操作中，然后在返回结果之前将其删除。但是，这会在没有子句的情况下混合聚合和非聚合GROUP BY- 所以我认为优化器会忽略它，或者拒绝查询。但是，我还没有用 MySQL 做过实验。

FWIW，IBM Informix Dynamic Server (IDS) 产生错误 -19828：ORDER BY 列或表达式必须在此上下文中的 SELECT 列表中。

如果没有 ORDER BY 子句，上面的分析就足够准确了。请注意，对于没有条件的 SELECT COUNT(*)，服务器通常可以使用它保留的有关表的元数据在 O(1) 时间内回答查询。

于 2009-02-20T04:03:37.347 回答