Re: PoC: Partial sort

On 22/12/13 20:26, Alexander Korotkov wrote:
> On Sat, Dec 14, 2013 at 6:30 PM, Jeremy Harris <jgh@wizmail.org> wrote:
>
>> On 14/12/13 12:54, Andres Freund wrote:
>>> Is that actually all that beneficial when sorting with a bog standard
>>> qsort() since that doesn't generally benefit from data being pre-sorted?
>>> I think we might need to switch to a different algorithm to really
>>> benefit from mostly pre-sorted input.
>>>
>>
>> Eg:  http://www.postgresql.org/message-id/5291467E.6070807@wizmail.org
>>
>> Maybe Alexander and I should bash our heads together.
>
>
> Partial sort patch is mostly optimizer/executor improvement rather than
> improvement of sort algorithm itself.

I finally got as far as understanding Alexander's cleverness, and it
does make the performance advantage (on partially-sorted input) of the
merge-sort irrelevant.

There's a slight tradeoff possible between the code complexity of
the chunking code front-ending the sorter and just using the
enhanced sorter.  The chunking does reduce the peak memory usage
quite nicely too.

The implementation of the chunker does O(n) compares using the
keys of the feed-stream index, to identify the chunk boundaries.
Would it be possible to get this information from the Index Scan?
-- 
Cheers,   Jeremy