Re: PoC: Partial sort

Some quick comments on partial-sort-basic-2.patch:

> *** a/src/include/utils/tuplesort.h
> --- b/src/include/utils/tuplesort.h
> ***************
> *** 24,29 ****
> --- 24,30 ----
> #include "executor/tuptable.h"
> #include "fmgr.h"
> #include "utils/relcache.h"
> + #include "utils/sortsupport.h"

Why include sortsupport.h here?

I would like to see more comments, especially within ExecSort(). The
structure of that routine is quite unclear.

I don't really like this MakeSortSupportKeys() stuff within ExecSort():

> ! /* Support structures for cmpSortSkipCols - already sorted columns */
> ! if (skipCols)
> ! node->skipKeys = MakeSortSupportKeys(skipCols,
> ! plannode->sortColIdx,
> ! plannode->sortOperators,
> ! plannode->collations,
> ! plannode->nullsFirst);
>
> + /* Only pass on remaining columns that are unsorted */
> tuplesortstate = tuplesort_begin_heap(tupDesc,
> ! plannode->numCols - skipCols,
> ! &(plannode->sortColIdx[skipCols]),
> ! &(plannode->sortOperators[skipCols]),
> ! &(plannode->collations[skipCols]),
> ! &(plannode->nullsFirst[skipCols]),
> work_mem,
> node->randomAccess);

You're calling the new function MakeSortSupportKeys() (which
encapsulates setting up sortsupport state for all attributes) twice;
first, to populate the skip keys (the indexed attribute(s)), and
second, when tuplesort_begin_heap() is called, so that there is state
for unindexed sort groups that must be manually sorted. That doesn't
seem great.

I think we might be better off if a tuplesort function was called
shortly after tuplesort_begin_heap() is called. How top-n heap sorts
work is something that largely lives in tuplesort's head. Today, we
call tuplesort_set_bound() to hint to tuplesort "By the way, this is a
top-n heap sort applicable sort". I think that with this patch, we
should then hint (where applicable) "by the way, you won't actually be
required to sort those first n indexed attributes; rather, you can
expect to scan those in logical order. You may work the rest out
yourself, and may be clever about exploiting the sorted-ness of the
first few columns". The idea of managing a bunch of tiny sorts from
with ExecSort(), and calling the new function tuplesort_reset() seems
questionable. tuplesortstate is supposed to be private/opaque to
nodeSort.c, and the current design strains that.

I'd like to keep nodeSort.c simple. I think it's pretty clear that the
guts of this do not belong within ExecSort(), in any case. Also, the
additions there should be much better commented, wherever they finally
end up.

In this struct:

> *** a/src/include/nodes/execnodes.h
> --- b/src/include/nodes/execnodes.h
> *************** typedef struct SortState
> *** 1670,1678 ****
> --- 1670,1682 ----
> bool bounded; /* is the result set bounded? */
> int64 bound; /* if bounded, how many tuples are needed */
> bool sort_Done; /* sort completed yet? */
> + bool finished; /* fetching tuples from outer node
> + is finished ? */
> bool bounded_Done; /* value of bounded we did the sort with */
> int64 bound_Done; /* value of bound we did the sort with */
> void *tuplesortstate; /* private state of tuplesort.c */
> + SortSupport skipKeys; /* columns already sorted in input */
> + HeapTuple prev; /* previous tuple from outer node */
> } SortState;

I think you should be clearer about the scope and duration of fields
like "finished", if this really belongs here. In general, there should
be some high-level comments about how the feature added by the patch
fits together, which there isn't right now.

That's all I have for now.

--
Peter Geoghegan