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 Size | Sort Size | 128MB | 64MB | 32MB | 16MB | 8MB | 4MB |
| 6914MB | 2672 MB | 64% | 70% | 93% | 110% | 133% | 137% |
| 3457MB | 1336 MB | 64% | 67% | 90% | 92% | 137% | 120% |
| 2765MB | 1069 MB | 68% | 66% | 84% | 95% | 111% | 137% |
| 1383MB | 535 MB | 66% | 70% | 72% | 92% | 99% | 96% |
| 691MB | 267 MB | 65% | 69% | 70% | 86% | 99% | 98% |
| 346MB | 134 MB | 65% | 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 Size | Sort Size | 128MB | 64MB | 32MB | 16MB | 8MB | 4MB |
| 6914MB | 2672 MB | 1068.07 | 963.23 | 1041.94 | 1246.54 | 1654.35 | 2472.79 |
| 3457MB | 1336 MB | 529.34 | 482.3 | 450.77 | 555.76 | 657.34 | 1027.57 |
| 2765MB | 1069 MB | 404.02 | 394.36 | 348.31 | 414.48 | 507.38 | 657.17 |
| 1383MB | 535 MB | 196.48 | 194.26 | 173.48 | 182.57 | 214.42 | 258.05 |
| 691MB | 267 MB | 95.93 | 93.79 | 87.73 | 80.4 | 93.67 | 105.24 |
| 346MB | 134 MB | 45.6 | 44.24 | 42.39 | 44.22 | 46.17 | 49.85 |
With the quicksort patch:
| Table Size | Sort Size | 128MB | 64MB | 32MB | 16MB | 8MB | 4MB |
| 6914MB | 2672 MB | 683.6 | 679.0 | 969.4 | 1366.2 | 2193.6 | 3379.3 |
| 3457MB | 1336 MB | 339.1 | 325.1 | 404.9 | 509.8 | 902.2 | 1229.1 |
| 2765MB | 1069 MB | 275.3 | 260.1 | 292.4 | 395.4 | 561.9 | 898.7 |
| 1383MB | 535 MB | 129.9 | 136.4 | 124.6 | 167.5 | 213.2 | 247.1 |
| 691MB | 267 MB | 62.3 | 64.3 | 61.4 | 69.2 | 92.3 | 103.2 |
| 346MB | 134 MB | 29.8 | 30.7 | 30.9 | 29.4 | 41.6 | 43.4 |