On Thu, Jun 2, 2022 at 9:24 PM John Naylor <john.nay...@enterprisedb.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
