Re: Timsort performance, quicksort

From: Dimitri Fontaine <dimitri(at)2ndQuadrant(dot)fr>
To: Peter Geoghegan <peter(at)2ndquadrant(dot)com>
Cc: PG Hackers <pgsql-hackers(at)postgresql(dot)org>, Greg S <stark(at)mit(dot)edu>
Subject: Re: Timsort performance, quicksort
Date: 2012-04-19 18:24:22
Message-ID: m28vhrk2ax.fsf@2ndQuadrant.fr
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Peter Geoghegan <peter(at)2ndquadrant(dot)com> writes:
> 1. What we should be doing with timsort, if anything. It is one
> thing to demonstrate that it's a useful algorithm under certain
> artificial conditions, but quite another to argue for its inclusion in
> Postgres, or for it being selectively used at points where that is
> likely to be a win, based on some criteria or another like known
> cardinality, physical/logical correlation or assumed costs of
> comparisons for each type. At the very least, it is an interesting
> algorithm, but without integration that makes it actually serve user
> needs, that's all it will ever be to us. Deciding if and when it
> should be used is a rather nuanced process, and I'm certainly not
> about to declare that we should get rid of quicksort. It does appear
> to be a fairly good fit to some of our requirements though.

I kind of understood timsort would shine in sorting text in non-C
collation, because of the comparison cost. So a test in some UTF8
collation or other would be interesting, right?

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Peter Eisentraut 2012-04-19 18:40:22 Re: libpq URI and regression testing
Previous Message Andrew Dunstan 2012-04-19 17:04:33 Re: Bug tracker tool we need