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 complexity. [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: http://www.postgresql.org/mailpref/pgsql-hackers
