Re: Small improvement to compactify_tuples

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
> simple
> 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
> itemIdSortData
> structure is simple, so specialized version could be a better choice.
>
> Attached patch adds combination of one pass of prefix sort with
> insertion
> sort for larger array and shell sort for smaller array.
> Insertion sort and shell sort are implemented as macros and could be
> reused.

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