Horton

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

James Coleman <jtc331@gmail.com>

View thread View on postgr.es
From: James Coleman <jtc331@gmail.com>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Michael Paquier <michael@paquier.xyz>, Rafia Sabih <rafia.pghackers@gmail.com>, Peter Geoghegan <pg@bowt.ie>, Simon Riggs <simon@2ndquadrant.com>, Shaun Thomas <shaun.thomas@2ndquadrant.com>, Dmitry Dolgov <9erthalion6@gmail.com>, Alexander Korotkov <a.korotkov@postgrespro.ru>, Tom Lane <tgl@sss.pgh.pa.us>, PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>, Alvaro Herrera <alvherre@2ndquadrant.com>
Date: 2020-03-07T22:47:00Z
Lists: pgsql-hackers

Attachments

On Tue, Jan 21, 2020 at 9:37 AM James Coleman <jtc331@gmail.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

Commits

  1. Further adjustments to Hashagg EXPLAIN ANALYZE output

  2. Rework EXPLAIN format for incremental sort

  3. Fix typos and improve incremental sort comments

  4. Stabilize incremental_sort tests

  5. Minor improvements in Incremental Sort explain

  6. Consider Incremental Sort paths at additional places

  7. Fix representation of SORT_TYPE_STILL_IN_PROGRESS.

  8. Fix failures in incremental_sort due to number of workers

  9. Fix show_incremental_sort_info with force_parallel_mode

  10. Implement Incremental Sort

  11. Fix handling of "Subplans Removed" field in EXPLAIN output.

  12. Fix EXPLAIN (SETTINGS) to follow policy about when to print empty fields.

  13. Ensure plpgsql result tuples have the right composite type marking.

  14. Propagate sort instrumentation from workers back to leader.

  15. Make new regression test case parallel-safe, and improve its output.

  16. Push limit through subqueries to underlying sort, where possible.

  17. Fix inappropriate printing of never-measured times in EXPLAIN.

  18. Fix some infelicities in EXPLAIN output for parallel query plans.