Re: Using quicksort for every external sort run

I ran sorts with various parameters on my small NAS server. This is a
fairly slow CPU and limited memory machine with lots of disk so I thought
it would actually make a good test case for smaller servers. The following
is the speedup (for values < 100%) or slowdown (values > 100%) for the
first patch only, the "quicksort all runs" without the extra memory
optimizations.

At first glance it's a clear pattern that the extra runs does cause a
slowdown whenever it causes more polyphase merges which is bad news. But on
further inspection look just how low work_mem had to be to have a
significant effect. Only the 4MB and 8MB work_mem cases were significantly
impacted and only when sorting over a GB of data (which was 2.7 - 7GB with
the tuple overhead). The savings when work_mem was 64MB or 128MB was
substantial.

Table SizeSort Size128MB64MB32MB16MB8MB4MB6914MB2672 MB64%70%93%110%133%137%
3457MB1336 MB64%67%90%92%137%120%2765MB1069 MB68%66%84%95%111%137%1383MB535
MB66%70%72%92%99%96%691MB267 MB65%69%70%86%99%98%346MB134 MB65%69%73%67%90%
87%

The raw numbers in seconds. I've only run the test once so far on the NAS
and there are some other things running on it so I really should rerun it a
few more times at least.

HEAD:
Table SizeSort Size128MB64MB32MB16MB8MB4MB6914MB2672 MB1068.07963.231041.94
1246.541654.352472.793457MB1336
MB529.34482.3450.77555.76657.341027.572765MB1069
MB404.02394.36348.31414.48507.38657.171383MB535 MB196.48194.26173.48182.57
214.42258.05691MB267 MB95.9393.7987.7380.493.67105.24346MB134 MB45.644.24
42.3944.2246.1749.85

With the quicksort patch:
Table SizeSort Size128MB64MB32MB16MB8MB4MB6914MB2672 MB683.6679.0969.41366.2
2193.63379.33457MB1336 MB339.1325.1404.9509.8902.21229.12765MB1069 MB275.3
260.1292.4395.4561.9898.71383MB535 MB129.9136.4124.6167.5213.2247.1691MB267
MB62.364.361.469.292.3103.2346MB134 MB29.830.730.929.441.643.4