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.
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.