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: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>, 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>, Andreas Karlsson <andreas@proxel.se>
Date: 2020-03-24T22:26:11Z
Lists: pgsql-hackers 
On Mon, Mar 23, 2020 at 11:44 PM Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:
>
> On 2020-Mar-23, James Coleman wrote:
>
> > 4. nodeIncrementalSort.c ExecReScanIncrementalSort: This whole chunk
> > is suspect. I've mentioned previously I don't have a great mental
> > model of how rescan works and its invariants (IIRC someone said it was
> > about moving around a result set in a cursor). Regardless I'm pretty
> > sure this code just doesn't work correctly.
>
> I don't think that's the whole of it.  My own vague understanding of
> ReScan is that it's there to support running a node again, possibly with
> different parameters.  For example if you have a join of an indexscan
> on the outer side and an incremental sort on the inner side, and the
> values from the index are used as parameters to the incremental sort,
> then the incremental sort is going to receive ReScan calls for each of
> the values that the index returns.  Sometimes the index could give you
> the same values as before (because there's a dupe in the index), so you
> can just return the same values from the incremental sort; but other
> times it's going to return different values so you need to reset the
> incremental sort to "start from scratch" using the new values as
> parameters.
>
> Now, if you have a cursor reading from the incremental sort and fetch
> all tuples, then rewind completely and fetch all again, then that's
> going to be a rescan as well.
>
> I agree with you that the code doesn't seem to implement that.

I grepped the codebase for rescan, and noted this relevant info in
src/backend/executor/README:

* Rescan command to reset a node and make it generate its output sequence
over again.

* Parameters that can alter a node's results. After adjusting a parameter,
the rescan command must be applied to that node and all nodes above it.
There is a moderately intelligent scheme to avoid rescanning nodes
unnecessarily (for example, Sort does not rescan its input if no parameters
of the input have changed, since it can just reread its stored sorted data).

That jives pretty well with what you're saying.

The interesting thing with incremental sort, as the comments in the
patch already note, is that even if the params haven't changed, we
can't regenerate the same values again *unless* we know that we're
still in the same batch, or, have only processed a single full batch
(and the tuples are still in the full sort state) or we've
transitioned to prefix mode and have only transferred tuples from the
full sort state for a single prefix key group.

That's a pretty narrow range of applicability of not needing to
re-execute the entire node, at least based on my assumptions about
when rescanning will typically happen.

So, two followup questions:

1. Given the narrow applicability, might it make sense to just say
"we're only going to do a total reset and rescan and not try to
implement a smart 'don't rescan if we don't have to'"?

2. What would be a typical or good way to test this? Should I
basically repeat many of the existing implementation tests but with a
cursor and verify that rescanning produces the same results? That's
probably the path I'm going to take if there are no objections. Of
course we would need even more testing if we wanted to have the "smart
rescan" functionality.

Thoughts?

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.