What is the performance of arbitrary ordering in PostgreSQL?

Question

In Postgres in is possible to perform an order like so

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;

To select arbitrary data in arbitrary order.

I have figured that if some sorting algorithm has has O(log n), and we naively do an indexof sort like so:

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

then we each sorting operation may take O(2n), making our total algorithmic time into O(n log n).

We can then create a simple index of values to positions instead of resorting each time. Assuming this has a worst time of O(log n) as well, we then get, for our sorting algorithm, O((log n)(log n)) or O((log n)^2). This is not great performance for an algorithm.

What algorithm, which what performance, does Postgres use? If it is better than O((log n) * the_sort_algorithms_performance), we will implement the sorting outside of the db. Alternatively, if the algorithm is one we easily can port to Java we may still not do the sorting in Postgres.

"psql" is the name of the command-line interface, and not a valid name for Postgres. — Erwin Brandstetter, Mar 20 '15 at 21:30
It seems like this would be fairly easy to determine through testing. — David Aldridge, Mar 20 '15 at 21:45

score 3 · Answer 1 · edited May 23 '17 at 11:50

TLDR; Not going into details with your broad question. Sort algorithms are a complex field.

As for your query: if you provide a list of values, this can be considerably cheaper, because you have to pass the values in some order anyway:

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

This works, but there are no guarantees. To be sure (in 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;

Details:

PostgreSQL unnest() with element number

What is the performance of arbitrary ordering in PostgreSQL?

1 Answers1