Re: some aspects of our qsort might not be ideal

On Thu, 23 Jun 2022 at 15:52, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
> On Thu, Jun 23, 2022 at 6:13 AM John Naylor
> <john(dot)naylor(at)enterprisedb(dot)com> wrote:
> > Here is a *rough* first pass at dual-pivot quicksort. I haven't
> > changed the regression tests to adjust for qsort being an unstable
> > sort, ...
>
> Hmm. I thought we had some reasons for preferring a stable sort algorithm.

I think that mostly has to do with reliability / stability of ORDER BY
in combination with LIMIT and OFFSET, even though right now we cannot
fully guarantee such stability due to unstable results from underlying
plan nodes.

As an example, a table scan node under a sort node can start its scan
at an arbitrary point in the table (using synchronize_seqscans), and
because Sort nodes only sort MinimalTuple-s, each set of tuples that
have an equal sort value will be ordered by TID + y (mod tablesize),
with arbitrary values for y.

- Matthias