| From: | Greg Stark <stark(at)mit(dot)edu> |
|---|---|
| To: | Robert Haas <robertmhaas(at)gmail(dot)com> |
| Cc: | Peter Geoghegan <peter(at)2ndquadrant(dot)com>, PG Hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Timsort performance, quicksort (was: Re: Memory usage during sorting) |
| Date: | 2012-04-24 16:30:27 |
| Message-ID: | CAM-w4HO5LWCankUHMD0yoF8Gt0Y+ih7z4cXTveBhqwrwFDJ5=g@mail.gmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On Tue, Apr 24, 2012 at 4:17 PM, Robert Haas <robertmhaas(at)gmail(dot)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.
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. 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.
--
greg
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Peter Geoghegan | 2012-04-24 16:51:00 | Re: Timsort performance, quicksort (was: Re: Memory usage during sorting) |
| Previous Message | Jeff Janes | 2012-04-24 16:21:49 | Re: New sync commit mode remote_write |