问题
我不是计算机科学专业的，所以如果我混淆了术语，请原谅我。调用的计算复杂度是多少
SELECT DISTINCT(column) FROM table
或者
SELECT * FROM table GROUP BY column
在被索引的列上？它是否与行数或列中不同值的数量成正比。我相信那会是O(1)*NUM_DISINCT_COLSvsO(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。
在我的情况下，任何一种方式的性能影响都不是很大，所以这可能看起来像是“过早优化”的情况，但很高兴知道我什么时候做的事情是可扩展的或不可扩展的其他选项不需要太多时间来构建。