mysql - SELECT DISTINCT(column) FROM table on an indexed column 的计算复杂度

Question

问题

我不是 comp sci 专业的，所以如果我混淆了术语，请原谅我。调用的计算复杂度是多少

 SELECT DISTINCT(column) FROM table

或

SELECT * FROM table GROUP BY column

在被索引的列上？它与行数或列中不同值的数量成正比。我相信这将是 O(1)*NUM_DISINCT_COLS 与 O(NUM_OF_ROWS)

背景

例如，如果我有 1000 万行，但在视觉上该列中只有 10 个不同的值/组，您可以简单地计算每个组中的最后一项，这样时间复杂度将与不同组的数量而不是行。因此，计算 100 万行和计算 100 行所花费的时间相同。我相信复杂度将是

O(1)*Number_Of_DISTINCT_ELEMENTS

但在 MySQL 的情况下，如果我有 10 个不同的组，MySQL 仍然会遍历每一行，基本上计算每个组的运行，或者它是否以一组具有相同值的行的方式设置可以在 O(1) 时间内计算每个不同的列值吗？如果不是，那么我相信这意味着复杂性是

O(NUM_ROWS)

我为什么要关心？

我的站点中有一个页面列出了消息类别的统计信息，例如未读总数、消息总数等。我可以使用 GROUP BY 和 SUM() 来计算这些信息 但我的印象是，随着消息数量的增加，这会花费更长的时间，所以我有一个每个类别的统计表。当发送或创建新消息时，我会增加 total_messages 字段。当我想查看状态页面时，我只需选择一行

SELECT total_unread_messages FROM stats WHERE category_id = x

而不是使用 GROUP BY 和/或 DISINCT 计算所有消息的实时统计数据。

在我的情况下，这两种方式对性能的影响都不大，所以这看起来像是“过早优化”的情况，但很高兴知道我什么时候做的事情是可扩展的或不可扩展的到不需要花费太多时间构建的其他选项。

Answer 1

如果你正在做:

select distinct column
from table

并且列上有一个索引，然后MySQL可以使用“松散索引扫描”(描述为here)来处理这个查询。

这应该允许引擎从索引中读取一个键，然后“跳转”到下一个键而不读取中间键(它们都是相同的)。这表明该操作不需要读取整个索引，因此通常小于 O(n)(其中 n = 表中的行数).

我怀疑找到下一个值只需要一次操作。如果整体复杂性类似于 O(m * log(n))，我不会感到惊讶，其中 m = 不同值的数量。