高效的top K PostgreSQL

Question

我在PostgreSQL中有一个很大的表，我需要获取前K个元素。有没有办法在O(N logK)中选择前K个条目？

最明显的例子：

SELECT *
FROM table
ORDER BY col
LIMIT k

将给我们类似于O(N logN)的解决方案

sorted(arr)[:k] # in python

有没有一种SQL方法可以使用堆来实现这一点？

如下例所示：

from heapq import nsmallest
nsmallest(k, arr)

使用最小堆的O(N logK)是什么？

Answer 1

预先在列上创建索引(例如，btree)将大大加快该列上的排序速度。在插入期间，您将获得一些开销，但如果您在指定列上有大量相同形式的查询，这将是值得的。我在this page (在“使用索引进行排序”下)上找到了关于你所要求的查询的有趣信息/实验。