On Thu, 23 Jun 2022 at 17:04, Peter Geoghegan wrote:
>
> On Thu, Jun 23, 2022 at 7:51 AM Matthias van de Meent
> wrote:
> > 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 sta
On Thu, Jun 23, 2022 at 7:51 AM Matthias van de Meent
wrote:
> 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.
The
On Thu, 23 Jun 2022 at 15:52, Robert Haas wrote:
>
> On Thu, Jun 23, 2022 at 6:13 AM John Naylor
> 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
On Thu, Jun 23, 2022 at 6:13 AM John Naylor
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.
--
Robert Haas
EDB: ht
On Fri, Jun 3, 2022 at 10:44 AM Peter Geoghegan wrote:
> What about dual-pivot quicksort, which is used in Java 7+? That is the
> defacto successor to Bentley & McIlroy. In fact, Jon Bentley himself
> collaborated with its author, and provided benchmarking input. The
> underlying philosophy is es
On Thu, Jun 2, 2022 at 9:24 PM John Naylor wrote:
> I had heard of it but not looked into it deeply. I did read that Java
> 7 uses dual pivot quicksort for primitives and timsort for objects. I
> wasn't sure if dual pivot was not good for objects (which could have
> possibly-complex comparators) o
On Fri, Jun 3, 2022 at 10:44 AM Peter Geoghegan wrote:
>
> What about dual-pivot quicksort, which is used in Java 7+? That is the
> defacto successor to Bentley & McIlroy. In fact, Jon Bentley himself
> collaborated with its author, and provided benchmarking input. The
> underlying philosophy is e
On Thu, Jun 2, 2022 at 8:33 PM John Naylor wrote:
> Attached is a draft series that implements some but not all features
> of pattern-defeating quicksort, namely the ones I thought were
> interesting for us. Recently this quicksort variant got committed for
> the next release of the Go language 1.
On Wed, Feb 16, 2022 at 2:29 AM John Naylor
wrote:
> Does anyone see a reason not to put in the necessary work to try it out?
Seems reasonable to me. It's always a bit difficult, I feel, to know
what test cases to use - almost any idea is going to have some case
where it's worse than what we do t
> This way, we *dynamically*
> decide to optimistically start an insertion sort, in the hopes that it
> will occasionally prevent a recursion, and worst case the input is
> slightly more sorted for the next recursion.
I should mention one detail -- we put a limit on how many iterations
we attempt
> [3]
> https://www.postgresql.org/message-id/flat/87F42982BF2B434F831FCEF4C45FC33E5BD369DF%40EXCHANGE.corporate.connx.com#e69718293c45d89555020bd0922ad055
The top of that thread is where I meant to point to:
https://www.postgresql.org/message-id/flat/CAEYLb_Xn4-6f1ofsf2qduf24dDCVHbQidt7JPpdL_Ri
While reviewing Thomas Munro's patchset to consider expanding the uses
of specialized qsort [1], I wondered about some aspects of the current
qsort implementation. For background, ours is based on Bentley &
McIlroy "Engineering a Sort Function" [2], which is a classic paper
worth studying.
1) the
12 matches
Mail list logo
