python - 高效top K PostgreSQL

Question

我在 PostgreSQL 中有一个巨大的表，我需要获取前 K 个元素。有没有办法在 O(N logK) 中选择 Top 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)将显着加快该列上的 ORDER BY。在插入期间，您会得到一些开销，但如果您在指定列上有很多相同形式的查询，这将得到返回。我在 this page 上找到了关于您要求的查询的有趣信息/实验。 (在“使用索引进行排序”下)