Re: [PATCH] Incremental sort (was: PoC: Partial sort) - Mailing list pgsql-hackers

On Mon, Jun 24, 2019 at 11:10 AM James Coleman <jtc331@gmail.com> wrote:
> As I see it the two most significant concerning cases right now are:
> 1. Very large batches (in particular where the batch is effectively
> all of the matching rows such that we're really just doing a standard
> sort).
> 2. Many very small batches.
...
> Alternatively I've been thinking about ways to achieve a hybrid
> approach: using single-batch suffix-only sort for large batches and
> multi-batch full sort for very small batches. For example, I could
> imagine maintaining two different tuplesorts (one for full sort and
> one for suffix-only sort) and inserting tuples into the full sorter
> until the minimum batch size, and then (like now) checking every tuple
> to see when we've finished the batch. If we finish the batch by, say,
> 2 * minimum batch size, then we perform the full sort. If we don't
> find a new batch by that point, we'd go back and check to see if the
> tuples we've accumulated so far are actually all the same batch. If
> so, we'd move all of them to the suffix-only sorter and continue
> adding rows until we hit a new batch. If not, we'd perform the full
> sort, but only return tuples out of the full sorter until we encounter
> the current batch, and then we'd move the remainder into the
> suffix-only sorter.

Over the past week or two I've implemented this approach. The attached
patch implements the sort retaining the minimum group size logic
already in the patch, but then after 32 tuples only looks for a
different prefix key group for the next 32 tuples. If it finds a new
prefix key group, then everything happens exactly as before. However
if it doesn't find a new prefix key group in that number of tuples,
then it assumes it's found a large set of tuples in a single prefix
key group. To guarantee this is the case it has to transfer tuples
from the full sorting tuplesort into a presorted prefix tuplesort and
(leaving out a few details here about how it handles the possibility
of multiple prefix key groups already in the sort) continues to fill
up that optimized sort with the large group.

This approach should allow us to, broadly speaking, have our cake and
eat it too with respect to small and large batches of tuples in prefix
key groups. There is of course the cost of switching modes, but this
is much like the cost that bound sort pays to switch into top-n heap
sorting mode; there's an inflection point, and you pay some extra cost
right at it, but it's worth it in the broad case.

Initial testing shows promising performance (akin to the original
patch for small groups and similar to my variant that only ever sorted
by single prefix key groups for large batches)

A couple of thoughts:
- It'd be nice if tuplesort allowed us to pull back out tuples in FIFO
manner without sorting. That'd lower the inflection point cost of
switching modes.
- I haven't adjusted costing yet for this change in approach; I wanted
to take a more holistic look at that after getting this working.
- I don't have strong feelings about the group size inflection points.
More perf testing would be useful, and also it's plausible we should
do more adjusting of those heuristics based on the size of the bound,
if we have one.
- The guc enable_sort current also disabled incremental sort, which
makes sense, but it also means there's not a good way to tweak a plan
using a full sort into a plan that uses incremental sort. That seems
not the greatest, but I'm not sure what the best solution would be.
- I did a lot of comment work in this patch, but comments for changes
to tuplesort.c and elsewhere still need to be cleaned up.

A few style notes:
- I know some of the variable declarations don't line up well; I need
to figure out how to get Vim to do what appears to be the standard
style in PG source.
- All code and comment lines are the right length, I think with the
exception of debug printf statements. I'm not sure if long strings are
an exception.
- Lining up arguments is another thing Vim isn't setup to do, though
maybe someone has some thoughts on a good approach.
I'm planning to look at the formatting utility when I get a chance,
but it'd be nice to have the editor handle the basic setup most of the
time.

Process questions:
- Do I need to explicitly move the patch somehow to the next CF?
- Since I've basically taken over patch ownership, should I move my
name from reviewer to author in the CF app? And can there be two
authors listed there?

James Coleman