From: | Peter Geoghegan <peter(at)2ndquadrant(dot)com> |
---|---|
To: | Greg Stark <stark(at)mit(dot)edu> |
Cc: | Robert Haas <robertmhaas(at)gmail(dot)com>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Jeff Janes <jeff(dot)janes(at)gmail(dot)com>, Hitoshi Harada <umi(dot)tanuki(at)gmail(dot)com>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: Memory usage during sorting |
Date: | 2012-04-13 17:15:20 |
Message-ID: | CAEYLb_WpkN1quSRd+=r0dHcRFQL86vxWQYpVrP-Y4W0wVqaSyA@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On 13 April 2012 17:42, Peter Geoghegan <peter(at)2ndquadrant(dot)com> wrote:
> One insight that I had at the time was that text comparisons where the
> c locale isn't used are really rather expensive, and I doubt that
> there is too much that can be done to address that directly. However,
> if we were to support timsort, that could substantially cut down on
> the number of comparisons for text columns, which could be a real win.
> Maybe that would happen through some explicit mechanism, or maybe the
> planner could actually infer that it was likely to be optimal to use
> timsort based on a high statistical correlation between physical row
> ordering and logical ordering of a key column's values.
Further thoughts:
At the time we committed our own quicksort implementation, based on
the NetBSD one, we eschewed the optimisation of using insertion sort
when n is fairly low. This happens to be a very common optimisation,
so I'm not really super-confident that that was a good decision.
However, we also added our own optimisation, which is to attempt,
regardless of the size of n, to ascertain that the array is
pre-sorted, in which case we don't quicksort at all.
So if we attempt to quicksort an array which is almost pre-sorted, but
say only has its very last element out-of-order, we'll do fairly
horribly, because we waste the effort of almost an entire "bubble sort
iteration". So almost-sorted data would seem to be a compelling thing
to optimise for that reason, as well as for the simple observation
that it isn't exactly uncommon in a relational database.
--
Peter Geoghegan http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services
From | Date | Subject | |
---|---|---|---|
Next Message | Bruce Momjian | 2012-04-13 17:29:38 | Re: 9.2 release notes, beta time? |
Previous Message | Robert Haas | 2012-04-13 17:15:18 | Re: [COMMITTERS] pgsql: Add new replication mode synchronous_commit = 'write'. |