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

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.

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.

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.

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.

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.

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 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.

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.

Thanks,
James