Re: Using quicksort and a merge step to significantly improve on tuplesort's single run "external sort"

On Wed, Jul 29, 2015 at 9:05 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> The behavior of external sorts that do not require any merge step due
> to only having one run (what EXPLAIN ANALYZE output shows as an
> "external sort", and not a "merge sort") seems like an area that can
> be significantly improved upon. As noted in code comments, this
> optimization did not appear in The Art of Computer Programming, Volume
> III. It's not an unreasonable idea, but it doesn't work well on modern
> machines due to using heapsort, which is known to use the cache
> ineffectively. It also often implies significant additional I/O for
> little or no benefit. I suspect that all the reports we've heard of
> smaller work_mem sizes improving sort performance are actually down to
> this one-run optimization *hurting* performance.

Very interesting. And great performance numbers. Thanks for taking
the time to investigate this - really cool.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company