Re: LIMIT/SORT optimization

Some comments on the patch below.

Gregory Stark wrote:

> + /* tuplesort_set_bound - External API to set a bound on a tuplesort
> + *
> + * Must be called before inserting any tuples.
> +
> + * Sets a maximum number of tuples the caller is interested in. The first
> + * <bound> tuples are maintained using a simple insertion sort and returned
> + * normally. Any tuples that lie after those in the sorted result set are
> + * simply thrown out
> + */

The "Must be called before inserting any tuples" is in contradiction
with the comment in the header file:

> + /* This can be called at any time before performsort to advise tuplesort that
> + * only this many tuples are interesting. If that many tuples fit in memory and
> + * we haven't already overflowed to disk then tuplesort will switch to a simple
> + * insertion sort or heap sort and throw away the uninteresting tuples.
> + */

The latter seems to be correct.

> ! /*
> ! * Convert the existing unordered list of sorttuples to a heap in either order.
> ! * This used to be inline but now there are three separate places we heap sort
> ! * (initializing the tapes, if we have a bounded output, and any time the user
> ! * says he doesn't want to use glibc's qsort).
> ! *
> ! * NOTE heapify passes false for checkIndex (and stores a constant tupindex
> ! * passed as a parameter) even though we use heaps for multi-run sources
> ! * because we only heapify when we're doing in-memory sorts or in inittapes
> ! * before there's any point in comparing tupindexes.
> ! */
> !
> ! static void
> ! tuplesort_heapify(Tuplesortstate *state, int tupindex, HeapOrder heaporder)
> ! {

The comment claims that we use heap sort when the user says he doesn't
want to use glibc's qsort. I recall that we always use our own qsort
implementation nowadays. And we never used the heap sort as a qsort
replacement, did we?

In performsort, you convert the in-memory heap to a sorted list in one
go. I wonder if it would be better to switch to a new TSS_ALLINHEAP
state that means "all tuples are now in the in-memory heap", and call
tuplesort_heap_siftup in gettuple. It probably doesn't make much
difference in most cases, but if there's another limit node in the plan
with a smaller limit or the client only fetches a few top rows with a
cursor you'd avoid unheapifying tuples that are just thrown away later.

There's a few blocks of code surrounded with "#if 0 - #endif". Are those
just leftovers that should be removed, or are things that still need to
finished and enabled?

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com