在索引列上使用SELECT DISTINCT(column) FROM table的计算复杂度

Question

问题

我不是计算机科学专业的人，如果我混淆了术语，请原谅。调用以下内容的计算复杂度是多少？

 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()来计算这些信息，但我认为随着消息数量增加，这种方式会花费更长的时间，因此我选择为每个类别建立了一张统计表。当新消息被发送或创建时，我会增加总消息数字段。当我想查看状态页面时，我只需选择单行即可。

SELECT total_unread_messages FROM stats WHERE category_id = x

与其使用GROUP BY和/或DISINCT在所有消息中实时计算这些统计数据，不如采用其他方法。

在我的情况下，无论哪种方式的性能影响都不大，因此这似乎是一种“过早优化”的情况，但如果能知道我所做的事情是否可扩展以及其他不需要花费太多时间来构建的选项，那就太好了。

- Usman Mutawakil

Answer 1

如果你正在做：

select distinct column
from table

如果在column上有索引，那么MySQL可以使用“宽松索引扫描”（在这里描述）处理此查询。

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

我怀疑找到下一个值只需要一次操作。如果总体复杂度大约为O(m * log(n))，其中m =不同值的数量，我也不会感到惊讶。

- Gordon Linoff