On 05/14/2017 09:47 PM, Sokolov Yura wrote:
Good day, everyone.

I've been playing a bit with unlogged tables - just random updates on
key-value table. I've noticed amount of cpu spent in a compactify_tuples
(called by PageRepareFragmentaion). Most of time were spent in qsort of
itemidbase items.

Ah, I played with this too a couple of years ago, see https://www.postgresql.org/message-id/546B89DE.7030906%40vmware.com, but got distracted by other things and never got around to commit that.

itemidbase array is bounded by number of tuples in a page, and
structure is simple, so specialized version could be a better choice.

Attached patch adds combination of one pass of prefix sort with
sort for larger array and shell sort for smaller array.
Insertion sort and shell sort are implemented as macros and could be

Cool! Could you compare that against the bucket sort I posted in the above thread, please?

At a quick glance, your "prefix sort" seems to be the the same algorithm as the bucket sort that I implemented. You chose 256 buckets, where I picked 32. And you're adding a shell sort implementation, for small arrays, while I used a straight insertion sort. Not sure what these differences mean in practice.

- Heikki

Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:

Reply via email to