Re: some aspects of our qsort might not be ideal

On Thu, Jun 2, 2022 at 9:24 PM John Naylor <john(dot)naylor(at)enterprisedb(dot)com> 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) or if timsort was just simply good for
> Java's use cases. It seems accessible to try doing, so I'll look into
> that.

I think that Timsort is most useful with cases where individual
comparisons are inherently very expensive (perhaps even implemented in
Python), which might be common with objects due to the indirection
that Python (and even Java) impose on objects in general.

I would imagine that this is a lot less relevant in
Postgres/tuplesort, because we have optimizations like abbreviated
keys. And because we're mostly just sorting tuples on one or more
attributes of scalar types.

The abbreviated keys optimization is very much something that comes
from the world of databases, not the world of sorting. It's pretty much a
domain-specific technique. That seems relevant to me.

--
Peter Geoghegan