The case for removing replacement selection sort

There was a number of improvements to tuplesort.c external sort
merging made for Postgres 10. One in particular, the changes to merge
heap maintenance that occurred for commit 24598337c8d, really helped
with presorted cases -- cases when there was an (inverse)
physical/logical correlation.

Replacement selection sort for run generation was not killed as part
of the improvements to external sorting in Postgres 9.6, although
there was a reasonably good case for that to be made at the time those
enhancements went in. This was because it was still possible for its
best case to come out ahead. The best case is the case where it
manages to produce a single run, all in one go, by exploiting
presortedness. The examples where this was possible were fairly
narrow, but they existed.

With the additional enhancements made to Postgres 10, I doubt that
there are any remaining cases where it wins. In addition to the point
about heap management and presortedness, you also have to consider
that TSS_SORTEDONTAPE processing is optimized for random access. This
means that one-big-replacement-selection-run cases will not take
advantage of available memory, improvements in Postgres 10 by Heikki
to tape preloading for merging, OS readahead, and so on. Merging is
often quite I/O bound these days, especially when merging naturally
requires few comparisons. TSS_SORTEDONTAPE processing is
inappropriate.

I think we should remove the replacement_sort_tuples GUC, and kill
replacement selection entirely. There is no need to do this for
Postgres 10. I don't feel very strongly about it. It just doesn't make
sense to continue to support replacement selection.

--
Peter Geoghegan