Thread: Stable sort?

Is sorting in PostgreSQL stable over subqueries, that is, is

select * from (select * from A order by x) as B order by y;

equivalent with

select * from A order by y, x;

?

redhog wrote:
> Is sorting in PostgreSQL stable over subqueries, that is, is
>
> select * from (select * from A order by x) as B order by y;
>
> equivalent with
>
> select * from A order by y, x;

Seems as easy to try as to guess.

If I did this query right, it seems not.

select * from (select random()>0.5 as a, random()>0.5 as b from generate_series(1,10) order by a) as x order by b;
 a | b
---+---
 f | t
 f | f
 f | f
 f | f
 f | t
 f | f
 t | t
 t | t
 t | t
 t | f
(10 rows)

OTOH, HEY, why isn't that result ordered by 'b' instead of by 'a' (or am I misreading my query or the results)?

redhog wrote:
> Is sorting in PostgreSQL stable over subqueries, that is, is
>
> select * from (select * from A order by x) as B order by y;
>
> equivalent with
>
> select * from A order by y, x;

I don't see how it could be:
   SELECT * FROM (SELECT * FROM a ORDER BY x DESC) AS B ORDER BY x ASC;

--
   Richard Huxton
   Archonet Ltd

> I don't see how it could be:
>    SELECT * FROM (SELECT * FROM a ORDER BY x DESC) AS B ORDER BY x ASC;

That is a rather different query. My question was if the order of two
elements whose internal order is not affected by the current ordering
clause, still may change places due to technicalities. That is, the
normal meaning of the term "stable sort" as it applies to sorting
algorithms.

Example:

Given a subquery that returns the rows

 a| b
<s>+</s>
 2|1
 2|2
 1|1
 1|2

and an order by a, will the result allways be

 a| b
<s>+</s>
 1|1
 1|2
 2|1
 2|2

or might it sometimes end up as e.g.

 a| b
<s>+</s>
 1|2
 1|1
 2|1
 2|2

?

"redhog" <redhog@redhog.org> writes:
> My question was if the order of two
> elements whose internal order is not affected by the current ordering
> clause, still may change places due to technicalities.

Postgres usually sorts using qsort(), which (on most platforms) is not
stable in that sense.

            regards, tom lane

> -----Original Message-----
> From: pgsql-general-owner@postgresql.org [mailto:pgsql-general-
> owner@postgresql.org] On Behalf Of Tom Lane
> Sent: Wednesday, November 08, 2006 7:05 AM
> To: redhog
> Cc: pgsql-general@postgresql.org
> Subject: Re: [GENERAL] Stable sort?
>
> "redhog" <redhog@redhog.org> writes:
> > My question was if the order of two
> > elements whose internal order is not affected by the current
ordering
> > clause, still may change places due to technicalities.
>
> Postgres usually sorts using qsort(), which (on most platforms) is not
> stable in that sense.

This is (of course) what we would expect from any SQL database.

From ISO/IEC ISO/IEC 9075-2:1999 (E) Section 4.29 Cursors on page 71, we
have this:
"A cursor in the open state identifies a table, an ordering of the rows
of that table, and a position relative to that ordering. If the <declare
cursor> does not contain an <order by clause>, or contains an <order by
clause> that does not specify the order of the rows completely, then the
rows of the table have an order that is defined only to the extent that
the <order by clause> specifies an order and is otherwise
implementation-dependent.
When the ordering of a cursor is not defined by an <order by clause>,
the relative position of two rows is implementation-dependent. When the
ordering of a cursor is partially determined by an <order by clause>,
then the relative positions of two rows are determined only by the
<order by clause>; if the two rows have equal values for the purpose of
evaluating the <order by clause>, then their relative positions are
implementation-dependent."

This is talking about cursors specifically, but the same ordering
principles would obviously hold throughout.

The standard does not prevent the use of a stable sort, but it also does
not require it.

Obviously, if you order by all the result columns, then the orderings
will always be identical (though this would in general be a bad idea).