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

On Fri, Mar 27, 2020 at 9:19 PM Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>
> On Fri, Mar 27, 2020 at 12:51:34PM -0400, James Coleman wrote:
> >In a previous email I'd summarized remaining TODOs I'd found. Here's
> >an updated listed with several resolved.
> >
> >Resolved:
> >
> >2. Not marked in the patch, but in nodeIncrementalSort.c
> >ExecIncrementalSort() I wonder if perhaps we should move the algorithm
> >discussion comments up to the file header comment. On the other hand,
> >I suppose it could be valuable to leave the the file header comment
> >more high level about the mathematical properties of incremental sort
> >rather than discussing the details of the hybrid mode.
> >
> >I've decided to do this, and the attached patch series includes the change.
> >
>
> It's a bit tough to find the right balance what to put into the header
> comment and what should go to function comments, but this seems mostly
> reasonable. I wouldn't use the double-tab indentation and the copyright
> notices should stay at the top.

Fixed. I also re-ran pg_indent on the the nodeIncrementalSort.c file.

> >3. nodeIncrementalSort.c ExecIncrementalSort() in the main for loop:
> > * TODO: do we need to check for interrupts inside these loops or
> > * will the outer node handle that?
> >
> >It seems like what we have is sufficient, given that the nodes (and
> >sort) we rely on have their own calls. The one place where someone
> >might make an argument otherwise would be in the mode transition
> >function where we copy tuples from the full sort state to the
> >presorted sort state. If this is a problem, let me know, and I'll
> >change it, but I'm proceeding under the assumption for now that it's
> >not.
> >
>
> I think what we have now is sufficient.
>
> >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. Additionally the sort_Done
> >variable is poorly named; it probably would make more sense to call it
> >something like "scanHasBegun". I'm waiting to change it though until
> >cleaning up this code more holistically.
> >
> >Fixed, as described in previous email.
> >
> >6. regress/expected/incremental_sort.out:
> >-- TODO if an analyze happens here the plans might change; should we
> >-- solve by inserting extra rows or by adding a GUC that would somehow
> >-- forcing the time of plan we expect.
> >
> >I've decided this doesn't seem to be a real issue, so, comment removed.
> >
>
> OK
>
> >7. Not listed as a comment in the patch, but I need to modify the
> >testing for analyze output to parse out the memory/disk stats to the
> >tests are stable.
> >
> >Included in the attached patch series. I use plpgsql to munge out the
> >space kB numbers. I also discovered two bugs in the JSON output along
> >the way and fixed those (memory and disk need to be output separate;
> >disk was using the wrong "space type" enum). Finally I also use
> >plpgsql to check a few invariants (for now just that max space is
> >greater than or equal to the average.
> >
>
> OK
>
> >8. optimizer/path/allpaths.c get_useful_pathkeys_for_relation:
> >* XXX At the moment this can only ever return a list with a single element,
> >* because it looks at query_pathkeys only. So we might return the pathkeys
> >* directly, but it seems plausible we'll want to consider other orderings
> >* in the future.
> >
> >I think we just leave this in as a comment.
> >
>
> Fine with me.
>
> As a side note here, I'm wondering if this (determining useful pathkeys)
> can be made a bit smarter by looking both at query_pathkeys and pathkeys
> useful for merging, similarly to what truncate_useless_pathkeys() does.
> But that can be seen as an improvement of what we do now.

Unless your comment below about looking at truncate_useless_pathkeys
is implying you're considering aiming to get this in now, I wonder if
we should just expand the comment to reference pathkeys useful for
merging as a possible future extension.

> >9. optimizer/path/allpaths.c get_useful_pathkeys_for_relation:
> >* Considering query_pathkeys is always worth it, because it might let us
> >* avoid a local sort.
> >
> >That originally was a copy from the fdw code, but since the two
> >functions have diverged (Is that concerning? I could be confusing, but
> >isn't a compilation problem) I didn't move the function.
> >
>
> I think it's OK the two functions diverged, it's simply because the FDW
> one needs to check other things too. But I might rework this once I look
> closer at truncate_useless_pathkeys.

Agreed, for now at least. It's tempting to think they should always be
shared, but I'm not convinced (without a lot more digging) that this
represents structural rather than incidental duplication.

> >I did notice though that find_em_expr_for_rel() is wholesale copied
> >(and unchanged) from the fdw code, so I moved it to equivclass.c so
> >both places can share it.
> >
>
> +1
>
> >
> >Still remaining:
> >
> >1. src/backend/optimizer/util/pathnode.c add_partial_path()
> >* XXX Perhaps we could do this only when incremental sort is enabled,
> >* and use the simpler version (comparing just total cost) otherwise?
> >
> >I don't have a strong opinion here. It doesn't seem like a significant
> >difference in terms of cost?
> >
> >5. planner.c create_ordered_paths:
> >* XXX This only looks at sort_pathkeys. I wonder if it needs to look at the
> >* other pathkeys (grouping, ...) like generate_useful_gather_paths.
> >
> >10. optimizer/path/allpaths.c generate_useful_gather_paths:
> >* XXX I wonder if we need to consider adding a projection here, as
> >* create_ordered_paths does.
> >
> >11. In the same function as the above:
> >* XXX Can't we skip this (maybe only for the cheapest partial path)
> >* when the path is already sorted? Then it's likely duplicate with
> >* the path created by generate_gather_paths.
> >
> >12. In the same function as the above:
> >* XXX This is not redundant with the gather merge path created in
> >* generate_gather_paths, because that merely preserves ordering of
> >* the cheapest partial path, while here we add an explicit sort to
> >* get match the useful ordering.
> >
> >13. planner.c create_ordered_paths:
> >* XXX This is probably duplicate with the paths we already generate
> >* in generate_useful_gather_paths in apply_scanjoin_target_to_paths.
> >
> >Tomas, any chance you could take a look at the above XXX/questions? I
> >believe all of them that remain relate to the planner patches.
> >
>
> Yes, I'll take a look over the weekend.

Awesome, thanks.

I collapsed things down including the changes referenced in this
email, since they were all comment formatting changes.

James