Re: PoC: Partial sort

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.

--
Cheers,
Jeremy