Re: PoC: Partial sort

On Sat, Dec 14, 2013 at 6:30 PM, Jeremy Harris <jgh@wizmail.org> wrote:

> On 14/12/13 12:54, Andres Freund wrote:
>
>> On 2013-12-14 13:59:02 +0400, Alexander Korotkov wrote:
>>
>>> Currently when we need to get ordered result from table we have to choose
>>> one of two approaches: get results from index in exact order we need or
>>> do
>>> sort of tuples. However, it could be useful to mix both methods: get
>>> results from index in order which partially meets our requirements and do
>>> rest of work from heap.
>>>
>>
>>  ------------------------------------------------------------
>>> ------------------------------------------------------------
>>> ------------------
>>>   Limit  (cost=69214.06..69214.08 rows=10 width=16) (actual
>>> time=0.097..0.099 rows=10 loops=1)
>>>     ->  Sort  (cost=69214.06..71714.06 rows=1000000 width=16) (actual
>>> time=0.096..0.097 rows=10 loops=1)
>>>           Sort Key: v1, v2
>>>           Sort Method: top-N heapsort  Memory: 25kB
>>>           ->  Index Scan using test_v1_idx on test  (cost=0.42..47604.42
>>> rows=1000000 width=16) (actual time=0.017..0.066 rows=56 loops=1)
>>>   Total runtime: 0.125 ms
>>> (6 rows)
>>>
>>
>> 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. But I would appreciate using
enchantments of sorting algorithms in my work.

------
With best regards,
Alexander Korotkov.