On Sat, Dec 14, 2013 at 6:30 PM, Jeremy Harris <j...@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.6070...@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.