请求详解SQL中DISTINCT关键字的运行机制与时间复杂度

一、DISTINCT的核心运行机制 #

DISTINCT的本质是从查询结果集中剔除重复行，不同数据库会根据数据场景选择不同的底层实现策略，常见的有三种：

• 排序去重：像MySQL、PostgreSQL这类数据库，当查询列没有合适索引时，会先提取所有符合条件的结果行，再对需要去重的列组合进行排序。排序后重复行会相邻排列，最后遍历结果只保留每组重复行的第一行。比如执行SELECT DISTINCT name FROM users，如果name列没建索引，就会走这个流程。
• 哈希表去重：SQL Server、Oracle在部分场景下会采用这种方式。遍历结果集时，把要去重的列值组合作为哈希键存入哈希表——如果键已存在就跳过当前行，不存在则存入哈希表并保留该行。这种方式不需要排序，适合内存充足、数据量较大的场景。
• 利用索引去重：如果查询列上有唯一索引或普通索引，数据库会直接遍历索引。因为索引本身是有序的（普通索引）或有序且无重复（唯一索引），可以直接按顺序读取，遇到重复值直接跳过即可，这是效率最高的方式，不需要额外的排序或哈希操作。

注意：DISTINCT是对所有选中列的组合去重，不是针对单个列。比如SELECT DISTINCT name, age FROM users，是对name+age的组合去重，不是分别给name和age去重。

二、时间复杂度分析 #

时间复杂度取决于数据库采用的去重策略，不同场景差异明显：

• 无索引+排序去重：时间复杂度由排序主导，为O(n log n)，其中n是查询结果集的总行数。排序本身的时间复杂度是n log n，后续去重遍历是O(n)，整体由排序步骤决定。
• 无索引+哈希表去重：理想状态下（哈希冲突极少、内存足够），哈希表的插入和查找都是O(1)，整体时间复杂度是O(n)。但如果哈希冲突严重，或者内存不足导致哈希表写到磁盘上，时间复杂度会上升，甚至接近O(n log n)。
• 有索引的情况：不管是唯一索引还是普通索引，数据库只需要遍历索引，时间复杂度是O(k)，其中k是去重后的结果行数。如果原数据重复率高，k会远小于n，效率会非常高。

另外补充个细节：当DISTINCT和聚合函数一起使用时，比如SELECT DISTINCT COUNT(id) FROM users，其实DISTINCT是作用在聚合后的结果上，这里意义不大，因为COUNT本身只返回一个值，去重后结果还是一致的。

内容的提问来源于stack exchange，提问作者Greeshmanth