From: | Jeremy Harris <jgh(at)wizmail(dot)org> |
---|---|
To: | Pg Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: Using quicksort and a merge step to significantly improve on tuplesort's single run "external sort" |
Date: | 2015-07-31 11:21:54 |
Message-ID: | 55BB5A52.7040300@wizmail.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On 30/07/15 02:05, Peter Geoghegan wrote:
> Since heapification is now a big fraction of the total cost of a sort
> sometimes, even where the heap invariant need not be maintained for
> any length of time afterwards, it might be worth revisiting the patch
> to make that an O(n) rather than a O(log n) operation [3].
O(n log n) ?
Heapification is O(n) already, whether siftup (existing) or down.
It might be worthwhile comparing actual times with a quicksort, given
that a sorted array is trivially a well-formed heap (the reverse is not
true) and that quicksort seems to be cache-friendly. Presumably there
will be a crossover N where the cache-friendliness k reduction
loses out to the log n penalty for doing a full sort; below this
it would be useful.
You could then declare the tape buffer to be the leading tranche of
work-mem (and dump it right away) and the heap to start with the
remainder.
--
Cheers,
Jeremy
From | Date | Subject | |
---|---|---|---|
Next Message | Michael Paquier | 2015-07-31 13:01:47 | Re: Doubt about AccessExclusiveLock in ALTER TABLE .. SET ( .. ); |
Previous Message | Heikki Linnakangas | 2015-07-31 10:41:23 | Re: LWLock deadlock and gdb advice |