Re: [PATCH] Incremental sort (was: PoC: Partial sort)

On Tue, Jan 21, 2020 at 9:37 AM James Coleman <jtc331(at)gmail(dot)com> wrote:

> That being said, the patch also needs some more work on improving
> EXPLAIN ANALYZE output (perhaps min/max/mean or median of
> memory usage number of groups in each sort mode), and I think it's far
> more feasible that I can tackle that piecemeal before the next CF.
>
> James
>

I'm attaching a rebased patch revision + a new commit that reworks EXPLAIN
output. I left that patch as separate for now so that it was easy enough to
see the difference, and so that as Tomas is working on stuff in parallel I
don't unnecessarily cause merge conflicts for now, but next patch revision
(assuming the EXPLAIN change looks good) can just incorporate it into the
base patch.

Here's what I've changed:

- The stats necessary for ANALYZE are now only kept if the PlanState has a
non-null instrument field (thanks to Tom for pointing out this as the
correct way to check that ANALYZE is in flight). I did leave lines like
`node->incsort_info.fullsortGroupInfo.groupCount++;` unguarded by that `if`
since it seems like practically zero overhead (and almost equal to check
the condition), but if anyone disagrees, I'm happy to change it.
Additionally those lines (if ANALYZE is not in flight) are technically
operating on variables that haven't explicitly been initialized in the Init
function; please tell me if that's actually an issue given the are counters
and we won't be using them in that case.
- A good bit of cleanup on how parallel workers are output (I believe there
was some duplicative group opening and also inconsistent text output with
other multi-worker explain nodes). I haven't had a chance to test this yet,
thought, so there could be bugs.
- I left and XXX in the patch to note a place I wanted extra eyes. The
original patch ignored workers if the tuplesort for that worker still had
an in-progress status, but from what I can tell that doesn't make a lot of
sense given that we re-use the same tuplesort multiple times. So a parallel
worker (I think) could have returned from the first batch, but then be
in-progress still on the 2nd batch, and we wouldn't want to ignore that
worker. As a replacement I'm now checking that at least one of the fullsort
and prefixsort group count stats are greater than 0 (to imply we've sorted
at least one batch).
- I also left a TODO wondering if we should break out the instrumentation
into a separate function; it seems like a decent sized chunk of cleanly
extractable code; I suppose that's always a bit of personal preference, so
anyone who wants to weigh in gets a vote :)
- The previous implementation assumed the most recent tuplesort usage had
the correct information for memory/disk usage and sort implementation, but
again, since we re-use, that doesn't make a lot of sense. Instead I now
output all sort methods used as well as maximum and average disk and memory
usage.

Here's example output:
-> Incremental Sort
Sort Key: a, b
Presorted Key: a
Full-sort Groups: 4 (Methods: quicksort) Memory: 26kB (avg), 26kB
(max)
-> Index Scan using idx_t_a...

You'd have an additional line for "Presorted groups: ..." if any are
present to parallel "Full-sort groups".

I haven't yet run pg formatting, but I didn't want to modify the base patch
given other work on it is in flight.

James