On Thu, 23 Jun 2022 at 15:52, Robert Haas <robertmh...@gmail.com> wrote: > > On Thu, Jun 23, 2022 at 6:13 AM John Naylor > <john.nay...@enterprisedb.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
