Re: Using quicksort for every external sort run

On Thu, Apr 7, 2016 at 11:10 AM, Robert Haas <robertmhaas@gmail.com> wrote:
> I prefer units of tuples, with the GUC itself therefore being
> unitless.  I suggest we call the parameter replacement_sort_threshold
> and document that (1) the ideal value may depend on the amount of CPU
> cache available to running processes, with more cache implying higher
> values; and (2) the ideal value may depend somewhat on the input data,
> with more correlation implying higher values.  And then pick some
> value that you think is likely to work well for most people and call
> it good.
>
> If you could prepare a new patch with those changes and also making
> the changes requested in my other email, I will try to commit that
> before the deadline.  Thanks.

Attached revision of patch series:

* Breaks out the parts you don't want to commit right now, as agreed.

These separate patches in the rebased patch series are included here
for completeness, but will probably be submitted separately to 9.7. I
do still think you should commit 0002-* alongside 0001-*, though,
because it's useful to be able to enable the memory context dumps on
dev builds to debug external sorting. I won't insist on it, but that
is my recommendation.

* Fixes "over-zealous assertion" that I pointed out recently.

* Replaces replacement_sort_mem GUC with replacement_sort_tuples GUC,
since, as discussed, effective cut-off points for using replacement
selection for the first run are easier to derive from the size of
memtuples (the might-be heap) than from work_mem/maintenance_work_mem
(the fraction of all tuplesort memory used that is used for memtuples
could be very low in cases with what Tomas called "padding").

Since you didn't get back to me on the name of the GUC, I just ran
with the name replacement_sort_tuples, but that's something I'm
totally unattached to. Feel free to change it to whatever you prefer,
including your original suggestion of replacement_sort_threshold if
you still think that works.

The new default value that I came up with for replacement_sort_tuples
is 150,000 tuples, which is intended as a rough generic break-even
point. Note that trace_sort reports how many tuples were in the heap
should replacement selection actually be chosen for the first run.
150,000 seems like a high enough generic delta between an out-of-order
tuple, and its optimal in-order position; if *that* amount of buffer
space to "juggle" tuples isn't enough, it seems unlikely that
*anything* will be (anything that is less than 1/2 of the total number
of input tuples, at least).

Note that I use the term "cache oblivious" in the documentation now,
per your suggestion that CPU cache characteristics be addressed. We
have traditionally avoided using jargon like that, but I think it
works well here. The reader is not required to know the definition.
Dropping that term provides bread-crumbs for advance users to put all
this together in more detail, which I believe has value. It suggests
that increasing work_mem or maintenance_work_mem can have almost no
downside provided you don't need that memory for anything else, which
is true.

I will be glad to see this through. Thanks for your help with this, Robert.

--
Peter Geoghegan