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 .
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 -- Sent via pgsql-hackers mailing list (firstname.lastname@example.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers