algorithm - PostgreSQL 中任意排序的性能如何？

Question

在 Postgres 中可以执行这样的命令

SELECT * FROM mytable
WHERE id in (8, 6, 7, 5, 10, 24)
ORDER BY id=8 DESC, id=6 DESC, id=7 DESC, id=5 DESC, id=10 DESC, id=24 DESC;

以任意顺序选择任意数据。

我想如果某种排序算法的复杂度为 O(log n)，我们天真地做了一个索引排序:

data.sort(function(a, b) {
    return indexOf(a) < indexOf(b);
});

然后我们每个排序操作可能需要 O(2n)，使我们的总算法时间为 O(n log n)。

然后我们可以创建一个简单的位置值索引，而不是每次都求助。假设这也有 O(log n) 的最坏时间，那么对于我们的排序算法，我们得到 O((log n)(log n)) 或 O((log n)^2)。这对于算法来说不是很好的性能。

Postgres 使用什么算法，性能如何？如果它优于 O((log n) * the_sort_algorithms_performance)，我们将在 db 之外实现排序。或者，如果算法是我们可以轻松移植到 Java 的算法，我们可能仍然不会在 Postgres 中进行排序。

Answer 1

TLDR；不详细讨论您的广泛问题。排序算法是一个复杂的领域。

至于您的查询:如果您提供一个值列表，这会便宜很多，因为无论如何您都必须按某种顺序传递值:

SELECT t.*
FROM   unnest('{8, 6, 7, 5, 10, 24}'::int[]) id
JOIN   mytable t USING (id);

这可行，但不能保证。可以肯定的是(在 Postgres 9.4+ 中):

SELECT *
FROM   unnest('{8, 6, 7, 5, 10, 24}'::int[]) WITH ORDINALITY x(id, rn)
JOIN   mytable t USING (id)
ORDER  BY x.rn;

详细信息:

• PostgreSQL unnest() with element number