On Tue, Apr 24, 2012 at 12:30 PM, Greg Stark <st...@mit.edu> wrote: > On Tue, Apr 24, 2012 at 4:17 PM, Robert Haas <robertmh...@gmail.com> wrote: >> Based on that, I'm inclined to propose rejiggering things so that the >> presorted-input check runs only at the top level, and not during any >> recursive steps. > > Just a thought. What about running only every nth step. Maybe > something like every 4th step.
If there's actually some advantage to that, sure. But so far, it looks like less is more. > But actually I'm confused. This seems to be misguided to me. Quicksort > isn't stable so even if you have a partially sorted data set the > recursive partitions are going to be at best partially sorted after a > pivot. Exactly. That's why I think we should do it only at the topmost level, before we've done any pivoting. Doing it at any lower level is apparently a waste of energy and counterproductive. > I haven't walked through it but suspect even your > all-but-one-sorted data set is not finding > the data sorted in either partition on the next iteration. I suspect that, too. Actually, I'm a bit confused about why it's picking such terrible pivots. Our median-of-medians optimization should be doing better than this, I would think. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
