On Tue, Jul 2, 2013 at 12:36 PM, Peter Geoghegan <p...@heroku.com> wrote:
> On Tue, Jul 2, 2013 at 5:04 AM, Atri Sharma <atri.j...@gmail.com> wrote:
>>> I think if you'll try it you'll find that we perform quite well on
>>> data sets of this kind - and if you read the code you'll see why.
>> Right, let me read the code again from that viewpoint.
> In my opinion, it would be worthwhile reading the original Bentley and
> McIlroy paper [1] and using what you learned to write a patch that
> adds comments throughout the canonical qsort_arg, and perhaps the
> other variants.
> [1] 
> http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/421/09/bentley93engineering.pdf

That's weird, it doesn't seem as sophisticated as even libc's introsort.

Perhaps an introsort[1] approach wouldn't hurt: do the quick and dirty
median selection pg is already doing (or a better one if a better one
is found), but check recursion depth/input size ratios.

When across K recursive calls the input set hasn't been halved in
size, switch to median of medians to guard off against quadratic

[1] http://en.wikipedia.org/wiki/Selection_algorithm#Introselect

Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:

Reply via email to